Stationary distributions of the selfish-mining chain
DefinitionBitcoinSelfishUniqueOne predicate over the selfish-mining mission's chain.
IsStationary α γ π — a function from states to reals is a stationary distribution of the chain with parameters : it is nonnegative on every state; its values on the lead states form a summable sequence; its total mass stateSum π is 1; and it is invariant under one step: for every state , stateSum (fun t => π t * P α γ t s), the inflow into 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 satisfying them.
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
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 and (completely unrestricted: any real values are allowed, including negative values or values larger than ) and a function from the state type to , the proposition holds exactly when the four fields nonneg, summable, mass and invariant listed at the end of the next section all hold. In words: (nonneg) takes a value at every one of the states , , (non-strict inequality, so zero values are allowed); (summable) the sequence of values 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 and play no role in this field); (mass) the "sum over all states" of , defined as with a tsum tail that is for a non-summable family, equals exactly ; (invariant) for every state , the value equals the "sum over all states" of , where is the one-step weight of going from to , itself defined as a three-term sum over outcomes of the outcome's weight (, or ) restricted to the outcomes whose step from lands in . Note the direction: is compared with the mass flowing into from all states (the kernel is evaluated as , from to ), and the condition is an equality, one for each state separately. The predicate depends on only through the kernel . 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, and are real numbers. Unless a hypothesis is listed explicitly for the declaration below, nothing restricts them: they need not lie in , so the "probabilities" below are simply real numbers that may be negative or exceed .
States. The state type has exactly these elements: a state (the constructor zero), a state (the constructor tie), and, for every natural number , a state (the constructor lead n). The documentation in the definition file says that encodes a private lead of blocks, so is "lead ", is "lead ", and is "lead "; the code itself only ever works with the index .
Outcomes and their weights. There are exactly three outcomes, , (honest miner on the pool's branch) and (honest miner on the honest branch), with real weights
Write for the sum of the two honest weights. As a polynomial identity, valid for all real , one has and ; the definitions, however, are written with the unsimplified expressions.
One-step map. The function sends a state and an outcome to a state:
- ; ;
- for each of the three outcomes ;
- ; ;
- ; ;
- for every : ; .
Transition kernel. For states ,
where is if the equality holds and 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 | to | |
|---|---|---|
| () | ||
| () |
Every other pair has .
Sums over all states. For a real-valued function on states,
where is Mathlib's tsum: if the family is summable (unconditionally summable in , 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 . 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 and a function from states to , 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):
- nonneg: for every state , .
- summable: the family is summable in .
- mass: , i.e. . (Because of condition 2 the tail here is the genuine infinite sum, not the fallback.)
- invariant: for every state ,
By the table above, for each fixed target the family 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 :
- at : ;
- at : ;
- at : ;
- at : ;
- at for every : .
Note that the invariant condition does not mention except through and , which simplify to and for every real .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.