(toExecution ω L base advParent).Typical lam ↔ TypicalTrunc ω lam L.
Preamble
import Definitions.Def_BitcoinBackboneProb
import Definitions.Def_BitcoinBackbone
open BitcoinBackboneProb BitcoinBackbone
open MeasureTheory ProbabilityTheory
Formal statement
theorem BitcoinBackboneProb.typical_toExecution_iff {n t : ℕ} (ω : Trace n t) (lam L : ℕ)
(base advParent : ℕ → ℕ → BitcoinBackbone.Chain) :
(toExecution ω L base advParent).Typical lam ↔ TypicalTrunc ω lam L := by sorry
Source
J. Garay, A. Kiayias, N. Leonardos, The Bitcoin Backbone Protocol: Analysis and Applications, EUROCRYPT 2015 (full version ePrint 2014/765): https://eprint.iacr.org/2014/765, Definition 9 (typical execution), Theorem 10, the honest-majority assumption; W. Hoeffding (1963) for the concentration bound; the backbone mission BitcoinBackbone (Execution, Typical, chain growth, common prefix, chain quality)
Read-back
What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Statement. For all natural numbers n,t (implicit, determined by the trace), every trace ω∈Ωn,t, all λ,L∈N, and all functions β,α:N×N→Chain, with no further hypotheses:
Typical(Eω,L[β,α],λ)⟺TypTrunc(ω,λ,L).
That is, typicality of the execution induced by ω with horizon L and base/parent chains β,α holds exactly when typicality of the induced execution with the constant-empty base/parent chains holds. No probability measure and no parameter p is involved. (Both sides are false for every ω when λ≤1 or n=0; see the edge cases below.)
Probabilistic round model (unfolded)
Parameters.n,t∈N are arbitrary natural numbers (either may be 0): n is the number of honest parties, t the number of adversarial queries per round. p is an element of the closed unit interval [0,1] (so p=0 and p=1 are allowed); wherever it appears in arithmetic it is the real number p. All casts of n,t and other naturals into formulas are casts into R (so (λ−3), (k−1) etc. below are real subtractions and may be negative), except where a natural-number subtraction is explicitly flagged.
Bernoulli law berp. The two-point Bernoulli measure on {true,false} built by Mathlib's bernoulliMeasure true false p: mass p on true and mass 1−p on false. It is a probability measure.
Round outcomes Rn,t. A round outcome is a pair ρ=(ρ1,ρ2) with ρ1:{0,…,n−1}→{true,false} (which honest parties succeeded) and ρ2:{0,…,t−1}→{true,false} (which adversarial queries succeeded). If n=0 (resp. t=0) the corresponding component is the unique empty function.
Round law μn,t,p. The product measure
μn,t,p=(i=0⨂n−1berp)⊗(j=0⨂t−1berp)
on Rn,t (product σ-algebra): all n+t coordinates are independent, each true with probability p. It is a probability measure.
Traces Ωn,t. A trace is an infinite sequence ω=(ω0,ω1,ω2,…) of round outcomes, indexed by allr∈N starting at r=0; Ωn,t=Rn,tN with the product σ-algebra.
Trace law Pn,t,p. The infinite product probability measure Pn,t,p=⨂r∈Nμn,t,p on Ωn,t (Mathlib's Measure.infinitePi): the coordinates ωr are i.i.d. with law μn,t,p. It is a probability measure. For any set A⊆Ωn,t (measurable or not; non-measurable sets get their outer measure), Pn,t,p(A) below denotes the real number obtained by converting the (extended-nonnegative) measure of A to R; it lies in [0,1].
Round indicators.x(ρ)=1 if #H(ρ)>0 and 0 otherwise; y(ρ)=1 if #H(ρ)=1 and 0 otherwise (both natural numbers); w(ρ)=#A(ρ)−y(ρ) computed in R.
Trace variables. For ω∈Ωn,t and r∈N (including r=0): Xr(ω)=x(ωr), Yr(ω)=y(ωr), Zr(ω)=#A(ωr) (natural numbers), Wr(ω)=w(ωr)∈R. So Xr,Yr∈{0,1} and Zr∈{0,…,t}.
Margin.
m(n,t,p)=np(1−p)n−˙1−tp∈R,
where n−˙1 is natural-number subtraction (truncated at 0): for n=0 the exponent is 0 and m=−tp; for n=1, m=p−tp; the convention 00=1 applies, so for n=1, p=1 the factor (1−p)0 equals 1.
Rate.
κ(n,t,p)=2(t+1)2m(n,t,p)2≥0
(the denominator is at least 2, never zero).
Window conventions
For natural numbers a,b: [a,b]={a,a+1,…,b} (closed window; empty if a>b, a single point if a=b) and (a,b)={a+1,…,b−1} (open window; empty whenever b≤a+1). A sum over an empty index set is 0. Sums of the natural-number variables Yi,Zi are computed in N and compared there.
Deterministic executions (unfolded)
Blocks and chains. A block is either honest(q,r) (with q,r∈N; "found by honest party q in round r") or adv(r,j) (with r,j∈N; "the j-th adversarial block of round r"). The round of a block is its r. A chain is a finite list of blocks (oldest first; the empty list is allowed).
Executions. An execution E consists of: a number E.n∈N; a function minedE:N×N→{true,false} (minedE(q,r): party q found a block in round r); a function ZE:N→N (adversarial block count per round); and two functions baseE,advParentE:N×N→Chain. Derived notions:
honest chain at the end of round r: chainE(q,0)=[] and chainE(q,r+1)=baseE(q,r+1) followed by the block honest(q,r+1) if minedE(q,r+1), else just baseE(q,r+1);
#HE(r)=#{q∈{0,…,E.n−1}:minedE(q,r)}, and YrE=1 if #HE(r)=1, else 0;
Eextends a chain C by block B: if B=honest(q,r), this means q<E.n, minedE(q,r)=true and C=baseE(q,r); if B=adv(r,j), it means j<ZrE and C=advParentE(r,j);
a chain C=(C0,…,Cℓ−1) is valid for E iff for every i<ℓ, Ci extends the prefix (C0,…,Ci−1) in the above sense (in particular C0 extends the empty chain).
Typical execution.Typical(E,λ) holds iff for alla,b∈N with a+λ≤b (no upper bound on b):
i∈[a,b]∑ZiE<i∈(a,b)∑YiE.
It depends only on E.n, minedE and ZE, not on baseE,advParentE. Edge case: if λ≤1 the window a=0, b=λ has an empty open window, so Typical(E,λ) is false for every execution E.
Legal execution.Legal(E) is the conjunction of the following six conditions:
minedE(q,0)=false for every q∈N;
for all q<E.n and r≥1, baseE(q,r) is a valid chain;
for all q<E.n, all r, every block of baseE(q,r) has round <r (so baseE(q,0) is empty);
for all q,q′<E.n and all r: the length of chainE(q′,r) is at most the length of baseE(q,r+1);
for all r,j with j<ZrE, advParentE(r,j) is a valid chain;
for all r,j with j<ZrE, every block of advParentE(r,j) has round ≤r.
Execution induced by a trace. For a trace ω∈Ωn,t, a horizon L∈N and arbitrary functions β,α:N×N→Chain, the execution Eω,L[β,α] has E.n=n, base=β, advParent=α, and
Consequently YrE=Yr(ω) for 1≤r≤L, Y0E=0, and for r>L: YrE=1 if n≥1 (only party 0 mines) and YrE=0 if n=0 (nobody ever mines when n=0). The adversarial count of round 0 is taken from the trace even though no honest party mines in round 0. Condition 1 of Legal holds automatically for these executions; the other conditions depend on β,α.
Truncated typicality.TypTrunc(ω,λ,L):⟺Typical(Eω,L[β0,α0],λ) where β0,α0 are the constant functions returning the empty chain. Explicitly: for all a,b with a+λ≤b (arbitrarily large b, windows may lie partly or wholly beyond L),
i∈[a,b]∑ZiE<i∈(a,b)∑YiE
with ZE,YE as just described. Edge cases: TypTrunc is false for every ω if λ≤1 (see above), and also false for every ω if n=0 (the window a=L+1, b=L+1+λ gives 0<0).
Confirmed by the moderator at approval.