Part IV · Surviving the long run This chapter detours back into cryptography — one of only two in eighteen.
Recall what has been done to hashing so far:
Chapter 1: a hash is a fixed-length fingerprint, a pure function, and it avalanches
Chapter 4: hashes linked end to end into a chain
This chapter: hashes combined upward in pairs into a tree
Same brick, third way of laying it.
11.1 The problem¶
A block may hold thousands of transactions. Your phone wants to confirm that its payment made it in. Must it download the entire block and scan every entry?
In real Bitcoin the full block data is several hundred gigabytes. A phone cannot do that, and should not have to.
The Merkle tree’s answer: one short path of hashes is enough — even among a million transactions.
import hashlib
def H(s): return hashlib.sha256(s.encode()).hexdigest() # chapter 1's hash
print("warm-up: the same hash as always.")
print(H("Alice pays Bob")[:16], "...")
warm-up: the same hash as always.
c4d09eac2af12725 ...
11.2 Combine transactions upward in pairs¶
The rule: hash each transaction into a leaf; then concatenate adjacent pairs and hash again to get the level above; repeat until one hash remains — the Merkle root.
(If a level has an odd count, duplicate the last entry to make it even. That detail becomes a real vulnerability in 11.6.)
def merkle_root(leaves):
'''Collapse a set of transactions into one Merkle root.'''
if not leaves:
return H("")
level = [H(x) for x in leaves] # level 0: one hash per transaction
while len(level) > 1:
if len(level) % 2 == 1:
level.append(level[-1]) # odd -> duplicate the last one
# hash adjacent pairs to build the level above
level = [H(level[i] + level[i+1]) for i in range(0, len(level), 2)]
return level[0]
txs = ["Alice pays Bob", "Bob pays Carol", "Carol pays Dave", "Dave pays Eve"]
root = merkle_root(txs)
print("4 transactions -> Merkle root:", root[:20], "...")
4 transactions -> Merkle root: a765893c3938e60b31bc ...
First be clear what level is: a list of strings, and each pass through the loop
halves its length.
level, pass 0: ['h(A)', 'h(B)', 'h(C)', 'h(D)'] 4 items
level, pass 1: ['h(AB)', 'h(CD)'] 2 items
level, pass 2: ['h(ABCD)'] 1 item -> loop ends, this is the rootDrawn out:
ROOT
/ \
H(AB) H(CD)
/ \ / \
H(A) H(B) H(C) H(D)
| | | |
txA txB txC txDFour transactions collapse in two levels. A million takes about twenty.
Because every level halves. That is log₂ — chapter 2’s complexity intuition, this time working for you instead of against you.
11.3 The proof path¶
To prove “transaction C is in this tree” you do not need all the transactions.
You need only the sibling hashes along C’s path to the root — follow them and you can recompute the root yourself.
def merkle_proof(leaves, index):
'''The proof path (sibling hashes) from leaf `index` up to the root.'''
level = [H(x) for x in leaves]
proof = []
idx = index
while len(level) > 1:
if len(level) % 2 == 1:
level.append(level[-1])
if idx % 2 == 0: # I'm on the left, sibling on the right
proof.append((level[idx+1], "right"))
else: # I'm on the right, sibling on the left
proof.append((level[idx-1], "left"))
idx //= 2
level = [H(level[i] + level[i+1]) for i in range(0, len(level), 2)]
return proof
# Prove "Carol pays Dave" (index 2) is in the block
proof = merkle_proof(txs, 2)
print("proof path for 'Carol pays Dave':")
for sib, side in proof:
print(f" sibling hash {sib[:12]}... on the {side}")
print(f"\n4 transactions, {len(proof)}-step proof.")
proof path for 'Carol pays Dave':
sibling hash fdc627173c15... on the right
sibling hash 18a400e83a3f... on the left
4 transactions, 2-step proof.
proof is a list, and each entry is “one hash, and which side of me it sits on”:
[('h(D)...', 'right'), ('h(AB)...', 'left')]Meaning: “combine with the h(D) on your right, then combine with the h(AB) on your left, and you’re at the root.”
That idx //= 2 is worth a glance too: if you are item 2 on this level, you are item 1 on
the level above — because every two items merge into one. That integer division is
“climb one level.”
11.4 Verification: a phone needs only the root and the path¶
The verifier holds only the Merkle root (32 bytes, stored in the block header) and the proof path.
def verify_proof(leaf, proof, root):
'''Verify using only the transaction, the path, and the root -- no block needed.'''
h = H(leaf)
for sibling, side in proof:
# sibling on the right -> I'm on the left: H(me + sibling); otherwise H(sibling + me)
h = H(h + sibling) if side == "right" else H(sibling + h)
return h == root
print("is 'Carol pays Dave' in the block:", verify_proof("Carol pays Dave", proof, root))
# Forgery: change one word
print("forged 'Carol pays Dave a million':", verify_proof("Carol pays Dave a million", proof, root))
is 'Carol pays Dave' in the block: True
forged 'Carol pays Dave a million': False
Four lines, and it is a for loop that hashes repeatedly.
Change one word and the recomputed root no longer matches — avalanche again (chapter 1). To forge, an attacker would need different transaction content hashing to the same value: a collision attack, which nobody can perform against SHA-256.
That is the basis of a light (SPV) wallet: no block download, just a block header and a path.
11.5 A callback to chapter 4 — now it’s the root that moves¶
In chapter 4, editing an old block broke the hash of every block after it.
Here, editing any transaction changes the Merkle root → changes the block header → changes the block’s hash.
root_before = merkle_root(["Alice pays Bob", "Bob pays Carol", "Carol pays Dave", "Dave pays Eve"])
root_after = merkle_root(["Alice pays Bob", "Bob pays Carol", "Carol pays Dave a million", "Dave pays Eve"])
print("root before the edit:", root_before[:16], "...")
print("root after the edit :", root_after[:16], "...")
print("did the root change:", root_before != root_after)
root before the edit: a765893c3938e60b ...
root after the edit : 66db0d01764f31b9 ...
did the root change: True
Two threads now join:
Chapters 4 and 7: the block header holds
prev_hash, which commits to all prior historyThis chapter: the block header also holds the Merkle root, which commits to every transaction in this block
So a block header — 80 bytes in real Bitcoin — simultaneously commits to “the entire history behind me” and “every transaction inside me.”
Eighty bytes, committing to everything. It is the most elegant single piece of Bitcoin’s design, and it is why a phone can verify a ledger of several hundred gigabytes.
11.6 Scale, and one real bug¶
The power of a Merkle tree only shows at scale.
import math
big = [f"tx{i}" for i in range(1000)]
big_root = merkle_root(big)
big_proof = merkle_proof(big, 500) # prove tx 500 is in there
print(f"transaction count: {len(big)}")
print(f"proof path length: {len(big_proof)} steps (log2(1000) = {math.log2(1000):.1f})")
print(f"is tx500 in the block: {verify_proof('tx500', big_proof, big_root)}")
print()
print("Without a Merkle tree you would download all 1000 and check them one by one.")
print("With one, you need 10 hashes.")
transaction count: 1000
proof path length: 10 steps (log2(1000) = 10.0)
is tx500 in the block: True
Without a Merkle tree you would download all 1000 and check them one by one.
With one, you need 10 hashes.
A thousand transactions, a ten-step proof. Double the transactions and the proof grows by one step.
A million → 20 steps. A billion → 30.
That “duplicate the last one” detail¶
Now back to the detail planted in 11.2: when a level has an odd number of leaves, we duplicate the last one.
In real Bitcoin this caused a vulnerability, CVE-2012-2459.
Think about it. A tree with 5 leaves duplicates the fifth: [1,2,3,4,5,5].
Now what about a tree with 6 leaves, where the 5th and 6th happen to be identical?
Also [1,2,3,4,5,5].
Two different transaction lists produce exactly the same Merkle root.
An attacker could take a valid block, duplicate some transactions inside it, and produce a block with the same Merkle root but different contents. A node computing the root sees it match, while the block’s contents have changed. This could be used to make nodes wrongly mark a valid block invalid and reject it permanently.
Bitcoin patched this in 2012 by rejecting blocks containing duplicate transactions.
What is worth remembering is not the bug itself, but where it lived. The mathematics was right. The hashing was right. The tree structure was right. It went wrong in a padding detail — in the kind of place nobody bothers to write down in the specification.
Section 3.6’s reused
kis the same class of error. You will meet it a third time in chapter 13, and a fourth in chapter 18.
YOUR TURN¶
# YOUR TURN:
# 1) From 1000 to 1,000,000 transactions -- how many steps? Estimate with log2, then check.
# big2 = [f"t{i}" for i in range(1000000)]; print(len(merkle_proof(big2, 12345)))
# 2) Take tx500's proof but verify tx999 with it. What happens?
print("using tx500's path to verify tx999:", verify_proof("tx999", big_proof, big_root))
# Why is that path only valid for tx500?
# 3) Reproduce the bug from 11.6 yourself:
# leaves_a = ["t1","t2","t3","t4","t5"] (5 leaves, t5 gets duplicated)
# leaves_b = ["t1","t2","t3","t4","t5","t5"] (6 leaves, already duplicated)
# Compare merkle_root(leaves_a) and merkle_root(leaves_b). Equal?
using tx500's path to verify tx999: False
Please actually do question 3. Watching two different lists produce one identical root is worth more than ten paragraphs of explanation.
11.7 The ledger¶
| What you wrote | Field |
|---|---|
merkle_root() — collapse pairs upward into one root | Cryptography (composed hashing) |
merkle_proof() — the sibling path | Cryptography |
verify_proof() — light verification | Cryptography |
| “80 bytes committing to everything” | Systems design |
| CVE-2012-2459 | Engineering safety — not mathematics |
This chapter’s ledger tips back to the left, for the first time since chapter 3.
But note what it is in service of: letting weak devices verify — which is a systems-level requirement.
A Merkle tree is pure hash composition with no new mathematics in it. It matters not because it is deep, but because it makes “anyone can verify independently” hold true on a device with limited bandwidth and a battery.
Chapter 1’s “anyone can check the arithmetic” only truly reaches a phone in this chapter.
Next¶
Mempool, fee market, and confirmations.
Chapter 10 had you write pick_txs from the miner’s side. The next chapter switches to
the user’s side:
After you broadcast a transaction, and before it makes it into a block — where is it?
In a place called the mempool. Chapter 7 already gave you the sentence: the mempool is “I heard about this”; the blockchain is “the network finally accepted this.”
The next chapter is about the blurry region between those two: why transactions get stuck, how to unstick one, and why “wait for 6 confirmations” is a probability judgment rather than a promise.