Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

UpdateCoins creates at most the output value and destroys the input value

Proved
BitcoinSupply.update_bound

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

21-millionbitcoinbitcoin-mainnetconsensusformal-verificationinflationsupplyutxo

For a ledger uuu with distinct keys and non-negative coin values, and a transaction with non-negative outputs, distinct prevouts, and (unless it is a coinbase) every input present in uuu: totalValue (updateCoins u tx H) ≤ totalValue u + valueOut tx − (if coinbase then 0 else valueIn u tx.vin). The inequality (rather than equality) absorbs unspendable outputs, which AddCoin does not store, and overwritten coins.

Preamble
import Definitions.Def_BitcoinSupply
import Definitions.Def_BitcoinSer
open BitcoinSupply BitcoinBlockV2
Formal statement
theorem BitcoinSupply.update_bound (u : Ledger) (tx : BitcoinSer.Tx) (H : Nat) (hnd : BitcoinBlockV2.keysNodup u)
    (hnn : ∀ e ∈ u, 0 ≤ e.2.out.nValue) (hos : ∀ o ∈ tx.vout, 0 ≤ o.nValue)
    (hdup : (tx.vin.map BitcoinSer.TxIn.prevout).Nodup)
    (hin : BitcoinBlockV2.isCoinBase tx = false → ∀ i ∈ tx.vin, BitcoinBlockV2.haveCoin u i.prevout = true) :
    BitcoinSupply.totalValue (BitcoinBlockV2.updateCoins u tx H) ≤
      BitcoinSupply.totalValue u + BitcoinBlockV2.valueOut tx -
        (if BitcoinBlockV2.isCoinBase tx then 0 else BitcoinBlockV2.valueIn u tx.vin) := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: GetBlockSubsidy, ConnectBlock (the coinbase bound), UpdateCoins, src/validation.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/validation.cpp; CheckTxInputs (consensus/tx_verify.cpp); CheckTransaction (consensus/tx_check.cpp); AddCoin, SpendCoin (coins.cpp); MAX_MONEY (consensus/amount.h)
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: BitcoinSupply.update_bound

Objects and notation

A ledger uuu is a finite list of pairs (k,c)(k, c)(k,c): kkk an outpoint (a byte list k.hashk.\mathrm{hash}k.hash and a natural number k.nk.nk.n), ccc a coin (c.out,c.height,c.isCoinbase)(c.\mathrm{out}, c.\mathrm{height}, c.\mathrm{isCoinbase})(c.out,c.height,c.isCoinbase) whose output c.outc.\mathrm{out}c.out has an integer value c.out.nValuec.\mathrm{out}.\mathrm{nValue}c.out.nValue and a byte-list script. A transaction txtxtx has a version ∈N\in \mathbb{N}∈N, a list of inputs tx.vintx.\mathrm{vin}tx.vin (each input iii has an outpoint i.prevouti.\mathrm{prevout}i.prevout, a scriptSig, a sequence number and a witness), a list of outputs tx.vouttx.\mathrm{vout}tx.vout (each output ooo has an integer o.nValueo.\mathrm{nValue}o.nValue and a script), and a lock time.

  • getCoin(u,p)\mathrm{getCoin}(u, p)getCoin(u,p): the coin of the first entry of uuu whose key equals ppp, if any. haveCoin(u,p)\mathrm{haveCoin}(u,p)haveCoin(u,p) is true iff such an entry exists.
  • accessCoin(u,p)\mathrm{accessCoin}(u,p)accessCoin(u,p): that coin if it exists, otherwise the dummy coin whose output has value −1-1−1 (and empty script, height 000, non-coinbase).
  • isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx) is true iff tx.vintx.\mathrm{vin}tx.vin consists of exactly one input and that input's outpoint is the null outpoint (hash === 32 zero bytes and index =232−1= 2^{32}-1=232−1). A transaction with no inputs, or with two or more inputs, is not a coinbase under this definition.
  • 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 (integer sum, 000 for no outputs).
  • 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}.\mathrm{nValue}valueIn(u,ins)=∑i∈ins​accessCoin(u,i.prevout).out.nValue; an input whose outpoint has no entry in uuu contributes −1-1−1.
  • totalValue(u)=∑(k,c)∈uc.out.nValue\mathrm{totalValue}(u) = \sum_{(k,c) \in u} c.\mathrm{out}.\mathrm{nValue}totalValue(u)=∑(k,c)∈u​c.out.nValue, every list entry counted.
  • keysNodup(u)\mathrm{keysNodup}(u)keysNodup(u): the list of keys [k1,…,km][k_1, \dots, k_m][k1​,…,km​] of uuu has no repeated element.
  • txid(tx)\mathrm{txid}(tx)txid(tx): the double SHA-256 of the witness-stripped serialization of txtxtx.
  • A script sss is unspendable iff (sss is non-empty and its first byte is 0x6a0x6a0x6a) or ∣s∣>10,000|s| > 10{,}000∣s∣>10,000.
  • updateCoins(u,tx,H)\mathrm{updateCoins}(u, tx, H)updateCoins(u,tx,H) for H∈NH \in \mathbb{N}H∈N: let u0=uu_0 = uu0​=u if isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx), and otherwise let u0u_0u0​ be uuu with, for each input iii of txtxtx in order, every entry whose key equals i.prevouti.\mathrm{prevout}i.prevout deleted. Then, for the outputs o0,o1,…o_0, o_1, \dotso0​,o1​,… of txtxtx in order with their indices: if ojo_joj​'s script is unspendable the ledger is unchanged; otherwise every entry with key (txid(tx),j)(\mathrm{txid}(tx), j)(txid(tx),j) is deleted and the entry ((txid(tx),j), (oj,H,isCoinBase(tx)))\big((\mathrm{txid}(tx), j),\ (o_j, H, \mathrm{isCoinBase}(tx))\big)((txid(tx),j), (oj​,H,isCoinBase(tx))) is prepended. The result is the ledger after the last output.

