Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Chains of blocks connected and disconnected: state equivalence, connectChain, disconnectChain, the freshness conditions, consistency

Definition
BitcoinReorg

by pitimespi · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitcoinbitcoin-mainnetchainstateconsensusformal-verificationreorgreorganizationundoutxo

Six 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.

Definition code
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
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: ConnectBlock, DisconnectBlock, UpdateCoins, ApplyTxInUndo, Chainstate::ConnectTip, Chainstate::DisconnectTip, Chainstate::ActivateBestChainStep, src/validation.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/validation.cpp; CCoinsViewCache (coins.cpp)
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 uuu is a finite list of pairs (p,c)(p, c)(p,c), where ppp is an outpoint (a byte string p.hashp.\mathrm{hash}p.hash and a natural number p.np.np.n) and ccc is a coin (an output c.outc.\mathrm{out}c.out consisting of an integer value c.out.nValuec.\mathrm{out}.\mathrm{nValue}c.out.nValue and a byte-string script c.out.scriptPubKeyc.\mathrm{out}.\mathrm{scriptPubKey}c.out.scriptPubKey; a natural-number creation height c.heightc.\mathrm{height}c.height; and a Boolean coinbase flag c.isCoinbasec.\mathrm{isCoinbase}c.isCoinbase). The lookup getCoin(u,p)\mathrm{getCoin}(u, p)getCoin(u,p) scans uuu from the front and returns the coin of the first pair whose outpoint equals ppp (as a value "some ccc"), or "none" if no pair has outpoint ppp; any later pair with the same outpoint is shadowed and never consulted. Two ledgers are equivalent, written u∼vu \sim vu∼v, when

∀p,getCoin(u,p)=getCoin(v,p),\forall p,\quad \mathrm{getCoin}(u, p) = \mathrm{getCoin}(v, p),∀p,getCoin(u,p)=getCoin(v,p),

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. spendCoin(u,p)\mathrm{spendCoin}(u, p)spendCoin(u,p) is uuu with every pair whose outpoint equals ppp removed. A script byte string sss is unspendable when it is non-empty and its first byte is the opcode OP_RETURN\mathtt{OP\_RETURN}OP_RETURN, or when its length exceeds the constant MAX_SCRIPT_SIZE\mathrm{MAX\_SCRIPT\_SIZE}MAX_SCRIPT_SIZE. addCoin(u,p,c)\mathrm{addCoin}(u, p, c)addCoin(u,p,c) is uuu unchanged if c.out.scriptPubKeyc.\mathrm{out}.\mathrm{scriptPubKey}c.out.scriptPubKey is unspendable, and otherwise is the pair (p,c)(p, c)(p,c) prepended to spendCoin(u,p)\mathrm{spendCoin}(u, p)spendCoin(u,p).

Transactions. A transaction txtxtx has a natural-number version, a list of inputs tx.vintx.\mathrm{vin}tx.vin (each input iii has an outpoint i.prevouti.\mathrm{prevout}i.prevout, a script i.scriptSigi.\mathrm{scriptSig}i.scriptSig, a natural number i.nSequencei.\mathrm{nSequence}i.nSequence, and a witness stack, a list of byte strings), a list of outputs tx.vouttx.\mathrm{vout}tx.vout (each an integer value and a script), and a natural number tx.nLockTimetx.\mathrm{nLockTime}tx.nLockTime. txtxtx is a coinbase exactly when tx.vintx.\mathrm{vin}tx.vin has exactly one input and that input's outpoint is the null outpoint (hash equal to 32 zero bytes and index n=232−1n = 2^{32} - 1n=232−1). txid(tx)\mathrm{txid}(tx)txid(tx) is the double SHA-256 of the serialization of txtxtx with all witness data stripped.

