You have two replicas, each holding 500 GB of data. One has drifted out of sync. How do you find the differences without shipping a terabyte across the network? You build a Merkle tree: a tree where every leaf is a hash of a data block, and every internal node is a hash of its children's hashes. Compare roots — if they match, the datasets are identical. If they differ, walk down only the branches that disagree.

The magic is the asymmetry: equality is proven with a single hash comparison, but inequality is localized in O(log n) steps. You only transfer the actual data for the blocks that truly differ.

How it's built:

• Partition data into fixed-size chunks (e.g., 4 KB blocks, or key ranges in a database).
• Hash each chunk → these become leaf nodes.
• Concatenate sibling hashes and hash again → parent nodes.
• Repeat until you have a single root hash.

Real-world example: Cassandra and DynamoDB use Merkle trees for anti-entropy repair. When two replicas need to reconcile, they exchange root hashes first. If equal, done — zero data transferred. If not, they walk the tree, exchanging only the subtree hashes on each level. For a 1 TB table partitioned into 1 million 1 MB chunks, finding the one corrupted chunk takes ~20 hash comparisons (log₂ 1,000,000) instead of streaming the whole table.

Git uses the same idea — every commit is a Merkle tree of file hashes. That's why git fetch can determine what objects you're missing with a handful of hash exchanges. Bitcoin uses it so light clients can verify a transaction is in a block without downloading the block.

The bandwidth rule of thumb: for n chunks with d differences, naive sync transfers all n chunks; Merkle sync transfers roughly d × log(n/d) chunks worth of hashes plus the d differing chunks. When d is small relative to n, the savings are enormous. When d approaches n, you're better off just shipping everything.

Watch out for:

• Chunk boundaries matter. Inserting one byte at the start shifts every block, making everything look different. Content-defined chunking (rolling hashes, like rsync uses) handles this.
• Tree depth vs. chunk size tradeoff. Smaller chunks = more precise diffs but bigger trees. Tune for your access patterns.
• Build cost is O(n). You're hashing everything. Cache the tree and update incrementally on writes.