Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Block validation composed: header path, CheckBlock, ContextualCheckBlock, ConnectBlock, DisconnectBlock, and the declarative specification

Definition
BitcoinBlock

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

bip30bip34bitcoinbitcoin-mainnetblock-validationconnectblockconsensusformal-verificationundo

Constants. 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 C(S,B,t)C(S,B,t)C(S,B,t) 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 (ApplySpec(S,B)\mathrm{ApplySpec}(S,B)ApplySpec(S,B)), 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 (V(S,B,t)V(S,B,t)V(S,B,t)), 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.

Definition code
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
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: AcceptBlockHeader, CheckBlockHeader, ContextualCheckBlockHeader, CheckBlock, CheckMerkleRoot, CheckWitnessMalleation, ContextualCheckBlock, ConnectBlock, GetBlockScriptFlags, IsBIP30Repeat, IsBIP30Unspendable, UpdateCoins, DisconnectBlock, ApplyTxInUndo, src/validation.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/validation.cpp; CheckTransaction (consensus/tx_check.cpp); IsFinalTx, GetLegacySigOpCount, GetP2SHSigOpCount, GetTransactionSigOpCost, CheckTxInputs (consensus/tx_verify.cpp); CScript::GetSigOpCount, IsUnspendable (script/script.cpp, script.h); CountWitnessSigOps (script/interpreter.cpp); AddCoin, SpendCoin, AddCoins (coins.cpp); GetBlockProof (chain.cpp); GetWitnessCommitmentIndex, GetBlockWeight (consensus/validation.h); CMainParams (kernel/chainparams.cpp)
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)

Read-back: 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 ⟨hash:byte list,n∈N⟩\langle \mathrm{hash} : \text{byte list}, n \in \mathbb{N}\rangle⟨hash:byte list,n∈N⟩; an input has a prevout, a scriptSig (byte list), a sequence ∈N\in \mathbb{N}∈N and a witness (list of byte lists); an output has a value ∈Z\in \mathbb{Z}∈Z and a scriptPubKey (byte list); a transaction has a version ∈N\in \mathbb{N}∈N, inputs, outputs and a lock time ∈N\in \mathbb{N}∈N; a header has version ∈Z\in \mathbb{Z}∈Z, prevBlock and merkleRoot (byte lists), time, bits and nonce ∈N\in \mathbb{N}∈N; 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 ⟨⟨[ ],0⟩,[ ],0,[ ]⟩\langle\langle [\,], 0\rangle, [\,], 0, [\,]\rangle⟨⟨[],0⟩,[],0,[]⟩ (empty prevout hash, index 000, empty scriptSig, sequence 000, no witness) and the "default output" is ⟨0,[ ]⟩\langle 0, [\,]\rangle⟨0,[]⟩. MMM denotes 2 100 000 000 000 0002\,100\,000\,000\,000\,0002100000000000000.

Constants

MAX_BLOCK_WEIGHT is the natural number 4 000 0004\,000\,0004000000.

MAX_BLOCK_SIGOPS_COST is the natural number 80 00080\,00080000.

WITNESS_SCALE_FACTOR is the natural number 444.

LOCKTIME_THRESHOLD is the natural number 500 000 000500\,000\,000500000000.

SEQUENCE_FINAL is the natural number 0xffffffff=42949672950xffffffff = 42949672950xffffffff=4294967295.

MINIMUM_WITNESS_COMMITMENT is the natural number 383838.

BIP34_IMPLIES_BIP30_LIMIT is the natural number 1 983 7021\,983\,7021983702.

MAX_FUTURE_BLOCK_TIME is the integer 2⋅60⋅60=72002\cdot 60\cdot 60 = 72002⋅60⋅60=7200. (A constant of the same name and value exists separately in the header development.)

COINBASE_MATURITY is the natural number 100100100.

MAX_MONEY is the integer 2 100 000 000 000 000=M2\,100\,000\,000\,000\,000 = M2100000000000000=M.

moneyRange (v∈Z)(v \in \mathbb{Z})(v∈Z) is the Boolean 0≤v∧v≤M0 \le v \wedge v \le M0≤v∧v≤M.

bip34Hash is a fixed 32-byte list beginning b8 08 08 9c 75 6a dd 15b8\,08\,08\,9c\,75\,6a\,dd\,15b808089c756add15 and ending with six zero bytes (the BIP34 block hash in internal byte order).

bip16ExceptionHash is a fixed 32-byte list beginning 22 9c 4f ac 88 ba b1 9422\,9c\,4f\,ac\,88\,ba\,b1\,94229c4fac88bab194 and ending with six zero bytes.

taprootExceptionHash is a fixed 32-byte list beginning ad 95 e3 a1 5e e5 ff d5ad\,95\,e3\,a1\,5e\,e5\,ff\,d5ad95e3a15ee5ffd5 and ending with nine zero bytes.

bip30Repeat91842 is a fixed 32-byte list beginning ec ca e0 00 e3 c8 e4 e0ec\,ca\,e0\,00\,e3\,c8\,e4\,e0eccae000e3c8e4e0 and ending with five zero bytes.

bip30Repeat91880 is a fixed 32-byte list beginning 21 d7 7c cb 4c 08 38 6a21\,d7\,7c\,cb\,4c\,08\,38\,6a21d77ccb4c08386a and ending with five zero bytes.

bip30Unspendable91722 is a fixed 32-byte list beginning 8e d0 4d 57 f2 f3 cd c68e\,d0\,4d\,57\,f2\,f3\,cd\,c68ed04d57f2f3cdc6 and ending with five zero bytes.

bip30Unspendable91812 is a fixed 32-byte list beginning 2f 6f 30 f9 d6 83 de b82f\,6f\,30\,f9\,d6\,83\,de\,b82f6f30f9d683deb8 and ending with five zero bytes.

isBIP30Repeat (height∈N,hash)(\mathit{height} \in \mathbb{N}, \mathit{hash})(height∈N,hash) is the Boolean (height=91842∧hash=bip30Repeat91842)∨(height=91880∧hash=bip30Repeat91880)(\mathit{height} = 91842 \wedge \mathit{hash} = \mathrm{bip30Repeat91842}) \vee (\mathit{height} = 91880 \wedge \mathit{hash} = \mathrm{bip30Repeat91880})(height=91842∧hash=bip30Repeat91842)∨(height=91880∧hash=bip30Repeat91880), with byte-list equality.

isBIP30Unspendable (height,hash)(\mathit{height}, \mathit{hash})(height,hash) is the Boolean (height=91722∧hash=bip30Unspendable91722)∨(height=91812∧hash=bip30Unspendable91812)(\mathit{height} = 91722 \wedge \mathit{hash} = \mathrm{bip30Unspendable91722}) \vee (\mathit{height} = 91812 \wedge \mathit{hash} = \mathrm{bip30Unspendable91812})(height=91722∧hash=bip30Unspendable91722)∨(height=91812∧hash=bip30Unspendable91812).

scriptException (hash)(\mathit{hash})(hash) returns the activation development's exception tag: bip16Block if hash=bip16ExceptionHash\mathit{hash} = \mathrm{bip16ExceptionHash}hash=bip16ExceptionHash, else taprootBlock if hash=taprootExceptionHash\mathit{hash} = \mathrm{taprootExceptionHash}hash=taprootExceptionHash, 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 (o)(o)(o) is the Boolean: o.hasho.\mathrm{hash}o.hash equals the list of 323232 zero bytes and o.n=4294967295o.n = 4294967295o.n=4294967295.

isCoinBase (tx)(tx)(tx) is true iff tx.vintx.\mathrm{vin}tx.vin 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 (s:byte list)(s : \text{byte list})(s:byte list) is the Boolean: (∣s∣>0|s| > 0∣s∣>0 and the byte at index 000 (default 000) equals OP_RETURN =0x6a= 0x6a=0x6a) or ∣s∣>10 000|s| > 10\,000∣s∣>10000 (MAX_SCRIPT_SIZE from the verification development).

sumValues maps a list of outputs to the integer sum of their values (000 for the empty list), computed by prepending: sumValues(o::r)=o.nValue+sumValues(r)\mathrm{sumValues}(o :: r) = o.\mathrm{nValue} + \mathrm{sumValues}(r)sumValues(o::r)=o.nValue+sumValues(r).

valueOut (tx)=sumValues(tx.vout)(tx) = \mathrm{sumValues}(tx.\mathrm{vout})(tx)=sumValues(tx.vout).

outputsLoop (outputs,acc∈Z)(\text{outputs}, \mathit{acc} \in \mathbb{Z})(outputs,acc∈Z) returns an optional integer: on the empty list, some acc\mathrm{some}\,\mathit{acc}someacc; on o::ro :: ro::r: none if o.nValue<0o.\mathrm{nValue} < 0o.nValue<0; else none if M<o.nValueM < o.\mathrm{nValue}M<o.nValue; else none if acc+o.nValue∉[0,M]\mathit{acc} + o.\mathrm{nValue} \notin [0, M]acc+o.nValue∈/[0,M]; else recurse on rrr with acc+o.nValue\mathit{acc} + o.\mathrm{nValue}acc+o.nValue.

checkTransaction (tx)(tx)(tx) is the Boolean conjunction, in order: tx.vintx.\mathrm{vin}tx.vin non-empty; tx.vouttx.\mathrm{vout}tx.vout non-empty; 4⋅∣serTx(false,tx)∣≤4 000 0004\cdot|\mathrm{serTx}(\mathrm{false},tx)| \le 4\,000\,0004⋅∣serTx(false,tx)∣≤4000000 (witness-free serialization length); outputsLoop(tx.vout,0)\mathrm{outputsLoop}(tx.\mathrm{vout}, 0)outputsLoop(tx.vout,0) is some value; the list of prevouts of tx.vintx.\mathrm{vin}tx.vin has no duplicates; and, if isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx), then the scriptSig length ℓ\ellℓ of the head of tx.vintx.\mathrm{vin}tx.vin (default input if empty) satisfies 2≤ℓ∧ℓ≤1002 \le \ell \wedge \ell \le 1002≤ℓ∧ℓ≤100, otherwise every input of txtxtx has a non-null prevout.

