Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

ConnectBlock respects ledger equivalence

Proved
BitcoinReorg.connectBlock_equiv

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

bitcoinbitcoin-mainnetchainstateconsensusformal-verificationreorgreorganizationundoutxo

For two states with the same headers and equivalent ledgers, connectBlock on the same block either fails on both or succeeds on both with equivalent ledgers and the same undo data. Every ledger read of the transaction loop — CheckTxInputs, SequenceLocks, the sigop cost, CheckInputScripts, the undo record, the BIP30 scan — goes through getCoin.

Preamble
import Definitions.Def_BitcoinReorg
import Definitions.Def_BitcoinSer
open BitcoinReorg BitcoinBlockV2
Formal statement
theorem BitcoinReorg.connectBlock_equiv (H : List BitcoinSer.Header) (u v : Ledger) (h : BitcoinBlockV2.Equiv u v)
    (b : BitcoinSer.Block) :
    (BitcoinBlockV2.connectBlock ⟨H, u⟩ b = none ∧ BitcoinBlockV2.connectBlock ⟨H, v⟩ b = none) ∨
    (∃ u' v' undo, BitcoinBlockV2.connectBlock ⟨H, u⟩ b = some (u', undo) ∧
      BitcoinBlockV2.connectBlock ⟨H, v⟩ b = some (v', undo) ∧ BitcoinBlockV2.Equiv u' v') := 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.connectBlock_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 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.

Statement

Binders. A list of headers H\mathcal HH; two ledgers uuu and vvv; a hypothesis h:u∼vh : u \sim vh:u∼v (∀p, getCoin(u,p)=getCoin(v,p)\forall p,\ \mathrm{getCoin}(u, p) = \mathrm{getCoin}(v, p)∀p, getCoin(u,p)=getCoin(v,p)); and a block bbb. The two chain states considered are ⟨H,u⟩\langle \mathcal H, u\rangle⟨H,u⟩ and ⟨H,v⟩\langle \mathcal H, v\rangle⟨H,v⟩: the same header list with the two ledgers. No condition is placed on H\mathcal HH (it may be empty, need not start with the genesis header), on bbb (it need not pass any header or block check — only connectBlock\mathrm{connectBlock}connectBlock is applied, not validate\mathrm{validate}validate), or on uuu, vvv beyond equivalence.

Conclusion. Exactly one of the following two alternatives is asserted to hold (as a disjunction):

  1. connectBlock(⟨H,u⟩,b)=none\mathrm{connectBlock}(\langle \mathcal H, u\rangle, b) = \text{none}connectBlock(⟨H,u⟩,b)=none and connectBlock(⟨H,v⟩,b)=none\mathrm{connectBlock}(\langle \mathcal H, v\rangle, b) = \text{none}connectBlock(⟨H,v⟩,b)=none; or
  2. there exist ledgers u′u'u′, v′v'v′ and undo data undo\mathit{undo}undo (a list of lists of coins) such that
connectBlock(⟨H,u⟩,b)=some (u′,undo),connectBlock(⟨H,v⟩,b)=some (v′,undo),u′∼v′.\mathrm{connectBlock}(\langle \mathcal H, u\rangle, b) = \text{some } (u', \mathit{undo}),\quad \mathrm{connectBlock}(\langle \mathcal H, v\rangle, b) = \text{some } (v', \mathit{undo}),\quad u' \sim v'.connectBlock(⟨H,u⟩,b)=some (u′,undo),connectBlock(⟨H,v⟩,b)=some (v′,undo),u′∼v′.

In alternative 2 the undo data is literally the same list on both sides (so, since each undo entry is the list of coins read by first-match lookup at the inputs' outpoints — or the dummy coin ⟨⟨−1,[ ]⟩,0,false⟩\langle\langle -1, [\,]\rangle, 0, \mathrm{false}\rangle⟨⟨−1,[]⟩,0,false⟩ where absent — those lookups agree), and the resulting ledgers are only asserted equivalent, not equal.

Edge cases the statement includes. If headerHash(b.header)=genesisHash\mathrm{headerHash}(b.\mathrm{header}) = \mathrm{genesisHash}headerHash(b.header)=genesisHash, connectBlock\mathrm{connectBlock}connectBlock returns "some (u,[ ])(u, [\,])(u,[])" and "some (v,[ ])(v, [\,])(v,[])" respectively, and alternative 2 holds with u′=uu' = uu′=u, v′=vv' = vv′=v. If b.vtxb.\mathrm{vtx}b.vtx is empty, the loop does nothing and the coinbase bound is checked against the fixed genesis coinbase's output value 5⋅1095\cdot 10^95⋅109 versus 0+subsidy(∣H∣)0 + \text{subsidy}(|\mathcal H|)0+subsidy(∣H∣). The height used throughout is ∣H∣|\mathcal H|∣H∣ and the BIP30 ancestor test consults H\mathcal HH at index 227931227931227931; the median-time-past function used by the sequence-lock check is derived from H\mathcal HH alone. The statement does not say which alternative holds for a given input, only that one does.

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