Back to blog
cryptographydata-structuresblockchain

Merkle Inclusion Proofs

A visual, step-by-step guide to proving a transaction lives in a block

01The Merkle Tree

A block contains 8 transactions. Each is hashed to form a leaf, then pairs are hashed together upward until a single Merkle Root remains. This root is stored in the block header.

L₀a3f1L₁b7c2L₂d9e4L₃f0a5L₄c8b3L₅e2d6L₆91f7L₇4a08H₀₁5c2dH₂₃8e7fH₄₅3b9aH₆₇d1c4H₀₋₃f6e3H₄₋₇7a5bMR2d8f
Leaf (transaction hash)
Internal node
Merkle Root

02Pick a Transaction to Prove

Select a transaction below. The proof consists of the sibling hashes (orange) needed at each level. The verification path (green) shows what you recompute.

L₀a3f1L₁b7c2L₂d9e4L₃f0a5L₄c8b3L₅e2d6L₆91f7L₇4a08H₀₁5c2dH₂₃8e7fH₄₅3b9aH₆₇d1c4H₀₋₃f6e3H₄₋₇7a5bMR2d8f
Verification path (you compute)
Sibling (provided in proof)
Not needed
Proof π for T₀
Leaf: L₀ = a3f1

Siblings needed:
  Level 0: s₀ = L₁ = b7c2, b₀ = 0 (I'm left)
  Level 1: s₁ = H₂₃ = 8e7f, b₁ = 0 (I'm left)
  Level 2: s₂ = H₄₋₇ = 7a5b, b₂ = 0 (I'm left)

Proof size: 3 hashes × 32 bytes = 96 bytes

03Step-by-Step Verification

Walk through the verification algorithm. At each level, combine the running hash with the sibling in the correct order.

Start: x₀ = L₀ = a3f1
Level 0: b₀ = 0 (left child → hash goes first)
x₁ = H( x₀ ‖ b7c2 ) = 5c2d
Level 1: b₁ = 0 (left child → hash goes first)
x₂ = H( x₁ ‖ 8e7f ) = f6e3
Level 2: b₂ = 0 (left child → hash goes first)
x₃ = H( x₂ ‖ 7a5b ) = 2d8f
✓ Check: x₃ = 2d8f == MR = 2d8f
Proof accepted! ✓

04Why This Works

The core insight: Each sibling hash is the missing ingredient needed to recompute the parent at that level. The proof is literally “here are the neighbors you need to rebuild the root.”

04aCompleteness

If the transaction is truly in the tree and the prover gives correct siblings, the verifier recomputes exactly the same parent hashes the tree originally computed — all the way up to the root. It's a simple induction on levels.

04bSoundness

To fake a proof for a transaction not in the tree, the attacker would need to find different inputs that produce the same hash at some internal node — i.e., a hash collision. Under standard cryptographic assumptions, this is computationally infeasible.

Above: a fake leaf (red) would need to “repair” the mismatch at some level — requiring a hash collision (✕).

05The Logarithmic Payoff

A proof needs only one sibling per level. For a tree of N transactions with depth ⌈log₂ N⌉, the proof is tiny:

8 transactions
3
sibling hashes
1,024 transactions
10
sibling hashes
1,000,000 tx
20
sibling hashes
Proof size
O(log N)
hashes · 32 bytes each
SPV clients (like mobile Bitcoin wallets) use this to verify transactions by downloading only block headers (~80 bytes) + a tiny Merkle proof, instead of the entire block.