Foundation of Blockchain — Merkle Trees

1.3 — Foundation of Blockchain: Merkle Trees

Recall first. From §1.2: a hash seals data and is second-preimage resistant. How could you “seal” a thousand transactions into a single hash stored in a block, so that changing any one transaction changes that single hash? Sketch an idea before reading.

Reference-book anchor

Primary reference: Blockchain Technology, Chapter 4, §4.4.4.2 — converted Markdown lines 2790–2801.¹

The book’s anchor covers the Bitcoin Merkle tree as a compact transaction commitment and contrasts it with Ethereum’s modified tree structures. Bitcoin-specific construction details are labeled below; other protocols may define different trees and odd-leaf rules.

Why Merkle trees exist

A block may contain thousands of transactions. We need one hash in the block header that commits to all of them — and we need to verify a single transaction’s inclusion without downloading all of them. The Merkle tree (Ralph Merkle, 1980)² solves both. Nakamoto adopted it explicitly so old blocks could be pruned yet still verifiable.³

What a Merkle tree is

A Merkle tree (a.k.a. hash tree) is a binary tree where:

• Leaves = H(transaction) (the txid).
• Each internal node = H(left_child || right_child) — in this binary construction, the hash of its two children concatenated.
• The root (top node) = the Merkle root, a single hash that commits to every leaf.

                Merkle Root = H(H01 || H23)
               /                        \
         H01 = H(H0||H1)          H23 = H(H2||H3)
        /            \            /            \
   H0=H(Tx0)    H1=H(Tx1)   H2=H(Tx2)    H3=H(Tx3)

In Bitcoin the hash used is double SHA-256: H(x) = SHA256(SHA256(x)).⁴⁵

How it is built (the algorithm)

Given leaves h1, h2, ..., hn (already H(tx)):

1. Pair adjacent hashes: p_i = H(h_{2i-1} || h_{2i}).
2. If the count is odd, apply the protocol’s specified rule. In Bitcoin, duplicate the last hash and pair it with itself: h_{n+1} = h_n.
3. Repeat on the new row until one hash remains — that is the Merkle root.
4. If only one transaction exists, its txid is the Merkle root.

Refresher — binary tree. A binary tree node has at most two children. Bottom-up means we compute leaves first, then parents, then grandparents, up to the root. Height of a tree with n leaves is ⌈log2 n⌉.

Why the odd-node duplication matters

Bitcoin’s rule (duplicate the last hash when a row is odd) is protocol-specific and unusual. It had a real security consequence: it enabled CVE-2012-2459, where two different transaction lists could yield the same Merkle root. Modern nodes detect this (they flag when two identical hashes would be combined) and reject such blocks.⁶ Other blockchain protocols may choose a different rule. Lesson: protocol details have security weight.

The killer feature: Merkle proofs (SPV)

This is the deepest, most exam-relevant idea. A light client (Simplified Payment Verification, SPV) stores only block headers, not full blocks. To prove transaction Tx3 is in the block, a full node sends a Merkle proof: just the sibling hashes on the path from Tx3 up to the root.

For Tx3 above, the proof is {H2, H01}:

compute  H23  = H(H2 || H3)
compute  root = H(H01 || H23)
check    root == merkle_root in the block header

The light client needs only ~log2(n) sibling hashes, plus the position (left/right) of each sibling, not all n transactions. For a million transactions, that’s ~20 hashes instead of a million. This is logarithmic verification — the whole reason the tree is efficient.³⁵

Beginner intuition. The Merkle root is like a “fingerprint of the whole block’s transactions.” A Merkle proof is like showing “here are the few puzzle pieces needed to rebuild that exact fingerprint from my one transaction.” If the fingerprint matches the header’s, the transaction is included in that committed tree.

What a Merkle proof does — and does not — prove

A valid proof establishes inclusion: a particular leaf contributes to the root recorded in a particular block header. By itself it does not prove that the transaction is valid, that its sender owns the inputs, that the block is on the canonical chain, or that the payment has reached finality. A Bitcoin SPV client relies on header-chain and consensus evidence for those additional judgments.³

The sibling’s position matters. H(left || right) is generally different from H(right || left), so a proof must tell the verifier whether each supplied sibling goes on the left or right as the path is rebuilt.

Worked example — build a Merkle root

Transactions A, B, C (three leaves). For this Bitcoin-style construction, compute the root step by step using H = SHA256d.

d1 = H(A)
d2 = H(B)
d3 = H(C)
d4 = H(C)                 # odd count → duplicate C
d5 = H(d1 || d2)
d6 = H(d3 || d4)
root = H(d5 || d6)

Check: if you changed C to C', then d3 and d4 both change, so d6 changes, so root changes. The block header’s stored root would no longer match — tamper detected.⁵

Exercise

A block has 8 transactions. (a) How many hashes are in the Merkle proof for one transaction? (b) If an attacker flips one bit in Tx5, which hashes in the tree change?

Exam lens

Diagram to reproduce: draw four transaction leaves, pair adjacent hashes upward, label the single top hash Merkle root, and mark the sibling path for one chosen transaction.

Likely distinction:

• A hash chain links records sequentially: changing one record breaks later links.
• A Merkle tree commits many records to one root and supports an inclusion proof with logarithmic size.

Calculation pattern: for n = 2^k leaves, a proof needs k sibling hashes. For non-powers of two, state the protocol’s rule; Bitcoin duplicates the final hash at an odd level, while other systems may define a different rule.

Common trap: a Merkle root commits to transaction data and order as encoded by the tree; it is not a list of transactions, a digital signature, or proof that the transaction is economically valid.

Rapid revision

• Can I compute a root from four leaves without skipping a level?
• Can I explain why odd-leaf handling is protocol-specific?
• Can I count the hashes and directions in an inclusion proof?
• Can I state exactly what SPV proves and what it still trusts?

Key takeaways

• A Merkle tree hashes transactions pairwise upward into one Merkle root.
• The root commits to all transactions; tampering with any one changes the root.
• Merkle proofs let light clients verify inclusion in O(log n) hashes (SPV).
• Bitcoin uses double-SHA256 and duplicates the last hash on odd rows (a quirk with a known CVE).
• This is the structural foundation that makes blocks both compact and verifiable.

Sources