Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

An accepted post-BIP34 block's coinbase starts with its height push

Proved
BitcoinUniqueness.coinbase_height_prefix

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

bip30bip34bitcoinbitcoin-mainnetcoinbaseconsensusformal-verificationuniqueness

For a reachable state at next height ≥227,931\ge 227{,}931≥227,931 and an accepted block: heightScript S.nextHeight is a prefix of coinbaseScriptSig b. From the acceptance theorem's contextual clause (ContextualCheckBlock's bad-cb-height).

Preamble
import Definitions.Def_BitcoinUniqueness
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinHeader
open BitcoinUniqueness BitcoinSer BitcoinBlockV2
Formal statement
theorem BitcoinUniqueness.coinbase_height_prefix (S : ChainState) (b : BitcoinSer.Block) (now : Int) (S' : ChainState)
    (undo : BlockUndo) (hR : BitcoinBlockV2.Reachable S) (h : BitcoinBlockV2.validate S b now = .accept S' undo)
    (h34 : BitcoinHeader.BIP34Height ≤ S.nextHeight) :
    (BitcoinBlockV2.heightScript S.nextHeight).isPrefixOf (BitcoinUniqueness.coinbaseScriptSig b) = true := 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.coinbase_height_prefix

Statement. For every chain state SSS, block bbb, integer ttt (clock reading), chain state S′S'S′, and undo list UUU, 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), and
  • 227,931≤∣S.headers∣227{,}931 \le |S.\mathrm{headers}|227,931≤∣S.headers∣ (the constant BIP34Height\mathrm{BIP34Height}BIP34Height is at most the next height of SSS),

then the byte string heightScript(∣S.headers∣)\mathrm{heightScript}(|S.\mathrm{headers}|)heightScript(∣S.headers∣) is a prefix (initial segment, possibly the whole string) of the byte string coinbaseScriptSig(b)\mathrm{coinbaseScriptSig}(b)coinbaseScriptSig(b).

Formally, with H:=∣S.headers∣H := |S.\mathrm{headers}|H:=∣S.headers∣:

∀S b t S′ U,Reachable(S)∧validate(S,b,t)=accept(S′,U)∧227931≤H ⟹ heightScript(H)⊑coinbaseScriptSig(b),\forall S\, b\, t\, S'\, U,\quad \mathrm{Reachable}(S) \wedge \mathrm{validate}(S,b,t) = \mathrm{accept}(S',U) \wedge 227931 \le H \ \Longrightarrow\ \mathrm{heightScript}(H) \sqsubseteq \mathrm{coinbaseScriptSig}(b),∀SbtS′U,Reachable(S)∧validate(S,b,t)=accept(S′,U)∧227931≤H ⟹ heightScript(H)⊑coinbaseScriptSig(b),

where x⊑yx \sqsubseteq yx⊑y means y=x+ ⁣ ⁣+zy = x \mathbin{+\!\!+} zy=x++z for some byte string zzz.

What coinbaseScriptSig says

coinbaseScriptSig(b)\mathrm{coinbaseScriptSig}(b)coinbaseScriptSig(b) is the scriptSig (a byte string) of the first input of the first transaction of b.vtxb.\mathrm{vtx}b.vtx, with two fallbacks: if b.vtxb.\mathrm{vtx}b.vtx is empty, the fixed genesis coinbase transaction stands in for the first transaction (its scriptSig is a fixed 77-byte string); if that transaction has no inputs, a default input with empty scriptSig stands in, giving the empty string.

What heightScript says

For a natural number nnn, heightScript(n)\mathrm{heightScript}(n)heightScript(n) is the byte string

heightScript(n)={[0x00]n=0,[0x50+n]1≤n≤16 (a single byte in 0x51..0x60),pushBytes(serialize(n))n≥17,\mathrm{heightScript}(n) = \begin{cases} [\mathtt{0x00}] & n = 0,\\ [\mathtt{0x50} + n] & 1 \le n \le 16 \ (\text{a single byte in } \mathtt{0x51}..\mathtt{0x60}),\\ \mathrm{pushBytes}(\mathrm{serialize}(n)) & n \ge 17,\end{cases}heightScript(n)=⎩⎨⎧​[0x00][0x50+n]pushBytes(serialize(n))​n=0,1≤n≤16 (a single byte in 0x51..0x60),n≥17,​

where, for n≥17n \ge 17n≥17 (so nnn is positive and serialize\mathrm{serialize}serialize takes its non-negative branch): serialize(n)\mathrm{serialize}(n)serialize(n) is the little-endian base-256 digit string of nnn with no trailing zero byte (the "magnitude"), followed by an extra byte 0x00\mathtt{0x00}0x00 if and only if the top bit (0x80\mathtt{0x80}0x80) of the magnitude's last byte is set; and pushBytes(d)\mathrm{pushBytes}(d)pushBytes(d), for a byte string ddd, is [ ∣d∣ ]+ ⁣ ⁣+d[\,|d|\,] \mathbin{+\!\!+} d[∣d∣]++d (one length byte then the data) when ∣d∣<76|d| < 76∣d∣<76, is [0x4c,∣d∣]+ ⁣ ⁣+d[\mathtt{0x4c}, |d|] \mathbin{+\!\!+} d[0x4c,∣d∣]++d when 76≤∣d∣≤25576 \le |d| \le 25576≤∣d∣≤255, is [0x4d]+ ⁣ ⁣+(2 little-endian bytes of ∣d∣)+ ⁣ ⁣+d[\mathtt{0x4d}] \mathbin{+\!\!+} (\text{2 little-endian bytes of } |d|) \mathbin{+\!\!+} d[0x4d]++(2 little-endian bytes of ∣d∣)++d when 256≤∣d∣≤65535256 \le |d| \le 65535256≤∣d∣≤65535, and is [0x4e]+ ⁣ ⁣+(4 little-endian bytes of ∣d∣ mod 232)+ ⁣ ⁣+d[\mathtt{0x4e}] \mathbin{+\!\!+} (\text{4 little-endian bytes of } |d| \bmod 2^{32}) \mathbin{+\!\!+} d[0x4e]++(4 little-endian bytes of ∣d∣mod232)++d otherwise. For 17≤n<23117 \le n < 2^{31}17≤n<231 the magnitude has between 1 and 4 bytes, so serialize(n)\mathrm{serialize}(n)serialize(n) has between 1 and 5 bytes and heightScript(n)\mathrm{heightScript}(n)heightScript(n) is one length byte (value 1 to 5) followed by those bytes.

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 height in the conclusion is ∣S.headers∣|S.\mathrm{headers}|∣S.headers∣, the length of the header list of the state before bbb is connected; it is not read from bbb and is not ∣S′.headers∣|S'.\mathrm{headers}|∣S′.headers∣ (which is one larger).
  • Under 227,931≤H227{,}931 \le H227,931≤H the header list is non-empty, so tipHeight+1=H\mathrm{tipHeight} + 1 = HtipHeight+1=H and the conditional BIP34 clause of validation stage 3 is in force; that clause compares heightScript(H)\mathrm{heightScript}(H)heightScript(H) against the very same byte-string expression that defines coinbaseScriptSig(b)\mathrm{coinbaseScriptSig}(b)coinbaseScriptSig(b). The read-back records this as the structure of the definitions.
  • Stage 2 of validation requires b.vtxb.\mathrm{vtx}b.vtx to be non-empty with a coinbase first transaction (exactly one input), so under the hypotheses neither fallback of coinbaseScriptSig\mathrm{coinbaseScriptSig}coinbaseScriptSig (genesis coinbase, default input) is exercised; the conclusion itself does not say so.
  • No upper bound on HHH is assumed here (unlike the sibling statements); heightScript\mathrm{heightScript}heightScript is defined for every natural number.
  • S′S'S′, UUU and ttt appear only in the acceptance hypothesis.
  • The statement asserts a prefix relation only: the coinbase scriptSig may contain arbitrary further bytes after the height push, and nothing is claimed about its length beyond what stage 2 requires (between 2 and 100 bytes).
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