Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A private fork loses (the core of Lemma 15)

Proved
BitcoinBackbone.common_prefix_private

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

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

For a legal, typical execution and honest party ppp at round rrr: any valid chain DDD of rounds ≤r\le r≤r that forks from an honest block of round r0r_0r0​ (or from genesis) and is adversarial above the fork, with r0+λ≤rr_0 + λ \le rr0​+λ≤r, is strictly shorter than chain p r.

Preamble
import Definitions.Def_BitcoinBackbone
Formal statement
theorem BitcoinBackbone.common_prefix_private (E : BitcoinBackbone.Execution) (hE : E.Legal)
    (lam : ℕ) (hT : E.Typical lam) (p : ℕ) (hp : p < E.n) (r : ℕ)
    (D : BitcoinBackbone.Chain) (hD : E.ValidChain D) (hDr : ∀ B ∈ D, B.round ≤ r)
    (f r₀ : ℕ) (hfD : f ≤ D.length)
    (hfork : (f = 0 ∧ r₀ = 0) ∨
      ∃ q, ∃ hf : f - 1 < D.length, 0 < f ∧ D[f - 1] = BitcoinBackbone.Block.honest q r₀)
    (hadv : ∀ k (hk : k < D.length), f ≤ k → D[k].isHonest = false)
    (hwin : r₀ + lam ≤ r) : D.length < (E.chain p r).length := 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; 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: BitcoinBackbone.common_prefix_private

Statement. Let EEE be an execution of the backbone model, assumed legal (no mined-flag in round 000; for p<np<np<n, r≥1r\ge1r≥1, base(p,r)\mathrm{base}(p,r)base(p,r) is a valid chain; for p<np<np<n every block of base(p,r)\mathrm{base}(p,r)base(p,r) has round <r<r<r; for p,q<np,q<np,q<n and all rrr, ∣Cq(r)∣≤∣base(p,r+1)∣|\mathcal{C}_q(r)|\le|\mathrm{base}(p,r+1)|∣Cq​(r)∣≤∣base(p,r+1)∣; for j<Zrj<Z_rj<Zr​, advParent(r,j)\mathrm{advParent}(r,j)advParent(r,j) is valid with all blocks of round ≤r\le r≤r). Let λ∈N\lambda\in\mathbb{N}λ∈N and assume EEE is λ\lambdaλ-typical:

∀a,b∈N,a+λ≤b  ⟹  ∑i=abZi<∑i=a+1b−1Yi,\forall a,b\in\mathbb{N},\quad a+\lambda\le b \;\Longrightarrow\; \sum_{i=a}^{b} Z_i < \sum_{i=a+1}^{b-1} Y_i ,∀a,b∈N,a+λ≤b⟹i=a∑b​Zi​<i=a+1∑b−1​Yi​,

with Yi=1Y_i=1Yi​=1 iff exactly one party index p′<np'<np′<n has mined(p′,i)=true\mathrm{mined}(p',i)=\mathtt{true}mined(p′,i)=true, else 000. Let p<np<np<n be a party index and r∈Nr\in\mathbb{N}r∈N a round. Let D=[D0,…,Dℓ−1]D = [D_0,\dots,D_{\ell-1}]D=[D0​,…,Dℓ−1​] be an arbitrary chain (list of blocks, ℓ=∣D∣\ell=|D|ℓ=∣D∣) satisfying:

  1. DDD is valid for EEE: for every position k<ℓk<\ellk<ℓ, the block DkD_kDk​ extends exactly the list [D0,…,Dk−1][D_0,\dots,D_{k-1}][D0​,…,Dk−1​], meaning: if Dk=honest(p′,r′)D_k=\mathsf{honest}(p',r')Dk​=honest(p′,r′) then p′<np'<np′<n, mined(p′,r′)=true\mathrm{mined}(p',r')=\mathtt{true}mined(p′,r′)=true and base(p′,r′)=[D0,…,Dk−1]\mathrm{base}(p',r') = [D_0,\dots,D_{k-1}]base(p′,r′)=[D0​,…,Dk−1​]; if Dk=adv(r′,j)D_k=\mathsf{adv}(r',j)Dk​=adv(r′,j) then j<Zr′j<Z_{r'}j<Zr′​ and advParent(r′,j)=[D0,…,Dk−1]\mathrm{advParent}(r',j)=[D_0,\dots,D_{k-1}]advParent(r′,j)=[D0​,…,Dk−1​].
  2. All rounds of DDD are ≤r\le r≤r: every block BBB in DDD has round⁡(B)≤r\operatorname{round}(B)\le rround(B)≤r.

