Merkle Trees

Зачем нужно знать

Merkle tree (hash tree) — это структура, в которой каждый внутренний узел равен hash(left_child || right_child), а листья — hash(data_block). Корневой hash — компактный отпечаток всего набора данных.

Знать её надо потому, что она закрывает три рутинные системные задачи, которые без неё стоят либо часов CPU, либо терабайт трафика:

• Anti-entropy / repair между репликами. Cassandra nodetool repair, DynamoDB, Riak, Apache Kafka KRaft — все они синхронизируют расходящиеся реплики не передачей всех данных, а сравнением Merkle-деревьев. Без неё anti-entropy = переслать весь dataset.
• Proof of membership за O(log N). Bitcoin SPV-клиент, Certificate Transparency, IPFS, BitTorrent v2 — все они доказывают «этот элемент действительно в наборе» через ~30 хешей вместо миллиардов.
• Tamper-detection. Git, ZFS/Btrfs, AWS QLDB, Sigstore Rekor — изменение любого байта в листе ломает root. Это базовый кирпич content-addressable storage и аудит-логов.

Если ваша система реплицирует данные между регионами, синхронизирует state между нодами, или хочет доказать клиенту факт включения без передачи всего набора — без Merkle вы будете изобретать его заново и хуже.

Mental model

«Сжимаем N элементов в один hash рекурсивно. Получаем два бонуса: (1) один корневой hash верифицирует весь набор; (2) O(log N) сиблинг-хешей доказывают, что конкретный лист в дереве — не зная остального дерева.»

Ключевая интуиция: Merkle tree превращает задачи на наборах данных в задачи на дереве хешей размера log N. Compare two datasets → compare two roots (1 сравнение). Differ → спускаемся в children, пока не найдём расхождение. Bandwidth — O(D + log N), где D — число расходящихся блоков, а не O(N).

Второй угол: Merkle root — это криптографический commit к состоянию. Когда blockchain хранит в header один hash вместо тысяч транзакций, это и есть commit. Когда Git хранит tree object с hash директорий — тоже commit. Любая система, где нужно «здесь моё текущее состояние, верь мне» — кандидат на Merkle.

Что показывает диаграмма

На канвасе — упрощённый Cassandra-стиль anti-entropy:

• Две реплики (Replica A, Replica B) в разных регионах. У каждой свой data-нода и in-memory Merkle tree, построенное поверх данных.
• Repair coordinator посередине — оркестрирует процесс синхронизации (роль nodetool repair, либо distributed scheduler типа Cassandra Reaper).
• Edges показывают физические связи: data → merkle (построение дерева), coordinator → merkle (выборка хешей), node-a → node-b (стриминг дельт после нахождения расхождений).

Это сознательно простая топология — две реплики и один координатор. В реальном Cassandra-кластере координатором становится одна из нод, а Merkle деревья строятся per-token-range. Идея та же.

Сценарии и что они учат

1. Detect divergence — partition + heal. Старт: реплики синхронны, root = X на обеих. Затем partition; writes к A проходят, B изолирована. После heal сети — root A изменился, root B остался прежним. Учит: Merkle tree — это состояние, а не процесс. Расхождение видно по одному сравнению hashes, независимо от того, какого размера сами данные.

2. Merkle comparison — O(log N) bandwidth. Координатор берёт top-hash обеих реплик, видит расхождение, спускается level-by-level: левое поддерево совпадает → не смотрим туда, расхождение справа → углубляемся. На leaf-уровне находим конкретный token range R. Учит: bandwidth ≈ log N хешей, не N строк. На триллион строк — около 40 hashes (≈1.3 KB) против миллиона+ строк.

3. Stream deltas — only divergent rows. Координатор приказывает A передать строки из range R к B. B применяет, пересчитывает Merkle, координатор верифицирует новый root. Учит: Merkle не реплицирует данные — он находит, что реплицировать. Сам стриминг идёт классически (range scan + apply).

4. Real uses — Bitcoin SPV + BitTorrent. Bitcoin block header содержит Merkle root всех транзакций; SPV-клиент не качает полный block, но получает Merkle proof (~10 хешей) и доказывает, что транзакция X включена в block Y. BitTorrent v2: каждая piece имеет Merkle leaf; corrupt piece детектится hash mismatch и реквестится у другого peer. Учит: тот же примитив работает и для anti-entropy, и для proof-of-membership, и для tamper-detection — это одна структура, три задачи.

