How many confirmations? Nakamoto’s double-spend calculation (2008)

Section 11 of the Bitcoin whitepaper asks how long a merchant should wait. While the honest chain adds z blocks, the attacker’s secret chain grows by a Poisson-distributed amount with mean z q/p; from each possible lead the gambler’s ruin gives the chance to catch up. The whitepaper tabulates the result, and concludes that the risk drops exponentially with z.

What to look for

The function reproduces the whitepaper’s table, and a Monte-Carlo race between two chains agrees. Six confirmations against a 10% attacker leave about a 0.02% risk; against 30% it takes 24.

The history behind this experiment: Breakthroughs in Consensus. See Exercises: consensus for a worked solution to the exercise.

The whitepaper’s table

from random import Random

import matplotlib.pyplot as plt

import blockchainkit as bk

for z, expected in ((0, 1.0), (1, 0.2045873), (2, 0.0509779), (5, 0.0009137), (10, 0.0000012)):
    assert abs(bk.consensus.attacker_success_probability(0.1, z) - expected) < 5e-8
print("q = 0.1, z = 6:", f"{bk.consensus.attacker_success_probability(0.1, 6):.7f}")

q = 0.1, z = 6: 0.0002428

A Monte-Carlo double-spend race

def attack_succeeds(q, z, rng, horizon=300):
    honest = attacker = 0
    while honest < z:  # The merchant waits for z blocks.
        if rng.random() < q:
            attacker += 1
        else:
            honest += 1
    for _ in range(horizon):  # Then the attacker keeps racing.
        if attacker > honest:
            return True
        if rng.random() < q:
            attacker += 1
        else:
            honest += 1
    return attacker > honest


rng = Random(2008)
zs = range(0, 11)
fig, ax = plt.subplots(figsize=(7, 4))
for q, color in ((0.1, "#2563eb"), (0.3, "#ea580c")):
    exact = [bk.consensus.attacker_success_probability(q, z) for z in zs]
    simulated = [sum(attack_succeeds(q, z, rng) for _ in range(3000)) / 3000 for z in zs]
    ax.semilogy(zs, exact, "-", color=color, label=f"q = {q}, whitepaper formula")
    ax.semilogy(
        zs, [max(s, 3e-4) for s in simulated], "o", color=color, label=f"q = {q}, simulated"
    )
ax.set(
    xlabel="confirmations z",
    ylabel="attacker success probability",
    title="Waiting longer makes double spends exponentially rarer",
)
ax.legend(fontsize=8)
fig.tight_layout()

Exercise

Find the smallest z with risk below 0.1% for q = 0.1, 0.2 and 0.3. Why does the required z grow so quickly as q approaches 1/2?