LESSON 27.1
Merkle trees
Build a tree of hashes whose root fingerprints a whole data set. How comparing roots finds differences in logarithmic time, and how short proofs show one item belongs to a set.
7 min read
Two servers each hold 100 million records. Are they the same? Sending all the data to compare is expensive. Sending one hash of everything tells you whether they differ, but not where. A Merkle tree gives both: a single fingerprint for the whole set, and a way to narrow down differences by exchanging only a few hashes.
Building one
- Split the data into blocks (file chunks, or ranges of keys) and hash each block. These are the leaves.
- Hash pairs of leaf hashes together to form the next level up.
- Repeat until one hash remains: the root.
Any change to any block changes its leaf hash, its parent, and so on up to the root. Two trees with the same root (using a cryptographic hash like SHA-256) hold the same data.
Finding differences
- Exchange root hashes. Equal? Done: the data matches.
- If not, exchange the children's hashes and descend only into subtrees that differ.
- At the leaves, exchange the actual differing blocks.
- Tree depth
- ~20 levels
- One differing block
- ~20 hash comparisons along one path
- d differing blocks
- roughly d × 20, often less where paths share
- Identical data
- 1 comparison
The tree turns "compare everything" into work proportional to the number of differences, times the depth.
Proofs of inclusion
A Merkle tree also proves that one block belongs to a set with a known root, without sending the set. The proof is the list of sibling hashes along the path from the block to the root. The verifier hashes the block, combines it with each sibling in turn, and checks that the result equals the trusted root.
Verify downloads from untrusted peers
- Check each chunk as it arrives against a trusted root
- Need the root from a trusted source
Pick it when: BitTorrent, IPFS, peer-assisted CDNs, package mirrors.
Tamper-evident logs
- Anyone can check an entry is in the log, and that the log only grew
- Requires publishing roots
Pick it when: Certificate Transparency, audit logs, ledgers.
Light clients
- Verify one transaction without the whole chain
- Trust in the block headers
Pick it when: Blockchains: Bitcoin's SPV clients.
Design choices
- Leaf granularity: smaller blocks find differences more precisely but make bigger trees. Key-range leaves of a few thousand keys are common for databases; file chunks of a few MB for sync.
- Hash function: cryptographic (SHA-256, BLAKE3) when data may be adversarial; a fast non-cryptographic hash is fine for detecting accidental drift between your own replicas.
- Incremental updates: when one block changes, only the hashes on its path need recomputing: O(log n) work.
Try it
Peer-assisted Content Distribution HLD
Fetch content from untrusted peers safely.