Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The synchronous backbone model: executions, valid chains, typical executions

Definition
BitcoinBackbone

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

backbonebitcoinchain-growthchain-qualitycommon-prefixformal-verificationgaray-kiayias-leonardosmathlibnakamoto-consensus

The deterministic core of Garay, Kiayias and Leonardos's synchronous analysis, over Mathlib.

Block — honest p r (found by honest party ppp in round rrr) or adv r j (the jjj-th adversarial block of round rrr); Block.round, Block.isHonest. Chain — a list of blocks oldest first (genesis omitted); Chain.work is its length; Chain.upTo C t the prefix of blocks of round ≤t\le t≤t.

Execution — a trace: the number nnn of honest parties, mined p r (whether ppp found a block in round rrr), Z r (the adversary's block count in round rrr), base p r (the chain ppp adopted at the start of round rrr after maxvalid), advParent r j (the chain the adversary's jjj-th block of round rrr extends). Derived: chain p r (the end-of-round chain: base, plus ppp's own block if mined; the empty chain at round 0), honestCount r, X r (1 iff some honest block in round rrr), Y r (1 iff exactly one honest block in round rrr).

Extends E parent B and ValidChain E C — every block of CCC sits on exactly the chain its creator extended (the hash-chain abstraction: a block determines its ancestry). Legal E — the rules of the synchronous model: nothing mined in round 0; adopted chains are valid and made of earlier rounds' blocks; every honest chain of round rrr is at most as long as what any honest party adopts in round r+1r+1r+1 (maxvalid over delivered chains); the adversary extends valid chains of rounds ≤r\le r≤r (rushing). Typical E λ — on every window [a,b][a, b][a,b] with a+λ≤ba + λ \le ba+λ≤b, the adversary's blocks in [a,b][a, b][a,b] are strictly fewer than the uniquely successful rounds strictly inside (a,b)(a, b)(a,b). advBlocks E a b — the adversarial blocks of rounds aaa to bbb as a finite set.

Formalization Note. Imports Mathlib and the block mission's BitcoinBlockV2. Typical is the paper's typical-execution property combined with honest majority, assumed rather than derived from Chernoff bounds; boundary rounds are credited to the adversary.

Definition code
import Mathlib
import Definitions.Def_BitcoinBlockV2

/-!
# The Bitcoin backbone protocol: deterministic core of the synchronous analysis

This file models the *synchronous* ("rounds", `Δ = 1`) execution model of Garay, Kiayias and
Leonardos, *The Bitcoin Backbone Protocol: Analysis and Applications* (EUROCRYPT 2015, full version
ePrint 2014/765), with the proof-of-work abstracted by the paper's random-oracle counts:

* `X r` — successful round (at least one honest block found in round `r`),
* `Y r` — uniquely successful round (exactly one honest block found in round `r`),
* `Z r` — number of adversarial blocks found in round `r`.

A block records who created it and in which round (`Block.honest p r`, `Block.adv r j`); a chain
is a list of blocks, oldest first; extending a chain is appending.  The hash-chain structure of
Bitcoin (a block commits to all of its ancestors) is modelled by `ValidChain`: every block of a
valid chain sits on top of *exactly* the chain its creator was extending when it was found
(`base p r` for honest party `p` in round `r`, `advParent r j` for the `j`-th adversarial block of
round `r`).  Thus a block determines its ancestry, exactly as a hash does under collision
resistance, which is what the paper's "typical execution" assumes (no insertions/copies).

An `Execution` is the trace of one run: the number of honest parties, who mined when, the
adversary's block counts, the chain each honest party adopted at the start of each round (after
`maxvalid` over its own chain and the chains delivered to it, honest or adversarial), and the parent
chain of every adversarial block.  `Execution.Legal` lists the rules of the synchronous model
that the proofs rely on (every honest chain of round `r` reaches every honest party by round
`r + 1`; the chains adopted in round `r` consist of blocks found before round `r`; the adversary is
"rushing": its blocks of round `r` may extend anything found up to and including round `r`).

The probabilistic part of the paper is isolated in the hypothesis `Typical`: on every window of
at least `λ + 1` consecutive rounds the uniquely successful rounds strictly inside the window
outnumber all adversarial blocks of the window.  The paper derives this (with constants) from
Chernoff bounds and the honest-majority assumption; here it is simply assumed, and the theorems
state that *every* execution that is typical in this sense has chain growth, common prefix and
chain quality.
-/

