Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

DisconnectBlock undoes ConnectBlock

Proved
BitcoinBlock.disconnect_connect

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

bip30bip34bitcoinbitcoin-mainnetblock-validationconnectblockconsensusformal-verificationundo

For a well-formed state, a block with pairwise distinct txids whose outputs do not pre-exist (the BIP30 condition that BIP34 guarantees on mainnet) and that is not the genesis, if validate S b now = accept S' undo then disconnectBlock S'.utxo height hash b undo = some (u, true) for a ledger uuu with exactly the coins of S.utxo: the undo data restores the previous ledger and the disconnect is clean.

Deprecated. Superseded by BitcoinBlockV2.disconnect_connect (revision 2 of the block mission): the p2shSigOpCount of this revision counted every push of scriptSig instead of only the redeem script, over-counting P2SH sigops; the V2 declarations carry the corrected definition.

Preamble
import Definitions.Def_BitcoinBlock
import Definitions.Def_BitcoinSer
Formal statement
theorem BitcoinBlock.disconnect_connect (S : ChainState) (b : BitcoinSer.Block) (now : Int) (S' : ChainState)
    (undo : BlockUndo) (hwf : BitcoinBlock.WellFormed S) (hnd : (b.vtx.map BitcoinSer.txid).Nodup)
    (hfresh : ∀ tx ∈ b.vtx, ∀ o, BitcoinBlock.getCoin S.utxo ⟨BitcoinSer.txid tx, o⟩ = none)
    (hg : BitcoinSer.headerHash b.header ≠ BitcoinSer.genesisHash)
    (h : BitcoinBlock.validate S b now = .accept S' undo) :
    ∃ u, BitcoinBlock.disconnectBlock S'.utxo S.nextHeight (BitcoinSer.headerHash b.header) b undo = some (u, true) ∧
      BitcoinBlock.Equiv u S.utxo := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: AcceptBlockHeader, CheckBlockHeader, ContextualCheckBlockHeader, CheckBlock, CheckMerkleRoot, CheckWitnessMalleation, ContextualCheckBlock, ConnectBlock, GetBlockScriptFlags, IsBIP30Repeat, IsBIP30Unspendable, UpdateCoins, DisconnectBlock, ApplyTxInUndo, src/validation.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/validation.cpp; CheckTransaction (consensus/tx_check.cpp); IsFinalTx, GetLegacySigOpCount, GetP2SHSigOpCount, GetTransactionSigOpCost, CheckTxInputs (consensus/tx_verify.cpp); CScript::GetSigOpCount, IsUnspendable (script/script.cpp, script.h); CountWitnessSigOps (script/interpreter.cpp); AddCoin, SpendCoin, AddCoins (coins.cpp); GetBlockProof (chain.cpp); GetWitnessCommitmentIndex, GetBlockWeight (consensus/validation.h); CMainParams (kernel/chainparams.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: BitcoinBlock.disconnect_connect

Binders and hypotheses

  • SSS : a chain state ⟨headers,utxo⟩\langle\mathit{headers}, \mathit{utxo}\rangle⟨headers,utxo⟩.
  • bbb : a serialized block (header, transaction list b.vtxb.\mathrm{vtx}b.vtx).
  • now∈Z\mathit{now} \in \mathbb{Z}now∈Z.
  • S′S'S′ : a chain state.
  • undo\mathit{undo}undo : a block undo list (list of lists of coins).
  • Hypothesis hwfh_{wf}hwf​ : WellFormed(S)\mathrm{WellFormed}(S)WellFormed(S): the first header of SSS exists and is the genesis header; the keys (outpoints) of S.utxoS.\mathrm{utxo}S.utxo are pairwise distinct; and every entry (op,c)(\mathit{op}, c)(op,c) of S.utxoS.\mathrm{utxo}S.utxo has 1≤c.height≤∣S.headers∣−11 \le c.\mathrm{height} \le |S.\mathrm{headers}| - 11≤c.height≤∣S.headers∣−1 and c.out.scriptPubKeyc.\mathrm{out.scriptPubKey}c.out.scriptPubKey is not unspendable (does not start with byte 0x6a0x6a0x6a and is at most 10 00010\,00010000 bytes).
  • Hypothesis hndh_{nd}hnd​ : the list [txid(tx)∣tx∈b.vtx][\mathrm{txid}(tx) \mid tx \in b.\mathrm{vtx}][txid(tx)∣tx∈b.vtx] has no duplicates (txid\mathrm{txid}txid = double-SHA256 of the witness-stripped serialization).
  • Hypothesis hfreshh_{fresh}hfresh​ : for every tx∈b.vtxtx \in b.\mathrm{vtx}tx∈b.vtx and every o∈No \in \mathbb{N}o∈N, getCoin(S.utxo,⟨txid(tx),o⟩)=none\mathrm{getCoin}(S.\mathrm{utxo}, \langle\mathrm{txid}(tx), o\rangle) = \mathrm{none}getCoin(S.utxo,⟨txid(tx),o⟩)=none (no outpoint of any transaction of the block, at any index whatsoever, is a key of S.utxoS.\mathrm{utxo}S.utxo).
  • Hypothesis hgh_ghg​ : headerHash(b.header)≠genesisHash\mathrm{headerHash}(b.\mathrm{header}) \ne \mathrm{genesisHash}headerHash(b.header)=genesisHash.
  • Hypothesis hhh : validate(S,b,now)=accept(S′,undo)\mathrm{validate}(S, b, \mathit{now}) = \mathrm{accept}(S', \mathit{undo})validate(S,b,now)=accept(S′,undo).

Conclusion

∃u, disconnectBlock(S′.utxo, ∣S.headers∣, headerHash(b.header), b, undo)=some(u,true)  ∧  Equiv(u,S.utxo),\exists u,\ \mathrm{disconnectBlock}\big(S'.\mathrm{utxo},\ |S.\mathrm{headers}|,\ \mathrm{headerHash}(b.\mathrm{header}),\ b,\ \mathit{undo}\big) = \mathrm{some}(u, \mathrm{true}) \;\wedge\; \mathrm{Equiv}(u, S.\mathrm{utxo}),∃u, disconnectBlock(S′.utxo, ∣S.headers∣, headerHash(b.header), b, undo)=some(u,true)∧Equiv(u,S.utxo),

where Equiv(u,v)\mathrm{Equiv}(u,v)Equiv(u,v) means ∀op, getCoin(u,op)=getCoin(v,op)\forall \mathit{op},\ \mathrm{getCoin}(u,\mathit{op}) = \mathrm{getCoin}(v,\mathit{op})∀op, getCoin(u,op)=getCoin(v,op) (first-match lookup agrees on every outpoint).

Hypothesis hhh, unfolded

validate\mathrm{validate}validate returns accept only when the header is accepted (PoW, parent === tip hash, bits === required bits, time >>> tip median-time-past, time ≤now+7200\le \mathit{now}+7200≤now+7200, version not outdated), checkBlock(b)\mathrm{checkBlock}(b)checkBlock(b) holds, contextualCheckBlock(S,b)\mathrm{contextualCheckBlock}(S,b)contextualCheckBlock(S,b) holds and connectBlock(S,b)=some(u1,undo)\mathrm{connectBlock}(S,b) = \mathrm{some}(u_1, \mathit{undo})connectBlock(S,b)=some(u1​,undo); then S′=⟨S.headers+ ⁣ ⁣+[b.header],u1⟩S' = \langle S.\mathrm{headers} \mathbin{+\!\!+} [b.\mathrm{header}], u_1\rangleS′=⟨S.headers++[b.header],u1​⟩. Under hgh_ghg​ the genesis shortcut of connectBlock\mathrm{connectBlock}connectBlock is not taken, so u1u_1u1​ and undo\mathit{undo}undo come from the transaction loop at height ∣S.headers∣|S.\mathrm{headers}|∣S.headers∣: u1u_1u1​ is S.utxoS.\mathrm{utxo}S.utxo with, for each transaction in order, the prevouts removed (non-coinbase only) and the spendable outputs added at that height with the coinbase flag; undo\mathit{undo}undo has one entry per non-coinbase transaction, in order, each being the list of coins (from accessCoin\mathrm{accessCoin}accessCoin on the running ledger) spent by its inputs.

Conclusion, unfolded

disconnectBlock(v,H,hash,b,undo)\mathrm{disconnectBlock}(v, H, \mathit{hash}, b, \mathit{undo})disconnectBlock(v,H,hash,b,undo): if ∣undo∣+1≠∣b.vtx∣|\mathit{undo}| + 1 \ne |b.\mathrm{vtx}|∣undo∣+1=∣b.vtx∣ then none; otherwise pair the transactions with none::[some c∣c∈undo]\mathrm{none} :: [\mathrm{some}\,c \mid c \in \mathit{undo}]none::[somec∣c∈undo] (the first transaction gets no undo record, the kkk-th transaction gets the (k−1)(k-1)(k−1)-th undo entry), reverse the list, and process it with disconnectTxs(H,exc,v,⋅)\mathrm{disconnectTxs}(H, \mathit{exc}, v, \cdot)disconnectTxs(H,exc,v,⋅) where exc=isBIP30Unspendable(H,hash)\mathit{exc} = \mathrm{isBIP30Unspendable}(H, \mathit{hash})exc=isBIP30Unspendable(H,hash) (true only for the two fixed (height, hash) pairs 917229172291722 and 918129181291812). disconnectTxs\mathrm{disconnectTxs}disconnectTxs handles the pairs in that (reversed) order, failing if any step fails and conjoining the clean flags. One step disconnectTx(v,H,exc,tx,undotx)\mathrm{disconnectTx}(v, H, \mathit{exc}, tx, \mathit{undo}_{tx})disconnectTx(v,H,exc,tx,undotx​): let cb=isCoinBase(tx)cb = \mathrm{isCoinBase}(tx)cb=isCoinBase(tx); first spendOutputs\mathrm{spendOutputs}spendOutputs walks tx.vouttx.\mathrm{vout}tx.vout in forward order with index i=0,1,…i = 0,1,\dotsi=0,1,…: an unspendable output is skipped (clean); otherwise the entry ⟨txid(tx),i⟩\langle\mathrm{txid}(tx), i\rangle⟨txid(tx),i⟩ is removed from the ledger and the step is clean iff that outpoint was present with a coin equal to ⟨tx.vouti,H,cb⟩\langle tx.\mathrm{vout}_i, H, cb\rangle⟨tx.vouti​,H,cb⟩, or (cbcbcb and exc\mathit{exc}exc). Then if undotx\mathit{undo}_{tx}undotx​ is none the result is that ledger and flag; if it is some coins\mathrm{some}\,\mathit{coins}somecoins: fail if ∣coins∣≠∣tx.vin∣|\mathit{coins}| \ne |tx.\mathrm{vin}|∣coins∣=∣tx.vin∣; else restoreInputs\mathrm{restoreInputs}restoreInputs on the zipped (input, coin) list, which recurses on the tail first (so restores the last input first) and for each pair applies applyTxInUndo(⋅,c,i.prevout)\mathrm{applyTxInUndo}(\cdot, c, i.\mathrm{prevout})applyTxInUndo(⋅,c,i.prevout): clean iff the prevout is currently absent; if c.height=0c.\mathrm{height} = 0c.height=0 then look for any entry of the ledger whose key hash equals the prevout hash — if found, take its height and coinbase flag for ccc, if not found fail; then add ccc under the prevout (unspendable scripts are not added; otherwise the new entry replaces an existing one). The final flag is the conjunction of all step flags.

So the conclusion asserts that this disconnection of bbb from S′.utxoS'.\mathrm{utxo}S′.utxo, with the height ∣S.headers∣|S.\mathrm{headers}|∣S.headers∣ and the block's own header hash, succeeds, reports clean === true, and yields a ledger that agrees with S.utxoS.\mathrm{utxo}S.utxo on every lookup.

Edge cases silently included

hfreshh_{fresh}hfresh​ quantifies over all indices ooo, not only existing outputs; the conclusion needs the undo count to match, which under hhh requires exactly one coinbase at the front (ensured by checkBlock\mathrm{checkBlock}checkBlock inside hhh); Equiv\mathrm{Equiv}Equiv compares first-match lookups only (ordering and duplicate shadowed entries are ignored); the exc\mathit{exc}exc path (isBIP30Unspendable\mathrm{isBIP30Unspendable}isBIP30Unspendable) is reachable only at heights 917229172291722/918129181291812 with the fixed hashes; hhh may be unsatisfiable for some SSS, making the claim vacuous; now\mathit{now}now is used only inside hhh; coins with height 000 restored via the "find any entry with the same hash" fallback.

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

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 27, 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