Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Median time past and the contextual block-header rules

Definition
BitcoinHeader

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

bitcoinbitcoin-mainnetblock-headerconsensusformal-verificationmedian-time-past

A chain of ancestors is the list of its block times t0,t1,…t_0, t_1, \dotst0​,t1​,…, most recent first. The window is the first nMedianTimeSpan=11\mathrm{nMedianTimeSpan} = 11nMedianTimeSpan=11 times. The median time past of a chain sorts its window by ≤\le≤ and returns the element at index ⌊∣w∣/2⌋\lfloor |w| / 2 \rfloor⌊∣w∣/2⌋, or 000 for an empty chain:

MTP(t0,t1,… )=sort(t0,…,tmin⁡(10, n−1))[⌊min⁡(11,n)/2⌋].\mathrm{MTP}(t_0, t_1, \dots) = \mathrm{sort}(t_0, \dots, t_{\min(10,\,n-1)})\big[\lfloor \min(11, n) / 2 \rfloor\big].MTP(t0​,t1​,…)=sort(t0​,…,tmin(10,n−1)​)[⌊min(11,n)/2⌋].

A header has a version, a time and nBits. MAX_FUTURE_BLOCK_TIME=7,200\mathrm{MAX\_FUTURE\_BLOCK\_TIME} = 7{,}200MAX_FUTURE_BLOCK_TIME=7,200 seconds. The mainnet activation heights are BIP34Height=227,931\mathrm{BIP34Height} = 227{,}931BIP34Height=227,931, BIP66Height=363,725\mathrm{BIP66Height} = 363{,}725BIP66Height=363,725, BIP65Height=388,381\mathrm{BIP65Height} = 388{,}381BIP65Height=388,381. activeAfter(prevHeight, h) holds when h≤prevHeight+1h \le \mathrm{prevHeight} + 1h≤prevHeight+1, as DeploymentActiveAfter for a buried deployment. versionOutdated(v, prevHeight) holds when v<2v < 2v<2 with BIP34 active, or v<3v < 3v<3 with BIP66 active, or v<4v < 4v<4 with BIP65 active.

contextualCheck(header, prevHeight, prevTimes, required, now) is ContextualCheckBlockHeader at mainnet parameters: nBits === required, MTP(prevTimes)<\mathrm{MTP}(\text{prevTimes}) <MTP(prevTimes)< time, time ≤\le≤ now +7,200+ 7{,}200+7,200, and the version is not outdated. The required nBits is supplied by the caller, as GetNextWorkRequired computes it.

Formalization Note. Times are Int; the sort is List.mergeSort on ≤ and the index access is getD with default 0. enforce_BIP94 is false as on mainnet, so the testnet timewarp rule is absent. Only Std is imported.

Definition code
import Std

namespace BitcoinHeader