isFinalTx (tx,height∈N,blockTime∈Z)(tx, \mathit{height} \in \mathbb{N}, \mathit{blockTime} \in \mathbb{Z})(tx,height∈N,blockTime∈Z): true if tx.nLockTime=0tx.\mathrm{nLockTime} = 0tx.nLockTime=0; otherwise let the threshold be height\mathit{height}height (as an integer) if tx.nLockTime<500 000 000tx.\mathrm{nLockTime} < 500\,000\,000tx.nLockTime<500000000 and blockTime\mathit{blockTime}blockTime otherwise; true if tx.nLockTime<tx.\mathrm{nLockTime} <tx.nLockTime< threshold; otherwise true iff every input of txtxtx has nSequence=4294967295\mathrm{nSequence} = 4294967295nSequence=4294967295 (vacuously true with no inputs).

Signature-operation counting

sigOpCountAux (accurate:Bool)(\mathit{accurate} : \text{Bool})(accurate:Bool) takes (fuel∈N,s:byte list,last∈N,n∈N)(\mathit{fuel} \in \mathbb{N}, s : \text{byte list}, \mathit{last} \in \mathbb{N}, n \in \mathbb{N})(fuel∈N,s:byte list,last∈N,n∈N) and returns a natural number: if sss is empty, nnn; else if fuel=0\mathit{fuel} = 0fuel=0, nnn; otherwise parse one instruction from sss with the signature development's getOp (a byte ≤0x4e\le 0x4e≤0x4e is a push of the indicated data, with the PUSHDATA1/2/4 length forms; a byte >0x4e> 0x4e>0x4e is an opcode; a truncated push yields a parse failure): on failure, nnn; on a push with remainder rrr, recurse with fuel−1\mathit{fuel}-1fuel−1, rrr, last:=0\mathit{last} := 0last:=0 and nnn unchanged; on an opcode ccc with remainder rrr: n′=n+1n' = n+1n′=n+1 if ccc is OP_CHECKSIG (0xac0xac0xac) or OP_CHECKSIGVERIFY (0xad0xad0xad); n′=n+(last−0x50)n' = n + (\mathit{last} - 0x50)n′=n+(last−0x50) if ccc is OP_CHECKMULTISIG (0xae0xae0xae) or OP_CHECKMULTISIGVERIFY (0xaf0xaf0xaf) and accurate\mathit{accurate}accurate and 0x51≤last≤0x600x51 \le \mathit{last} \le 0x600x51≤last≤0x60 (via decodeOpN, which maps 000 to 000 and bbb to b−0x50b - 0x50b−0x50); n′=n+20n' = n + 20n′=n+20 for those two opcodes otherwise; n′=nn' = nn′=n for any other opcode; then recurse with fuel−1\mathit{fuel}-1fuel−1, rrr, last:=c\mathit{last} := clast:=c and n′n'n′.

getSigOpCount (accurate,s)=sigOpCountAux(accurate,∣s∣,s,0xff,0)(\mathit{accurate}, s) = \mathrm{sigOpCountAux}(\mathit{accurate}, |s|, s, 0xff, 0)(accurate,s)=sigOpCountAux(accurate,∣s∣,s,0xff,0): fuel is the byte length, the initial "last opcode" is 0xff0xff0xff, the initial count 000.

lastPushAux (fuel,s,d)(\mathit{fuel}, s, d)(fuel,s,d) returns an optional byte list: if sss is empty, some d\mathrm{some}\,dsomed; else if fuel=0\mathit{fuel} = 0fuel=0, none; else parse one instruction: failure gives none; a push of data d′d'd′ recurses with d:=d′d := d'd:=d′; an opcode ccc gives none if c>c > c> OP_16 =0x60= 0x60=0x60, otherwise recurses with d:=[ ]d := [\,]d:=[].

lastPush (s)=lastPushAux(∣s∣,s,[ ])(s) = \mathrm{lastPushAux}(|s|, s, [\,])(s)=lastPushAux(∣s∣,s,[]): the data of the last push instruction of a script all of whose instructions are pushes or opcodes ≤0x60\le 0x60≤0x60 (an opcode ≤0x60\le 0x60≤0x60 resets the result to the empty list), or none if some instruction fails to parse or is an opcode above 0x600x600x60; the empty script gives some [ ]\mathrm{some}\,[\,]some[].

p2shSigOpCount (scriptPubKey,scriptSig)(\mathit{scriptPubKey}, \mathit{scriptSig})(scriptPubKey,scriptSig): if scriptPubKey\mathit{scriptPubKey}scriptPubKey is not pay-to-script-hash (exactly 232323 bytes with byte 0=0xa90 = 0xa90=0xa9, byte 1=0x141 = 0x141=0x14, byte 22=0x8722 = 0x8722=0x87), then getSigOpCount(true,scriptPubKey)\mathrm{getSigOpCount}(\mathrm{true}, \mathit{scriptPubKey})getSigOpCount(true,scriptPubKey); otherwise 000 if lastPush(scriptSig)\mathrm{lastPush}(\mathit{scriptSig})lastPush(scriptSig) is none, else getSigOpCount(true,d)\mathrm{getSigOpCount}(\mathrm{true}, d)getSigOpCount(true,d) for the last pushed data ddd.

witnessSigOps (version∈N,program,witness)(\mathit{version} \in \mathbb{N}, \mathit{program}, \mathit{witness})(version∈N,program,witness): if version=0\mathit{version} = 0version=0: 111 when ∣program∣=20|\mathit{program}| = 20∣program∣=20; getSigOpCount(true,last witness element)\mathrm{getSigOpCount}(\mathrm{true}, \text{last witness element})getSigOpCount(true,last witness element) when ∣program∣=32|\mathit{program}| = 32∣program∣=32 and the witness is non-empty (the last element defaults to [ ][\,][] if absent, but that branch requires non-emptiness); otherwise 000. For any other version, 000.

countWitnessSigOps (f,scriptSig,scriptPubKey,witness)(f, \mathit{scriptSig}, \mathit{scriptPubKey}, \mathit{witness})(f,scriptSig,scriptPubKey,witness): 000 if f.witnessf.\mathrm{witness}f.witness is false; else if scriptPubKey\mathit{scriptPubKey}scriptPubKey is a witness program (length in [4,42][4,42][4,42], first byte 000 or in [0x51,0x60][0x51,0x60][0x51,0x60], second byte equal to the length minus 222) with version vvv and program ppp, then witnessSigOps(v,p,witness)\mathrm{witnessSigOps}(v, p, \mathit{witness})witnessSigOps(v,p,witness); else if scriptPubKey\mathit{scriptPubKey}scriptPubKey is pay-to-script-hash and scriptSig\mathit{scriptSig}scriptSig is push-only (every instruction parses and is a push or an opcode ≤0x60\le 0x60≤0x60), then: 000 if lastPush(scriptSig)\mathrm{lastPush}(\mathit{scriptSig})lastPush(scriptSig) is none; else, with the last push ddd, witnessSigOps(v,p,witness)\mathrm{witnessSigOps}(v,p,\mathit{witness})witnessSigOps(v,p,witness) if ddd is a witness program (v,p)(v,p)(v,p) and 000 otherwise; else 000.

legacySigOpCount (tx)(tx)(tx) is ∑i∈tx.vingetSigOpCount(false,i.scriptSig)+∑o∈tx.voutgetSigOpCount(false,o.scriptPubKey)\sum_{i \in tx.\mathrm{vin}} \mathrm{getSigOpCount}(\mathrm{false}, i.\mathrm{scriptSig}) + \sum_{o \in tx.\mathrm{vout}} \mathrm{getSigOpCount}(\mathrm{false}, o.\mathrm{scriptPubKey})∑i∈tx.vin​getSigOpCount(false,i.scriptSig)+∑o∈tx.vout​getSigOpCount(false,o.scriptPubKey).

The ledger

Coin is a record ⟨out:output,height∈N,isCoinbase:Bool⟩\langle \mathrm{out} : \text{output}, \mathrm{height} \in \mathbb{N}, \mathrm{isCoinbase} : \text{Bool}\rangle⟨out:output,height∈N,isCoinbase:Bool⟩ with decidable equality.

dummyCoin is the coin ⟨⟨−1,[ ]⟩,0,false⟩\langle\langle -1, [\,]\rangle, 0, \mathrm{false}\rangle⟨⟨−1,[]⟩,0,false⟩: value −1-1−1, empty script, height 000, not coinbase.

Ledger is an abbreviation for lists of pairs (outpoint, coin). Nothing enforces distinct keys.

getCoin (u,op)(u, \mathit{op})(u,op) scans uuu from the front and returns some c\mathrm{some}\,csomec for the first pair (k,c)(k,c)(k,c) with k=opk = \mathit{op}k=op, or none.

haveCoin (u,op)(u, \mathit{op})(u,op) is the Boolean "getCoin(u,op)\mathrm{getCoin}(u,\mathit{op})getCoin(u,op) is some".

accessCoin (u,op)(u, \mathit{op})(u,op) is getCoin(u,op)\mathrm{getCoin}(u, \mathit{op})getCoin(u,op) if present, otherwise dummyCoin\mathrm{dummyCoin}dummyCoin.

spendCoin (u,op)(u, \mathit{op})(u,op) returns uuu with every pair whose key equals op\mathit{op}op removed, order otherwise preserved.

addCoin (u,op,c)(u, \mathit{op}, c)(u,op,c): if c.out.scriptPubKeyc.\mathrm{out.scriptPubKey}c.out.scriptPubKey is unspendable (starts with 0x6a0x6a0x6a or exceeds 10 00010\,00010000 bytes), uuu unchanged; otherwise (op,c)(\mathit{op}, c)(op,c) prepended to spendCoin(u,op)\mathrm{spendCoin}(u, \mathit{op})spendCoin(u,op).