Trade-offs (развёрнутые ADR)

ADR-001: Merkle tree vs naive full-replica comparison.

• Контекст: надо синхронизировать две реплики после network partition. Naive: качать всё с одной и diff'ать. На терабайтных датасетах это часы и гигабайты трафика, при том что расходится обычно <1%.
• Решение: построить Merkle tree на обоих сторонах, рекурсивно сравнивать сверху вниз. Передаются только хеши O(log N) плюс реально расходящиеся блоки O(D).
• Цена: нужно держать или строить tree (память + CPU); на mutation надо инвалидировать путь от листа к корню. Build O(N) хешей.
• Когда оправдано: D << N (типично для healthy systems после короткого partition). При D ≈ N (рестарт ноды с нуля) дешевле bulk-copy.

ADR-002: Binary vs k-ary tree.

• Контекст: при глубоком дереве (бинарное, миллиард листьев → высота 30) каждый proof = 30 хешей, и repair-проход — 30 уровней рекурсии.
• Решение в Ethereum Patricia: 16-ary (hex) trie — короче пути, но больше sibling-хешей на уровне. В Verkle trie — 256-ary с vector commitments, proofs сжимаются с десятков KB до сотен байт.
• Цена: k-ary даёт более сложную имплементацию и (для plain hash) больше sibling-хешей в proof. Verkle требует vector commitments (KZG) — дороже компьютеишн, но дешевле сеть.
• Когда оправдано: k-ary — когда proof-size доминирует над compute (light clients, on-chain storage gas). Binary — когда главное простота и build-throughput.

ADR-003: Standard Merkle vs Sparse Merkle Tree.

• Контекст: нужно доказывать не только membership, но и non-membership («ключа K в state нет»).
• Решение: Sparse Merkle Tree — дерево фиксированной огромной высоты (256 для 256-bit keys); большинство branches — default value. Non-membership = доказать, что путь к K ведёт к default leaf.
• Цена: naive implementation = O(256) хешей на каждый proof. Нужны оптимизации: default subtree caching, sparse encoding. Иначе compute убивает выгоду.
• Когда оправдано: state-trees блокчейнов (Ethereum), Certificate Transparency, любой случай, где нужны proofs of absence. Для anti-entropy SMT избыточен.

ADR-004: SHA-256 vs SHA-1 vs Blake3.

• Контекст: выбор hash-функции определяет security и performance дерева.
• Решение: SHA-256 — текущий дефолт (Bitcoin, CT, Cassandra). Blake3 — заметно быстрее на современных CPU при сравнимой security. SHA-1 — избегать для security-critical, доказаны collision attacks (SHAttered 2017).
• Цена: SHA-1 в Git — историческое legacy, переход на SHA-256 идёт годами. Blake3 — экосистема меньше, библиотек меньше.
• Когда оправдано: SHA-256 для blockchain/audit-logs (regulatory); Blake3 — внутренние deduplication, anti-entropy где security важна, но не critical (атакующий не может подменить блоки в кластере).

ADR-005: Per-range Merkle vs single tree on entire dataset.

• Контекст: в Cassandra данные шардированы по token-ranges. Один tree на весь dataset был бы 100GB+ только из хешей.
• Решение: строить tree per-token-range; repair гранулярен по range, можно репарить параллельно и инкрементально.
• Цена: надо выбирать гранулярность range. Слишком мелкие — много build-overhead и фрагментированный repair. Слишком крупные — больше передаём при divergence, медленнее compare.
• Когда оправдано: всегда, как только dataset не помещается в комфортный single-tree budget (примерно 10–100M ключей).

Реальные системы

• Cassandra nodetool repair — Merkle tree per token range, обмен root между replicas, стриминг diverged ranges. Основа anti-entropy с 2010.
• DynamoDB / Riak — internal anti-entropy через Merkle, скрыто от пользователя.
• Bitcoin — Merkle root транзакций в block header с 2009. SPV-клиенты живут на Merkle proofs.
• Ethereum — Merkle Patricia Trie для state, transactions, receipts. Gas-cost оптимизации — отдельная индустрия.
• Git — каждый commit ссылается на tree object, который ссылается на blob и sub-trees — это Merkle DAG. Content-addressing built-in.
• IPFS — content-addressed Merkle DAG; sub-DAGs переиспользуются между файлами.
• BitTorrent v2 (BEP 52) — Merkle hashes per piece, верификация на лету.
• Certificate Transparency (RFC 9162) — Merkle-логи сертификатов, операторы доказывают inclusion браузерам.
• Sigstore Rekor / Google Trillian — generic verifiable Merkle log infrastructure.
• AWS QLDB — immutable ledger с Merkle proofs для cross-region и audit.
• ZFS / Btrfs — Merkle-like checksumming блоков для detection bit-rot.
• Apache Kafka KRaft — controller state синхронизация.

