MASTERING-BITCOIN · Interactive Practice | Unit 12 · Video 3

32 Bytes to Rule Them All: Merkle Trees

IKey Concepts and Formulas

Concept	Formula / Rule	Description
Parent hash	$\text{Parent} = \text{SHA256}(\text{SHA256}(L \mathbin{\\|} R))$	Concatenate two 32-byte children, double-hash
Output size	Always 32 bytes	Regardless of how many transactions in the block
Proof size	$\lceil \log_2 N \rceil$ hashes	Sibling hashes needed for inclusion proof
Odd-count rule	Duplicate last hash, pair with itself	Keeps tree balanced (source of CVE-2012-2459)
SPV verification	Header (80 B) + Merkle path	Phones verify without full blocks

IIVisualization 1: Build a Merkle Tree

How does the tree grow as you add transactions?

Adjust the slider to change the number of transactions in the block. Notice how the tree height grows logarithmically — doubling the number of transactions only adds one level. No matter how many transactions, the root is always 32 bytes.

⚙ interactive visualization — coming to this page format soon

Notice: Each time you double the number of transactions, only one new level appears. Dashed red circles mark hashes that had to be duplicated to maintain pairs (the odd-count rule). The gold root at the top is always exactly 32 bytes — whether N = 2 or N = 16,000.

IIIVisualization 2: Proof Size Scales Logarithmically

Why can a phone verify a 4 MB block with under 1 KB of data?

An inclusion proof requires only the sibling hashes along the path from a leaf to the root — that's $\lceil \log_2 N \rceil$ hashes of 32 bytes each. Use the slider to see how proof size grows with block size.

⚙ interactive visualization — coming to this page format soon

Reflect: Try moving the slider from N = 16 to N = 16,000. The block grows 1,000× larger, but the proof grows from 4 hashes to only 14 hashes — less than 4× growth. This is the magic of logarithmic scaling that makes SPV wallets practical on mobile phones.

IVVisualization 3: Trace an Inclusion Proof

Which sibling hashes do you need to prove a transaction belongs?

Pick a transaction (A through P) in a 16-transaction block. The visualization highlights the path from your leaf to the root (green) and the sibling hashes (orange) you need to include in the proof.

⚙ interactive visualization — coming to this page format soon

Notice: No matter which of the 16 transactions you select, the proof always contains exactly 4 sibling hashes (because $\log_2 16 = 4$ ). The verifier recomputes each green path node by hashing it with its orange sibling, and finally checks the recomputed root against the one in the block header.

VQuiz Questions

Question 1

A Bitcoin block contains 1,024 transactions. How many sibling hashes are required to prove that any single transaction is included in the block?

✅ Correct! log₂(1024) = 10, so the proof needs 10 sibling hashes (320 bytes).

❌ Not quite. The proof size is logarithmic, not linear or fixed. Compute log₂(N).

Show solution

Solution:

The number of sibling hashes equals the tree depth, which is $\lceil \log_2 N \rceil$ .

$\log_2(1024) = 10$

So a verifier needs 10 sibling hashes (10 × 32 = 320 bytes) to reconstruct the path from any leaf to the root. This is the whole point of Merkle trees: proof size grows logarithmically, not linearly.

Question 2

A Bitcoin block has 5 transactions at the bottom level. According to Bitcoin's Merkle tree construction rules, what happens at the pairing step?

✅ Correct! Bitcoin duplicates the lone hash: H₅ pairs with H₅ to form a new parent.

❌ Not quite. Bitcoin doesn't reject odd counts or pad with zeros — it duplicates.

Show solution

Solution:

Bitcoin's rule for odd-count levels: duplicate the last hash and pair it with itself.

So with hashes $H_1, H_2, H_3, H_4, H_5$ , the pairing becomes:

$(H_1, H_2),\; (H_3, H_4),\; (H_5, H_5)$

This keeps the tree balanced (every internal node has two children) and lets the same hashing rule apply at every level. Unfortunately, this exact rule is what enabled CVE-2012-2459: the duplication creates collisions between blocks with different transaction lists but identical roots.

Question 3

True or False: If even one bit of a single transaction in a block changes, the Merkle root of that block will also change.

✅ Correct! A single bit flip propagates up the path and changes the root.

❌ Not quite. That's the whole purpose of a cryptographic commitment — any change is detectable.

Show solution

Solution:

True. This is the whole point of cryptographic commitments.

Changing one bit of a transaction changes its dSHA256 leaf hash (avalanche effect).
That leaf is concatenated with its sibling to form its parent — so the parent hash changes.
The change propagates up the path: every ancestor hash changes.
Therefore the root changes.

This is why a 32-byte root can "commit to" every byte of a 4 MB block: any tampering, anywhere, is detectable at the root.

Question 4

An SPV (Simplified Payment Verification) wallet receives a merkleblock message containing the 80-byte block header plus a Merkle path for a transaction it cares about. What does the wallet verify with this data?

✅ Correct! Two-part verification: Merkle path proves membership; header chain proves the block belongs.

❌ Not quite. SPV wallets don't validate signatures or other transactions — they verify membership and chain inclusion.

Show solution

Solution:

The SPV wallet performs two distinct checks:

Transaction is in the block: Use the Merkle path (sibling hashes) to recompute the root from the transaction's hash. Compare with the root stored in the 80-byte block header.
Block is in the blockchain: Verify the chain of block headers (each header references the previous one's hash, and proof-of-work is checked on each).

Together these give strong assurance without downloading the full ~4 MB block. The wallet does not verify other transactions' signatures or contents — it trusts the network's miners to have done that work via proof-of-work.

Total bandwidth per relevant block: typically under 1 KB, compared to 4 MB for the full block.

Solved: 0 / 4