Chains of blocks connected and disconnected: state equivalence, connectChain, disconnectChain, the freshness conditions, consistency
DefinitionBitcoinReorgSix names over the block mission's BitcoinBlockV2; nothing is re-transcribed.
StateEquiv S T — two chain states with the same header list whose ledgers hold the same coin at every outpoint (getCoin agrees everywhere; the association lists may differ in order).
connectChain S bs — connect the blocks of bs in order, each with its own clock reading, through the block mission's validate; none if any block is not accepted, else the final state and the list of the blocks' undo data (CBlockUndo of each, in connection order).
disconnectTip S b undo — DisconnectBlock on S.utxo at the tip's height with b's hash and undo data, then the tip header popped; none is DISCONNECT_FAILED, the flag is DISCONNECT_OK (clean) versus DISCONNECT_UNCLEAN.
disconnectChain S l — disconnectTip for each (block, undo) pair of l in the order given (the tip first), the flags conjoined.
FreshChain S bs — the side conditions under which undo data restores a ledger exactly, continued along the states each accepted block produces: the txids within each block are distinct, no txid of the block already has a coin in the ledger it is connected to (the BIP30 condition, which ConnectBlock enforces only where its scan runs), and the block does not hash to the genesis hash.
Consistent S — S is StateEquiv to some state reachable from the genesis.
Formalization Note. validate, disconnectBlock, Reachable, Equiv, updateCoins, connectBlock are the block mission's. Only Std is imported.
import Definitions.Def_BitcoinBlockV2
/-!
# Reorganizations
A node that learns of a better chain disconnects blocks from its tip, restoring the UTXO set from
the undo data it recorded when it connected them, and then connects the blocks of the new branch.
`DisconnectBlock` and `ConnectBlock` are the block mission's; this file names the sequences — a
chain of blocks connected in order with one clock reading each, a chain disconnected from the tip
with the recorded undo data — and the relation under which two chain states are the same up to
the order of their ledgers, so that the theorems can say: the state a reorganization produces is,
up to that order, a state reachable from the genesis by direct validation.
-/
namespace BitcoinReorg
open BitcoinSer BitcoinBlockV2
/-- Two chain states with the same headers whose ledgers hold the same coin at every outpoint. -/
def StateEquiv (S T : ChainState) : Prop := S.headers = T.headers ∧ Equiv S.utxo T.utxo
/-- Connect blocks in order, each with its clock reading; the undo data of every block is kept.
`none` if any block is not accepted. -/
def connectChain : ChainState → List (Block × Int) → Option (ChainState × List BlockUndo)
| S, [] => some (S, [])
| S, (b, now) :: rest =>
match validate S b now with
| .accept S' undo =>
match connectChain S' rest with
| none => none
| some (T, undos) => some (T, undo :: undos)
| _ => none
/-- Disconnect the tip block `b` with its undo data: `DisconnectBlock` on the ledger at the tip's
height and hash, and the header popped. The flag is `DISCONNECT_OK` versus `DISCONNECT_UNCLEAN`. -/
def disconnectTip (S : ChainState) (b : Block) (undo : BlockUndo) : Option (ChainState × Bool) :=
match disconnectBlock S.utxo S.tipHeight (headerHash b.header) b undo with
| none => none
| some (u, clean) => some (⟨S.headers.dropLast, u⟩, clean)
/-- Disconnect blocks from the tip, in the order given (the tip block first). -/
def disconnectChain : ChainState → List (Block × BlockUndo) → Option (ChainState × Bool)
| S, [] => some (S, true)
| S, (b, undo) :: rest =>
match disconnectTip S b undo with
| none => none
| some (S', clean) =>
match disconnectChain S' rest with
| none => none
| some (T, c) => some (T, clean && c)
/-- The side conditions under which undo data restores a ledger exactly, along a chain: every
block's txids are distinct, none of them already has a coin in the ledger it is connected to
(the BIP30 condition, which `ConnectBlock` enforces only where its scan runs), and no block
hashes to the genesis hash; the condition continues from the state each block produces. -/
def FreshChain : ChainState → List (Block × Int) → Prop
| _, [] => True
| S, (b, now) :: rest =>
(b.vtx.map txid).Nodup ∧ (∀ tx ∈ b.vtx, ∀ o, getCoin S.utxo ⟨txid tx, o⟩ = none) ∧
headerHash b.header ≠ genesisHash ∧
∀ S' undo, validate S b now = .accept S' undo → FreshChain S' rest
/-- A chain state that is, up to the order of its ledger, reachable from the genesis. -/
def Consistent (S : ChainState) : Prop := ∃ S₀, Reachable S₀ ∧ StateEquiv S S₀
end BitcoinReorg
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: Def_BitcoinReorg.lean
This file introduces six declarations in the namespace BitcoinReorg, building on the block-validation definitions it imports. The imported notions are expanded first so that each declaration's paragraph can be read on its own.
Imported notions, expanded
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 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)".
Declaration 1: StateEquiv
For chain states and , — written below — is the proposition
The first conjunct is literal equality of the two header lists (same length, same headers at every position). The second is ledger equivalence : the first-match lookup agrees at every outpoint, with the quantifier ranging over all byte strings and all natural numbers. Two ledgers that differ only in the order of entries, in shadowed duplicate entries, or in the number of copies of an entry are equivalent; two ledgers of different lengths can be equivalent; and a ledger with entries whose scripts are unspendable is not excluded.
Declaration 2: connectChain
takes a chain state and a list of pairs of a block and an integer clock reading, and returns "none" or "some " where is a chain state and is a list of undo data (each undo datum being a list of lists of coins). It is defined by recursion on :
- ;
- : evaluate . If it is , then evaluate : if that is "none" the result is "none", and if it is "some " the result is "some ". If is , or , the result is "none".
Each block is validated against the state produced by its predecessors with its own clock reading ; the clock readings are independent integers with no monotonicity relation among them. On success the returned list has exactly one entry per block, in order. For the empty list the state is returned unchanged with an empty undo list, with no condition on .
Declaration 3: disconnectTip
, for a chain state , a block and undo data , returns "none" or "some " with a Boolean. It evaluates
where with truncated subtraction (so for both one and zero headers). If that is "none" the result is "none"; if it is "some " the result is "some (where removes the last element of a list, and is the identity on the empty list)". The hash passed to is the hash of the given block's header, and the header removed is whatever is last in ; nothing checks that these coincide. Removing the last element of an empty list yields the empty list, so on a state with no headers can still succeed. The Boolean returned is the flag of (the conjunction of all per-output and per-input flags described above); the docstring names it "DISCONNECT_OK versus DISCONNECT_UNCLEAN".
Declaration 4: disconnectChain
takes a chain state and a list of pairs of a block and undo data, and returns "none" or "some " with a Boolean, by recursion on the list:
- ;
- : if is "none" the result is "none"; if it is "some ", then if is "none" the result is "none", and if it is "some " the result is "some ".
The pairs are consumed from the front, so the first pair of the list is disconnected first (the docstring: "the tip block first"), and each later pair is disconnected from the state the previous step produced; the final Boolean is the conjunction of every step's flag, and is for the empty list.
Declaration 5: FreshChain
is a proposition on a chain state and a list of block–clock pairs, defined by recursion on :
- is true (no condition on );
- is the conjunction of
- has no duplicate entries (so no two transactions of , including the coinbase, have the same txid);
- — the ledger of has no coin at any outpoint whose hash is a txid of , the index ranging over all natural numbers, not only the indices of actual outputs;
- ;
- .
Conjunct 4 is vacuously satisfied whenever is not an acceptance, so does not by itself imply that any block of is accepted; conjuncts 1–3 are only ever imposed on the blocks up to and including the first one that is not accepted. The docstring says that conjunct 2 is the BIP30 condition, "which ConnectBlock enforces only where its scan runs" — the scan inside is conditional on the height and hash and tests only indices below the output count, whereas conjunct 2 is unconditional and over all indices.
Declaration 6: Consistent
is the proposition
i.e. there is some state reachable from the initial state by a sequence of accepted blocks (each with an arbitrary clock reading) whose header list equals that of and whose ledger is equivalent to that of . In particular every reachable state is consistent (take ), and consistency does not constrain the order, duplication or shadowing of entries in .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.