Хеш-функции и деревья Меркла

Блокчейн это реплицированная машина состояний поверх криптографии, и самый нижний её слой это хеш. Адрес, идентификатор блока, связь блока с предыдущим, корень множества транзакций: всё это хеши. Разберём свойства криптографического хеша, три рабочие лошадки (SHA-256, Keccak, BLAKE3), HMAC и деревья Меркла, и всё закодим на Rust руками, без чёрных ящиков.

Идея

Хеш-функцию ты уже встречал в уроке про алгоритмы и структуры данных: там она раскидывала ключи по корзинам хеш-таблицы, и от неё хотели одного, чтобы била равномерно и быстро. Криптографический хеш решает другую задачу, и требования к нему жёстче на порядок.

Криптографическая хеш-функция берёт сообщение любой длины и выдаёт дайджест фиксированной длины: SHA-256 всегда отдаёт 256 бит, хоть на пустой вход, хоть на гигабайтный файл. От неё требуют три свойства стойкости, и каждое описывает атаку, которую она обязана сделать невозможной на практике.

1. Устойчивость к прообразу (preimage resistance). Зная дайджест h, нельзя найти такое сообщение m, что hash(m) = h. Функция односторонняя: вычислить вперёд легко, обратить нельзя. Именно на этом стоит хранение паролей и адреса в блокчейне.
2. Устойчивость ко второму прообразу (second preimage resistance). Зная конкретное сообщение m1, нельзя найти другое m2, дающее тот же дайджест. Иначе подменишь транзакцию, сохранив её хеш.
3. Устойчивость к коллизиям (collision resistance). Нельзя найти любую пару разных сообщений с одинаковым дайджестом. Это сильнее второго прообраза: тут злоумышленник волен выбирать обе стороны.

Коллизии существуют всегда: входов бесконечно много, выходов ровно 2^256, по принципу Дирихле какие-то входы обязаны столкнуться. Стойкость не в их отсутствии, а в вычислительной невозможности их найти. Атака дней рождения говорит, что коллизию в 256-битном хеше ищут примерно за 2^128 попыток, а не 2^256. Поэтому 256 бит дают 128 бит запаса по коллизиям, и этого хватает: 2^128 это около 3,4·10^38 попыток. Даже вся сеть Bitcoin, которая суммарно считает порядка 10^21 хешей в секунду, потратила бы на такой перебор около десяти миллиардов лет, сопоставимо с возрастом вселенной. А знаменитое сравнение с числом атомов в наблюдаемой вселенной (их порядка 10^80) прибереги для полного пространства 2^256: вот оно с числом атомов действительно одного масштаба.

Четвёртое свойство не про стойкость, а про поведение: лавинный эффект. Поменяй во входе один бит, и в среднем половина битов выхода перевернётся. Дайджест не намекает, насколько входы похожи: «attack at dawn» и «attack at dusk» дают полностью несвязанные хеши. Это и делает хеш честным отпечатком: либо совпал целиком, либо это другой документ.

SHA-256, Keccak и BLAKE3

В Web3 живут три семейства, и выбор между ними не вкусовщина, а история и устройство.

SHA-256 из семейства SHA-2 это рабочая лошадь Bitcoin: идентификатор блока и дерево транзакций считаются двойным SHA-256. Внутри это конструкция Меркла и Дамгора. Работает она так. Сообщение добивают до кратного 512 битам: ставят один бит 1, потом нули, а в самый конец кладут 64-битную длину исходного сообщения. Получившиеся блоки по 512 бит идут по очереди через сжимающую функцию: на входе у неё текущее 256-битное состояние (накопитель) и очередной блок, на выходе новое 256-битное состояние. Стартует накопитель с фиксированных констант, а финальное состояние после последнего блока и есть дайджест. Эта схема строго последовательная: блок N нельзя посчитать, пока не готово состояние после блока N минус 1. Отсюда и потолок скорости, и слабость length extension, к которой мы вернёмся в разделе про HMAC.

Keccak-256 это то, что в Ethereum называют просто keccak256 и чем считают адреса и хеши транзакций. Тонкость, на которой спотыкаются все: Ethereum зафиксировал исходный Keccak ещё до того, как NIST стандартизировал его как SHA-3, а при стандартизации (FIPS 202, 2015 год) NIST поменял один байт набивки. Keccak дописывает к сообщению байт-разделитель 0x01, а SHA3-256 ставит 0x06 (это домен-разделитель, чтобы две функции на один вход никогда не совпали). Из-за единственного байта keccak256 Ethereum и SHA3-256 дают совершенно разные дайджесты, это не одно и то же. На пустом входе видно сразу: keccak256("") начинается с c5d2460186f7..., а sha3_256("") с a7ffc6f8bf1e.... Перепутаешь их в коде Ethereum, и адреса с хешами транзакций разъедутся со всей сетью. Внутри обе используют одну губчатую конструкцию (sponge): данные впитываются (absorb) в большое 1600-битное состояние блоками, потом из него выжимают (squeeze) выход. Наружу отдают лишь часть состояния, поэтому length extension к губке неприменима по построению.

BLAKE3 это современный быстрый хеш: внутри он строит дерево Меркла из самого сообщения. Вход режется на куски по 1024 байта, каждый кусок хешируется независимо, потом хеши кусков сводятся в двоичное дерево к корню. Независимые куски и дают распараллеливание: на один поток BLAKE3 держит около 8 ГБ/с против примерно 0,4 ГБ/с у чисто программного SHA-256, а на многих ядрах разрыв растёт ещё линейно. Оговорка для честности: на современных процессорах с аппаратными расширениями SHA-NI SHA-256 разгоняется до 1,5 или даже 2,5 ГБ/с, так что на одном ядре разрыв сжимается с порядка до нескольких раз, но параллелизм по ядрам остаётся козырем только BLAKE3. На коротких входах (около килобайта и меньше) дерево не успевает развернуться, и преимущество скукоживается. Его берут там, где хеширование на горячем пути и важна скорость, а наследие Bitcoin или Ethereum не диктует выбор.

На Rust все три это крейты семейства RustCrypto с одинаковым интерфейсом, трейтом Digest. Заведём проект и зависимости:

# Cargo.toml
[dependencies]
sha2 = "0.10"
sha3 = "0.10"
blake3 = "1"
hex = "0.4"

use sha2::{Digest, Sha256};
use sha3::Keccak256;

fn main() {
    let msg = b"attack at dawn";

    // SHA-256: построй, скорми данные, забери дайджест.
    let mut hasher = Sha256::new();
    hasher.update(msg);
    let sha = hasher.finalize();          // [u8; 32] внутри GenericArray
    println!("sha256:   {}", hex::encode(sha));

    // Keccak-256 (тот, что в Ethereum) живёт за тем же трейтом Digest.
    let keccak = Keccak256::digest(msg);  // короткая форма без new/update
    println!("keccak256: {}", hex::encode(keccak));

    // BLAKE3 со своим API, но идея та же.
    let b3 = blake3::hash(msg);
    println!("blake3:   {}", b3.to_hex());
}

Поменяй dawn на dusk и запусти снова: все три дайджеста сменятся целиком, ни одного общего префикса. Это и есть лавинный эффект руками.