Skip to content
Optimal Lab

System design · interactive

Merkle trees: find what's different

Two replicas each hold 8 blocks. Instead of sending every block to compare, each builds a tree of hashes: leaves hash the blocks, parents hash their children. Compare roots, and only walk down where hashes differ.

Replica A

b868
5017c9df
532d988cea007d33
872286c66708d06c36adf40c9c486ed3
alicebobcaroldaveerinfrankgraceheidi

Replica B

e595
5017c192
532d988c8eb27d33
872286c66708d06c36ad214d9c486ed3
alicebobcaroldaveerinfrank2graceheidi

compared 7 hashes · blocks to sync: 6

Dashed: never compared. With a million blocks and one difference, about 40 comparisons instead of a million.

Roots differ. Follow only the mismatched branches down to block 6.

Replica B

Step 3 of 4

  1. 1

    Hash the blocks

    Each leaf is the hash of one block of data.

    leaf = hash(block)

  2. 2

    Hash pairs up to a root

    Each parent hashes its two children. The root summarises everything: change any byte and the root changes.

    parent = hash(left + right)

  3. 3

    Walk down only where it differs

    Matching subtrees are skipped entirely. Work grows with the number of differences × log n.

    Red: hashes that differ.

  4. 4

    Where you meet them

    Cassandra and DynamoDB repair replicas this way; Git and blockchains prove content; certificate transparency logs prove inclusion.

    A short path of hashes proves one block is in the tree.

In production

Tools and technologies

Merkle trees verify and sync data everywhere.

Not tied to one language — use these names when you search docs or design a system.