Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

ConnectBlock characterized

Proved
BitcoinBlock.connectBlock_iff

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

bip30bip34bitcoinbitcoin-mainnetblock-validationconnectblockconsensusformal-verificationundo

For a non-empty block with non-negative outputs, connectBlock S b succeeds iff LedgerSpec S b: the genesis shortcut, or the BIP30 freshness where the scan applies, the transaction sequence, and the coinbase value at most the fees plus the specification subsidy (core_eq_spec).

Deprecated. Superseded by BitcoinBlockV2.connectBlock_iff (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.connectBlock_iff (S : ChainState) (b : BitcoinSer.Block) (hne : b.vtx ≠ [])
    (hpos : ∀ tx ∈ b.vtx, 0 ≤ BitcoinBlock.valueOut tx) :
    (∃ r, BitcoinBlock.connectBlock S b = some r) ↔ BitcoinBlock.LedgerSpec S b := 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.connectBlock_iff

Binders and hypotheses

  • SSS : a chain state ⟨headers,utxo⟩\langle \mathit{headers}, \mathit{utxo}\rangle⟨headers,utxo⟩.
  • bbb : a serialized block (header and transaction list b.vtxb.\mathrm{vtx}b.vtx).
  • Hypothesis hneh_{ne}hne​ : b.vtx≠[ ]b.\mathrm{vtx} \ne [\,]b.vtx=[].
  • Hypothesis hposh_{pos}hpos​ : for every transaction txtxtx in b.vtxb.\mathrm{vtx}b.vtx, 0≤valueOut(tx)0 \le \mathrm{valueOut}(tx)0≤valueOut(tx), where valueOut(tx)=∑o∈tx.vouto.nValue\mathrm{valueOut}(tx) = \sum_{o \in tx.\mathrm{vout}} o.\mathrm{nValue}valueOut(tx)=∑o∈tx.vout​o.nValue over Z\mathbb{Z}Z.

Both hypotheses are carried by the statement; neither appears in the conclusion.

Conclusion

(∃r, connectBlock(S,b)=some r)  ⟺  LedgerSpec(S,b).\big(\exists r,\ \mathrm{connectBlock}(S,b) = \mathrm{some}\,r\big) \iff \mathrm{LedgerSpec}(S,b).(∃r, connectBlock(S,b)=somer)⟺LedgerSpec(S,b).

Left side, unfolded

With hash\mathit{hash}hash the double-SHA256 of the serialized header of bbb and height=∣S.headers∣\mathit{height} = |S.\mathrm{headers}|height=∣S.headers∣, connectBlock(S,b)\mathrm{connectBlock}(S,b)connectBlock(S,b) returns some pair (ledger, undo) exactly in these cases:

  • hash\mathit{hash}hash equals the genesis hash constant (result some(S.utxo,[ ])\mathrm{some}(S.\mathrm{utxo},[\,])some(S.utxo,[]) unconditionally); or
  • hash\mathit{hash}hash is not the genesis hash, and not [bip30Checked(S,height,hash)\mathrm{bip30Checked}(S,\mathit{height},\mathit{hash})bip30Checked(S,height,hash) and some output ⟨txid(tx),o⟩\langle\mathrm{txid}(tx), o\rangle⟨txid(tx),o⟩, tx∈b.vtxtx \in b.\mathrm{vtx}tx∈b.vtx, o<∣tx.vout∣o < |tx.\mathrm{vout}|o<∣tx.vout∣, is present in S.utxoS.\mathrm{utxo}S.utxo], and the transaction loop connectLoop(flags,height,mtpNatS,ltf,⟨S.utxo,0,0,[ ]⟩,b.vtx)\mathrm{connectLoop}(\mathit{flags}, \mathit{height}, \mathrm{mtpNat}_S, \mathrm{ltf}, \langle S.\mathrm{utxo}, 0, 0, [\,]\rangle, b.\mathrm{vtx})connectLoop(flags,height,mtpNatS​,ltf,⟨S.utxo,0,0,[]⟩,b.vtx) returns some final state st\mathit{st}st, and valueOut(head(b.vtx))≤st.fees+coreSubsidy(height)\mathrm{valueOut}(\mathrm{head}(b.\mathrm{vtx})) \le \mathit{st}.\mathrm{fees} + \mathrm{coreSubsidy}(\mathit{height})valueOut(head(b.vtx))≤st.fees+coreSubsidy(height).

Here bip30Checked\mathrm{bip30Checked}bip30Checked is (¬isBIP30Repeat(height,hash)∧¬ [header at index 227931 exists and hashes to the BIP34 constant])∨1983702≤height(\neg\mathrm{isBIP30Repeat}(\mathit{height},\mathit{hash}) \wedge \neg\,\text{[header at index } 227931 \text{ exists and hashes to the BIP34 constant]}) \vee 1983702 \le \mathit{height}(¬isBIP30Repeat(height,hash)∧¬[header at index 227931 exists and hashes to the BIP34 constant])∨1983702≤height; flags=blockScriptFlags(height,scriptException(hash))\mathit{flags} = \mathrm{blockScriptFlags}(\mathit{height}, \mathrm{scriptException}(\mathit{hash}))flags=blockScriptFlags(height,scriptException(hash)) (exception table keyed on two fixed hashes, then DERSIG/CLTV/CSV/NULLDUMMY by height thresholds 363725/388381/419328/481824363725/388381/419328/481824363725/388381/419328/481824); mtpNatS(k)=max⁡(0,median of the first 11 of the times of headers 0..k most recent first)\mathrm{mtpNat}_S(k) = \max(0, \text{median of the first } 11 \text{ of the times of headers } 0..k \text{ most recent first})mtpNatS​(k)=max(0,median of the first 11 of the times of headers 0..k most recent first); ltf=1\mathrm{ltf} = 1ltf=1 if height≥419328\mathit{height}\ge 419328height≥419328 else 000; coreSubsidy(height)=0\mathrm{coreSubsidy}(\mathit{height}) = 0coreSubsidy(height)=0 if ⌊height/210000⌋≥64\lfloor \mathit{height}/210000\rfloor \ge 64⌊height/210000⌋≥64, else 5 000 000 0005\,000\,000\,0005000000000 shifted right by ⌊height/210000⌋\lfloor\mathit{height}/210000\rfloor⌊height/210000⌋ bits.

The loop, per transaction txtxtx from ⟨v,fees,sigOps,undo⟩\langle v, \mathit{fees}, \mathit{sigOps}, \mathit{undo}\rangle⟨v,fees,sigOps,undo⟩: if isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx) the fee/undo step is trivial; else checkTxInputs(v,tx,height)\mathrm{checkTxInputs}(v, tx, \mathit{height})checkTxInputs(v,tx,height) must be some fee\mathrm{some}\,\mathit{fee}somefee (all prevouts present; coinbase coins mature: height−c.height≥100\mathit{height} - c.\mathrm{height} \ge 100height−c.height≥100 in natural subtraction; each coin value and running sum in [0,M][0, M][0,M], M=2.1⋅1015M = 2.1\cdot10^{15}M=2.1⋅1015; inputs ≥\ge≥ outputs; difference in [0,M][0,M][0,M]), fees+fee∈[0,M]\mathit{fees}+\mathit{fee} \in [0,M]fees+fee∈[0,M], and sequenceLocksOk(v,height,mtpNatS,ltf,tx)\mathrm{sequenceLocksOk}(v, \mathit{height}, \mathrm{mtpNat}_S, \mathrm{ltf}, tx)sequenceLocksOk(v,height,mtpNatS​,ltf,tx) (the BIP68 core calculation on 32-bit truncations of the version, flags and sequences, with coin heights from accessCoin\mathrm{accessCoin}accessCoin, dummy height 000 if missing); then sigOps+txSigOpCost(flags,v,tx)≤80 000\mathit{sigOps} + \mathrm{txSigOpCost}(\mathit{flags}, v, tx) \le 80\,000sigOps+txSigOpCost(flags,v,tx)≤80000; then (non-coinbase) inputScriptsOk(flags,v,tx)\mathrm{inputScriptsOk}(\mathit{flags}, v, tx)inputScriptsOk(flags,v,tx): for every input index nnn, the full script verification (legacy, P2SH, witness v0 and Taproot paths) of the input's scriptSig, the spent coin's scriptPubKey and the witness succeeds, in the context of txtxtx, nnn, the spent amount and the list of all spent outputs; then continue with updateCoins(v,tx,height)\mathrm{updateCoins}(v, tx, \mathit{height})updateCoins(v,tx,height).