Let f,r0∈Nf, r_0\in\mathbb{N}f,r0​∈N with f≤ℓf\le\ellf≤ℓ, and assume:

  1. Fork point (a disjunction):
    • either f=0f=0f=0 and r0=0r_0=0r0​=0;
    • or there exist a natural number qqq and a proof that f−1<ℓf-1<\ellf−1<ℓ such that 0<f0<f0<f and Df−1=honest(q,r0)D_{f-1} = \mathsf{honest}(q, r_0)Df−1​=honest(q,r0​) (the block at 000-based position f−1f-1f−1 is the honest block of party qqq in round r0r_0r0​).
  2. Adversarial tail: for every position k<ℓk<\ellk<ℓ with f≤kf\le kf≤k, the block DkD_kDk​ is adversarial, i.e. isHonest⁡(Dk)=false\operatorname{isHonest}(D_k)=\mathtt{false}isHonest(Dk​)=false, equivalently DkD_kDk​ has the shape adv(⋅,⋅)\mathsf{adv}(\cdot,\cdot)adv(⋅,⋅).
  3. Window: r0+λ≤rr_0+\lambda\le rr0​+λ≤r.

Then

∣D∣  <  ∣Cp(r)∣,|D| \;<\; |\mathcal{C}_p(r)| ,∣D∣<∣Cp​(r)∣,

where Cp(r)\mathcal{C}_p(r)Cp​(r) is party ppp's chain at the end of round rrr ([ ][\,][] if r=0r=0r=0; for r≥1r\ge1r≥1, base(p,r)\mathrm{base}(p,r)base(p,r) with honest(p,r)\mathsf{honest}(p,r)honest(p,r) appended iff mined(p,r)=true\mathrm{mined}(p,r)=\mathtt{true}mined(p,r)=true) and ∣⋅∣|\cdot|∣⋅∣ is list length. The inequality is strict.

Unpacking the fork disjunction. The two disjuncts are mutually exclusive via the value of fff: if f=0f=0f=0 the second disjunct fails (it requires 0<f0<f0<f), so the first forces r0=0r_0=0r0​=0; if f>0f>0f>0 the first disjunct fails, so the second must hold, and then f−1<ℓf-1<\ellf−1<ℓ is automatic from 0<f≤ℓ0<f\le\ell0<f≤ℓ. So the hypothesis says: either f=0f=0f=0 and r0=0r_0=0r0​=0 (in which case, by item 4, every block of DDD is adversarial and item 5 reads λ≤r\lambda\le rλ≤r), or f≥1f\ge1f≥1, position f−1f-1f−1 of DDD holds honest(q,r0)\mathsf{honest}(q,r_0)honest(q,r0​) for some qqq (unconstrained in the hypothesis itself, but validity of DDD at position f−1f-1f−1 entails q<nq<nq<n, mined(q,r0)=true\mathrm{mined}(q,r_0)=\mathtt{true}mined(q,r0​)=true and base(q,r0)=[D0,…,Df−2]\mathrm{base}(q,r_0)=[D_0,\dots,D_{f-2}]base(q,r0​)=[D0​,…,Df−2​]), and all blocks at positions f,…,ℓ−1f,\dots,\ell-1f,…,ℓ−1 are adversarial. The blocks at positions 0,…,f−20,\dots,f-20,…,f−2 are not constrained in honesty by hypotheses 3–4 (only by validity and the round bound).

Edge cases. DDD need not be the chain of any party; it is any list satisfying 1–2. f=ℓf=\ellf=ℓ is allowed (empty adversarial tail; then DDD's last block is honest(q,r0)\mathsf{honest}(q,r_0)honest(q,r0​) if f>0f>0f>0). If D=[ ]D=[\,]D=[] then f=0f=0f=0, hence r0=0r_0=0r0​=0, item 4 is vacuous, item 5 is λ≤r\lambda\le rλ≤r, and the conclusion asserts 0<∣Cp(r)∣0<|\mathcal{C}_p(r)|0<∣Cp​(r)∣, i.e. that ppp's chain at round rrr is non-empty. 000- and 111-typicality are unsatisfiable (for λ=0\lambda=0λ=0 take a=ba=ba=b; for λ=1\lambda=1λ=1 take b=a+1b=a+1b=a+1), so the theorem is vacuous for λ≤1\lambda\le1λ≤1; typicality also forces n≥1n\ge1n≥1. Legality's round-000 rule means an honest block with r0=0r_0=0r0​=0 cannot occur in the valid chain DDD, so in the second disjunct r0≥1r_0\ge1r0​≥1 is forced; in the first disjunct r0=0r_0=0r0​=0 by fiat.

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