namespace BitcoinBackbone

/-- A block of the abstract blockchain: either the block found by honest party `p` in round `r`
(an honest party finds at most one block per round, as the backbone protocol's `pow` stops after
the first success), or the `j`-th of the `Z r` blocks the adversary finds in round `r`. -/
inductive Block
  | honest (p : ℕ) (r : ℕ)
  | adv (r : ℕ) (j : ℕ)
  deriving DecidableEq, Repr

instance : Inhabited Block := ⟨Block.adv 0 0⟩

/-- The round in which a block was found. -/
def Block.round : Block → ℕ
  | .honest _ r => r
  | .adv r _ => r

/-- Whether a block was found by an honest party. -/
def Block.isHonest : Block → Bool
  | .honest _ _ => true
  | .adv _ _ => false

/-- A chain: the list of its blocks after the genesis, oldest first.  Extending a chain by a block
is `C ++ [B]`; the length of a chain is its (fixed-difficulty) work. -/
abbrev Chain := List Block

/-- The work of a chain in the fixed-difficulty model of the paper: its number of blocks. -/
def Chain.work (C : Chain) : ℕ := C.length

/-- The blocks of `C` found in round `t` or earlier.  For a valid chain (whose rounds are
nondecreasing, `round_mono` in the solutions) this is exactly the prefix of `C` older than `t`. -/
def Chain.upTo (C : Chain) (t : ℕ) : Chain := C.takeWhile (fun B => decide (B.round ≤ t))

/-- The trace of one execution of the backbone protocol in the synchronous model.

* `n`: the honest parties are `0, …, n - 1`.
* `mined p r`: honest party `p` found a block in round `r` (rounds are `1, 2, …`; round `0` is the
  initial state in which every party holds the empty chain, i.e. the genesis block only).
* `Z r`: the number of blocks the adversary found in round `r`.
* `base p r`: the chain honest party `p` adopted in round `r ≥ 1` before mining, i.e. the longest
  valid chain among its own chain and the chains delivered to it (honest broadcasts of round
  `r - 1` and whatever the adversary chose to deliver to `p`).  If `p` finds a block in round `r`
  it extends `base p r` by it and broadcasts the result (`chain p r`).
* `advParent r j`: the chain the adversary extended with its `j`-th block of round `r`. -/
structure Execution where
  n : ℕ
  mined : ℕ → ℕ → Bool
  Z : ℕ → ℕ
  base : ℕ → ℕ → Chain
  advParent : ℕ → ℕ → Chain

/-- The chain held (and broadcast) by honest party `p` at the end of round `r`: the chain it
adopted in round `r`, extended by its own block if it found one. -/
def Execution.chain (E : Execution) (p : ℕ) : ℕ → Chain
  | 0 => []
  | r + 1 =>
    if E.mined p (r + 1) = true then E.base p (r + 1) ++ [Block.honest p (r + 1)]
    else E.base p (r + 1)

/-- The number of honest blocks found in round `r`. -/
def Execution.honestCount (E : Execution) (r : ℕ) : ℕ :=
  ((Finset.range E.n).filter (fun p => E.mined p r = true)).card

/-- The paper's `X_r`: `1` if round `r` is successful (some honest party found a block), else `0`. -/
def Execution.X (E : Execution) (r : ℕ) : ℕ := if 0 < E.honestCount r then 1 else 0

/-- The paper's `Y_r`: `1` if round `r` is uniquely successful (exactly one honest block), else `0`. -/
def Execution.Y (E : Execution) (r : ℕ) : ℕ := if E.honestCount r = 1 then 1 else 0

/-- `B` legitimately extends `parent`: an honest block `honest p r` was found by honest party
`p < n` in round `r` on top of exactly `base p r`; an adversarial block `adv r j` is one of the
`Z r` blocks of round `r` and was found on top of exactly `advParent r j`. -/
def Execution.Extends (E : Execution) (parent : Chain) : Block → Prop
  | .honest p r => p < E.n ∧ E.mined p r = true ∧ parent = E.base p r
  | .adv r j => j < E.Z r ∧ parent = E.advParent r j

/-- A valid chain: every block sits on top of exactly the chain its creator extended.  This is the
abstract form of Bitcoin's hash chain (each block commits to its ancestry). -/
def Execution.ValidChain (E : Execution) (C : Chain) : Prop :=
  ∀ i (h : i < C.length), E.Extends (C.take i) C[i]