Right side, unfolded

LedgerSpec(S,b)\mathrm{LedgerSpec}(S,b)LedgerSpec(S,b) is: hash=genesis hash\mathit{hash} = \text{genesis hash}hash=genesis hash, or the conjunction of

  1. bip30Checked(S,height,hash)=true⇒∀tx∈b.vtx, ∀o<∣tx.vout∣, getCoin(S.utxo,⟨txid(tx),o⟩)=none\mathrm{bip30Checked}(S,\mathit{height},\mathit{hash}) = \mathrm{true} \Rightarrow \forall tx \in b.\mathrm{vtx},\ \forall o < |tx.\mathrm{vout}|,\ \mathrm{getCoin}(S.\mathrm{utxo}, \langle\mathrm{txid}(tx), o\rangle) = \mathrm{none}bip30Checked(S,height,hash)=true⇒∀tx∈b.vtx, ∀o<∣tx.vout∣, getCoin(S.utxo,⟨txid(tx),o⟩)=none;
  2. TxsSpec(flags,height,mtpNatS,ltf,S.utxo,0,0,b.vtx)\mathrm{TxsSpec}(\mathit{flags}, \mathit{height}, \mathrm{mtpNat}_S, \mathrm{ltf}, S.\mathrm{utxo}, 0, 0, b.\mathrm{vtx})TxsSpec(flags,height,mtpNatS​,ltf,S.utxo,0,0,b.vtx): defined recursively — true for the empty list; for tx::resttx :: \mathit{rest}tx::rest from (v,fees,sigOps)(v, \mathit{fees}, \mathit{sigOps})(v,fees,sigOps): [isCoinBase(tx)=false⇒TxInputsSpec(flags,v,height,mtpNatS,ltf,tx)∧fees+feeOf(v,tx)≤M\mathrm{isCoinBase}(tx) = \mathrm{false} \Rightarrow \mathrm{TxInputsSpec}(\mathit{flags}, v, \mathit{height}, \mathrm{mtpNat}_S, \mathrm{ltf}, tx) \wedge \mathit{fees} + \mathrm{feeOf}(v, tx) \le MisCoinBase(tx)=false⇒TxInputsSpec(flags,v,height,mtpNatS​,ltf,tx)∧fees+feeOf(v,tx)≤M] ∧\wedge∧ sigOps+txSigOpCost(flags,v,tx)≤80 000\mathit{sigOps} + \mathrm{txSigOpCost}(\mathit{flags}, v, tx) \le 80\,000sigOps+txSigOpCost(flags,v,tx)≤80000 ∧\wedge∧ TxsSpec\mathrm{TxsSpec}TxsSpec on rest\mathit{rest}rest from (updateCoins(v,tx,height), fees or fees+feeOf(v,tx) for non-coinbase, sigOps+txSigOpCost(flags,v,tx))(\mathrm{updateCoins}(v,tx,\mathit{height}),\ \mathit{fees} \text{ or } \mathit{fees}+\mathrm{feeOf}(v,tx) \text{ for non-coinbase},\ \mathit{sigOps}+\mathrm{txSigOpCost}(\mathit{flags},v,tx))(updateCoins(v,tx,height), fees or fees+feeOf(v,tx) for non-coinbase, sigOps+txSigOpCost(flags,v,tx)). TxInputsSpec\mathrm{TxInputsSpec}TxInputsSpec requires: every input's prevout has a coin ccc in vvv with (ccc coinbase ⇒c.height+100≤height\Rightarrow c.\mathrm{height}+100 \le \mathit{height}⇒c.height+100≤height) and 0≤c.out.nValue≤M0 \le c.\mathrm{out.nValue} \le M0≤c.out.nValue≤M; valueIn(v,tx.vin)≤M\mathrm{valueIn}(v, tx.\mathrm{vin}) \le MvalueIn(v,tx.vin)≤M; valueOut(tx)≤valueIn(v,tx.vin)\mathrm{valueOut}(tx) \le \mathrm{valueIn}(v,tx.\mathrm{vin})valueOut(tx)≤valueIn(v,tx.vin); the BIP68 specification predicate satisfiesBIP68\mathrm{satisfiesBIP68}satisfiesBIP68 on the same 32-bit truncated inputs (either BIP68 is not enabled — version below 222 or flag bit 000 clear — or every input is disabled (bit 31 set) or satisfies its height/time lock); and for every n<∣tx.vin∣n < |tx.\mathrm{vin}|n<∣tx.vin∣ the full script verification succeeds as in inputScriptsOk\mathrm{inputScriptsOk}inputScriptsOk;
  3. for every cbcbcb among the first one element of b.vtxb.\mathrm{vtx}b.vtx: valueOut(cb)≤totalFees(height,S.utxo,b.vtx)+specSubsidy(height)\mathrm{valueOut}(cb) \le \mathrm{totalFees}(\mathit{height}, S.\mathrm{utxo}, b.\mathrm{vtx}) + \mathrm{specSubsidy}(\mathit{height})valueOut(cb)≤totalFees(height,S.utxo,b.vtx)+specSubsidy(height), where totalFees\mathrm{totalFees}totalFees sums feeOf\mathrm{feeOf}feeOf of each non-coinbase against the running ledger (coinbases contribute 000) and specSubsidy(height)=⌊5 000 000 000/2⌊height/210000⌋⌋\mathrm{specSubsidy}(\mathit{height}) = \lfloor 5\,000\,000\,000 / 2^{\lfloor\mathit{height}/210000\rfloor}\rfloorspecSubsidy(height)=⌊5000000000/2⌊height/210000⌋⌋.

Edge cases silently included

The hypotheses exclude an empty block and negative total outputs but nothing else (no checkBlock\mathrm{checkBlock}checkBlock: coinbase-shaped transactions in later positions, duplicate txids, missing coins defaulting to value −1-1−1 in feeOf\mathrm{feeOf}feeOf/valueIn\mathrm{valueIn}valueIn on the right); genesis-hashed blocks satisfy both sides trivially; coreSubsidy\mathrm{coreSubsidy}coreSubsidy versus specSubsidy\mathrm{specSubsidy}specSubsidy (shift versus floor division, with a hard cut at 646464 halvings on the left); 32-bit truncation of version/sequence values in BIP68; mtpNat\mathrm{mtpNat}mtpNat clamps negative medians to 000; the undo component r.2r.2r.2 is unconstrained.

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