Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

UTXO set, transaction checks, and block value accounting

Definition
BitcoinUtxo

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

bitcoinbitcoin-mainnetconsensusformal-verificationutxovalue-conservation

Amounts are integers in satoshi, COIN=108\mathrm{COIN} = 10^{8}COIN=108, MAX_MONEY=2.1×1015\mathrm{MAX\_MONEY} = 2.1 \times 10^{15}MAX_MONEY=2.1×1015, and moneyRange(v)  ⟺  0≤v≤MAX_MONEY\mathrm{moneyRange}(v) \iff 0 \le v \le \mathrm{MAX\_MONEY}moneyRange(v)⟺0≤v≤MAX_MONEY; COINBASE_MATURITY=100\mathrm{COINBASE\_MATURITY} = 100COINBASE_MATURITY=100. Transaction ids form an arbitrary type TTT with decidable equality.

Data. An outpoint is a pair (txid, index). An output carries a value and an unspendable bit, standing for scriptPubKey.IsUnspendable(). A coin is an output with its creation height and coinbase flag. A transaction has a txid, input outpoints, outputs, and a coinbase flag standing for IsCoinBase(). The UTXO set is a list of (outpoint, coin) entries; keysNodup says the outpoints are pairwise distinct.

View operations. getCoin looks up an outpoint; haveCoin tests presence; spendCoin removes the entry; addCoin does nothing for an unspendable output and otherwise inserts the entry in place of any entry with the same outpoint; addCoinsFrom adds outputs i,i+1,…i, i+1, \dotsi,i+1,… of a transaction; spendInputs spends a list of outpoints; updateCoins spends the inputs (unless coinbase) and adds the outputs, as UpdateCoins.

Values. sumValues sums output values; valueOut is GetValueOut(); valueIn sums the values of the coins at a list of outpoints (zero for a missing coin); totalValue sums the values held in the set.

Checks. outputsLoop is the output loop of CheckTransaction: each value non-negative and at most MAX_MONEY, the running total in range. checkTransaction requires non-empty inputs and outputs, the output loop, and pairwise distinct inputs. haveInputs is HaveInputs. inputsLoop is the input loop of CheckTxInputs: each input present, a coinbase coin mature (spend height minus coin height at least 100), each value and the running nValueIn in range. checkTxInputs then requires nValueIn≥valueOut\mathrm{nValueIn} \ge \mathrm{valueOut}nValueIn≥valueOut and returns the fee nValueIn−valueOut\mathrm{nValueIn} - \mathrm{valueOut}nValueIn−valueOut if in range.

Blocks. bip30Ok is the BIP30 pre-check: no output of any transaction of the block already exists in the view. checkBlockTxs requires the first transaction to be a coinbase, the others not, all passing checkTransaction. connectLoop processes the transactions in order: a non-coinbase must pass checkTxInputs, its fee is added to nFees which must stay in range, then updateCoins. connectBlocks_ss​ runs the structural check, the BIP30 check, the loop, and the coinbase bound valueOut(coinbase)≤nFees+s(height)\mathrm{valueOut}(\text{coinbase}) \le \mathrm{nFees} + s(\text{height})valueOut(coinbase)≤nFees+s(height) for a subsidy function sss. connectChains_ss​ connects a list of blocks at consecutive heights. subsidySums(h,n)=∑i<ns(h+i)_s(h, n) = \sum_{i<n} s(h+i)s​(h,n)=∑i<n​s(h+i).

These definitions fix the value-accounting semantics of block connection for the conservation theorems.

Formalization Note. Heights are Nat and the maturity test uses truncated subtraction, which rejects a spend below the coin's height as the signed source does. fEnforceBIP30 is fixed to enforced. Size, script-length, null-prevout and script-validity rules are not modeled. Only Std is imported.

Definition code
import Std

namespace BitcoinUtxo