/-- The rules of the synchronous backbone model obeyed by a trace.

* `mined_zero`: nothing is mined in the initial round `0`.
* `base_valid`, `base_rounds`: the chain an honest party adopts in round `r` is valid and consists
  of blocks found in rounds `< r` (messages are delivered at the start of the next round).
* `base_length`: every honest party's chain of round `r` is received by every honest party by
  round `r + 1`, and honest parties adopt a longest chain (`maxvalid`); so what `p` adopts in round
  `r + 1` is at least as long as every honest chain of round `r` (its own included).
* `advParent_valid`, `advParent_rounds`: the adversary extends valid chains, made of blocks found
  in rounds `≤ r` when it works in round `r` (rushing adversary: it may build on the honest blocks
  of the current round). -/
structure Execution.Legal (E : Execution) : Prop where
  mined_zero : ∀ p, E.mined p 0 = false
  base_valid : ∀ p r, p < E.n → 1 ≤ r → E.ValidChain (E.base p r)
  base_rounds : ∀ p r, p < E.n → ∀ B ∈ E.base p r, B.round < r
  base_length : ∀ p q r, p < E.n → q < E.n → (E.chain q r).length ≤ (E.base p (r + 1)).length
  advParent_valid : ∀ r j, j < E.Z r → E.ValidChain (E.advParent r j)
  advParent_rounds : ∀ r j, j < E.Z r → ∀ B ∈ E.advParent r j, B.round ≤ r

/-- Typical execution with window parameter `λ` (deterministic form of the paper's Definition of a
typical execution combined with the honest-majority assumption): for every window `[a, b]` of at
least `λ + 1` consecutive rounds, the uniquely successful rounds strictly inside the window
outnumber all adversarial blocks found in the window, boundary rounds included.  (The two boundary
rounds are credited to the adversary because a rushing adversary may build on the honest block of
round `a` during round `a`, and may deliver blocks of round `b` in round `b`; the paper absorbs
these two rounds in the `(1 ± ε)` slack of its Chernoff bounds.) -/
def Execution.Typical (E : Execution) (lam : ℕ) : Prop :=
  ∀ a b : ℕ, a + lam ≤ b → (∑ i ∈ Finset.Icc a b, E.Z i) < ∑ i ∈ Finset.Ioo a b, E.Y i

/-- The adversarial blocks of rounds `a, …, b`, as a finite set of `Block`s (its cardinality is
`∑ i ∈ Icc a b, Z i`). -/
def Execution.advBlocks (E : Execution) (a b : ℕ) : Finset Block :=
  ((Finset.Icc a b).sigma (fun s => Finset.range (E.Z s))).image (fun x => Block.adv x.1 x.2)

end BitcoinBackbone
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; Lemmas 7, 14, 15, Theorem 16, the chain-quality theorem; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: GetBlockProof (chain.cpp) through the block mission's chainWork
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_BitcoinBackbone.lean

Everything below lives in a namespace called BitcoinBackbone; the file imports Mathlib and the block-validation preamble Def_BitcoinBlockV2, but none of the definitions in this file refer to anything from that preamble. One paragraph per definition, in file order.


Block (inductive type). A block is a value of one of exactly two shapes: an honest block honest(p,r)\mathsf{honest}(p, r)honest(p,r) carrying two natural numbers ppp (a party index) and rrr (a round), or an adversarial block adv(r,j)\mathsf{adv}(r, j)adv(r,j) carrying two natural numbers rrr (a round) and jjj (an index). Two blocks are equal exactly when they have the same shape and the same two numbers; in particular honest(p,r)\mathsf{honest}(p,r)honest(p,r) and adv(r′,j)\mathsf{adv}(r',j)adv(r′,j) are never equal, and honest(p,r)≠honest(p′,r)\mathsf{honest}(p,r) \ne \mathsf{honest}(p',r)honest(p,r)=honest(p′,r) whenever p≠p′p \ne p'p=p′. Nothing restricts ppp, rrr or jjj at the level of the type: honest(109,0)\mathsf{honest}(10^9, 0)honest(109,0) and adv(0,109)\mathsf{adv}(0, 10^9)adv(0,109) are blocks. Equality of blocks is decidable. (An accompanying instance declares adv(0,0)\mathsf{adv}(0,0)adv(0,0) as the default block value; it is used only as a junk value by out-of-range list indexing operations that need one.)

