The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

5 Waiting for confirmations

A merchant defends against a double-spend by shipping only after the paying transaction has n confirmations (Definition 2.3). This section fixes one convention of the paper’s attack timeline and computes, in the paper’s first-seen model, the exact probability that the attacker overtakes after n confirmations.

Remark 5.1 (The pre-mined block).

The paper assumes the attacker holds one block before the race is scored: “we assume one block was pre-mined by the attacker before commencing the attack” (§4). The attacker forks from the public leaf at the moment the merchant’s transaction is broadcast, and times the broadcast to coincide with a private block he has found but not yet announced. At the moment the honest chain reaches n confirmations, the attacker who has found m further blocks therefore holds m+1, and the deficit walk of Definition 4.3 starts at

z=n−m−1.

The convention is a modelling choice: an attacker with no pre-mined block starts at z=n−m, and for a minority attacker every probability below is smaller. It is also the convention under which the two sums in the proof of Theorem 5.2 are equal, so that the final formula describes a symmetric race.

By Proposition 3.5, the number m of attacker blocks found while the honest network finds its n is negative binomial. Averaging the catch-up probability of Theorem 4.4 over m gives the success probability under the first-seen tie rule of the specification and of Rosenfeld, which Zebra also applies from version 6.4.0 (Section 8.1). The model does not give an exact rollback probability for the deployed network.

Theorem 5.2 (Double-spend success probability; Rosenfeld eq. (1)).

Let the merchant wait for n≥1 confirmations, under Assumptions 4.1 and 4.2 and the convention of Remark 5.1, with a private branch accepted only after it becomes strictly heavier. The probability that the attacker’s branch eventually overtakes the public chain is r(q,n)=1 if q≥p, and otherwise

r⁢(q,n)= 1−∑m=0n−1(m+n−1m)⁢(pn⁢qm−pm⁢qn)= 2⁢∑m=0n−1(m+n−1m)⁢pm⁢qn. (2)
Proof.

Conditioning on m and applying Theorem 4.4 at z=n−m−1,

r=∑m=0∞P⁢(m)⁢an−m−1=∑m=0n−1P⁢(m)⁢(qp)n−m⏟behind: must catch up+∑m=n∞P⁢(m)⏟already ahead,

valid for q<p; when q≥p every an−m−1=1 and r=∑mP(m)=1 immediately. For the first sum, each term transforms exactly:

(m+n−1m)⁢pn⁢qm⁢(qp)n−m=(m+n−1m)⁢pm⁢qn,

which by Lemma 3.6 is the probability that the attacker’s n-th block arrives while the honest network holds m; summed over m≤n−1, the first sum is Pr[An], the probability that the attacker wins the first-to-n race. The second sum is Pr[m≥n]=1−Pr[Hn]=Pr[An] by the same lemma. Hence r=2Pr[An], the right-hand form of (2); the middle form follows from Pr[An]=1−Pr[Hn] applied to one of the two copies. The printed upper limit in the paper’s equation (1) is n rather than n−1; the m=n term is identically zero, so the forms agree. □

Remark 5.3 (The race doubling).

Under the one-pre-mined-block convention, the catch-up half — the honest chain reaches n first and the attacker later overtakes — has exactly the same probability as the already-ahead half, in which the attacker reaches n first. A first-to-n winner may have fallen behind and recovered along the way; neither half asserts otherwise. The double-spend probability is therefore twice the probability of winning a first-to-n race. The identity also covers the boundary case: at q=p each race half is exactly 12, giving r=1 with no case split, continuously with the q>p regime. The algebra here is the paper’s; reading its two sums as the two halves of one race, and the observation that the pre-mine convention is what makes them equal, are this volume’s presentational additions (verified by script over random (q,n); the two sums agree to floating-point precision).

Example 5.4 (A full race, exactly).

Take q=1/5 (a twenty-percent attacker) and n=6. The deficit starts at z=5−m, the catch-up factor is (q/p)6−m=4−(6−m), and every quantity below is an exact rational, printed to six decimals (script-computed):

m P⁢(m) a5−m=4−(6−m) product
0 0.262144 0.000244 0.000064
1 0.314573 0.000977 0.000307
2 0.220201 0.003906 0.000860
3 0.117441 0.015625 0.001835
4 0.052848 0.062500 0.003303
5 0.021139 0.250000 0.005285
catch-up half (sum of products) 0.011654
already-ahead half, Pr⁢[m≥6] 0.011654
r⁢(0.2, 6) 0.023308

The two halves are equal exactly, by Remark 5.3, and the closed form (2) evaluates to the same 0.023308. For a merchant who ships after six confirmations against a twenty-percent attacker, the model gives a 2.33% probability of a strict overtake.

Remark 5.5 (Satoshi’s approximation).

The whitepaper’s §11 computes the same quantity with one approximation and two offsetting conventions: the attacker’s progress is approximated as Poisson with mean λ=nq/p (the law Pr[k]=e−λλk/k! on the nonnegative integers); no block is pre-mined, but success is scored at breakeven rather than strictly ahead, and those two conventions cancel exactly — the whitepaper’s catch-up factor for m attacker blocks is (q/p)n−m, term for term the factor of Remark 5.1. The two results therefore differ only by the Poisson approximation. In each of the following script-computed comparisons the approximation lowers the estimate: at q=10%, n=6, the whitepaper’s formula gives 0.0243% against the exact 0.0591% — an understatement by a factor of about 2.4; at q=30%, n=6: 13.211% against 15.645%; at q=10%, n=10: 0.0001% against 0.0008%. The direction of the error is not the same for all (q,n); the negative binomial model is preferred because it is exact under the stated assumptions.

q n=1 2 3 4 5 6 7 8 9 10
2% 4.000 0.237 0.016 0.0011 8⋅10−5 <10−5
5% 10.000 1.450 0.232 0.039 0.0066 0.0012 2.1⋅10−4 4⋅10−5 <10−5
10% 20.000 5.600 1.712 0.546 0.178 0.059 0.020 0.0067 0.0023 0.0008
20% 40.000 20.800 11.584 6.669 3.916 2.331 1.401 0.848 0.516 0.316
30% 60.000 43.200 32.616 25.207 19.762 15.645 12.475 10.003 8.055 6.511
40% 80.000 70.400 63.488 57.958 53.314 49.300 45.769 42.621 39.787 37.218
45% 90.000 85.050 81.375 78.342 75.716 73.375 71.252 69.299 67.487 65.793
48% 96.000 94.003 92.508 91.264 90.177 89.201 88.307 87.478 86.703 85.972
50% 100 for every n
Table 1: The double-spend success probability r(q,n), in percent, computed by script from Theorem 5.2. On the rows the paper’s Table 1 also prints (q∈{2,10,20,30,40,48,50}%), the script reproduces its values cell-for-cell; the 5% and 45% rows are this volume’s additions.
Refer to caption
Figure 3: The success probability r(q,n) against the attacker’s hashrate share q, for n∈{1,2,4,6,8,10} confirmations, logarithmic vertical scale clipped at 10−5; coordinates computed by script from Theorem 5.2. Every curve reaches 1 at q=12 (dashed) and stays there: to the right of that line, confirmations give no protection. To its left, each added confirmation divides r by a roughly constant factor — the curves are near-equally spaced in log scale — and the factor grows as q falls.