ConnectBlock respects ledger equivalence
ProvedBitcoinReorg.connectBlock_equivFor two states with the same headers and equivalent ledgers, connectBlock on the same block either fails on both or succeeds on both with equivalent ledgers and the same undo data. Every ledger read of the transaction loop — CheckTxInputs, SequenceLocks, the sigop cost, CheckInputScripts, the undo record, the BIP30 scan — goes through getCoin.
import Definitions.Def_BitcoinReorg import Definitions.Def_BitcoinSer open BitcoinReorg BitcoinBlockV2
theorem BitcoinReorg.connectBlock_equiv (H : List BitcoinSer.Header) (u v : Ledger) (h : BitcoinBlockV2.Equiv u v)
(b : BitcoinSer.Block) :
(BitcoinBlockV2.connectBlock ⟨H, u⟩ b = none ∧ BitcoinBlockV2.connectBlock ⟨H, v⟩ b = none) ∨
(∃ u' v' undo, BitcoinBlockV2.connectBlock ⟨H, u⟩ b = some (u', undo) ∧
BitcoinBlockV2.connectBlock ⟨H, v⟩ b = some (v', undo) ∧ BitcoinBlockV2.Equiv 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.connectBlock_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.
Spending and adding coins. is with every pair whose outpoint equals removed. A script byte string is unspendable when it is non-empty and its first byte is the opcode , or when its length exceeds the constant . is unchanged if is unspendable, and otherwise is the pair prepended to .
Transactions. A transaction has a natural-number version, a list of inputs (each input has an outpoint , a script , a natural number , and a witness stack, a list of byte strings), a list of outputs (each an integer value and a script), and a natural number . is a coinbase exactly when has exactly one input and that input's outpoint is the null outpoint (hash equal to 32 zero bytes and index ). is the double SHA-256 of the serialization of with all witness data stripped.
The ledger update , for a ledger , a transaction and a natural number : let if is a coinbase, and otherwise let be with applied successively for the outpoint of every input of in order (no check is made that those outpoints are present). Then, for the outputs of in order, apply successively
and the result is . Outputs with unspendable scripts are therefore not stored, and each stored output replaces (after removal of) any earlier entry with the same outpoint.
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.
The ledger connection returns either "none" or "some " with a ledger and a list of lists of coins. Let and .
- If , the result is "some ": the ledger is unchanged and the undo data is the empty list, whatever contains.
- Else, the BIP30 scan is required when , where holds only for and holds when has an entry at index whose hash is the fixed BIP34 hash. If the scan is required and some transaction and some index have , the result is "none".
- Else, with the script flags determined by and by whether is one of two fixed exception hashes, the transactions of are processed in order starting from the accumulator . For each with current ledger :
- if is a coinbase, fees and undo are unchanged;
- otherwise
checkTxInputsmust succeed: every input outpoint has a coin in ; for each input coin in order, it is not the case that and (truncated subtraction, so a coinbase coin with counts as immature), and the running input total are in ; the input total is at least the output total of ; and the fee (input total minus output total) is in ; then the accumulated fees plus this fee must be in ; the transcribed BIP68 sequence-lock check against , the median-time-past function , the lock-time flags of , and the heights of the spent coins must pass; and the list — for each input in order, the coin at its outpoint in , or the dummy coin if absent — is appended to the undo list; - then the accumulated sigop cost is increased by the transaction's sigop cost (legacy count times 4, plus, for a non-coinbase, the P2SH count times 4 when the P2SH flag is set and the witness sigop count), and must not exceed ;
- then, for a non-coinbase, every input's script must verify under the full transcribed script interpreter (with the spent outputs supplied);
- the ledger becomes . Any failure yields "none".
- After the loop, if the output total of the first transaction of (the fixed genesis coinbase if is empty) exceeds the accumulated fees plus the subsidy at height (namely shifted right by , and once that quotient is at least ), the result is "none"; otherwise it is "some (final ledger, final undo list)".
When the result is "some " and , has exactly one entry per non-coinbase transaction of , in block order.
Statement
Binders. A list of headers ; two ledgers and ; a hypothesis (); and a block . The two chain states considered are and : the same header list with the two ledgers. No condition is placed on (it may be empty, need not start with the genesis header), on (it need not pass any header or block check — only is applied, not ), or on , beyond equivalence.
Conclusion. Exactly one of the following two alternatives is asserted to hold (as a disjunction):
- and ; or
- there exist ledgers , and undo data (a list of lists of coins) such that
In alternative 2 the undo data is literally the same list on both sides (so, since each undo entry is the list of coins read by first-match lookup at the inputs' outpoints — or the dummy coin where absent — those lookups agree), and the resulting ledgers are only asserted equivalent, not equal.
Edge cases the statement includes. If , returns "some " and "some " respectively, and alternative 2 holds with , . If is empty, the loop does nothing and the coinbase bound is checked against the fixed genesis coinbase's output value versus . The height used throughout is and the BIP30 ancestor test consults at index ; the median-time-past function used by the sequence-lock check is derived from alone. The statement does not say which alternative holds for a given input, only that one does.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.