Block.round. The round of a block is a natural number read off from the block: round⁡(honest(p,r))=r\operatorname{round}(\mathsf{honest}(p,r)) = rround(honest(p,r))=r and round⁡(adv(r,j))=r\operatorname{round}(\mathsf{adv}(r,j)) = rround(adv(r,j))=r. This is purely syntactic; a block "found in round 000" is allowed by this definition.

Block.isHonest. A Boolean flag: isHonest⁡(honest(p,r))=true\operatorname{isHonest}(\mathsf{honest}(p,r)) = \mathtt{true}isHonest(honest(p,r))=true and isHonest⁡(adv(r,j))=false\operatorname{isHonest}(\mathsf{adv}(r,j)) = \mathtt{false}isHonest(adv(r,j))=false. So "BBB is adversarial" (as the theorem files write it, isHonest⁡(B)=false\operatorname{isHonest}(B) = \mathtt{false}isHonest(B)=false) means exactly that BBB has the shape adv(⋅,⋅)\mathsf{adv}(\cdot,\cdot)adv(⋅,⋅).

Chain (abbreviation). A chain CCC is simply a finite list of blocks, C=[B0,B1,…,Bℓ−1]C = [B_0, B_1, \dots, B_{\ell-1}]C=[B0​,B1​,…,Bℓ−1​], with ℓ=∣C∣\ell = |C|ℓ=∣C∣ its length; there is no genesis element in the list, no well-formedness condition, and repeated blocks are allowed. Throughout, positions are 000-based: C[i]C[i]C[i] is the iii-th block counting from 000, defined only for i<∣C∣i < |C|i<∣C∣. The empty list [ ][\,][] is a chain. The documentation describes position 000 as the oldest block, but this is a convention of the author, not something enforced by the type.

Chain.work. work⁡(C)=∣C∣\operatorname{work}(C) = |C|work(C)=∣C∣, the length of the list CCC as a natural number. (This definition is not used by any of the eight theorem statements.)

Chain.upTo. For a chain CCC and a natural number ttt, upTo⁡(C,t)\operatorname{upTo}(C, t)upTo(C,t) is the longest initial segment of CCC all of whose blocks have round ≤t\le t≤t: scanning CCC from position 000, blocks are kept while round⁡(B)≤t\operatorname{round}(B) \le tround(B)≤t, and the scan stops at the first block with round⁡(B)>t\operatorname{round}(B) > tround(B)>t, discarding it and everything after it—even blocks further on whose round is ≤t\le t≤t. If every block of CCC has round ≤t\le t≤t, then upTo⁡(C,t)=C\operatorname{upTo}(C,t) = CupTo(C,t)=C; if C[0]C[0]C[0] has round >t> t>t, or CCC is empty, then upTo⁡(C,t)=[ ]\operatorname{upTo}(C,t) = [\,]upTo(C,t)=[]. In general upTo⁡(C,t)\operatorname{upTo}(C,t)upTo(C,t) is a prefix of CCC but it is not in general "the set of blocks of CCC with round ≤t\le t≤t" unless rounds are nondecreasing along CCC (which nothing in the type guarantees).

Execution (structure). An execution EEE is a 5-tuple of completely unconstrained data:

  • n∈Nn \in \mathbb{N}n∈N (the number of honest parties; parties are the indices 0,…,n−10,\dots,n-10,…,n−1; n=0n=0n=0 is allowed, in which case there are no parties);
  • mined:N×N→{true,false}\mathrm{mined} : \mathbb{N}\times\mathbb{N} \to \{\mathtt{true},\mathtt{false}\}mined:N×N→{true,false}, a Boolean mined(p,r)\mathrm{mined}(p,r)mined(p,r) for every party index ppp and round rrr (also defined for p≥np \ge np≥n, where its values are simply ignored by the counting definitions below);
  • Z:N→NZ : \mathbb{N} \to \mathbb{N}Z:N→N, a natural number ZrZ_rZr​ for every round rrr (including r=0r=0r=0; nothing forces Z0=0Z_0 = 0Z0​=0);
  • base:N×N→Chain\mathrm{base} : \mathbb{N}\times\mathbb{N}\to \text{Chain}base:N×N→Chain, a chain base(p,r)\mathrm{base}(p,r)base(p,r) for every ppp and rrr (also for r=0r=0r=0 and for p≥np\ge np≥n);
  • advParent:N×N→Chain\mathrm{advParent} : \mathbb{N}\times\mathbb{N}\to \text{Chain}advParent:N×N→Chain, a chain advParent(r,j)\mathrm{advParent}(r,j)advParent(r,j) for every rrr and jjj (also for j≥Zrj \ge Z_rj≥Zr​).

