Merkle Trees

You've downloaded a 4 GB file from a server. How do you verify it arrived intact? You could hash the entire file and compare it to the server's hash. If even one bit changed, the hash won't match.

But now imagine a harder problem: you have two databases with 100 million records that should be identical. They're in different data centers. Some records might have drifted out of sync due to network issues, race conditions, or bugs. How do you find which records differ?

Option A: Transfer all 100 million records from one database to the other and compare row by row. Works, but you're transferring terabytes of data just to find a handful of mismatches.

Option B: Hash each record individually, send 100 million hashes across the network, and compare. Better, hashes are small, but you're still sending 100 million hashes.

Option C: Use a Merkle tree. Send a single hash (the root), compare it, and if it differs, drill down through the tree to identify exactly which records differ, transferring only O(log n) hashes instead of O(n).

Merkle trees are the reason Git can instantly tell you which files changed in a repository with millions of files. They're how Cassandra detects and repairs data inconsistencies across replicas. They're the integrity backbone of Bitcoin and Ethereum. They're beautifully simple, a binary tree where every leaf is a hash of a data block, and every internal node is a hash of its children.

A Merkle tree is a binary tree of hashes built bottom-up.

Step 1: Hash each data block individually.

Data blocks: [A] [B] [C] [D]
Leaf hashes: H(A) H(B) H(C) H(D)

Step 2: Hash pairs of leaf hashes to create parent nodes.

 H(AB) H(CD)
 / \ / \
 H(A) H(B) H(C) H(D)

Step 3: Hash the parent hashes to create the root.

 ROOT = H(ABCD)
 / \
 H(AB) H(CD)
 / \ / \
 H(A) H(B) H(C) H(D)

The root hash is a fingerprint of the entire dataset. If any single bit in any block changes, the root hash changes.

Detecting where the difference is:

Two nodes each have a copy of this tree. They compare root hashes. If the roots match, the data is identical. Done. If the roots differ:

1. Compare H(AB) and H(CD), one side at a time
2. Suppose H(AB) matches but H(CD) doesn't
3. Drill into H(CD), compare H(C) and H(D)
4. Suppose H(C) matches but H(D) doesn't
5. Block D is the one that differs, sync only block D

For a tree with N leaf nodes, you need at most O(log N) hash comparisons to find the differing blocks. With 100 million records organized into a Merkle tree, you need at most ~27 hash comparisons to pinpoint a mismatch, instead of comparing 100 million records.