Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Connecting a chain to a consistent state gives a consistent state

Proved
BitcoinReorg.consistent_connectChain

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

bitcoinbitcoin-mainnetchainstateconsensusformal-verificationreorgreorganizationundoutxo

If S is StateEquiv to a reachable state and connectChain S cs succeeds, the result is StateEquiv to a reachable state.

Preamble
import Definitions.Def_BitcoinReorg
import Definitions.Def_BitcoinSer
open BitcoinReorg BitcoinBlockV2
Formal statement
theorem BitcoinReorg.consistent_connectChain (S : ChainState) (hS : BitcoinReorg.Consistent S)
    (cs : List (BitcoinSer.Block × Int)) (U : ChainState) (undos : List BlockUndo)
    (h : BitcoinReorg.connectChain S cs = some (U, undos)) : BitcoinReorg.Consistent U := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: ConnectBlock, DisconnectBlock, UpdateCoins, ApplyTxInUndo, Chainstate::ConnectTip, Chainstate::DisconnectTip, Chainstate::ActivateBestChainStep, src/validation.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/validation.cpp; CCoinsViewCache (coins.cpp)
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: BitcoinReorg.consistent_connectChain

Notions used

Ledgers and coin lookup. A ledger uuu is a finite list of pairs (p,c)(p, c)(p,c), where ppp is an outpoint (a byte string p.hashp.\mathrm{hash}p.hash and a natural number p.np.np.n) and ccc is a coin (an output c.outc.\mathrm{out}c.out consisting of an integer value c.out.nValuec.\mathrm{out}.\mathrm{nValue}c.out.nValue and a byte-string script c.out.scriptPubKeyc.\mathrm{out}.\mathrm{scriptPubKey}c.out.scriptPubKey; a natural-number creation height c.heightc.\mathrm{height}c.height; and a Boolean coinbase flag c.isCoinbasec.\mathrm{isCoinbase}c.isCoinbase). The lookup getCoin(u,p)\mathrm{getCoin}(u, p)getCoin(u,p) scans uuu from the front and returns the coin of the first pair whose outpoint equals ppp (as a value "some ccc"), or "none" if no pair has outpoint ppp; any later pair with the same outpoint is shadowed and never consulted. Two ledgers are equivalent, written u∼vu \sim vu∼v, when

∀p,getCoin(u,p)=getCoin(v,p),\forall p,\quad \mathrm{getCoin}(u, p) = \mathrm{getCoin}(v, p),∀p,getCoin(u,p)=getCoin(v,p),

the quantifier ranging over every outpoint (every byte string and every natural number). Equivalence says nothing about the order of the lists, about duplicate or shadowed entries, or about list length.

Chain states. A chain state SSS is a pair of a list of headers S.headersS.\mathrm{headers}S.headers and a ledger S.utxoS.\mathrm{utxo}S.utxo. A header has an integer version, byte strings prevBlock\mathrm{prevBlock}prevBlock and merkleRoot\mathrm{merkleRoot}merkleRoot, and natural numbers time\mathrm{time}time, bits\mathrm{bits}bits, nonce\mathrm{nonce}nonce; headerHash(h)\mathrm{headerHash}(h)headerHash(h) is the double SHA-256 of its 80-byte serialization. A block bbb is a header b.headerb.\mathrm{header}b.header and a list of transactions b.vtxb.\mathrm{vtx}b.vtx. Derived quantities of a state SSS with n=∣S.headers∣n = |S.\mathrm{headers}|n=∣S.headers∣:

  • tipHeight(S)=n−1\mathrm{tipHeight}(S) = n - 1tipHeight(S)=n−1 with truncated natural-number subtraction, so it is 000 both when n=1n = 1n=1 and when n=0n = 0n=0;
  • nextHeight(S)=n\mathrm{nextHeight}(S) = nnextHeight(S)=n;
  • tip(S)\mathrm{tip}(S)tip(S) is the last header of the list, or the fixed genesis header if the list is empty; tipHash(S)=headerHash(tip(S))\mathrm{tipHash}(S) = \mathrm{headerHash}(\mathrm{tip}(S))tipHash(S)=headerHash(tip(S));
  • mtp(S)\mathrm{mtp}(S)mtp(S) ("median time past"): take the times of the headers at indices 0,…,tipHeight(S)0, \dots, \mathrm{tipHeight}(S)0,…,tipHeight(S), list them most recent first, keep the first 111111, sort ascending, and take the element at index ⌊ℓ/2⌋\lfloor \ell / 2 \rfloor⌊ℓ/2⌋ where ℓ\ellℓ is the length of that window (000 if the window is empty); mtpNat(S,h)\mathrm{mtpNat}(S, h)mtpNat(S,h) is the same computation for the headers at indices 0..h0..h0..h, converted to a natural number (negative values become 000);
  • requiredBits(S)\mathrm{requiredBits}(S)requiredBits(S): let fff be the header at index tipHeight(S)−2015\mathrm{tipHeight}(S) - 2015tipHeight(S)−2015 (truncated subtraction; the genesis header if the index is out of range); if (tipHeight(S)+1) mod 2016≠0(\mathrm{tipHeight}(S) + 1) \bmod 2016 \neq 0(tipHeight(S)+1)mod2016=0 the result is the tip's bits\mathrm{bits}bits field, otherwise it is the retargeted compact difficulty computed by the transcribed difficulty-adjustment routine from the tip's bits and time and fff's time.

