Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

connectChain respects state equivalence

Proved
BitcoinReorg.connectChain_equiv

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

bitcoinbitcoin-mainnetchainstateconsensusformal-verificationreorgreorganizationundoutxo

Connecting the same chain to two StateEquiv states either fails on both or succeeds on both with StateEquiv results and the same undo data.

Preamble
import Definitions.Def_BitcoinReorg
import Definitions.Def_BitcoinSer
open BitcoinReorg BitcoinBlockV2
Formal statement
theorem BitcoinReorg.connectChain_equiv (bs : List (BitcoinSer.Block × Int)) :
    ∀ (S T : ChainState), BitcoinReorg.StateEquiv S T →
    (BitcoinReorg.connectChain S bs = none ∧ BitcoinReorg.connectChain T bs = none) ∨
    (∃ U V undos, BitcoinReorg.connectChain S bs = some (U, undos) ∧ BitcoinReorg.connectChain T bs = some (V, undos) ∧
      BitcoinReorg.StateEquiv U V) := 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.connectChain_equiv

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 returning the ledger unchanged with empty undo data; the BIP30 scan where required; per-transaction input, fee, sequence-lock, sigop and script checks with the ledger updated by updateCoins\mathrm{updateCoins}updateCoins; 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 with connected ledger uuu and recorded undo data undo\mathit{undo}undo, and otherwise invalid\mathrm{invalid}invalid, futureTime\mathrm{futureTime}futureTime or missingPrev\mathrm{missingPrev}missingPrev. All header and block tests read only the header list and bbb; only connectBlock\mathrm{connectBlock}connectBlock reads the ledger, and it does so through getCoin\mathrm{getCoin}getCoin (first-match lookup) and the dummy-coin fallback.

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.

Statement

Binders and hypotheses. A list bsbsbs of block–clock pairs; then, universally, chain states SSS and TTT with the hypothesis S≈TS \approx TS≈T (equal header lists, equivalent ledgers). No reachability or well-formedness is assumed.

Conclusion. A disjunction: either

  1. connectChain(S,bs)=none\mathrm{connectChain}(S, bs) = \text{none}connectChain(S,bs)=none and connectChain(T,bs)=none\mathrm{connectChain}(T, bs) = \text{none}connectChain(T,bs)=none; or
  2. there exist chain states UUU, VVV and a list undos\mathit{undos}undos of undo data such that
connectChain(S,bs)=some (U,undos),connectChain(T,bs)=some (V,undos),U≈V.\mathrm{connectChain}(S, bs) = \text{some } (U, \mathit{undos}),\qquad \mathrm{connectChain}(T, bs) = \text{some } (V, \mathit{undos}),\qquad U \approx V.connectChain(S,bs)=some (U,undos),connectChain(T,bs)=some (V,undos),U≈V.

In alternative 2 the undo lists are literally the same list, and the final states have equal header lists and equivalent (not necessarily equal) ledgers.

Edge cases the statement includes. For bs=[ ]bs = [\,]bs=[] alternative 2 holds with U=SU = SU=S, V=TV = TV=T, undos=[ ]\mathit{undos} = [\,]undos=[] directly from the hypothesis. The statement does not say which alternative holds, only that one does; it also does not say at which block, if any, both runs fail.

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