Consensus Guide Nakamoto consensus: the double-spend race, the arithmetic of confirmations, and the deployed most-work rule 3 A probability toolkit 5 Waiting for confirmations

4 Playing catch-up

The attacker of Section 2.2 finds himself, at the moment the merchant ships, some number of blocks behind the public chain, and wins if his branch ever overtakes it. This section computes the probability of that event as a function of the deficit; the next section supplies the distribution of the deficit itself.

Both computations run under the paper’s two standing assumptions, stated here nearly verbatim (the environment form is ours, Remark 1.1):

Assumption 4.1 (Constant hashrates).

The total hashrate of the honest network and the attacker is constant. Combined they have a hashrate of $H$ , of which $p H$ belongs to the honest network and $q H$ to the attacker, where $0<p,q<1$ and $p+q=1$ .

Assumption 4.2 (Constant difficulty).

The mining difficulty is constant, and such that with hashrate $H$ the average time to find a block is $T_{0}$ .

Under Assumption 4.2 every block carries equal work, so “most work” and “longest” coincide and the race can be scored in block counts. Section 8.2 explains how the deployed chain departs from these assumptions — difficulty adjusts after every block and hashrate drifts — and why the formulas should be read as an equal-difficulty baseline rather than an exact deployment model.

Definition 4.3 (The deficit walk).

Let $z$ denote the honest chain’s lead in blocks over the attacker’s branch. By Proposition 3.4, each newly found block moves $z$ up by $1$ with probability $p$ (honest block) or down by $1$ with probability $q$ (attacker block), independently of the past:

z_{i+1}\;=\;\begin{cases}z_{i}+1&\text{with probability }p,\\ z_{i}-1&\text{with probability }q.\end{cases}

The attack succeeds the moment $z$ reaches $-1$ : the secret branch is then strictly ahead, and releasing it rewrites history.

Theorem 4.4 (Catch-up probability; Rosenfeld §3).

Let $a_{z}$ be the probability that the walk of Definition 4.3, started at deficit $z$ , ever reaches $-1$ . Then

a_{z}\;=\;\min(q/p,\,1)^{\max(z+1,\,0)}\;=\;\begin{cases}1&\text{if }z<0\text{% or }q\geq p,\\ (q/p)^{z+1}&\text{if }z\geq 0\text{ and }q<p.\end{cases}

(1)

Proof.

For $z<0$ the walk has already succeeded, so $a_{z}=1$ ; assume $z\geq 0$ . Fix an integer $N>z$ and absorb the walk at both $-1$ and $N$ ; let $h_{N}(z)$ be the probability of reaching $-1$ before $N$ . Conditioning on the first step,

h_{N}(z)=p\,h_{N}(z+1)+q\,h_{N}(z-1)\qquad(0\leq z\leq N-1),\qquad h_{N}(-1)=1% ,\quad h_{N}(N)=0,

a second-order linear recurrence. The trial solution $h_{N}(z)=t^{z}$ satisfies it exactly when $t$ is a root of the characteristic polynomial $pt^{2}-t+q=p(t-1)(t-q/p)$ .

If $q\neq p$ the roots $1$ and $q/p$ are distinct, so $h_{N}(z)=A+B(q/p)^{z}$ ; the boundary conditions give

h_{N}(z)\;=\;\frac{(q/p)^{z}-(q/p)^{N}}{(q/p)^{-1}-(q/p)^{N}}.

If $q=p$ the root is double and $h_{N}(z)=A+Bz$ , giving $h_{N}(z)=(N-z)/(N+1)$ .

Now let $N\to\infty$ . The events $E_{N}=\{\text{reach }-1\text{ before }N\}$ are nondecreasing in $N$ , and their union is the event that the walk ever reaches $-1$ : a walk that does so does it at a finite time, having visited finitely many states, so $E_{N}$ holds for every $N$ above the largest state visited. By continuity along monotone events (Math Guide, §“Beyond finite spaces: countable additivity, limits, and densities”), $a_{z}=\lim_{N\to\infty}h_{N}(z)$ . For $q<p$ the term $(q/p)^{N}$ vanishes and the quotient tends to $(q/p)^{z+1}$ ; for $q=p$ , $(N-z)/(N+1)\to 1$ ; for $q>p$ , dividing numerator and denominator by $(q/p)^{N}$ sends both to $-1$ , so the quotient tends to $1$ . □

Corollary 4.5 (Half or more always catches up).

When $q\geq p$ , the attacker overtakes the public chain with probability $1$ from any finite deficit. No confirmation count defends when the attacker controls at least half of the hashrate.

Corollary 4.6 (Geometric decay in the deficit).

When $q<p$ , each additional block of deficit multiplies the catch-up probability by $q/p$ . Concretely (script-computed): at $q=10\%$ , $a_{0}=1/9\approx 0.1111$ and $a_{5}\approx 1.88\times 10^{-6}$ ; at $q=30\%$ , $a_{0}=3/7\approx 0.4286$ and $a_{5}\approx 6.20\times 10^{-3}$ .

Corollary 4.7 (Blocks, not time).

Equation (1) contains neither $T_{0}$ nor any other time scale: the security of a deficit is a function of block counts alone. Two chains with different block spacings but the same $q$ offer identical security per confirmation — and therefore different security per minute (Section 6.1).

Refer to caption — Figure 2: Two runs of the deficit walk from $z=2$ , simulated by script with fixed seeds. At $q=0.45$ the drift is weak and this run reaches $-1$ after $23$ blocks — the attack succeeds; at $q=0.20$ the deficit grows roughly linearly, and by Theorem 4.4 the chance of ever returning from deficit $13$ is $(1/4)^{14}\approx 3.7\times 10^{-9}$ .