Блоки, Merkle root и связывание хешем

Транзакции есть. Теперь упакуем их в блок и свяжем блоки в цепь, которую нельзя переписать незаметно. Тут наконец заработают два кирпича из урока про хеши и деревья Меркла. И тут же всплывёт требование, без которого консенсус невозможен: детерминированная сериализация.

Идея

Блок состоит из двух частей. Заголовок мал и фиксирован: ссылка на родителя, корень Меркла транзакций, время, высота, сложность и nonce. Тело это список транзакций. Хитрость в том, что хешируется только заголовок, а к телу он привязан одним полем merkle_root. Поэтому id блока это 32 байта, сколько бы транзакций ни лежало внутри.

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

Детерминированная сериализация

Прежде чем что-то хешировать, надо превратить структуру в байты. И тут кроется правило, на котором держится весь консенсус: разные узлы считают хеш блока независимо и обязаны получить один и тот же результат. Значит, у байтов не должно быть ни малейшей свободы.

Тут развилка, которую стоит проговорить, а не проскочить. Можно было взять готовое: serde с bincode или protobuf, и не писать ни строчки кодека. Но у готовых форматов сериализация это деталь реализации: байтовое представление может поменяться с версией библиотеки, флагом конфигурации или порядком полей в структуре. Для обычного сервиса это мелочь, а у нас байты это часть консенсуса: они обязаны быть детерминированы до последнего бита и не меняться никогда. Поэтому пишем свой плоский кодер и контролируем формат сами, как в уроках Rust про кодирование битиков и проектирование игрового протокола: целые фиксированной ширины как есть, переменные длины как varint, всё в строго заданном порядке. Цена решения честная: свой кодек надо тестировать самому (roundtrip-тесты, обрезанные буферы, мусор на входе), и обратная совместимость не достаётся бесплатно, любое изменение формата это хард-форк сети.

Сам write_varint мы уже видели в прошлом уроке, когда собирали подписываемые байты транзакции. Теперь он дома, и рядом с ним второй помощник для полей переменной длины:

/// Кодирует u64 как LEB128 varint (семь бит на байт, старший бит это
/// «продолжение»). Маленькие числа занимают один байт.
pub fn write_varint(out: &mut Vec<u8>, mut value: u64) {
    loop {
        let mut byte = (value & 0x7F) as u8;
        value >>= 7;
        if value != 0 {
            byte |= 0x80;
        }
        out.push(byte);
        if value == 0 {
            break;
        }
    }
}

/// Дописывает байтовый блок с префиксом длины. Так декодер знает границу,
/// не угадывая её по разделителю.
pub fn write_bytes(out: &mut Vec<u8>, bytes: &[u8]) {
    write_varint(out, bytes.len() as u64);
    out.extend_from_slice(bytes);
}

Важная деталь: мы никогда не сериализуем HashMap напрямую. У хеш-карты нет порядка, а порядок тут часть контракта. Состояние всегда выводится из упорядоченной истории блоков, а не пишется как есть. Это прямое следствие требования детерминизма из прошлого урока.

Дерево Меркла в деле

В заголовок не лезут все транзакции, туда кладут один корень Меркла, который их фиксирует. Поменяй любую транзакцию, корень изменится. Это прямое продолжение урока про хеши и деревья Меркла, теперь оно встаёт на место.

const LEAF_PREFIX: u8 = 0x00;
const NODE_PREFIX: u8 = 0x01;

/// Хеш листа: префикс домена плюс сами байты.
fn hash_leaf(data: &[u8]) -> Hash {
    let mut buf = Vec::with_capacity(1 + data.len());
    buf.push(LEAF_PREFIX);
    buf.extend_from_slice(data);
    Hash::of(&buf)
}

/// Хеш внутреннего узла из пары детей.
fn hash_node(left: &Hash, right: &Hash) -> Hash {
    let mut buf = [0u8; 1 + 32 + 32];
    buf[0] = NODE_PREFIX;
    buf[1..33].copy_from_slice(&left.0);
    buf[33..].copy_from_slice(&right.0);
    Hash::of(&buf)
}

/// Корень Меркла по списку хешей листьев (id транзакций). Пустой список даёт
/// нулевой корень. На нечётном уровне последний узел дублируется (схема Bitcoin).
pub fn root(leaves: &[Hash]) -> Hash {
    if leaves.is_empty() {
        return Hash::ZERO;
    }
    let mut level: Vec<Hash> = leaves.to_vec();
    while level.len() > 1 {
        let mut next = Vec::with_capacity(level.len().div_ceil(2));
        for pair in level.chunks(2) {
            let left = pair[0];
            let right = if pair.len() == 2 { pair[1] } else { pair[0] };
            next.push(hash_node(&left, &right));
        }
        level = next;
    }
    level[0]
}

Обрати внимание на префиксы 0x00 для листа и 0x01 для узла. Это та самая защита доменов из урока про хеши: без неё дерево уязвимо к подмене, где внутренний узел выдают за лист. Разные домены, разные хеши.

И тут же честное признание про наш собственный код. Присмотрись: hash_leaf в пути блока не участвует. Листом дерева у нас выступает голый txid, уже готовый 32-байтовый двойной SHA-256 транзакции (увидишь ниже в merkle_root_of), без префикса 0x00. Не дыра ли это? В нашей схеме нет, и полезно понять почему. Внутренние узлы всё равно хешируются с префиксом 0x01 от ровно 65 байт, а txid это хеш сериализованной транзакции, которая по нашему формату не может весить 65 байт (одни адреса, ключ и подпись дают за сотню байт). Значит, предъявить внутренний узел как «транзакцию» и наоборот не выйдет: их прообразы не пересекаются. У Bitcoin, где ни префиксов, ни такой страховки нет, двусмысленность дерева выстрелила по-настоящему: дублирование нечётного хвоста позволило двум разным спискам транзакций дать один корень, и это стало уязвимостью CVE-2012-2459, мы разбирали её в уроке про хеши и деревья Меркла. Наше дерево дублирует хвост так же, как Bitcoin, поэтому та же двусмысленность списков есть и у нас; спасает то, что блок с дублированной транзакцией не пройдёт переход состояния (повторный nonce), а невалидные блоки мы не кешируем. А hash_leaf в модуле остаётся: он пригодится там, где листом будут произвольные байты, а не готовый хеш.

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