The random mining process of the synchronous backbone model, and typicality on a horizon
DefinitionBitcoinBackboneProbThe probabilistic layer under the backbone mission's BitcoinBackbone, over Mathlib's measure theory.
ber p — the Bernoulli() measure on Bool. Round n t — one round's outcomes: one success bit per honest party ( of them) and per adversarial query ( of them); roundMeasure n t p — the product of independent Bernoulli() bits. Trace n t — a sequence of rounds; P n t p — the product measure over all rounds (Measure.infinitePi).
honestCount, advCount — the numbers of successful honest parties and adversarial queries in a round; roundX ( iff some honest success), roundY ( iff exactly one honest success), roundW (); X ω r, Y ω r, Z ω r, W ω r — the same for round of a trace. margin n t p (); rate n t p .
TypicalOn ω lam L — the backbone mission's typicality inequality for every window with . toExecution ω L base advParent — the backbone Execution induced by a trace on the horizon for any network behaviour base and adversarial chain choices advParent: honest party mines in round iff its bit is set; the adversary finds Z ω r blocks; after the execution is frozen (party 0 mines alone, the adversary finds nothing). TypicalTrunc ω lam L — the induced execution is typical in the backbone mission's sense.
Formalization Note. Imports Mathlib and the backbone mission. The adversary is modelled by its query count per round; its strategy (which chains it extends, what it delivers) is the arbitrary advParent/base, quantified universally in the end-to-end theorems.
import Mathlib
import Definitions.Def_BitcoinBackbone
/-!
# The Bitcoin backbone protocol: the probabilistic round model
This file sets up the probabilistic model of mining of Garay, Kiayias and Leonardos
(*The Bitcoin Backbone Protocol*, ePrint 2014/765, Section 3 and Definition 9) on top of the
deterministic analysis of `Definitions.Def_BitcoinBackbone`.
* In every round each of the `n` honest parties finds a block independently with probability `p`
(one proof-of-work query per party and round, as in the paper's `q = 1` flat model), and the
adversary makes `t` queries each of which succeeds independently with probability `p`.
* A round outcome is a pair `(Fin n → Bool) × (Fin t → Bool)` (which honest parties / adversarial
queries succeeded); its law `roundMeasure n t p` is the product of Bernoulli(`p`) measures, so the
honest success count is `Binomial(n, p)` and the adversarial count `Z` is `Binomial(t, p)`.
* A trace is a sequence of round outcomes `ℕ → Round n t`; its law `P n t p` is the infinite product
measure `MeasureTheory.Measure.infinitePi`, so the rounds are independent.
* `X ω r`, `Y ω r`, `Z ω r` are the paper's random variables: successful round, uniquely successful
round (exactly one honest block), number of adversarial blocks.
* `margin n t p = E[Y] - E[Z] = n p (1-p)^(n-1) - t p` is the honest-majority margin and
`rate n t p = margin² / (2 (t+1)²)` the exponential rate of the Hoeffding bounds.
* `TypicalOn ω lam L` is the deterministic typicality hypothesis `Execution.Typical` restricted to
the windows inside the horizon `[0, L]`.
* `toExecution ω L base advParent` turns a trace into a `BitcoinBackbone.Execution` on the horizon
`[1, L]` (rounds after `L` are frozen: party `0` mines alone and the adversary finds nothing),
so that the deterministic theorems (chain growth, common prefix, chain quality) apply to it on
the event `TypicalTrunc ω lam L` that this execution is typical.
-/
namespace BitcoinBackboneProb
/-- The Bernoulli law on `Bool` with success probability `p`. -/
noncomputable def ber (p : unitInterval) : MeasureTheory.Measure Bool :=
ProbabilityTheory.bernoulliMeasure true false p
instance ber_isProbabilityMeasure (p : unitInterval) :
MeasureTheory.IsProbabilityMeasure (ber p) := by
unfold ber; infer_instance
/-- The outcome of one round: which of the `n` honest parties found a block, and which of the `t`
adversarial queries succeeded. -/
abbrev Round (n t : ℕ) : Type := (Fin n → Bool) × (Fin t → Bool)
/-- The law of one round: all `n + t` queries succeed independently with probability `p`. -/
noncomputable def roundMeasure (n t : ℕ) (p : unitInterval) : MeasureTheory.Measure (Round n t) :=
(MeasureTheory.Measure.pi fun _ : Fin n => ber p).prod
(MeasureTheory.Measure.pi fun _ : Fin t => ber p)
instance roundMeasure_isProbabilityMeasure (n t : ℕ) (p : unitInterval) :
MeasureTheory.IsProbabilityMeasure (roundMeasure n t p) := by
unfold roundMeasure; infer_instance
/-- A trace: the outcomes of rounds `0, 1, 2, …`. -/
abbrev Trace (n t : ℕ) : Type := ℕ → Round n t
/-- The law of a trace: rounds are independent, each distributed as `roundMeasure n t p`. -/
noncomputable def P (n t : ℕ) (p : unitInterval) : MeasureTheory.Measure (Trace n t) :=
MeasureTheory.Measure.infinitePi fun _ : ℕ => roundMeasure n t p
instance P_isProbabilityMeasure (n t : ℕ) (p : unitInterval) :
MeasureTheory.IsProbabilityMeasure (P n t p) := by
unfold P; infer_instance
/-- The number of honest parties that found a block in a round outcome. -/
def honestCount {n t : ℕ} (ρ : Round n t) : ℕ :=
(Finset.univ.filter fun i => ρ.1 i = true).card
/-- The number of adversarial blocks found in a round outcome. -/
def advCount {n t : ℕ} (ρ : Round n t) : ℕ :=
(Finset.univ.filter fun j => ρ.2 j = true).card
/-- Round-level `X`: `1` if some honest party found a block in the round outcome, else `0`. -/
def roundX {n t : ℕ} (ρ : Round n t) : ℕ := if 0 < honestCount ρ then 1 else 0
/-- Round-level `Y`: `1` if exactly one honest party found a block, else `0`. -/
def roundY {n t : ℕ} (ρ : Round n t) : ℕ := if honestCount ρ = 1 then 1 else 0
/-- Round-level `W = Z - Y` as a real number (it lies in `[-1, t]`). -/
def roundW {n t : ℕ} (ρ : Round n t) : ℝ := (advCount ρ : ℝ) - (roundY ρ : ℝ)
/-- The paper's `X_r`: `1` if round `r` is successful (some honest block), else `0`. -/
def X {n t : ℕ} (ω : Trace n t) (r : ℕ) : ℕ := roundX (ω r)
/-- The paper's `Y_r`: `1` if round `r` is uniquely successful (exactly one honest block), else `0`. -/
def Y {n t : ℕ} (ω : Trace n t) (r : ℕ) : ℕ := roundY (ω r)
/-- The paper's `Z_r`: the number of adversarial blocks found in round `r`. -/
def Z {n t : ℕ} (ω : Trace n t) (r : ℕ) : ℕ := advCount (ω r)
/-- The real-valued round variable `W_r = Z_r - Y_r` (in `[-1, t]`), whose window sums decide
typicality. -/
def W {n t : ℕ} (ω : Trace n t) (r : ℕ) : ℝ := roundW (ω r)
/-- The honest-majority margin `E[Y_r] - E[Z_r] = n p (1 - p)^(n-1) - t p`. -/
noncomputable def margin (n t : ℕ) (p : unitInterval) : ℝ :=
(n : ℝ) * p * (1 - (p : ℝ)) ^ (n - 1) - (t : ℝ) * p
/-- The exponential rate of the window bounds: `margin² / (2 (t + 1)²)`. -/
noncomputable def rate (n t : ℕ) (p : unitInterval) : ℝ :=
margin n t p ^ 2 / (2 * ((t : ℝ) + 1) ^ 2)
/-- Typicality on the horizon `[0, L]`: the inequality of `BitcoinBackbone.Execution.Typical` for
every window `[a, b]` with `a + lam ≤ b ≤ L`. -/
def TypicalOn {n t : ℕ} (ω : Trace n t) (lam L : ℕ) : Prop :=
∀ a b : ℕ, a + lam ≤ b → b ≤ L →
(∑ i ∈ Finset.Icc a b, Z ω i) < ∑ i ∈ Finset.Ioo a b, Y ω i
/-- The execution of the backbone protocol induced by a trace on the horizon `[1, L]`, for a given
behaviour of the network (`base`) and of the adversary's chain choices (`advParent`). Honest party
`p < n` mines in round `1 ≤ r ≤ L` iff its query succeeded in the trace; the adversary finds
`Z ω r` blocks in round `r ≤ L`. After the horizon the execution is frozen: party `0` mines alone
and the adversary finds nothing, so that typicality after the horizon is automatic. -/
def toExecution {n t : ℕ} (ω : Trace n t) (L : ℕ)
(base advParent : ℕ → ℕ → BitcoinBackbone.Chain) : BitcoinBackbone.Execution where
n := n
mined := fun q r =>
if h : q < n then (if 1 ≤ r ∧ r ≤ L then (ω r).1 ⟨q, h⟩ else decide (L < r ∧ q = 0))
else false
Z := fun r => if r ≤ L then Z ω r else 0
base := base
advParent := advParent
/-- The induced execution (for any network/adversary behaviour, which does not matter here) is
typical in the sense of `BitcoinBackbone.Execution.Typical`. -/
def TypicalTrunc {n t : ℕ} (ω : Trace n t) (lam L : ℕ) : Prop :=
(toExecution ω L (fun _ _ => []) (fun _ _ => [])).Typical lam
end BitcoinBackboneProb
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_BitcoinBackboneProb (namespace BitcoinBackboneProb)
The file imports Mathlib and the deterministic backbone file (whose definitions used here — blocks, chains, executions, Typical, Legal — are unfolded in the last section). Throughout, are arbitrary (possibly ) and ranges over the closed unit interval (endpoints included), used as a real number in arithmetic. One paragraph per declaration, in file order.
1. ber. For , is the measure on given by Mathlib's two-point Bernoulli measure bernoulliMeasure true false p: mass on and on .
2. ber_isProbabilityMeasure (instance). Registers (with proof) that is a probability measure for every .
3. Round. is the set of pairs with and . For (resp. ) the first (resp. second) component has only the empty function. It carries the product -algebra (all subsets of the finite set, since is discrete).
4. roundMeasure. is the product measure
on : all coordinates are independent, each with probability . (An empty product is the Dirac mass on the empty function.)
5. roundMeasure_isProbabilityMeasure (instance). Registers (with proof) that is a probability measure.
6. Trace. : sequences of round outcomes indexed by all , starting at , with the product -algebra.
7. P. , the infinite product measure on (Mathlib's Measure.infinitePi): the coordinates are i.i.d. with law . In the theorems, "as a real" means the extended-nonnegative measure of converted to ; it is defined for every set (outer measure for non-measurable ) and lies in .
8. P_isProbabilityMeasure (instance). Registers (with proof) that is a probability measure.
9. honestCount. For , , a natural number.
10. advCount. For , , a natural number.
11. roundX. if , else (a natural number).
12. roundY. if , else (a natural number).
13. roundW. , computed in (both terms cast to reals, so no truncation; values in ).
14. X. For a trace and any (including ), .
15. Y. , for every .
16. Z. , for every .
17. W. , for every .
18. margin. The real number
where are cast to and the exponent is natural-number subtraction truncated at . Edge values: gives exponent and ; gives (with , also at ); for and , ; for , . No sign is imposed.
19. rate. The real number
always (and exactly when ); the denominator is at least .
20. TypicalOn. For a trace and , is the proposition: for all with and ,
(closed window on the left, open window on the right, which is empty when ; sums in ; strict inequality; allowed). Edge cases: if there are no admissible windows and the proposition holds vacuously; for it is false for every and every (window gives ); for it is false for every whenever (window has empty right-hand sum).
21. toExecution. For a trace , a horizon , and arbitrary functions , is the deterministic execution with number of honest parties , , , and
So honest successes come from the trace for rounds only (round : nobody mines), while the adversarial count comes from the trace for rounds (round included). After the horizon, party alone mines in every round (if ; if nobody ever mines) and the adversary finds nothing. Hence the execution's uniquely-successful indicator is for , , and for it is if , if . When , no round's honest outcome is taken from the trace and only is used.
22. TypicalTrunc. is the proposition , where are the constant functions returning the empty chain. Unfolded: for all with (no upper bound ; windows may extend past or lie entirely beyond the horizon),
with as in item 21. Edge cases: false for every when (window , has empty right-hand sum), and false for every when (window , gives ). The choice does not affect the value, since does not involve base/parent chains.
Imported definitions from the deterministic backbone file (unfolded)
- Blocks and chains. A block is either (with ; "found by honest party in round ") or (with ; "the -th adversarial block of round "). The round of a block is its . A chain is a finite list of blocks (oldest first; the empty list is allowed).
- Executions. An execution consists of: a number ; a function (: party found a block in round ); a function (adversarial block count per round); and two functions . Derived notions:
- honest chain at the end of round : and followed by the block if , else just ;
- , and if , else ;
- extends a chain by block : if , this means , and ; if , it means and ;
- a chain is valid for iff for every , extends the prefix in the above sense (in particular extends the empty chain).
- Typical execution. holds iff for all with (no upper bound on ):
It depends only on , and , not on . Edge case: if the window , has an empty open window, so is false for every execution .
- Legal execution. is the conjunction of the following six conditions:
- for every ;
- for all and , is a valid chain;
- for all , all , every block of has round (so is empty);
- for all and all : the length of is at most the length of ;
- for all with , is a valid chain;
- for all with , every block of has round .
- Execution induced by a trace. For a trace , a horizon and arbitrary functions , the execution has , , , and
Consequently for , , and for : if (only party mines) and if (nobody ever mines when ). The adversarial count of round is taken from the trace even though no honest party mines in round . Condition 1 of holds automatically for these executions; the other conditions depend on .
- Truncated typicality. where are the constant functions returning the empty chain. Explicitly: for all with (arbitrarily large , windows may lie partly or wholly beyond ),
with as just described. Edge cases: is false for every if (see above), and also false for every if (the window , gives ).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.