Merkle Trees

A tree of hashes whose root fingerprints a whole data set, so two copies can find their differences by comparing a few hashes, and anyone can prove one item belongs with a short proof.

Overview

A Merkle tree is a tree of hashes. Each leaf holds the hash of one block of data, and each parent holds the hash of its children's hashes. The hash at the top, the root, depends on every block below it: change one byte anywhere and the root changes.

That single property does two useful jobs. Two machines holding copies of the same data can compare roots, and if the roots differ, walk down the tree comparing only the branches that differ, until they find exactly which blocks disagree. And anyone who trusts a root can check that one block belongs to the data with a short proof: the sibling hashes along its path, one per level.

Ralph Merkle filed the patent for this in 1979 and described it in a 1987 paper on digital signatures. Today it sits inside Amazon's Dynamo design and Cassandra's repair, Git's object store, Bitcoin's block headers and the Certificate Transparency logs that browsers rely on.

What you will be able to do

  • Build a Merkle tree, update it after a change, and say what each step costs.
  • Explain how two replicas use one to find and repair their differences.
  • Produce and check an inclusion proof, and explain why it is small.
  • Choose the leaf size, the hash function and the tree shape for a real system.

Key concepts

  • Hash of hashes
  • Root hash
  • Anti-entropy repair
  • Top-down comparison
  • Inclusion proof
  • Incremental update
  • Leaf and node prefixes
  • Merkle DAG
  • Content addressing

Interview questions

  • What is a Merkle tree, and why does it make comparing replicas cheap?
  • How does Cassandra use Merkle trees in repair, and why must repair run regularly?
  • How does an inclusion proof work, and how big is it?
  • What happens to the tree when one record changes?
  • Why does Git count as a Merkle structure?
  • How would you choose the leaf size for a replica-repair tree?
  • Merkle tree or Bloom filter: which would you use, and for what?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio