Sign in

Merkle trees

Suggest an edit

You have a long list of things. Someone asks you "is this specific thing on your list?" You want to prove the answer is yes without sending them the whole list. You also want nobody to be able to forge a "yes" for anything not actually on it. The data structure that solves this is the Merkle tree.

Hashing in pairs gives a tree with one root

Take eight items, A to H. You want a single short value that summarises all eight, with two properties:

  1. Tamper-evident. Change any one of the eight items, and the summary changes, so nobody can swap an item secretly.
  2. Cheap to check a single item. A verifier shouldn't have to download all eight to confirm D is in the set.

The first thing to try is to hash the whole list: summary = hash(A || B || C || D || E || F || G || H). This solves property 1, because changing anything changes the hash. But it fails property 2. To verify that D is in the set, the verifier has to compute the hash of the entire concatenation, which means they need all eight items in the first place.

A better idea is to hash each item individually first, then hash the results in pairs, then hash those pair-hashes in pairs, and keep going until you're down to one value. The result is a tree, called a Merkle tree.

Merkle tree from leaves A-H up to a single Merkle rootEight items, A through H, are each hashed to form h(A) through h(H) at the bottom level. Pairs of hashes are combined and hashed again at each level up (h(AB), h(CD), h(EF), h(GH), then h(AB,CD) and h(EF,GH)), until only one Merkle root remains at the top. A B C D E F G H h(A) h(B) h(C) h(D) h(E) h(F) h(G) h(H) h(AB) h(CD) h(EF) h(GH) h(AB,CD) h(EF,GH) Merkle root

The items in the bottom row are called leaves. Each parent is the hash of the concatenation of its two children. The single value at the top is the Merkle root, and it's only 32 bytes regardless of how many items you started with.

For 8 leaves the tree has 4 levels and a total of 15 hashes. For 1,000 leaves it would have 11 levels and about 2,000 hashes. Doubling the number of leaves adds only one level, and this slow growth is what makes the structure efficient.

The root depends on every leaf

If you change one bit of D, then h(D) changes, then h(CD) changes, then h(AB,CD) changes, then the root changes. This is the avalanche effect from the hashing lesson: change one bit and the resulting hash looks completely different, and here that change propagates all the way up to the root. The root is a compact, tamper-evident commitment to the entire set of leaves.

Two parties can confirm they have the same set of items by exchanging just the root. If their roots match, every byte of every leaf is identical. If the roots differ by even one bit, something somewhere on the tree differs. They don't have to compare the leaves directly.

A proof for one item is the sibling hashes on its path

Suppose you're the verifier and you know only the Merkle root. Someone else, the prover, has the whole tree and wants to convince you that item D is one of the leaves. They send you a short sequence of hashes called a Merkle proof. For D in our 8-leaf tree, the proof is three hashes: h(C), h(AB), and h(EF,GH).

Merkle proof path for leaf D in an 8-leaf Merkle treeEight leaves A to H are hashed and paired upward through h(AB), h(CD), h(EF), h(GH) and further pairs until they reach the Merkle root. The highlighted path shows that proving D only needs h(C), h(AB), and h(EF,GH) combined with D's own hash chain up to the root. A B C D E F G H h(A) h(B) h(C) h(D) h(E) h(F) h(G) h(H) h(AB) h(CD) h(EF) h(GH) h(AB,CD) h(EF,GH) Merkle root

The red solid nodes (h(C), h(AB), h(EF,GH)) are the proof: the sibling hashes that the verifier needs but cannot compute on their own. The red dashed nodes show what the verifier can compute themselves once they have D and the proof.

The verification:

  1. The verifier knows D (the item being proved) and the root (already trusted). They receive the proof: three hashes.
  2. They compute h(D) themselves from D.
  3. They concatenate h(C) from the proof with their own h(D) and hash the result, producing h(CD).
  4. They concatenate h(AB) from the proof with h(CD) and hash again, producing h(AB,CD).
  5. They concatenate h(AB,CD) with h(EF,GH) from the proof and hash one more time, producing a value.
  6. If that final value equals the root they already trusted, D is in the set. If it doesn't, the proof is rejected.

Three hashes travel from the prover. The verifier does four hash operations: one to turn D into h(D), then three more to combine up the path to the root. The other seven items are never sent. For a tree with 1,000 leaves, the proof would be 10 hashes. For a tree with one billion leaves, the proof would still only be 30 hashes.

The verifier doesn't need to trust the prover. If the prover sends a wrong sibling hash, the final computed value won't match the root, and the proof fails. If the prover lies about which item they're proving (claims D was in the set when it wasn't), they can't construct a sequence of hashes that rolls up to the trusted root without breaking the hash function itself. This is the hash function's collision resistance: finding two different inputs that produce the same hash is computationally infeasible, so the prover cannot forge a path that leads to the real root.

Someone still has to store every item and the tree above them to produce a proof on request. A proof also shows only that an item is in the set, and a rejected proof does not show that the item is absent.

Bitcoin puts one Merkle root in every block

Not every participant in a blockchain network can afford to download everything. They need a way to ask "is my piece in there?" and get a cheap, verifiable answer. Bitcoin is the first example in this course: every block carries a single 32-byte Merkle root that summarises every transaction inside it, as the Blocks and mining lesson shows. Wherever a system needs to commit to a large set with a small hash and prove individual membership efficiently, there's a Merkle tree underneath.