Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The header path is the Header mission's contextual check

Proved
BitcoinBlock.acceptHeader_iff

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

bip30bip34bitcoinbitcoin-mainnetblock-validationconnectblockconsensusformal-verificationundo

acceptHeader S h now = accept S [] iff the proof of work holds, h.prevBlock is the tip's hash, and the Header mission's contextualCheck holds with the chain's tip height, times, required bits and the clock.

Deprecated. Superseded by BitcoinBlockV2.acceptHeader_iff (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.

Preamble
import Definitions.Def_BitcoinBlock
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinHeader
Formal statement
theorem BitcoinBlock.acceptHeader_iff (S : ChainState) (h : BitcoinSer.Header) (now : Int) :
    BitcoinBlock.acceptHeader S h now = .accept S [] ↔
      BitcoinBlock.checkHeaderPow h = true ∧ h.prevBlock = S.tipHash ∧
      BitcoinHeader.contextualCheck ⟨h.version, (h.time : Int), BitVec.ofNat 32 h.bits⟩ S.tipHeight
        (S.timesTo S.tipHeight) S.requiredBits now = true := by sorry
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: BitcoinBlock.acceptHeader_iff

Binders

  • SSS : a chain state, i.e. a pair (headers,utxo)(\mathit{headers}, \mathit{utxo})(headers,utxo) where headers\mathit{headers}headers is a list of serialized block headers (each with fields: version ∈Z\in \mathbb{Z}∈Z, previous-block hash (a byte list), merkle root (a byte list), time ∈N\in \mathbb{N}∈N, bits ∈N\in \mathbb{N}∈N, nonce ∈N\in \mathbb{N}∈N) and utxo\mathit{utxo}utxo is a ledger (an association list from outpoints to coins). No hypothesis is placed on SSS: its header list may be empty, may not start with the genesis header, etc.
  • hhh : a serialized block header (same six fields as above; time and bits are unbounded natural numbers).
  • now∈Z\mathit{now} \in \mathbb{Z}now∈Z : the local clock.

There are no further hypotheses.

Conclusion

The statement is an equivalence (iff):

acceptHeader(S,h,now)=accept(S,[ ])  ⟺  checkHeaderPow(h)=true  ∧  h.prevBlock=tipHash(S)  ∧  contextualCheck(⟨h.version,h.time,bits32(h)⟩, tipHeight(S), timesTo(S,tipHeight(S)), requiredBits(S), now)=true.\mathrm{acceptHeader}(S, h, \mathit{now}) = \mathrm{accept}(S, [\,]) \iff \mathrm{checkHeaderPow}(h) = \mathrm{true} \;\wedge\; h.\mathrm{prevBlock} = \mathrm{tipHash}(S) \;\wedge\; \mathrm{contextualCheck}\big(\langle h.\mathrm{version}, h.\mathrm{time}, \mathrm{bits}_{32}(h)\rangle,\ \mathrm{tipHeight}(S),\ \mathrm{timesTo}(S, \mathrm{tipHeight}(S)),\ \mathrm{requiredBits}(S),\ \mathit{now}\big) = \mathrm{true}.acceptHeader(S,h,now)=accept(S,[])⟺checkHeaderPow(h)=true∧h.prevBlock=tipHash(S)∧contextualCheck(⟨h.version,h.time,bits32​(h)⟩, tipHeight(S), timesTo(S,tipHeight(S)), requiredBits(S), now)=true.

Left-hand side, unfolded

acceptHeader(S,h,now)\mathrm{acceptHeader}(S,h,\mathit{now})acceptHeader(S,h,now) is a value of the four-constructor outcome type (accept with a state and undo list / invalid / futureTime / missingPrev), computed by the following ordered chain of tests:

  1. if checkHeaderPow(h)\mathrm{checkHeaderPow}(h)checkHeaderPow(h) is false, the result is invalid;
  2. else if h.prevBlock≠tipHash(S)h.\mathrm{prevBlock} \ne \mathrm{tipHash}(S)h.prevBlock=tipHash(S), the result is missingPrev;
  3. else if bits32(h)≠requiredBits(S)\mathrm{bits}_{32}(h) \ne \mathrm{requiredBits}(S)bits32​(h)=requiredBits(S), the result is invalid;
  4. else if h.time≤mtp(S)h.\mathrm{time} \le \mathrm{mtp}(S)h.time≤mtp(S) (as integers), the result is invalid;
  5. else if now+7200<h.time\mathit{now} + 7200 < h.\mathrm{time}now+7200<h.time, the result is futureTime;
  6. else if versionOutdated(h.version,tipHeight(S))\mathrm{versionOutdated}(h.\mathrm{version}, \mathrm{tipHeight}(S))versionOutdated(h.version,tipHeight(S)), the result is invalid;
  7. else the result is accept(S,[ ])\mathrm{accept}(S, [\,])accept(S,[]): the very same state SSS and the empty undo list.

So the left side holds exactly when all six tests pass (constructor equality on the outcome type; the accepted state must be literally SSS and the undo list literally empty, which is what step 7 produces).

Here:

  • bits32(h)\mathrm{bits}_{32}(h)bits32​(h) is h.bitsh.\mathrm{bits}h.bits reduced modulo 2322^{32}232 and viewed as a 32-bit word.
  • checkHeaderPow(h)\mathrm{checkHeaderPow}(h)checkHeaderPow(h): let HHH be the little-endian numeric value of the 32-byte double-SHA256 of the serialized header; decode bits32(h)\mathrm{bits}_{32}(h)bits32​(h) as a compact target (mantissa == = low 23 bits, exponent === top byte, shifted into 256 bits with truncation modulo 22562^{256}2256); the check is false if the compact word is "negative" (mantissa non-zero and bit 0x008000000x008000000x00800000 set), the decoded target is 000, the compact word "overflows", or the target exceeds 2224−12^{224}-12224−1; otherwise it is H≤targetH \le \text{target}H≤target.
  • tipHeight(S)=∣headers∣−1\mathrm{tipHeight}(S) = |\mathit{headers}| - 1tipHeight(S)=∣headers∣−1 with natural-number subtraction (so 000 when the header list is empty).
  • tip(S)\mathrm{tip}(S)tip(S) is the last header of SSS, or the genesis header if the list is empty; tipHash(S)\mathrm{tipHash}(S)tipHash(S) is its double-SHA256 header hash.
  • timesTo(S,k)\mathrm{timesTo}(S, k)timesTo(S,k) is the list of the times (as integers) of the first k+1k+1k+1 headers of SSS, most recent first.
  • mtp(S)\mathrm{mtp}(S)mtp(S) is the median-time-past of the tip: take the first 111111 entries of timesTo(S,tipHeight(S))\mathrm{timesTo}(S, \mathrm{tipHeight}(S))timesTo(S,tipHeight(S)), sort them ascending, and take the element at index ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ (nnn the window length), with default 000 for an empty window.
  • requiredBits(S)\mathrm{requiredBits}(S)requiredBits(S): with first\mathit{first}first the header at index tipHeight(S)−2015\mathrm{tipHeight}(S) - 2015tipHeight(S)−2015 (natural subtraction, so index 000 when the tip height is below 201520152015; the genesis header if that index is out of range), it is nextWorkRequired(tipHeight(S),bits32(tip),tip.time,first.time)\mathrm{nextWorkRequired}(\mathrm{tipHeight}(S), \mathrm{bits}_{32}(\mathrm{tip}), \mathrm{tip.time}, \mathit{first}.\mathrm{time})nextWorkRequired(tipHeight(S),bits32​(tip),tip.time,first.time): the tip's bits unchanged unless tipHeight+1\mathrm{tipHeight}+1tipHeight+1 is a multiple of 201620162016, in which case the retargeted compact word computed from the clamped timespan tip.time−first.time\mathrm{tip.time} - \mathit{first}.\mathrm{time}tip.time−first.time.
  • versionOutdated(v,p)\mathrm{versionOutdated}(v, p)versionOutdated(v,p) holds when v<2v<2v<2 and 227931≤p+1227931 \le p+1227931≤p+1, or v<3v<3v<3 and 363725≤p+1363725 \le p+1363725≤p+1, or v<4v<4v<4 and 388381≤p+1388381 \le p+1388381≤p+1.

Right-hand side, unfolded

The right side is a conjunction of three Boolean equalities:

  1. checkHeaderPow(h)=true\mathrm{checkHeaderPow}(h) = \mathrm{true}checkHeaderPow(h)=true (as above);
  2. h.prevBlock=tipHash(S)h.\mathrm{prevBlock} = \mathrm{tipHash}(S)h.prevBlock=tipHash(S) (byte-list equality);
  3. contextualCheck\mathrm{contextualCheck}contextualCheck from the header-rules development, applied to the reduced header ⟨h.version, h.time cast to Z, bits32(h)⟩\langle h.\mathrm{version},\ h.\mathrm{time} \text{ cast to } \mathbb{Z},\ \mathrm{bits}_{32}(h)\rangle⟨h.version, h.time cast to Z, bits32​(h)⟩, the previous height tipHeight(S)\mathrm{tipHeight}(S)tipHeight(S), the previous times timesTo(S,tipHeight(S))\mathrm{timesTo}(S,\mathrm{tipHeight}(S))timesTo(S,tipHeight(S)), the required word requiredBits(S)\mathrm{requiredBits}(S)requiredBits(S) and the clock now\mathit{now}now. That function is the conjunction
bits32(h)=requiredBits(S)  ∧  medianTimePast(timesTo(S,tipHeight(S)))<h.time  ∧  h.time≤now+7200  ∧  ¬ versionOutdated(h.version,tipHeight(S)),\mathrm{bits}_{32}(h) = \mathrm{requiredBits}(S) \;\wedge\; \mathrm{medianTimePast}(\mathrm{timesTo}(S,\mathrm{tipHeight}(S))) < h.\mathrm{time} \;\wedge\; h.\mathrm{time} \le \mathit{now} + 7200 \;\wedge\; \neg\,\mathrm{versionOutdated}(h.\mathrm{version}, \mathrm{tipHeight}(S)),bits32​(h)=requiredBits(S)∧medianTimePast(timesTo(S,tipHeight(S)))<h.time∧h.time≤now+7200∧¬versionOutdated(h.version,tipHeight(S)),

where medianTimePast\mathrm{medianTimePast}medianTimePast is the same window-of-11 sorted median described above and 720072007200 is the header development's own constant 2⋅60⋅602\cdot 60\cdot 602⋅60⋅60 (a separate definition from the block development's constant of the same value).

Edge cases silently included

Empty header list (tipHeight=0\mathrm{tipHeight}=0tipHeight=0, tip defaults to the genesis header, median defaults over a window of length 000 gives 000); h.bitsh.\mathrm{bits}h.bits and h.timeh.\mathrm{time}h.time are unbounded naturals reduced/cast when used; tipHeight−2015\mathrm{tipHeight}-2015tipHeight−2015 clamps at 000; the header at index tipHeight−2015\mathrm{tipHeight}-2015tipHeight−2015 defaults to the genesis header when out of range; no well-formedness of SSS or hhh is assumed; the "futureTime" and "missingPrev" outcomes are both just "not accept" on the left.

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