Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The stationary distribution is unique

Proved
BitcoinSelfishUnique.stationary_unique

by pitimespi · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitcoineyal-sirerformal-verificationmarkov-chainmathlibselfish-miningstationary-distributionuniqueness

For 0<α<1/20 < \alpha < 1/20<α<1/2, any γ\gammaγ, and any π\piπ with IsStationary α γ π: π(s)=\pi(s) = π(s)= stationary α s for every state sss. With the geometric form, the balance equations at 0′0'0′ and 111 express every value through π0\pi_0π0​, and total mass 1 fixes π0=(1−2α)/(2α3−4α2+1)\pi_0 = (1-2\alpha)/(2\alpha^3 - 4\alpha^2 + 1)π0​=(1−2α)/(2α3−4α2+1), the paper's equation (7). Together with the selfish-mining mission this makes the revenue analysis a statement about the chain's only stationary distribution.

Preamble
import Definitions.Def_BitcoinSelfishUnique
import Definitions.Def_BitcoinSelfishMining
open BitcoinSelfishUnique BitcoinSelfishMining
Formal statement
theorem BitcoinSelfishUnique.stationary_unique (α γ : ℝ) (π : BitcoinSelfishMining.State → ℝ)
    (h0 : 0 < α) (h1 : α < 1 / 2) (h : BitcoinSelfishUnique.IsStationary α γ π)
    (s : BitcoinSelfishMining.State) : π s = BitcoinSelfishMining.stationary α s := by sorry
Source
I. Eyal, E. G. Sirer, Majority is not Enough: Bitcoin Mining is Vulnerable, Financial Cryptography 2014, arXiv:1311.0243, Section 4, equation (7) (the stationary distribution): https://arxiv.org/abs/1311.0243; the selfish-mining mission's BitcoinSelfishMining (State, P, stateSum, stationary)
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)

Read-back: Thm_BitcoinSelfishUnique_stationary_unique.lean

Theorem BitcoinSelfishUnique.stationary_unique. For every real number α\alphaα, every real number γ\gammaγ, and every function π\piπ from the state type to R\mathbb{R}R, under the hypotheses

  • h0:0<αh_0 : 0 < \alphah0​:0<α (strict),
  • h1:α<1/2h_1 : \alpha < 1/2h1​:α<1/2 (strict; 1/21/21/2 is the real number one half),
  • h:IsStationaryα,γ(π)h : \mathrm{IsStationary}_{\alpha,\gamma}(\pi)h:IsStationaryα,γ​(π) (which bundles the four conditions nonneg, summable, mass and invariant spelled out below),

