Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Stationary distributions of the selfish-mining chain

Definition
BitcoinSelfishUnique

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

bitcoineyal-sirerformal-verificationmarkov-chainmathlibselfish-miningstationary-distributionuniqueness

One predicate over the selfish-mining mission's chain.

IsStationary α γ π — a function π\piπ from states to reals is a stationary distribution of the chain with parameters α,γ\alpha, \gammaα,γ: it is nonnegative on every state; its values on the lead states π(lead n)\pi(\text{lead } n)π(lead n) form a summable sequence; its total mass stateSum π =π(zero)+π(tie)+∑n′π(lead n)= \pi(\text{zero}) + \pi(\text{tie}) + \sum'_n \pi(\text{lead } n)=π(zero)+π(tie)+∑n′​π(lead n) is 1; and it is invariant under one step: for every state sss, π(s)=\pi(s) = π(s)= stateSum (fun t => π t * P α γ t s), the inflow into sss from all states weighted by the one-step transition probabilities.

Formalization Note. Imports Mathlib and the selfish-mining mission's definitions. The selfish-mining mission proved that its stationary α satisfies the balance equations and has mass 1; this mission is about every π\piπ satisfying them.

Definition code
import Definitions.Def_BitcoinSelfishMining

/-!
# Selfish mining: stationary distributions of the Eyal–Sirer chain

This file defines what it means for a function `π : State → ℝ` to be a stationary distribution of
the selfish-mining chain of `Definitions/Def_BitcoinSelfishMining.lean`: it is nonnegative, its
values on the leads form a summable family (so that `stateSum π` is a genuine sum), it has total
mass one and it is invariant under one step of the chain, `π s = Σ_t π t · P(t → s)` for every
state `s` (the sum running over all states via `stateSum`).

The paper's distribution `stationary α` is one such distribution (`stationary_balance`,
`total_mass` in the solutions of `BitcoinSelfishMining`); the theorems in
`Solutions/Sol_BitcoinSelfishUnique_all.lean` show that for `0 < α < 1/2` it is the only one.
-/

namespace BitcoinSelfishUnique

/-- A stationary distribution of the selfish-mining chain: nonnegative, summable over the leads,
total mass one, invariant under one step. -/
structure IsStationary (α γ : ℝ) (π : BitcoinSelfishMining.State → ℝ) : Prop where
  nonneg : ∀ s, 0 ≤ π s
  summable : Summable (fun n : ℕ => π (.lead n))
  mass : BitcoinSelfishMining.stateSum π = 1
  invariant : ∀ s, π s = BitcoinSelfishMining.stateSum (fun t => π t * BitcoinSelfishMining.P α γ t s)

end BitcoinSelfishUnique
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: Def_BitcoinSelfishUnique.lean

This file imports Mathlib and Def_BitcoinSelfishMining.lean and contains a single definition, the structure (predicate) IsStationary. Everything it refers to is unfolded below; the only new declaration is the last block, "The predicate IsStationary".

Definition IsStationary. For real numbers α\alphaα and γ\gammaγ (completely unrestricted: any real values are allowed, including negative values or values larger than 111) and a function π\piπ from the state type to R\mathbb{R}R, the proposition IsStationaryα,γ(π)\mathrm{IsStationary}_{\alpha,\gamma}(\pi)IsStationaryα,γ​(π) holds exactly when the four fields nonneg, summable, mass and invariant listed at the end of the next section all hold. In words: (nonneg) π\piπ takes a value ≥0\ge 0≥0 at every one of the states 000, 0′0'0′, ℓ0,ℓ1,ℓ2,…\ell_0, \ell_1, \ell_2, \dotsℓ0​,ℓ1​,ℓ2​,… (non-strict inequality, so zero values are allowed); (summable) the sequence of values π(ℓ0),π(ℓ1),π(ℓ2),…\pi(\ell_0), \pi(\ell_1), \pi(\ell_2), \dotsπ(ℓ0​),π(ℓ1​),π(ℓ2​),… on the lead states is a summable family of reals (this is Mathlib's Summable, i.e. unconditional convergence of the sum, equivalent for real numbers to absolute convergence; the values at 000 and 0′0'0′ play no role in this field); (mass) the "sum over all states" of π\piπ, defined as π(0)+π(0′)+∑n≥0′π(ℓn)\pi(0) + \pi(0') + {\sum}'_{n\ge 0}\pi(\ell_n)π(0)+π(0′)+∑n≥0′​π(ℓn​) with a tsum tail that is 000 for a non-summable family, equals exactly 111; (invariant) for every state sss, the value π(s)\pi(s)π(s) equals the "sum over all states" of t↦π(t) Pα,γ(t,s)t \mapsto \pi(t)\,P_{\alpha,\gamma}(t,s)t↦π(t)Pα,γ​(t,s), where Pα,γ(t,s)P_{\alpha,\gamma}(t,s)Pα,γ​(t,s) is the one-step weight of going from ttt to sss, itself defined as a three-term sum over outcomes of the outcome's weight (α\alphaα, (1−α)γ(1-\alpha)\gamma(1−α)γ or (1−α)(1−γ)(1-\alpha)(1-\gamma)(1−α)(1−γ)) restricted to the outcomes whose step from ttt lands in sss. Note the direction: π(s)\pi(s)π(s) is compared with the mass flowing into sss from all states ttt (the kernel is evaluated as P(t,s)P(t,s)P(t,s), from ttt to sss), and the condition is an equality, one for each state sss separately. The predicate depends on γ\gammaγ only through the kernel Pα,γP_{\alpha,\gamma}Pα,γ​. The structure is a Prop, so it carries no data beyond the truth of the four conditions.

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γ.

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