/-! Transcription of the contextual block-header rules of Bitcoin Core at revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`: `CBlockIndex::GetMedianTimePast` (`chain.h`),
`ContextualCheckBlockHeader` (`validation.cpp`), `DeploymentActiveAfter` for buried deployments
(`deploymentstatus.h`), `MAX_FUTURE_BLOCK_TIME` (`chain.h`), and the mainnet activation heights
of BIP34, BIP66 and BIP65 (`kernel/chainparams.cpp`), with `enforce_BIP94 = false` as on mainnet.

A chain of ancestors is represented by the list of its block times, most recent first
(`pindex`, `pindex->pprev`, …). The required `nBits` is supplied by the caller, as it is computed
by `GetNextWorkRequired` in the proof-of-work development. -/

/-- `chain.h`: `MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60`. -/
def MAX_FUTURE_BLOCK_TIME : Int := 2 * 60 * 60

/-- `CBlockIndex::nMedianTimeSpan = 11`. -/
def nMedianTimeSpan : Nat := 11

/-- `CMainParams`: `BIP34Height = 227931` (`DEPLOYMENT_HEIGHTINCB`). -/
def BIP34Height : Nat := 227931

/-- `CMainParams`: `BIP66Height = 363725` (`DEPLOYMENT_DERSIG`). -/
def BIP66Height : Nat := 363725

/-- `CMainParams`: `BIP65Height = 388381` (`DEPLOYMENT_CLTV`). -/
def BIP65Height : Nat := 388381

/-- The window `GetMedianTimePast` sorts: the times of the block and its ancestors, at most
`nMedianTimeSpan` of them. -/
def timeWindow (times : List Int) : List Int := times.take nMedianTimeSpan

/-- `GetMedianTimePast`: sort the window and take the element at index `size / 2`. The result is
`0` for an empty chain, which the source never queries. -/
def medianTimePast (times : List Int) : Int :=
  let w := timeWindow times
  (w.mergeSort fun a b => decide (a ≤ b)).getD (w.length / 2) 0

/-- A block header, reduced to the fields the contextual rules read. -/
structure Header where
  version : Int
  time : Int
  bits : BitVec 32

/-- `DeploymentActiveAfter(pindexPrev, dep)` for a buried deployment:
`pindexPrev->nHeight + 1 >= DeploymentHeight(dep)`. -/
def activeAfter (prevHeight : Nat) (deploymentHeight : Nat) : Bool :=
  decide (deploymentHeight ≤ prevHeight + 1)

/-- The version floor of `ContextualCheckBlockHeader`: rejected when the version is below 2, 3
or 4 while BIP34, BIP66 or BIP65 respectively is active for the next block. -/
def versionOutdated (version : Int) (prevHeight : Nat) : Bool :=
  (decide (version < 2) && activeAfter prevHeight BIP34Height) ||
  (decide (version < 3) && activeAfter prevHeight BIP66Height) ||
  (decide (version < 4) && activeAfter prevHeight BIP65Height)

/-- `ContextualCheckBlockHeader` at mainnet parameters: `nBits` equals the required work, the time
exceeds the previous block's median time past, the time is at most the local clock plus
`MAX_FUTURE_BLOCK_TIME`, and the version is not outdated. `prevTimes` lists the times of the
previous block and its ancestors, most recent first. -/
def contextualCheck (h : Header) (prevHeight : Nat) (prevTimes : List Int) (required : BitVec 32)
    (now : Int) : Bool :=
  decide (h.bits = required) &&
  decide (medianTimePast prevTimes < h.time) &&
  decide (h.time ≤ now + MAX_FUTURE_BLOCK_TIME) &&
  !versionOutdated h.version prevHeight

end BitcoinHeader
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: CBlockIndex::GetMedianTimePast and nMedianTimeSpan, MAX_FUTURE_BLOCK_TIME, src/chain.h: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/chain.h; ContextualCheckBlockHeader, src/validation.cpp (lines 4091-4128): https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/validation.cpp; DeploymentActiveAfter (buried), src/deploymentstatus.h; BIP34Height, BIP66Height, BIP65Height in CMainParams, src/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)

MAX_FUTURE_BLOCK_TIME. This is a named integer constant (an element of Z\mathbb{Z}Z, not of N\mathbb{N}N) whose value is 2⋅60⋅60=72002 \cdot 60 \cdot 60 = 72002⋅60⋅60=7200. Nothing else is asserted about it; it is simply the number 720072007200 typed as an integer.

nMedianTimeSpan. This is a named natural-number constant whose value is 111111.

BIP34Height. This is a named natural-number constant whose value is 227931227931227931.

BIP66Height. This is a named natural-number constant whose value is 363725363725363725.

BIP65Height. This is a named natural-number constant whose value is 388381388381388381.

timeWindow. This is a function from finite lists of integers to finite lists of integers. Given a list T=[t0,t1,t2,… ]T = [t_0, t_1, t_2, \dots]T=[t0​,t1​,t2​,…] of integers (indexed from 000, in the order in which the list is given), timeWindow(T)\mathrm{timeWindow}(T)timeWindow(T) is the list consisting of the first min⁡(11,∣T∣)\min(11, |T|)min(11,∣T∣) entries of TTT, in their original order:

timeWindow(T)=[t0,t1,…,tmin⁡(11,∣T∣)−1].\mathrm{timeWindow}(T) = [t_0, t_1, \dots, t_{\min(11,|T|)-1}].timeWindow(T)=[t0​,t1​,…,tmin(11,∣T∣)−1​].

If ∣T∣≤11|T| \le 11∣T∣≤11 the window is TTT itself (in particular, the window of the empty list is the empty list); if ∣T∣>11|T| > 11∣T∣>11 the entries t11,t12,…t_{11}, t_{12}, \dotst11​,t12​,… are discarded. No sorting or reordering takes place in this definition.

medianTimePast. This is a function from finite lists of integers to a single integer. Given a list of integers TTT, let W=timeWindow(T)W = \mathrm{timeWindow}(T)W=timeWindow(T) be the list of its first min⁡(11,∣T∣)\min(11,|T|)min(11,∣T∣) entries as above, let n=∣W∣n = |W|n=∣W∣ (so 0≤n≤110 \le n \le 110≤n≤11), and let W↑=[w0≤w1≤⋯≤wn−1]W^{\uparrow} = [w_0 \le w_1 \le \dots \le w_{n-1}]W↑=[w0​≤w1​≤⋯≤wn−1​] be the list obtained by sorting WWW into non-decreasing order (a merge sort using the comparison "a≤ba \le ba≤b"; since equal integers are indistinguishable as values, the handling of ties does not affect the result). Then

medianTimePast(T)={w⌊n/2⌋if n≥1,0if n=0,\mathrm{medianTimePast}(T) = \begin{cases} w_{\lfloor n/2 \rfloor} & \text{if } n \ge 1,\\ 0 & \text{if } n = 0,\end{cases}medianTimePast(T)={w⌊n/2⌋​0​if n≥1,if n=0,​

where ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ is natural-number division (rounding down) and indexing is from 000. Concretely: the function reads the entry at position ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ of the sorted window and returns the fallback value 000 if that position does not exist, which happens exactly when the window is empty, i.e. exactly when TTT is the empty list. For n≥1n \ge 1n≥1 the position ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ always lies in range, so the fallback is never used. When nnn is odd, say n=2k+1n = 2k+1n=2k+1, the result is wkw_kwk​, the unique middle element of the sorted window (the (k+1)(k+1)(k+1)-st smallest). When nnn is even and positive, say n=2kn = 2kn=2k, the result is wkw_kwk​, the upper of the two middle elements (the (k+1)(k+1)(k+1)-st smallest), not their average and not the lower middle element. For example, for T=[a]T = [a]T=[a] the result is aaa; for T=[a,b]T = [a, b]T=[a,b] the result is max⁡(a,b)\max(a,b)max(a,b); for TTT of length ≥11\ge 11≥11 the result is w5w_5w5​, the 666-th smallest among the first 111111 entries of TTT. Note that the result is always a value that occurs in the window when T≠[]T \ne []T=[], and is the number 000 (which need not occur in TTT) when T=[]T = []T=[].

Header. This is a record type with exactly three fields and no constraints between them: a field version, which is an arbitrary integer (it may be negative or arbitrarily large; it is not restricted to 32 bits); a field time, which is an arbitrary integer (likewise unrestricted); and a field bits, which is a bit-vector of exactly 323232 bits (equivalently, an element of {0,1,…,232−1}\{0, 1, \dots, 2^{32}-1\}{0,1,…,232−1}). Any triple of such values is a Header.

activeAfter. This is a function taking two natural numbers, ppp (named prevHeight) and ddd (named deploymentHeight), and returning a Boolean truth value (true/false). It returns true exactly when

d≤p+1,d \le p + 1,d≤p+1,

where +++ is natural-number addition (no overflow), and false otherwise. Equivalently, it is true iff p≥d−1p \ge d - 1p≥d−1 when d≥1d \ge 1d≥1, and is always true when d=0d = 0d=0.

versionOutdated. This is a function taking an integer vvv (named version; any integer, possibly negative) and a natural number ppp (named prevHeight) and returning a Boolean. It is true exactly when at least one of the following three conditions holds (Boolean "or" of three Boolean "and"s):

(v<2  ∧  227931≤p+1)  ∨  (v<3  ∧  363725≤p+1)  ∨  (v<4  ∧  388381≤p+1),\bigl(v < 2 \;\wedge\; 227931 \le p+1\bigr) \;\vee\; \bigl(v < 3 \;\wedge\; 363725 \le p+1\bigr) \;\vee\; \bigl(v < 4 \;\wedge\; 388381 \le p+1\bigr),(v<2∧227931≤p+1)∨(v<3∧363725≤p+1)∨(v<4∧388381≤p+1),

where each "d≤p+1d \le p + 1d≤p+1" is the activeAfter test unfolded with ddd equal to the constants 227931227931227931, 363725363725363725, 388381388381388381 respectively. Here v<2v < 2v<2 etc. are integer comparisons (so, e.g., every negative vvv satisfies all three), and p+1p + 1p+1 is natural-number addition. Equivalently (since 227931≤p+1  ⟺  p≥227930227931 \le p+1 \iff p \ge 227930227931≤p+1⟺p≥227930, etc.): true iff (v≤1v \le 1v≤1 and p≥227930p \ge 227930p≥227930) or (v≤2v \le 2v≤2 and p≥363724p \ge 363724p≥363724) or (v≤3v \le 3v≤3 and p≥388380p \ge 388380p≥388380). For p≤227929p \le 227929p≤227929 the function is false regardless of vvv; for v≥4v \ge 4v≥4 the function is false regardless of ppp.

contextualCheck. This is a function taking a Header hhh (with integer fields h.versionh.\mathrm{version}h.version, h.timeh.\mathrm{time}h.time and 32-bit field h.bitsh.\mathrm{bits}h.bits), a natural number ppp (named prevHeight), a list of integers PPP (named prevTimes), a 32-bit bit-vector rrr (named required, supplied by the caller and not computed by anything in this file), and an integer ν\nuν (named now; an arbitrary integer parameter), and returning a Boolean. It is true exactly when all four of the following hold (Boolean "and" of four conditions):

  1. h.bits=rh.\mathrm{bits} = rh.bits=r, equality of 32-bit bit-vectors;
  2. medianTimePast(P)<h.time\mathrm{medianTimePast}(P) < h.\mathrm{time}medianTimePast(P)<h.time (strict), where medianTimePast(P)\mathrm{medianTimePast}(P)medianTimePast(P) is, as unfolded above, the entry at position ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ of the non-decreasing sort of the first n=min⁡(11,∣P∣)n=\min(11,|P|)n=min(11,∣P∣) entries of PPP, and is 000 when PPP is the empty list — so for P=[]P = []P=[] this conjunct reads 0<h.time0 < h.\mathrm{time}0<h.time;
  3. h.time≤ν+7200h.\mathrm{time} \le \nu + 7200h.time≤ν+7200 (non-strict), integer arithmetic, where 720072007200 is the constant MAX_FUTURE_BLOCK_TIME;
  4. the Boolean negation of versionOutdated(h.version,p)\mathrm{versionOutdated}(h.\mathrm{version}, p)versionOutdated(h.version,p), i.e.
¬[(h.version<2∧227931≤p+1)∨(h.version<3∧363725≤p+1)∨(h.version<4∧388381≤p+1)].\neg\Bigl[\bigl(h.\mathrm{version} < 2 \wedge 227931 \le p+1\bigr) \vee \bigl(h.\mathrm{version} < 3 \wedge 363725 \le p+1\bigr) \vee \bigl(h.\mathrm{version} < 4 \wedge 388381 \le p+1\bigr)\Bigr].¬[(h.version<2∧227931≤p+1)∨(h.version<3∧363725≤p+1)∨(h.version<4∧388381≤p+1)].

It is false if any one of the four conditions fails. Nothing in this definition relates ppp to ∣P∣|P|∣P∣, relates ν\nuν to the entries of PPP, or constrains rrr in any way; all five inputs are independent.

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

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 26, 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