IV Consensus Guide: Nakamoto consensus: the double-spend race, the arithmetic of confirmations, and the deployed most-work rule 2 The block tree and the most-work rule 4 Playing catch-up

3 A probability toolkit

The analysis ahead needs four tools: memoryless clocks (to model block discovery), a reduction from continuous time to a coin sequence, the negative binomial distribution (to count the attacker’s progress), and one normalisation lemma about races. Their foundations are the Math Guide’s: probability spaces, conditioning, independence, random variables, and expectation are constructed there from the definition of probability onward (§“Probability, asymptotics, and computation”), and the extension beyond finite spaces — countable additivity, continuity along monotone events, density-defined laws, and infinite sequences of independent trials — is its §“Beyond finite spaces: countable additivity, limits, and densities”. What no lower volume owns are the four instruments themselves; each is constructed here on that base, only as far as the critical path requires.

3.1 Memoryless clocks and the attribution sequence

Definition 3.1 (Exponential clock).

A random variable $X$ is exponential with rate $\lambda>0$ if $\mathrm{Pr}[X>t]=e^{-\lambda t}$ for all $t\geq 0$ — a law defined by the density $\lambda e^{-\lambda t}$ on $t\geq 0$ in the sense of the Math Guide’s density definition, with mean $1/\lambda$ .

Lemma 3.2 (Memorylessness).

An exponential $X$ satisfies $\mathrm{Pr}[X>s+t\mid X>s]=\mathrm{Pr}[X>t]$ for all $s,t\geq 0$ : having waited without success teaches nothing about the remaining wait.

Proof.

$\mathrm{Pr}[X>s+t\mid X>s]=e^{-\lambda(s+t)}/e^{-\lambda s}=e^{-\lambda t}$ . □

Lemma 3.3 (Race of two clocks).

Let $X$ and $Y$ be independent exponentials with rates $\lambda$ and $\mu$ . Then

\mathrm{Pr}[X<Y]\;=\;\frac{\lambda}{\lambda+\mu},

and the winning time $\min(X,Y)$ is exponential with rate $\lambda+\mu$ .

Proof.

Integrating over the time at which $X$ fires,

\mathrm{Pr}[X<Y]=\int_{0}^{\infty}\lambda e^{-\lambda t}\,\mathrm{Pr}[Y>t]\,dt% =\int_{0}^{\infty}\lambda e^{-(\lambda+\mu)t}\,dt=\frac{\lambda}{\lambda+\mu}.

For the minimum, $\mathrm{Pr}[\min(X,Y)>t]=\mathrm{Pr}[X>t]\mathrm{Pr}[Y>t]=e^{-(\lambda+\mu)t}$ . Moreover, the joint density that $X$ wins at time $t$ factors as

\lambda e^{-(\lambda+\mu)t}=\frac{\lambda}{\lambda+\mu}\,(\lambda+\mu)e^{-(% \lambda+\mu)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/T_{0}$ and $q/T_{0}$ , 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/T_{0})/(p/T_{0}+q/T_{0})=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 bridge (its §3, with footnote 1 supplying the clock rates) from physical time to combinatorics: since the question “does the attacker ever get ahead?” concerns only the order of block discoveries, not their times, every result below is a statement about a $p$ / $q$ coin sequence, and the time constant $T_{0}$ disappears from the answers. Where the exponential model itself comes from — and how well Zcash’s Equihash fits it — is a deployment question, taken up in Section 8.3.

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)\;=\;\binom{m+n-1}{m}\,p^{n}q^{m},\qquad m=0,1,2,\ldots

— the negative binomial distribution.

Proof.

The event fixes the first $m+n$ trials exactly this far: 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 $\binom{m+n-1}{m}$ orders. Each such order has probability $p^{n-1}q^{m}\cdot p$ . □

Lemma 3.6 (First-to- $n$ race).

In the same sequence, let $H_{n}$ be the event that the honest network reaches $n$ blocks before the attacker does, and $A_{n}$ the reverse. Then $H_{n}$ and $A_{n}$ partition the sample space, and

\begin{gathered}\mathrm{Pr}[H_{n}]=\sum_{m=0}^{n-1}\binom{m+n-1}{m}p^{n}q^{m},% \qquad\mathrm{Pr}[A_{n}]=\sum_{h=0}^{n-1}\binom{h+n-1}{h}q^{n}p^{h},\\ \mathrm{Pr}[H_{n}]+\mathrm{Pr}[A_{n}]=1.\end{gathered}

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 $H_{n}$ says the $n$ -th honest block arrives while the attacker holds $m\leq n-1$ ; summing Proposition 3.5 over those $m$ gives the first sum, and $A_{n}$ 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 itself a limit, not an axiom. A miner’s work is modelled as a stream of candidate evaluations, each an independent Bernoulli trial with a tiny success probability; the number of trials to the first success is geometric, and a geometric law with small success probability, viewed at the scale of its mean, converges to the exponential of Definition 3.1. The step that matters is progress-freeness: a candidate that fails must carry no information usable by the next one. Whether Zcash’s Equihash satisfies this is examined with the deployed parameters in Section 8.3.