and for every state sss (i.e. s=0s = 0s=0, s=0′s = 0's=0′, or s=ℓns = \ell_ns=ℓn​ for some natural number nnn), the following equality of real numbers holds:

π(s)=σα(s),\pi(s) = \sigma_\alpha(s),π(s)=σα​(s),

where σα\sigma_\alphaσα​ is the specific function stationary α unfolded in the last block below. Spelled out, the conclusion is the conjunction, over all states, of

π(0)=1−2αD(α),π(0′)=(1−α)(α−2α2)D(α),π(ℓn)=(α1−α)n⋅α−2α2D(α)  for every n≥0,\pi(0) = \frac{1-2\alpha}{D(\alpha)},\qquad \pi(0') = \frac{(1-\alpha)(\alpha-2\alpha^2)}{D(\alpha)},\qquad \pi(\ell_n) = \Big(\frac{\alpha}{1-\alpha}\Big)^{n}\cdot\frac{\alpha-2\alpha^2}{D(\alpha)}\ \text{ for every } n \ge 0,π(0)=D(α)1−2α​,π(0′)=D(α)(1−α)(α−2α2)​,π(ℓn​)=(1−αα​)n⋅D(α)α−2α2​  for every n≥0,

with D(α)=2α3−4α2+1D(\alpha) = 2\alpha^3 - 4\alpha^2 + 1D(α)=2α3−4α2+1 and real division (which returns 000 for a zero divisor; the statement contains no separate hypothesis D(α)≠0D(\alpha)\neq 0D(α)=0, while h1h_1h1​ ensures 1−α≠01-\alpha \ne 01−α=0). There is no hypothesis on γ\gammaγ: it is an arbitrary real number (possibly negative or larger than 111), it enters only through the kernel Pα,γP_{\alpha,\gamma}Pα,γ​ inside the hypothesis hhh, and the right-hand side σα(s)\sigma_\alpha(s)σα​(s) does not depend on it. The statement is a pointwise equality of functions (every stationary π\piπ in the sense of IsStationary agrees with σα\sigma_\alphaσα​ at every state); it is phrased as "for all π\piπ satisfying the predicate, π=σα\pi = \sigma_\alphaπ=σα​ pointwise", not as a unique-existence statement, and it does not itself assert that σα\sigma_\alphaσα​ satisfies the predicate. All four fields of hhh are available as hypotheses; the statement itself does not indicate which of them are needed.

Setting and unfolded definitions (as they are actually defined in the bundle)

Throughout, α\alphaα and γ\gammaγ are real numbers. Unless a hypothesis is listed explicitly for the declaration below, nothing restricts them: they need not lie in [0,1][0,1][0,1], so the "probabilities" below are simply real numbers that may be negative or exceed 111.

States. The state type has exactly these elements: a state 000 (the constructor zero), a state 0′0'0′ (the constructor tie), and, for every natural number n=0,1,2,…n = 0, 1, 2, \dotsn=0,1,2,…, a state ℓn\ell_nℓn​ (the constructor lead n). The documentation in the definition file says that ℓn\ell_nℓn​ encodes a private lead of n+1n+1n+1 blocks, so ℓ0\ell_0ℓ0​ is "lead 111", ℓ1\ell_1ℓ1​ is "lead 222", and ℓn+2\ell_{n+2}ℓn+2​ is "lead n+3n+3n+3"; the code itself only ever works with the index nnn.

Outcomes and their weights. There are exactly three outcomes, pool\mathrm{pool}pool, hP\mathrm{hP}hP (honest miner on the pool's branch) and hO\mathrm{hO}hO (honest miner on the honest branch), with real weights

wα,γ(pool)=α,wα,γ(hP)=(1−α) γ,wα,γ(hO)=(1−α)(1−γ).w_{\alpha,\gamma}(\mathrm{pool}) = \alpha,\qquad w_{\alpha,\gamma}(\mathrm{hP}) = (1-\alpha)\,\gamma,\qquad w_{\alpha,\gamma}(\mathrm{hO}) = (1-\alpha)(1-\gamma).wα,γ​(pool)=α,wα,γ​(hP)=(1−α)γ,wα,γ​(hO)=(1−α)(1−γ).

Write h(α,γ):=(1−α)γ+(1−α)(1−γ)h(\alpha,\gamma) := (1-\alpha)\gamma + (1-\alpha)(1-\gamma)h(α,γ):=(1−α)γ+(1−α)(1−γ) for the sum of the two honest weights. As a polynomial identity, valid for all real α,γ\alpha,\gammaα,γ, one has h(α,γ)=1−αh(\alpha,\gamma) = 1-\alphah(α,γ)=1−α and α+h(α,γ)=1\alpha + h(\alpha,\gamma) = 1α+h(α,γ)=1; the definitions, however, are written with the unsimplified expressions.

One-step map. The function step(s,o)\mathrm{step}(s,o)step(s,o) sends a state and an outcome to a state:

  • step(0,pool)=ℓ0\mathrm{step}(0,\mathrm{pool}) = \ell_0step(0,pool)=ℓ0​; step(0,hP)=step(0,hO)=0\mathrm{step}(0,\mathrm{hP}) = \mathrm{step}(0,\mathrm{hO}) = 0step(0,hP)=step(0,hO)=0;
  • step(0′,o)=0\mathrm{step}(0',o) = 0step(0′,o)=0 for each of the three outcomes ooo;
  • step(ℓ0,pool)=ℓ1\mathrm{step}(\ell_0,\mathrm{pool}) = \ell_1step(ℓ0​,pool)=ℓ1​; step(ℓ0,hP)=step(ℓ0,hO)=0′\mathrm{step}(\ell_0,\mathrm{hP}) = \mathrm{step}(\ell_0,\mathrm{hO}) = 0'step(ℓ0​,hP)=step(ℓ0​,hO)=0′;
  • step(ℓ1,pool)=ℓ2\mathrm{step}(\ell_1,\mathrm{pool}) = \ell_2step(ℓ1​,pool)=ℓ2​; step(ℓ1,hP)=step(ℓ1,hO)=0\mathrm{step}(\ell_1,\mathrm{hP}) = \mathrm{step}(\ell_1,\mathrm{hO}) = 0step(ℓ1​,hP)=step(ℓ1​,hO)=0;
  • for every n≥0n \ge 0n≥0: step(ℓn+2,pool)=ℓn+3\mathrm{step}(\ell_{n+2},\mathrm{pool}) = \ell_{n+3}step(ℓn+2​,pool)=ℓn+3​; step(ℓn+2,hP)=step(ℓn+2,hO)=ℓn+1\mathrm{step}(\ell_{n+2},\mathrm{hP}) = \mathrm{step}(\ell_{n+2},\mathrm{hO}) = \ell_{n+1}step(ℓn+2​,hP)=step(ℓn+2​,hO)=ℓn+1​.

Transition kernel. For states s,ts,ts,t,

Pα,γ(s,t):=∑o∈{pool, hP, hO}[step(s,o)=t]  wα,γ(o),P_{\alpha,\gamma}(s,t) := \sum_{o \in \{\mathrm{pool},\,\mathrm{hP},\,\mathrm{hO}\}} \big[\mathrm{step}(s,o) = t\big]\; w_{\alpha,\gamma}(o),Pα,γ​(s,t):=o∈{pool,hP,hO}∑​[step(s,o)=t]wα,γ​(o),

where [ ⋅ ][\,\cdot\,][⋅] is 111 if the equality holds and 000 otherwise (the three-term sum is taken in the order pool, hP, hO). Reading off the step map, the only entries that are not literally a sum of three zeros are:

from sssto tttPα,γ(s,t)P_{\alpha,\gamma}(s,t)Pα,γ​(s,t)
000ℓ0\ell_0ℓ0​α\alphaα
000000h(α,γ)h(\alpha,\gamma)h(α,γ)
0′0'0′000α+h(α,γ)\alpha + h(\alpha,\gamma)α+h(α,γ)
ℓ0\ell_0ℓ0​ℓ1\ell_1ℓ1​α\alphaα
ℓ0\ell_0ℓ0​0′0'0′h(α,γ)h(\alpha,\gamma)h(α,γ)
ℓ1\ell_1ℓ1​ℓ2\ell_2ℓ2​α\alphaα
ℓ1\ell_1ℓ1​000h(α,γ)h(\alpha,\gamma)h(α,γ)
ℓn+2\ell_{n+2}ℓn+2​ (n≥0n \ge 0n≥0)ℓn+3\ell_{n+3}ℓn+3​α\alphaα
ℓn+2\ell_{n+2}ℓn+2​ (n≥0n \ge 0n≥0)ℓn+1\ell_{n+1}ℓn+1​h(α,γ)h(\alpha,\gamma)h(α,γ)

Every other pair (s,t)(s,t)(s,t) has Pα,γ(s,t)=0P_{\alpha,\gamma}(s,t) = 0Pα,γ​(s,t)=0.

Sums over all states. For a real-valued function fff on states,

stateSum(f):=f(0)+f(0′)+∑n=0∞′f(ℓn),\mathrm{stateSum}(f) := f(0) + f(0') + {\sum_{n=0}^{\infty}}' f(\ell_n),stateSum(f):=f(0)+f(0′)+n=0∑∞​′f(ℓn​),

where ∑′{\sum}'∑′ is Mathlib's tsum: if the family (f(ℓn))n∈N(f(\ell_n))_{n\in\mathbb{N}}(f(ℓn​))n∈N​ is summable (unconditionally summable in R\mathbb{R}R, which for real numbers is the same as absolute convergence), it is the ordinary infinite sum; if the family is not summable, the tail is defined to be 000. A family with only finitely many nonzero terms is summable and its tsum is the finite sum of those terms.

The predicate "IsStationary". For real α,γ\alpha,\gammaα,γ and a function π\piπ from states to R\mathbb{R}R, IsStationaryα,γ(π)\mathrm{IsStationary}_{\alpha,\gamma}(\pi)IsStationaryα,γ​(π) is the conjunction of the following four conditions (it is a structure with four fields; being given it as a hypothesis means all four are available, and the statement of a theorem does not say which of them its proof uses):

  1. nonneg: for every state sss, 0≤π(s)0 \le \pi(s)0≤π(s).
  2. summable: the family (π(ℓn))n∈N(\pi(\ell_n))_{n \in \mathbb{N}}(π(ℓn​))n∈N​ is summable in R\mathbb{R}R.
  3. mass: stateSum(π)=1\mathrm{stateSum}(\pi) = 1stateSum(π)=1, i.e. π(0)+π(0′)+∑n′π(ℓn)=1\pi(0) + \pi(0') + {\sum}'_{n} \pi(\ell_n) = 1π(0)+π(0′)+∑n′​π(ℓn​)=1. (Because of condition 2 the tail here is the genuine infinite sum, not the 000 fallback.)
  4. invariant: for every state sss,
π(s)=stateSum(t↦π(t) Pα,γ(t,s))=π(0)Pα,γ(0,s)+π(0′)Pα,γ(0′,s)+∑n=0∞′π(ℓn) Pα,γ(ℓn,s).\pi(s) = \mathrm{stateSum}\big(t \mapsto \pi(t)\,P_{\alpha,\gamma}(t,s)\big) = \pi(0)P_{\alpha,\gamma}(0,s) + \pi(0')P_{\alpha,\gamma}(0',s) + {\sum_{n=0}^{\infty}}' \pi(\ell_n)\,P_{\alpha,\gamma}(\ell_n,s).π(s)=stateSum(t↦π(t)Pα,γ​(t,s))=π(0)Pα,γ​(0,s)+π(0′)Pα,γ​(0′,s)+n=0∑∞​′π(ℓn​)Pα,γ​(ℓn​,s).

By the table above, for each fixed target sss the family n↦π(ℓn)Pα,γ(ℓn,s)n \mapsto \pi(\ell_n)P_{\alpha,\gamma}(\ell_n,s)n↦π(ℓn​)Pα,γ​(ℓn​,s) has at most one nonzero term, so this tail is always a genuine (finite) sum. Unfolding the table, condition 4 says exactly the following five families of equations, where h=h(α,γ)=(1−α)γ+(1−α)(1−γ)h = h(\alpha,\gamma) = (1-\alpha)\gamma + (1-\alpha)(1-\gamma)h=h(α,γ)=(1−α)γ+(1−α)(1−γ):

  • at s=0s = 0s=0: π(0)=h π(0)+(α+h) π(0′)+h π(ℓ1)\pi(0) = h\,\pi(0) + (\alpha + h)\,\pi(0') + h\,\pi(\ell_1)π(0)=hπ(0)+(α+h)π(0′)+hπ(ℓ1​);
  • at s=0′s = 0's=0′: π(0′)=h π(ℓ0)\pi(0') = h\,\pi(\ell_0)π(0′)=hπ(ℓ0​);
  • at s=ℓ0s = \ell_0s=ℓ0​: π(ℓ0)=α π(0)\pi(\ell_0) = \alpha\,\pi(0)π(ℓ0​)=απ(0);
  • at s=ℓ1s = \ell_1s=ℓ1​: π(ℓ1)=α π(ℓ0)+h π(ℓ2)\pi(\ell_1) = \alpha\,\pi(\ell_0) + h\,\pi(\ell_2)π(ℓ1​)=απ(ℓ0​)+hπ(ℓ2​);
  • at s=ℓm+2s = \ell_{m+2}s=ℓm+2​ for every m≥0m \ge 0m≥0: π(ℓm+2)=α π(ℓm+1)+h π(ℓm+3)\pi(\ell_{m+2}) = \alpha\,\pi(\ell_{m+1}) + h\,\pi(\ell_{m+3})π(ℓm+2​)=απ(ℓm+1​)+hπ(ℓm+3​).

Note that the invariant condition does not mention γ\gammaγ except through h(α,γ)h(\alpha,\gamma)h(α,γ) and α+h(α,γ)\alpha + h(\alpha,\gamma)α+h(α,γ), which simplify to 1−α1-\alpha1−α and 111 for every real γ\gammaγ.

The candidate distribution "stationary". Let D(α):=2α3−4α2+1D(\alpha) := 2\alpha^3 - 4\alpha^2 + 1D(α):=2α3−4α2+1 (the definition denom). The function σα\sigma_\alphaσα​ (the definition stationary α) from states to R\mathbb{R}R is

σα(0)=1−2αD(α),σα(0′)=(1−α)(α−2α2)D(α),σα(ℓn)=(α1−α)n⋅α−2α2D(α)(n≥0).\sigma_\alpha(0) = \frac{1-2\alpha}{D(\alpha)},\qquad \sigma_\alpha(0') = \frac{(1-\alpha)(\alpha - 2\alpha^2)}{D(\alpha)},\qquad \sigma_\alpha(\ell_n) = \Big(\frac{\alpha}{1-\alpha}\Big)^{n}\cdot\frac{\alpha - 2\alpha^2}{D(\alpha)}\quad (n \ge 0).σα​(0)=D(α)1−2α​,σα​(0′)=D(α)(1−α)(α−2α2)​,σα​(ℓn​)=(1−αα​)n⋅D(α)α−2α2​(n≥0).

Here /// is real division with the convention x/0=0x/0 = 0x/0=0: if D(α)=0D(\alpha) = 0D(α)=0 then all three values are 000, and if α=1\alpha = 1α=1 then α/(1−α)=0\alpha/(1-\alpha) = 0α/(1−α)=0. The exponent nnn is a natural number, so (α/(1−α))0=1(\alpha/(1-\alpha))^0 = 1(α/(1−α))0=1 (even when the base is 000). The function σα\sigma_\alphaσα​ does not depend on γ\gammaγ.

Human review
  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me