Merkle trees

Why it matters

Two replicas are supposed to hold the same ten million rows. Do they? Comparing every row costs ten million transfers. Comparing one hash of everything tells you whether they differ but not where. A Merkle tree gives the middle path: by exchanging hashes top-down, two nodes locate every differing range in a number of steps logarithmic in the data size and transfer only what differs. It is how replicated databases heal, how Git knows what changed, and how a client verifies that one record is in a set without downloading the set.

The idea

A Merkle tree (hash tree) hashes each data block to make the leaves, then hashes pairs of child hashes to make each parent, up to a single root hash that depends on every byte below it. Change one block and its leaf hash changes, so does its parent, and so on up to the root. Equal roots mean (with cryptographic certainty) identical data; different roots mean descending into the children whose hashes differ finds the changed blocks.

Anti-entropy between replicas

1. 1

   Build

   Each replica partitions its key range into buckets (say 2 to the 15 ranges), hashes the rows in each bucket to a leaf, and builds the tree. Trees are built per partition range so that nodes sharing a range compare like with like.
2. 2

   Compare roots

   Exchange root hashes. Equal: the replicas agree and the comparison is one hash. Different: proceed.
3. 3

   Descend

   Exchange the children of mismatching nodes, recursing only into subtrees that differ. For a handful of differing rows, this is a few dozen hashes rather than millions of rows.
4. 4

   Repair

   Stream the rows in the differing leaf ranges and reconcile (newest timestamp wins, or a merge function). Cassandra's repair, Dynamo's anti-entropy and Riak's active anti-entropy all do this.

The cost moves from the size of the data to the size of the difference, which is what you want when replicas are usually almost identical.

Inclusion proofs

To prove that a particular leaf is in a tree whose root a verifier trusts, provide the sibling hashes along the path from that leaf to the root: log n hashes. The verifier recomputes the path and checks that it reaches the trusted root. Certificate transparency logs let a browser verify that a certificate is in a public append-only log this way; blockchains let light clients verify that a transaction is in a block; software update systems verify a file against a signed root.

Content addressing

Git stores every file, directory and commit as an object named by its hash, and a directory's hash covers its children: a Merkle structure. Two repositories compare commit hashes and exchange only the objects one lacks; a changed file changes exactly the hashes on its path. IPFS, Nix and container image layers use the same idea: identical content has identical hashes, so it is stored and transferred once.

Design choices

Leaf granularity trades tree size against repair precision: more leaves mean more hashes to store and compute but less data transferred when a leaf differs. Trees are rebuilt or incrementally updated as data changes; Cassandra builds them on demand during repair, which is expensive and scheduled. Hash function choice matters only for integrity against adversaries (SHA-256 for proofs) versus accidental divergence (a fast hash suffices for anti-entropy). Ranges must be identically defined on both sides or every subtree mismatches.