The Zcash ArboretumIV Consensus Guide
Contents
PDF
Theme

4 The catch-up probability

When the merchant of Section 2.2 ships the goods, the attacker’s private branch is some number of blocks behind the public chain; the attack succeeds if that branch ever overtakes it. This section models the deficit as a random walk (Definition 4.3) and computes the probability of that event as a function of the deficit (Theorem 4.4); the next section derives the distribution of the deficit. Both computations rest on the paper’s two assumptions, stated 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 pH belongs to the honest network and qH 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 T0.

Under Assumption 4.2 every block carries equal work, so the branch with the most work is the longest, and the race is measured in blocks. The deployed chain departs from both assumptions: difficulty adjusts after every block and hashrate drifts. The formulas are therefore an equal-difficulty baseline, not an exact model of deployment (Section 8.2).

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:

zi+1={zi+1with probability ⁢p,zi−1with probability ⁢q.

The attack succeeds when z reaches −1: the private branch is then strictly ahead, and once released it replaces the public chain, removing the payment to the merchant.

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

Let az be the probability that the walk of Definition 4.3, started at deficit z, ever reaches −1. Then

az=min(q/p, 1)max⁡(z+1, 0)={1if ⁢z<0⁢ or ⁢q≥p,(q/p)z+1if ⁢z≥0⁢ and ⁢q<p. (1)
Proof.

For z<0 the walk has already succeeded, so az=1; assume z≥0. Fix an integer N>z and absorb the walk at both −1 and N; let hN(z) be the probability of reaching −1 before N. Conditioning on the first step,

hN⁢(z)=p⁢hN⁢(z+1)+q⁢hN⁢(z−1)(0≤z≤N−1),hN⁢(−1)=1,hN⁢(N)=0,

a second-order linear recurrence. The trial solution hN(z)=tz satisfies it exactly when t is a root of the characteristic polynomial pt2−t+q=p(t−1)(t−q/p).

If q≠p the roots 1 and q/p are distinct, so hN(z)=A+B(q/p)z; the boundary conditions give

hN⁢(z)=(q/p)z−(q/p)N(q/p)−1−(q/p)N.

If q=p the root is double and hN(z)=A+Bz, giving hN(z)=(N−z)/(N+1).

Now let N→∞. The events EN={reach −1 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 EN holds for every N above the largest state visited. By continuity along monotone events (Math Guide, §“Beyond finite spaces: countable additivity, limits, and densities”), az=limN→∞hN(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)→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≥p, the attacker overtakes the public chain with probability 1 from any finite deficit. No confirmation count protects a payment 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%, a0=1/9≈0.1111 and a5≈1.88×10−6; at q=30%, a0=3/7≈0.4286 and a5≈6.20×10−3; at q=45%, a0=9/11≈0.8182 and a5≈0.300. Near one half the factor q/p approaches 1, and a deficit of five blocks still leaves the attacker a 30% chance.

Corollary 4.7 (Blocks, not time).

Equation (1) contains neither T0 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, so 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≈3.7×10−9.