The ledger update updateCoins(u,tx,h)\mathrm{updateCoins}(u, tx, h)updateCoins(u,tx,h), for a ledger uuu, a transaction txtxtx and a natural number hhh: let u1=uu_1 = uu1​=u if txtxtx is a coinbase, and otherwise let u1u_1u1​ be uuu with spendCoin\mathrm{spendCoin}spendCoin applied successively for the outpoint i.prevouti.\mathrm{prevout}i.prevout of every input iii of txtxtx in order (no check is made that those outpoints are present). Then, for the outputs o0,o1,…,ok−1o_0, o_1, \dots, o_{k-1}o0​,o1​,…,ok−1​ of txtxtx in order, apply successively

uj+1=addCoin(uj, (txid(tx),j), ⟨oj, h, isCoinbase(tx)⟩),u_{j+1} = \mathrm{addCoin}\big(u_j,\ (\mathrm{txid}(tx), j),\ \langle o_j,\ h,\ \text{isCoinbase}(tx)\rangle\big),uj+1​=addCoin(uj​, (txid(tx),j), ⟨oj​, h, isCoinbase(tx)⟩),

and the result is uku_kuk​. 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 SSS is a pair of a list of headers S.headersS.\mathrm{headers}S.headers and a ledger S.utxoS.\mathrm{utxo}S.utxo. A header has an integer version, byte strings prevBlock\mathrm{prevBlock}prevBlock and merkleRoot\mathrm{merkleRoot}merkleRoot, and natural numbers time\mathrm{time}time, bits\mathrm{bits}bits, nonce\mathrm{nonce}nonce; headerHash(h)\mathrm{headerHash}(h)headerHash(h) is the double SHA-256 of its 80-byte serialization. A block bbb is a header b.headerb.\mathrm{header}b.header and a list of transactions b.vtxb.\mathrm{vtx}b.vtx. Derived quantities of a state SSS with n=∣S.headers∣n = |S.\mathrm{headers}|n=∣S.headers∣:

  • tipHeight(S)=n−1\mathrm{tipHeight}(S) = n - 1tipHeight(S)=n−1 with truncated natural-number subtraction, so it is 000 both when n=1n = 1n=1 and when n=0n = 0n=0;
  • nextHeight(S)=n\mathrm{nextHeight}(S) = nnextHeight(S)=n;
  • tip(S)\mathrm{tip}(S)tip(S) is the last header of the list, or the fixed genesis header if the list is empty; tipHash(S)=headerHash(tip(S))\mathrm{tipHash}(S) = \mathrm{headerHash}(\mathrm{tip}(S))tipHash(S)=headerHash(tip(S));
  • mtp(S)\mathrm{mtp}(S)mtp(S) ("median time past"): take the times of the headers at indices 0,…,tipHeight(S)0, \dots, \mathrm{tipHeight}(S)0,…,tipHeight(S), list them most recent first, keep the first 111111, sort ascending, and take the element at index ⌊ℓ/2⌋\lfloor \ell / 2 \rfloor⌊ℓ/2⌋ where ℓ\ellℓ is the length of that window (000 if the window is empty); mtpNat(S,h)\mathrm{mtpNat}(S, h)mtpNat(S,h) is the same computation for the headers at indices 0..h0..h0..h, converted to a natural number (negative values become 000);
  • requiredBits(S)\mathrm{requiredBits}(S)requiredBits(S): let fff be the header at index tipHeight(S)−2015\mathrm{tipHeight}(S) - 2015tipHeight(S)−2015 (truncated subtraction; the genesis header if the index is out of range); if (tipHeight(S)+1) mod 2016≠0(\mathrm{tipHeight}(S) + 1) \bmod 2016 \neq 0(tipHeight(S)+1)mod2016=0 the result is the tip's bits\mathrm{bits}bits field, otherwise it is the retargeted compact difficulty computed by the transcribed difficulty-adjustment routine from the tip's bits and time and fff's time.

The initial state is ⟨[genesisHeader], [ ]⟩\langle [\text{genesisHeader}],\ [\,]\rangle⟨[genesisHeader], []⟩: the single fixed genesis header and the empty ledger. genesisHash\mathrm{genesisHash}genesisHash is a fixed 32-byte constant.

