Block validation composed: header path, CheckBlock, ContextualCheckBlock, ConnectBlock, DisconnectBlock, and the declarative specification
DefinitionBitcoinBlockConstants. MAX_BLOCK_WEIGHT = 4,000,000, MAX_BLOCK_SIGOPS_COST = 80,000, WITNESS_SCALE_FACTOR = 4, LOCKTIME_THRESHOLD = 500,000,000, SEQUENCE_FINAL = 0xffffffff, MINIMUM_WITNESS_COMMITMENT = 38, BIP34_IMPLIES_BIP30_LIMIT = 1,983,702, MAX_FUTURE_BLOCK_TIME = 7200 s, COINBASE_MATURITY = 100, MAX_MONEY; the mainnet hashes BIP34Hash, the two script_flag_exceptions, the two IsBIP30Repeat blocks (91842, 91880) and the two IsBIP30Unspendable blocks (91722, 91812), in serialized byte order.
Transactions. isCoinBase (one input with a null prevout), isUnspendable (OP_RETURN first or over 10,000 bytes), valueOut, checkTransaction (CheckTransaction: non-empty inputs and outputs, witness-stripped size within the weight limit, each output and the running total in MoneyRange, no duplicate prevouts, coinbase script 2–100 bytes, no null prevout otherwise), isFinalTx.
Signature operations. getSigOpCount accurate is CScript::GetSigOpCount(fAccurate); p2shSigOpCount is the redeem-script count; witnessSigOps/countWitnessSigOps are CountWitnessSigOps; legacySigOpCount and txSigOpCost are GetLegacySigOpCount and GetTransactionSigOpCost (legacy and P2SH counts weighted by 4, witness counts unweighted; P2SH only with the flag).
Ledger. Coin (output, height, coinbase flag); a Ledger is an association list; getCoin, haveCoin, accessCoin, spendCoin, addCoin (unspendable outputs are not stored; an existing entry is replaced), updateCoins (UpdateCoins), txUndo (the coins an input list spends), Equiv (same coins), keysNodup, LedgerOk.
Per-transaction checks. checkTxInputs (Consensus::CheckTxInputs, returning the fee), sequenceLocksOk (SequenceLocks through the BIP68 mission), inputScriptsOk (CheckInputScripts through the complete VerifyScript with the Taproot branch and the spent outputs), and connectLoop, the transaction loop of ConnectBlock in source order (inputs, fee range, BIP68, sigop budget, scripts, UpdateCoins), accumulating the ledger, fees, sigop cost and undo data.
Chain state. ChainState is the list of validated headers from the genesis and the ledger; initialState; tip, heights, timesTo/mtpAt/mtp (GetMedianTimePast through the Header mission), requiredBits (GetNextWorkRequired through the PoW mission with the period's first block), blockProof/chainWork (GetBlockProof, nChainWork), hashValue.
The validation path. checkBlock (CheckBlock with proof of work and merkle root through the Merkle mission), heightScript/witnessCommitmentIndex/checkWitnessMalleation/contextualCheckBlock (ContextualCheckBlock), bip30Checked (fEnforceBIP30 || nHeight >= BIP34_IMPLIES_BIP30_LIMIT), bip30Ok, connectBlock (ConnectBlock after CheckBlock: genesis shortcut, BIP30, flags from the Activation mission, the loop, the coinbase bound with GetBlockSubsidy), acceptHeader (AcceptBlockHeader on the tip, in source order), and validate S B t : Outcome — the source-linked outcome with constructors accept S' undo, invalid, futureTime (BLOCK_TIME_FUTURE) and missingPrev. accepts, and Reachable (from the genesis state through accepted blocks).
Disconnect. applyTxInUndo, restoreInputs, spendOutputs, disconnectTx, disconnectTxs, disconnectBlock (DisconnectBlock with the clean flag and the two exception blocks).
Specification. TxSpec, valueIn, feeOf, TxInputsSpec (existing mature coins, value bounds, the BIP68 specification satisfiesBIP68, every input script), TxsSpec (transactions applied in order), applyTxs, totalFees, applySpec (), HeaderSpec (the PoW mission's specTarget form, parent, difficulty, median-time floor, clock ceiling, version floors), BlockSpec, ContextSpec, LedgerSpec (BIP30 where it applies, the sequence, the coinbase bound with specSubsidy), Valid (), LedgerOk, WellFormed.
Formalization Note. fJustCheck is false and script checks are always performed (no assumed-valid shortcut); the chain is linear (a header not on the tip is missingPrev, the orphan case); flags, subsidy, difficulty, median time, merkle root and scripts are the published missions' functions. Only Std is imported.
Deprecated. Superseded by BitcoinBlockV2 (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.
import Std
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinScript
import Definitions.Def_BitcoinSig
import Definitions.Def_BitcoinVerify
import Definitions.Def_BitcoinTaproot
import Definitions.Def_BitcoinActivation
import Definitions.Def_BitcoinHeader
import Definitions.Def_BitcoinPow
import Definitions.Def_BitcoinSubsidy
import Definitions.Def_BitcoinMerkle
import Definitions.Def_BIP68_Core
import Definitions.Def_BitcoinUtxo
namespace BitcoinBlock
/-! Composition of Bitcoin Core's block validation at revision `a773e1e33b349dc819b5a0edc1c7a4839dc73b48`,
mainnet parameters: the header path of `AcceptBlockHeader` (`CheckBlockHeader`, the previous-block
lookup, `ContextualCheckBlockHeader`), `CheckBlock`, `ContextualCheckBlock` (`IsFinalTx`, the BIP34
coinbase height, `CheckWitnessMalleation`, `GetBlockWeight`), and `ConnectBlock` (the BIP30 rule with
`IsBIP30Repeat` and the BIP34 shortcut, `CheckTxInputs`, `SequenceLocks`, `GetTransactionSigOpCost`,
`CheckInputScripts` through the complete `VerifyScript`, `UpdateCoins`, the coinbase bound), together
with `DisconnectBlock`/`ApplyTxInUndo`, the genesis state, `GetBlockProof`, and a declarative
specification of block admissibility and of the ledger transition. -/
open BitcoinSer (Byte Bytes Tx TxIn TxOut OutPoint Header Block)
/-! ### Constants (`consensus/consensus.h`, `script/script.h`, `validation.cpp`, `chainparams.cpp`) -/
def MAX_BLOCK_WEIGHT : Nat := 4000000
def MAX_BLOCK_SIGOPS_COST : Nat := 80000
def WITNESS_SCALE_FACTOR : Nat := 4
def LOCKTIME_THRESHOLD : Nat := 500000000
def SEQUENCE_FINAL : Nat := 0xffffffff
def MINIMUM_WITNESS_COMMITMENT : Nat := 38
def BIP34_IMPLIES_BIP30_LIMIT : Nat := 1983702
def MAX_FUTURE_BLOCK_TIME : Int := 2 * 60 * 60
def COINBASE_MATURITY : Nat := 100
def MAX_MONEY : Int := 2100000000000000
/-- `MoneyRange`. -/
def moneyRange (v : Int) : Bool := decide (0 ≤ v ∧ v ≤ MAX_MONEY)
/-- Block hashes in serialized (internal) byte order: `consensus.BIP34Hash`. -/
def bip34Hash : Bytes := [0xb8, 0x08, 0x08, 0x9c, 0x75, 0x6a, 0xdd, 0x15, 0x91, 0xb1, 0xd1, 0x7b, 0xab, 0x44, 0xbb, 0xa3, 0xfe, 0xd9, 0xe0, 0x2f, 0x94, 0x2a, 0xb4, 0x89, 0x4b, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]
/-- The `script_flag_exceptions` keys. -/
def bip16ExceptionHash : Bytes := [0x22, 0x9c, 0x4f, 0xac, 0x88, 0xba, 0xb1, 0x94, 0xeb, 0x08, 0xf1, 0xa5, 0x28, 0xcc, 0x30, 0x8d, 0xed, 0x23, 0x97, 0xf4, 0xf4, 0xeb, 0x6e, 0x75, 0xdc, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]
def taprootExceptionHash : Bytes := [0xad, 0x95, 0xe3, 0xa1, 0x5e, 0xe5, 0xff, 0xd5, 0x85, 0xc5, 0xe8, 0x1d, 0x44, 0xb5, 0x6a, 0x98, 0x1e, 0x84, 0x2d, 0x5b, 0xc3, 0x14, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]
/-- `IsBIP30Repeat`: the two blocks whose coinbases repeat earlier ones. -/
def bip30Repeat91842 : Bytes := [0xec, 0xca, 0xe0, 0x00, 0xe3, 0xc8, 0xe4, 0xe0, 0x93, 0x93, 0x63, 0x60, 0x43, 0x1f, 0x3b, 0x76, 0x03, 0xc5, 0x63, 0xc1, 0xff, 0x61, 0x81, 0x39, 0x0a, 0x4d, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x00]
def bip30Repeat91880 : Bytes := [0x21, 0xd7, 0x7c, 0xcb, 0x4c, 0x08, 0x38, 0x6a, 0x04, 0xac, 0x01, 0x96, 0xae, 0x10, 0xf6, 0xa1, 0xd2, 0xc2, 0xa3, 0x77, 0x55, 0x8c, 0xa1, 0x90, 0xf1, 0x43, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00]
/-- `IsBIP30Unspendable`: the two blocks whose coinbases were overwritten. -/
def bip30Unspendable91722 : Bytes := [0x8e, 0xd0, 0x4d, 0x57, 0xf2, 0xf3, 0xcd, 0xc6, 0xa6, 0xe5, 0x55, 0x69, 0xdc, 0x16, 0x54, 0xe1, 0xf2, 0x19, 0x84, 0x7f, 0x66, 0xe7, 0x26, 0xdc, 0xa2, 0x71, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00]
def bip30Unspendable91812 : Bytes := [0x2f, 0x6f, 0x30, 0xf9, 0xd6, 0x83, 0xde, 0xb8, 0x5d, 0x93, 0x14, 0xef, 0x5d, 0xcf, 0x36, 0xaf, 0x66, 0xd9, 0xe3, 0xce, 0x1a, 0x2b, 0x79, 0xd4, 0xae, 0xf0, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x00]
def isBIP30Repeat (height : Nat) (hash : Bytes) : Bool :=
(decide (height = 91842) && decide (hash = bip30Repeat91842)) ||
(decide (height = 91880) && decide (hash = bip30Repeat91880))
def isBIP30Unspendable (height : Nat) (hash : Bytes) : Bool :=
(decide (height = 91722) && decide (hash = bip30Unspendable91722)) ||
(decide (height = 91812) && decide (hash = bip30Unspendable91812))
/-- The `script_flag_exceptions` lookup by block hash. -/
def scriptException (hash : Bytes) : BitcoinActivation.ScriptException :=
if hash = bip16ExceptionHash then .bip16Block
else if hash = taprootExceptionHash then .taprootBlock
else .none
/-! ### Transactions (`primitives/transaction.h`, `consensus/tx_check.cpp`, `tx_verify.cpp`) -/
/-- `COutPoint::IsNull`. -/
def outPointNull (o : OutPoint) : Bool := decide (o.hash = List.replicate 32 0) && decide (o.n = 0xffffffff)
/-- `CTransaction::IsCoinBase`: one input whose prevout is null. -/
def isCoinBase (tx : Tx) : Bool :=
match tx.vin with
| [i] => outPointNull i.prevout
| _ => false
/-- `CScript::IsUnspendable`: starts with `OP_RETURN`, or longer than `MAX_SCRIPT_SIZE`. -/
def isUnspendable (s : Bytes) : Bool :=
(decide (0 < s.length) && decide ((s.getD 0 0) = BitcoinScript.OP_RETURN)) ||
decide (BitcoinVerify.MAX_SCRIPT_SIZE < s.length)
def sumValues : List TxOut → Int
| [] => 0
| o :: rest => o.nValue + sumValues rest
/-- `CTransaction::GetValueOut`. -/
def valueOut (tx : Tx) : Int := sumValues tx.vout
/-- The output loop of `CheckTransaction`: each value in `[0, MAX_MONEY]` and the running total in
`MoneyRange`. -/
def outputsLoop : List TxOut → Int → Option Int
| [], acc => some acc
| o :: rest, acc =>
if o.nValue < 0 then none
else if MAX_MONEY < o.nValue then none
else if !moneyRange (acc + o.nValue) then none
else outputsLoop rest (acc + o.nValue)
/-- `CheckTransaction`. -/
def checkTransaction (tx : Tx) : Bool :=
!tx.vin.isEmpty && !tx.vout.isEmpty &&
decide ((BitcoinSer.serTx false tx).length * WITNESS_SCALE_FACTOR ≤ MAX_BLOCK_WEIGHT) &&
(outputsLoop tx.vout 0).isSome &&
decide ((tx.vin.map TxIn.prevout).Nodup) &&
(if isCoinBase tx then
decide (2 ≤ (tx.vin.headD ⟨⟨[], 0⟩, [], 0, []⟩).scriptSig.length ∧
(tx.vin.headD ⟨⟨[], 0⟩, [], 0, []⟩).scriptSig.length ≤ 100)
else tx.vin.all fun i => !outPointNull i.prevout)
/-- `IsFinalTx(tx, nBlockHeight, nBlockTime)`. -/
def isFinalTx (tx : Tx) (height : Nat) (blockTime : Int) : Bool :=
if tx.nLockTime = 0 then true
else if (tx.nLockTime : Int) < (if tx.nLockTime < LOCKTIME_THRESHOLD then (height : Int) else blockTime) then true
else tx.vin.all fun i => decide (i.nSequence = SEQUENCE_FINAL)
/-! ### Signature-operation counting (`script/script.cpp`, `script/interpreter.cpp`, `tx_verify.cpp`) -/
/-- `CScript::GetSigOpCount(fAccurate)`: `CHECKSIG(VERIFY)` counts one, `CHECKMULTISIG(VERIFY)` counts
the preceding `OP_n` when accurate, else 20; a parse failure ends the count. `last` is the previous
opcode (`OP_INVALIDOPCODE` initially). -/
def sigOpCountAux (accurate : Bool) : Nat → Bytes → Nat → Nat → Nat
| _, [], _, n => n
| 0, _, _, n => n
| fuel + 1, s, last, n =>
match BitcoinSig.getOp s with
| none => n
| some (.push _, r) => sigOpCountAux accurate fuel r 0 n
| some (.op c, r) =>
let n' :=
if c = BitcoinScript.OP_CHECKSIG ∨ c = BitcoinScript.OP_CHECKSIGVERIFY then n + 1
else if c = BitcoinScript.OP_CHECKMULTISIG ∨ c = BitcoinScript.OP_CHECKMULTISIGVERIFY then
if accurate ∧ 0x51 ≤ last ∧ last ≤ 0x60 then n + BitcoinVerify.decodeOpN last
else n + BitcoinScript.MAX_PUBKEYS_PER_MULTISIG
else n
sigOpCountAux accurate fuel r c.toNat n'
def getSigOpCount (accurate : Bool) (s : Bytes) : Nat := sigOpCountAux accurate s.length s 0xff 0
/-- The last datum pushed by a push-only script (`vData` after the `GetOp` loop); `none` when some
instruction fails to parse or is above `OP_16`. -/
def lastPushAux : Nat → Bytes → Bytes → Option Bytes
| _, [], d => some d
| 0, _, _ => none
| fuel + 1, s, _ =>
match BitcoinSig.getOp s with
| none => none
| some (.push d, r) => lastPushAux fuel r d
| some (.op c, r) => if BitcoinScript.OP_16 < c then none else lastPushAux fuel r []
def lastPush (s : Bytes) : Option Bytes := lastPushAux s.length s []
/-- `CScript::GetSigOpCount(scriptSig)` on the output script: the accurate count of the output
script unless it is P2SH, in which case the accurate count of the redeem script (the last push of
`scriptSig`), or `0` when `scriptSig` is not push-only. -/
def p2shSigOpCount (scriptPubKey scriptSig : Bytes) : Nat :=
if !BitcoinVerify.isPayToScriptHash scriptPubKey then getSigOpCount true scriptPubKey
else match lastPush scriptSig with
| none => 0
| some d => getSigOpCount true d
/-- `WitnessSigOps`. -/
def witnessSigOps (version : Nat) (program : Bytes) (witness : List Bytes) : Nat :=
if version = 0 then
if program.length = 20 then 1
else if program.length = 32 ∧ 0 < witness.length then getSigOpCount true (witness.getLast?.getD [])
else 0
else 0
/-- `CountWitnessSigOps(scriptSig, scriptPubKey, witness, flags)`. -/
def countWitnessSigOps (f : BitcoinActivation.ScriptFlags) (scriptSig scriptPubKey : Bytes) (witness : List Bytes) : Nat :=
if !f.witness then 0
else match BitcoinVerify.isWitnessProgram scriptPubKey with
| some (v, p) => witnessSigOps v p witness
| none =>
if BitcoinVerify.isPayToScriptHash scriptPubKey && BitcoinVerify.isPushOnly scriptSig then
match lastPush scriptSig with
| none => 0
| some d =>
match BitcoinVerify.isWitnessProgram d with
| some (v, p) => witnessSigOps v p witness
| none => 0
else 0
/-- `GetLegacySigOpCount`. -/
def legacySigOpCount (tx : Tx) : Nat :=
(tx.vin.map fun i => getSigOpCount false i.scriptSig).sum +
(tx.vout.map fun o => getSigOpCount false o.scriptPubKey).sum
/-! ### The ledger (`coins.h`, `coins.cpp`, `validation.cpp`) -/
/-- `Coin`: an unspent output with its creation height and coinbase flag. -/
structure Coin where
out : TxOut
height : Nat
isCoinbase : Bool
deriving DecidableEq, Repr
def dummyCoin : Coin := ⟨⟨-1, []⟩, 0, false⟩
/-- The UTXO set as an association list keyed by outpoint. -/
abbrev Ledger := List (OutPoint × Coin)
def getCoin : Ledger → OutPoint → Option Coin
| [], _ => none
| (k, c) :: rest, op => if k = op then some c else getCoin rest op
def haveCoin (u : Ledger) (op : OutPoint) : Bool := (getCoin u op).isSome
/-- `AccessCoin`: the coin, or a spent (dummy) coin. -/
def accessCoin (u : Ledger) (op : OutPoint) : Coin := (getCoin u op).getD dummyCoin
def spendCoin : Ledger → OutPoint → Ledger
| [], _ => []
| (k, c) :: rest, op => if k = op then spendCoin rest op else (k, c) :: spendCoin rest op
/-- `AddCoin`: unspendable outputs are not stored; otherwise the entry replaces any existing one. -/
def addCoin (u : Ledger) (op : OutPoint) (c : Coin) : Ledger :=
if isUnspendable c.out.scriptPubKey then u else (op, c) :: spendCoin u op
def addCoinsFrom (txid : Bytes) (height : Nat) (cb : Bool) : Ledger → Nat → List TxOut → Ledger
| u, _, [] => u
| u, i, o :: rest => addCoinsFrom txid height cb (addCoin u ⟨txid, i⟩ ⟨o, height, cb⟩) (i + 1) rest
def spendInputs : Ledger → List TxIn → Ledger
| u, [] => u
| u, i :: rest => spendInputs (spendCoin u i.prevout) rest
/-- `UpdateCoins(tx, view, undo, height)`: spend the inputs of a non-coinbase, then `AddCoins`. -/
def updateCoins (u : Ledger) (tx : Tx) (height : Nat) : Ledger :=
addCoinsFrom (BitcoinSer.txid tx) height (isCoinBase tx)
(if isCoinBase tx then u else spendInputs u tx.vin) 0 tx.vout
/-- The `CTxUndo` of a transaction: the coins its inputs spend. -/
def txUndo (u : Ledger) (tx : Tx) : List Coin := tx.vin.map fun i => accessCoin u i.prevout
/-- `CBlockUndo`: one `CTxUndo` per non-coinbase transaction, in block order. -/
abbrev BlockUndo := List (List Coin)
/-- Two ledgers with the same coins. -/
def Equiv (u v : Ledger) : Prop := ∀ op, getCoin u op = getCoin v op
/-- The pairwise-distinct-keys invariant. -/
def keysNodup (u : Ledger) : Prop := (u.map Prod.fst).Nodup
/-! ### `CheckTxInputs` and the per-transaction checks of `ConnectBlock` -/
def inputsLoop (u : Ledger) (spendHeight : Nat) : List TxIn → Int → Option Int
| [], acc => some acc
| i :: rest, acc =>
match getCoin u i.prevout with
| none => none
| some coin =>
if coin.isCoinbase && decide (spendHeight - coin.height < COINBASE_MATURITY) then none
else
let acc' := acc + coin.out.nValue
if !moneyRange coin.out.nValue || !moneyRange acc' then none
else inputsLoop u spendHeight rest acc'
/-- `Consensus::CheckTxInputs`: the fee on success. -/
def checkTxInputs (u : Ledger) (tx : Tx) (spendHeight : Nat) : Option Int :=
if !(tx.vin.all fun i => haveCoin u i.prevout) then none
else match inputsLoop u spendHeight tx.vin 0 with
| none => none
| some valueIn =>
if valueIn < valueOut tx then none
else if !moneyRange (valueIn - valueOut tx) then none
else some (valueIn - valueOut tx)
/-- `GetTransactionSigOpCost(tx, view, flags)`. -/
def txSigOpCost (f : BitcoinActivation.ScriptFlags) (u : Ledger) (tx : Tx) : Nat :=
legacySigOpCount tx * WITNESS_SCALE_FACTOR +
(if isCoinBase tx then 0
else
(if f.p2sh then
(tx.vin.map fun i => p2shSigOpCount (accessCoin u i.prevout).out.scriptPubKey i.scriptSig).sum *
WITNESS_SCALE_FACTOR
else 0) +
(tx.vin.map fun i => countWitnessSigOps f i.scriptSig (accessCoin u i.prevout).out.scriptPubKey i.witness).sum)
/-- `SequenceLocks(tx, nLockTimeFlags, prevheights, *pindex)` through the BIP68 mission's
transcription; `mtp h` is the median time past of the chain at height `h`. -/
def sequenceLocksOk (u : Ledger) (height : Nat) (mtp : Nat → Nat) (lockTimeFlags : Nat) (tx : Tx) : Bool :=
BitcoinBIP68.sequenceLocks (BitVec.ofNat 32 tx.version) (BitVec.ofNat 32 lockTimeFlags) ⟨height, mtp⟩
(tx.vin.map fun i => ⟨BitVec.ofNat 32 i.nSequence, (accessCoin u i.prevout).height⟩)
/-- `CheckInputScripts`: every input's script verifies under the block's flags, with the complete
`VerifyScript` (Taproot branch included) and the spent outputs for the BIP341 hash. -/
def inputScriptsOk (f : BitcoinActivation.ScriptFlags) (u : Ledger) (tx : Tx) : Bool :=
let spent := tx.vin.map fun i => (accessCoin u i.prevout).out
(List.range tx.vin.length).all fun n =>
let i := tx.vin.getD n ⟨⟨[], 0⟩, [], 0, []⟩
let coin := accessCoin u i.prevout
BitcoinTaproot.verifyScriptFull spent ⟨f, tx, n, coin.out.nValue⟩ i.scriptSig coin.out.scriptPubKey i.witness
/-- The accumulator of the `ConnectBlock` loop. -/
structure LoopState where
utxo : Ledger
fees : Int
sigOps : Nat
undo : BlockUndo
/-- The transaction loop of `ConnectBlock`, in source order: `CheckTxInputs`, the fee range,
`SequenceLocks`, the sigop budget, `CheckInputScripts`, `UpdateCoins`. -/
def connectLoop (f : BitcoinActivation.ScriptFlags) (height : Nat) (mtp : Nat → Nat) (lockTimeFlags : Nat) :
LoopState → List Tx → Option LoopState
| st, [] => some st
| st, tx :: rest =>
let step : Option (Int × BlockUndo) :=
if isCoinBase tx then some (st.fees, st.undo)
else match checkTxInputs st.utxo tx height with
| none => none
| some fee =>
if !moneyRange (st.fees + fee) then none
else if !sequenceLocksOk st.utxo height mtp lockTimeFlags tx then none
else some (st.fees + fee, st.undo ++ [txUndo st.utxo tx])
match step with
| none => none
| some (fees, undo) =>
let sigOps := st.sigOps + txSigOpCost f st.utxo tx
if MAX_BLOCK_SIGOPS_COST < sigOps then none
else if !isCoinBase tx && !inputScriptsOk f st.utxo tx then none
else connectLoop f height mtp lockTimeFlags ⟨updateCoins st.utxo tx height, fees, sigOps, undo⟩ rest
/-! ### Chain state -/
/-- A validated chain: its headers from the genesis to the tip, and the UTXO set. -/
structure ChainState where
headers : List Header
utxo : Ledger
/-- Genesis initialization: the genesis header, and an empty UTXO set (the genesis coinbase is not
spendable). -/
def initialState : ChainState := ⟨[BitcoinSer.genesisHeader], []⟩
def ChainState.tipHeight (S : ChainState) : Nat := S.headers.length - 1
def ChainState.tip (S : ChainState) : Header := S.headers.getLastD BitcoinSer.genesisHeader
def ChainState.tipHash (S : ChainState) : Bytes := BitcoinSer.headerHash S.tip
/-- The height of the next block. -/
def ChainState.nextHeight (S : ChainState) : Nat := S.headers.length
/-- The times of the blocks at heights `0..h`, most recent first. -/
def ChainState.timesTo (S : ChainState) (h : Nat) : List Int :=
((S.headers.take (h + 1)).map fun hd => (hd.time : Int)).reverse
/-- `GetMedianTimePast` of the block at height `h`. -/
def ChainState.mtpAt (S : ChainState) (h : Nat) : Int := BitcoinHeader.medianTimePast (S.timesTo h)
/-- The median time past of the tip. -/
def ChainState.mtp (S : ChainState) : Int := S.mtpAt S.tipHeight
/-- The `Context.mtp` function of the BIP68 mission (times are non-negative on any real chain). -/
def ChainState.mtpNat (S : ChainState) (h : Nat) : Nat := (S.mtpAt h).toNat
/-- `GetNextWorkRequired(pindexLast, …)`: the first block of the period is the ancestor at
`nHeight - 2015`. -/
def ChainState.requiredBits (S : ChainState) : BitVec 32 :=
let first := (S.headers.getD (S.tipHeight - (BitcoinPow.difficultyAdjustmentInterval - 1)) BitcoinSer.genesisHeader)
BitcoinPow.nextWorkRequired S.tipHeight (BitVec.ofNat 32 S.tip.bits) S.tip.time first.time
/-- `GetBlockProof`: `(~target / (target + 1)) + 1` on 256-bit words, zero for an invalid target. -/
def blockProof (bits : Nat) : Nat :=
match BitcoinPow.deriveTarget (BitVec.ofNat 32 bits) with
| none => 0
| some t => (BitcoinPow.width - 1 - t) / (t + 1) + 1
/-- `nChainWork`. -/
def ChainState.chainWork (S : ChainState) : Nat := (S.headers.map fun h => blockProof h.bits).sum
/-- The hash of a block as a 256-bit number (`uint256` is little-endian). -/
def hashValue (h : Header) : Nat := BitcoinSer.leVal (BitcoinSer.headerHash h)
/-! ### `CheckBlock` -/
def merkleCombine (a b : Bytes) : Bytes := BitcoinSer.hash256 (a ++ b)
def zeroHash : Bytes := List.replicate 32 0
/-- `BlockMerkleRoot(block, &mutated)`. -/
def blockMerkleRoot (b : Block) : Bytes × Bool :=
BitcoinMerkle.computeMerkleRoot merkleCombine zeroHash (b.vtx.map BitcoinSer.txid)
/-- `BlockWitnessMerkleRoot`: the coinbase's witness hash is zero. -/
def blockWitnessMerkleRoot (b : Block) : Bytes :=
(BitcoinMerkle.computeMerkleRoot merkleCombine zeroHash (zeroHash :: (b.vtx.drop 1).map BitcoinSer.wtxid)).1
/-- `CheckProofOfWork(block.GetHash(), block.nBits)`. -/
def checkHeaderPow (h : Header) : Bool := BitcoinPow.checkProofOfWork (hashValue h) (BitVec.ofNat 32 h.bits)
/-- `CheckBlock` with `fCheckPOW` and `fCheckMerkleRoot`, in source order. -/
def checkBlock (b : Block) : Bool :=
checkHeaderPow b.header &&
decide ((blockMerkleRoot b).1 = b.header.merkleRoot) && !(blockMerkleRoot b).2 &&
!b.vtx.isEmpty && decide (b.vtx.length * WITNESS_SCALE_FACTOR ≤ MAX_BLOCK_WEIGHT) &&
decide ((BitcoinSer.serBlock false b).length * WITNESS_SCALE_FACTOR ≤ MAX_BLOCK_WEIGHT) &&
isCoinBase (b.vtx.headD BitcoinSer.genesisCoinbase) &&
(b.vtx.drop 1).all (fun tx => !isCoinBase tx) &&
b.vtx.all checkTransaction &&
decide ((b.vtx.map legacySigOpCount).sum * WITNESS_SCALE_FACTOR ≤ MAX_BLOCK_SIGOPS_COST)
/-! ### `ContextualCheckBlock` -/
/-- `CScript() << nHeight` for a non-negative height. -/
def heightScript (n : Nat) : Bytes :=
if n = 0 then [0] else if n ≤ 16 then [BitVec.ofNat 8 (0x50 + n)]
else BitcoinSig.pushBytes (BitcoinScript.serialize n)
/-- `GetWitnessCommitmentIndex`: the last coinbase output of at least 38 bytes starting with
`6a 24 aa 21 a9 ed`. -/
def isCommitmentOutput (o : TxOut) : Bool :=
decide (MINIMUM_WITNESS_COMMITMENT ≤ o.scriptPubKey.length) &&
decide (o.scriptPubKey.take 6 = [0x6a, 0x24, 0xaa, 0x21, 0xa9, 0xed])
def witnessCommitmentIndex (b : Block) : Option Nat :=
match b.vtx with
| [] => none
| cb :: _ => ((List.range cb.vout.length).filter fun i => isCommitmentOutput (cb.vout.getD i ⟨0, []⟩)).getLast?
/-- `CheckWitnessMalleation(block, expect_witness_commitment)`. -/
def checkWitnessMalleation (b : Block) (expect : Bool) : Bool :=
let noWitness := b.vtx.all fun tx => !tx.hasWitness
if expect then
match witnessCommitmentIndex b with
| none => noWitness
| some pos =>
let cb := b.vtx.headD BitcoinSer.genesisCoinbase
let stack := (cb.vin.headD ⟨⟨[], 0⟩, [], 0, []⟩).witness
match stack with
| [nonce] =>
decide (nonce.length = 32) &&
decide (BitcoinSer.hash256 (blockWitnessMerkleRoot b ++ nonce) =
((cb.vout.getD pos ⟨0, []⟩).scriptPubKey.drop 6).take 32)
| _ => false
else noWitness
/-- `ContextualCheckBlock(block, pindexPrev)`: finality against the lock-time cutoff, the BIP34
coinbase height, the witness commitment, and the weight limit. -/
def contextualCheckBlock (S : ChainState) (b : Block) : Bool :=
let height := S.nextHeight
let cutoff : Int := if BitcoinActivation.activeAfter S.tipHeight .csv then S.mtp else (b.header.time : Int)
b.vtx.all (fun tx => isFinalTx tx height cutoff) &&
(!BitcoinActivation.activeAfter S.tipHeight .heightInCB ||
(heightScript height).isPrefixOf ((b.vtx.headD BitcoinSer.genesisCoinbase).vin.headD ⟨⟨[], 0⟩, [], 0, []⟩).scriptSig) &&
checkWitnessMalleation b (BitcoinActivation.activeAfter S.tipHeight .segwit) &&
decide (BitcoinSer.blockWeight b ≤ MAX_BLOCK_WEIGHT)
/-! ### `ConnectBlock` -/
/-- `fEnforceBIP30 || nHeight >= BIP34_IMPLIES_BIP30_LIMIT`: the BIP30 scan is performed unless the
block is one of the two repeats or the BIP34 activation block is an ancestor with the expected hash,
and always from height 1983702 on. -/
def bip30Checked (S : ChainState) (height : Nat) (hash : Bytes) : Bool :=
let bip34Ancestor := match S.headers[BitcoinHeader.BIP34Height]? with
| some h => decide (BitcoinSer.headerHash h = bip34Hash)
| none => false
(!isBIP30Repeat height hash && !bip34Ancestor) || decide (BIP34_IMPLIES_BIP30_LIMIT ≤ height)
/-- The BIP30 scan: no output of the block already exists as an unspent coin. -/
def bip30Ok (u : Ledger) (b : Block) : Bool :=
b.vtx.all fun tx => (List.range tx.vout.length).all fun o => !haveCoin u ⟨BitcoinSer.txid tx, o⟩
/-- `ConnectBlock` after `CheckBlock`: the genesis shortcut, BIP30, the flags, the loop, the coinbase
bound. Returns the new ledger and the undo data. -/
def connectBlock (S : ChainState) (b : Block) : Option (Ledger × BlockUndo) :=
let hash := BitcoinSer.headerHash b.header
let height := S.nextHeight
if hash = BitcoinSer.genesisHash then some (S.utxo, [])
else if bip30Checked S height hash && !bip30Ok S.utxo b then none
else
let flags := BitcoinActivation.blockScriptFlags height (scriptException hash)
match connectLoop flags height S.mtpNat (BitcoinActivation.lockTimeFlags height) ⟨S.utxo, 0, 0, []⟩ b.vtx with
| none => none
| some st =>
if valueOut (b.vtx.headD BitcoinSer.genesisCoinbase) >
st.fees + (BitcoinSubsidy.coreSubsidy height : Int) then none
else some (st.utxo, st.undo)
/-! ### The complete validation path -/
/-- The outcome of offering a block to a chain state: accepted with the new state and undo data;
rejected as invalid; rejected only because its time is too far in the future (`BLOCK_TIME_FUTURE`);
or not building on the tip (`BLOCK_MISSING_PREV`). -/
inductive Outcome where
| accept (S' : ChainState) (undo : BlockUndo)
| invalid
| futureTime
| missingPrev
/-- `AcceptBlockHeader` for a header on top of the tip: `CheckBlockHeader` (proof of work), the
previous-block lookup, then `ContextualCheckBlockHeader` in source order (`nBits`, `time-too-old`,
`time-too-new`, the version floors). `now` is the local clock. -/
def acceptHeader (S : ChainState) (h : Header) (now : Int) : Outcome :=
if !checkHeaderPow h then .invalid
else if h.prevBlock ≠ S.tipHash then .missingPrev
else if BitVec.ofNat 32 h.bits ≠ S.requiredBits then .invalid
else if (h.time : Int) ≤ S.mtp then .invalid
else if now + MAX_FUTURE_BLOCK_TIME < (h.time : Int) then .futureTime
else if BitcoinHeader.versionOutdated h.version S.tipHeight then .invalid
else .accept S []
/-- The source-linked validation outcome `C(S, B, t)`: the header path, `CheckBlock`,
`ContextualCheckBlock`, `ConnectBlock`. -/
def validate (S : ChainState) (b : Block) (now : Int) : Outcome :=
match acceptHeader S b.header now with
| .accept _ _ =>
if !checkBlock b then .invalid
else if !contextualCheckBlock S b then .invalid
else match connectBlock S b with
| none => .invalid
| some (u, undo) => .accept ⟨S.headers ++ [b.header], u⟩ undo
| o => o
def accepts (S : ChainState) (b : Block) (now : Int) : Prop := ∃ S' undo, validate S b now = .accept S' undo
/-- Reachability from the genesis state through accepted blocks. -/
inductive Reachable : ChainState → Prop
| genesis : Reachable initialState
| step {S : ChainState} {b : Block} {now : Int} {S' : ChainState} {undo : BlockUndo} :
Reachable S → validate S b now = .accept S' undo → Reachable S'
/-! ### `DisconnectBlock` -/
/-- `ApplyTxInUndo`: restore a spent coin; `none` is `DISCONNECT_FAILED`, the flag is `fClean`. -/
def applyTxInUndo (u : Ledger) (undo : Coin) (out : OutPoint) : Option (Ledger × Bool) :=
let clean := !haveCoin u out
let undo? : Option Coin :=
if undo.height = 0 then
match u.find? (fun e => e.1.hash = out.hash) with
| some (_, alt) => some { undo with height := alt.height, isCoinbase := alt.isCoinbase }
| none => none
else some undo
match undo? with
| none => none
| some c => some (addCoin u out c, clean)
/-- Restore the inputs of a transaction in reverse order. -/
def restoreInputs (u : Ledger) : List (TxIn × Coin) → Option (Ledger × Bool)
| [] => some (u, true)
| (i, c) :: rest =>
match restoreInputs u rest with
| none => none
| some (u', clean) =>
match applyTxInUndo u' c i.prevout with
| none => none
| some (u'', clean') => some (u'', clean && clean')
/-- Spend the (spendable) outputs of a transaction, checking each against the block. -/
def spendOutputs (u : Ledger) (txid : Bytes) (height : Nat) (cb : Bool) (exception : Bool) :
List TxOut → Nat → Ledger × Bool
| [], _ => (u, true)
| o :: rest, i =>
let (u', clean) :=
if isUnspendable o.scriptPubKey then (u, true)
else
let op : OutPoint := ⟨txid, i⟩
let ok := match getCoin u op with
| none => false
| some coin => decide (coin.out = o) && decide (coin.height = height) && decide (coin.isCoinbase = cb)
(spendCoin u op, ok || exception)
let (u'', clean') := spendOutputs u' txid height cb exception rest (i + 1)
(u'', clean && clean')
/-- Undo one transaction: its outputs, then (for a non-coinbase) its inputs. -/
def disconnectTx (u : Ledger) (height : Nat) (exception : Bool) (tx : Tx) (undo : Option (List Coin)) :
Option (Ledger × Bool) :=
let cb := isCoinBase tx
let (u', clean) := spendOutputs u (BitcoinSer.txid tx) height cb (cb && exception) tx.vout 0
match undo with
| none => some (u', clean)
| some coins =>
if coins.length ≠ tx.vin.length then none
else match restoreInputs u' (tx.vin.zip coins) with
| none => none
| some (u'', clean') => some (u'', clean && clean')
def disconnectTxs (height : Nat) (exception : Bool) : Ledger → List (Tx × Option (List Coin)) → Option (Ledger × Bool)
| u, [] => some (u, true)
| u, (tx, undo) :: rest =>
match disconnectTx u height exception tx undo with
| none => none
| some (u', clean) =>
match disconnectTxs height exception u' rest with
| none => none
| some (u'', clean') => some (u'', clean && clean')
/-- `DisconnectBlock(block, pindex, view)`: the undo-count test, the two unspendable-coinbase
exceptions, and the transactions in reverse order. -/
def disconnectBlock (u : Ledger) (height : Nat) (hash : Bytes) (b : Block) (undo : BlockUndo) :
Option (Ledger × Bool) :=
if undo.length + 1 ≠ b.vtx.length then none
else disconnectTxs height (isBIP30Unspendable height hash) u
((b.vtx.zip (none :: undo.map some)).reverse)
/-! ### The declarative specification `V(S, B, t)` and `ApplySpec` -/
/-- Transaction well-formedness, as a predicate. -/
def TxSpec (tx : Tx) : Prop :=
tx.vin ≠ [] ∧ tx.vout ≠ [] ∧
(BitcoinSer.serTx false tx).length * WITNESS_SCALE_FACTOR ≤ MAX_BLOCK_WEIGHT ∧
(∀ o ∈ tx.vout, 0 ≤ o.nValue ∧ o.nValue ≤ MAX_MONEY) ∧ valueOut tx ≤ MAX_MONEY ∧
(tx.vin.map TxIn.prevout).Nodup ∧
(isCoinBase tx = true → ∀ i ∈ tx.vin, 2 ≤ i.scriptSig.length ∧ i.scriptSig.length ≤ 100) ∧
(isCoinBase tx = false → ∀ i ∈ tx.vin, outPointNull i.prevout = false)
/-- The sum of the values of the coins spent by the inputs. -/
def valueIn (u : Ledger) : List TxIn → Int
| [] => 0
| i :: rest => (accessCoin u i.prevout).out.nValue + valueIn u rest
/-- The fee of a transaction against a ledger. -/
def feeOf (u : Ledger) (tx : Tx) : Int := valueIn u tx.vin - valueOut tx
/-- Admissibility of one non-coinbase transaction against the ledger `u` at `height`: every input
spends an existing, mature coin of valid value; the total input value is in range and covers the
outputs; the fee is in range; BIP68 holds (the specification form of the BIP68 mission); every
input script verifies. -/
def TxInputsSpec (f : BitcoinActivation.ScriptFlags) (u : Ledger) (height : Nat) (mtp : Nat → Nat)
(lockTimeFlags : Nat) (tx : Tx) : Prop :=
(∀ i ∈ tx.vin, ∃ c, getCoin u i.prevout = some c ∧
(c.isCoinbase = true → c.height + COINBASE_MATURITY ≤ height) ∧ 0 ≤ c.out.nValue ∧ c.out.nValue ≤ MAX_MONEY) ∧
valueIn u tx.vin ≤ MAX_MONEY ∧ valueOut tx ≤ valueIn u tx.vin ∧
BitcoinBIP68.satisfiesBIP68 (BitVec.ofNat 32 tx.version) (BitVec.ofNat 32 lockTimeFlags) ⟨height, mtp⟩
(tx.vin.map fun i => ⟨BitVec.ofNat 32 i.nSequence, (accessCoin u i.prevout).height⟩) ∧
∀ n, n < tx.vin.length →
let i := tx.vin.getD n ⟨⟨[], 0⟩, [], 0, []⟩
let coin := accessCoin u i.prevout
BitcoinTaproot.verifyScriptFull (tx.vin.map fun j => (accessCoin u j.prevout).out)
⟨f, tx, n, coin.out.nValue⟩ i.scriptSig coin.out.scriptPubKey i.witness = true
/-- The transactions of a block, applied in order: each is admissible against the ledger produced
by its predecessors, the accumulated fees and sigop cost stay within their limits. -/
def TxsSpec (f : BitcoinActivation.ScriptFlags) (height : Nat) (mtp : Nat → Nat) (lockTimeFlags : Nat) :
Ledger → Int → Nat → List Tx → Prop
| _, _, _, [] => True
| u, fees, sigOps, tx :: rest =>
(isCoinBase tx = false → TxInputsSpec f u height mtp lockTimeFlags tx ∧ fees + feeOf u tx ≤ MAX_MONEY) ∧
sigOps + txSigOpCost f u tx ≤ MAX_BLOCK_SIGOPS_COST ∧
TxsSpec f height mtp lockTimeFlags (updateCoins u tx height)
(if isCoinBase tx then fees else fees + feeOf u tx) (sigOps + txSigOpCost f u tx) rest
/-- The ledger after applying the transactions in order. -/
def applyTxs (height : Nat) : Ledger → List Tx → Ledger
| u, [] => u
| u, tx :: rest => applyTxs height (updateCoins u tx height) rest
/-- The total fees of a block's non-coinbase transactions, against the running ledger. -/
def totalFees (height : Nat) : Ledger → List Tx → Int
| _, [] => 0
| u, tx :: rest => (if isCoinBase tx then 0 else feeOf u tx) + totalFees height (updateCoins u tx height) rest
/-- The declarative state transition `ApplySpec(S, B)`. -/
def applySpec (S : ChainState) (b : Block) : ChainState :=
if BitcoinSer.headerHash b.header = BitcoinSer.genesisHash then ⟨S.headers ++ [b.header], S.utxo⟩
else ⟨S.headers ++ [b.header], applyTxs S.nextHeight S.utxo b.vtx⟩
/-- The header rules as a predicate: a valid compact target met by the hash (the PoW mission's
specification form), the tip as parent, the required difficulty, the median-time-past floor, the
clock ceiling, and the version floors. -/
def HeaderSpec (S : ChainState) (h : Header) (now : Int) : Prop :=
(BitcoinPow.compactNegative (BitVec.ofNat 32 h.bits) = false ∧
BitcoinPow.compactOverflow (BitVec.ofNat 32 h.bits) = false ∧
0 < BitcoinPow.specTarget (BitVec.ofNat 32 h.bits) ∧
BitcoinPow.specTarget (BitVec.ofNat 32 h.bits) ≤ BitcoinPow.powLimit ∧
hashValue h ≤ BitcoinPow.specTarget (BitVec.ofNat 32 h.bits)) ∧
h.prevBlock = S.tipHash ∧
BitVec.ofNat 32 h.bits = S.requiredBits ∧
S.mtp < (h.time : Int) ∧ (h.time : Int) ≤ now + MAX_FUTURE_BLOCK_TIME ∧
¬ ((h.version < 2 ∧ BitcoinHeader.BIP34Height ≤ S.tipHeight + 1) ∨
(h.version < 3 ∧ BitcoinHeader.BIP66Height ≤ S.tipHeight + 1) ∨
(h.version < 4 ∧ BitcoinHeader.BIP65Height ≤ S.tipHeight + 1))
/-- The context-free block rules as a predicate. -/
def BlockSpec (b : Block) : Prop :=
b.vtx ≠ [] ∧
(blockMerkleRoot b).1 = b.header.merkleRoot ∧ (blockMerkleRoot b).2 = false ∧
b.vtx.length * WITNESS_SCALE_FACTOR ≤ MAX_BLOCK_WEIGHT ∧
(BitcoinSer.serBlock false b).length * WITNESS_SCALE_FACTOR ≤ MAX_BLOCK_WEIGHT ∧
(∀ tx ∈ b.vtx.take 1, isCoinBase tx = true) ∧ (∀ tx ∈ b.vtx.drop 1, isCoinBase tx = false) ∧
(∀ tx ∈ b.vtx, TxSpec tx) ∧
(b.vtx.map legacySigOpCount).sum * WITNESS_SCALE_FACTOR ≤ MAX_BLOCK_SIGOPS_COST
/-- The contextual block rules as a predicate. -/
def ContextSpec (S : ChainState) (b : Block) : Prop :=
let height := S.nextHeight
let cutoff : Int := if BitcoinActivation.activeAfter S.tipHeight .csv then S.mtp else (b.header.time : Int)
(∀ tx ∈ b.vtx, isFinalTx tx height cutoff = true) ∧
(BitcoinActivation.activeAfter S.tipHeight .heightInCB = true →
∀ cb ∈ b.vtx.take 1, ∀ i ∈ cb.vin.take 1, (heightScript height).isPrefixOf i.scriptSig = true) ∧
checkWitnessMalleation b (BitcoinActivation.activeAfter S.tipHeight .segwit) = true ∧
BitcoinSer.blockWeight b ≤ MAX_BLOCK_WEIGHT
/-- The ledger rules as a predicate: BIP30 where it applies, the transaction sequence, and the
coinbase bound against the specification subsidy. -/
def LedgerSpec (S : ChainState) (b : Block) : Prop :=
let hash := BitcoinSer.headerHash b.header
let height := S.nextHeight
let flags := BitcoinActivation.blockScriptFlags height (scriptException hash)
hash = BitcoinSer.genesisHash ∨
((bip30Checked S height hash = true →
∀ tx ∈ b.vtx, ∀ o, o < tx.vout.length → getCoin S.utxo ⟨BitcoinSer.txid tx, o⟩ = none) ∧
TxsSpec flags height S.mtpNat (BitcoinActivation.lockTimeFlags height) S.utxo 0 0 b.vtx ∧
∀ cb ∈ b.vtx.take 1,
valueOut cb ≤ totalFees height S.utxo b.vtx + (BitcoinSubsidy.specSubsidy height : Int))
/-- Declarative admissibility `V(S, B, t)`. -/
def Valid (S : ChainState) (b : Block) (now : Int) : Prop :=
HeaderSpec S b.header now ∧ BlockSpec b ∧ ContextSpec S b ∧ LedgerSpec S b
/-- A ledger with distinct keys whose coins are spendable and were created above the genesis. -/
def LedgerOk (u : Ledger) : Prop :=
keysNodup u ∧ ∀ e ∈ u, e.2.height ≠ 0 ∧ isUnspendable e.2.out.scriptPubKey = false
/-- The well-formedness every reachable state enjoys: a non-empty header list starting at the
genesis, distinct ledger keys, and spendable coins created at heights `1..tip`. -/
def WellFormed (S : ChainState) : Prop :=
S.headers.head? = some BitcoinSer.genesisHeader ∧ keysNodup S.utxo ∧
∀ e ∈ S.utxo, 1 ≤ e.2.height ∧ e.2.height ≤ S.tipHeight ∧ isUnspendable e.2.out.scriptPubKey = false
end BitcoinBlock
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_BitcoinBlock.lean (namespace BitcoinBlock)
This file imports the serialization, script, signature, verification, Taproot, activation, header, proof-of-work, subsidy, merkle, BIP68 and UTXO developments. Of these, the UTXO development (Def_BitcoinUtxo) is imported but no declaration of this file refers to it; the file defines its own ledger notions. Throughout, "byte list" means a list of 8-bit words; "transaction", "input", "output", "outpoint", "header" and "block" are the serialization development's records: an outpoint is ; an input has a prevout, a scriptSig (byte list), a sequence and a witness (list of byte lists); an output has a value and a scriptPubKey (byte list); a transaction has a version , inputs, outputs and a lock time ; a header has version , prevBlock and merkleRoot (byte lists), time, bits and nonce ; a block is a header with a transaction list. No field is bounded by its type. The "default input" used by several defaults below is (empty prevout hash, index , empty scriptSig, sequence , no witness) and the "default output" is . denotes .
Constants
MAX_BLOCK_WEIGHT is the natural number .
MAX_BLOCK_SIGOPS_COST is the natural number .
WITNESS_SCALE_FACTOR is the natural number .
LOCKTIME_THRESHOLD is the natural number .
SEQUENCE_FINAL is the natural number .
MINIMUM_WITNESS_COMMITMENT is the natural number .
BIP34_IMPLIES_BIP30_LIMIT is the natural number .
MAX_FUTURE_BLOCK_TIME is the integer . (A constant of the same name and value exists separately in the header development.)
COINBASE_MATURITY is the natural number .
MAX_MONEY is the integer .
moneyRange is the Boolean .
bip34Hash is a fixed 32-byte list beginning and ending with six zero bytes (the BIP34 block hash in internal byte order).
bip16ExceptionHash is a fixed 32-byte list beginning and ending with six zero bytes.
taprootExceptionHash is a fixed 32-byte list beginning and ending with nine zero bytes.
bip30Repeat91842 is a fixed 32-byte list beginning and ending with five zero bytes.
bip30Repeat91880 is a fixed 32-byte list beginning and ending with five zero bytes.
bip30Unspendable91722 is a fixed 32-byte list beginning and ending with five zero bytes.
bip30Unspendable91812 is a fixed 32-byte list beginning and ending with five zero bytes.
isBIP30Repeat is the Boolean , with byte-list equality.
isBIP30Unspendable is the Boolean .
scriptException returns the activation development's exception tag: bip16Block if , else taprootBlock if , else none. (Downstream, bip16Block yields no script flags at all as base, taprootBlock yields P2SH and witness only, none yields P2SH, witness and Taproot.)
Transactions
outPointNull is the Boolean: equals the list of zero bytes and .
isCoinBase is true iff is a list of exactly one input and that input's prevout is null in the above sense; for zero or two-or-more inputs it is false.
isUnspendable is the Boolean: ( and the byte at index (default ) equals OP_RETURN ) or (MAX_SCRIPT_SIZE from the verification development).
sumValues maps a list of outputs to the integer sum of their values ( for the empty list), computed by prepending: .
valueOut .
outputsLoop returns an optional integer: on the empty list, ; on : none if ; else none if ; else none if ; else recurse on with .
checkTransaction is the Boolean conjunction, in order: non-empty; non-empty; (witness-free serialization length); is some value; the list of prevouts of has no duplicates; and, if , then the scriptSig length of the head of (default input if empty) satisfies , otherwise every input of has a non-null prevout.
isFinalTx : true if ; otherwise let the threshold be (as an integer) if and otherwise; true if threshold; otherwise true iff every input of has (vacuously true with no inputs).
Signature-operation counting
sigOpCountAux takes and returns a natural number: if is empty, ; else if , ; otherwise parse one instruction from with the signature development's getOp (a byte is a push of the indicated data, with the PUSHDATA1/2/4 length forms; a byte is an opcode; a truncated push yields a parse failure): on failure, ; on a push with remainder , recurse with , , and unchanged; on an opcode with remainder : if is OP_CHECKSIG () or OP_CHECKSIGVERIFY (); if is OP_CHECKMULTISIG () or OP_CHECKMULTISIGVERIFY () and and (via decodeOpN, which maps to and to ); for those two opcodes otherwise; for any other opcode; then recurse with , , and .
getSigOpCount : fuel is the byte length, the initial "last opcode" is , the initial count .
lastPushAux returns an optional byte list: if is empty, ; else if , none; else parse one instruction: failure gives none; a push of data recurses with ; an opcode gives none if OP_16 , otherwise recurses with .
lastPush : the data of the last push instruction of a script all of whose instructions are pushes or opcodes (an opcode resets the result to the empty list), or none if some instruction fails to parse or is an opcode above ; the empty script gives .
p2shSigOpCount : if is not pay-to-script-hash (exactly bytes with byte , byte , byte ), then ; otherwise if is none, else for the last pushed data .
witnessSigOps : if : when ; when and the witness is non-empty (the last element defaults to if absent, but that branch requires non-emptiness); otherwise . For any other version, .
countWitnessSigOps : if is false; else if is a witness program (length in , first byte or in , second byte equal to the length minus ) with version and program , then ; else if is pay-to-script-hash and is push-only (every instruction parses and is a push or an opcode ), then: if is none; else, with the last push , if is a witness program and otherwise; else .
legacySigOpCount is .
The ledger
Coin is a record with decidable equality.
dummyCoin is the coin : value , empty script, height , not coinbase.
Ledger is an abbreviation for lists of pairs (outpoint, coin). Nothing enforces distinct keys.
getCoin scans from the front and returns for the first pair with , or none.
haveCoin is the Boolean " is some".
accessCoin is if present, otherwise .
spendCoin returns with every pair whose key equals removed, order otherwise preserved.
addCoin : if is unspendable (starts with or exceeds bytes), unchanged; otherwise prepended to .
addCoinsFrom takes and folds: for the empty list, ; for , recurse on with index from .
spendInputs folds over the inputs' prevouts in order.
updateCoins is applied to (if then else ), starting index , over . Here is the double-SHA256 of the witness-free serialization.
txUndo is the list (dummy coins for missing entries).
BlockUndo abbreviates lists of lists of coins.
Equiv is the proposition .
keysNodup is the proposition that the list of first components of has no duplicates.
CheckTxInputs and the per-transaction checks
inputsLoop takes : on the empty list, ; on : if is none, none; else with coin : none if and (natural subtraction, so this fires whenever , including ); else let ; none if or ; else recurse with .
checkTxInputs returns an optional integer fee: none if some input's prevout has no coin in ; else none if is none; else with its value: none if ; none if ; else .
txSigOpCost where if , and otherwise if , else , sums over (missing coins contribute the dummy's empty script).
sequenceLocksOk is the BIP68 core development's sequenceLocks applied to version , flags , context and the input list : with BIP68 enabled (version and flag bit set), fold the inputs into integer minima starting at — an input with bit set contributes nothing; with bit set it raises to ; otherwise it raises to — and return ; with BIP68 not enabled, the minima stay and the result is true.
inputScriptsOk : let ; for every index , with the -th input (default input if out of range, which cannot happen) and , the Taproot development's verifyScriptFull holds on , context , , and — the complete VerifyScript: evaluate scriptSig then scriptPubKey on the stack, require a true top, then the native witness-program branch (when ; scriptSig must be empty), the P2SH branch (when ; push-only scriptSig, redeem script evaluation, nested witness program requiring the scriptSig to be exactly the canonical push of the redeem script), and the rule that a non-empty witness with no witness program fails; Taproot spends are dispatched to the Taproot handler with the spent-outputs list.
LoopState is a record .
connectLoop takes and returns an optional loop state: on the empty list, ; on : compute an optional (fees, undo) "step": if , ; else none if is none, else with fee : none if ; none if is false; else . If the step is none, none. Otherwise let : none if ; none if is not a coinbase and is false; else recurse on from . The coinbase test is positional-agnostic: any coinbase-shaped transaction anywhere skips the input checks and the undo record.
Chain state
ChainState is a record .
initialState is : the mainnet genesis header alone and an empty ledger (the genesis coinbase output is not present).
ChainState.tipHeight with natural subtraction ( for an empty list).
ChainState.tip is the last header of , or if the list is empty.
ChainState.tipHash , the double-SHA256 of the 80-byte serialization (version as 4 little-endian bytes modulo , prevBlock bytes, merkleRoot bytes, time, bits, nonce each as 4 little-endian bytes modulo ).
ChainState.nextHeight .
ChainState.timesTo is the list of the times (cast to ) of the first headers of , reversed (so most recent first); fewer if the list is shorter.
ChainState.mtpAt is the header development's medianTimePast of : take the first elements, sort ascending, return the element at index , with default for an empty window.
ChainState.mtp .
ChainState.mtpNat as a natural number (negative medians become ).
ChainState.requiredBits : let be the header at index (natural subtraction; ), defaulting to when out of range; the result is the proof-of-work development's nextWorkRequired with last height , last bits , last time and first time (both cast to ): the last bits unchanged if , otherwise the retarget (decode the last target, multiply by the actual timespan clamped to modulo , divide by , cap at , re-encode as a compact word).
blockProof : with deriveTarget of — none if the compact word is negative, decodes to , overflows, or exceeds — the result is on none, and on (natural subtraction and floor division).
ChainState.chainWork .
hashValue is the little-endian numeric value of (byte weighted by ).
CheckBlock
merkleCombine , double-SHA256 of the concatenation.
zeroHash is the list of zero bytes.
blockMerkleRoot is the merkle development's computeMerkleRoot with combiner and empty-root on : a pair (root, mutated). The loop: while more than one hash remains, set mutated if some aligned pair (positions , , both present) is equal, then replace the level by the combiner applied to aligned pairs, the odd last element combined with itself; the root is the remaining element, or for an empty list; mutated starts false.
blockWitnessMerkleRoot is the root component of the same computation on , where is the double-SHA256 of the witness serialization when the transaction has a witness, else the txid.
checkHeaderPow is the proof-of-work development's checkProofOfWork on and : false if deriveTarget is none, else .
checkBlock is the Boolean conjunction, in order: ; ; ; non-empty; ; ; of the head of (default ); every element of is not a coinbase; every element of passes ; .
ContextualCheckBlock
heightScript : if ; (one byte) if ; otherwise the signature development's canonical push (pushBytes: a length byte for data shorter than bytes, else a PUSHDATA1/2/4 prefix) of the script development's serialize of (the little-endian magnitude bytes with a sign byte appended when the top bit of the last byte is set).
isCommitmentOutput is the Boolean and the first six bytes of are .
witnessCommitmentIndex : none if is empty; otherwise, with the first transaction, the last index such that the -th output (default output if out of range) satisfies , or none if there is no such index.
checkWitnessMalleation : let be "every transaction of has no input with a non-empty witness". If is false, return . If true: if is none, return ; else with position , let be the head of (default ) and the witness of the head of (default input): if is exactly , return and equals the bytes of the -th output's scriptPubKey (default output) after dropping bytes; for a stack of any other length (including empty), return false.
contextualCheckBlock : let and if the activation development's activeAfter (i.e. ) else as an integer. The Boolean conjunction of: every transaction satisfies ; not activeAfter () or is a prefix of the scriptSig of the head input (default input) of the head transaction (default ); (); and where .
ConnectBlock
bip30Checked : let be: if has an element at index then else false. Result: .
bip30Ok : for every transaction of and every index , is not a key of (all outputs counted, including unspendable ones).
connectBlock returns an optional (ledger, undo): let and . If (the fixed 32-byte constant beginning ), return without any further check. Else if and not , none. Else let be the activation development's blockScriptFlags (base per the exception, then DERSIG when , CLTV when , CSV when , NULLDUMMY when ), and run where lockTimeFlags is if else : none on failure; else with final state : none if , where if and otherwise; else .
The complete validation path
Outcome is an inductive type with four constructors: accept carrying a chain state and a block undo; invalid; futureTime; missingPrev.
acceptHeader : invalid if ; else missingPrev if ; else invalid if ; else invalid if ; else futureTime if ; else invalid if the header development's versionOutdated ( and , or and , or and ); else accept (the unchanged state and the empty undo).
validate : match : on accept (payload ignored): invalid if ; else invalid if ; else on : invalid if none, and accept if ; on any other header outcome, that outcome.
accepts is the proposition .
Reachable is the inductive predicate on chain states generated by: genesis: ; step: for implicit , from and conclude .
DisconnectBlock
applyTxInUndo returns an optional (ledger, Bool): let . If : search for the first entry whose key hash equals (index ignored); if found with coin , the coin to restore is with height and coinbase flag replaced by 's; if not found, return none. If , the coin to restore is itself. Return (so an unspendable coin is silently not added).
restoreInputs : on the empty list, ; on : first (so the tail, i.e. later inputs, is restored first); none propagates; then ; none propagates; result is the new ledger with the conjunction of the two clean flags.
spendOutputs takes and returns a (ledger, Bool) pair — never none: on the empty list, ; on : if is unspendable, for this output; otherwise with , let be false if is not a key of and otherwise "the stored coin equals componentwise"; this output yields ; then recurse on with from that ledger and and the flags.
disconnectTx : let and . If is none, . If : none if ; else , none propagating, with the clean flags and-ed.
disconnectTxs takes : on the empty list, ; else apply to the head, none propagating, then recurse on the tail from the resulting ledger, none propagating, and-ing the flags.
disconnectBlock : none if ; otherwise where is the reverse of : the first transaction is paired with no undo record, the -th with the -th undo entry, and the pairs are processed last-to-first.
The declarative specification and ApplySpec
TxSpec is the proposition: ; ; ; every output value has ; ; prevouts pairwise distinct; every input's scriptSig length lies in ; every input has .
valueIn is over , computed by prepending; a missing coin contributes .
feeOf .
TxInputsSpec is the conjunction: for every input there is a coin with , , and ; ; ; the BIP68 model's satisfiesBIP68 on version , flags , context and inputs (BIP68 not enabled, or every input disabled (bit 31) or satisfying when bit 22 is set and otherwise); and for every , with the -th input (default input) and , verifyScriptFull on the spent list , context , , , equals true.
TxsSpec on : true for the empty list; for : , and , and on from , fees if coinbase else , and sigops . No lower bound on the fee total is stated.
applyTxs on : the left fold of over the list.
totalFees on : for the empty list; for , ( if else ) plus on from .
applySpec : if then , else .
HeaderSpec is the conjunction: [the proof-of-work development's compactNegative of is false, compactOverflow is false, , specTarget , and specTarget], where specTarget is the exact value mantissa (floor-divided when the exponent is ) with no truncation; ; ; and ; and .
BlockSpec is the conjunction: ; and ; ; ; every has and every has ; every satisfies ; .
ContextSpec : with and as in : every has ; activeAfter is a prefix of (vacuous with no transactions or no inputs); ; .
LedgerSpec : with , and blockScriptFlags: , or [ and and ], where (the subsidy development's declarative schedule, distinct from coreSubsidy used by ).
Valid is .
LedgerOk is and every entry of has and . (Not referenced by any of the nineteen theorem statements.)
WellFormed is: the head of is ; ; and every entry of has , , and .
Edge cases and defaults the file silently includes
Empty header lists (, tip and retarget-anchor default to the genesis header, median ); empty transaction lists (head defaults to the genesis coinbase in checkBlock, checkWitnessMalleation, contextualCheckBlock, connectBlock's coinbase bound); empty input lists (default input with empty scriptSig and witness); getD/headD/getLastD defaults throughout; natural subtraction in tipHeight, the retarget index, coinbase maturity, and in BIP68, and blockProof; modulo- reductions of bits, version, sequence and flags; accessCoin's dummy coin (value , height ) feeding valueIn, feeOf, txUndo, txSigOpCost, sequenceLocksOk and inputScriptsOk when a prevout is missing; ledgers with duplicate keys (first match wins on lookup, all matches removed on spend); coinbase-shaped transactions in non-first positions treated as coinbases by the loop, updateCoins and the specifications; the genesis-hash shortcut in connectBlock, applySpec and LedgerSpec; fuel-bounded script scans that stop silently at the byte length.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.