Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

CheckTxInputs characterized

Proved
BitcoinBlock.checkTxInputs_iff

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

bip30bip34bitcoinbitcoin-mainnetblock-validationconnectblockconsensusformal-verificationundo

checkTxInputs u tx H succeeds iff every input spends an existing coin with value in range that is mature if a coinbase (height+100≤Hheight + 100 \le Hheight+100≤H), the input total is in range, the outputs do not exceed it, and the fee is in range; the returned value is valueIn − valueOut.

Deprecated. Superseded by BitcoinBlockV2.checkTxInputs_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.checkTxInputs_iff (u : Ledger) (tx : BitcoinSer.Tx) (H : Nat) :
    ((∃ fee, BitcoinBlock.checkTxInputs u tx H = some fee) ↔
      (∀ i ∈ tx.vin, ∃ c, BitcoinBlock.getCoin u i.prevout = some c ∧
        (c.isCoinbase = true → c.height + COINBASE_MATURITY ≤ H) ∧ 0 ≤ c.out.nValue ∧ c.out.nValue ≤ MAX_MONEY) ∧
      BitcoinBlock.valueIn u tx.vin ≤ MAX_MONEY ∧ BitcoinBlock.valueOut tx ≤ BitcoinBlock.valueIn u tx.vin ∧
      BitcoinBlock.valueIn u tx.vin - BitcoinBlock.valueOut tx ≤ MAX_MONEY) ∧
    (∀ fee, BitcoinBlock.checkTxInputs u tx H = some fee → fee = BitcoinBlock.feeOf u tx) := 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.checkTxInputs_iff

Binders

  • uuu : a ledger, i.e. a list of pairs (op,c)(\mathit{op}, c)(op,c) where op\mathit{op}op is an outpoint ⟨hash bytes,n∈N⟩\langle \text{hash bytes}, n\in\mathbb{N}\rangle⟨hash bytes,n∈N⟩ and ccc is a coin ⟨out,height,isCoinbase⟩\langle \mathrm{out}, \mathrm{height}, \mathrm{isCoinbase}\rangle⟨out,height,isCoinbase⟩ with out\mathrm{out}out an output (value ∈Z\in\mathbb{Z}∈Z, scriptPubKey), height∈N\mathrm{height}\in\mathbb{N}height∈N, isCoinbase\mathrm{isCoinbase}isCoinbase a Boolean. Keys need not be distinct.
  • txtxtx : a serialized transaction (version, inputs tx.vintx.\mathrm{vin}tx.vin, outputs tx.vouttx.\mathrm{vout}tx.vout, lock time).
  • H∈NH \in \mathbb{N}H∈N : the spend height.

There are no hypotheses.

Conclusion

The conclusion is a conjunction of two parts.

Part 1 (an equivalence):

(∃fee, checkTxInputs(u,tx,H)=some fee)  ⟺  (∀i∈tx.vin, ∃c, getCoin(u,i.prevout)=some c∧(c.isCoinbase=true⇒c.height+100≤H)∧0≤c.out.nValue∧c.out.nValue≤M)∧valueIn(u,tx.vin)≤M∧valueOut(tx)≤valueIn(u,tx.vin)∧valueIn(u,tx.vin)−valueOut(tx)≤M,\big(\exists \mathit{fee},\ \mathrm{checkTxInputs}(u, tx, H) = \mathrm{some}\,\mathit{fee}\big) \iff \Big( \forall i \in tx.\mathrm{vin},\ \exists c,\ \mathrm{getCoin}(u, i.\mathrm{prevout}) = \mathrm{some}\,c \wedge (c.\mathrm{isCoinbase} = \mathrm{true} \Rightarrow c.\mathrm{height} + 100 \le H) \wedge 0 \le c.\mathrm{out.nValue} \wedge c.\mathrm{out.nValue} \le M \Big) \wedge \mathrm{valueIn}(u, tx.\mathrm{vin}) \le M \wedge \mathrm{valueOut}(tx) \le \mathrm{valueIn}(u, tx.\mathrm{vin}) \wedge \mathrm{valueIn}(u, tx.\mathrm{vin}) - \mathrm{valueOut}(tx) \le M,(∃fee, checkTxInputs(u,tx,H)=somefee)⟺(∀i∈tx.vin, ∃c, getCoin(u,i.prevout)=somec∧(c.isCoinbase=true⇒c.height+100≤H)∧0≤c.out.nValue∧c.out.nValue≤M)∧valueIn(u,tx.vin)≤M∧valueOut(tx)≤valueIn(u,tx.vin)∧valueIn(u,tx.vin)−valueOut(tx)≤M,

with M=2 100 000 000 000 000M = 2\,100\,000\,000\,000\,000M=2100000000000000 (MAX_MONEY) and 100100100 = COINBASE_MATURITY.

Part 2 (an implication, for all fees):

