Part II · Retracing the ancestors Last chapter ended with: if making a block is expensive, rewriting history becomes unaffordable. This chapter builds the expense.
In 1997 Adam Back was trying to solve email spam.
His idea was to make senders buy a stamp — not with money, but with computation. Before sending, you must solve a small puzzle. For a person writing one email that’s nothing. For someone sending a million a day it is fatal.
He called it Hashcash. Satoshi repurposed it into something entirely different: a way to decide who gets to write the next page of the ledger.
(He is the first citation in the whitepaper.)
5.1 A puzzle that is hard to solve and trivial to check¶
The rule is simple: given some data, find a number nonce such that
hash(data + nonce) starts with some zeros.
Finding it: no shortcut. Try nonces one at a time — hard
Checking it: one hash, look at the front — instant
Why is there no shortcut? Because of chapter 1’s avalanche. Increment the nonce and the hash is completely new. You cannot get warmer — there is no gradient to climb, only blind guessing.
import hashlib, time
def h(s: str) -> str:
return hashlib.sha256(s.encode()).hexdigest()
def mine(data: str, difficulty: int):
'''Find a nonce so the hash starts with `difficulty` zeros.'''
target = "0" * difficulty # the goal: this many leading zeros
nonce = 0
while True:
digest = h(f"{data}{nonce}") # try one nonce
if digest.startswith(target): # hit?
return nonce, digest
nonce += 1 # nope, next
nonce, digest = mine("hello world", difficulty=3)
print("nonce found:", nonce)
print("hash :", digest)
print("verify :", digest.startswith("000"))
nonce found: 6742
hash : 000fd9024e22437d38075ad87a7ca2649e66384ee67943a66eef482f5fe437c7
verify : True
“Mining,” in code, is that while True loop.
There is nothing deep in it — it counts up from zero, trying one value after another, until it happens to hit a hash starting with three zeros. This time it took 6,742 attempts.
Now look at the asymmetry:
You just made 6,742 attempts to find it
Anyone else confirms you aren’t lying with one hash
Hard to find, easy to verify. That is the soul of proof-of-work.
It gives you something you did not have before: a piece of evidence, checkable by anyone, that you burned real resources. A signature proves I am me. Proof-of-work proves I spent something.
5.2 Difficulty: what does one more zero cost?¶
Each additional leading zero cuts the chance of a hit to about 1/16 (a hex digit has sixteen possible values). So the expected number of attempts should multiply by 16 per level.
for diff in [1, 2, 3, 4]:
t0 = time.time()
nonce, digest = mine("block data", diff)
dt = time.time() - t0
print(f"difficulty {diff}: {nonce+1:>7} tries {dt:6.3f}s hash={digest[:14]}...")
difficulty 1: 18 tries 0.000s hash=015d48fff3a644...
difficulty 2: 159 tries 0.000s hash=009a3fe57e28e2...
difficulty 3: 2894 tries 0.003s hash=00033494d6564e...
difficulty 4: 226326 tries 0.207s hash=0000b55ea7ba12...
Roughly:
difficulty 1: 18 tries 0.000s hash=015d48fff3a644...
difficulty 2: 159 tries 0.000s hash=009a3fe57e28e2...
difficulty 3: 2894 tries 0.002s hash=00033494d6564e...
difficulty 4: 226326 tries 0.117s hash=0000b55ea7ba12...Hold on, that data is wrong¶
Theory said ×16 per level. In practice: 18 → 159 is ×8.8. 159 → 2894 is ×18.2. 2894 → 226326 is ×78.2.
All over the place.
If you read “×16 per level” in some other book and then ran this, you would assume you’d made a mistake. You haven’t. This data is correct, and the most important thing in the chapter is hiding inside it.
Mining is a geometric distribution¶
Think about what mine is doing: repeating an action with a fixed success probability.
At difficulty 3, each nonce has a 1/16³ = 1/4096 chance of working.
So “which attempt succeeds” follows a geometric distribution. Its mean is 4096 — and its standard deviation is also about 4096. In other words, the noise is as large as the signal.
A single run hands you one sample from that distribution, not its average.
Run it three hundred times:
import statistics
def tries(data, difficulty):
'''How many attempts until a valid nonce is found.'''
target = "0" * difficulty
n = 0
while not h(f"{data}{n}").startswith(target):
n += 1
return n + 1
for d in [1, 2, 3]:
xs = [tries(f"blk{i}", d) for i in range(300)]
print(f"difficulty {d}: mean of 300 = {statistics.mean(xs):9.1f} "
f"theory 16^{d} = {16**d:>6} min {min(xs):>5} max {max(xs):>7}")
difficulty 1: mean of 300 = 16.5 theory 16^1 = 16 min 1 max 89
difficulty 2: mean of 300 = 262.0 theory 16^2 = 256 min 1 max 1168
difficulty 3: mean of 300 = 4180.3 theory 16^3 = 4096 min 1 max 23386
The means land almost exactly on 16, 256, 4096. The theory was right all along.
But look at the last two columns. At difficulty 3, the luckiest run hit on the first try, and the unluckiest took 23,386 — 5.7× the mean.
A single mining result carries no information. Only the average over many samples obeys the ×16 rule.
This explains something about real Bitcoin¶
Bitcoin targets an average of ten minutes per block. Most people hear that as “roughly one every ten minutes.”
It doesn’t mean that. Block intervals follow exactly the distribution above:
You will see two blocks thirty seconds apart
You will also see two blocks forty minutes apart
And both are completely normal. Nothing is wrong with the network.
Ten minutes is an expectation, not a metronome. That fact comes back twice:
Chapter 10: difficulty adjustment must average over a long window, or noise drags it around
Chapter 12: why “wait for 6 confirmations” is a probability judgment, not a guarantee
The price of intuition-first is that sometimes the intuition is wrong. This is the first place in the book where the theory is correct and a single experiment looks like it flatly contradicts it. Remember the feeling.
YOUR TURN¶
# YOUR TURN:
# 1) How many tries for difficulty 5? Estimate with x16 first (4096 x 16 x 16 ~ 1 million),
# then run and see how far off you are.
# nonce, digest = mine("block data", 5); print(nonce) # may take a few seconds
# 2) Write verify_pow: given data, nonce, difficulty, decide instantly whether it's valid.
def verify_pow(data, nonce, difficulty):
return ____ # hint: h(f"{data}{nonce}").startswith("0"*difficulty)
# print(verify_pow("block data", 226325, 4))
Question 2 matters — it is the other half of this chapter. Once written, compare the two:
mine has a while loop; verify_pow is one line.
That difference in length is the entire value of proof-of-work.
5.3 Put proof-of-work inside a block¶
Now upgrade chapter 4’s block: a block only counts once it has been mined.
class Block:
def __init__(self, data, prev_hash, difficulty):
self.data = data
self.prev_hash = prev_hash
self.difficulty = difficulty
self.nonce = None # empty before mining
def content(self):
return f"{self.data}|{self.prev_hash}|{self.nonce}"
def mine(self):
'''Mine: find a nonce that meets the target.'''
target = "0" * self.difficulty
n = 0
while not h(f"{self.data}|{self.prev_hash}|{n}").startswith(target):
n += 1
self.nonce = n
return n
def hash(self):
return h(self.content())
blk = Block("Alice pays Bob", "0"*64, difficulty=4)
print("mining...")
t0 = time.time()
blk.mine()
print(f"found it. nonce={blk.nonce} in {time.time()-t0:.3f}s")
print("block hash:", blk.hash())
print("does it meet the target:", blk.hash().startswith("0000"))
print("object fields:", blk.__dict__)
print("what actually gets hashed:", blk.content())
mining...
found it. nonce=810 in 0.001s
block hash: 0000866391a1d6d54f0b4fe03563044c1c0df0b0e5c1d82981fcbc2e5f944c46
does it meet the target: True
object fields: {'data': 'Alice pays Bob', 'prev_hash': '0000000000000000000000000000000000000000000000000000000000000000', 'difficulty': 4, 'nonce': 810}
what actually gets hashed: Alice pays Bob|0000000000000000000000000000000000000000000000000000000000000000|810
Open up Block — it is an index card:
data: what this block records, e.g."Alice pays Bob"prev_hash: the previous block’s hash, here 64 zeros to startdifficulty: how many leading zeros are requirednonce:Noneuntil mined, then a number
Four fields, three methods. Compared with chapter 4’s Block, only two things are new:
difficulty and nonce.
Those last two print lines are there on purpose — read them:
object fields: {'data': 'Alice pays Bob', 'prev_hash': '0000...', 'difficulty': 4, 'nonce': ...}
what actually gets hashed: Alice pays Bob|0000000000...|47124blk.__dict__ shows you the object is four fields in a dictionary, with no hidden state.
blk.content() shows you exactly which string gets hashed — three fields joined by |.
The word “block” should now be completely demystified. It is an object with four fields, one of which was found by guessing.
5.4 Now try rewriting history¶
Combine chapter 4 and this one:
Edit an old block → its hash changes → every later block breaks (chapter 4)
To repair it → every later block must be re-mined (this chapter, and each one is expensive)
def build_chain(datas, difficulty):
chain = []
prev = "0"*64
for d in datas:
b = Block(d, prev, difficulty)
b.mine()
chain.append(b)
prev = b.hash()
return chain
chain = build_chain(["genesis", "Alice pays Bob", "Bob pays Carol"], difficulty=3)
for i, b in enumerate(chain):
print(f"block{i}: {b.data:<16} nonce={b.nonce:<6} hash={b.hash()[:12]}...")
# The attacker edits block 1 and hopes nobody notices.
print("\nAttacker rewrites block 1, and must now re-mine it and everything after...")
chain[1].data = "Alice pays Bob one million"
t0 = time.time()
for i in range(1, len(chain)):
chain[i].prev_hash = chain[i-1].hash()
chain[i].mine()
print(f"re-mined {len(chain)-1} blocks in {time.time()-t0:.3f}s (difficulty is only 3!)")
block0: genesis nonce=2294 hash=000d8022762a...
block1: Alice pays Bob nonce=994 hash=000eeb6b19cf...
block2: Bob pays Carol nonce=1587 hash=0006efde192f...
Attacker rewrites block 1, and must now re-mine it and everything after...
re-mined 2 blocks in 0.008s (difficulty is only 3!)
The attacker succeeds, and quickly.
This has to be said plainly: at this scale, proof-of-work stops nobody. Difficulty 3, a three-block chain — re-mining it is a fraction of a second.
Real Bitcoin differs in three places, and each one is orders of magnitude:
| Here | Real Bitcoin | |
|---|---|---|
| Difficulty | 3 leading zeros | equivalent to dozens |
| Chain length | 3 blocks | over 900,000 |
| Competition | none | honest miners keep extending, constantly |
The third is decisive, and it is the one thing this chapter did not build.
While the attacker is redoing history, the honest network does not politely wait. It keeps moving forward. So the attacker must not only redo those blocks, he must run faster than every honest miner on Earth combined to catch up and overtake.
Which raises the real question: If two chains exist right now, why would you believe one over the other?
The answer is “the one with the most accumulated work.” But note carefully — that sentence is not cryptography and it is not mathematics. It is a rule people agree to follow.
Why would mutually distrustful strangers voluntarily follow a rule? That is chapter 7, and it needs a game theorist, not a cryptographer.
5.5 The ledger¶
| What you wrote | Field |
|---|---|
h() — SHA-256 | Cryptography (still that one line) |
mine() — blind nonce search | Systems design (an application of hashing) |
| difficulty = number of leading zeros | Systems design |
| “hard to find, easy to verify” | Systems design |
| single results follow a geometric distribution | Probability (not cryptography) |
| the cost of rewriting history | Economics |
Again, one line of cryptography.
Part II ends here. You have now hand-written every borrowed brick Satoshi stood on:
Signatures (chapters 1–3) — Diffie, Hellman, RSA, 1976–77
The hash chain (chapter 4) — Haber & Stornetta, 1991
Proof-of-work (chapter 5) — Adam Back, 1997
All of it borrowed, and all of it now in place.
From the next chapter on, nobody handed Satoshi a blueprint for what you are about to build.
Next¶
Transactions and double-spending.
You will build a ledger and let Alice pay Bob. Then you will discover something: the signature you wrote stops forgery, but it does not stop Alice from spending the same coin twice.
That is the first time in this book that the cryptography in your hands runs out.
For thirty years, everyone was stuck on that page.