The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

3 Probabilistic preliminaries

This section constructs the probabilistic tools of the double-spend analysis in Sections 4 to 6: exponential clocks, which model block discovery; the attribution sequence (Proposition 3.4), which reduces the race in continuous time to a sequence of Bernoulli trials; the negative binomial law of the attacker’s progress (Proposition 3.5); and the normalisation of a first-to-n race (Lemma 3.6). Probability spaces, conditioning, independence, random variables and expectation are those of the Math Guide, §“Probability, asymptotics, and computation”; countable additivity, continuity along monotone events, density-defined laws and infinite sequences of independent trials are those of its §“Beyond finite spaces: countable additivity, limits, and densities”.

3.1 Memoryless clocks and the attribution sequence

Definition 3.1 (Exponential clock).

A random variable X is exponential with rate λ>0 if Pr[X>t]=e−λ⁢t for all t≥0 — a law defined by the density λe−λ⁢t on t≥0 in the sense of the Math Guide’s density definition, with mean 1/λ.

Lemma 3.2 (Memorylessness).

An exponential X satisfies Pr[X>s+t∣X>s]=Pr[X>t] for all s,t≥0: the remaining wait of a clock that has not fired has the law of a fresh clock.

Proof.

Pr[X>s+t∣X>s]=e−λ⁢(s+t)/e−λ⁢s=e−λ⁢t. □

Lemma 3.3 (Race of two clocks).

Let X and Y be independent exponentials with rates λ and μ. Then

Pr⁢[X<Y]=λλ+μ,

and the winning time min(X,Y) is exponential with rate λ+μ.

Proof.

Integrating over the time at which X fires,

Pr⁢[X<Y]=∫0∞λ⁢e−λ⁢t⁢Pr⁢[Y>t]⁢𝑑t=∫0∞λ⁢e−(λ+μ)⁢t⁢𝑑t=λλ+μ.

For the minimum, Pr[min(X,Y)>t]=Pr[X>t]Pr[Y>t]=e−(λ+μ)⁢t. Moreover, the joint density that X wins at time t factors as

λ⁢e−(λ+μ)⁢t=λλ+μ⁢(λ+μ)⁢e−(λ+μ)⁢t,

and similarly for Y. Thus the winner is independent of the winning time. □

Proposition 3.4 (The attribution sequence).

Model the honest network and attacker as independent exponential clocks with rates p/T0 and q/T0, restarting when either fires (Section 4). Successive block attributions form an infinite sequence of independent, identically distributed Bernoulli trials in the Math Guide’s sense: attacker with probability q, honest network with probability p, independent of all earlier attributions and all elapsed times.

Proof.

By Lemma 3.3 the first block is the attacker’s with probability (q/T0)/(p/T0+q/T0)=q. When a block is found, the finder’s clock restarts by construction, and the loser’s remaining wait is distributed as a fresh clock by Lemma 3.2; the state after each block is therefore probabilistically identical to the start, independent of the past. The density factorisation in Lemma 3.3 also makes each winner independent of that race’s elapsed time. The claim follows by induction. □

Proposition 3.4 is the paper’s reduction (its §3, with the clock rates of its footnote 1) of the race in continuous time to a sequence of trials. Whether the attacker’s branch ever overtakes the public chain depends only on the order of block discoveries, not on their times; every result below is therefore a statement about a p/q trial sequence, and the time constant T0 does not appear in any of them.

3.2 The negative binomial law

Proposition 3.5 (Progress of the loser).

In an attribution sequence with attacker probability q=1−p, let m be the number of attacker blocks found strictly before the honest network’s n-th block. Then

P⁢(m)=(m+n−1m)⁢pn⁢qm,m=0,1,2,…

— the negative binomial distribution.

Proof.

The event constrains the first m+n trials as follows: the (m+n)-th trial is honest (the n-th honest success), and among the first m+n−1 trials exactly m are the attacker’s, in any of (m+n−1m) orders. Each such order has probability pn−1qm⋅p. □

Lemma 3.6 (First-to-n race).

In the same sequence, let Hn be the event that the honest network reaches n blocks before the attacker does, and An the reverse. Then Hn and An partition the sample space, and

Pr⁢[Hn]=∑m=0n−1(m+n−1m)⁢pn⁢qm,Pr⁢[An]=∑h=0n−1(h+n−1h)⁢qn⁢ph,Pr⁢[Hn]+Pr⁢[An]=1.
Proof.

Among the first 2n−1 trials one side already has n successes, so the race terminates; a tie is impossible because block counts advance one at a time. The event Hn says the n-th honest block arrives while the attacker holds m≤n−1; summing Proposition 3.5 over those m gives the first sum, and An is the same computation with the roles of p and q swapped. □

Remark 3.7 (From hash trials to exponential clocks).

The exponential model is a limit, not an axiom. A miner’s work is modelled as a sequence of candidate evaluations, each an independent Bernoulli trial with a small success probability; the number of trials to the first success is geometric, and a geometric law with small success probability, rescaled by its mean, converges to the exponential of Definition 3.1. The limit requires progress-freeness: a failed candidate carries no information usable by the next one. Whether Zcash’s Equihash satisfies this is examined with the deployed parameters in Section 8.3.