∀fee, checkTxInputs(u,tx,H)=some fee⇒fee=feeOf(u,tx).\forall \mathit{fee},\ \mathrm{checkTxInputs}(u,tx,H) = \mathrm{some}\,\mathit{fee} \Rightarrow \mathit{fee} = \mathrm{feeOf}(u, tx).∀fee, checkTxInputs(u,tx,H)=somefee⇒fee=feeOf(u,tx).

Definitions unfolded

  • getCoin(u,op)\mathrm{getCoin}(u, \mathit{op})getCoin(u,op): the coin of the first entry of uuu whose key equals op\mathit{op}op, or none.
  • accessCoin(u,op)\mathrm{accessCoin}(u, \mathit{op})accessCoin(u,op): getCoin(u,op)\mathrm{getCoin}(u,\mathit{op})getCoin(u,op) if present, else the dummy coin ⟨⟨−1,[ ]⟩,0,false⟩\langle \langle -1, [\,]\rangle, 0, \mathrm{false}\rangle⟨⟨−1,[]⟩,0,false⟩ (value −1-1−1).
  • 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.
  • valueIn(u,ins)=∑i∈insaccessCoin(u,i.prevout).out.nValue\mathrm{valueIn}(u, \mathit{ins}) = \sum_{i \in \mathit{ins}} \mathrm{accessCoin}(u, i.\mathrm{prevout}).\mathrm{out.nValue}valueIn(u,ins)=∑i∈ins​accessCoin(u,i.prevout).out.nValue over Z\mathbb{Z}Z (a missing coin contributes −1-1−1).
  • feeOf(u,tx)=valueIn(u,tx.vin)−valueOut(tx)\mathrm{feeOf}(u,tx) = \mathrm{valueIn}(u, tx.\mathrm{vin}) - \mathrm{valueOut}(tx)feeOf(u,tx)=valueIn(u,tx.vin)−valueOut(tx).
  • checkTxInputs(u,tx,H)\mathrm{checkTxInputs}(u,tx,H)checkTxInputs(u,tx,H): if some input's prevout has no coin in uuu, none; otherwise run the input loop over tx.vintx.\mathrm{vin}tx.vin with accumulator 000: for each input, look up its coin (none ⇒\Rightarrow⇒ fail); if the coin is a coinbase and H−c.height<100H - c.\mathrm{height} < 100H−c.height<100 (natural-number subtraction, so 000 when c.height>Hc.\mathrm{height} > Hc.height>H) then fail; let acc′=acc+c.out.nValue\mathit{acc}' = \mathit{acc} + c.\mathrm{out.nValue}acc′=acc+c.out.nValue; if c.out.nValue∉[0,M]c.\mathrm{out.nValue} \notin [0, M]c.out.nValue∈/[0,M] or acc′∉[0,M]\mathit{acc}' \notin [0,M]acc′∈/[0,M] then fail; else continue with acc′\mathit{acc}'acc′. If the loop fails, none. Otherwise with valueIn\mathit{valueIn}valueIn the final accumulator: none if valueIn<valueOut(tx)\mathit{valueIn} < \mathrm{valueOut}(tx)valueIn<valueOut(tx); none if valueIn−valueOut(tx)∉[0,M]\mathit{valueIn} - \mathrm{valueOut}(tx) \notin [0, M]valueIn−valueOut(tx)∈/[0,M]; else some(valueIn−valueOut(tx))\mathrm{some}(\mathit{valueIn} - \mathrm{valueOut}(tx))some(valueIn−valueOut(tx)).

So Part 1 says: the executable check succeeds exactly when every input's prevout is present in uuu with a coin that is mature if coinbase (c.height+100≤Hc.\mathrm{height}+100 \le Hc.height+100≤H) and whose value lies in [0,M][0,M][0,M], the total input value (as computed with the dummy default, which is irrelevant when all coins exist) is at most MMM, the outputs do not exceed the inputs, and the difference is at most MMM. Part 2 says any fee returned equals valueIn−valueOut\mathrm{valueIn} - \mathrm{valueOut}valueIn−valueOut.

Edge cases silently included

Empty tx.vintx.\mathrm{vin}tx.vin (left: loop trivially succeeds with valueIn=0\mathit{valueIn}=0valueIn=0, so success iff valueOut(tx)≤0\mathrm{valueOut}(tx) \le 0valueOut(tx)≤0 and −valueOut(tx)≤M-\mathrm{valueOut}(tx) \le M−valueOut(tx)≤M; right: the universal clause is vacuous and the same three inequalities remain); negative output values are not excluded here, so valueIn−valueOut\mathrm{valueIn} - \mathrm{valueOut}valueIn−valueOut can exceed MMM (hence the last conjunct is not redundant); duplicate keys in uuu (first match wins); coins with c.height>Hc.\mathrm{height} > Hc.height>H (natural subtraction yields 0<1000 < 1000<100, so a coinbase coin from the "future" fails, consistent with c.height+100≤Hc.\mathrm{height}+100 \le Hc.height+100≤H failing); duplicate prevouts within tx.vintx.\mathrm{vin}tx.vin are not excluded and each is counted separately in valueIn\mathrm{valueIn}valueIn.

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