The synchronous backbone model: executions, valid chains, typical executions
DefinitionBitcoinBackboneThe deterministic core of Garay, Kiayias and Leonardos's synchronous analysis, over Mathlib.
Block — honest p r (found by honest party in round ) or adv r j (the -th adversarial block of round ); 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 .
Execution — a trace: the number of honest parties, mined p r (whether found a block in round ), Z r (the adversary's block count in round ), base p r (the chain adopted at the start of round after maxvalid), advParent r j (the chain the adversary's -th block of round extends). Derived: chain p r (the end-of-round chain: base, plus 's own block if mined; the empty chain at round 0), honestCount r, X r (1 iff some honest block in round ), Y r (1 iff exactly one honest block in round ).
Extends E parent B and ValidChain E C — every block of 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 is at most as long as what any honest party adopts in round (maxvalid over delivered chains); the adversary extends valid chains of rounds (rushing). Typical E λ — on every window with , the adversary's blocks in are strictly fewer than the uniquely successful rounds strictly inside . advBlocks E a b — the adversarial blocks of rounds to 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.
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
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 carrying two natural numbers (a party index) and (a round), or an adversarial block carrying two natural numbers (a round) and (an index). Two blocks are equal exactly when they have the same shape and the same two numbers; in particular and are never equal, and whenever . Nothing restricts , or at the level of the type: and are blocks. Equality of blocks is decidable. (An accompanying instance declares 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: and . This is purely syntactic; a block "found in round " is allowed by this definition.
Block.isHonest. A Boolean flag: and . So " is adversarial" (as the theorem files write it, ) means exactly that has the shape .
Chain (abbreviation). A chain is simply a finite list of blocks, , with its length; there is no genesis element in the list, no well-formedness condition, and repeated blocks are allowed. Throughout, positions are -based: is the -th block counting from , defined only for . The empty list is a chain. The documentation describes position as the oldest block, but this is a convention of the author, not something enforced by the type.
Chain.work. , the length of the list as a natural number. (This definition is not used by any of the eight theorem statements.)
Chain.upTo. For a chain and a natural number , is the longest initial segment of all of whose blocks have round : scanning from position , blocks are kept while , and the scan stops at the first block with , discarding it and everything after it—even blocks further on whose round is . If every block of has round , then ; if has round , or is empty, then . In general is a prefix of but it is not in general "the set of blocks of with round " unless rounds are nondecreasing along (which nothing in the type guarantees).
Execution (structure). An execution is a 5-tuple of completely unconstrained data:
- (the number of honest parties; parties are the indices ; is allowed, in which case there are no parties);
- , a Boolean for every party index and round (also defined for , where its values are simply ignored by the counting definitions below);
- , a natural number for every round (including ; nothing forces );
- , a chain for every and (also for and for );
- , a chain for every and (also for ).
The structure itself imposes no relation between these fields; all constraints come from the separate predicate Legal below.
Execution.chain. For an execution , a natural number (not required to satisfy ) and a round , the chain ("the chain of at the end of round ") is defined by recursion on :
Here is list concatenation, so the honest block is appended at the end (highest position). Note that is the empty list regardless of , and that for the definition does not depend on at all—only on and . Consequently if holds and otherwise, for .
Execution.honestCount. For a round , , the number of party indices below for which the mined-flag is set in round . Values of with do not count. If then for every . Note that this counts parties, which under this model is the same as counting honest blocks of round because each party has at most one flag per round.
Execution.X. if and otherwise, a natural number (not a Boolean). So means: at least one party index has .
Execution.Y. if and otherwise, a natural number. So means: exactly one party index has . In particular when two or more parties mined in round and when none did; if then for all .
Execution.Extends. For an execution , a chain (the "parent") and a block , the proposition is defined by cases on the shape of :
- if : (equality of lists);
- if : .
So an honest block "extends" exactly one chain, namely , and only if the party is in range and the mined-flag is set; an adversarial block "extends" exactly , and only if its index is below the adversarial count of its round. Nothing here relates the round of to the rounds of blocks in .
Execution.ValidChain. A chain is valid for , written , when for every position with ,
i.e. the block at position extends (in the sense just defined) exactly the list of the blocks before it (the first elements of ). Unfolded: for each , either with , and , or with and . The empty chain is vacuously valid. For the condition says extends the empty list.
Execution.Legal (structure of propositions). An execution is legal when all six of the following hold:
- mined_zero: for every (all , not only ), . Hence and no honest block of the form can appear in a valid chain. (Nothing analogous is required of or of .)
- base_valid: for every and with and , the chain is valid for . (No requirement on , nor on for .)
- base_rounds: for every and every (including ), every block occurring in the list satisfies . For this forces for .
- base_length: for all and every (including ), : the chain that party adopts in round is at least as long as the chain any party (including ) held at the end of round . Only lengths are compared; no prefix or content relation is required.
- advParent_valid: for every and every , the chain is valid for .
- advParent_rounds: for every and every , every block in satisfies (non-strict, in contrast with item 3).
Nothing in Legal says that honest parties' chains are prefix-related, that is one of the previously broadcast chains, or anything about for .
Execution.Typical. For an execution and a natural number (written lam), is the statement: for all natural numbers with ,
where the left sum ranges over the closed interval and the right sum over the open interval (empty when ); both are sums of natural numbers and the inequality is strict. Degenerate cases to note: when , taking makes the right-hand sum empty (value ), so the condition demands , which is impossible—hence is false for every ; likewise when , taking gives an empty right-hand sum and the impossible demand , so is false for every . If then every and the condition is again impossible, so forces . For the condition requires, among other things, that every window of consecutive rounds contain at least one round strictly inside it with (in particular infinitely many uniquely successful rounds), and that the adversarial counts over any window of length be strictly fewer than the uniquely successful rounds strictly inside it. The window includes and so also the round- value .
Execution.advBlocks. For rounds , is the finite set of blocks , obtained as the image of the pairs with , under . If the set is empty. Since the map is injective, its cardinality is . (This definition is not used by any of the eight theorem statements.)
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.