Statement

For every ledger uuu, every transaction txtxtx, and every natural number HHH, under the hypotheses

  1. keysNodup(u)\mathrm{keysNodup}(u)keysNodup(u): the keys of uuu are pairwise distinct;
  2. for every entry (k,c)∈u(k,c) \in u(k,c)∈u: 0≤c.out.nValue0 \le c.\mathrm{out}.\mathrm{nValue}0≤c.out.nValue;
  3. for every output o∈tx.vouto \in tx.\mathrm{vout}o∈tx.vout: 0≤o.nValue0 \le o.\mathrm{nValue}0≤o.nValue;
  4. the list of outpoints [ i.prevout:i∈tx.vin ][\,i.\mathrm{prevout} : i \in tx.\mathrm{vin}\,][i.prevout:i∈tx.vin] has no repeated element;
  5. if isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx) is false, then for every input i∈tx.vini \in tx.\mathrm{vin}i∈tx.vin, haveCoin(u,i.prevout)\mathrm{haveCoin}(u, i.\mathrm{prevout})haveCoin(u,i.prevout) is true (some entry of uuu has key i.prevouti.\mathrm{prevout}i.prevout);

the following inequality between integers holds:

totalValue(updateCoins(u,tx,H))  ≤  totalValue(u)+valueOut(tx)−{0if isCoinBase(tx)valueIn(u,tx.vin)otherwise.\mathrm{totalValue}\big(\mathrm{updateCoins}(u, tx, H)\big) \;\le\; \mathrm{totalValue}(u) + \mathrm{valueOut}(tx) - \begin{cases} 0 & \text{if } \mathrm{isCoinBase}(tx) \\ \mathrm{valueIn}(u, tx.\mathrm{vin}) & \text{otherwise.} \end{cases}totalValue(updateCoins(u,tx,H))≤totalValue(u)+valueOut(tx)−{0valueIn(u,tx.vin)​if isCoinBase(tx)otherwise.​

The subtraction is ordinary integer subtraction. The inequality is non-strict.

Edge cases the statement includes

  • HHH only becomes the recorded height of the newly added coins; it is otherwise unconstrained (it may be 000, or unrelated to anything in uuu).
  • txtxtx with no inputs: isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx) is false, hypothesis 5 is vacuous, no entries are deleted, valueIn(u,[])=0\mathrm{valueIn}(u, []) = 0valueIn(u,[])=0, and the claim is \mathrm{totalValue}(\text{uwiththespendableoutputsofwith the spendable outputs ofwiththespendableoutputsoftx added}) \le \mathrm{totalValue}(u) + \mathrm{valueOut}(tx).
  • txtxtx with no outputs: nothing is added; for a non-coinbase the claim is that deleting the spent entries lowers the total by at least valueIn\mathrm{valueIn}valueIn.
  • A coinbase (one null-outpoint input): no deletion, no valueIn\mathrm{valueIn}valueIn term; hypothesis 5 does not apply, and nothing requires uuu to lack an entry at the null outpoint.
  • Outputs with unspendable scripts are counted in valueOut(tx)\mathrm{valueOut}(tx)valueOut(tx) but are never added to the ledger.
  • Outputs of txtxtx whose key (txid(tx),j)(\mathrm{txid}(tx), j)(txid(tx),j) already occurs in uuu replace the existing entry (the old entry is deleted); hypothesis 5 and the BIP30 rule are not part of this statement, so such collisions are allowed here.
  • No upper bound on any value is assumed: values in uuu and in tx.vouttx.\mathrm{vout}tx.vout may exceed MAX_MONEY\mathrm{MAX\_MONEY}MAX_MONEY; only non-negativity is assumed.
  • The hypotheses do not require txtxtx to be well formed in any other way (no script checks, no size checks, no requirement that non-coinbase inputs have non-null outpoints).
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