addCoinsFrom (txid,height,cb)(\mathit{txid}, \mathit{height}, cb)(txid,height,cb) takes (u,i∈N,outputs)(u, i \in \mathbb{N}, \text{outputs})(u,i∈N,outputs) and folds: for the empty list, uuu; for o::ro :: ro::r, recurse on rrr with index i+1i+1i+1 from addCoin(u,⟨txid,i⟩,⟨o,height,cb⟩)\mathrm{addCoin}(u, \langle\mathit{txid}, i\rangle, \langle o, \mathit{height}, cb\rangle)addCoin(u,⟨txid,i⟩,⟨o,height,cb⟩).

spendInputs (u,inputs)(u, \text{inputs})(u,inputs) folds spendCoin\mathrm{spendCoin}spendCoin over the inputs' prevouts in order.

updateCoins (u,tx,height)(u, tx, \mathit{height})(u,tx,height) is addCoinsFrom(txid(tx),height,isCoinBase(tx))\mathrm{addCoinsFrom}(\mathrm{txid}(tx), \mathit{height}, \mathrm{isCoinBase}(tx))addCoinsFrom(txid(tx),height,isCoinBase(tx)) applied to (if isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx) then uuu else spendInputs(u,tx.vin)\mathrm{spendInputs}(u, tx.\mathrm{vin})spendInputs(u,tx.vin)), starting index 000, over tx.vouttx.\mathrm{vout}tx.vout. Here txid(tx)\mathrm{txid}(tx)txid(tx) is the double-SHA256 of the witness-free serialization.

txUndo (u,tx)(u, tx)(u,tx) is the list [accessCoin(u,i.prevout)∣i∈tx.vin][\mathrm{accessCoin}(u, i.\mathrm{prevout}) \mid i \in tx.\mathrm{vin}][accessCoin(u,i.prevout)∣i∈tx.vin] (dummy coins for missing entries).

BlockUndo abbreviates lists of lists of coins.

Equiv (u,v)(u, v)(u,v) is the proposition ∀op, getCoin(u,op)=getCoin(v,op)\forall \mathit{op},\ \mathrm{getCoin}(u,\mathit{op}) = \mathrm{getCoin}(v,\mathit{op})∀op, getCoin(u,op)=getCoin(v,op).

keysNodup (u)(u)(u) is the proposition that the list of first components of uuu has no duplicates.

CheckTxInputs and the per-transaction checks

inputsLoop (u,spendHeight)(u, \mathit{spendHeight})(u,spendHeight) takes (inputs,acc∈Z)(\text{inputs}, \mathit{acc} \in \mathbb{Z})(inputs,acc∈Z): on the empty list, some acc\mathrm{some}\,\mathit{acc}someacc; on i::ri :: ri::r: if getCoin(u,i.prevout)\mathrm{getCoin}(u, i.\mathrm{prevout})getCoin(u,i.prevout) is none, none; else with coin ccc: none if c.isCoinbasec.\mathrm{isCoinbase}c.isCoinbase and spendHeight−c.height<100\mathit{spendHeight} - c.\mathrm{height} < 100spendHeight−c.height<100 (natural subtraction, so this fires whenever c.height+100>spendHeightc.\mathrm{height} + 100 > \mathit{spendHeight}c.height+100>spendHeight, including c.height>spendHeightc.\mathrm{height} > \mathit{spendHeight}c.height>spendHeight); else let acc′=acc+c.out.nValue\mathit{acc}' = \mathit{acc} + c.\mathrm{out.nValue}acc′=acc+c.out.nValue; none if c.out.nValue∉[0,M]c.\mathrm{out.nValue} \notin [0,M]c.out.nValue∈/[0,M] or acc′∉[0,M]\mathit{acc}' \notin [0,M]acc′∈/[0,M]; else recurse with acc′\mathit{acc}'acc′.

checkTxInputs (u,tx,spendHeight)(u, tx, \mathit{spendHeight})(u,tx,spendHeight) returns an optional integer fee: none if some input's prevout has no coin in uuu; else none if inputsLoop(u,spendHeight,tx.vin,0)\mathrm{inputsLoop}(u, \mathit{spendHeight}, tx.\mathrm{vin}, 0)inputsLoop(u,spendHeight,tx.vin,0) is none; else with valueIn\mathit{valueIn}valueIn its value: none if valueIn<valueOut(tx)\mathit{valueIn} < \mathrm{valueOut}(tx)valueIn<valueOut(tx); none if valueIn−valueOut(tx)∉[0,M]\mathit{valueIn} - \mathrm{valueOut}(tx) \notin [0,M]valueIn−valueOut(tx)∈/[0,M]; else some(valueIn−valueOut(tx))\mathrm{some}(\mathit{valueIn} - \mathrm{valueOut}(tx))some(valueIn−valueOut(tx)).

txSigOpCost (f,u,tx)=4⋅legacySigOpCount(tx)+X(f, u, tx) = 4\cdot\mathrm{legacySigOpCount}(tx) + X(f,u,tx)=4⋅legacySigOpCount(tx)+X where X=0X = 0X=0 if isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx), and otherwise X=(4⋅∑ip2shSigOpCount(accessCoin(u,i.prevout).out.scriptPubKey,i.scriptSig)X = \big(4\cdot\sum_{i} \mathrm{p2shSigOpCount}(\mathrm{accessCoin}(u, i.\mathrm{prevout}).\mathrm{out.scriptPubKey}, i.\mathrm{scriptSig})X=(4⋅∑i​p2shSigOpCount(accessCoin(u,i.prevout).out.scriptPubKey,i.scriptSig) if f.p2shf.\mathrm{p2sh}f.p2sh, else 0)+∑icountWitnessSigOps(f,i.scriptSig,accessCoin(u,i.prevout).out.scriptPubKey,i.witness)0\big) + \sum_i \mathrm{countWitnessSigOps}(f, i.\mathrm{scriptSig}, \mathrm{accessCoin}(u, i.\mathrm{prevout}).\mathrm{out.scriptPubKey}, i.\mathrm{witness})0)+∑i​countWitnessSigOps(f,i.scriptSig,accessCoin(u,i.prevout).out.scriptPubKey,i.witness), sums over i∈tx.vini \in tx.\mathrm{vin}i∈tx.vin (missing coins contribute the dummy's empty script).

sequenceLocksOk (u,height,mtp:N→N,lockTimeFlags∈N,tx)(u, \mathit{height}, \mathit{mtp} : \mathbb{N}\to\mathbb{N}, \mathit{lockTimeFlags} \in \mathbb{N}, tx)(u,height,mtp:N→N,lockTimeFlags∈N,tx) is the BIP68 core development's sequenceLocks applied to version tx.version mod 232tx.\mathrm{version} \bmod 2^{32}tx.versionmod232, flags lockTimeFlags mod 232\mathit{lockTimeFlags} \bmod 2^{32}lockTimeFlagsmod232, context ⟨height,mtp⟩\langle\mathit{height}, \mathit{mtp}\rangle⟨height,mtp⟩ and the input list [⟨i.nSequence mod 232,accessCoin(u,i.prevout).height⟩∣i∈tx.vin][\langle i.\mathrm{nSequence} \bmod 2^{32}, \mathrm{accessCoin}(u,i.\mathrm{prevout}).\mathrm{height}\rangle \mid i \in tx.\mathrm{vin}][⟨i.nSequencemod232,accessCoin(u,i.prevout).height⟩∣i∈tx.vin]: with BIP68 enabled (version ≥2\ge 2≥2 and flag bit 000 set), fold the inputs into integer minima minHeight,minTime\mathit{minHeight}, \mathit{minTime}minHeight,minTime starting at −1-1−1 — an input with bit 313131 set contributes nothing; with bit 222222 set it raises minTime\mathit{minTime}minTime to mtp(c−1)+512⋅(s mod 216)−1\mathit{mtp}(c-1) + 512\cdot(s \bmod 2^{16}) - 1mtp(c−1)+512⋅(smod216)−1; otherwise it raises minHeight\mathit{minHeight}minHeight to c+(s mod 216)−1c + (s \bmod 2^{16}) - 1c+(smod216)−1 — and return minHeight<height∧minTime<mtp(height−1)\mathit{minHeight} < \mathit{height} \wedge \mathit{minTime} < \mathit{mtp}(\mathit{height}-1)minHeight<height∧minTime<mtp(height−1); with BIP68 not enabled, the minima stay −1-1−1 and the result is true.

inputScriptsOk (f,u,tx)(f, u, tx)(f,u,tx): let spent=[accessCoin(u,i.prevout).out∣i∈tx.vin]\mathit{spent} = [\mathrm{accessCoin}(u, i.\mathrm{prevout}).\mathrm{out} \mid i \in tx.\mathrm{vin}]spent=[accessCoin(u,i.prevout).out∣i∈tx.vin]; for every index n<∣tx.vin∣n < |tx.\mathrm{vin}|n<∣tx.vin∣, with iii the nnn-th input (default input if out of range, which cannot happen) and c=accessCoin(u,i.prevout)c = \mathrm{accessCoin}(u, i.\mathrm{prevout})c=accessCoin(u,i.prevout), the Taproot development's verifyScriptFull holds on spent\mathit{spent}spent, context ⟨f,tx,n,c.out.nValue⟩\langle f, tx, n, c.\mathrm{out.nValue}\rangle⟨f,tx,n,c.out.nValue⟩, i.scriptSigi.\mathrm{scriptSig}i.scriptSig, c.out.scriptPubKeyc.\mathrm{out.scriptPubKey}c.out.scriptPubKey and i.witnessi.\mathrm{witness}i.witness — the complete VerifyScript: evaluate scriptSig then scriptPubKey on the stack, require a true top, then the native witness-program branch (when f.witnessf.\mathrm{witness}f.witness; scriptSig must be empty), the P2SH branch (when f.p2shf.\mathrm{p2sh}f.p2sh; 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 ⟨utxo:Ledger,fees∈Z,sigOps∈N,undo:BlockUndo⟩\langle \mathrm{utxo} : \text{Ledger}, \mathrm{fees} \in \mathbb{Z}, \mathrm{sigOps} \in \mathbb{N}, \mathrm{undo} : \text{BlockUndo}\rangle⟨utxo:Ledger,fees∈Z,sigOps∈N,undo:BlockUndo⟩.

connectLoop (f,height,mtp,lockTimeFlags)(f, \mathit{height}, \mathit{mtp}, \mathit{lockTimeFlags})(f,height,mtp,lockTimeFlags) takes (st,transactions)(\mathit{st}, \text{transactions})(st,transactions) and returns an optional loop state: on the empty list, some st\mathrm{some}\,\mathit{st}somest; on tx::rtx :: rtx::r: compute an optional (fees, undo) "step": if isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx), some(st.fees,st.undo)\mathrm{some}(\mathit{st}.\mathrm{fees}, \mathit{st}.\mathrm{undo})some(st.fees,st.undo); else none if checkTxInputs(st.utxo,tx,height)\mathrm{checkTxInputs}(\mathit{st}.\mathrm{utxo}, tx, \mathit{height})checkTxInputs(st.utxo,tx,height) is none, else with fee φ\varphiφ: none if st.fees+φ∉[0,M]\mathit{st}.\mathrm{fees} + \varphi \notin [0, M]st.fees+φ∈/[0,M]; none if sequenceLocksOk(st.utxo,height,mtp,lockTimeFlags,tx)\mathrm{sequenceLocksOk}(\mathit{st}.\mathrm{utxo}, \mathit{height}, \mathit{mtp}, \mathit{lockTimeFlags}, tx)sequenceLocksOk(st.utxo,height,mtp,lockTimeFlags,tx) is false; else some(st.fees+φ, st.undo+ ⁣ ⁣+[txUndo(st.utxo,tx)])\mathrm{some}(\mathit{st}.\mathrm{fees} + \varphi,\ \mathit{st}.\mathrm{undo} \mathbin{+\!\!+} [\mathrm{txUndo}(\mathit{st}.\mathrm{utxo}, tx)])some(st.fees+φ, st.undo++[txUndo(st.utxo,tx)]). If the step is none, none. Otherwise let σ=st.sigOps+txSigOpCost(f,st.utxo,tx)\sigma = \mathit{st}.\mathrm{sigOps} + \mathrm{txSigOpCost}(f, \mathit{st}.\mathrm{utxo}, tx)σ=st.sigOps+txSigOpCost(f,st.utxo,tx): none if 80 000<σ80\,000 < \sigma80000<σ; none if txtxtx is not a coinbase and inputScriptsOk(f,st.utxo,tx)\mathrm{inputScriptsOk}(f, \mathit{st}.\mathrm{utxo}, tx)inputScriptsOk(f,st.utxo,tx) is false; else recurse on rrr from ⟨updateCoins(st.utxo,tx,height),fees,σ,undo⟩\langle \mathrm{updateCoins}(\mathit{st}.\mathrm{utxo}, tx, \mathit{height}), \text{fees}, \sigma, \text{undo}\rangle⟨updateCoins(st.utxo,tx,height),fees,σ,undo⟩. 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 ⟨headers:list of headers,utxo:Ledger⟩\langle \mathrm{headers} : \text{list of headers}, \mathrm{utxo} : \text{Ledger}\rangle⟨headers:list of headers,utxo:Ledger⟩.

