Merkle Trees (the Primitive)

The first three primitives gave us fingerprints (hashing), identities (keys), and authorization (signatures). The fourth solves a scaling problem: a block can hold thousands of transactions, but a block header is a fixed ~80 bytes. How do you commit to all of them in one tiny, fixed-size field? A Merkle tree is the answer — and the same structure lets a phone prove a transaction is in a block without downloading the block.

This page frames Merkle trees as a cryptographic primitive. For how the root rides in the header and powers light clients, see Merkle Trees & SPV; to build a proof by hand, see Verify a Merkle Proof.

The construction: hash pairs until one remains

Take the transaction ids, hash them two at a time, then hash the results two at a time, and keep going until a single hash is left — the Merkle root.

   root = H( H(AB) ‖ H(CD) )                    ← goes in the block header
            ╱            ╲
      H(AB)=H(a‖b)    H(CD)=H(c‖d)
        ╱   ╲            ╱   ╲
      a=H(A) b=H(B)   c=H(C) d=H(D)              ← leaf = double-SHA-256 of each tx
       │     │         │     │
      txA   txB       txC   txD

(In Bitcoin every node here is double SHA-256, and pairs are concatenated in internal byte order.) Change one bit of one transaction and its leaf hash changes, which changes its parent, its grandparent, and so on up to the root — so the single 32-byte root is a tamper-evident commitment to the entire transaction set. This is the avalanche effect put to structural use.

By the numbers — why the tree beats a flat hash

A flat “hash of all transactions concatenated” would also detect tampering — but to prove one transaction is included you’d have to ship all of them. The tree’s payoff is the proof size. To prove tx A is under the root, you reveal only the sibling hashes along one path:

   block of  1,024 txs  →  proof =  10 hashes  (log₂ 1024)  ≈  320 bytes
   block of  4,096 txs  →  proof =  12 hashes               ≈  384 bytes

Proof size grows as log₂(n), not n. Double the transactions and a proof gets one hash longer. That logarithm is what lets an SPV wallet on a phone verify inclusion against an 80-byte header instead of a multi-megabyte block.

Under the hood — the odd-node rule, and the CVE it caused

A binary tree wants pairs, but a level can have an odd number of nodes. Bitcoin’s rule: duplicate the last hash to make the count even. Simple — but that very shortcut hid a real bug.

It actually happened — CVE-2012-2459

Because the last hash is duplicated, a block with an odd row could be re-arranged by an attacker into a different transaction layout that hashed to the same Merkle root. A node receiving the mutated block would compute a matching root but fail other checks and could mark the block — including its valid twin — as permanently invalid, a denial-of-service that could split nodes off the network. The 2012 fix made nodes detect the duplicated-hash structure and reject it as malformed rather than mutated. The lesson echoes signature malleability: two different inputs must never map to the same commitment, or “verify by hash” quietly breaks.

The thread

How does this help untrusting strangers agree on one ledger? It makes verification cheap enough to be universal. A stranger doesn’t have to trust your claim that “transaction X is in block 800,000” — and they don’t have to download the whole block to disprove it either. They check a handful of hashes against a root they already trust from the header. By collapsing “is this in the set?” from a megabyte-scale download to a few hundred bytes, the Merkle tree lets even the weakest device participate in checking the one ledger. That completes Part 1’s four primitives — hashing, keys, signatures, and trees — the entire cryptographic toolkit the rest of the book arranges into Bitcoin.

The architect’s lens

• Why does it exist? To commit to thousands of transactions inside the block header’s single fixed ~32-byte field — folding the whole tx set into one Merkle root by hashing pairs until one hash remains.
• What problem does it solve? Cheap, universal inclusion proofs: revealing only the log₂(n) sibling hashes along one path proves a tx is under the root, so a 1,024-tx block needs ~10 hashes (~320 bytes) instead of the whole block — the foundation of SPV.
• What are the trade-offs? Proof size is O(log n), not O(1), and the odd-node “duplicate the last hash” rule once let two different layouts hash to the same root (CVE-2012-2459, a DoS) — whenever two inputs map to one commitment, “verify by hash” quietly breaks.
• When would you choose differently? A flat hash-of-everything is simpler and just as tamper-evident if you’ll never need to prove one item’s inclusion without shipping the rest — the tree only earns its complexity when light clients must check membership against a header.
• What breaks if I remove it? The header could no longer commit to all transactions in fixed space, and a phone could no longer verify “tx X is in block 800,000” without downloading the full block — light-client verification becomes impossible.

Check your understanding

1. Describe how a Merkle root is built from a block’s transaction ids, and why changing one transaction changes the root.
2. A flat hash-of-everything also detects tampering. What can a Merkle tree do that the flat hash cannot, and what is the cost saving in big-O terms?
3. For a block of 4,096 transactions, how many hashes are in an inclusion proof, and why?
4. What is Bitcoin’s rule for an odd number of nodes at a tree level, and what real vulnerability (CVE-2012-2459) did it enable?
5. Tie it back: which earlier primitive does the Merkle tree depend on entirely, and which property of it (from the hash-functions page) makes the root tamper-evident?

Show answers

1. Hash each tx (the leaves), then repeatedly hash adjacent pairs until one hash — the root — remains. Any change to a transaction changes its leaf, which propagates up every parent to the root, so the root commits to the exact transaction set.
2. It can prove a single transaction’s inclusion by revealing only the sibling hashes on its path (log₂ n hashes), instead of shipping all n transactions. Proof size is O(log n) vs O(n).
3. 12 hashes (log₂ 4096 = 12) — one sibling hash per tree level, and a 4,096-leaf tree is 12 levels deep.
4. Duplicate the last hash to make the count even. This let an attacker rearrange an odd row into a different layout with the same root (CVE-2012-2459), enabling a DoS where a node could reject a block and its valid twin. The fix rejects the duplicated-hash structure as malformed.
5. It depends entirely on hash functions. The property that makes the root tamper-evident is collision/second-preimage resistance plus the avalanche effect — you can’t find a different transaction set that yields the same root, and any change cascades to the top.