/-! Transcription of the value-accounting rules of Bitcoin Core at revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`: `CheckTransaction` (`consensus/tx_check.cpp`),
`Consensus::CheckTxInputs` (`consensus/tx_verify.cpp`), `CCoinsViewCache::AddCoin` / `SpendCoin`,
`AddCoins`, `HaveInputs` (`coins.cpp`), `UpdateCoins`, the BIP30 pre-check and the fee / coinbase
accounting of `Chainstate::ConnectBlock` (`validation.cpp`), with `COIN`, `MAX_MONEY`, `MoneyRange`
(`consensus/amount.h`) and `COINBASE_MATURITY` (`consensus/consensus.h`).

Transaction ids are an arbitrary type `T` with decidable equality. Amounts are `Int`, as `CAmount`
is a signed 64-bit integer whose sign the checks test explicitly. Scripts are abstracted to the one
bit the accounting reads: whether an output's `scriptPubKey.IsUnspendable()`, in which case
`AddCoin` does not add it to the UTXO set. The UTXO set is a list of `(outpoint, coin)` entries
with pairwise distinct outpoints, standing for the map `cacheCoins`. -/

variable {T : Type} [DecidableEq T]

/-- `consensus/amount.h`: `COIN{100'000'000}`. -/
def COIN : Int := 100000000

/-- `consensus/amount.h`: `MAX_MONEY{21'000'000 * COIN}`. -/
def MAX_MONEY : Int := 21000000 * COIN

/-- `consensus/amount.h`: `MoneyRange(nValue) = (nValue >= 0 && nValue <= MAX_MONEY)`. -/
def moneyRange (v : Int) : Bool := decide (0 ≤ v ∧ v ≤ MAX_MONEY)

/-- `consensus/consensus.h`: `COINBASE_MATURITY = 100`. -/
def COINBASE_MATURITY : Nat := 100

/-- `COutPoint`: a transaction id and an output index. -/
structure OutPoint (T : Type) where
  txid : T
  n : Nat
  deriving DecidableEq

/-- `CTxOut`, reduced to its value and to `scriptPubKey.IsUnspendable()`. -/
structure TxOut where
  value : Int
  unspendable : Bool
  deriving DecidableEq

/-- `Coin`: an unspent output with its creation height and coinbase flag. -/
structure Coin where
  out : TxOut
  height : Nat
  isCoinbase : Bool
  deriving DecidableEq

/-- `CTransaction`, reduced to what the accounting reads. `isCoinbase` stands for
`IsCoinBase()`, i.e. a single null previous outpoint, which `CheckBlock` requires of the first
transaction of a block and forbids for the others. -/
structure Tx (T : Type) where
  txid : T
  vin : List (OutPoint T)
  vout : List TxOut
  isCoinbase : Bool

/-- The UTXO set: `(outpoint, coin)` entries, meant to have pairwise distinct outpoints. -/
abbrev UtxoSet (T : Type) := List (OutPoint T × Coin)

/-- The entry for an outpoint, if present. -/
def getCoin : UtxoSet T → OutPoint T → Option Coin
  | [], _ => none
  | (k, c) :: rest, op => if k = op then some c else getCoin rest op

/-- `HaveCoin`. -/
def haveCoin (u : UtxoSet T) (op : OutPoint T) : Bool := (getCoin u op).isSome

/-- The outpoints are pairwise distinct. -/
def keysNodup (u : UtxoSet T) : Prop := (u.map Prod.fst).Nodup

/-- `SpendCoin`: remove the entry for the outpoint. -/
def spendCoin : UtxoSet T → OutPoint T → UtxoSet T
  | [], _ => []
  | (k, c) :: rest, op => if k = op then spendCoin rest op else (k, c) :: spendCoin rest op

/-- `AddCoin`: an unspendable output is not added; otherwise the entry replaces any entry with the
same outpoint (`possible_overwrite`); the BIP30 check of `ConnectBlock` is what rules out a live
entry being overwritten. -/
def addCoin (u : UtxoSet T) (op : OutPoint T) (c : Coin) : UtxoSet T :=
  if c.out.unspendable then u else (op, c) :: spendCoin u op

/-- `AddCoins`: add the outputs `vout[i]` at outpoints `(txid, i)`, starting from index `i`. -/
def addCoinsFrom (txid : T) (height : Nat) (cb : Bool) : UtxoSet T → Nat → List TxOut → UtxoSet T
  | u, _, [] => u
  | u, i, o :: rest => addCoinsFrom txid height cb (addCoin u ⟨txid, i⟩ ⟨o, height, cb⟩) (i + 1) rest

/-- `SpendCoin` on every input. -/
def spendInputs : UtxoSet T → List (OutPoint T) → UtxoSet T
  | u, [] => u
  | u, op :: rest => spendInputs (spendCoin u op) rest

/-- `UpdateCoins`: mark the inputs spent (not for a coinbase), then add the outputs. -/
def updateCoins (u : UtxoSet T) (tx : Tx T) (height : Nat) : UtxoSet T :=
  addCoinsFrom tx.txid height tx.isCoinbase (if tx.isCoinbase then u else spendInputs u tx.vin) 0 tx.vout

/-- The output-value loop of `CheckTransaction`: each value non-negative, at most `MAX_MONEY`, and
the running total in range; returns the total. -/
def outputsLoop : List TxOut → Int → Option Int
  | [], acc => some acc
  | o :: rest, acc =>
    if o.value < 0 then none
    else if MAX_MONEY < o.value then none
    else if !moneyRange (acc + o.value) then none
    else outputsLoop rest (acc + o.value)

/-- The sum of a list of output values. -/
def sumValues : List TxOut → Int
  | [] => 0
  | o :: rest => o.value + sumValues rest

/-- `CTransaction::GetValueOut()`: the sum of the output values. -/
def valueOut (tx : Tx T) : Int := sumValues tx.vout

/-- `nValueIn`: the sum of the values of the coins at the given outpoints (zero for a missing coin). -/
def valueIn (u : UtxoSet T) : List (OutPoint T) → Int
  | [] => 0
  | op :: rest => (match getCoin u op with | none => 0 | some c => c.out.value) + valueIn u rest

/-- `CheckTransaction`, restricted to the context-free rules that concern values and inputs:
non-empty inputs and outputs, the output-value loop, and no duplicate inputs (CVE-2018-17144).
The serialized-size bound, the coinbase script-length bound and the null-prevout test concern
serialization and scripts and are outside this file. -/
def checkTransaction (tx : Tx T) : Bool :=
  !tx.vin.isEmpty && !tx.vout.isEmpty && (outputsLoop tx.vout 0).isSome &&
    decide (tx.vin.Nodup)

/-- `HaveInputs`. -/
def haveInputs (u : UtxoSet T) (tx : Tx T) : Bool :=
  tx.isCoinbase || tx.vin.all fun op => haveCoin u op

/-- The input loop of `CheckTxInputs`: for each input, the coin must exist, a coinbase coin must
be mature (`nSpendHeight - coin.nHeight >= COINBASE_MATURITY`), and the coin value and the running
total must be in `MoneyRange`; returns `nValueIn`. -/
def inputsLoop (u : UtxoSet T) (spendHeight : Nat) : List (OutPoint T) → Int → Option Int
  | [], acc => some acc
  | op :: rest, acc =>
    match getCoin u op with
    | none => none
    | some coin =>
      if coin.isCoinbase && decide (spendHeight - coin.height < COINBASE_MATURITY) then none
      else
        let acc' := acc + coin.out.value
        if !moneyRange coin.out.value || !moneyRange acc' then none
        else inputsLoop u spendHeight rest acc'

/-- `Consensus::CheckTxInputs`: returns the fee `txfee` on success. -/
def checkTxInputs (u : UtxoSet T) (tx : Tx T) (spendHeight : Nat) : Option Int :=
  if !haveInputs u tx then none
  else
    match inputsLoop u spendHeight tx.vin 0 with
    | none => none
    | some valueIn =>
      let vOut := valueOut tx
      if valueIn < vOut then none
      else
        let fee := valueIn - vOut
        if !moneyRange fee then none else some fee

/-- The BIP30 pre-check of `ConnectBlock`: no output of any transaction of the block may already
exist as an unspent coin. -/
def bip30Ok (u : UtxoSet T) (block : List (Tx T)) : Bool :=
  block.all fun tx => (List.range tx.vout.length).all fun o => !haveCoin u ⟨tx.txid, o⟩

/-- The structural requirements `CheckBlock` places on the transactions: every transaction passes
`CheckTransaction`, the first is a coinbase and no other is. -/
def checkBlockTxs : List (Tx T) → Bool
  | [] => false
  | cb :: rest => cb.isCoinbase && checkTransaction cb && rest.all fun tx => !tx.isCoinbase && checkTransaction tx

/-- The per-transaction loop of `ConnectBlock`, restricted to accounting: for a non-coinbase
transaction, `CheckTxInputs` must succeed and the accumulated fees must stay in `MoneyRange`;
then `UpdateCoins`. Returns the final view and `nFees`. -/
def connectLoop (height : Nat) : UtxoSet T → Int → List (Tx T) → Option (UtxoSet T × Int)
  | u, fees, [] => some (u, fees)
  | u, fees, tx :: rest =>
    if tx.isCoinbase then connectLoop height (updateCoins u tx height) fees rest
    else
      match checkTxInputs u tx height with
      | none => none
      | some fee =>
        let fees' := fees + fee
        if !moneyRange fees' then none
        else connectLoop height (updateCoins u tx height) fees' rest

/-- `ConnectBlock`, restricted to value accounting, at a height where BIP30 is enforced: the
structural checks, the BIP30 pre-check, the transaction loop, and the coinbase bound
`GetValueOut() <= nFees + GetBlockSubsidy(height)`. The subsidy function is a parameter. -/
def connectBlock (subsidy : Nat → Int) (u : UtxoSet T) (height : Nat) (block : List (Tx T)) :
    Option (UtxoSet T × Int) :=
  if !checkBlockTxs block then none
  else if !bip30Ok u block then none
  else
    match connectLoop height u 0 block with
    | none => none
    | some (u', fees) =>
      match block with
      | [] => none
      | cb :: _ => if valueOut cb > fees + subsidy height then none else some (u', fees)

/-- Connect a sequence of blocks at consecutive heights starting from `height`. -/
def connectChain (subsidy : Nat → Int) : UtxoSet T → Nat → List (List (Tx T)) → Option (UtxoSet T)
  | u, _, [] => some u
  | u, height, block :: rest =>
    match connectBlock subsidy u height block with
    | none => none
    | some (u', _) => connectChain subsidy u' (height + 1) rest

/-- The total value held in the UTXO set. -/
def totalValue : UtxoSet T → Int
  | [] => 0
  | (_, c) :: rest => c.out.value + totalValue rest

/-- The sum of the subsidies at heights `h, h + 1, …, h + n - 1`. -/
def subsidySum (subsidy : Nat → Int) (h : Nat) : Nat → Int
  | 0 => 0
  | n + 1 => subsidySum subsidy h n + subsidy (h + n)

end BitcoinUtxo
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: CheckTransaction, src/consensus/tx_check.cpp lines 11-68: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/consensus/tx_check.cpp; Consensus::CheckTxInputs, src/consensus/tx_verify.cpp (lines 157-220): https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/consensus/tx_verify.cpp; CCoinsViewCache::AddCoin, AddCoins, SpendCoin, HaveInputs, src/coins.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/coins.cpp; UpdateCoins, BIP30 check (lines 2396-2475), fee accumulation and coinbase bound in Chainstate::ConnectBlock (lines 2518-2612), src/validation.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/validation.cpp; COIN, MAX_MONEY, MoneyRange, src/consensus/amount.h; COINBASE_MATURITY, src/consensus/consensus.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: Def_BitcoinUtxo.lean (namespace BitcoinUtxo)

Throughout the file there is a standing assumption: TTT is an arbitrary type (the type of transaction identifiers) equipped with a decidable equality, i.e. for any a,b∈Ta, b \in Ta,b∈T it can be decided whether a=ba = ba=b. Every declaration below that mentions TTT carries these two implicit assumptions. Nothing else is assumed about TTT: it may be empty, finite, or infinite, and no hash function or structure is attached to it.


COIN. An integer constant: COIN=100,000,000=108\mathrm{COIN} = 100{,}000{,}000 = 10^8COIN=100,000,000=108 (an element of Z\mathbb{Z}Z).


MAX_MONEY. An integer constant: MAX_MONEY=21,000,000⋅COIN=2,100,000,000,000,000=2.1×1015\mathrm{MAX\_MONEY} = 21{,}000{,}000 \cdot \mathrm{COIN} = 2{,}100{,}000{,}000{,}000{,}000 = 2.1 \times 10^{15}MAX_MONEY=21,000,000⋅COIN=2,100,000,000,000,000=2.1×1015 (an element of Z\mathbb{Z}Z).


moneyRange. A Boolean-valued function on integers: for v∈Zv \in \mathbb{Z}v∈Z,

moneyRange(v)=true  ⟺  0≤v and v≤MAX_MONEY,\mathrm{moneyRange}(v) = \mathrm{true} \iff 0 \le v \ \text{and}\ v \le \mathrm{MAX\_MONEY},moneyRange(v)=true⟺0≤v and v≤MAX_MONEY,

and moneyRange(v)=false\mathrm{moneyRange}(v) = \mathrm{false}moneyRange(v)=false otherwise. Both inequalities are non-strict; v=0v = 0v=0 and v=MAX_MONEYv = \mathrm{MAX\_MONEY}v=MAX_MONEY pass.


COINBASE_MATURITY. A natural-number constant: COINBASE_MATURITY=100\mathrm{COINBASE\_MATURITY} = 100COINBASE_MATURITY=100 (an element of N\mathbb{N}N).


OutPoint (parametrised by a type TTT). A record with two fields: txid∈T\mathrm{txid} \in Ttxid∈T and n∈N\mathrm{n} \in \mathbb{N}n∈N. Two outpoints are equal exactly when both fields agree; equality of outpoints is decidable (this is derived, and requires decidable equality on TTT). I write an outpoint as ⟨t,i⟩\langle t, i\rangle⟨t,i⟩.


TxOut. A record with two fields: value∈Z\mathrm{value} \in \mathbb{Z}value∈Z (any integer, possibly negative or larger than MAX_MONEY\mathrm{MAX\_MONEY}MAX_MONEY) and unspendable∈{true,false}\mathrm{unspendable} \in \{\mathrm{true}, \mathrm{false}\}unspendable∈{true,false}. Equality is decidable and componentwise.


Coin. A record with three fields: out∈TxOut\mathrm{out} \in \mathrm{TxOut}out∈TxOut, height∈N\mathrm{height} \in \mathbb{N}height∈N, and isCoinbase∈{true,false}\mathrm{isCoinbase} \in \{\mathrm{true}, \mathrm{false}\}isCoinbase∈{true,false}. Equality is decidable and componentwise. For a coin ccc I write c.out.valuec.\mathrm{out}.\mathrm{value}c.out.value for the integer value of its output and c.out.unspendablec.\mathrm{out}.\mathrm{unspendable}c.out.unspendable for its unspendable flag.


Tx (parametrised by a type TTT). A record with four fields: txid∈T\mathrm{txid} \in Ttxid∈T; vin\mathrm{vin}vin, a finite list of outpoints over TTT (possibly empty, possibly with repetitions); vout\mathrm{vout}vout, a finite list of TxOut records (possibly empty); and isCoinbase∈{true,false}\mathrm{isCoinbase} \in \{\mathrm{true}, \mathrm{false}\}isCoinbase∈{true,false}. Note that isCoinbase\mathrm{isCoinbase}isCoinbase is an independent Boolean field: it is not computed from vin\mathrm{vin}vin, and nothing in the record ties it to the contents of vin\mathrm{vin}vin. No decidable equality is derived for Tx.


UtxoSet (parametrised by a type TTT). A synonym for "finite list of pairs (p,c)(p, c)(p,c) with ppp an outpoint over TTT and ccc a coin". The list is ordered and may contain repeated outpoints; distinctness of outpoints is not part of this type, it is a separate predicate (keysNodup, below).


getCoin. For a UTXO set uuu and an outpoint ppp, getCoin(u,p)\mathrm{getCoin}(u, p)getCoin(u,p) is an optional coin defined by recursion on the list: if uuu is empty the result is "none"; if u=(k,c)::restu = (k, c) :: \mathrm{rest}u=(k,c)::rest then the result is "some ccc" when k=pk = pk=p, and otherwise getCoin(rest,p)\mathrm{getCoin}(\mathrm{rest}, p)getCoin(rest,p). So the result is the coin of the first (left-most) entry whose outpoint equals ppp, or "none" if no entry has outpoint ppp; later entries with the same outpoint are ignored. I write u[p]u[p]u[p] for getCoin(u,p)\mathrm{getCoin}(u,p)getCoin(u,p).


haveCoin. For a UTXO set uuu and outpoint ppp, haveCoin(u,p)\mathrm{haveCoin}(u, p)haveCoin(u,p) is the Boolean that is true exactly when u[p]u[p]u[p] is "some coin", i.e. when at least one entry of uuu has outpoint ppp.


keysNodup. For a UTXO set uuu, keysNodup(u)\mathrm{keysNodup}(u)keysNodup(u) is the proposition that the list of first components of uuu (the outpoints, in order, with multiplicity) has no duplicate element, i.e. the outpoints of uuu are pairwise distinct. It says nothing about the coins. The empty list satisfies it.


spendCoin. For a UTXO set uuu and outpoint ppp, spendCoin(u,p)\mathrm{spendCoin}(u, p)spendCoin(u,p) is the UTXO set obtained by recursion: the empty list maps to the empty list; (k,c)::rest(k, c) :: \mathrm{rest}(k,c)::rest maps to spendCoin(rest,p)\mathrm{spendCoin}(\mathrm{rest}, p)spendCoin(rest,p) if k=pk = pk=p, and to (k,c)::spendCoin(rest,p)(k, c) :: \mathrm{spendCoin}(\mathrm{rest}, p)(k,c)::spendCoin(rest,p) otherwise. Thus every entry whose outpoint equals ppp is removed (not only the first), the relative order of the remaining entries is preserved, and if no entry has outpoint ppp the list is returned unchanged. There is no failure case when ppp is absent.


addCoin. For a UTXO set uuu, outpoint ppp and coin ccc:

addCoin(u,p,c)={uif c.out.unspendable=true,(p,c)::spendCoin(u,p)otherwise.\mathrm{addCoin}(u, p, c) = \begin{cases} u & \text{if } c.\mathrm{out}.\mathrm{unspendable} = \mathrm{true},\\ (p, c) :: \mathrm{spendCoin}(u, p) & \text{otherwise.}\end{cases}addCoin(u,p,c)={u(p,c)::spendCoin(u,p)​if c.out.unspendable=true,otherwise.​

In the unspendable case uuu is returned unchanged — in particular any existing entry at outpoint ppp is kept. In the spendable case all existing entries at outpoint ppp are first removed and the new pair (p,c)(p, c)(p,c) is placed at the front of the list (replace-on-insert).


addCoinsFrom. Given a transaction id t∈Tt \in Tt∈T, a height h∈Nh \in \mathbb{N}h∈N, a Boolean cb\mathrm{cb}cb, a UTXO set uuu, a starting index i∈Ni \in \mathbb{N}i∈N and a list of outputs: if the list is empty the result is uuu; if it is o::resto :: \mathrm{rest}o::rest, the result is

addCoinsFrom(t,h,cb, addCoin(u,⟨t,i⟩,⟨o,h,cb⟩), i+1, rest),\mathrm{addCoinsFrom}\big(t, h, \mathrm{cb},\ \mathrm{addCoin}(u, \langle t, i\rangle, \langle o, h, \mathrm{cb}\rangle),\ i + 1,\ \mathrm{rest}\big),addCoinsFrom(t,h,cb, addCoin(u,⟨t,i⟩,⟨o,h,cb⟩), i+1, rest),

where ⟨o,h,cb⟩\langle o, h, \mathrm{cb}\rangle⟨o,h,cb⟩ is the coin with output ooo, height hhh and coinbase flag cb\mathrm{cb}cb. So the kkk-th output of the list (counting from 000) is added at outpoint ⟨t,i+k⟩\langle t, i + k\rangle⟨t,i+k⟩, left to right, each insertion applied to the result of the previous one. An unspendable output still consumes its index (the index advances to i+1i+1i+1 whether or not anything was inserted).


spendInputs. For a UTXO set uuu and a list of outpoints: the empty list gives uuu; p::restp :: \mathrm{rest}p::rest gives spendInputs(spendCoin(u,p),rest)\mathrm{spendInputs}(\mathrm{spendCoin}(u, p), \mathrm{rest})spendInputs(spendCoin(u,p),rest). That is, spendCoin\mathrm{spendCoin}spendCoin is applied successively for each outpoint in the list, in order. Outpoints absent from uuu, or repeated in the list, cause no error.


updateCoins. For a UTXO set uuu, a transaction tx\mathrm{tx}tx and a height h∈Nh \in \mathbb{N}h∈N:

updateCoins(u,tx,h)=addCoinsFrom(tx.txid, h, tx.isCoinbase, u0, 0, tx.vout),\mathrm{updateCoins}(u, \mathrm{tx}, h) = \mathrm{addCoinsFrom}\big(\mathrm{tx}.\mathrm{txid},\ h,\ \mathrm{tx}.\mathrm{isCoinbase},\ u_0,\ 0,\ \mathrm{tx}.\mathrm{vout}\big),updateCoins(u,tx,h)=addCoinsFrom(tx.txid, h, tx.isCoinbase, u0​, 0, tx.vout),

where u0=uu_0 = uu0​=u if tx.isCoinbase=true\mathrm{tx}.\mathrm{isCoinbase} = \mathrm{true}tx.isCoinbase=true and u0=spendInputs(u,tx.vin)u_0 = \mathrm{spendInputs}(u, \mathrm{tx}.\mathrm{vin})u0​=spendInputs(u,tx.vin) otherwise. So for a transaction flagged coinbase the inputs in tx.vin\mathrm{tx}.\mathrm{vin}tx.vin are not removed (whatever that list contains), and in both cases the outputs are added at outpoints ⟨tx.txid,0⟩,⟨tx.txid,1⟩,…\langle \mathrm{tx}.\mathrm{txid}, 0\rangle, \langle \mathrm{tx}.\mathrm{txid}, 1\rangle, \dots⟨tx.txid,0⟩,⟨tx.txid,1⟩,… as coins of height hhh carrying the transaction's coinbase flag.


outputsLoop. Given a list of outputs and an accumulator a∈Za \in \mathbb{Z}a∈Z, the result is an optional integer: the empty list gives "some aaa"; for o::resto :: \mathrm{rest}o::rest,

  • if o.value<0o.\mathrm{value} < 0o.value<0 the result is "none";
  • else if MAX_MONEY<o.value\mathrm{MAX\_MONEY} < o.\mathrm{value}MAX_MONEY<o.value (strict) the result is "none";
  • else if moneyRange(a+o.value)=false\mathrm{moneyRange}(a + o.\mathrm{value}) = \mathrm{false}moneyRange(a+o.value)=false (i.e. not 0≤a+o.value≤MAX_MONEY0 \le a + o.\mathrm{value} \le \mathrm{MAX\_MONEY}0≤a+o.value≤MAX_MONEY) the result is "none";
  • else the result is outputsLoop(rest,a+o.value)\mathrm{outputsLoop}(\mathrm{rest}, a + o.\mathrm{value})outputsLoop(rest,a+o.value).

So it returns "some a+∑o.valuea + \sum o.\mathrm{value}a+∑o.value" exactly when every output value lies in [0,MAX_MONEY][0, \mathrm{MAX\_MONEY}][0,MAX_MONEY] and every partial sum a+(values so far)a + (\text{values so far})a+(values so far) lies in [0,MAX_MONEY][0, \mathrm{MAX\_MONEY}][0,MAX_MONEY]; on an empty list it returns "some aaa" without any test.


sumValues. For a list of outputs, sumValues([ ])=0\mathrm{sumValues}([\,]) = 0sumValues([])=0 and sumValues(o::rest)=o.value+sumValues(rest)\mathrm{sumValues}(o :: \mathrm{rest}) = o.\mathrm{value} + \mathrm{sumValues}(\mathrm{rest})sumValues(o::rest)=o.value+sumValues(rest): the integer sum of the values, with no range check.


valueOut. For a transaction tx\mathrm{tx}tx, valueOut(tx)=sumValues(tx.vout)=∑o∈tx.vouto.value∈Z\mathrm{valueOut}(\mathrm{tx}) = \mathrm{sumValues}(\mathrm{tx}.\mathrm{vout}) = \sum_{o \in \mathrm{tx}.\mathrm{vout}} o.\mathrm{value} \in \mathbb{Z}valueOut(tx)=sumValues(tx.vout)=∑o∈tx.vout​o.value∈Z (zero for an empty output list).


valueIn. For a UTXO set uuu and a list of outpoints: valueIn(u,[ ])=0\mathrm{valueIn}(u, [\,]) = 0valueIn(u,[])=0, and

valueIn(u,p::rest)=(if u[p]=none then 0 else c.out.value where u[p]=some c)+valueIn(u,rest).\mathrm{valueIn}(u, p :: \mathrm{rest}) = \big(\text{if } u[p] = \text{none then } 0 \text{ else } c.\mathrm{out}.\mathrm{value} \text{ where } u[p] = \text{some } c\big) + \mathrm{valueIn}(u, \mathrm{rest}).valueIn(u,p::rest)=(if u[p]=none then 0 else c.out.value where u[p]=some c)+valueIn(u,rest).

So it is the sum, with multiplicity over the list, of the values of the first-matching coins, contributing 000 for an outpoint with no entry in uuu. A repeated outpoint is counted once per occurrence.


checkTransaction. For a transaction tx\mathrm{tx}tx, the Boolean conjunction of four conditions:

  1. tx.vin\mathrm{tx}.\mathrm{vin}tx.vin is non-empty;
  2. tx.vout\mathrm{tx}.\mathrm{vout}tx.vout is non-empty;
  3. outputsLoop(tx.vout,0)\mathrm{outputsLoop}(\mathrm{tx}.\mathrm{vout}, 0)outputsLoop(tx.vout,0) is "some ⋅\cdot⋅" (every output value in [0,MAX_MONEY][0,\mathrm{MAX\_MONEY}][0,MAX_MONEY] and every partial sum from 000 in [0,MAX_MONEY][0, \mathrm{MAX\_MONEY}][0,MAX_MONEY]);
  4. the list tx.vin\mathrm{tx}.\mathrm{vin}tx.vin has no duplicate outpoints.

It does not inspect tx.isCoinbase\mathrm{tx}.\mathrm{isCoinbase}tx.isCoinbase or tx.txid\mathrm{tx}.\mathrm{txid}tx.txid.


haveInputs. For a UTXO set uuu and a transaction tx\mathrm{tx}tx: haveInputs(u,tx)=true\mathrm{haveInputs}(u, \mathrm{tx}) = \mathrm{true}haveInputs(u,tx)=true iff tx.isCoinbase=true\mathrm{tx}.\mathrm{isCoinbase} = \mathrm{true}tx.isCoinbase=true, or every outpoint ppp in tx.vin\mathrm{tx}.\mathrm{vin}tx.vin satisfies haveCoin(u,p)=true\mathrm{haveCoin}(u, p) = \mathrm{true}haveCoin(u,p)=true. For a coinbase-flagged transaction it is true regardless of vin\mathrm{vin}vin; for an empty vin\mathrm{vin}vin it is true vacuously.


inputsLoop. Given a UTXO set uuu, a spend height s∈Ns \in \mathbb{N}s∈N, a list of outpoints and an accumulator a∈Za \in \mathbb{Z}a∈Z, the result is an optional integer: the empty list gives "some aaa"; for p::restp :: \mathrm{rest}p::rest,

  • if u[p]=u[p] = u[p]= none, the result is "none";
  • if u[p]=u[p] = u[p]= some coin\mathrm{coin}coin: if coin.isCoinbase=true\mathrm{coin}.\mathrm{isCoinbase} = \mathrm{true}coin.isCoinbase=true and s−˙coin.height<100s \mathbin{\dot-} \mathrm{coin}.\mathrm{height} < 100s−˙​coin.height<100, the result is "none", where −˙\dot-−˙​ is truncated natural-number subtraction (x−˙y=0x \dot- y = 0x−˙​y=0 whenever x≤yx \le yx≤y); consequently a coinbase coin with coin.height≥s\mathrm{coin}.\mathrm{height} \ge scoin.height≥s has s−˙coin.height=0<100s \dot- \mathrm{coin}.\mathrm{height} = 0 < 100s−˙​coin.height=0<100 and is rejected, and a coinbase coin passes exactly when s≥coin.height+100s \ge \mathrm{coin}.\mathrm{height} + 100s≥coin.height+100; a non-coinbase coin is never rejected by this test;
  • otherwise let a′=a+coin.out.valuea' = a + \mathrm{coin}.\mathrm{out}.\mathrm{value}a′=a+coin.out.value; if moneyRange(coin.out.value)=false\mathrm{moneyRange}(\mathrm{coin}.\mathrm{out}.\mathrm{value}) = \mathrm{false}moneyRange(coin.out.value)=false or moneyRange(a′)=false\mathrm{moneyRange}(a') = \mathrm{false}moneyRange(a′)=false, the result is "none"; else the result is inputsLoop(u,s,rest,a′)\mathrm{inputsLoop}(u, s, \mathrm{rest}, a')inputsLoop(u,s,rest,a′).

A repeated outpoint in the list is processed (and its value added) once per occurrence.


checkTxInputs. For a UTXO set uuu, a transaction tx\mathrm{tx}tx and a spend height s∈Ns \in \mathbb{N}s∈N, an optional integer:

  • if haveInputs(u,tx)=false\mathrm{haveInputs}(u, \mathrm{tx}) = \mathrm{false}haveInputs(u,tx)=false, "none";
  • else if inputsLoop(u,s,tx.vin,0)=\mathrm{inputsLoop}(u, s, \mathrm{tx}.\mathrm{vin}, 0) = inputsLoop(u,s,tx.vin,0)= none, "none";
  • else, with inputsLoop(u,s,tx.vin,0)=\mathrm{inputsLoop}(u, s, \mathrm{tx}.\mathrm{vin}, 0) = inputsLoop(u,s,tx.vin,0)= some vinv_{\mathrm{in}}vin​ and vout=valueOut(tx)v_{\mathrm{out}} = \mathrm{valueOut}(\mathrm{tx})vout​=valueOut(tx): if vin<voutv_{\mathrm{in}} < v_{\mathrm{out}}vin​<vout​, "none"; else let fee=vin−vout\mathrm{fee} = v_{\mathrm{in}} - v_{\mathrm{out}}fee=vin​−vout​; if moneyRange(fee)=false\mathrm{moneyRange}(\mathrm{fee}) = \mathrm{false}moneyRange(fee)=false, "none"; otherwise "some fee\mathrm{fee}fee".

Note that even for a coinbase-flagged transaction (for which haveInputs\mathrm{haveInputs}haveInputs is automatically true) the loop still requires every outpoint of tx.vin\mathrm{tx}.\mathrm{vin}tx.vin to be present in uuu; with an empty vin\mathrm{vin}vin the loop yields vin=0v_{\mathrm{in}} = 0vin​=0.


bip30Ok. For a UTXO set uuu and a list of transactions BBB: the Boolean that is true iff for every transaction tx\mathrm{tx}tx in BBB (including any coinbase) and every index o∈{0,1,…,∣tx.vout∣−1}o \in \{0, 1, \dots, |\mathrm{tx}.\mathrm{vout}| - 1\}o∈{0,1,…,∣tx.vout∣−1}, haveCoin(u,⟨tx.txid,o⟩)=false\mathrm{haveCoin}(u, \langle \mathrm{tx}.\mathrm{txid}, o\rangle) = \mathrm{false}haveCoin(u,⟨tx.txid,o⟩)=false. It is tested against the single set uuu given, not against intermediate states; it is vacuously true for an empty block or for a transaction with no outputs, and it does not look at indices ≥∣tx.vout∣\ge |\mathrm{tx}.\mathrm{vout}|≥∣tx.vout∣.


checkBlockTxs. For a list of transactions: the empty list gives false\mathrm{false}false; cb::rest\mathrm{cb} :: \mathrm{rest}cb::rest gives the conjunction of cb.isCoinbase=true\mathrm{cb}.\mathrm{isCoinbase} = \mathrm{true}cb.isCoinbase=true, checkTransaction(cb)=true\mathrm{checkTransaction}(\mathrm{cb}) = \mathrm{true}checkTransaction(cb)=true, and, for every tx\mathrm{tx}tx in rest\mathrm{rest}rest, tx.isCoinbase=false\mathrm{tx}.\mathrm{isCoinbase} = \mathrm{false}tx.isCoinbase=false and checkTransaction(tx)=true\mathrm{checkTransaction}(\mathrm{tx}) = \mathrm{true}checkTransaction(tx)=true. A block consisting of the coinbase alone passes if the coinbase passes checkTransaction (which in particular requires it to have at least one input and one output).


connectLoop. Given a height h∈Nh \in \mathbb{N}h∈N, a UTXO set uuu, an accumulated fee f∈Zf \in \mathbb{Z}f∈Z and a list of transactions, the result is an optional pair (UTXO set, integer): the empty list gives "some (u,f)(u, f)(u,f)"; for tx::rest\mathrm{tx} :: \mathrm{rest}tx::rest,

  • if tx.isCoinbase=true\mathrm{tx}.\mathrm{isCoinbase} = \mathrm{true}tx.isCoinbase=true, the result is connectLoop(h,updateCoins(u,tx,h),f,rest)\mathrm{connectLoop}(h, \mathrm{updateCoins}(u, \mathrm{tx}, h), f, \mathrm{rest})connectLoop(h,updateCoins(u,tx,h),f,rest) — no input check and no fee change, wherever in the list such a transaction sits;
  • otherwise, if checkTxInputs(u,tx,h)=\mathrm{checkTxInputs}(u, \mathrm{tx}, h) = checkTxInputs(u,tx,h)= none, "none"; if it is some fee\mathrm{fee}fee, let f′=f+feef' = f + \mathrm{fee}f′=f+fee; if moneyRange(f′)=false\mathrm{moneyRange}(f') = \mathrm{false}moneyRange(f′)=false, "none"; else connectLoop(h,updateCoins(u,tx,h),f′,rest)\mathrm{connectLoop}(h, \mathrm{updateCoins}(u, \mathrm{tx}, h), f', \mathrm{rest})connectLoop(h,updateCoins(u,tx,h),f′,rest).

The same hhh is used both as the spend height passed to checkTxInputs and as the creation height of the new coins.


connectBlock. Given a function subsidy:N→Z\mathrm{subsidy} : \mathbb{N} \to \mathbb{Z}subsidy:N→Z, a UTXO set uuu, a height h∈Nh \in \mathbb{N}h∈N and a list of transactions BBB, an optional pair (UTXO set, integer):

  • if checkBlockTxs(B)=false\mathrm{checkBlockTxs}(B) = \mathrm{false}checkBlockTxs(B)=false, "none";
  • else if bip30Ok(u,B)=false\mathrm{bip30Ok}(u, B) = \mathrm{false}bip30Ok(u,B)=false, "none";
  • else if connectLoop(h,u,0,B)=\mathrm{connectLoop}(h, u, 0, B) = connectLoop(h,u,0,B)= none, "none";
  • else, with connectLoop(h,u,0,B)=\mathrm{connectLoop}(h, u, 0, B) = connectLoop(h,u,0,B)= some (u′,f)(u', f)(u′,f): if BBB is empty, "none" (this branch cannot actually occur since checkBlockTxs already rejected the empty list, but it is what the code returns); if B=cb::_B = \mathrm{cb} :: \_B=cb::_, then "none" if valueOut(cb)>f+subsidy(h)\mathrm{valueOut}(\mathrm{cb}) > f + \mathrm{subsidy}(h)valueOut(cb)>f+subsidy(h) (strict), and "some (u′,f)(u', f)(u′,f)" otherwise, i.e. when valueOut(cb)≤f+subsidy(h)\mathrm{valueOut}(\mathrm{cb}) \le f + \mathrm{subsidy}(h)valueOut(cb)≤f+subsidy(h).

Only the first transaction's output value is compared against f+subsidy(h)f + \mathrm{subsidy}(h)f+subsidy(h); subsidy(h)\mathrm{subsidy}(h)subsidy(h) may be any integer, including negative.


connectChain. Given subsidy:N→Z\mathrm{subsidy} : \mathbb{N} \to \mathbb{Z}subsidy:N→Z, a UTXO set uuu, a height h∈Nh \in \mathbb{N}h∈N and a list of blocks (each a list of transactions), an optional UTXO set: the empty list of blocks gives "some uuu"; B::restB :: \mathrm{rest}B::rest gives "none" if connectBlock(subsidy,u,h,B)=\mathrm{connectBlock}(\mathrm{subsidy}, u, h, B) = connectBlock(subsidy,u,h,B)= none, and otherwise, with that result some (u′,_)(u', \_)(u′,_), gives connectChain(subsidy,u′,h+1,rest)\mathrm{connectChain}(\mathrm{subsidy}, u', h + 1, \mathrm{rest})connectChain(subsidy,u′,h+1,rest). The fee component returned by each block is discarded; the kkk-th block (from 000) is connected at height h+kh + kh+k.


totalValue. For a UTXO set uuu: totalValue([ ])=0\mathrm{totalValue}([\,]) = 0totalValue([])=0 and totalValue((_,c)::rest)=c.out.value+totalValue(rest)\mathrm{totalValue}((\_, c) :: \mathrm{rest}) = c.\mathrm{out}.\mathrm{value} + \mathrm{totalValue}(\mathrm{rest})totalValue((_,c)::rest)=c.out.value+totalValue(rest): the integer sum of the values of all entries, counted with multiplicity even if several entries share an outpoint, with no range check. I write it tv(u)\mathrm{tv}(u)tv(u).


subsidySum. For subsidy:N→Z\mathrm{subsidy} : \mathbb{N} \to \mathbb{Z}subsidy:N→Z, h∈Nh \in \mathbb{N}h∈N and n∈Nn \in \mathbb{N}n∈N: subsidySum(subsidy,h,0)=0\mathrm{subsidySum}(\mathrm{subsidy}, h, 0) = 0subsidySum(subsidy,h,0)=0 and subsidySum(subsidy,h,n+1)=subsidySum(subsidy,h,n)+subsidy(h+n)\mathrm{subsidySum}(\mathrm{subsidy}, h, n+1) = \mathrm{subsidySum}(\mathrm{subsidy}, h, n) + \mathrm{subsidy}(h + n)subsidySum(subsidy,h,n+1)=subsidySum(subsidy,h,n)+subsidy(h+n), i.e.

subsidySum(subsidy,h,n)=∑k=0n−1subsidy(h+k)∈Z,\mathrm{subsidySum}(\mathrm{subsidy}, h, n) = \sum_{k=0}^{n-1} \mathrm{subsidy}(h + k) \in \mathbb{Z},subsidySum(subsidy,h,n)=k=0∑n−1​subsidy(h+k)∈Z,

which is 000 for n=0n = 0n=0.

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

    Confirmed by the moderator at approval.

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