validate respects state equivalence
ProvedBitcoinReorg.validate_equivFor StateEquiv S T and any block and clock reading, validate gives the same outcome on both (invalid, futureTime, missingPrev), or accepts both with StateEquiv results and the same undo data. The header path and ContextualCheckBlock read only the headers.
import Definitions.Def_BitcoinReorg import Definitions.Def_BitcoinSer open BitcoinReorg BitcoinBlockV2
theorem BitcoinReorg.validate_equiv (S T : ChainState) (h : BitcoinReorg.StateEquiv S T) (b : BitcoinSer.Block) (now : Int) :
(BitcoinBlockV2.validate S b now = .invalid ∧ BitcoinBlockV2.validate T b now = .invalid) ∨
(BitcoinBlockV2.validate S b now = .futureTime ∧ BitcoinBlockV2.validate T b now = .futureTime) ∨
(BitcoinBlockV2.validate S b now = .missingPrev ∧ BitcoinBlockV2.validate T b now = .missingPrev) ∨
(∃ S' T' undo, BitcoinBlockV2.validate S b now = .accept S' undo ∧ BitcoinBlockV2.validate T b now = .accept T' undo ∧
BitcoinReorg.StateEquiv S' T') := 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.validate_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.
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.
Statement
Binders. Chain states and ; a hypothesis , i.e. and ; a block ; and an integer clock reading . Nothing else is assumed: need not be reachable or well-formed, its header list may be empty or not start at the genesis header, and is arbitrary.
Conclusion. A four-way disjunction; the statement asserts that at least one of the following holds:
- and ;
- and ;
- and ;
- there exist chain states , and undo data with
In alternative 4 the undo data is the same list on both sides, and the accepted states are equivalent: by the definition of each has header list (equal on both sides since the input header lists are equal), and their ledgers — the outputs of — are asserted equivalent, not equal.
Edge cases the statement includes. Every test on the header path, the context-free block check and the contextual block check reads only the header list and , so under the hypothesis they agree on and by construction; the content of the claim lies in , which reads the ledger. The ordering of the header tests is part of what is asserted: for instance, a block whose time exceeds but whose do not match the required bits yields , not . When and the header and block checks pass, alternative 4 holds with and carrying the unchanged ledgers of and and empty undo data.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.