Median time past and the contextual block-header rules
DefinitionBitcoinHeaderA chain of ancestors is the list of its block times , most recent first. The window is the first times. The median time past of a chain sorts its window by and returns the element at index , or for an empty chain:
A header has a version, a time and nBits. seconds. The mainnet activation heights are , , . activeAfter(prevHeight, h) holds when , as DeploymentActiveAfter for a buried deployment. versionOutdated(v, prevHeight) holds when with BIP34 active, or with BIP66 active, or with BIP65 active.
contextualCheck(header, prevHeight, prevTimes, required, now) is ContextualCheckBlockHeader at mainnet parameters: nBits required, time, time now , 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.
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
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 , not of ) whose value is . Nothing else is asserted about it; it is simply the number typed as an integer.
nMedianTimeSpan. This is a named natural-number constant whose value is .
BIP34Height. This is a named natural-number constant whose value is .
BIP66Height. This is a named natural-number constant whose value is .
BIP65Height. This is a named natural-number constant whose value is .
timeWindow. This is a function from finite lists of integers to finite lists of integers. Given a list of integers (indexed from , in the order in which the list is given), is the list consisting of the first entries of , in their original order:
If the window is itself (in particular, the window of the empty list is the empty list); if the entries 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 , let be the list of its first entries as above, let (so ), and let be the list obtained by sorting into non-decreasing order (a merge sort using the comparison ""; since equal integers are indistinguishable as values, the handling of ties does not affect the result). Then
where is natural-number division (rounding down) and indexing is from . Concretely: the function reads the entry at position of the sorted window and returns the fallback value if that position does not exist, which happens exactly when the window is empty, i.e. exactly when is the empty list. For the position always lies in range, so the fallback is never used. When is odd, say , the result is , the unique middle element of the sorted window (the -st smallest). When is even and positive, say , the result is , the upper of the two middle elements (the -st smallest), not their average and not the lower middle element. For example, for the result is ; for the result is ; for of length the result is , the -th smallest among the first entries of . Note that the result is always a value that occurs in the window when , and is the number (which need not occur in ) when .
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 bits (equivalently, an element of ). Any triple of such values is a Header.
activeAfter. This is a function taking two natural numbers, (named prevHeight) and (named deploymentHeight), and returning a Boolean truth value (true/false). It returns true exactly when
where is natural-number addition (no overflow), and false otherwise. Equivalently, it is true iff when , and is always true when .
versionOutdated. This is a function taking an integer (named version; any integer, possibly negative) and a natural number (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):
where each "" is the activeAfter test unfolded with equal to the constants , , respectively. Here etc. are integer comparisons (so, e.g., every negative satisfies all three), and is natural-number addition. Equivalently (since , etc.): true iff ( and ) or ( and ) or ( and ). For the function is false regardless of ; for the function is false regardless of .
contextualCheck. This is a function taking a Header (with integer fields , and 32-bit field ), a natural number (named prevHeight), a list of integers (named prevTimes), a 32-bit bit-vector (named required, supplied by the caller and not computed by anything in this file), and an integer (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):
- , equality of 32-bit bit-vectors;
- (strict), where is, as unfolded above, the entry at position of the non-decreasing sort of the first entries of , and is when is the empty list — so for this conjunct reads ;
- (non-strict), integer arithmetic, where is the constant
MAX_FUTURE_BLOCK_TIME; - the Boolean negation of , i.e.
It is false if any one of the four conditions fails. Nothing in this definition relates to , relates to the entries of , or constrains in any way; all five inputs are independent.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.