The validation outcome validate(S,b,t)\mathrm{validate}(S, b, t)validate(S,b,t), for a chain state SSS, a block bbb and an integer clock reading ttt, is one of four outcomes: accept(S′,undo)\mathrm{accept}(S', \mathit{undo})accept(S′,undo) carrying a new state and undo data, invalid\mathrm{invalid}invalid, futureTime\mathrm{futureTime}futureTime, or missingPrev\mathrm{missingPrev}missingPrev. It is computed by the following sequence of tests, the first failing test deciding the outcome. Write h=b.headerh = b.\mathrm{header}h=b.header.

Header path.

  1. If the proof-of-work test fails — the header hash read as a little-endian 256-bit integer exceeds the target decoded from h.bitsh.\mathrm{bits}h.bits, or h.bitsh.\mathrm{bits}h.bits decodes to a negative, zero, overflowing, or above-limit target — the outcome is invalid\mathrm{invalid}invalid.
  2. Else if h.prevBlock≠tipHash(S)h.\mathrm{prevBlock} \neq \mathrm{tipHash}(S)h.prevBlock=tipHash(S), the outcome is missingPrev\mathrm{missingPrev}missingPrev.
  3. Else if h.bits≠requiredBits(S)h.\mathrm{bits} \neq \mathrm{requiredBits}(S)h.bits=requiredBits(S) (as 32-bit words), the outcome is invalid\mathrm{invalid}invalid.
  4. Else if h.time≤mtp(S)h.\mathrm{time} \le \mathrm{mtp}(S)h.time≤mtp(S), the outcome is invalid\mathrm{invalid}invalid.
  5. Else if t+7200<h.timet + 7200 < h.\mathrm{time}t+7200<h.time, the outcome is futureTime\mathrm{futureTime}futureTime.
  6. Else if the version is outdated — (h.version<2∧227931≤tipHeight(S)+1)∨(h.version<3∧363725≤tipHeight(S)+1)∨(h.version<4∧388381≤tipHeight(S)+1)(h.\mathrm{version} < 2 \wedge 227931 \le \mathrm{tipHeight}(S) + 1) \vee (h.\mathrm{version} < 3 \wedge 363725 \le \mathrm{tipHeight}(S) + 1) \vee (h.\mathrm{version} < 4 \wedge 388381 \le \mathrm{tipHeight}(S) + 1)(h.version<2∧227931≤tipHeight(S)+1)∨(h.version<3∧363725≤tipHeight(S)+1)∨(h.version<4∧388381≤tipHeight(S)+1) — the outcome is invalid\mathrm{invalid}invalid.

Context-free block check (checkBlock): the outcome is invalid\mathrm{invalid}invalid unless all of the following hold: the proof-of-work test of step 1 again; the Merkle root computed from the txids of b.vtxb.\mathrm{vtx}b.vtx equals h.merkleRooth.\mathrm{merkleRoot}h.merkleRoot and the Merkle computation does not report a duplicated-subtree mutation; b.vtxb.\mathrm{vtx}b.vtx is non-empty; 4 ∣b.vtx∣≤4,000,0004\,|b.\mathrm{vtx}| \le 4{,}000{,}0004∣b.vtx∣≤4,000,000; four times the length of the witness-stripped serialization of bbb is at most 4,000,0004{,}000{,}0004,000,000; 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 4,000,0004{,}000{,}0004,000,000; every output value in [0,21⋅1014][0, 21\cdot 10^{14}][0,21⋅1014] with the running total staying in that range; input outpoints pairwise distinct; for a coinbase the first input's scriptSig has length in [2,100][2, 100][2,100], 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 80,00080{,}00080,000.

Contextual block check (contextualCheckBlock), with height H=nextHeight(S)H = \mathrm{nextHeight}(S)H=nextHeight(S) and cutoff c=mtp(S)c = \mathrm{mtp}(S)c=mtp(S) if 419328≤tipHeight(S)+1419328 \le \mathrm{tipHeight}(S) + 1419328≤tipHeight(S)+1 and c=h.timec = h.\mathrm{time}c=h.time otherwise: the outcome is invalid\mathrm{invalid}invalid unless every transaction txtxtx is final (tx.nLockTime=0tx.\mathrm{nLockTime} = 0tx.nLockTime=0, or tx.nLockTime<Htx.\mathrm{nLockTime} < Htx.nLockTime<H when tx.nLockTime<5⋅108tx.\mathrm{nLockTime} < 5\cdot 10^8tx.nLockTime<5⋅108 and tx.nLockTime<ctx.\mathrm{nLockTime} < ctx.nLockTime<c otherwise, or every input has nSequence=232−1\mathrm{nSequence} = 2^{32}-1nSequence=232−1); unless, when 227931≤tipHeight(S)+1227931 \le \mathrm{tipHeight}(S) + 1227931≤tipHeight(S)+1, the canonical script push of HHH is a prefix of the coinbase's first input scriptSig; unless the witness-commitment check passes with "expected" set to 481824≤tipHeight(S)+1481824 \le \mathrm{tipHeight}(S) + 1481824≤tipHeight(S)+1 (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 4,000,0004{,}000{,}0004,000,000.

Ledger connection. Finally connectBlock(S,b)\mathrm{connectBlock}(S, b)connectBlock(S,b) (expanded below) is computed; if it is "none" the outcome is invalid\mathrm{invalid}invalid, and if it is "some (u,undo)(u, \mathit{undo})(u,undo)" the outcome is

accept(⟨S.headers+ ⁣ ⁣+[h], u⟩, undo),\mathrm{accept}\big(\langle S.\mathrm{headers} \mathbin{+\!\!+} [h],\ u\rangle,\ \mathit{undo}\big),accept(⟨S.headers++[h], u⟩, undo),

the header appended at the end of the list and the ledger replaced by uuu.

The ledger connection connectBlock(S,b)\mathrm{connectBlock}(S, b)connectBlock(S,b) returns either "none" or "some (u,undo)(u, \mathit{undo})(u,undo)" with uuu a ledger and undo\mathit{undo}undo a list of lists of coins. Let η=headerHash(b.header)\eta = \mathrm{headerHash}(b.\mathrm{header})η=headerHash(b.header) and H=nextHeight(S)H = \mathrm{nextHeight}(S)H=nextHeight(S).

  • If η=genesisHash\eta = \mathrm{genesisHash}η=genesisHash, the result is "some (S.utxo,[ ])(S.\mathrm{utxo}, [\,])(S.utxo,[])": the ledger is unchanged and the undo data is the empty list, whatever b.vtxb.\mathrm{vtx}b.vtx contains.
  • Else, the BIP30 scan is required when (¬isBIP30Repeat(H,η)∧¬β)∨1983702≤H\big(\neg\mathrm{isBIP30Repeat}(H, \eta) \wedge \neg\beta\big) \vee 1983702 \le H(¬isBIP30Repeat(H,η)∧¬β)∨1983702≤H, where isBIP30Repeat\mathrm{isBIP30Repeat}isBIP30Repeat holds only for (H,η)∈{(91842,a fixed hash),(91880,a fixed hash)}(H, \eta) \in \{(91842, \text{a fixed hash}), (91880, \text{a fixed hash})\}(H,η)∈{(91842,a fixed hash),(91880,a fixed hash)} and β\betaβ holds when S.headersS.\mathrm{headers}S.headers has an entry at index 227931227931227931 whose hash is the fixed BIP34 hash. If the scan is required and some transaction tx∈b.vtxtx \in b.\mathrm{vtx}tx∈b.vtx and some index o<∣tx.vout∣o < |tx.\mathrm{vout}|o<∣tx.vout∣ have getCoin(S.utxo,(txid(tx),o))≠none\mathrm{getCoin}(S.\mathrm{utxo}, (\mathrm{txid}(tx), o)) \neq \text{none}getCoin(S.utxo,(txid(tx),o))=none, the result is "none".
  • Else, with the script flags determined by HHH and by whether η\etaη is one of two fixed exception hashes, the transactions of b.vtxb.\mathrm{vtx}b.vtx are processed in order starting from the accumulator (ledger S.utxo, fees 0, sigops 0, undo [ ])(\text{ledger } S.\mathrm{utxo},\ \text{fees } 0,\ \text{sigops } 0,\ \text{undo } [\,])(ledger S.utxo, fees 0, sigops 0, undo []). For each txtxtx with current ledger www:
    • if txtxtx is a coinbase, fees and undo are unchanged;
    • otherwise checkTxInputs must succeed: every input outpoint has a coin in www; for each input coin ccc in order, it is not the case that c.isCoinbasec.\mathrm{isCoinbase}c.isCoinbase and H−c.height<100H - c.\mathrm{height} < 100H−c.height<100 (truncated subtraction, so a coinbase coin with c.height>Hc.\mathrm{height} > Hc.height>H counts as immature), c.out.nValuec.\mathrm{out}.\mathrm{nValue}c.out.nValue and the running input total are in [0,21⋅1014][0, 21\cdot 10^{14}][0,21⋅1014]; the input total is at least the output total of txtxtx; and the fee (input total minus output total) is in [0,21⋅1014][0, 21\cdot 10^{14}][0,21⋅1014]; then the accumulated fees plus this fee must be in [0,21⋅1014][0, 21\cdot 10^{14}][0,21⋅1014]; the transcribed BIP68 sequence-lock check against HHH, the median-time-past function mtpNat(S,⋅)\mathrm{mtpNat}(S, \cdot)mtpNat(S,⋅), the lock-time flags of HHH, and the heights of the spent coins must pass; and the list txUndo(w,tx)\mathrm{txUndo}(w, tx)txUndo(w,tx) — for each input in order, the coin at its outpoint in www, or the dummy coin ⟨⟨−1,[ ]⟩,0,false⟩\langle\langle -1, [\,]\rangle, 0, \mathrm{false}\rangle⟨⟨−1,[]⟩,0,false⟩ 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 80,00080{,}00080,000;
    • 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 updateCoins(w,tx,H)\mathrm{updateCoins}(w, tx, H)updateCoins(w,tx,H). Any failure yields "none".
  • After the loop, if the output total of the first transaction of bbb (the fixed genesis coinbase if b.vtxb.\mathrm{vtx}b.vtx is empty) exceeds the accumulated fees plus the subsidy at height HHH (namely 50⋅10850 \cdot 10^850⋅108 shifted right by ⌊H/210000⌋\lfloor H / 210000 \rfloor⌊H/210000⌋, and 000 once that quotient is at least 646464), the result is "none"; otherwise it is "some (final ledger, final undo list)".

When the result is "some (u,undo)(u, \mathit{undo})(u,undo)" and η≠genesisHash\eta \neq \mathrm{genesisHash}η=genesisHash, undo\mathit{undo}undo has exactly one entry per non-coinbase transaction of bbb, in block order.

Reachability. Reachable(S)\mathrm{Reachable}(S)Reachable(S) is the least predicate such that the initial state ⟨[genesisHeader],[ ]⟩\langle [\text{genesisHeader}], [\,]\rangle⟨[genesisHeader],[]⟩ is reachable, and whenever Reachable(S)\mathrm{Reachable}(S)Reachable(S) and there exist a block bbb, an integer ttt, a state S′S'S′ and undo data undo\mathit{undo}undo with validate(S,b,t)=accept(S′,undo)\mathrm{validate}(S, b, t) = \mathrm{accept}(S', \mathit{undo})validate(S,b,t)=accept(S′,undo), then Reachable(S′)\mathrm{Reachable}(S')Reachable(S′). The clock reading ttt is unconstrained in each step and may differ from step to step.

The block disconnection disconnectBlock(u,H,η,b,undo)\mathrm{disconnectBlock}(u, H, \eta, b, \mathit{undo})disconnectBlock(u,H,η,b,undo), for a ledger uuu, a natural number HHH, a byte string η\etaη, a block bbb and undo data undo\mathit{undo}undo (a list of lists of coins), returns "none" or "some (u′,clean)(u', \mathit{clean})(u′,clean)" with clean\mathit{clean}clean a Boolean:

  • If ∣undo∣+1≠∣b.vtx∣|\mathit{undo}| + 1 \neq |b.\mathrm{vtx}|∣undo∣+1=∣b.vtx∣, the result is "none".
  • Otherwise let eee (the exception flag) hold exactly when (H,η)(H, \eta)(H,η) is (91722,a fixed hash)(91722, \text{a fixed hash})(91722,a fixed hash) or (91812,a fixed hash)(91812, \text{a fixed hash})(91812,a fixed hash). Pair the transactions of bbb with undo entries so that the first transaction gets "no undo" and the jjj-th transaction (j≥1j \ge 1j≥1) gets the (j−1)(j-1)(j−1)-th entry of undo\mathit{undo}undo, and process these pairs in reverse block order (last transaction first), threading the ledger and conjoining the flags. For one pair (tx,undotx)(tx, \mathit{undo}_{tx})(tx,undotx​) on ledger www, with cbcbcb = "txtxtx is a coinbase":
    • Outputs. For each output ojo_joj​ of txtxtx at index jjj in order: if ojo_joj​'s script is unspendable, nothing happens and the flag for this output is true; otherwise let p=(txid(tx),j)p = (\mathrm{txid}(tx), j)p=(txid(tx),j), let okokok hold when getCoin(w,p)\mathrm{getCoin}(w, p)getCoin(w,p) is some coin ccc with c.out=ojc.\mathrm{out} = o_jc.out=oj​, c.height=Hc.\mathrm{height} = Hc.height=H and c.isCoinbase=cbc.\mathrm{isCoinbase} = cbc.isCoinbase=cb, replace www by spendCoin(w,p)\mathrm{spendCoin}(w, p)spendCoin(w,p), and the flag for this output is ok∨(cb∧e)ok \vee (cb \wedge e)ok∨(cb∧e). The output phase's flag is the conjunction over outputs.
    • Inputs. If undotx\mathit{undo}_{tx}undotx​ is "no undo", the pair yields (w,output flag)(w, \text{output flag})(w,output flag). Otherwise, with undotx\mathit{undo}_{tx}undotx​ a list of coins c1,…,cmc_1, \dots, c_mc1​,…,cm​: if m≠∣tx.vin∣m \neq |tx.\mathrm{vin}|m=∣tx.vin∣ the whole result is "none"; else the inputs are restored last input first: for the input iii paired with coin ccc and outpoint q=i.prevoutq = i.\mathrm{prevout}q=i.prevout, let the per-input flag be "getCoin(w,q)\mathrm{getCoin}(w, q)getCoin(w,q) is none"; if c.height=0c.\mathrm{height} = 0c.height=0 then look for the first entry of www whose outpoint hash equals q.hashq.\mathrm{hash}q.hash — if there is none the whole result is "none", and if there is one with coin c∗c^\astc∗ then replace ccc by ccc with height and coinbase flag copied from c∗c^\astc∗; then replace www by addCoin(w,q,c)\mathrm{addCoin}(w, q, c)addCoin(w,q,c) (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 SSS and TTT, StateEquiv(S,T)\mathrm{StateEquiv}(S, T)StateEquiv(S,T) — written S≈TS \approx TS≈T below — is the proposition

S.headers=T.headers  ∧  ∀p, getCoin(S.utxo,p)=getCoin(T.utxo,p).S.\mathrm{headers} = T.\mathrm{headers} \;\wedge\; \forall p,\ \mathrm{getCoin}(S.\mathrm{utxo}, p) = \mathrm{getCoin}(T.\mathrm{utxo}, p).S.headers=T.headers∧∀p, getCoin(S.utxo,p)=getCoin(T.utxo,p).

The first conjunct is literal equality of the two header lists (same length, same headers at every position). The second is ledger equivalence S.utxo∼T.utxoS.\mathrm{utxo} \sim T.\mathrm{utxo}S.utxo∼T.utxo: 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

connectChain\mathrm{connectChain}connectChain takes a chain state SSS and a list bsbsbs of pairs (b,t)(b, t)(b,t) of a block and an integer clock reading, and returns "none" or "some (T,undos)(T, \mathit{undos})(T,undos)" where TTT is a chain state and undos\mathit{undos}undos is a list of undo data (each undo datum being a list of lists of coins). It is defined by recursion on bsbsbs:

  • connectChain(S,[ ])=some (S,[ ])\mathrm{connectChain}(S, [\,]) = \text{some } (S, [\,])connectChain(S,[])=some (S,[]);
  • connectChain(S,(b,t)::rest)\mathrm{connectChain}(S, (b, t) :: \mathit{rest})connectChain(S,(b,t)::rest): evaluate validate(S,b,t)\mathrm{validate}(S, b, t)validate(S,b,t). If it is accept(S′,undo)\mathrm{accept}(S', \mathit{undo})accept(S′,undo), then evaluate connectChain(S′,rest)\mathrm{connectChain}(S', \mathit{rest})connectChain(S′,rest): if that is "none" the result is "none", and if it is "some (T,undos)(T, \mathit{undos})(T,undos)" the result is "some (T,undo::undos)(T, \mathit{undo} :: \mathit{undos})(T,undo::undos)". If validate(S,b,t)\mathrm{validate}(S, b, t)validate(S,b,t) is invalid\mathrm{invalid}invalid, futureTime\mathrm{futureTime}futureTime or missingPrev\mathrm{missingPrev}missingPrev, the result is "none".

Each block is validated against the state produced by its predecessors with its own clock reading ttt; 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 SSS.

Declaration 3: disconnectTip

disconnectTip(S,b,undo)\mathrm{disconnectTip}(S, b, \mathit{undo})disconnectTip(S,b,undo), for a chain state SSS, a block bbb and undo data undo\mathit{undo}undo, returns "none" or "some (S′,clean)(S', \mathit{clean})(S′,clean)" with clean\mathit{clean}clean a Boolean. It evaluates

disconnectBlock(S.utxo, tipHeight(S), headerHash(b.header), b, undo),\mathrm{disconnectBlock}\big(S.\mathrm{utxo},\ \mathrm{tipHeight}(S),\ \mathrm{headerHash}(b.\mathrm{header}),\ b,\ \mathit{undo}\big),disconnectBlock(S.utxo, tipHeight(S), headerHash(b.header), b, undo),

where tipHeight(S)=∣S.headers∣−1\mathrm{tipHeight}(S) = |S.\mathrm{headers}| - 1tipHeight(S)=∣S.headers∣−1 with truncated subtraction (so 000 for both one and zero headers). If that is "none" the result is "none"; if it is "some (u,clean)(u, \mathit{clean})(u,clean)" the result is "some (⟨dropLast(S.headers), u⟩, clean)(\langle \mathrm{dropLast}(S.\mathrm{headers}),\ u\rangle,\ \mathit{clean})(⟨dropLast(S.headers), u⟩, clean) (where dropLast\mathrm{dropLast}dropLast removes the last element of a list, and is the identity on the empty list)". The hash passed to disconnectBlock\mathrm{disconnectBlock}disconnectBlock is the hash of the given block's header, and the header removed is whatever is last in S.headersS.\mathrm{headers}S.headers; nothing checks that these coincide. Removing the last element of an empty list yields the empty list, so disconnectTip\mathrm{disconnectTip}disconnectTip on a state with no headers can still succeed. The Boolean returned is the flag of disconnectBlock\mathrm{disconnectBlock}disconnectBlock (the conjunction of all per-output and per-input flags described above); the docstring names it "DISCONNECT_OK versus DISCONNECT_UNCLEAN".

Declaration 4: disconnectChain

disconnectChain\mathrm{disconnectChain}disconnectChain takes a chain state SSS and a list of pairs (b,undo)(b, \mathit{undo})(b,undo) of a block and undo data, and returns "none" or "some (T,c)(T, c)(T,c)" with ccc a Boolean, by recursion on the list:

  • disconnectChain(S,[ ])=some (S,true)\mathrm{disconnectChain}(S, [\,]) = \text{some } (S, \mathrm{true})disconnectChain(S,[])=some (S,true);
  • disconnectChain(S,(b,undo)::rest)\mathrm{disconnectChain}(S, (b, \mathit{undo}) :: \mathit{rest})disconnectChain(S,(b,undo)::rest): if disconnectTip(S,b,undo)\mathrm{disconnectTip}(S, b, \mathit{undo})disconnectTip(S,b,undo) is "none" the result is "none"; if it is "some (S′,clean)(S', \mathit{clean})(S′,clean)", then if disconnectChain(S′,rest)\mathrm{disconnectChain}(S', \mathit{rest})disconnectChain(S′,rest) is "none" the result is "none", and if it is "some (T,c)(T, c)(T,c)" the result is "some (T,clean∧c)(T, \mathit{clean} \wedge c)(T,clean∧c)".

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 true\mathrm{true}true for the empty list.

Declaration 5: FreshChain

FreshChain(S,bs)\mathrm{FreshChain}(S, bs)FreshChain(S,bs) is a proposition on a chain state SSS and a list bsbsbs of block–clock pairs, defined by recursion on bsbsbs:

  • FreshChain(S,[ ])\mathrm{FreshChain}(S, [\,])FreshChain(S,[]) is true (no condition on SSS);
  • FreshChain(S,(b,t)::rest)\mathrm{FreshChain}(S, (b, t) :: \mathit{rest})FreshChain(S,(b,t)::rest) is the conjunction of
    1. [txid(tx):tx∈b.vtx][\mathrm{txid}(tx) : tx \in b.\mathrm{vtx}][txid(tx):tx∈b.vtx] has no duplicate entries (so no two transactions of bbb, including the coinbase, have the same txid);
    2. ∀tx∈b.vtx, ∀o∈N, getCoin(S.utxo,(txid(tx),o))=none\forall tx \in b.\mathrm{vtx},\ \forall o \in \mathbb{N},\ \mathrm{getCoin}(S.\mathrm{utxo}, (\mathrm{txid}(tx), o)) = \text{none}∀tx∈b.vtx, ∀o∈N, getCoin(S.utxo,(txid(tx),o))=none — the ledger of SSS has no coin at any outpoint whose hash is a txid of bbb, the index ooo ranging over all natural numbers, not only the indices of actual outputs;
    3. headerHash(b.header)≠genesisHash\mathrm{headerHash}(b.\mathrm{header}) \neq \mathrm{genesisHash}headerHash(b.header)=genesisHash;
    4. ∀S′,∀undo, validate(S,b,t)=accept(S′,undo)→FreshChain(S′,rest)\forall S', \forall \mathit{undo},\ \mathrm{validate}(S, b, t) = \mathrm{accept}(S', \mathit{undo}) \rightarrow \mathrm{FreshChain}(S', \mathit{rest})∀S′,∀undo, validate(S,b,t)=accept(S′,undo)→FreshChain(S′,rest).

Conjunct 4 is vacuously satisfied whenever validate(S,b,t)\mathrm{validate}(S, b, t)validate(S,b,t) is not an acceptance, so FreshChain(S,bs)\mathrm{FreshChain}(S, bs)FreshChain(S,bs) does not by itself imply that any block of bsbsbs 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 connectBlock\mathrm{connectBlock}connectBlock 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

Consistent(S)\mathrm{Consistent}(S)Consistent(S) is the proposition

∃S0, Reachable(S0)∧S≈S0,\exists S_0,\ \mathrm{Reachable}(S_0) \wedge S \approx S_0,∃S0​, Reachable(S0​)∧S≈S0​,

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 SSS and whose ledger is equivalent to that of SSS. In particular every reachable state is consistent (take S0=SS_0 = SS0​=S), and consistency does not constrain the order, duplication or shadowing of entries in S.utxoS.\mathrm{utxo}S.utxo.

Human review
  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me