Anti-patterns

• Merkle для маленьких данных (KB-уровень). Build-overhead и log-передача не оправданы. Отправьте hash от всего набора или сам набор.
• Mutate leaf без rebuild path. Любая мутация листа должна обновить все хеши от листа до корня. Иначе root перестаёт соответствовать данным, и все proofs ломаются молча.
• SHA-1 в security-critical Merkle. Git исторически на SHA-1, и это известный долг. Не повторяйте в новых системах — SHAttered (2017) практически демонстрирует collision.
• Игнорировать padding для нечётных N. Bitcoin CVE-2012-2459 — дублирование последнего листа без проверки позволяло атакующему форжить proof для несуществующих транзакций. Padding должен быть детерминированным и проверяемым.
• Build Merkle на live-mutating данных без snapshot. Если данные меняются во время построения дерева, root не соответствует никакому консистентному состоянию. Снапшот (SSTable, MVCC view, copy-on-write) обязателен.
• Reverse edges для ответов в архитектуре. Если рисуете Merkle-anti-entropy и хотите показать «ответ от B → coordinator», используйте reverse-анимацию по существующему edge, не создавайте новый edge coordinator ← B.
• Naive Sparse Merkle Tree без default-subtree caching. Honest 256-уровневая рекурсия = 256 × hash на каждый proof. Без кеша default-поддеревьев это убивает производительность.

Когда НЕ использовать

• Малые datasets (N < ~1000 элементов). Дешевле передать все хеши или весь набор. Merkle добавляет сложность без выигрыша по bandwidth.
• Frequently-mutating hot data, где не нужны proofs. Если просто хотите синхронизировать счётчик — CRDT или vector clocks дешевле; пересчёт пути от листа к корню на каждый write дорог.
• Однонаправленная репликация без verify. Если у вас leader → follower и follower доверяет leader безусловно — log-shipping или WAL-streaming проще и быстрее. Merkle нужен, когда обе стороны равноправны и могут расходиться.
• Когда главный bottleneck — compute, а не bandwidth. Anti-entropy через Merkle экономит трафик, но добавляет hash-compute. На CPU-bound системах с дешёвой сетью (одна стойка, 100 Gb/s) bulk-diff может выиграть.
• Когда proof-size критичен, а deплатформа поддерживает vector commitments. Для blockchain light-clients Verkle Trie (KZG-commitments) даёт меньшие proofs ценой более тяжёлого crypto — для новых проектов рассмотрите вместо классического Merkle.

Дальше читать

• Merkle, R. (CRYPTO '87) — оригинальная работа: A Digital Signature Based on a Conventional Encryption Function.
• Mastering Bitcoin (Antonopoulos), Ch. 7 — Merkle trees в Bitcoin, SPV, block headers.
• Ethereum Yellow Paper — спецификация Patricia Merkle Trie.
• Vitalik Buterin — Verkle Trees (vitalik.eth.limo/general/2021/06/18/verkle.html) — что приходит после Merkle для on-chain state.
• Cassandra repair docs (cassandra.apache.org/doc/latest/cassandra/operating/repair.html) — самая прозрачная industrial-grade имплементация Merkle anti-entropy.
• Dynamo paper (2007) — раздел про anti-entropy, исток Cassandra/Riak подхода.
• RFC 9162 — Certificate Transparency v2 — формализация Merkle-логов для PKI.
• BEP 52 — BitTorrent v2 — Merkle hashes per piece вместо SHA-1 всего torrent.
• Pro Git, Ch. 10 Internals (git-scm.com/book/en/v2/Git-Internals-Git-Objects) — Git как Merkle DAG.
• DDIA (Kleppmann), Ch. 5 — упоминание anti-entropy в контексте replication.
• Cross-links: [CONCEPT]probabilistic-data-structures (предыдущий шаг по структурам данных), [CONCEPT]replication (где anti-entropy живёт), [CASE]twitter-system-design и [CASE]instagram-system-design (cross-region replication, где Merkle anti-entropy в проде).