initialState is ⟨[genesisHeader],[ ]⟩\langle [\mathrm{genesisHeader}], [\,]\rangle⟨[genesisHeader],[]⟩: the mainnet genesis header alone and an empty ledger (the genesis coinbase output is not present).

ChainState.tipHeight (S)=∣S.headers∣−1(S) = |S.\mathrm{headers}| - 1(S)=∣S.headers∣−1 with natural subtraction (000 for an empty list).

ChainState.tip (S)(S)(S) is the last header of S.headersS.\mathrm{headers}S.headers, or genesisHeader\mathrm{genesisHeader}genesisHeader if the list is empty.

ChainState.tipHash (S)=headerHash(tip(S))(S) = \mathrm{headerHash}(\mathrm{tip}(S))(S)=headerHash(tip(S)), the double-SHA256 of the 80-byte serialization (version as 4 little-endian bytes modulo 2322^{32}232, prevBlock bytes, merkleRoot bytes, time, bits, nonce each as 4 little-endian bytes modulo 2322^{32}232).

ChainState.nextHeight (S)=∣S.headers∣(S) = |S.\mathrm{headers}|(S)=∣S.headers∣.

ChainState.timesTo (S,h)(S, h)(S,h) is the list of the times (cast to Z\mathbb{Z}Z) of the first h+1h+1h+1 headers of SSS, reversed (so most recent first); fewer if the list is shorter.

ChainState.mtpAt (S,h)(S, h)(S,h) is the header development's medianTimePast of timesTo(S,h)\mathrm{timesTo}(S,h)timesTo(S,h): take the first 111111 elements, sort ascending, return the element at index ⌊window length/2⌋\lfloor \text{window length}/2\rfloor⌊window length/2⌋, with default 000 for an empty window.

ChainState.mtp (S)=mtpAt(S,tipHeight(S))(S) = \mathrm{mtpAt}(S, \mathrm{tipHeight}(S))(S)=mtpAt(S,tipHeight(S)).

ChainState.mtpNat (S,h)=max⁡(0,mtpAt(S,h))(S, h) = \max(0, \mathrm{mtpAt}(S,h))(S,h)=max(0,mtpAt(S,h)) as a natural number (negative medians become 000).

ChainState.requiredBits (S)(S)(S): let first\mathit{first}first be the header at index tipHeight(S)−(2016−1)\mathrm{tipHeight}(S) - (2016 - 1)tipHeight(S)−(2016−1) (natural subtraction; 2016=⌊14⋅24⋅60⋅60/600⌋2016 = \lfloor 14\cdot24\cdot60\cdot60 / 600\rfloor2016=⌊14⋅24⋅60⋅60/600⌋), defaulting to genesisHeader\mathrm{genesisHeader}genesisHeader when out of range; the result is the proof-of-work development's nextWorkRequired with last height tipHeight(S)\mathrm{tipHeight}(S)tipHeight(S), last bits tip(S).bits mod 232\mathrm{tip}(S).\mathrm{bits} \bmod 2^{32}tip(S).bitsmod232, last time tip(S).time\mathrm{tip}(S).\mathrm{time}tip(S).time and first time first.time\mathit{first}.\mathrm{time}first.time (both cast to Z\mathbb{Z}Z): the last bits unchanged if (tipHeight+1) mod 2016≠0(\mathrm{tipHeight}+1) \bmod 2016 \ne 0(tipHeight+1)mod2016=0, otherwise the retarget (decode the last target, multiply by the actual timespan clamped to [timespan/4,4⋅timespan][\text{timespan}/4, 4\cdot\text{timespan}][timespan/4,4⋅timespan] modulo 22562^{256}2256, divide by 1 209 6001\,209\,6001209600, cap at 2224−12^{224}-12224−1, re-encode as a compact word).

blockProof (bits∈N)(\mathit{bits} \in \mathbb{N})(bits∈N): with deriveTarget of bits mod 232\mathit{bits} \bmod 2^{32}bitsmod232 — none if the compact word is negative, decodes to 000, overflows, or exceeds 2224−12^{224}-12224−1 — the result is 000 on none, and ⌊(2256−1−t)/(t+1)⌋+1\lfloor (2^{256} - 1 - t)/(t+1)\rfloor + 1⌊(2256−1−t)/(t+1)⌋+1 on some t\mathrm{some}\,tsomet (natural subtraction and floor division).

ChainState.chainWork (S)=∑h∈S.headersblockProof(h.bits)(S) = \sum_{h \in S.\mathrm{headers}} \mathrm{blockProof}(h.\mathrm{bits})(S)=∑h∈S.headers​blockProof(h.bits).

hashValue (h)(h)(h) is the little-endian numeric value of headerHash(h)\mathrm{headerHash}(h)headerHash(h) (byte kkk weighted by 256k256^k256k).

CheckBlock

merkleCombine (a,b)=hash256(a+ ⁣ ⁣+b)(a, b) = \mathrm{hash256}(a \mathbin{+\!\!+} b)(a,b)=hash256(a++b), double-SHA256 of the concatenation.

zeroHash is the list of 323232 zero bytes.

blockMerkleRoot (b)(b)(b) is the merkle development's computeMerkleRoot with combiner merkleCombine\mathrm{merkleCombine}merkleCombine and empty-root zeroHash\mathrm{zeroHash}zeroHash on [txid(tx)∣tx∈b.vtx][\mathrm{txid}(tx) \mid tx \in b.\mathrm{vtx}][txid(tx)∣tx∈b.vtx]: a pair (root, mutated). The loop: while more than one hash remains, set mutated if some aligned pair (positions 2k2k2k, 2k+12k+12k+1, 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 zeroHash\mathrm{zeroHash}zeroHash for an empty list; mutated starts false.

blockWitnessMerkleRoot (b)(b)(b) is the root component of the same computation on zeroHash::[wtxid(tx)∣tx∈drop1(b.vtx)]\mathrm{zeroHash} :: [\mathrm{wtxid}(tx) \mid tx \in \mathrm{drop}_1(b.\mathrm{vtx})]zeroHash::[wtxid(tx)∣tx∈drop1​(b.vtx)], where wtxid\mathrm{wtxid}wtxid is the double-SHA256 of the witness serialization when the transaction has a witness, else the txid.

checkHeaderPow (h)(h)(h) is the proof-of-work development's checkProofOfWork on hashValue(h)\mathrm{hashValue}(h)hashValue(h) and h.bits mod 232h.\mathrm{bits} \bmod 2^{32}h.bitsmod232: false if deriveTarget is none, else hashValue(h)≤t\mathrm{hashValue}(h) \le thashValue(h)≤t.

