Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 41 ยท Cryptography Foundations

Merkle Trees and Proofs of Inclusion

Build a Merkle tree in Python, handle odd leaf counts, compute the root and verify a proof of inclusion with only log n hashes. See how light clients use it.

A block may contain thousands of transactions. How can a phone wallet check that one particular transaction is inside a block without downloading all of them? And how can a block header commit to every transaction while staying tiny? The answer is a Merkle tree, named after Ralph Merkle: a binary tree built from hash pointers.

In this lesson you will build a Merkle tree in Python, compute its root, create an inclusion proof for one transaction, and verify it with just a handful of hashes.

The idea

Start with the transactions as leaves. Hash each one. Then hash neighboring pairs together to form the next level up, repeating until a single hash remains: the Merkle root.

flowchart BT
    T1["tx1"] --> H1["H1 = hash(tx1)"]
    T2["tx2"] --> H2["H2 = hash(tx2)"]
    T3["tx3"] --> H3["H3 = hash(tx3)"]
    T4["tx4"] --> H4["H4 = hash(tx4)"]
    H1 --> H12["H12 = hash(H1 + H2)"]
    H2 --> H12
    H3 --> H34["H34 = hash(H3 + H4)"]
    H4 --> H34
    H12 --> R["Merkle root = hash(H12 + H34)"]
    H34 --> R

Four transactions are summarized by one root; changing any leaf changes every hash on the path up to the root.

The root goes into the block header. Because it depends on every leaf, changing, removing or reordering any transaction changes the root and therefore the block's hash.

Building the root

Python Compute a Merkle root

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Editing one amount or merely swapping two transactions yields a completely different root. Hashing the concatenation left + right also means that order matters.

Odd numbers of leaves

If a level has an odd count, there is no sibling for the last hash. Bitcoin's rule is to duplicate the last hash and pair it with itself, which the code above does. Other designs promote the lone node unchanged or pad with a fixed value. Which rule you use matters: it must be identical everywhere, and the duplicate rule has a known quirk, where two different transaction lists can produce the same root (for example [a, b, c] and [a, b, c, c]). Bitcoin handles this by other validity rules; when designing your own, be aware of it.

Python The duplicate-last quirk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Inclusion proofs

Suppose a light client knows only the block header, which contains the Merkle root. A full node claims that tx3 is in that block. The node does not need to send all transactions. It sends only the sibling hashes along the path from tx3 up to the root, the Merkle proof. For four leaves that is two hashes.

The client hashes tx3, combines it with the first sibling (knowing whether the sibling is on the left or right), then with the second, and compares the result with the root from the header.

Python Create and verify a proof

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The proof only works for the genuine transaction in the right position. Any other item hashes to a different value and the final comparison fails.

Why this is efficient

For n leaves, a proof contains about log2(n) hashes. That grows very slowly:

Python Proof size versus block size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A billion transactions need only 30 hashes, or 960 bytes. That is why light clients (often called SPV clients in Bitcoin) can run on phones: they download block headers, which are around 80 bytes each in Bitcoin, and request a small proof only for transactions that concern them.

Light clients still trust that the header chain is the real one (proof of work gives them evidence) but they do not trust the full node supplying the proof. A dishonest node cannot produce a valid proof for a transaction that is not there, as that would require a hash collision. A node can withhold information, though, which is a reason to ask several peers.

Other uses

  • State commitments. Ethereum stores account data in a variant of a Merkle tree (a Merkle Patricia trie), so one root summarizes all balances and contract storage.
  • Git and file sync. Directory trees are hashed upward so that tools can quickly find which files changed.
  • Certificate transparency, databases and package registries use Merkle trees to prove that a log only grows.

A good test of understanding: if you change one leaf in a tree of 1,000 leaves, how many hashes must be recomputed? Only the path to the root, about 10, plus the leaf itself. Trees make updating cheap as well as verifying.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Merkle root in a block header commit to?

    Each parent hash depends on its children, so the root depends on every leaf and on their positions.
  2. 2. How many hashes does an inclusion proof need for a tree with 1,024 leaves?

    A proof holds one sibling per level, which is log2(1024) = 10 hashes.
  3. 3. What does a verifier do with a Merkle proof?

    Recomputing the path from the leaf to the root and comparing it with the root in the header is the entire check.
  4. 4. Why can a light client trust a proof from an untrusted node?

    Only the genuine transaction in its real position hashes up to the committed root, unless the attacker can find a collision, which is infeasible.

Summary

  • A Merkle tree hashes transactions as leaves, then hashes pairs upward until a single Merkle root remains.
  • The root in the block header commits to all transactions and their order.
  • Odd levels need a rule (such as duplicating the last hash), and the rule must be identical everywhere.
  • An inclusion proof is the list of sibling hashes along the path, with size about log2(n).
  • Light clients use headers and proofs to verify transactions without storing whole blocks.

Next: Public-Key Cryptography Basics, where you meet the keys that authorize spending.