Skip to content
Hashing · Data Structures

Merkle Tree Proofs

Build a tree, prove one leaf is in it with a handful of hashes, and verify it without the whole tree.

What you'll be able to do

  • Build a Merkle tree and explain what its root commits to.
  • Generate and verify an inclusion proof by hand — and say why it's only ⌈log₂ n⌉ hashes.
  • Explain where the trusted root must come from, and why a proof without that is worthless.
  • Break two real constructions: the second-preimage forgery (no domain separation) and CVE-2012-2459 (odd-node duplication).
  • Verify a consistency proof and state exactly what "append-only" does and doesn't guarantee.
  • Verify a real Certificate Transparency entry — production data, in this page, offline.

1 · What is a Merkle Tree?

A Merkle tree is a binary tree of hashes. Each leaf holds the hash of one data block; each internal node holds the hash of its two children concatenated. The single hash at the top — the root — commits to every leaf at once: change any byte of any block and the root changes.

This demo uses real SHA-256 via the browser's WebCrypto API, with RFC 6962 domain separation:

  • leaf hash = SHA-256(0x00 ∥ data)
  • node hash = SHA-256(0x01 ∥ left ∥ right)

A small 4-leaf tree (leaf order is left to right; the root sits on top):

2 · Build a Tree

Add or remove data blocks. The tree (and its root) rebuilds live. Click any leaf to select it for a proof.

Presets:

Merkle root (SHA-256)

3 · Generate a Proof

An inclusion proof (audit path) is the minimal set of sibling hashes needed to recompute the root from one leaf. Pick a leaf below (or tap one in the tree above) to highlight its proof.

  • selected leaf
  • proof (sibling) hash — the only hashes a verifier receives
  • recomputed path to the root

4 · Verify a Proof

A verifier recomputes the root from only the leaf and the proof, then checks it against the trusted root. Try tampering — the verdict flips to REJECTED the moment anything changes.

Walk it:
Predict

You flip one bit of a single sibling hash deep in the proof. Will verification still pass?

No. That bit changes the parent hash, which changes its parent, all the way up — the recomputed root no longer matches. One bit anywhere in the leaf or proof is enough to break it. This is the avalanche property of SHA-256 plus the tree's hash chaining.

Proof steps (editable)

Each row is one sibling hash. Flip a bit to see verification fail.

Recomputation trace

The verifier recomputes the root from the leaf up. Expand “show bytes” on any line to see the exact input to SHA-256 — leaves are 0x00 ∥ data, nodes are 0x01 ∥ left ∥ right.

Where does the trusted root come from?

Everything above assumed the verifier already holds the right root. That assumption is the entire security model. A proof only ties a leaf to some root — if the person making the claim also hands you the root, they can build a tree around any lie.

Predict

Mallory invents a fake transaction, builds her own Merkle tree around it, and sends you the leaf, the proof, and the root. Does verification pass?

Yes — perfectly. The hashes are all real SHA-256 and all self-consistent. Verification can never tell you the root is the agreed-upon one; only the channel that delivered the root can. That's why Bitcoin roots live in mined block headers and CT roots come as signed tree heads that clients gossip and compare.

Self-check

What does a verifier need to confirm a leaf is in the tree?

5 · Why It Scales (Logarithmic Proofs)

Proof size grows with the height of the tree, not its width — that's ⌈log₂ n⌉ hashes for n leaves. Drag to see how a proof stays tiny even as the dataset explodes.

Prove it on a real tree

Build an actual SHA-256 tree in your browser and verify a proof against it — no shortcuts.

In the wild: a Bitcoin block with ~3,000 transactions (~1.5 MB) needs a 12-hash proof — 384 bytes — for an SPV wallet to confirm a payment. Certificate Transparency logs hold billions of certificates and still prove any one of them in 32 hashes ≈ 1 KB — you'll verify a real one in section 8.

Self-check

A tree commits to one billion leaves. Roughly how many hashes are in one inclusion proof?

6 · Security: Why the 0x00 / 0x01 Prefixes Matter

Without domain separation, a leaf is hashed exactly like an internal node — so an attacker can take an internal node's two child hashes, glue them into a 64-byte "leaf", and prove inclusion of a leaf that never existed. This is the classic second-preimage (leaf-node confusion) attack. RFC 6962's 0x00/0x01 prefixes put leaf and node hashes in separate spaces and shut it down.

Turn the toggle off to see the forgery accepted (vulnerable), then back on to see it rejected. The main builder above always keeps domain separation on.

A second pitfall: odd-node handling (CVE-2012-2459)

When a level has an odd number of nodes, something must be done with the lone node. Bitcoin duplicated it (hash(x ∥ x)), which let an attacker pad a block's transaction list with a repeated last transaction to get the same Merkle root — mutating blocks and splitting the network. RFC 6962 promotes the lone node unchanged, which has no such collision.

