# Merkle trees

> Hash trees that find which parts of two large datasets differ by comparing a few hashes.

Concept · Data structures for scale · https://levelcode.org/concepts/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.

```text
                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](https://levelcode.org/concepts/quorums)).
- **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](https://levelcode.org/concepts/gossip-protocols).