Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Multi-block undo: a connected chain is disconnected back to its starting state

Proved
BitcoinReorg.disconnectChain_connectChain

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

bitcoinbitcoin-mainnetchainstateconsensusformal-verificationreorgreorganizationundoutxo

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

Preamble
import Definitions.Def_BitcoinReorg
import Definitions.Def_BitcoinSer
open BitcoinReorg BitcoinBlockV2
Formal statement
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 sorry
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: BitcoinReorg.disconnectChain_connectChain

Notions used

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.

State equivalence. Two chain states are equivalent, written S≈TS \approx TS≈T (the file's StateEquiv), when

S.headers=T.headersandS.utxo∼T.utxo,S.\mathrm{headers} = T.\mathrm{headers} \quad\text{and}\quad S.\mathrm{utxo} \sim T.\mathrm{utxo},S.headers=T.headersandS.utxo∼T.utxo,

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 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)".

Connecting a chain (the file's connectChain). For a chain state SSS and a list bs=[(b1,t1),…,(bk,tk)]bs = [(b_1, t_1), \dots, (b_k, t_k)]bs=[(b1​,t1​),…,(bk​,tk​)] of pairs of a block and an integer clock reading, connectChain(S,bs)\mathrm{connectChain}(S, bs)connectChain(S,bs) returns "none" or "some (T,[undo1,…,undok])(T, [\mathit{undo}_1, \dots, \mathit{undo}_k])(T,[undo1​,…,undok​])", defined by: for bs=[ ]bs = [\,]bs=[] it is "some (S,[ ])(S, [\,])(S,[])"; for (b,t)::rest(b, t) :: \mathit{rest}(b,t)::rest, if 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 it is "none" if connectChain(S′,rest)\mathrm{connectChain}(S', \mathit{rest})connectChain(S′,rest) is "none" and "some (T,undo::undos)(T, \mathit{undo} :: \mathit{undos})(T,undo::undos)" if that is "some (T,undos)(T, \mathit{undos})(T,undos)"; if validate(S,b,t)\mathrm{validate}(S, b, t)validate(S,b,t) is any other outcome (invalid\mathrm{invalid}invalid, futureTime\mathrm{futureTime}futureTime or missingPrev\mathrm{missingPrev}missingPrev) it is "none". Thus a successful result has exactly one undo entry per block, in order, and TTT is the state after all kkk accepted blocks; for the empty list it is SSS itself.