checkBlock (b)(b)(b) is the Boolean conjunction, in order: checkHeaderPow(b.header)\mathrm{checkHeaderPow}(b.\mathrm{header})checkHeaderPow(b.header); (blockMerkleRoot b).1=b.header.merkleRoot(\mathrm{blockMerkleRoot}\,b).1 = b.\mathrm{header.merkleRoot}(blockMerkleRootb).1=b.header.merkleRoot; ¬(blockMerkleRoot b).2\neg(\mathrm{blockMerkleRoot}\,b).2¬(blockMerkleRootb).2; b.vtxb.\mathrm{vtx}b.vtx non-empty; 4⋅∣b.vtx∣≤4 000 0004\cdot|b.\mathrm{vtx}| \le 4\,000\,0004⋅∣b.vtx∣≤4000000; 4⋅∣serBlock(false,b)∣≤4 000 0004\cdot|\mathrm{serBlock}(\mathrm{false}, b)| \le 4\,000\,0004⋅∣serBlock(false,b)∣≤4000000; isCoinBase\mathrm{isCoinBase}isCoinBase of the head of b.vtxb.\mathrm{vtx}b.vtx (default genesisCoinbase\mathrm{genesisCoinbase}genesisCoinbase); every element of drop1(b.vtx)\mathrm{drop}_1(b.\mathrm{vtx})drop1​(b.vtx) is not a coinbase; every element of b.vtxb.\mathrm{vtx}b.vtx passes checkTransaction\mathrm{checkTransaction}checkTransaction; 4⋅∑tx∈b.vtxlegacySigOpCount(tx)≤80 0004\cdot\sum_{tx\in b.\mathrm{vtx}}\mathrm{legacySigOpCount}(tx) \le 80\,0004⋅∑tx∈b.vtx​legacySigOpCount(tx)≤80000.

ContextualCheckBlock

heightScript (n∈N)(n \in \mathbb{N})(n∈N): [0][0][0] if n=0n = 0n=0; [0x50+n][0x50 + n][0x50+n] (one byte) if 1≤n≤161 \le n \le 161≤n≤16; otherwise the signature development's canonical push (pushBytes: a length byte for data shorter than 0x4c0x4c0x4c bytes, else a PUSHDATA1/2/4 prefix) of the script development's serialize of nnn (the little-endian magnitude bytes with a 0x000x000x00 sign byte appended when the top bit of the last byte is set).

isCommitmentOutput (o)(o)(o) is the Boolean 38≤∣o.scriptPubKey∣38 \le |o.\mathrm{scriptPubKey}|38≤∣o.scriptPubKey∣ and the first six bytes of o.scriptPubKeyo.\mathrm{scriptPubKey}o.scriptPubKey are 6a 24 aa 21 a9 ed6a\,24\,aa\,21\,a9\,ed6a24aa21a9ed.

witnessCommitmentIndex (b)(b)(b): none if b.vtxb.\mathrm{vtx}b.vtx is empty; otherwise, with cbcbcb the first transaction, the last index i<∣cb.vout∣i < |cb.\mathrm{vout}|i<∣cb.vout∣ such that the iii-th output (default output if out of range) satisfies isCommitmentOutput\mathrm{isCommitmentOutput}isCommitmentOutput, or none if there is no such index.

checkWitnessMalleation (b,expect:Bool)(b, \mathit{expect} : \text{Bool})(b,expect:Bool): let noWitness\mathit{noWitness}noWitness be "every transaction of bbb has no input with a non-empty witness". If expect\mathit{expect}expect is false, return noWitness\mathit{noWitness}noWitness. If true: if witnessCommitmentIndex(b)\mathrm{witnessCommitmentIndex}(b)witnessCommitmentIndex(b) is none, return noWitness\mathit{noWitness}noWitness; else with position ppp, let cbcbcb be the head of b.vtxb.\mathrm{vtx}b.vtx (default genesisCoinbase\mathrm{genesisCoinbase}genesisCoinbase) and stack\mathit{stack}stack the witness of the head of cb.vincb.\mathrm{vin}cb.vin (default input): if stack\mathit{stack}stack is exactly [nonce][\mathit{nonce}][nonce], return ∣nonce∣=32|\mathit{nonce}| = 32∣nonce∣=32 and hash256(blockWitnessMerkleRoot(b)+ ⁣ ⁣+nonce)\mathrm{hash256}(\mathrm{blockWitnessMerkleRoot}(b) \mathbin{+\!\!+} \mathit{nonce})hash256(blockWitnessMerkleRoot(b)++nonce) equals the 323232 bytes of the ppp-th output's scriptPubKey (default output) after dropping 666 bytes; for a stack of any other length (including empty), return false.

contextualCheckBlock (S,b)(S, b)(S,b): let height=nextHeight(S)\mathit{height} = \mathrm{nextHeight}(S)height=nextHeight(S) and cutoff=mtp(S)\mathit{cutoff} = \mathrm{mtp}(S)cutoff=mtp(S) if the activation development's activeAfter(tipHeight(S),csv)(\mathrm{tipHeight}(S), \mathrm{csv})(tipHeight(S),csv) (i.e. 419328≤tipHeight(S)+1419328 \le \mathrm{tipHeight}(S)+1419328≤tipHeight(S)+1) else b.header.timeb.\mathrm{header.time}b.header.time as an integer. The Boolean conjunction of: every transaction satisfies isFinalTx(tx,height,cutoff)\mathrm{isFinalTx}(tx, \mathit{height}, \mathit{cutoff})isFinalTx(tx,height,cutoff); not activeAfter(tipHeight(S),heightInCB)(\mathrm{tipHeight}(S), \mathrm{heightInCB})(tipHeight(S),heightInCB) (227931≤tipHeight+1227931 \le \mathrm{tipHeight}+1227931≤tipHeight+1) or heightScript(height)\mathrm{heightScript}(\mathit{height})heightScript(height) is a prefix of the scriptSig of the head input (default input) of the head transaction (default genesisCoinbase\mathrm{genesisCoinbase}genesisCoinbase); checkWitnessMalleation(b,‘activeAfter‘(tipHeight(S),segwit))\mathrm{checkWitnessMalleation}(b, \text{`activeAfter`}(\mathrm{tipHeight}(S), \mathrm{segwit}))checkWitnessMalleation(b,‘activeAfter‘(tipHeight(S),segwit)) (481824≤tipHeight+1481824 \le \mathrm{tipHeight}+1481824≤tipHeight+1); and blockWeight(b)≤4 000 000\mathrm{blockWeight}(b) \le 4\,000\,000blockWeight(b)≤4000000 where blockWeight(b)=3⋅∣serBlock(false,b)∣+∣serBlock(true,b)∣\mathrm{blockWeight}(b) = 3\cdot|\mathrm{serBlock}(\mathrm{false},b)| + |\mathrm{serBlock}(\mathrm{true},b)|blockWeight(b)=3⋅∣serBlock(false,b)∣+∣serBlock(true,b)∣.

ConnectBlock

bip30Checked (S,height,hash)(S, \mathit{height}, \mathit{hash})(S,height,hash): let bip34Ancestor\mathit{bip34Ancestor}bip34Ancestor be: if S.headersS.\mathrm{headers}S.headers has an element hhh at index 227931227931227931 then headerHash(h)=bip34Hash\mathrm{headerHash}(h) = \mathrm{bip34Hash}headerHash(h)=bip34Hash else false. Result: (¬ isBIP30Repeat(height,hash)∧¬ bip34Ancestor)∨1983702≤height(\neg\,\mathrm{isBIP30Repeat}(\mathit{height},\mathit{hash}) \wedge \neg\,\mathit{bip34Ancestor}) \vee 1983702 \le \mathit{height}(¬isBIP30Repeat(height,hash)∧¬bip34Ancestor)∨1983702≤height.

bip30Ok (u,b)(u, b)(u,b): for every transaction txtxtx of bbb and every index o<∣tx.vout∣o < |tx.\mathrm{vout}|o<∣tx.vout∣, ⟨txid(tx),o⟩\langle\mathrm{txid}(tx), o\rangle⟨txid(tx),o⟩ is not a key of uuu (all outputs counted, including unspendable ones).

connectBlock (S,b)(S, b)(S,b) returns an optional (ledger, undo): let hash=headerHash(b.header)\mathit{hash} = \mathrm{headerHash}(b.\mathrm{header})hash=headerHash(b.header) and height=nextHeight(S)\mathit{height} = \mathrm{nextHeight}(S)height=nextHeight(S). If hash=genesisHash\mathit{hash} = \mathrm{genesisHash}hash=genesisHash (the fixed 32-byte constant beginning 6f e2 8c 0a6f\,e2\,8c\,0a6fe28c0a), return some(S.utxo,[ ])\mathrm{some}(S.\mathrm{utxo}, [\,])some(S.utxo,[]) without any further check. Else if bip30Checked(S,height,hash)\mathrm{bip30Checked}(S,\mathit{height},\mathit{hash})bip30Checked(S,height,hash) and not bip30Ok(S.utxo,b)\mathrm{bip30Ok}(S.\mathrm{utxo}, b)bip30Ok(S.utxo,b), none. Else let flags\mathit{flags}flags be the activation development's blockScriptFlags(height,scriptException(hash))(\mathit{height}, \mathrm{scriptException}(\mathit{hash}))(height,scriptException(hash)) (base per the exception, then DERSIG when height≥363725\mathit{height}\ge 363725height≥363725, CLTV when ≥388381\ge 388381≥388381, CSV when ≥419328\ge 419328≥419328, NULLDUMMY when ≥481824\ge 481824≥481824), and run connectLoop(flags,height,mtpNat(S),‘lockTimeFlags‘(height),⟨S.utxo,0,0,[ ]⟩,b.vtx)\mathrm{connectLoop}(\mathit{flags}, \mathit{height}, \mathrm{mtpNat}(S), \text{`lockTimeFlags`}(\mathit{height}), \langle S.\mathrm{utxo}, 0, 0, [\,]\rangle, b.\mathrm{vtx})connectLoop(flags,height,mtpNat(S),‘lockTimeFlags‘(height),⟨S.utxo,0,0,[]⟩,b.vtx) where lockTimeFlags is 111 if height≥419328\mathit{height} \ge 419328height≥419328 else 000: none on failure; else with final state st\mathit{st}st: none if valueOut(head of b.vtx,default genesisCoinbase)>st.fees+coreSubsidy(height)\mathrm{valueOut}(\text{head of } b.\mathrm{vtx}, \text{default } \mathrm{genesisCoinbase}) > \mathit{st}.\mathrm{fees} + \mathrm{coreSubsidy}(\mathit{height})valueOut(head of b.vtx,default genesisCoinbase)>st.fees+coreSubsidy(height), where coreSubsidy(h)=0\mathrm{coreSubsidy}(h) = 0coreSubsidy(h)=0 if ⌊h/210000⌋≥64\lfloor h/210000\rfloor \ge 64⌊h/210000⌋≥64 and 5 000 000 000≫⌊h/210000⌋5\,000\,000\,000 \gg \lfloor h/210000\rfloor5000000000≫⌊h/210000⌋ otherwise; else some(st.utxo,st.undo)\mathrm{some}(\mathit{st}.\mathrm{utxo}, \mathit{st}.\mathrm{undo})some(st.utxo,st.undo).

