Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Balance at state 0' for any stationary distribution

Proved
BitcoinSelfishUnique.balance_tie_of

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

bitcoineyal-sirerformal-verificationmarkov-chainmathlibselfish-miningstationary-distributionuniqueness

Under the same hypotheses: π0′=(1−α)π1\pi_{0'} = (1-\alpha)\pi_1π0′​=(1−α)π1​.

Preamble
import Definitions.Def_BitcoinSelfishUnique
import Definitions.Def_BitcoinSelfishMining
open BitcoinSelfishUnique BitcoinSelfishMining
Formal statement
theorem BitcoinSelfishUnique.balance_tie_of (α γ : ℝ) (π : BitcoinSelfishMining.State → ℝ)
    (h : BitcoinSelfishUnique.IsStationary α γ π) :
    π .tie = (1 - α) * π (.lead 0) := 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_balance_tie_of.lean

Theorem BitcoinSelfishUnique.balance_tie_of. For every real number α\alphaα, every real number γ\gammaγ, and every function π\piπ from the state type to R\mathbb{R}R, under the single hypothesis h:IsStationaryα,γ(π)h : \mathrm{IsStationary}_{\alpha,\gamma}(\pi)h:IsStationaryα,γ​(π) (which bundles the four conditions nonneg, summable, mass and invariant spelled out below), the following equality of real numbers holds:

π(0′)=(1−α) π(ℓ0).\pi(0') = (1-\alpha)\,\pi(\ell_0).π(0′)=(1−α)π(ℓ0​).

Here 0′0'0′ is the state tie and ℓ0\ell_0ℓ0​ is the state lead 0 (described in the definition file's documentation as a private lead of exactly one block). The statement places no hypothesis on α\alphaα or γ\gammaγ beyond their being real numbers: no assumption 0<α0<\alpha0<α, α<1/2\alpha<1/2α<1/2, or anything about γ\gammaγ. The conclusion is written with the literal coefficient 1−α1-\alpha1−α, whereas the invariant condition at the state 0′0'0′ (see below) is written with the coefficient h(α,γ)=(1−α)γ+(1−α)(1−γ)h(\alpha,\gamma) = (1-\alpha)\gamma + (1-\alpha)(1-\gamma)h(α,γ)=(1−α)γ+(1−α)(1−γ), the only incoming weight to 0′0'0′ being Pα,γ(ℓ0,0′)=h(α,γ)P_{\alpha,\gamma}(\ell_0,0') = h(\alpha,\gamma)Pα,γ​(ℓ0​,0′)=h(α,γ); the two coefficients are equal as polynomials for all real α,γ\alpha,\gammaα,γ. The conclusion involves no division and no infinite sum. All four fields of hhh are available as hypotheses; the statement itself does not indicate which of them (in particular whether nonneg, summable or mass) 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γ.

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