Один хеш, вместо миллиона проверок: пишем Merkle Tree на Go с нуля

Представьте: у вас есть база из миллиона транзакций. Клиент спрашивает: «Моя транзакция точно в блоке?» Вы можете отдать ему все миллион записей для проверки. Или отдать 20 хешей по 32 байта - и он сам математически докажет, что его транзакция на месте. Без доверия. Без скачивания всего блока. За O(log N)

Merkle tree - структура данных на которая являеться Bitcoin, Git, IPFS и Certificate Transparency. Посмотим как она работает и напием свою реализацию на Golang c ДЖЕНЕРИКАМИ йоу

Итак рассмотрим ситуацию:
У нас есть транзакции

A: "Alice → Bob: 10 BTC"
B: "Bob → Charlie: 3 BTC"
C: "Charlie → Dave: 7 BTC"
D: "Dave → Alice: 1 BTC"

Примитивный подход - захешировать всё вместе:
RootHash = SHA256(A + B + C + D)

Клиент хочет проверить, что транзакция A входит в блок. Что ему для этого нужно? Все четыре транзакции целиком. Только тогда он сможет пересчитать хеш и сравнить с RootHash

При миллионе транзакций это означает скачать весь блок :<
Что откровенно говоря - не приятно...

Решение: Дерево хешей

Каждый хеш - это хеш всех его детей:
H(AB) = SHA256(H(A) + H(B))
H(CD) = SHA256(H© + H(D))
Root = SHA256(H(AB) + H(CD))

Теперь, чтобы доказать, что A в дереве клиенту нужны только H(B), H(CD)
Он вычесляет H(AB) и Root

Сравинивает с известным RootHash. Если совпало - A блок 100% в дереве. Два хеша вместо 4-х транзакций. А при МИЛЛИОНЕ элементов - 20 хешей :3

Это и есть Merkle proof или proof of inclusion

Реализация на go :>

Интерфейс узла

Нужно начать с общего интерфейса. Дерево состоит из узлов, у которого есть дети

type Node[T any] interface {
    String() string
    StringIndent(level int) string
    AddChild(Node[T])
    GetBytes() []byte
    GetChildren() []Node[T]
}

T - это дженерик

Листья

Лист хранит оригинальное значение и его хеш:

type Leaf[T any] struct {
    Value     T
    ValueHash []byte
}

func NewLeaf[T any](value T, hash hash.Hash) (*Leaf[T], error) {
    hashedValue, err := valueToHash(value, hash)
    if err != nil {
        return nil, err
    }
    return &Leaf[T]{Value: value, ValueHash: hashedValue}, nil
}

Но тут проблема T иммеет тип any. Вопрос как его кешировать, ничего умнее не пирдумал как использовать cbor для этого дела

func valueToHash(value any, hash hash.Hash) ([]byte, error) {
    encoded, err := cbor.Marshal(value)
    if err != nil {
        return nil, err
    }
    hash.Reset()
    hash.Write(encoded)
    return hash.Sum(nil), nil
}

Почему CBOR, а не JSON? JSON не гарантирует порядок ключей в map. Одинаковые данные могут дать разные байты это значит разные хеши. CBOR детерминирован по спецификации (RFC 8949)

Бинарный узел (ака узел бинарного дерева)

type BinaryNode[T any] struct {
    Value []byte
    Right Node[T]
    Left  Node[T]
}

Дерево и фабрика хешей

type BinaryTree[T any] struct {
    newHash func() hash.Hash
}

func NewBinaryTree[T any](newHash func() hash.Hash) *BinaryTree[T] {
    return &BinaryTree[T]{newHash: newHash}
}

Тут мы используем фабрику а не передаем hash.Hash тк он имеет свое внутреннее состояние, которое меняется при каждом Write

Теперь каждая операция создаёт свежий hasher:

tree := merkletree.NewBinaryTree[string](sha256.New) // передаём функцию, не результат вызова

Proof of Inclusion

Это самая сильная сторона в Merkle tree возможность доказать, что элемент есть в дереве, передав лишь несколько хешей. Без скачивания всех данных

Идея
Допустим, клиент хочет убедиться, что транзакция A есть в дереве. У него на руках:

- хеш транзакции A (он её знает)
- RootHash (публичный, есть в заголовке блока)

Ему не нужно всё дерево. Нужны только хеши соседей на пути от листа к корню:

Генерация proof: собираем соседей

Идём от корня вниз, ищем целевой лист. На каждом уровне запоминаем хеш соседнего узла - того, который нам не нужен для спуска, но понадобится для пересчёта

А потом шлем proof и теперь поднимается снизу вверх. Если в итоге получился RootHash - элемент точно в дереве

Почему это эффективно

Proof растёт логарифмически. Миллиард элементов - 30 хешей, меньше килобайта. Именно поэтому SPV-кошельки Bitcoin работают на телефоне, не скачивая 500+ ГБ блокчейна

Где это используется

Bitcoin - Transaction root в заголовке блока. SPV-клиенты проверяют транзакции без скачивания блока
Ethereum - State trie, transaction trie, receipt trie - три Merkle-дерева в каждом блоке
Git - Tree objects - каждый коммит ссылается на дерево хешей файлов
IPFS - Content addressing - хеш файла = корень Merkle tree его чанков
Certificate Transparency - Публичный лог SSL-сертификатов, аудируемый через Merkle proofs

Итого

Merkle tree - это структура данных, которая решает одну задачу и решает её идеально: доказать принадлежность элемента к набору данных за O(log N), не раскрывая остальные данные

Исходный код: GitHub