The complete validation path

Outcome is an inductive type with four constructors: accept carrying a chain state S′S'S′ and a block undo; invalid; futureTime; missingPrev.

acceptHeader (S,h,now∈Z)(S, h, \mathit{now} \in \mathbb{Z})(S,h,now∈Z): invalid if ¬ checkHeaderPow(h)\neg\,\mathrm{checkHeaderPow}(h)¬checkHeaderPow(h); else missingPrev if h.prevBlock≠tipHash(S)h.\mathrm{prevBlock} \ne \mathrm{tipHash}(S)h.prevBlock=tipHash(S); else invalid if h.bits mod 232≠requiredBits(S)h.\mathrm{bits} \bmod 2^{32} \ne \mathrm{requiredBits}(S)h.bitsmod232=requiredBits(S); else invalid if h.time≤mtp(S)h.\mathrm{time} \le \mathrm{mtp}(S)h.time≤mtp(S); else futureTime if now+7200<h.time\mathit{now} + 7200 < h.\mathrm{time}now+7200<h.time; else invalid if the header development's versionOutdated(h.version,tipHeight(S))(h.\mathrm{version}, \mathrm{tipHeight}(S))(h.version,tipHeight(S)) (h.version<2h.\mathrm{version} < 2h.version<2 and 227931≤tipHeight+1227931 \le \mathrm{tipHeight}+1227931≤tipHeight+1, or <3<3<3 and 363725≤tipHeight+1363725 \le \mathrm{tipHeight}+1363725≤tipHeight+1, or <4<4<4 and 388381≤tipHeight+1388381 \le \mathrm{tipHeight}+1388381≤tipHeight+1); else accept SSS [ ][\,][] (the unchanged state and the empty undo).

validate (S,b,now)(S, b, \mathit{now})(S,b,now): match acceptHeader(S,b.header,now)\mathrm{acceptHeader}(S, b.\mathrm{header}, \mathit{now})acceptHeader(S,b.header,now): on accept (payload ignored): invalid if ¬ checkBlock(b)\neg\,\mathrm{checkBlock}(b)¬checkBlock(b); else invalid if ¬ contextualCheckBlock(S,b)\neg\,\mathrm{contextualCheckBlock}(S,b)¬contextualCheckBlock(S,b); else on connectBlock(S,b)\mathrm{connectBlock}(S,b)connectBlock(S,b): invalid if none, and accept ⟨S.headers+ ⁣ ⁣+[b.header],u⟩\langle S.\mathrm{headers} \mathbin{+\!\!+} [b.\mathrm{header}], u\rangle⟨S.headers++[b.header],u⟩ undo\mathit{undo}undo if some(u,undo)\mathrm{some}(u, \mathit{undo})some(u,undo); on any other header outcome, that outcome.

accepts (S,b,now)(S, b, \mathit{now})(S,b,now) is the proposition ∃S′ ∃undo, validate(S,b,now)=‘accept‘ S′ undo\exists S'\,\exists\mathit{undo},\ \mathrm{validate}(S,b,\mathit{now}) = \text{`accept`}\ S'\ \mathit{undo}∃S′∃undo, validate(S,b,now)=‘accept‘ S′ undo.

