Compact targets, proof of work, and difficulty retargeting at mainnet parameters
DefinitionBitcoinPowThis file transcribes the mainnet proof-of-work arithmetic of Bitcoin Core. An arith_uint256 is modelled by its value, a natural number below (width); its left shift and its multiplications discard carries out of the top word, so they reduce modulo , and its division is exact integer division.
Parameters. , the target timespan seconds, the target spacing seconds, and the difficulty adjustment interval blocks.
Compact words. For a 32-bit word : the size and the mantissa . SetCompact yields when and otherwise. The word is negative when and ; it overflows when and (, or and , or and ). The exact value is the same formula without the reduction modulo .
Encoding. bitLength is at and otherwise. GetCompact of sets , forms the mantissa as when and as otherwise; if bit 23 of the mantissa is set it divides the mantissa by and increments ; the result is the 32-bit word mantissa .
Validation. deriveTarget returns the decoded value unless the word is negative, decodes to , overflows, or exceeds . checkProofOfWork(hash, word) holds when a target is derived and target. clampTimespan raises a signed timespan to and lowers it to . calculateNextWork(last word, last time, first time) decodes the last word, multiplies by the clamped elapsed time modulo , divides by , caps at , and re-encodes. permittedTransition(height, old, new) at a height divisible by requires the decoded new word to lie between the re-encoded caps of old and old (products modulo ); at other heights it requires old new. nextWorkRequired returns the last word unless the next height is divisible by , in which case it retargets.
These definitions fix the meaning of nBits on the wire and the retarget rule, as inputs for header validation.
Formalization Note. Compact words are BitVec 32 read through toNat; values are Nat; block times are Int, converted with Int.toNat only after clamping. fPowAllowMinDifficultyBlocks, fPowNoRetargeting, and enforce_BIP94 are fixed to false as on mainnet. Only Std is imported.
import Std
namespace BitcoinPow
/-! Transcription of the mainnet proof-of-work arithmetic of Bitcoin Core at revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`: `arith_uint256::SetCompact` / `GetCompact`
(`arith_uint256.cpp`), and `DeriveTarget`, `CheckProofOfWorkImpl`, `CalculateNextWorkRequired`,
`PermittedDifficultyTransition`, `GetNextWorkRequired` (`pow.cpp`), with `CMainParams`
(`kernel/chainparams.cpp`): `fPowAllowMinDifficultyBlocks = false`, `fPowNoRetargeting = false`,
`enforce_BIP94 = false`.
An `arith_uint256` is modelled by its value, a natural number below `2 ^ 256`. Its left shift and
its multiplications discard carries out of the top word, i.e. they reduce modulo `2 ^ 256`; its
division is exact integer division. -/
/-- `2 ^ 256`, the modulus of `arith_uint256` arithmetic. -/
def width : Nat := 2 ^ 256
/-- `consensus.powLimit = uint256{"00000000ffff…ff"}`: `2 ^ 224 - 1`. -/
def powLimit : Nat := 2 ^ 224 - 1
/-- `consensus.nPowTargetTimespan = 14 * 24 * 60 * 60`. -/
def targetTimespan : Nat := 14 * 24 * 60 * 60
/-- `consensus.nPowTargetSpacing = 10 * 60`. -/
def targetSpacing : Nat := 10 * 60
/-- `Consensus::Params::DifficultyAdjustmentInterval() = nPowTargetTimespan / nPowTargetSpacing`. -/
def difficultyAdjustmentInterval : Nat := targetTimespan / targetSpacing
/-- `int nSize = nCompact >> 24`. -/
def compactSize (c : BitVec 32) : Nat := (c >>> 24).toNat
/-- `uint32_t nWord = nCompact & 0x007fffff`. -/
def compactWord (c : BitVec 32) : Nat := (c &&& 0x007fffff).toNat
/-- The value produced by `SetCompact`: the mantissa shifted right by `8 * (3 - nSize)` bytes when
`nSize <= 3`, otherwise shifted left by `8 * (nSize - 3)` bytes inside 256 bits. -/
def setCompact (c : BitVec 32) : Nat :=
let nSize := compactSize c
let nWord := compactWord c
if nSize ≤ 3 then nWord >>> (8 * (3 - nSize)) else (nWord <<< (8 * (nSize - 3))) % width
/-- `*pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0`. -/
def compactNegative (c : BitVec 32) : Bool :=
compactWord c != 0 && (c &&& 0x00800000) != 0
/-- `*pfOverflow = nWord != 0 && ((nSize > 34) || (nWord > 0xff && nSize > 33) || (nWord > 0xffff && nSize > 32))`. -/
def compactOverflow (c : BitVec 32) : Bool :=
let nSize := compactSize c
let nWord := compactWord c
nWord != 0 && (decide (34 < nSize) || (decide (0xff < nWord) && decide (33 < nSize)) ||
(decide (0xffff < nWord) && decide (32 < nSize)))
/-- The exact mathematical value `mantissa * 256 ^ (nSize - 3)` encoded by a compact word, with no
256-bit truncation (and floor division for `nSize <= 3`). -/
def specTarget (c : BitVec 32) : Nat :=
let nSize := compactSize c
let nWord := compactWord c
if nSize ≤ 3 then nWord / 256 ^ (3 - nSize) else nWord * 256 ^ (nSize - 3)
/-- `base_uint::bits()`: the bit length, `0` for `0`. -/
def bitLength (v : Nat) : Nat := if v = 0 then 0 else Nat.log2 v + 1
/-- `GetCompact(fNegative = false)` on a value below `2 ^ 256`. `GetLow64()` is the value modulo
`2 ^ 64`; the assignment to the `uint32_t nCompact` reduces modulo `2 ^ 32`; when bit `0x00800000`
of the mantissa is set, the mantissa is divided by 256 and the exponent incremented. -/
def getCompact (v : Nat) : BitVec 32 :=
let nSize := (bitLength v + 7) / 8
let nCompact :=
if nSize ≤ 3 then ((v % 2 ^ 64) <<< (8 * (3 - nSize))) % 2 ^ 32
else ((v >>> (8 * (nSize - 3))) % 2 ^ 64) % 2 ^ 32
let adjust := nCompact &&& 0x00800000 != 0
let nCompact' := if adjust then nCompact >>> 8 else nCompact
let nSize' := if adjust then nSize + 1 else nSize
BitVec.ofNat 32 (nCompact' ||| (nSize' <<< 24))
/-- `DeriveTarget`: the target, unless negative, zero, overflowing, or above `powLimit`. -/
def deriveTarget (nBits : BitVec 32) : Option Nat :=
let t := setCompact nBits
if compactNegative nBits || decide (t = 0) || compactOverflow nBits || decide (powLimit < t) then none
else some t
/-- `CheckProofOfWorkImpl`: the header hash, read as a 256-bit number, is at most the derived target. -/
def checkProofOfWork (hash : Nat) (nBits : BitVec 32) : Bool :=
match deriveTarget nBits with
| none => false
| some t => decide (hash ≤ t)
/-- The timespan clamp of `CalculateNextWorkRequired`: `nActualTimespan` (a signed difference of
block times) is raised to `nPowTargetTimespan / 4` and lowered to `nPowTargetTimespan * 4`. -/
def clampTimespan (actual : Int) : Int :=
let lo : Int := (targetTimespan / 4 : Nat)
let hi : Int := (targetTimespan * 4 : Nat)
if actual < lo then lo else if hi < actual then hi else actual
/-- `CalculateNextWorkRequired(pindexLast, nFirstBlockTime)` at mainnet parameters: decode the last
target, multiply by the clamped timespan (modulo `2 ^ 256`), divide by the target timespan, cap at
`powLimit`, and re-encode. -/
def calculateNextWork (lastBits : BitVec 32) (lastTime firstTime : Int) : BitVec 32 :=
let ts := (clampTimespan (lastTime - firstTime)).toNat
let bn := (setCompact lastBits * ts) % width
let bn := bn / targetTimespan
let bn := if powLimit < bn then powLimit else bn
getCompact bn
/-- `PermittedDifficultyTransition(params, height, old_nbits, new_nbits)` at mainnet parameters. -/
def permittedTransition (height : Nat) (oldBits newBits : BitVec 32) : Bool :=
if height % difficultyAdjustmentInterval = 0 then
let observed := setCompact newBits
let largest := (setCompact oldBits * (targetTimespan * 4)) % width / targetTimespan
let largest := if powLimit < largest then powLimit else largest
let maximum := setCompact (getCompact largest)
let smallest := (setCompact oldBits * (targetTimespan / 4)) % width / targetTimespan
let smallest := if powLimit < smallest then powLimit else smallest
let minimum := setCompact (getCompact smallest)
!(decide (maximum < observed)) && !(decide (minimum > observed))
else
decide (oldBits = newBits)
/-- `GetNextWorkRequired` at mainnet parameters, with the first block time of the period supplied
by the caller. -/
def nextWorkRequired (lastHeight : Nat) (lastBits : BitVec 32) (lastTime firstTime : Int) : BitVec 32 :=
if (lastHeight + 1) % difficultyAdjustmentInterval ≠ 0 then lastBits
else calculateNextWork lastBits lastTime firstTime
end BitcoinPow
Read-back
What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Throughout, a "32-bit word" is a bit-vector of length 32, which we identify with the integer with that it encodes. All other quantities are natural numbers unless stated to be integers. "" is natural-number (floor) division, "" the remainder, and natural-number subtraction truncates at (it is whenever ).
width. The constant is the natural number .
powLimit. The constant is the natural number (a genuine subtraction; so no truncation occurs).
targetTimespan. The constant is the natural number .
targetSpacing. The constant is the natural number .
difficultyAdjustmentInterval. The constant is the natural number (the division is exact).
compactSize. For a 32-bit word , is the natural number obtained by shifting right by 24 bit positions (as a logical shift inside 32 bits) and reading the result as a number; equivalently it is the top byte of ,
Below we abbreviate it or simply .
compactWord. For a 32-bit word , is the natural number obtained by bitwise-ANDing with the mask and reading the result as a number; equivalently it is the low 23 bits of ,
Below we abbreviate it or simply . Note that bit 23 of (the bit of value ) is excluded from ; bits 24–31 form .
setCompact. For a 32-bit word with and as above, is the natural number
In the first branch is an ordinary (non-truncating) subtraction since ; a right shift of a natural number is floor division by the corresponding power of two, so when this is (because ), when it is , when it is , and when it is . In the second branch the left shift is multiplication by on unbounded natural numbers followed by reduction modulo ; since this reduction is the identity when , i.e. , while for it keeps only , for only , and for the result is . The value is always . Below we abbreviate as .
compactNegative. For a 32-bit word , is the Boolean value (true/false, not a proposition)
i.e. true exactly when the low 23 bits of are not all zero and bit 23 of (the bit of value ) is set. In particular it is false whenever , regardless of bit 23. Below we abbreviate it .
compactOverflow. For a 32-bit word with and , is the Boolean value
all comparisons strict as written (, , , , ). It is false whenever , whenever , and also when and , or and . Below we abbreviate it .
specTarget. For a 32-bit word with and , is the natural number
with no reduction modulo in the second branch (so it can be as large as ). The first branch coincides literally with the first branch of (floor division by equals a right shift by bits). Below we abbreviate it .
bitLength. For a natural number , is the natural number
where is the natural-number base-2 logarithm (the largest with ). The case is handled explicitly, so the convention for the logarithm of is never used. For this is the number of binary digits of , i.e. the unique with . Below we abbreviate it .
getCompact. For a natural number (any natural number; no upper bound is imposed by the definition), is the 32-bit word computed as follows. Let
(the number of bytes needed to write ; when ). Let
where in the first branch is a non-truncating subtraction (as ). Let be the Boolean "bit 23 of is set", i.e. as natural numbers. Let if holds and otherwise, and let if holds and otherwise. The result is the 32-bit word
where OR is bitwise-or of natural numbers, is a left shift on unbounded natural numbers, and the final reduction modulo is the conversion of that natural number to a 32-bit word. Facts about the ranges implied by the definition: since in both branches, , so the reductions modulo and in the definition of never change the value; consequently , the OR with touches disjoint bits, and the final reduction modulo is the identity unless (which requires ). For one has and . For : , , is false, and the result is the word . Below we abbreviate as .
deriveTarget. For a 32-bit word , is an optional natural number: with , it is "none" (no value) if
and otherwise it is "some ". Note the test on uses (with its modulo- reduction), not , and the cap test is the strict inequality (so is accepted).
checkProofOfWork. For a natural number (any natural number; it is not required to be below ) and a 32-bit word , is the Boolean value which is false if is "none", and is (non-strict) if is "some ". Unfolded: it is true exactly when , , , , and .
clampTimespan. For an integer (possibly negative), is the integer
where and , both computed as natural numbers and then cast to integers. The first test is checked first, so for every integer the result satisfies ; in particular it is always strictly positive.
calculateNextWork. For a 32-bit word and integers and (both arbitrary integers), is the 32-bit word computed as follows. Let be the natural number obtained from the integer by the "to-natural" conversion (which sends negative integers to ); since the clamp is always , exactly and . Let
The result is . No condition is placed on : is used even if or is true or (in which case and the result is the word ). The product is reduced modulo before the division.
permittedTransition. For a natural number and 32-bit words , is a Boolean value. If (this includes ), define
(here and ; in each case the product is reduced modulo first and then divided), and the result is
If , the result is , equality of the two 32-bit words bit for bit (not equality of the values and ). No validity condition (negativity, overflow, zero, cap) is checked on either word in either branch; both branches use , never , and the negative bit (bit 23) of is ignored by .
nextWorkRequired. For a natural number , a 32-bit word , and integers , is the 32-bit word
The second branch applies when . The word is returned unchanged in the first branch, whatever its negative/overflow bits are; are unused there.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.