Multi-block undo: a connected chain is disconnected back to its starting state
ProvedBitcoinReorg.disconnectChain_connectChainFor a reachable S, a chain bs satisfying FreshChain S bs, and connectChain S bs = some (T, undos): disconnecting from T the blocks of bs with their undo data, tip first, succeeds with every disconnect clean and yields a state StateEquiv to S. The undo data recorded over any number of blocks restores the chain state exactly, up to ledger order.
import Definitions.Def_BitcoinReorg import Definitions.Def_BitcoinSer open BitcoinReorg BitcoinBlockV2
theorem BitcoinReorg.disconnectChain_connectChain (bs : List (BitcoinSer.Block × Int)) :
∀ (S : ChainState), BitcoinBlockV2.Reachable S → BitcoinReorg.FreshChain S bs →
∀ (T : ChainState) (undos : List BlockUndo), BitcoinReorg.connectChain S bs = some (T, undos) →
∃ S', BitcoinReorg.disconnectChain T ((bs.map Prod.fst).zip undos).reverse = some (S', true) ∧
BitcoinReorg.StateEquiv S' S := 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.disconnectChain_connectChain
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.
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.
The validation outcome , for a chain state , a block and an integer clock reading , is one of four outcomes: carrying a new state and undo data, , , or . It is computed by the following sequence of tests, the first failing test deciding the outcome. Write .
Header path.
- If the proof-of-work test fails — the header hash read as a little-endian 256-bit integer exceeds the target decoded from , or decodes to a negative, zero, overflowing, or above-limit target — the outcome is .
- Else if , the outcome is .
- Else if (as 32-bit words), the outcome is .
- Else if , the outcome is .
- Else if , the outcome is .
- Else if the version is outdated — — the outcome is .
Context-free block check (checkBlock): the outcome is unless all of the following hold: the proof-of-work test of step 1 again; the Merkle root computed from the txids of equals and the Merkle computation does not report a duplicated-subtree mutation; is non-empty; ; four times the length of the witness-stripped serialization of is at most ; the first transaction is a coinbase; every other transaction is not a coinbase; every transaction passes checkTransaction (non-empty inputs and outputs; four times its witness-stripped size at most ; every output value in with the running total staying in that range; input outpoints pairwise distinct; for a coinbase the first input's scriptSig has length in , for a non-coinbase no input has the null outpoint); and four times the sum of the legacy signature-operation counts of all transactions is at most .
Contextual block check (contextualCheckBlock), with height and cutoff if and otherwise: the outcome is unless every transaction is final (, or when and otherwise, or every input has ); unless, when , the canonical script push of is a prefix of the coinbase's first input scriptSig; unless the witness-commitment check passes with "expected" set to (when not expected: no transaction carries witness data; when expected: if no coinbase output is a commitment output then no transaction carries witness data, else the coinbase's first-input witness stack is a single 32-byte nonce and the double SHA-256 of the witness Merkle root concatenated with that nonce equals bytes 6–37 of the last commitment output's script); and unless the block weight (three times the witness-stripped serialized length plus the full serialized length) is at most .
Ledger connection. Finally (expanded below) is computed; if it is "none" the outcome is , and if it is "some " the outcome is
the header appended at the end of the list and the ledger replaced by .
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.
Reachability. is the least predicate such that the initial state is reachable, and whenever and there exist a block , an integer , a state and undo data with , then . The clock reading is unconstrained in each step and may differ from step to step.
The block disconnection , for a ledger , a natural number , a byte string , a block and undo data (a list of lists of coins), returns "none" or "some " with a Boolean:
- If , the result is "none".
- Otherwise let (the exception flag) hold exactly when is or . Pair the transactions of with undo entries so that the first transaction gets "no undo" and the -th transaction () gets the -th entry of , and process these pairs in reverse block order (last transaction first), threading the ledger and conjoining the flags. For one pair on ledger , with = " is a coinbase":
- Outputs. For each output of at index in order: if 's script is unspendable, nothing happens and the flag for this output is true; otherwise let , let hold when is some coin with , and , replace by , and the flag for this output is . The output phase's flag is the conjunction over outputs.
- Inputs. If is "no undo", the pair yields . Otherwise, with a list of coins : if the whole result is "none"; else the inputs are restored last input first: for the input paired with coin and outpoint , let the per-input flag be " is none"; if then look for the first entry of whose outpoint hash equals — if there is none the whole result is "none", and if there is one with coin then replace by with height and coinbase flag copied from ; then replace by (so a coin with an unspendable script is not re-added). The input phase's flag is the conjunction of the per-input flags, and the pair's flag is the output flag and the input flag.
- The result is "some (final ledger, conjunction of all pairs' flags)".
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.
Disconnecting the tip and a chain (the file's disconnectTip and disconnectChain). computes ; if that is "none" the result is "none", and if it is "some " the result is "some (where removes the last element of a list, and is the identity on the empty list)". No comparison is made between and the header actually at the tip of ; removing the last element of an empty list gives the empty list. is "some " for the empty list, and otherwise applies with , then recursively the rest on the resulting state, returning "none" if any step is "none" and otherwise "some (final state, conjunction of all the Boolean flags)".
The freshness side condition (the file's FreshChain). is the proposition defined by: for it is true; for it is the conjunction of
- the list has no duplicates;
- for every transaction and every natural number (not only ), ;
- ;
- for every state and undo data such that , .
Conjunct 4 is vacuously true when is not an acceptance; since acceptance determines and uniquely, when it is an acceptance conjunct 4 is just of the accepted state and the remaining list.
Statement
Binders and hypotheses. A list of block–clock pairs; then, universally, a chain state with and ; then, universally, a chain state and a list of undo data with
Under the last hypothesis has the same length as , each block was accepted by on the state its predecessors produced, and .
Conclusion. There exists a chain state such that
The list passed to is the pairing of the blocks of (the clock readings dropped) with the entries of , position by position, in reverse order — so the last connected block is disconnected first, each from the state the previous disconnection produced, using of the current state as the height and the block's own header hash. The flag means every one of the disconnections returned the flag (for every block: each non-unspendable output was present with the recorded value, height and coinbase flag, or the height/hash exception applied; each restored input was absent when restored; no height- undo coin lacked a same-hash entry to borrow from). means has exactly the header list of and a ledger equivalent to under first-match lookup.
Edge cases the statement includes. For : , , the pairing is empty, , and . If has a block whose validation on its predecessor state is not an acceptance, the hypothesis is false and the statement is vacuous for that . Pairing by position (zip) truncates to the shorter list, but under the hypotheses both lists have length . excludes genesis-hash blocks, so no block takes the shortcut that returns empty undo data.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.