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 qq of the total hash rate, the honest miners the rest, p=1−qp = 1 - q. 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 qq and to the honest miners with probability pp, independently of everything before.

The attacker’s deficit therefore performs a random walk, one step up with probability pp and one step down with probability qq. The white paper splits the attack in two phases. First the merchant waits until the transaction is in a block followed by zz more; meanwhile the attacker mines in secret and gets some random number kk of blocks. Then the attacker has to close the remaining gap of z−kz - k.

Catching up from z blocks behind

Let aza_z be the probability of ever closing a gap of zz blocks. Closing zz 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 az=a1za_z = a_1^z. Conditioning on the next block gives

a1=q+pa12,a_1 = q + p\,a_1^2 ,

whose roots are 11 and q/pq/p. When p>qp > q, the law of large numbers sends the deficit to infinity, so a1<1a_1 < 1, which leaves a1=q/pa_1 = q/p:

az=(qp)z(p>q),a_z = \left(\frac{q}{p}\right)^{z} \qquad (p > q),

and az=1a_z = 1 for p≤qp \le q. 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 zz blocks, the attacker finds zq/pz\,q/p blocks on average. The white paper assumes that the honest blocks take exactly the expected time. Then the attacker’s progress kk is Poisson with mean λ=zq/p\lambda = z\,q/p. Weighting each kk with the chance of catching up from there, which is 1 once the attacker is ahead, gives

PSN(z)=∑k=0∞λke−λk!min⁡{1,(qp)z−k},P_{\text{SN}}(z) = \sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \min\left\{1, \left(\frac{q}{p}\right)^{z-k}\right\},

or, since the probabilities of all kk add up to 1, without the infinite sum,

PSN(z)=1−∑k=0zλke−λk!(1−(qp)z−k).P_{\text{SN}}(z) = 1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!}\left(1 - \left(\frac{q}{p}\right)^{z-k}\right).

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 (q=0.1q = 0.1 for z=0z = 0 to 1010, q=0.3q = 0.3 for z=0,5,…,50z = 0, 5, \dots, 50), and the table of the smallest zz with P<0.1%P < 0.1\,\%: 5, 8, 11, 15, 24, 41, 89 and 340 confirmations for q=0.10q = 0.10 to 0.450.45.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 (q/p)z−k(q/p)^{z-k} by p/qp/q, a factor of 9 when q=0.1q = 0.1, 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 qq, count the attacker blocks that come before the zz-th honest one. That count has a negative binomial distribution,

Pr⁡(k)=(k+z−1k)pzqk,\Pr(k) = \binom{k + z - 1}{k} p^z q^k ,

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 q<pq < p,

P(z)=1−∑k=0z(k+z−1k)(pzqk−pkqz),P(z) = 1 - \sum_{k=0}^{z} \binom{k + z - 1}{k} \left(p^z q^k - p^k q^z\right),

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:

P(z)=I4pq(z,1/2).P(z) = I_{4pq}\left(z, 1/2\right).

For all 20 combinations of qq and zz 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

qzwhite paperexactratio
0.110.20458730.20000000.98
0.120.05097790.05600001.10
0.160.00024280.00059142.44
0.1100.00000120.00000796.33
0.350.17735230.19761731.11
0.3100.04166050.06510671.56
0.3240.00081060.00400074.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 zz. For q=0.3q = 0.3 and the 24 confirmations the white paper recommends for less than 0.1 %, the actual risk is 0.4 %.

Success probability of a double spend against the number of confirmations Log-scale plot for z from 0 to 30. For an attacker with 10 % and with 30 % of the hash rate, the white-paper value (dashed) lies below the exact value (solid), and the gap grows with z. 1 10-3 10-6 10-9 10-12 0 5 10 15 20 25 30 confirmations z q = 0.1 q = 0.3
Dashed: white paper (Poisson). Solid: negative-binomial model (Rosenfeld; Grunspan and Pérez-Marco). Vertical axis logarithmic.

The growing ratio comes from different decay rates. Grunspan and Pérez-Marco give the asymptotics of both: the exact value falls like (4pq)z(4pq)^z, up to a factor of order 1/z1/\sqrt{z}, the white-paper value like e−zce^{-z c} with c=λ−1−ln⁡λc = \lambda - 1 - \ln\lambda and λ=q/p\lambda = q/p. At q=0.1q = 0.1, 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 P<0.1%P < 0.1\,\% shifts accordingly:

qwhite paperexact
0.1056
0.1589
0.201113
0.251520
0.302432
0.354158
0.4089133
0.45340539

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 zz, then run the walk until the attacker has caught up or fallen 80 blocks behind. At that point the remaining chance is below 10−2910^{-29} for q≤0.3q \le 0.3, 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 q=0.3q = 0.3 and z=5z = 5, 200,000 races give 0.1979, against 0.1976 exact and 0.1774 in the white paper. For q=0.1q = 0.1 and z=6z = 6, 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. qq is treated as a constant. Hash power can be rented, and nobody observes qq directly. The result is a probability for an assumed qq, 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

Footnotes

  1. Table 1 of Grunspan and Pérez-Marco lists 81 in the row with Nakamoto’s values for q=0.40q = 0.40. The white-paper formula gives 89, as printed there: at z=81z = 81 it is still at 0.18 %. ↩