Skip to content

CONCEPT Cited by 1 source

Merkle tree

A Merkle tree is a binary tree of hashes in which every internal node is the hash of its two children's hashes. Named for Ralph Merkle's 1979 construction. Two properties make it the workhorse of distributed-systems integrity + reconciliation:

  1. Root hash uniquely identifies the whole dataset. Any single-byte change in any leaf bubbles up to a new root.
  2. Logarithmic diff — two replicas can find every differing leaf by exchanging O(log n) hashes, recursively descending into mismatching subtrees.

Why it matters for gossip

In anti-entropy gossip, two replicas must identify the keys on which they disagree. Naive anti-entropy transfers the whole dataset (as Demers-1987 described). Merkle trees collapse that to "exchange root hash → for each mismatching child, exchange its hash → recurse → transfer only the differing leaves".

From sources/2023-07-16-highscalability-gossip-protocol-explained:

"The techniques such as checksum, recent update list, and Merkle tree can be used to identify the differences between nodes to avoid transmission of the entire dataset and reduce network bandwidth usage."

Canonical deployments

  • Apache Cassandra — Merkle trees drive read-repair and anti-entropy repair; a cluster-wide nodetool repair is a Merkle-tree anti-entropy pass over the token ranges.
  • Amazon Dynamo — the original 2007 SIGOPS paper uses Merkle trees for inconsistency detection between replicas.
  • Riak — Merkle trees (via riak_core) for Active Anti-Entropy (AAE).
  • Git — every commit is a Merkle tree of trees of blobs; git diff across commits is a Merkle comparison.
  • Bitcoin / Ethereum — block bodies are Merkle trees; SPV clients verify transaction inclusion with an O(log n) Merkle proof without downloading the full block.
  • IPFS — Merkle DAG of content-addressed objects.
  • BitTorrent v2 — per-file Merkle trees for piece-level verification.

Structural variants

  • Binary Merkle tree — original Merkle construction.
  • Merkle Patricia trie — Ethereum's variant, a trie of hashed key-paths; supports efficient key-range proofs.
  • Merkle B-tree — B-tree with internal hashes; used in authenticated dictionaries.
  • Verkle tree — vector-commitment variant, shallower than Merkle, active research in Ethereum scaling.
  • Sparse Merkle tree — fixed-depth tree over a large key space; common in zk-rollup state commitments.

Seen in

Last updated · 319 distilled / 1,201 read