The initial state is ⟨[genesisHeader], [ ]⟩\langle [\text{genesisHeader}],\ [\,]\rangle⟨[genesisHeader], []⟩: the single fixed genesis header and the empty ledger. genesisHash\mathrm{genesisHash}genesisHash is a fixed 32-byte constant.

State equivalence. Two chain states are equivalent, written S≈TS \approx TS≈T (the file's StateEquiv), when

S.headers=T.headersandS.utxo∼T.utxo,S.\mathrm{headers} = T.\mathrm{headers} \quad\text{and}\quad S.\mathrm{utxo} \sim T.\mathrm{utxo},S.headers=T.headersandS.utxo∼T.utxo,

i.e. the header lists are literally equal (same length, same headers in the same order) and the ledgers are equivalent in the sense above.

Validation. validate(S,b,t)\mathrm{validate}(S, b, t)validate(S,b,t), for a chain state SSS, a block bbb and an integer clock reading ttt, is the transcribed Bitcoin Core validation path: the header tests (proof-of-work, parent equal to tipHash(S)\mathrm{tipHash}(S)tipHash(S), bits equal to requiredBits(S)\mathrm{requiredBits}(S)requiredBits(S), time above mtp(S)\mathrm{mtp}(S)mtp(S), time at most t+7200t + 7200t+7200, version floors), the context-free block checks, the contextual block checks, and the ledger connection connectBlock(S,b)\mathrm{connectBlock}(S, b)connectBlock(S,b) (genesis-hash shortcut; the BIP30 scan where required; per-transaction input, fee, sequence-lock, sigop and script checks with the ledger updated transaction by transaction; the coinbase bound). Its outcome is accept(⟨S.headers+ ⁣ ⁣+[b.header],u⟩,undo)\mathrm{accept}(\langle S.\mathrm{headers} \mathbin{+\!\!+} [b.\mathrm{header}], u\rangle, \mathit{undo})accept(⟨S.headers++[b.header],u⟩,undo) when everything passes, and otherwise invalid\mathrm{invalid}invalid, futureTime\mathrm{futureTime}futureTime or missingPrev\mathrm{missingPrev}missingPrev. The ledger is consulted only through first-match lookup getCoin\mathrm{getCoin}getCoin (with a dummy coin where absent).

Reachability. Reachable(S)\mathrm{Reachable}(S)Reachable(S) is the least predicate such that the initial state ⟨[genesisHeader],[ ]⟩\langle [\text{genesisHeader}], [\,]\rangle⟨[genesisHeader],[]⟩ is reachable, and whenever Reachable(S)\mathrm{Reachable}(S)Reachable(S) and there exist a block bbb, an integer ttt, a state S′S'S′ and undo data undo\mathit{undo}undo with validate(S,b,t)=accept(S′,undo)\mathrm{validate}(S, b, t) = \mathrm{accept}(S', \mathit{undo})validate(S,b,t)=accept(S′,undo), then Reachable(S′)\mathrm{Reachable}(S')Reachable(S′). The clock reading ttt is unconstrained in each step and may differ from step to step.

Connecting a chain (the file's connectChain). For a chain state SSS and a list bs=[(b1,t1),…,(bk,tk)]bs = [(b_1, t_1), \dots, (b_k, t_k)]bs=[(b1​,t1​),…,(bk​,tk​)] of pairs of a block and an integer clock reading, connectChain(S,bs)\mathrm{connectChain}(S, bs)connectChain(S,bs) returns "none" or "some (T,[undo1,…,undok])(T, [\mathit{undo}_1, \dots, \mathit{undo}_k])(T,[undo1​,…,undok​])", defined by: for bs=[ ]bs = [\,]bs=[] it is "some (S,[ ])(S, [\,])(S,[])"; for (b,t)::rest(b, t) :: \mathit{rest}(b,t)::rest, if validate(S,b,t)=accept(S′,undo)\mathrm{validate}(S, b, t) = \mathrm{accept}(S', \mathit{undo})validate(S,b,t)=accept(S′,undo) then it is "none" if connectChain(S′,rest)\mathrm{connectChain}(S', \mathit{rest})connectChain(S′,rest) is "none" and "some (T,undo::undos)(T, \mathit{undo} :: \mathit{undos})(T,undo::undos)" if that is "some (T,undos)(T, \mathit{undos})(T,undos)"; if validate(S,b,t)\mathrm{validate}(S, b, t)validate(S,b,t) is any other outcome (invalid\mathrm{invalid}invalid, futureTime\mathrm{futureTime}futureTime or missingPrev\mathrm{missingPrev}missingPrev) it is "none". Thus a successful result has exactly one undo entry per block, in order, and TTT is the state after all kkk accepted blocks; for the empty list it is SSS itself.

Consistency. Consistent(S)\mathrm{Consistent}(S)Consistent(S) holds when there exists a chain state S0S_0S0​ with Reachable(S0)\mathrm{Reachable}(S_0)Reachable(S0​) and S≈S0S \approx S_0S≈S0​ (equal header lists and equivalent ledgers).

Statement

Binders and hypotheses. A chain state SSS with hS:Consistent(S)\mathit{hS} : \mathrm{Consistent}(S)hS:Consistent(S), i.e. there is a reachable S0S_0S0​ with S.headers=S0.headersS.\mathrm{headers} = S_0.\mathrm{headers}S.headers=S0​.headers and S.utxo∼S0.utxoS.\mathrm{utxo} \sim S_0.\mathrm{utxo}S.utxo∼S0​.utxo; a list cscscs of block–clock pairs; a chain state UUU; a list undos\mathit{undos}undos of undo data; and

h:connectChain(S,cs)=some (U,undos).h : \mathrm{connectChain}(S, cs) = \text{some } (U, \mathit{undos}).h:connectChain(S,cs)=some (U,undos).

Conclusion. Consistent(U)\mathrm{Consistent}(U)Consistent(U): there exists a reachable chain state U0U_0U0​ with U.headers=U0.headersU.\mathrm{headers} = U_0.\mathrm{headers}U.headers=U0​.headers and U.utxo∼U0.utxoU.\mathrm{utxo} \sim U_0.\mathrm{utxo}U.utxo∼U0​.utxo.

Edge cases the statement includes. For cs=[ ]cs = [\,]cs=[], U=SU = SU=S and the conclusion is hS\mathit{hS}hS. The hypothesis hhh requires every block of cscscs to be accepted in turn on SSS itself (not on S0S_0S0​); the conclusion does not relate U0U_0U0​ to S0S_0S0​ or to cscscs, nor mention undos\mathit{undos}undos. Nothing is asserted when connectChain(S,cs)\mathrm{connectChain}(S, cs)connectChain(S,cs) is "none".

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