The structure itself imposes no relation between these fields; all constraints come from the separate predicate Legal below.

Execution.chain. For an execution EEE, a natural number ppp (not required to satisfy p<np<np<n) and a round rrr, the chain Cp(r)\mathcal{C}_p(r)Cp​(r) ("the chain of ppp at the end of round rrr") is defined by recursion on rrr:

Cp(0)=[ ],Cp(r+1)={base(p,r+1)+ ⁣ ⁣+[honest(p,r+1)]if mined(p,r+1)=true,base(p,r+1)otherwise.\mathcal{C}_p(0) = [\,],\qquad \mathcal{C}_p(r+1) = \begin{cases} \mathrm{base}(p, r+1) \mathbin{+\!\!+} [\mathsf{honest}(p, r+1)] & \text{if } \mathrm{mined}(p, r+1) = \mathtt{true},\\ \mathrm{base}(p, r+1) & \text{otherwise.} \end{cases}Cp​(0)=[],Cp​(r+1)={base(p,r+1)++[honest(p,r+1)]base(p,r+1)​if mined(p,r+1)=true,otherwise.​

Here + ⁣ ⁣+\mathbin{+\!\!+}++ is list concatenation, so the honest block is appended at the end (highest position). Note that Cp(0)\mathcal{C}_p(0)Cp​(0) is the empty list regardless of base(p,0)\mathrm{base}(p,0)base(p,0), and that for r≥1r\ge1r≥1 the definition does not depend on Cp(r−1)\mathcal{C}_p(r-1)Cp​(r−1) at all—only on base(p,r)\mathrm{base}(p,r)base(p,r) and mined(p,r)\mathrm{mined}(p,r)mined(p,r). Consequently ∣Cp(r)∣=∣base(p,r)∣+1|\mathcal{C}_p(r)| = |\mathrm{base}(p,r)| + 1∣Cp​(r)∣=∣base(p,r)∣+1 if mined(p,r)\mathrm{mined}(p,r)mined(p,r) holds and ∣base(p,r)∣|\mathrm{base}(p,r)|∣base(p,r)∣ otherwise, for r≥1r \ge 1r≥1.

Execution.honestCount. For a round rrr, hr=#{ p∈{0,…,n−1}:mined(p,r)=true }h_r = \#\{\,p \in \{0,\dots,n-1\} : \mathrm{mined}(p,r) = \mathtt{true}\,\}hr​=#{p∈{0,…,n−1}:mined(p,r)=true}, the number of party indices below nnn for which the mined-flag is set in round rrr. Values of mined(p,r)\mathrm{mined}(p,r)mined(p,r) with p≥np \ge np≥n do not count. If n=0n = 0n=0 then hr=0h_r = 0hr​=0 for every rrr. Note that this counts parties, which under this model is the same as counting honest blocks of round rrr because each party has at most one flag per round.

Execution.X. Xr=1X_r = 1Xr​=1 if hr>0h_r > 0hr​>0 and Xr=0X_r = 0Xr​=0 otherwise, a natural number (not a Boolean). So Xr=1X_r=1Xr​=1 means: at least one party index p<np<np<n has mined(p,r)=true\mathrm{mined}(p,r)=\mathtt{true}mined(p,r)=true.

Execution.Y. Yr=1Y_r = 1Yr​=1 if hr=1h_r = 1hr​=1 and Yr=0Y_r = 0Yr​=0 otherwise, a natural number. So Yr=1Y_r = 1Yr​=1 means: exactly one party index p<np<np<n has mined(p,r)=true\mathrm{mined}(p,r)=\mathtt{true}mined(p,r)=true. In particular Yr=0Y_r = 0Yr​=0 when two or more parties mined in round rrr and when none did; if n=0n=0n=0 then Yr=0Y_r=0Yr​=0 for all rrr.

Execution.Extends. For an execution EEE, a chain PPP (the "parent") and a block BBB, the proposition Extends⁡E(P,B)\operatorname{Extends}_E(P, B)ExtendsE​(P,B) is defined by cases on the shape of BBB:

  • if B=honest(p,r)B = \mathsf{honest}(p,r)B=honest(p,r):   p<n  ∧  mined(p,r)=true  ∧  P=base(p,r)\;p < n \;\wedge\; \mathrm{mined}(p,r) = \mathtt{true} \;\wedge\; P = \mathrm{base}(p,r)p<n∧mined(p,r)=true∧P=base(p,r) (equality of lists);
  • if B=adv(r,j)B = \mathsf{adv}(r,j)B=adv(r,j):   j<Zr  ∧  P=advParent(r,j)\;j < Z_r \;\wedge\; P = \mathrm{advParent}(r,j)j<Zr​∧P=advParent(r,j).

So an honest block "extends" exactly one chain, namely base(p,r)\mathrm{base}(p,r)base(p,r), and only if the party is in range and the mined-flag is set; an adversarial block "extends" exactly advParent(r,j)\mathrm{advParent}(r,j)advParent(r,j), and only if its index jjj is below the adversarial count ZrZ_rZr​ of its round. Nothing here relates the round of BBB to the rounds of blocks in PPP.

Execution.ValidChain. A chain C=[B0,…,Bℓ−1]C = [B_0,\dots,B_{\ell-1}]C=[B0​,…,Bℓ−1​] is valid for EEE, written Valid⁡E(C)\operatorname{Valid}_E(C)ValidE​(C), when for every position iii with 0≤i<ℓ0 \le i < \ell0≤i<ℓ,

Extends⁡E([B0,…,Bi−1],  Bi),\operatorname{Extends}_E\bigl([B_0,\dots,B_{i-1}],\; B_i\bigr),ExtendsE​([B0​,…,Bi−1​],Bi​),

i.e. the block at position iii extends (in the sense just defined) exactly the list of the iii blocks before it (the first iii elements of CCC). Unfolded: for each i<ℓi<\elli<ℓ, either Bi=honest(p,r)B_i = \mathsf{honest}(p,r)Bi​=honest(p,r) with p<np<np<n, mined(p,r)=true\mathrm{mined}(p,r)=\mathtt{true}mined(p,r)=true and base(p,r)=[B0,…,Bi−1]\mathrm{base}(p,r) = [B_0,\dots,B_{i-1}]base(p,r)=[B0​,…,Bi−1​], or Bi=adv(r,j)B_i = \mathsf{adv}(r,j)Bi​=adv(r,j) with j<Zrj<Z_rj<Zr​ and advParent(r,j)=[B0,…,Bi−1]\mathrm{advParent}(r,j) = [B_0,\dots,B_{i-1}]advParent(r,j)=[B0​,…,Bi−1​]. The empty chain is vacuously valid. For i=0i=0i=0 the condition says B0B_0B0​ extends the empty list.

Execution.Legal (structure of propositions). An execution EEE is legal when all six of the following hold:

  1. mined_zero: for every p∈Np \in \mathbb{N}p∈N (all ppp, not only p<np<np<n), mined(p,0)=false\mathrm{mined}(p,0) = \mathtt{false}mined(p,0)=false. Hence h0=X0=Y0=0h_0 = X_0 = Y_0 = 0h0​=X0​=Y0​=0 and no honest block of the form honest(p,0)\mathsf{honest}(p,0)honest(p,0) can appear in a valid chain. (Nothing analogous is required of Z0Z_0Z0​ or of advParent(0,j)\mathrm{advParent}(0,j)advParent(0,j).)
  2. base_valid: for every ppp and rrr with p<np<np<n and 1≤r1 \le r1≤r, the chain base(p,r)\mathrm{base}(p,r)base(p,r) is valid for EEE. (No requirement on base(p,0)\mathrm{base}(p,0)base(p,0), nor on base(p,r)\mathrm{base}(p,r)base(p,r) for p≥np \ge np≥n.)
  3. base_rounds: for every p<np<np<n and every rrr (including r=0r=0r=0), every block BBB occurring in the list base(p,r)\mathrm{base}(p,r)base(p,r) satisfies round⁡(B)<r\operatorname{round}(B) < rround(B)<r. For r=0r=0r=0 this forces base(p,0)=[ ]\mathrm{base}(p,0)=[\,]base(p,0)=[] for p<np<np<n.
  4. base_length: for all p,q<np,q<np,q<n and every r∈Nr\in\mathbb{N}r∈N (including r=0r=0r=0), ∣Cq(r)∣≤∣base(p,r+1)∣|\mathcal{C}_q(r)| \le |\mathrm{base}(p, r+1)|∣Cq​(r)∣≤∣base(p,r+1)∣: the chain that party ppp adopts in round r+1r+1r+1 is at least as long as the chain any party qqq (including q=pq=pq=p) held at the end of round rrr. Only lengths are compared; no prefix or content relation is required.
  5. advParent_valid: for every rrr and every j<Zrj < Z_rj<Zr​, the chain advParent(r,j)\mathrm{advParent}(r,j)advParent(r,j) is valid for EEE.
  6. advParent_rounds: for every rrr and every j<Zrj<Z_rj<Zr​, every block BBB in advParent(r,j)\mathrm{advParent}(r,j)advParent(r,j) satisfies round⁡(B)≤r\operatorname{round}(B) \le rround(B)≤r (non-strict, in contrast with item 3).

Nothing in Legal says that honest parties' chains are prefix-related, that base(p,r)\mathrm{base}(p,r)base(p,r) is one of the previously broadcast chains, or anything about mined(p,r)\mathrm{mined}(p,r)mined(p,r) for r≥1r\ge1r≥1.

Execution.Typical. For an execution EEE and a natural number λ\lambdaλ (written lam), Typical⁡E(λ)\operatorname{Typical}_E(\lambda)TypicalE​(λ) is the statement: for all natural numbers a,ba, ba,b with a+λ≤ba + \lambda \le ba+λ≤b,

∑i=abZi  <  ∑i=a+1b−1Yi,\sum_{i=a}^{b} Z_i \;<\; \sum_{i=a+1}^{b-1} Y_i ,i=a∑b​Zi​<i=a+1∑b−1​Yi​,

where the left sum ranges over the closed interval {a,a+1,…,b}\{a, a+1, \dots, b\}{a,a+1,…,b} and the right sum over the open interval {a+1,…,b−1}\{a+1,\dots,b-1\}{a+1,…,b−1} (empty when b≤a+1b \le a+1b≤a+1); both are sums of natural numbers and the inequality is strict. Degenerate cases to note: when λ=0\lambda = 0λ=0, taking b=ab=ab=a makes the right-hand sum empty (value 000), so the condition demands Za<0Z_a < 0Za​<0, which is impossible—hence Typical⁡E(0)\operatorname{Typical}_E(0)TypicalE​(0) is false for every EEE; likewise when λ=1\lambda = 1λ=1, taking b=a+1b = a+1b=a+1 gives an empty right-hand sum and the impossible demand Za+Za+1<0Z_a + Z_{a+1} < 0Za​+Za+1​<0, so Typical⁡E(1)\operatorname{Typical}_E(1)TypicalE​(1) is false for every EEE. If n=0n = 0n=0 then every Yi=0Y_i = 0Yi​=0 and the condition is again impossible, so Typical⁡E(λ)\operatorname{Typical}_E(\lambda)TypicalE​(λ) forces n≥1n \ge 1n≥1. For λ≥2\lambda\ge2λ≥2 the condition requires, among other things, that every window of λ+1\lambda+1λ+1 consecutive rounds contain at least one round strictly inside it with Yi=1Y_i = 1Yi​=1 (in particular infinitely many uniquely successful rounds), and that the adversarial counts over any window of length ≥λ+1\ge \lambda + 1≥λ+1 be strictly fewer than the uniquely successful rounds strictly inside it. The window includes a=0a = 0a=0 and so also the round-000 value Z0Z_0Z0​.

Execution.advBlocks. For rounds a≤ba \le ba≤b, advBlocks⁡E(a,b)\operatorname{advBlocks}_E(a,b)advBlocksE​(a,b) is the finite set of blocks { adv(s,j):a≤s≤b,  0≤j<Zs }\{\,\mathsf{adv}(s, j) : a \le s \le b,\; 0 \le j < Z_s\,\}{adv(s,j):a≤s≤b,0≤j<Zs​}, obtained as the image of the pairs (s,j)(s,j)(s,j) with s∈{a,…,b}s\in\{a,\dots,b\}s∈{a,…,b}, j<Zsj<Z_sj<Zs​ under (s,j)↦adv(s,j)(s,j)\mapsto \mathsf{adv}(s,j)(s,j)↦adv(s,j). If a>ba > ba>b the set is empty. Since the map is injective, its cardinality is ∑i=abZi\sum_{i=a}^{b} Z_i∑i=ab​Zi​. (This definition is not used by any of the eight theorem statements.)

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