Self-check

What actually prevents the second-preimage (leaf-as-node) forgery?

7 · Consistency (Append-Only) Proofs

Everything above proves inclusion — that one leaf is in the tree. A consistency proof answers a different question that logs care about: is the old tree of size m an exact prefix of the new tree of size n — i.e. did the log only append, never rewrite history? This is the guarantee Certificate Transparency is built on.

Why it works: the old root is stitched together from a few complete subtrees — and those exact subtrees still sit, byte-for-byte, inside the new tree. The proof hands the auditor just enough subtree roots to rebuild both the remembered old root and the claimed new root. If the same handful of hashes can reproduce both, nothing before entry m changed.

The log (a growing list of certificates; shaded = the old size-m prefix):

  • the old size-m tree (shaded prefix)
  • proof hash inside the prefix — rebuilds the old root, then reused for the new one
  • proof hash in the appended region — completes the new root
Predict

The log operator deletes one early entry but keeps appending, so the log is still growing. Will the consistency proof still verify?

No. "Append-only" means every old entry must stay at its exact position. A deletion shifts every later leaf one slot left, which changes every subtree containing them — the remembered old root can no longer be rebuilt from the new tree's subtrees. Same for reordering: same contents, different positions, different hashes. Try both below.

Attack the log:

Every attack keeps the auditor's remembered old root but alters the log the operator presents — the consistency proof then fails, exposing the tampering. Entries marked ≠ are where the presented log differs from the original. Honest limit: tampering is only caught if it touches entries the old root committed to (positions < m) — a change entirely after position m is invisible to this old root, which is why auditors keep requesting fresh signed tree heads.

Self-check

You hold last month's root (size m) and today's root (size n). What does a valid consistency proof convince you of?

8 · Verify a REAL Certificate Transparency Entry

Everything so far used toy data. This section uses none. Below is a real entry from Google's Argon2026h1 CT log — a Let's Encrypt certificate that actually protects a real website — together with the real audit path the log served, pinned so it verifies offline forever. The verifier here is the same RFC 6962 construction you've been stepping through: SHA-256(0x00 ∥ leaf), SHA-256(0x01 ∥ L ∥ R).

One production difference: a real log doesn't send left/right flags with the proof. The verifier derives each side from the entry's index and the tree size by walking the index's bits (RFC 9162 §2.1.3.2) — expand the steps below to see the derived sides.

In production the verifier also checks the log's ECDSA signature over the tree head (the signed tree head); here that head is pinned into the page instead. The tree had 2,807,499,968 certificates when fetched — and one flipped bit anywhere in this 1,033-byte certificate entry still breaks all 32 hashes above it.

9 · Where Merkle Proofs Are Used

Bitcoin & Ethereum

Block headers commit to a Merkle root of all transactions. An SPV / light client proves a transaction is in a block with a short branch — no need to download the full chain. Caveat if you try this at home: Bitcoin's construction differs from this lab's — double SHA-256, byte-reversed txids, no domain separation (hence section 6's CVE), so its roots won't match an RFC 6962 tree.

Git

Every commit, tree, and blob is content-addressed by hash, forming a Merkle DAG. The commit hash pins the entire history; any tampering changes every descendant hash.

Certificate Transparency

CT logs (RFC 6962 — the exact construction here) publish a Merkle root so anyone can prove a certificate was logged and that the log is append-only. Section 8 verifies a real entry from a live log.

Stateless / light clients

Merkle (and Verkle) proofs let a client check that an account balance or state value is part of a committed root without holding the whole state tree.

10 · Recap: The Two Proofs, Side by Side

Inclusion proof (§3–4)Consistency proof (§7)
Question answered"Is this leaf in the tree?""Is the old tree an untouched prefix of the new one?"
Verifier holdsthe leaf + the trusted rootthe old root + the new root
Prover sendssibling hashes up the leaf's paththe subtree roots that rebuild both roots
Size⌈log₂ n⌉ hashes≈ log₂ n hashes
Who runs itlight clients, SPV wallets, browserslog auditors and monitors
What it can NOT proveabsence, order, or that the root is the agreed-upon one (§4)that entries are valid, or that any specific entry is present

Test yourself (no peeking)

  • Sketch a 4-leaf tree from memory and mark exactly which hashes a proof for leaf 2 contains.
  • Explain to a rubber duck why the 0x00/0x01 prefixes are load-bearing and not decoration.
  • State the one thing verification can never tell you about the root — and where real systems get it instead.
  • Say what breaks if a log deletes an entry, in terms of leaf positions and subtree hashes.

Further reading