Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Disconnect undoes connect, from any equivalent ledger

Proved
BitcoinReorg.disconnect_connect_equiv

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

bitcoinbitcoin-mainnetchainstateconsensusformal-verificationreorgreorganizationundoutxo

The block mission's disconnect_connect for any ledger with the same coins as the accepted state's: under its hypotheses (well-formed state, distinct and fresh txids, not the genesis hash), disconnectBlock on that ledger with the recorded undo data succeeds cleanly and yields a ledger equivalent to the state before the block.

Preamble
import Definitions.Def_BitcoinReorg
import Definitions.Def_BitcoinSer
open BitcoinReorg BitcoinBlockV2
Formal statement
theorem BitcoinReorg.disconnect_connect_equiv (S : ChainState) (b : BitcoinSer.Block) (now : Int) (S' : ChainState)
    (undo : BlockUndo) (hwf : BitcoinBlockV2.WellFormed S) (hnd : (b.vtx.map BitcoinSer.txid).Nodup)
    (hfresh : ∀ tx ∈ b.vtx, ∀ o, BitcoinBlockV2.getCoin S.utxo ⟨BitcoinSer.txid tx, o⟩ = none)
    (hg : BitcoinSer.headerHash b.header ≠ BitcoinSer.genesisHash)
    (h : BitcoinBlockV2.validate S b now = .accept S' undo) (v : Ledger) (hv : BitcoinBlockV2.Equiv v S'.utxo) :
    ∃ u, BitcoinBlockV2.disconnectBlock v S.nextHeight (BitcoinSer.headerHash b.header) b undo = some (u, true) ∧
      BitcoinBlockV2.Equiv u S.utxo := 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.disconnect_connect_equiv

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.

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.

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

Well-formedness. WellFormed(S)\mathrm{WellFormed}(S)WellFormed(S) is the conjunction of: the first element of S.headersS.\mathrm{headers}S.headers exists and is the fixed genesis header; the outpoints [p:(p,c)∈S.utxo][p : (p, c) \in S.\mathrm{utxo}][p:(p,c)∈S.utxo] are pairwise distinct; and for every pair (p,c)(p, c)(p,c) in S.utxoS.\mathrm{utxo}S.utxo, 1≤c.height≤tipHeight(S)1 \le c.\mathrm{height} \le \mathrm{tipHeight}(S)1≤c.height≤tipHeight(S) and c.out.scriptPubKeyc.\mathrm{out}.\mathrm{scriptPubKey}c.out.scriptPubKey is not unspendable.

Statement

Binders and hypotheses.

  • A chain state SSS, a block bbb, an integer clock reading ttt (now), a chain state S′S'S′ and undo data undo\mathit{undo}undo (a list of lists of coins).
  • hwf:WellFormed(S)\mathit{hwf} : \mathrm{WellFormed}(S)hwf:WellFormed(S) — the first header of SSS is the genesis header, the outpoints of S.utxoS.\mathrm{utxo}S.utxo are pairwise distinct, and every coin in S.utxoS.\mathrm{utxo}S.utxo has height in [1,tipHeight(S)][1, \mathrm{tipHeight}(S)][1,tipHeight(S)] and a script that is not unspendable. (Nothing says SSS is reachable.)
  • hnd\mathit{hnd}hnd : the list [txid(tx):tx∈b.vtx][\mathrm{txid}(tx) : tx \in b.\mathrm{vtx}][txid(tx):tx∈b.vtx] has no duplicates.
  • hfresh\mathit{hfresh}hfresh : ∀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 — no coin of SSS sits at any outpoint whose hash is a txid of bbb, for every natural-number index, not only indices of actual outputs.
  • hg\mathit{hg}hg : headerHash(b.header)≠genesisHash\mathrm{headerHash}(b.\mathrm{header}) \neq \mathrm{genesisHash}headerHash(b.header)=genesisHash.
  • hhh : validate(S,b,t)=accept(S′,undo)\mathrm{validate}(S, b, t) = \mathrm{accept}(S', \mathit{undo})validate(S,b,t)=accept(S′,undo) — the full validation path (header tests, context-free and contextual block checks, and connectBlock\mathrm{connectBlock}connectBlock) accepts bbb on SSS with clock ttt, producing S′=⟨S.headers+ ⁣ ⁣+[b.header], u′⟩S' = \langle S.\mathrm{headers} \mathbin{+\!\!+} [b.\mathrm{header}],\ u'\rangleS′=⟨S.headers++[b.header], u′⟩ where connectBlock(S,b)=some (u′,undo)\mathrm{connectBlock}(S, b) = \text{some } (u', \mathit{undo})connectBlock(S,b)=some (u′,undo).
  • A ledger vvv and hv:v∼S′.utxo\mathit{hv} : v \sim S'.\mathrm{utxo}hv:v∼S′.utxo — vvv agrees with the accepted state's ledger at every outpoint under first-match lookup (its order, duplicates and shadowed entries are unconstrained).

Conclusion. There exists a ledger uuu such that

disconnectBlock(v, nextHeight(S), headerHash(b.header), b, undo)=some (u,true)andu∼S.utxo.\mathrm{disconnectBlock}\big(v,\ \mathrm{nextHeight}(S),\ \mathrm{headerHash}(b.\mathrm{header}),\ b,\ \mathit{undo}\big) = \text{some } (u, \mathrm{true}) \quad\text{and}\quad u \sim S.\mathrm{utxo}.disconnectBlock(v, nextHeight(S), headerHash(b.header), b, undo)=some (u,true)andu∼S.utxo.

That is: disconnecting bbb from vvv — at height ∣S.headers∣|S.\mathrm{headers}|∣S.headers∣ (the height at which bbb was connected), with bbb's own header hash, and with the undo data that the acceptance produced — does not fail, returns the flag true\mathrm{true}true (every spent output of bbb was found in vvv with exactly the recorded output, the height ∣S.headers∣|S.\mathrm{headers}|∣S.headers∣ and the right coinbase flag, or was unspendable; every restored input was absent from the ledger at the moment of restoration; no restored coin with height 000 lacked a same-hash entry to borrow from), and yields a ledger equivalent to the ledger SSS had before bbb was connected.

Edge cases the statement includes. The height passed to disconnectBlock\mathrm{disconnectBlock}disconnectBlock is nextHeight(S)=∣S.headers∣\mathrm{nextHeight}(S) = |S.\mathrm{headers}|nextHeight(S)=∣S.headers∣, which equals tipHeight(S′)\mathrm{tipHeight}(S')tipHeight(S′) because S′S'S′ has one more header. The exception flag of disconnectBlock\mathrm{disconnectBlock}disconnectBlock is set only when that height is 917229172291722 or 918129181291812 and the header hash is the corresponding fixed constant. Because hhh is an acceptance and hg\mathit{hg}hg excludes the genesis shortcut, undo\mathit{undo}undo has one entry per non-coinbase transaction of bbb, so the length test ∣undo∣+1=∣b.vtx∣|\mathit{undo}| + 1 = |b.\mathrm{vtx}|∣undo∣+1=∣b.vtx∣ is met. The hypotheses are jointly satisfiable only if some block is actually accepted on a well-formed state; if, for a given SSS, no bbb and ttt yield acceptance, the statement is vacuous for that SSS.

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