Disconnecting the tip and a chain (the file's disconnectTip and disconnectChain). disconnectTip(S,b,undo)\mathrm{disconnectTip}(S, b, \mathit{undo})disconnectTip(S,b,undo) computes disconnectBlock(S.utxo,tipHeight(S),headerHash(b.header),b,undo)\mathrm{disconnectBlock}(S.\mathrm{utxo}, \mathrm{tipHeight}(S), \mathrm{headerHash}(b.\mathrm{header}), b, \mathit{undo})disconnectBlock(S.utxo,tipHeight(S),headerHash(b.header),b,undo); if that is "none" the result is "none", and 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)". No comparison is made between b.headerb.\mathrm{header}b.header and the header actually at the tip of SSS; removing the last element of an empty list gives the empty list. disconnectChain(S,[(b1,undo1),…,(bk,undok)])\mathrm{disconnectChain}(S, [(b_1, \mathit{undo}_1), \dots, (b_k, \mathit{undo}_k)])disconnectChain(S,[(b1​,undo1​),…,(bk​,undok​)]) is "some (S,true)(S, \mathrm{true})(S,true)" for the empty list, and otherwise applies disconnectTip\mathrm{disconnectTip}disconnectTip with (b1,undo1)(b_1, \mathit{undo}_1)(b1​,undo1​), 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). FreshChain(S,bs)\mathrm{FreshChain}(S, bs)FreshChain(S,bs) is the proposition defined by: for bs=[ ]bs = [\,]bs=[] it is true; for (b,t)::rest(b, t) :: \mathit{rest}(b,t)::rest it is the conjunction of

  1. the list [txid(tx):tx∈b.vtx][\mathrm{txid}(tx) : tx \in b.\mathrm{vtx}][txid(tx):tx∈b.vtx] has no duplicates;
  2. for every transaction tx∈b.vtxtx \in b.\mathrm{vtx}tx∈b.vtx and every natural number ooo (not only o<∣tx.vout∣o < |tx.\mathrm{vout}|o<∣tx.vout∣), getCoin(S.utxo,(txid(tx),o))=none\mathrm{getCoin}(S.\mathrm{utxo}, (\mathrm{txid}(tx), o)) = \text{none}getCoin(S.utxo,(txid(tx),o))=none;
  3. headerHash(b.header)≠genesisHash\mathrm{headerHash}(b.\mathrm{header}) \neq \mathrm{genesisHash}headerHash(b.header)=genesisHash;
  4. for every state S′S'S′ and undo data undo\mathit{undo}undo such that validate(S,b,t)=accept(S′,undo)\mathrm{validate}(S, b, t) = \mathrm{accept}(S', \mathit{undo})validate(S,b,t)=accept(S′,undo), FreshChain(S′,rest)\mathrm{FreshChain}(S', \mathit{rest})FreshChain(S′,rest).

Conjunct 4 is vacuously true when validate(S,b,t)\mathrm{validate}(S, b, t)validate(S,b,t) is not an acceptance; since acceptance determines S′S'S′ and undo\mathit{undo}undo uniquely, when it is an acceptance conjunct 4 is just FreshChain\mathrm{FreshChain}FreshChain of the accepted state and the remaining list.

Statement

Binders and hypotheses. A list bs=[(b1,t1),…,(bk,tk)]bs = [(b_1, t_1), \dots, (b_k, t_k)]bs=[(b1​,t1​),…,(bk​,tk​)] of block–clock pairs; then, universally, a chain state SSS with Reachable(S)\mathrm{Reachable}(S)Reachable(S) and FreshChain(S,bs)\mathrm{FreshChain}(S, bs)FreshChain(S,bs); then, universally, a chain state TTT and a list undos\mathit{undos}undos of undo data with

connectChain(S,bs)=some (T,undos).\mathrm{connectChain}(S, bs) = \text{some } (T, \mathit{undos}).connectChain(S,bs)=some (T,undos).

Under the last hypothesis undos=[undo1,…,undok]\mathit{undos} = [\mathit{undo}_1, \dots, \mathit{undo}_k]undos=[undo1​,…,undok​] has the same length as bsbsbs, each block was accepted by validate\mathrm{validate}validate on the state its predecessors produced, and T.headers=S.headers+ ⁣ ⁣+[b1.header,…,bk.header]T.\mathrm{headers} = S.\mathrm{headers} \mathbin{+\!\!+} [b_1.\mathrm{header}, \dots, b_k.\mathrm{header}]T.headers=S.headers++[b1​.header,…,bk​.header].

Conclusion. There exists a chain state S′S'S′ such that

disconnectChain(T, [(bk,undok),…,(b1,undo1)])=some (S′,true)andS′≈S.\mathrm{disconnectChain}\Big(T,\ \big[(b_k, \mathit{undo}_k), \dots, (b_1, \mathit{undo}_1)\big]\Big) = \text{some } (S', \mathrm{true}) \quad\text{and}\quad S' \approx S.disconnectChain(T, [(bk​,undok​),…,(b1​,undo1​)])=some (S′,true)andS′≈S.

The list passed to disconnectChain\mathrm{disconnectChain}disconnectChain is the pairing of the blocks of bsbsbs (the clock readings dropped) with the entries of undos\mathit{undos}undos, position by position, in reverse order — so the last connected block is disconnected first, each from the state the previous disconnection produced, using tipHeight\mathrm{tipHeight}tipHeight of the current state as the height and the block's own header hash. The flag true\mathrm{true}true means every one of the kkk disconnections returned the flag true\mathrm{true}true (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-000 undo coin lacked a same-hash entry to borrow from). S′≈SS' \approx SS′≈S means S′S'S′ has exactly the header list of SSS and a ledger equivalent to S.utxoS.\mathrm{utxo}S.utxo under first-match lookup.

Edge cases the statement includes. For bs=[ ]bs = [\,]bs=[]: T=ST = ST=S, undos=[ ]\mathit{undos} = [\,]undos=[], the pairing is empty, disconnectChain(S,[ ])=some (S,true)\mathrm{disconnectChain}(S, [\,]) = \text{some } (S, \mathrm{true})disconnectChain(S,[])=some (S,true), and S′=SS' = SS′=S. If bsbsbs has a block whose validation on its predecessor state is not an acceptance, the hypothesis connectChain(S,bs)=some(… )\mathrm{connectChain}(S, bs) = \text{some}(\dots)connectChain(S,bs)=some(…) is false and the statement is vacuous for that bsbsbs. Pairing by position (zip) truncates to the shorter list, but under the hypotheses both lists have length kkk. FreshChain\mathrm{FreshChain}FreshChain excludes genesis-hash blocks, so no block takes the shortcut that returns empty undo data.

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