Merkle trees

A Merkle tree is a tree of hashes. Leaves hold hashes of data blocks (or key ranges); each parent holds the hash of its children's hashes; the root summarises everything. If any block changes, its hash changes, and so does every hash on the path up to the root.

                root = H(H12 + H34)
              /                     \
      H12 = H(H1 + H2)        H34 = H(H3 + H4)
       /         \              /        \
  H1=H(block1) H2=H(block2) H3=H(block3) H4=H(block4)

#Finding differences cheaply

Two replicas each build a Merkle tree over the same key ranges.

1. Compare roots. Equal → the datasets are identical; done, after exchanging one hash.
2. Not equal → compare the children, and descend only into subtrees whose hashes differ.
3. At the leaves, exchange only the ranges that actually differ.

For datasets of millions of keys with a handful of differences, this exchanges a few kilobytes of hashes instead of the data itself.

#Where they're used

• Anti-entropy in leaderless databases: Cassandra's repair and Dynamo-style systems use Merkle trees to find and fix divergent replicas (quorum reads and writes).
• Git: commits, trees and blobs form a Merkle structure, so identical directories share objects and any change produces a new commit hash.
• Content verification: BitTorrent and IPFS verify downloaded blocks against a trusted root hash; certificate transparency logs prove that entries are included without downloading the whole log.
• Blockchains summarise a block's transactions in a Merkle root.

#Trade-offs

Trees must be rebuilt or updated as data changes, which costs CPU and I/O, and they're only as fine-grained as their leaves: a large leaf range means re-sending a lot of data for one changed key. See also gossip protocols.