To check whether a large file or dataset arrived correctly, you can compare one checksum for the whole thing.

That works when everything matches. But when the checksum does not match, it only tells you "something changed." It does not tell you which part is wrong, so the system may have to fetch or compare everything again.

A Merkle tree solves this by hashing data in chunks. It hashes each block, then hashes those hashes in pairs, and keeps going until only one top hash remains.

That top hash tells you whether the whole dataset matches. The tree below it helps you quickly find which block is different when it does not match.

This is why Merkle trees show up in systems like Git, Bitcoin, Cassandra, and DynamoDB.

This chapter explains what a Merkle tree is, how it helps systems verify data quickly, how to build one, and where it is used in real systems.

Consider a distributed database that stores copies of the same data on multiple nodes. The copies are there for reliability, but they can drift apart after failures, network issues, or delayed replication.

The challenge is simple: how do we quickly find out whether one copy differs from another?

The Naive Approach: Compare Everything

The simplest solution is to compare every piece of data between nodes:

This works, but it is expensive. If you have 1 million data blocks, you may need to transfer and compare 1 million hashes just to find one bad block.

A Better Approach: Single Hash

What if we compute a single hash of all the data?

Now we only compare one hash. But there is a problem: if the hashes do not match, we know something is different, but not what. We may still have to fall back to comparing everything.

The Solution: Merkle Trees

Merkle Trees give us both: