Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Where the BIP30 scan runs, an accepted block's outputs are fresh

Proved
BitcoinUniqueness.scan_freshness

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

bip30bip34bitcoinbitcoin-mainnetcoinbaseconsensusformal-verificationuniqueness

For a reachable state, an accepted block (not hashing to the genesis hash) and ScanRuns S b: FreshOutputs S.utxo b. From the acceptance theorem: the ledger predicate's BIP30 clause.

Preamble
import Definitions.Def_BitcoinUniqueness
import Definitions.Def_BitcoinSer
open BitcoinUniqueness BitcoinSer BitcoinBlockV2
Formal statement
theorem BitcoinUniqueness.scan_freshness (S : ChainState) (b : BitcoinSer.Block) (now : Int) (S' : ChainState)
    (undo : BlockUndo) (hR : BitcoinBlockV2.Reachable S) (h : BitcoinBlockV2.validate S b now = .accept S' undo)
    (hscan : BitcoinUniqueness.ScanRuns S b) (hg : BitcoinSer.headerHash b.header ≠ BitcoinSer.genesisHash) :
    BitcoinUniqueness.FreshOutputs S.utxo b := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: ConnectBlock (fEnforceBIP30, BIP34_IMPLIES_BIP30_LIMIT), ContextualCheckBlock (the BIP34 height push), src/validation.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/validation.cpp; CScript::push_int64, CScriptNum::serialize (script/script.h); BIP30, BIP34
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: BitcoinUniqueness.scan_freshness

Statement. For every chain state SSS, block bbb, integer ttt (the clock reading, named now), chain state S′S'S′, and undo list UUU (a list of lists of coins), if

  • Reachable(S)\mathrm{Reachable}(S)Reachable(S),
  • validate(S,b,t)=accept(S′,U)\mathrm{validate}(S, b, t) = \mathrm{accept}(S', U)validate(S,b,t)=accept(S′,U),
  • ScanRuns(S,b)\mathrm{ScanRuns}(S, b)ScanRuns(S,b), and
  • headerHash(b.header)≠G\mathrm{headerHash}(b.\mathrm{header}) \ne GheaderHash(b.header)=G, where GGG is the fixed 32-byte genesis block hash (beginning 6f e2 8c 0a\mathtt{6f\,e2\,8c\,0a}6fe28c0a),

then FreshOutputs(S.utxo,b)\mathrm{FreshOutputs}(S.\mathrm{utxo}, b)FreshOutputs(S.utxo,b) holds.

Formally:

∀S b t S′ U,Reachable(S)∧validate(S,b,t)=accept(S′,U)∧ScanRuns(S,b)∧headerHash(b.header)≠G ⟹ FreshOutputs(S.utxo,b).\forall S\, b\, t\, S'\, U,\quad \mathrm{Reachable}(S) \wedge \mathrm{validate}(S,b,t) = \mathrm{accept}(S',U) \wedge \mathrm{ScanRuns}(S,b) \wedge \mathrm{headerHash}(b.\mathrm{header}) \ne G \ \Longrightarrow\ \mathrm{FreshOutputs}(S.\mathrm{utxo}, b).∀SbtS′U,Reachable(S)∧validate(S,b,t)=accept(S′,U)∧ScanRuns(S,b)∧headerHash(b.header)=G ⟹ FreshOutputs(S.utxo,b).

What the conclusion says

FreshOutputs(u,b)\mathrm{FreshOutputs}(u, b)FreshOutputs(u,b) for a ledger uuu (association list of outpoint–coin pairs) is

∀ tx∈b.vtx, ∀ o∈N, o<∣tx.vout∣⟹getCoin(u,(txid(tx),o))=none,\forall\, \mathrm{tx} \in b.\mathrm{vtx},\ \forall\, o \in \mathbb{N},\ o < |\mathrm{tx}.\mathrm{vout}| \Longrightarrow \mathrm{getCoin}\big(u, (\mathrm{txid}(\mathrm{tx}), o)\big) = \mathrm{none},∀tx∈b.vtx, ∀o∈N, o<∣tx.vout∣⟹getCoin(u,(txid(tx),o))=none,

where txid(tx)\mathrm{txid}(\mathrm{tx})txid(tx) is the double-SHA-256 of the witness-stripped serialization of tx\mathrm{tx}tx and getCoin(u,p)\mathrm{getCoin}(u,p)getCoin(u,p) returns the coin of the first pair of uuu whose key equals ppp, or none\mathrm{none}none if there is none. The ledger in the conclusion is that of SSS (the state before the block), not of S′S'S′.

What ScanRuns says

ScanRuns(S,b)\mathrm{ScanRuns}(S,b)ScanRuns(S,b) is, by definition, bip30Checked(S,H,η)=true\mathrm{bip30Checked}(S, H, \eta) = \mathtt{true}bip30Checked(S,H,η)=true with H:=∣S.headers∣H := |S.\mathrm{headers}|H:=∣S.headers∣ and η:=headerHash(b.header)\eta := \mathrm{headerHash}(b.\mathrm{header})η:=headerHash(b.header) (double-SHA-256 of the serialized header), which unfolds to

(¬ Rep(H,η) ∧ ¬ Anc(S)) ∨ 1,983,702≤H,\Big(\neg\,\mathrm{Rep}(H,\eta)\ \wedge\ \neg\,\mathrm{Anc}(S)\Big)\ \vee\ 1{,}983{,}702 \le H,(¬Rep(H,η) ∧ ¬Anc(S)) ∨ 1,983,702≤H,

where Rep(H,η)\mathrm{Rep}(H,\eta)Rep(H,η) holds iff (H=91842∧η=C91842)(H = 91842 \wedge \eta = C_{91842})(H=91842∧η=C91842​) or (H=91880∧η=C91880)(H = 91880 \wedge \eta = C_{91880})(H=91880∧η=C91880​) for two fixed 32-byte constants, and Anc(S)\mathrm{Anc}(S)Anc(S) holds iff S.headersS.\mathrm{headers}S.headers has an element at zero-based position 227,931227{,}931227,931 (i.e. H≥227,932H \ge 227{,}932H≥227,932) whose header hash equals a fixed 32-byte constant C34C_{34}C34​. The block bbb enters only through η\etaη.

What the acceptance hypothesis says

validate(S,b,t)=accept(S′,U)\mathrm{validate}(S, b, t) = \mathrm{accept}(S', U)validate(S,b,t)=accept(S′,U) asserts that the four stages below all succeed and that S′S'S′ and UUU are exactly the state and undo list they produce. Write h:=b.headerh := b.\mathrm{header}h:=b.header, H:=∣S.headers∣H := |S.\mathrm{headers}|H:=∣S.headers∣ (the next height), tip\mathrm{tip}tip for the last element of S.headersS.\mathrm{headers}S.headers (the fixed genesis header if the list is empty), tipHeight:=H−˙1\mathrm{tipHeight} := H \mathbin{\dot{-}} 1tipHeight:=H−˙​1 (truncated subtraction, so 000 when H=0H = 0H=0), and cb\mathrm{cb}cb for the first transaction of b.vtxb.\mathrm{vtx}b.vtx (the fixed genesis coinbase transaction if b.vtxb.\mathrm{vtx}b.vtx is empty). A transaction "is a coinbase" iff it has exactly one input and that input's previous outpoint is (32 zero bytes,0xffffffff)(32\text{ zero bytes}, \mathtt{0xffffffff})(32 zero bytes,0xffffffff).

  1. Header stage. hhh passes the proof-of-work test of the imported proof-of-work development (its double-SHA-256 hash, read as a little-endian 256-bit number, against the 32-bit field h.bitsh.\mathrm{bits}h.bits); h.prevBlockh.\mathrm{prevBlock}h.prevBlock equals the header hash of tip\mathrm{tip}tip (otherwise the outcome is "missing previous", not accept); the 32-bit value of h.bitsh.\mathrm{bits}h.bits equals the required work computed from SSS by the imported difficulty rule; the median time past of SSS at tipHeight\mathrm{tipHeight}tipHeight is strictly less than h.timeh.\mathrm{time}h.time; h.time≤t+7200h.\mathrm{time} \le t + 7200h.time≤t+7200 (otherwise the outcome is "future time", not accept); and it is not the case that (h.version<2h.\mathrm{version} < 2h.version<2 and 227931≤tipHeight+1227931 \le \mathrm{tipHeight}+1227931≤tipHeight+1), nor (h.version<3h.\mathrm{version} < 3h.version<3 and 363725≤tipHeight+1363725 \le \mathrm{tipHeight}+1363725≤tipHeight+1), nor (h.version<4h.\mathrm{version} < 4h.version<4 and 388381≤tipHeight+1388381 \le \mathrm{tipHeight}+1388381≤tipHeight+1).

  2. Context-free block stage. The proof-of-work test again; the Merkle root computed from the txids of b.vtxb.\mathrm{vtx}b.vtx equals h.merkleRooth.\mathrm{merkleRoot}h.merkleRoot and the Merkle computation reports no mutation; b.vtxb.\mathrm{vtx}b.vtx is non-empty; 4⋅∣b.vtx∣≤4,000,0004\cdot|b.\mathrm{vtx}| \le 4{,}000{,}0004⋅∣b.vtx∣≤4,000,000 and 4⋅(length of the witness-stripped serialization of b)≤4,000,0004\cdot(\text{length of the witness-stripped serialization of } b) \le 4{,}000{,}0004⋅(length of the witness-stripped serialization of b)≤4,000,000; cb\mathrm{cb}cb is a coinbase and no other transaction of bbb is; every transaction has non-empty inputs and outputs, witness-stripped size times 4 at most 4,000,0004{,}000{,}0004,000,000, every output value in [0,2.1×1015][0, 2.1\times 10^{15}][0,2.1×1015] with running totals in that range, pairwise distinct previous outpoints, and (for a coinbase) a first-input scriptSig of length between 222 and 100100100 inclusive, or (for a non-coinbase) no null previous outpoint; and 4⋅∑4\cdot\sum4⋅∑ of the legacy signature-operation counts is at most 80,00080{,}00080,000.

  3. Contextual stage. Every transaction of bbb is final at height HHH against a cutoff (the median time past of SSS if 419328≤tipHeight+1419328 \le \mathrm{tipHeight}+1419328≤tipHeight+1, else h.timeh.\mathrm{time}h.time); if 227931≤tipHeight+1227931 \le \mathrm{tipHeight}+1227931≤tipHeight+1 then heightScript(H)\mathrm{heightScript}(H)heightScript(H) is a prefix of the scriptSig of the first input of cb\mathrm{cb}cb (the first input being the default input with empty scriptSig if cb\mathrm{cb}cb has no inputs) — this byte string is literally the same expression as coinbaseScriptSig(b)\mathrm{coinbaseScriptSig}(b)coinbaseScriptSig(b); the witness-malleation check passes with the expectation flag set iff 481824≤tipHeight+1481824 \le \mathrm{tipHeight}+1481824≤tipHeight+1; and the block weight (3×3\times3× stripped size +++ full size) is at most 4,000,0004{,}000{,}0004,000,000.

  4. Connect stage. Let η:=headerHash(h)\eta := \mathrm{headerHash}(h)η:=headerHash(h). If η\etaη equals the fixed genesis block hash GGG (32 bytes beginning 6f e2 8c 0a\mathtt{6f\,e2\,8c\,0a}6fe28c0a), the stage succeeds immediately with ledger S.utxoS.\mathrm{utxo}S.utxo and empty undo list, performing no further check. Otherwise: if bip30Checked(S,H,η)=true\mathrm{bip30Checked}(S,H,\eta) = \mathtt{true}bip30Checked(S,H,η)=true (see the ScanRuns unfolding) and it is not the case that for every tx∈b.vtx\mathrm{tx} \in b.\mathrm{vtx}tx∈b.vtx and every o<∣tx.vout∣o < |\mathrm{tx}.\mathrm{vout}|o<∣tx.vout∣ the ledger S.utxoS.\mathrm{utxo}S.utxo has no entry keyed (txid(tx),o)(\mathrm{txid}(\mathrm{tx}), o)(txid(tx),o), the stage fails; otherwise the transactions are processed in order through the imported per-transaction loop (input lookup and maturity, fee range, sequence locks, sigop budget, full script verification, ledger update), which must succeed, and finally the output value of cb\mathrm{cb}cb must be at most the accumulated fees plus the subsidy at height HHH.

On success, S′=(S.headers+ ⁣ ⁣+[h], u)S' = \big(S.\mathrm{headers} \mathbin{+\!\!+} [h],\ u\big)S′=(S.headers++[h], u) where uuu is the ledger produced by stage 4, and UUU is the undo list produced by stage 4. In particular ∣S′.headers∣=H+1|S'.\mathrm{headers}| = H + 1∣S′.headers∣=H+1.

What reachability says

Reachable(S)\mathrm{Reachable}(S)Reachable(S) is the least predicate such that (i) the initial state ([genesis header], [ ])\big([\text{genesis header}],\ [\,]\big)([genesis header], []) (one header, empty ledger) is reachable, and (ii) whenever S0S_0S0​ is reachable and validate(S0,b0,t0)=accept(S1,U0)\mathrm{validate}(S_0, b_0, t_0) = \mathrm{accept}(S_1, U_0)validate(S0​,b0​,t0​)=accept(S1​,U0​) for some block b0b_0b0​, integer t0t_0t0​ and undo list U0U_0U0​, then S1S_1S1​ is reachable. So Reachable(S)\mathrm{Reachable}(S)Reachable(S) means SSS arises from the initial state by a finite sequence of accepted validations, each with its own arbitrary clock reading.

Edge cases and scope

  • The conclusion is vacuous for a block with no transactions or for transactions with no outputs; stage 2 of validation requires b.vtxb.\mathrm{vtx}b.vtx non-empty and every transaction to have outputs, so under the hypotheses these do not occur, but the conclusion itself does not say so.
  • S′S'S′, UUU and ttt appear only inside the acceptance hypothesis; the conclusion does not mention them.
  • The hypothesis headerHash(b.header)≠G\mathrm{headerHash}(b.\mathrm{header}) \ne GheaderHash(b.header)=G excludes exactly the case in which stage 4 of validation takes its genesis shortcut (which performs no ledger check at all).
  • Under ScanRuns(S,b)\mathrm{ScanRuns}(S,b)ScanRuns(S,b) and the non-genesis hypothesis, stage 4 of validation fails unless the Boolean form of the same quantified condition as the conclusion holds on S.utxoS.\mathrm{utxo}S.utxo; the read-back records this as the structure of the definitions, not as an assessment.
  • The conclusion says nothing about duplicate txids within bbb, nor about the ledger S′.utxoS'.\mathrm{utxo}S′.utxo after connection, nor about any outpoint that bbb does not create.
Human review
  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 29, 2026

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

View graph

Get started

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

About Prove2Me

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

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me