connectChain respects state equivalence
ProvedBitcoinReorg.connectChain_equivConnecting the same chain to two StateEquiv states either fails on both or succeeds on both with StateEquiv results and the same undo data.
import Definitions.Def_BitcoinReorg import Definitions.Def_BitcoinSer open BitcoinReorg BitcoinBlockV2
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 sorryRead-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 is a finite list of pairs , where is an outpoint (a byte string and a natural number ) and is a coin (an output consisting of an integer value and a byte-string script ; a natural-number creation height ; and a Boolean coinbase flag ). The lookup scans from the front and returns the coin of the first pair whose outpoint equals (as a value "some "), or "none" if no pair has outpoint ; any later pair with the same outpoint is shadowed and never consulted. Two ledgers are equivalent, written , when
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 is a pair of a list of headers and a ledger . A header has an integer version, byte strings and , and natural numbers , , ; is the double SHA-256 of its 80-byte serialization. A block is a header and a list of transactions . Derived quantities of a state with :
- with truncated natural-number subtraction, so it is both when and when ;
- ;
- is the last header of the list, or the fixed genesis header if the list is empty; ;
- ("median time past"): take the times of the headers at indices , list them most recent first, keep the first , sort ascending, and take the element at index where is the length of that window ( if the window is empty); is the same computation for the headers at indices , converted to a natural number (negative values become );
- : let be the header at index (truncated subtraction; the genesis header if the index is out of range); if the result is the tip's field, otherwise it is the retargeted compact difficulty computed by the transcribed difficulty-adjustment routine from the tip's bits and time and 's time.
The initial state is : the single fixed genesis header and the empty ledger. is a fixed 32-byte constant.
State equivalence. Two chain states are equivalent, written (the file's StateEquiv), when
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. , for a chain state , a block and an integer clock reading , is the transcribed Bitcoin Core validation path: the header tests (proof-of-work, parent equal to , bits equal to , time above , time at most , version floors), the context-free block checks, the contextual block checks, and the ledger connection (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 ; the coinbase bound). Its outcome is when everything passes with connected ledger and recorded undo data , and otherwise , or . All header and block tests read only the header list and ; only reads the ledger, and it does so through (first-match lookup) and the dummy-coin fallback.
Connecting a chain (the file's connectChain). For a chain state and a list of pairs of a block and an integer clock reading, returns "none" or "some ", defined by: for it is "some "; for , if then it is "none" if is "none" and "some " if that is "some "; if is any other outcome (, or ) it is "none". Thus a successful result has exactly one undo entry per block, in order, and is the state after all accepted blocks; for the empty list it is itself.
Statement
Binders and hypotheses. A list of block–clock pairs; then, universally, chain states and with the hypothesis (equal header lists, equivalent ledgers). No reachability or well-formedness is assumed.
Conclusion. A disjunction: either
- and ; or
- there exist chain states , and a list of undo data such that
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 alternative 2 holds with , , 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.