The double-spend calculation in the Bitcoin white paper, recomputed
Section 11 of the Bitcoin white paper recomputed: the tables are right, the model understates the risk. Derivation, code and a simulation.
A merchant who accepts a Bitcoin payment waits until the transaction is in a block and a few more blocks have been built on top of it. The reason is the double spend. An attacker pays, receives the goods, and then tries to publish an alternative chain in which the same coins go back to himself. If that chain wins, the payment disappears from the history every node accepts.
Section 11 of the 2008 white paper works out how long to wait. Its result, a handful of tables, is still quoted today. Reimplemented, those tables come out exactly as printed. The model behind them, however, contains a simplification that understates the risk, and the longer the merchant waits, the larger the error.
This is about a probability model. It says nothing about whether anyone should use or buy Bitcoin.
A race between two chains
The attacker controls a fraction of the total hash rate, the honest miners the rest, . Blocks result from independent hash attempts, so waiting times are memoryless and each side produces blocks as a Poisson process. That has a convenient consequence: every newly found block, on either side, belongs to the attacker with probability and to the honest miners with probability , independently of everything before.
The attacker’s deficit therefore performs a random walk, one step up with probability and one step down with probability . The white paper splits the attack in two phases. First the merchant waits until the transaction is in a block followed by more; meanwhile the attacker mines in secret and gets some random number of blocks. Then the attacker has to close the remaining gap of .
Catching up from z blocks behind
Let be the probability of ever closing a gap of blocks. Closing blocks means closing one, then the next, and so on; because the walk has no memory, these are independent stages with the same success probability, and . Conditioning on the next block gives
whose roots are and . When , the law of large numbers sends the deficit to infinity, so , which leaves :
and for . This is the gambler’s ruin, and it appears in exactly this form in the white paper. With half the hash rate or more, the attacker succeeds with certainty, however long the merchant waits.
What the attacker manages while the merchant waits
While the honest network finds blocks, the attacker finds blocks on average. The white paper assumes that the honest blocks take exactly the expected time. Then the attacker’s progress is Poisson with mean . Weighting each with the chance of catching up from there, which is 1 once the attacker is ahead, gives
or, since the probabilities of all add up to 1, without the infinite sum,
The paper turns this into a short C function. Here it is in Python, line by line:
from math import exp
def nakamoto(q: float, z: int) -> float:
p = 1.0 - q
lam = z * (q / p)
total = 1.0
for k in range(z + 1):
poisson = exp(-lam)
for i in range(1, k + 1):
poisson *= lam / i
total -= poisson * (1 - (q / p) ** (z - k))
return total
print(f"{nakamoto(0.1, 6):.7f}") # 0.0002428
Rounded to seven decimals, it reproduces all 22 values of the two result tables ( for to , for ), and the table of the smallest with : 5, 8, 11, 15, 24, 41, 89 and 340 confirmations for to .1 The arithmetic is fine.
Where intuition misleads: the waiting time is random too
Assuming the honest blocks arrive in exactly the expected time sounds harmless because it is true on average. But only on average. If the honest network happens to be slow, the attacker gets more time; if it is fast, less. These deviations do not cancel out. Each extra attacker block multiplies the catch-up probability by , a factor of 9 when , so a long wait helps the attacker more than a short one hurts. The exception is the region where he is already ahead: probabilities stop at 1, and there the effect reverses.
Without the assumption the calculation actually gets simpler. In the sequence of blocks, each one the attacker’s with probability , count the attacker blocks that come before the -th honest one. That count has a negative binomial distribution,
which is also what the Poisson model gives once the waiting time is treated as a gamma-distributed random variable instead of a constant. Combined with the same catch-up rule, this yields, for ,
the formula Meni Rosenfeld published in 2014. Cyril Grunspan and Ricardo Pérez-Marco showed in 2017 that it has a closed form in terms of the regularized incomplete beta function:
For all 20 combinations of and in the accompanying script, the two expressions and a direct sum over the negative binomial distribution agree, the sums exactly and the beta function up to the error of numerical integration.
The difference in numbers
| q | z | white paper | exact | ratio |
|---|---|---|---|---|
| 0.1 | 1 | 0.2045873 | 0.2000000 | 0.98 |
| 0.1 | 2 | 0.0509779 | 0.0560000 | 1.10 |
| 0.1 | 6 | 0.0002428 | 0.0005914 | 2.44 |
| 0.1 | 10 | 0.0000012 | 0.0000079 | 6.33 |
| 0.3 | 5 | 0.1773523 | 0.1976173 | 1.11 |
| 0.3 | 10 | 0.0416605 | 0.0651067 | 1.56 |
| 0.3 | 24 | 0.0008106 | 0.0040007 | 4.94 |
Only for a single confirmation is the white-paper value too high, which is the capped region just described. From two confirmations on it understates the risk, by a factor that grows with . For and the 24 confirmations the white paper recommends for less than 0.1 %, the actual risk is 0.4 %.
The growing ratio comes from different decay rates. Grunspan and Pérez-Marco give the asymptotics of both: the exact value falls like , up to a factor of order , the white-paper value like with and . At , every extra confirmation multiplies the exact risk by about 0.36, the white-paper risk by about 0.27.
The number of confirmations needed for shifts accordingly:
| q | white paper | exact |
|---|---|---|
| 0.10 | 5 | 6 |
| 0.15 | 8 | 9 |
| 0.20 | 11 | 13 |
| 0.25 | 15 | 20 |
| 0.30 | 24 | 32 |
| 0.35 | 41 | 58 |
| 0.40 | 89 | 133 |
| 0.45 | 340 | 539 |
The familiar rule of six confirmations is a convention, not part of the protocol. The Bitcoin wiki traces it to two arbitrary assumptions: an attacker with at most 10 % of the hash rate, and an accepted risk below 0.1 %. The white-paper formula would need five confirmations for that; the exact one needs precisely six.
Settling it by simulation
When two formulas disagree, an experiment decides. The simulation replays the race: draw blocks until the honest chain has , then run the walk until the attacker has caught up or fallen 80 blocks behind. At that point the remaining chance is below for , so stopping there changes nothing measurable.
import random
def simulate(q: float, z: int, trials: int, rng: random.Random) -> float:
wins = 0
for _ in range(trials):
honest = attacker = 0
while honest < z: # phase 1
if rng.random() < q:
attacker += 1
else:
honest += 1
deficit = z - attacker
while 0 < deficit < 80: # phase 2
deficit += -1 if rng.random() < q else 1
wins += deficit <= 0
return wins / trials
rng = random.Random(20261029)
print(simulate(0.3, 5, 200_000, rng)) # 0.1979
print(simulate(0.1, 6, 1_000_000, rng)) # 0.000606
For and , 200,000 races give 0.1979, against 0.1976 exact and 0.1774 in the white paper. For and , a million races give 0.000606, against 0.000591 exact and 0.000243 in the white paper. Both times the exact value is well within the statistical noise and the white-paper value far outside it.
What the model leaves out
The corrected formula is still a model, and its assumptions matter before turning it into a waiting time.
- No head start. Both calculations assume the attacker starts mining at the moment of payment. The white paper justifies this by having the receiver create a fresh key pair just before the payment. An attacker who can choose the moment and pre-mine a block first does better.
- Fixed shares. is treated as a constant. Hash power can be rented, and nobody observes directly. The result is a probability for an assumed , not for the actual attacker.
- No propagation delay. Blocks take time to spread. Orphaned honest blocks waste hash power that the model counts as fully effective.
- Honest miners stay honest. Eyal and Sirer showed in 2013 that a large enough miner can earn more by withholding blocks (selfish mining). Such a miner behaves neither like the honest side nor like the attacker here.
- One attempt, no cost. The formula is the success probability of a single attempt. Whether an attack pays also depends on the amount, the cost of hash power and the number of attempts; Rosenfeld’s paper covers those questions as well.
For the question the section set out to answer, the conclusion is short: the white-paper tables are computed correctly but are too optimistic, and the exact formula is no harder to use.
Further reading
- Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Section 11, “Calculations”, pp. 6–8.
- Meni Rosenfeld, Analysis of Hashrate-Based Double Spending, 2014. Equation (1) and Table 1.
- Cyril Grunspan, Ricardo Pérez-Marco, Double spend races, International Journal of Theoretical and Applied Finance 21(8), 2018. Theorem 1 (closed form), Theorem 2 (asymptotics), Table 1.
- Ittay Eyal, Emin Gün Sirer, Majority is not Enough: Bitcoin Mining is Vulnerable, 2013.
- William Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd edition, Wiley 1968. Chapter XIV (random walk and ruin problems).
- Bitcoin wiki, Confirmation, on where the six confirmations come from.
- Every number in this post comes from
tests/articles/double_spend.pyin the repository of this site, the figure fromtests/articles/double_spend_svg.py --lang en.
Footnotes
-
Table 1 of Grunspan and Pérez-Marco lists 81 in the row with Nakamoto’s values for . The white-paper formula gives 89, as printed there: at it is still at 0.18 %. ↩