Reachable is the inductive predicate on chain states generated by: genesis: Reachable(initialState)\mathrm{Reachable}(\mathrm{initialState})Reachable(initialState); step: for implicit S,b,now,S′,undoS, b, \mathit{now}, S', \mathit{undo}S,b,now,S′,undo, from Reachable(S)\mathrm{Reachable}(S)Reachable(S) and validate(S,b,now)=‘accept‘ S′ undo\mathrm{validate}(S,b,\mathit{now}) = \text{`accept`}\ S'\ \mathit{undo}validate(S,b,now)=‘accept‘ S′ undo conclude Reachable(S′)\mathrm{Reachable}(S')Reachable(S′).

DisconnectBlock

applyTxInUndo (u,undo:Coin,out:outpoint)(u, \mathit{undo} : \text{Coin}, \mathit{out} : \text{outpoint})(u,undo:Coin,out:outpoint) returns an optional (ledger, Bool): let clean=¬ haveCoin(u,out)\mathit{clean} = \neg\,\mathrm{haveCoin}(u, \mathit{out})clean=¬haveCoin(u,out). If undo.height=0\mathit{undo}.\mathrm{height} = 0undo.height=0: search uuu for the first entry whose key hash equals out.hash\mathit{out}.\mathrm{hash}out.hash (index ignored); if found with coin alt\mathit{alt}alt, the coin to restore is undo\mathit{undo}undo with height and coinbase flag replaced by alt\mathit{alt}alt's; if not found, return none. If undo.height≠0\mathit{undo}.\mathrm{height} \ne 0undo.height=0, the coin to restore is undo\mathit{undo}undo itself. Return some(addCoin(u,out,c),clean)\mathrm{some}(\mathrm{addCoin}(u, \mathit{out}, c), \mathit{clean})some(addCoin(u,out,c),clean) (so an unspendable coin is silently not added).

restoreInputs (u,list of (input, coin) pairs)(u, \text{list of (input, coin) pairs})(u,list of (input, coin) pairs): on the empty list, some(u,true)\mathrm{some}(u, \mathrm{true})some(u,true); on (i,c)::r(i,c) :: r(i,c)::r: first restoreInputs(u,r)\mathrm{restoreInputs}(u, r)restoreInputs(u,r) (so the tail, i.e. later inputs, is restored first); none propagates; then applyTxInUndo(u′,c,i.prevout)\mathrm{applyTxInUndo}(u', c, i.\mathrm{prevout})applyTxInUndo(u′,c,i.prevout); none propagates; result is the new ledger with the conjunction of the two clean flags.

spendOutputs (u,txid,height,cb,exception)(u, \mathit{txid}, \mathit{height}, cb, \mathit{exception})(u,txid,height,cb,exception) takes (outputs,i∈N)(\text{outputs}, i \in \mathbb{N})(outputs,i∈N) and returns a (ledger, Bool) pair — never none: on the empty list, (u,true)(u, \mathrm{true})(u,true); on o::ro :: ro::r: if o.scriptPubKeyo.\mathrm{scriptPubKey}o.scriptPubKey is unspendable, (u,true)(u, \mathrm{true})(u,true) for this output; otherwise with op=⟨txid,i⟩\mathit{op} = \langle\mathit{txid}, i\rangleop=⟨txid,i⟩, let ok\mathit{ok}ok be false if op\mathit{op}op is not a key of uuu and otherwise "the stored coin equals ⟨o,height,cb⟩\langle o, \mathit{height}, cb\rangle⟨o,height,cb⟩ componentwise"; this output yields (spendCoin(u,op),ok∨exception)(\mathrm{spendCoin}(u,\mathit{op}), \mathit{ok} \vee \mathit{exception})(spendCoin(u,op),ok∨exception); then recurse on rrr with i+1i+1i+1 from that ledger and and the flags.

disconnectTx (u,height,exception,tx,undo:optional list of coins)(u, \mathit{height}, \mathit{exception}, tx, \mathit{undo} : \text{optional list of coins})(u,height,exception,tx,undo:optional list of coins): let cb=isCoinBase(tx)cb = \mathrm{isCoinBase}(tx)cb=isCoinBase(tx) and (u′,clean)=spendOutputs(u,txid(tx),height,cb,cb∧exception,tx.vout,0)(u', \mathit{clean}) = \mathrm{spendOutputs}(u, \mathrm{txid}(tx), \mathit{height}, cb, cb \wedge \mathit{exception}, tx.\mathrm{vout}, 0)(u′,clean)=spendOutputs(u,txid(tx),height,cb,cb∧exception,tx.vout,0). If undo\mathit{undo}undo is none, some(u′,clean)\mathrm{some}(u', \mathit{clean})some(u′,clean). If some coins\mathrm{some}\,\mathit{coins}somecoins: none if ∣coins∣≠∣tx.vin∣|\mathit{coins}| \ne |tx.\mathrm{vin}|∣coins∣=∣tx.vin∣; else restoreInputs(u′,zip(tx.vin,coins))\mathrm{restoreInputs}(u', \mathrm{zip}(tx.\mathrm{vin}, \mathit{coins}))restoreInputs(u′,zip(tx.vin,coins)), none propagating, with the clean flags and-ed.

disconnectTxs (height,exception)(\mathit{height}, \mathit{exception})(height,exception) takes (u,list of (transaction, optional coins))(u, \text{list of (transaction, optional coins)})(u,list of (transaction, optional coins)): on the empty list, some(u,true)\mathrm{some}(u, \mathrm{true})some(u,true); else apply disconnectTx\mathrm{disconnectTx}disconnectTx to the head, none propagating, then recurse on the tail from the resulting ledger, none propagating, and-ing the flags.

disconnectBlock (u,height,hash,b,undo:BlockUndo)(u, \mathit{height}, \mathit{hash}, b, \mathit{undo} : \text{BlockUndo})(u,height,hash,b,undo:BlockUndo): none if ∣undo∣+1≠∣b.vtx∣|\mathit{undo}| + 1 \ne |b.\mathrm{vtx}|∣undo∣+1=∣b.vtx∣; otherwise disconnectTxs(height,isBIP30Unspendable(height,hash),u,L)\mathrm{disconnectTxs}(\mathit{height}, \mathrm{isBIP30Unspendable}(\mathit{height}, \mathit{hash}), u, L)disconnectTxs(height,isBIP30Unspendable(height,hash),u,L) where LLL is the reverse of zip(b.vtx,none::[some c∣c∈undo])\mathrm{zip}(b.\mathrm{vtx}, \mathrm{none} :: [\mathrm{some}\,c \mid c \in \mathit{undo}])zip(b.vtx,none::[somec∣c∈undo]): the first transaction is paired with no undo record, the (k+1)(k+1)(k+1)-th with the kkk-th undo entry, and the pairs are processed last-to-first.

The declarative specification and ApplySpec

TxSpec (tx)(tx)(tx) is the proposition: tx.vin≠[ ]tx.\mathrm{vin} \ne [\,]tx.vin=[]; tx.vout≠[ ]tx.\mathrm{vout} \ne [\,]tx.vout=[]; 4⋅∣serTx(false,tx)∣≤4 000 0004\cdot|\mathrm{serTx}(\mathrm{false},tx)| \le 4\,000\,0004⋅∣serTx(false,tx)∣≤4000000; every output value vvv has 0≤v≤M0 \le v \le M0≤v≤M; valueOut(tx)≤M\mathrm{valueOut}(tx) \le MvalueOut(tx)≤M; prevouts pairwise distinct; isCoinBase(tx)=true⇒\mathrm{isCoinBase}(tx) = \mathrm{true} \RightarrowisCoinBase(tx)=true⇒ every input's scriptSig length lies in [2,100][2,100][2,100]; isCoinBase(tx)=false⇒\mathrm{isCoinBase}(tx) = \mathrm{false} \RightarrowisCoinBase(tx)=false⇒ every input has outPointNull=false\mathrm{outPointNull} = \mathrm{false}outPointNull=false.

valueIn (u,inputs)(u, \text{inputs})(u,inputs) is ∑iaccessCoin(u,i.prevout).out.nValue\sum_i \mathrm{accessCoin}(u, i.\mathrm{prevout}).\mathrm{out.nValue}∑i​accessCoin(u,i.prevout).out.nValue over Z\mathbb{Z}Z, computed by prepending; a missing coin contributes −1-1−1.

feeOf (u,tx)=valueIn(u,tx.vin)−valueOut(tx)(u, tx) = \mathrm{valueIn}(u, tx.\mathrm{vin}) - \mathrm{valueOut}(tx)(u,tx)=valueIn(u,tx.vin)−valueOut(tx).

TxInputsSpec (f,u,height,mtp,lockTimeFlags,tx)(f, u, \mathit{height}, \mathit{mtp}, \mathit{lockTimeFlags}, tx)(f,u,height,mtp,lockTimeFlags,tx) is the conjunction: for every input iii there is a coin ccc with getCoin(u,i.prevout)=some c\mathrm{getCoin}(u, i.\mathrm{prevout}) = \mathrm{some}\,cgetCoin(u,i.prevout)=somec, (c.isCoinbase=true⇒c.height+100≤height)(c.\mathrm{isCoinbase} = \mathrm{true} \Rightarrow c.\mathrm{height} + 100 \le \mathit{height})(c.isCoinbase=true⇒c.height+100≤height), 0≤c.out.nValue0 \le c.\mathrm{out.nValue}0≤c.out.nValue and c.out.nValue≤Mc.\mathrm{out.nValue} \le Mc.out.nValue≤M; valueIn(u,tx.vin)≤M\mathrm{valueIn}(u, tx.\mathrm{vin}) \le MvalueIn(u,tx.vin)≤M; valueOut(tx)≤valueIn(u,tx.vin)\mathrm{valueOut}(tx) \le \mathrm{valueIn}(u, tx.\mathrm{vin})valueOut(tx)≤valueIn(u,tx.vin); the BIP68 model's satisfiesBIP68 on version tx.version mod 232tx.\mathrm{version} \bmod 2^{32}tx.versionmod232, flags lockTimeFlags mod 232\mathit{lockTimeFlags} \bmod 2^{32}lockTimeFlagsmod232, context ⟨height,mtp⟩\langle\mathit{height},\mathit{mtp}\rangle⟨height,mtp⟩ and inputs ⟨i.nSequence mod 232,accessCoin(u,i.prevout).height⟩\langle i.\mathrm{nSequence} \bmod 2^{32}, \mathrm{accessCoin}(u, i.\mathrm{prevout}).\mathrm{height}\rangle⟨i.nSequencemod232,accessCoin(u,i.prevout).height⟩ (BIP68 not enabled, or every input disabled (bit 31) or satisfying mtp(c−1)+512⋅(s mod 216)≤mtp(height−1)\mathit{mtp}(c-1) + 512\cdot(s \bmod 2^{16}) \le \mathit{mtp}(\mathit{height}-1)mtp(c−1)+512⋅(smod216)≤mtp(height−1) when bit 22 is set and c+(s mod 216)≤heightc + (s \bmod 2^{16}) \le \mathit{height}c+(smod216)≤height otherwise); and for every n<∣tx.vin∣n < |tx.\mathrm{vin}|n<∣tx.vin∣, with iii the nnn-th input (default input) and c=accessCoin(u,i.prevout)c = \mathrm{accessCoin}(u, i.\mathrm{prevout})c=accessCoin(u,i.prevout), verifyScriptFull on the spent list [accessCoin(u,j.prevout).out∣j∈tx.vin][\mathrm{accessCoin}(u, j.\mathrm{prevout}).\mathrm{out} \mid j \in tx.\mathrm{vin}][accessCoin(u,j.prevout).out∣j∈tx.vin], context ⟨f,tx,n,c.out.nValue⟩\langle f, tx, n, c.\mathrm{out.nValue}\rangle⟨f,tx,n,c.out.nValue⟩, i.scriptSigi.\mathrm{scriptSig}i.scriptSig, c.out.scriptPubKeyc.\mathrm{out.scriptPubKey}c.out.scriptPubKey, i.witnessi.\mathrm{witness}i.witness equals true.

TxsSpec (f,height,mtp,lockTimeFlags)(f, \mathit{height}, \mathit{mtp}, \mathit{lockTimeFlags})(f,height,mtp,lockTimeFlags) on (u,fees∈Z,sigOps∈N,transactions)(u, \mathit{fees} \in \mathbb{Z}, \mathit{sigOps} \in \mathbb{N}, \text{transactions})(u,fees∈Z,sigOps∈N,transactions): true for the empty list; for tx::rtx :: rtx::r: (isCoinBase(tx)=false⇒TxInputsSpec(f,u,height,mtp,lockTimeFlags,tx)∧fees+feeOf(u,tx)≤M)(\mathrm{isCoinBase}(tx) = \mathrm{false} \Rightarrow \mathrm{TxInputsSpec}(f,u,\mathit{height},\mathit{mtp},\mathit{lockTimeFlags},tx) \wedge \mathit{fees} + \mathrm{feeOf}(u,tx) \le M)(isCoinBase(tx)=false⇒TxInputsSpec(f,u,height,mtp,lockTimeFlags,tx)∧fees+feeOf(u,tx)≤M), and sigOps+txSigOpCost(f,u,tx)≤80 000\mathit{sigOps} + \mathrm{txSigOpCost}(f,u,tx) \le 80\,000sigOps+txSigOpCost(f,u,tx)≤80000, and TxsSpec\mathrm{TxsSpec}TxsSpec on rrr from updateCoins(u,tx,height)\mathrm{updateCoins}(u,tx,\mathit{height})updateCoins(u,tx,height), fees fees\mathit{fees}fees if coinbase else fees+feeOf(u,tx)\mathit{fees} + \mathrm{feeOf}(u,tx)fees+feeOf(u,tx), and sigops sigOps+txSigOpCost(f,u,tx)\mathit{sigOps} + \mathrm{txSigOpCost}(f,u,tx)sigOps+txSigOpCost(f,u,tx). No lower bound on the fee total is stated.

applyTxs (height)(\mathit{height})(height) on (u,transactions)(u, \text{transactions})(u,transactions): the left fold of updateCoins(⋅,tx,height)\mathrm{updateCoins}(\cdot, tx, \mathit{height})updateCoins(⋅,tx,height) over the list.

totalFees (height)(\mathit{height})(height) on (u,transactions)(u, \text{transactions})(u,transactions): 000 for the empty list; for tx::rtx :: rtx::r, (000 if isCoinBase(tx)\mathrm{isCoinBase}(tx)isCoinBase(tx) else feeOf(u,tx)\mathrm{feeOf}(u,tx)feeOf(u,tx)) plus totalFees\mathrm{totalFees}totalFees on rrr from updateCoins(u,tx,height)\mathrm{updateCoins}(u,tx,\mathit{height})updateCoins(u,tx,height).

applySpec (S,b)(S, b)(S,b): if headerHash(b.header)=genesisHash\mathrm{headerHash}(b.\mathrm{header}) = \mathrm{genesisHash}headerHash(b.header)=genesisHash then ⟨S.headers+ ⁣ ⁣+[b.header],S.utxo⟩\langle S.\mathrm{headers} \mathbin{+\!\!+} [b.\mathrm{header}], S.\mathrm{utxo}\rangle⟨S.headers++[b.header],S.utxo⟩, else ⟨S.headers+ ⁣ ⁣+[b.header],applyTxs(nextHeight(S),S.utxo,b.vtx)⟩\langle S.\mathrm{headers} \mathbin{+\!\!+} [b.\mathrm{header}], \mathrm{applyTxs}(\mathrm{nextHeight}(S), S.\mathrm{utxo}, b.\mathrm{vtx})\rangle⟨S.headers++[b.header],applyTxs(nextHeight(S),S.utxo,b.vtx)⟩.

HeaderSpec (S,h,now)(S, h, \mathit{now})(S,h,now) is the conjunction: [the proof-of-work development's compactNegative of h.bits mod 232h.\mathrm{bits} \bmod 2^{32}h.bitsmod232 is false, compactOverflow is false, 0<‘specTarget‘0 < \text{`specTarget`}0<‘specTarget‘, specTarget ≤2224−1\le 2^{224}-1≤2224−1, and hashValue(h)≤\mathrm{hashValue}(h) \lehashValue(h)≤ specTarget], where specTarget is the exact value mantissa ⋅256exponent−3\cdot 256^{\text{exponent}-3}⋅256exponent−3 (floor-divided when the exponent is ≤3\le 3≤3) with no 22562^{256}2256 truncation; h.prevBlock=tipHash(S)h.\mathrm{prevBlock} = \mathrm{tipHash}(S)h.prevBlock=tipHash(S); h.bits mod 232=requiredBits(S)h.\mathrm{bits} \bmod 2^{32} = \mathrm{requiredBits}(S)h.bitsmod232=requiredBits(S); mtp(S)<h.time\mathrm{mtp}(S) < h.\mathrm{time}mtp(S)<h.time and h.time≤now+7200h.\mathrm{time} \le \mathit{now} + 7200h.time≤now+7200; and ¬((h.version<2∧227931≤tipHeight(S)+1)∨(h.version<3∧363725≤tipHeight(S)+1)∨(h.version<4∧388381≤tipHeight(S)+1))\neg\big((h.\mathrm{version} < 2 \wedge 227931 \le \mathrm{tipHeight}(S)+1) \vee (h.\mathrm{version} < 3 \wedge 363725 \le \mathrm{tipHeight}(S)+1) \vee (h.\mathrm{version} < 4 \wedge 388381 \le \mathrm{tipHeight}(S)+1)\big)¬((h.version<2∧227931≤tipHeight(S)+1)∨(h.version<3∧363725≤tipHeight(S)+1)∨(h.version<4∧388381≤tipHeight(S)+1)).

BlockSpec (b)(b)(b) is the conjunction: b.vtx≠[ ]b.\mathrm{vtx} \ne [\,]b.vtx=[]; (blockMerkleRoot b).1=b.header.merkleRoot(\mathrm{blockMerkleRoot}\,b).1 = b.\mathrm{header.merkleRoot}(blockMerkleRootb).1=b.header.merkleRoot and (blockMerkleRoot b).2=false(\mathrm{blockMerkleRoot}\,b).2 = \mathrm{false}(blockMerkleRootb).2=false; 4⋅∣b.vtx∣≤4 000 0004\cdot|b.\mathrm{vtx}| \le 4\,000\,0004⋅∣b.vtx∣≤4000000; 4⋅∣serBlock(false,b)∣≤4 000 0004\cdot|\mathrm{serBlock}(\mathrm{false},b)| \le 4\,000\,0004⋅∣serBlock(false,b)∣≤4000000; every tx∈take1(b.vtx)tx \in \mathrm{take}_1(b.\mathrm{vtx})tx∈take1​(b.vtx) has isCoinBase=true\mathrm{isCoinBase} = \mathrm{true}isCoinBase=true and every tx∈drop1(b.vtx)tx \in \mathrm{drop}_1(b.\mathrm{vtx})tx∈drop1​(b.vtx) has isCoinBase=false\mathrm{isCoinBase} = \mathrm{false}isCoinBase=false; every tx∈b.vtxtx \in b.\mathrm{vtx}tx∈b.vtx satisfies TxSpec\mathrm{TxSpec}TxSpec; 4⋅∑txlegacySigOpCount(tx)≤80 0004\cdot\sum_{tx}\mathrm{legacySigOpCount}(tx) \le 80\,0004⋅∑tx​legacySigOpCount(tx)≤80000.

ContextSpec (S,b)(S, b)(S,b): with height\mathit{height}height and cutoff\mathit{cutoff}cutoff as in contextualCheckBlock\mathrm{contextualCheckBlock}contextualCheckBlock: every tx∈b.vtxtx \in b.\mathrm{vtx}tx∈b.vtx has isFinalTx(tx,height,cutoff)=true\mathrm{isFinalTx}(tx,\mathit{height},\mathit{cutoff}) = \mathrm{true}isFinalTx(tx,height,cutoff)=true; activeAfter(tipHeight(S),heightInCB)=true⇒∀cb∈take1(b.vtx), ∀i∈take1(cb.vin), heightScript(height)(\mathrm{tipHeight}(S), \mathrm{heightInCB}) = \mathrm{true} \Rightarrow \forall cb \in \mathrm{take}_1(b.\mathrm{vtx}),\ \forall i \in \mathrm{take}_1(cb.\mathrm{vin}),\ \mathrm{heightScript}(\mathit{height})(tipHeight(S),heightInCB)=true⇒∀cb∈take1​(b.vtx), ∀i∈take1​(cb.vin), heightScript(height) is a prefix of i.scriptSigi.\mathrm{scriptSig}i.scriptSig (vacuous with no transactions or no inputs); checkWitnessMalleation(b,‘activeAfter‘(tipHeight(S),segwit))=true\mathrm{checkWitnessMalleation}(b, \text{`activeAfter`}(\mathrm{tipHeight}(S), \mathrm{segwit})) = \mathrm{true}checkWitnessMalleation(b,‘activeAfter‘(tipHeight(S),segwit))=true; blockWeight(b)≤4 000 000\mathrm{blockWeight}(b) \le 4\,000\,000blockWeight(b)≤4000000.

LedgerSpec (S,b)(S, b)(S,b): with hash=headerHash(b.header)\mathit{hash} = \mathrm{headerHash}(b.\mathrm{header})hash=headerHash(b.header), height=nextHeight(S)\mathit{height} = \mathrm{nextHeight}(S)height=nextHeight(S) and flags=\mathit{flags} = flags= blockScriptFlags(height,scriptException(hash))(\mathit{height}, \mathrm{scriptException}(\mathit{hash}))(height,scriptException(hash)): hash=genesisHash\mathit{hash} = \mathrm{genesisHash}hash=genesisHash, or [(bip30Checked(S,height,hash)=true⇒∀tx∈b.vtx, ∀o<∣tx.vout∣, getCoin(S.utxo,⟨txid(tx),o⟩)=none)(\mathrm{bip30Checked}(S,\mathit{height},\mathit{hash}) = \mathrm{true} \Rightarrow \forall tx \in b.\mathrm{vtx},\ \forall o < |tx.\mathrm{vout}|,\ \mathrm{getCoin}(S.\mathrm{utxo}, \langle\mathrm{txid}(tx), o\rangle) = \mathrm{none})(bip30Checked(S,height,hash)=true⇒∀tx∈b.vtx, ∀o<∣tx.vout∣, getCoin(S.utxo,⟨txid(tx),o⟩)=none) and TxsSpec(flags,height,mtpNat(S),‘lockTimeFlags‘(height),S.utxo,0,0,b.vtx)\mathrm{TxsSpec}(\mathit{flags}, \mathit{height}, \mathrm{mtpNat}(S), \text{`lockTimeFlags`}(\mathit{height}), S.\mathrm{utxo}, 0, 0, b.\mathrm{vtx})TxsSpec(flags,height,mtpNat(S),‘lockTimeFlags‘(height),S.utxo,0,0,b.vtx) and ∀cb∈take1(b.vtx), valueOut(cb)≤totalFees(height,S.utxo,b.vtx)+specSubsidy(height)\forall cb \in \mathrm{take}_1(b.\mathrm{vtx}),\ \mathrm{valueOut}(cb) \le \mathrm{totalFees}(\mathit{height}, S.\mathrm{utxo}, b.\mathrm{vtx}) + \mathrm{specSubsidy}(\mathit{height})∀cb∈take1​(b.vtx), valueOut(cb)≤totalFees(height,S.utxo,b.vtx)+specSubsidy(height)], where specSubsidy(h)=⌊5 000 000 000/2⌊h/210000⌋⌋\mathrm{specSubsidy}(h) = \lfloor 5\,000\,000\,000 / 2^{\lfloor h/210000\rfloor}\rfloorspecSubsidy(h)=⌊5000000000/2⌊h/210000⌋⌋ (the subsidy development's declarative schedule, distinct from coreSubsidy used by connectBlock\mathrm{connectBlock}connectBlock).

Valid (S,b,now)(S, b, \mathit{now})(S,b,now) is HeaderSpec(S,b.header,now)∧BlockSpec(b)∧ContextSpec(S,b)∧LedgerSpec(S,b)\mathrm{HeaderSpec}(S, b.\mathrm{header}, \mathit{now}) \wedge \mathrm{BlockSpec}(b) \wedge \mathrm{ContextSpec}(S,b) \wedge \mathrm{LedgerSpec}(S,b)HeaderSpec(S,b.header,now)∧BlockSpec(b)∧ContextSpec(S,b)∧LedgerSpec(S,b).

LedgerOk (u)(u)(u) is keysNodup(u)\mathrm{keysNodup}(u)keysNodup(u) and every entry eee of uuu has e.2.height≠0e.2.\mathrm{height} \ne 0e.2.height=0 and isUnspendable(e.2.out.scriptPubKey)=false\mathrm{isUnspendable}(e.2.\mathrm{out.scriptPubKey}) = \mathrm{false}isUnspendable(e.2.out.scriptPubKey)=false. (Not referenced by any of the nineteen theorem statements.)

WellFormed (S)(S)(S) is: the head of S.headersS.\mathrm{headers}S.headers is some genesisHeader\mathrm{some}\,\mathrm{genesisHeader}somegenesisHeader; keysNodup(S.utxo)\mathrm{keysNodup}(S.\mathrm{utxo})keysNodup(S.utxo); and every entry eee of S.utxoS.\mathrm{utxo}S.utxo has 1≤e.2.height1 \le e.2.\mathrm{height}1≤e.2.height, e.2.height≤tipHeight(S)e.2.\mathrm{height} \le \mathrm{tipHeight}(S)e.2.height≤tipHeight(S), and isUnspendable(e.2.out.scriptPubKey)=false\mathrm{isUnspendable}(e.2.\mathrm{out.scriptPubKey}) = \mathrm{false}isUnspendable(e.2.out.scriptPubKey)=false.

Edge cases and defaults the file silently includes

Empty header lists (tipHeight=0\mathrm{tipHeight} = 0tipHeight=0, tip and retarget-anchor default to the genesis header, median 000); 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, height−1\mathit{height}-1height−1 and c−1c-1c−1 in BIP68, and blockProof; modulo-2322^{32}232 reductions of bits, version, sequence and flags; accessCoin's dummy coin (value −1-1−1, height 000) 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.

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

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me