Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Compact targets, proof of work, and difficulty retargeting at mainnet parameters

Definition
BitcoinPow

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

bitcoinbitcoin-mainnetconsensusdifficultyformal-verificationproof-of-work

This file transcribes the mainnet proof-of-work arithmetic of Bitcoin Core. An arith_uint256 is modelled by its value, a natural number below 22562^{256}2256 (width); its left shift and its multiplications discard carries out of the top word, so they reduce modulo 22562^{256}2256, and its division is exact integer division.

Parameters. powLimit=2224−1\mathrm{powLimit} = 2^{224} - 1powLimit=2224−1, the target timespan T=14⋅24⋅60⋅60=1,209,600T = 14 \cdot 24 \cdot 60 \cdot 60 = 1{,}209{,}600T=14⋅24⋅60⋅60=1,209,600 seconds, the target spacing 600600600 seconds, and the difficulty adjustment interval T/600=2016T / 600 = 2016T/600=2016 blocks.

Compact words. For a 32-bit word ccc: the size S=⌊c/224⌋S = \lfloor c / 2^{24} \rfloorS=⌊c/224⌋ and the mantissa W=c&0x007fffffW = c \mathbin{\&} \mathtt{0x007fffff}W=c&0x007fffff. SetCompact yields ⌊W/28(3−S)⌋\lfloor W / 2^{8(3-S)} \rfloor⌊W/28(3−S)⌋ when S≤3S \le 3S≤3 and (W⋅28(S−3)) mod 2256(W \cdot 2^{8(S-3)}) \bmod 2^{256}(W⋅28(S−3))mod2256 otherwise. The word is negative when W≠0W \ne 0W=0 and c&0x00800000≠0c \mathbin{\&} \mathtt{0x00800000} \ne 0c&0x00800000=0; it overflows when W≠0W \ne 0W=0 and (S>34S > 34S>34, or W>0xffW > \mathtt{0xff}W>0xff and S>33S > 33S>33, or W>0xffffW > \mathtt{0xffff}W>0xffff and S>32S > 32S>32). The exact value specTarget(c)\mathrm{specTarget}(c)specTarget(c) is the same formula without the reduction modulo 22562^{256}2256.

Encoding. bitLength is 000 at 000 and ⌊log⁡2v⌋+1\lfloor \log_2 v \rfloor + 1⌊log2​v⌋+1 otherwise. GetCompact of vvv sets S=⌊(bitLength(v)+7)/8⌋S = \lfloor (\mathrm{bitLength}(v) + 7) / 8 \rfloorS=⌊(bitLength(v)+7)/8⌋, forms the mantissa as ((v mod 264)⋅28(3−S)) mod 232((v \bmod 2^{64}) \cdot 2^{8(3-S)}) \bmod 2^{32}((vmod264)⋅28(3−S))mod232 when S≤3S \le 3S≤3 and as ((⌊v/28(S−3)⌋ mod 264) mod 232)((\lfloor v / 2^{8(S-3)} \rfloor \bmod 2^{64}) \bmod 2^{32})((⌊v/28(S−3)⌋mod264)mod232) otherwise; if bit 23 of the mantissa is set it divides the mantissa by 256256256 and increments SSS; the result is the 32-bit word mantissa ∨(S⋅224)\lor (S \cdot 2^{24})∨(S⋅224).

Validation. deriveTarget returns the decoded value unless the word is negative, decodes to 000, overflows, or exceeds powLimit\mathrm{powLimit}powLimit. checkProofOfWork(hash, word) holds when a target is derived and hash≤\mathrm{hash} \lehash≤ target. clampTimespan raises a signed timespan to T/4T/4T/4 and lowers it to 4T4T4T. calculateNextWork(last word, last time, first time) decodes the last word, multiplies by the clamped elapsed time modulo 22562^{256}2256, divides by TTT, caps at powLimit\mathrm{powLimit}powLimit, and re-encodes. permittedTransition(height, old, new) at a height divisible by 201620162016 requires the decoded new word to lie between the re-encoded caps of old ⋅(T/4)/T\cdot (T/4) / T⋅(T/4)/T and old ⋅4T/T\cdot 4T / T⋅4T/T (products modulo 22562^{256}2256); at other heights it requires old === new. nextWorkRequired returns the last word unless the next height is divisible by 201620162016, 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.

Definition code
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
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: GetNextWorkRequired (lines 14-48), CalculateNextWorkRequired (50-85), PermittedDifficultyTransition (89-136), DeriveTarget (146-159), CheckProofOfWorkImpl (161-171), src/pow.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/pow.cpp; arith_uint256::SetCompact (176-194), GetCompact (196-216), base_uint::operator<<= (15-30), operator*=(uint32_t) (49-59), operator/= (77-104), bits() (205-218), src/arith_uint256.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/arith_uint256.cpp; CMainParams powLimit, nPowTargetTimespan, nPowTargetSpacing, fPowAllowMinDifficultyBlocks, fPowNoRetargeting, enforce_BIP94, src/kernel/chainparams.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/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)

Throughout, a "32-bit word" is a bit-vector of length 32, which we identify with the integer ccc with 0≤c<2320 \le c < 2^{32}0≤c<232 that it encodes. All other quantities are natural numbers {0,1,2,… }\{0,1,2,\dots\}{0,1,2,…} unless stated to be integers. "⌊x/y⌋\lfloor x/y \rfloor⌊x/y⌋" is natural-number (floor) division, "x mod yx \bmod yxmody" the remainder, and natural-number subtraction x−yx - yx−y truncates at 000 (it is 000 whenever y≥xy \ge xy≥x).

width. The constant width\mathrm{width}width is the natural number 22562^{256}2256.

powLimit. The constant powLimit\mathrm{powLimit}powLimit is the natural number 2224−12^{224} - 12224−1 (a genuine subtraction; 2224≥12^{224} \ge 12224≥1 so no truncation occurs).

targetTimespan. The constant targetTimespan\mathrm{targetTimespan}targetTimespan is the natural number 14⋅24⋅60⋅60=120960014 \cdot 24 \cdot 60 \cdot 60 = 120960014⋅24⋅60⋅60=1209600.

targetSpacing. The constant targetSpacing\mathrm{targetSpacing}targetSpacing is the natural number 10⋅60=60010 \cdot 60 = 60010⋅60=600.

difficultyAdjustmentInterval. The constant difficultyAdjustmentInterval\mathrm{difficultyAdjustmentInterval}difficultyAdjustmentInterval is the natural number ⌊1209600/600⌋=2016\lfloor 1209600 / 600 \rfloor = 2016⌊1209600/600⌋=2016 (the division is exact).

compactSize. For a 32-bit word ccc, compactSize(c)\mathrm{compactSize}(c)compactSize(c) is the natural number obtained by shifting ccc 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 ccc,

compactSize(c)=⌊c/224⌋,0≤compactSize(c)≤255.\mathrm{compactSize}(c) = \lfloor c / 2^{24} \rfloor, \qquad 0 \le \mathrm{compactSize}(c) \le 255 .compactSize(c)=⌊c/224⌋,0≤compactSize(c)≤255.

Below we abbreviate it s(c)s(c)s(c) or simply sss.

compactWord. For a 32-bit word ccc, compactWord(c)\mathrm{compactWord}(c)compactWord(c) is the natural number obtained by bitwise-ANDing ccc with the mask 0x007fffff=223−1\mathtt{0x007fffff} = 2^{23}-10x007fffff=223−1 and reading the result as a number; equivalently it is the low 23 bits of ccc,

compactWord(c)=c mod 223,0≤compactWord(c)≤223−1=8388607.\mathrm{compactWord}(c) = c \bmod 2^{23}, \qquad 0 \le \mathrm{compactWord}(c) \le 2^{23}-1 = 8388607 .compactWord(c)=cmod223,0≤compactWord(c)≤223−1=8388607.

Below we abbreviate it m(c)m(c)m(c) or simply mmm. Note that bit 23 of ccc (the bit of value 223=0x008000002^{23} = \mathtt{0x00800000}223=0x00800000) is excluded from mmm; bits 24–31 form sss.

setCompact. For a 32-bit word ccc with s=s(c)s = s(c)s=s(c) and m=m(c)m = m(c)m=m(c) as above, setCompact(c)\mathrm{setCompact}(c)setCompact(c) is the natural number

setCompact(c)={⌊m/28(3−s)⌋=⌊m/256 3−s⌋if s≤3,(m⋅28(s−3)) mod 2256=(m⋅256 s−3) mod 2256if s>3.\mathrm{setCompact}(c) = \begin{cases} \big\lfloor m / 2^{8(3-s)} \big\rfloor = \lfloor m / 256^{\,3-s} \rfloor & \text{if } s \le 3, \\[2pt] \big( m \cdot 2^{8(s-3)} \big) \bmod 2^{256} = (m \cdot 256^{\,s-3}) \bmod 2^{256} & \text{if } s > 3. \end{cases}setCompact(c)={⌊m/28(3−s)⌋=⌊m/2563−s⌋(m⋅28(s−3))mod2256=(m⋅256s−3)mod2256​if s≤3,if s>3.​

In the first branch 3−s3 - s3−s is an ordinary (non-truncating) subtraction since s≤3s \le 3s≤3; a right shift of a natural number is floor division by the corresponding power of two, so when s=0s = 0s=0 this is ⌊m/224⌋=0\lfloor m/2^{24} \rfloor = 0⌊m/224⌋=0 (because m<223m < 2^{23}m<223), when s=1s=1s=1 it is ⌊m/65536⌋\lfloor m/65536 \rfloor⌊m/65536⌋, when s=2s=2s=2 it is ⌊m/256⌋\lfloor m/256 \rfloor⌊m/256⌋, and when s=3s=3s=3 it is mmm. In the second branch the left shift is multiplication by 28(s−3)2^{8(s-3)}28(s−3) on unbounded natural numbers followed by reduction modulo 22562^{256}2256; since m<223m < 2^{23}m<223 this reduction is the identity when 8(s−3)+23≤2568(s-3) + 23 \le 2568(s−3)+23≤256, i.e. s≤32s \le 32s≤32, while for s=33s = 33s=33 it keeps only (m mod 216)⋅2240(m \bmod 2^{16}) \cdot 2^{240}(mmod216)⋅2240, for s=34s = 34s=34 only (m mod 28)⋅2248(m \bmod 2^{8}) \cdot 2^{248}(mmod28)⋅2248, and for s≥35s \ge 35s≥35 the result is 000. The value is always <2256< 2^{256}<2256. Below we abbreviate setCompact(c)\mathrm{setCompact}(c)setCompact(c) as S(c)S(c)S(c).

compactNegative. For a 32-bit word ccc, compactNegative(c)\mathrm{compactNegative}(c)compactNegative(c) is the Boolean value (true/false, not a proposition)

compactNegative(c)=[ m(c)≠0 ] ∧ [ (c AND 0x00800000)≠0 ],\mathrm{compactNegative}(c) = \big[\, m(c) \ne 0 \,\big] \ \wedge\ \big[\, (c \text{ AND } \mathtt{0x00800000}) \ne 0 \,\big],compactNegative(c)=[m(c)=0] ∧ [(c AND 0x00800000)=0],

i.e. true exactly when the low 23 bits of ccc are not all zero and bit 23 of ccc (the bit of value 2232^{23}223) is set. In particular it is false whenever m(c)=0m(c) = 0m(c)=0, regardless of bit 23. Below we abbreviate it N(c)N(c)N(c).

compactOverflow. For a 32-bit word ccc with s=s(c)s = s(c)s=s(c) and m=m(c)m = m(c)m=m(c), compactOverflow(c)\mathrm{compactOverflow}(c)compactOverflow(c) is the Boolean value

compactOverflow(c)=[m≠0] ∧ ([s>34] ∨ ([m>255]∧[s>33]) ∨ ([m>65535]∧[s>32])),\mathrm{compactOverflow}(c) = [m \ne 0] \ \wedge\ \Big( [s > 34] \ \vee\ \big([m > 255] \wedge [s > 33]\big) \ \vee\ \big([m > 65535] \wedge [s > 32]\big) \Big),compactOverflow(c)=[m=0] ∧ ([s>34] ∨ ([m>255]∧[s>33]) ∨ ([m>65535]∧[s>32])),

all comparisons strict as written (34<s34 < s34<s, 255<m255 < m255<m, 33<s33 < s33<s, 65535<m65535 < m65535<m, 32<s32 < s32<s). It is false whenever m=0m = 0m=0, whenever s≤32s \le 32s≤32, and also when s=33s = 33s=33 and m≤65535m \le 65535m≤65535, or s=34s = 34s=34 and m≤255m \le 255m≤255. Below we abbreviate it O(c)O(c)O(c).

specTarget. For a 32-bit word ccc with s=s(c)s = s(c)s=s(c) and m=m(c)m = m(c)m=m(c), specTarget(c)\mathrm{specTarget}(c)specTarget(c) is the natural number

specTarget(c)={⌊m/256 3−s⌋if s≤3,m⋅256 s−3if s>3,\mathrm{specTarget}(c) = \begin{cases} \lfloor m / 256^{\,3-s} \rfloor & \text{if } s \le 3, \\[2pt] m \cdot 256^{\,s-3} & \text{if } s > 3, \end{cases}specTarget(c)={⌊m/2563−s⌋m⋅256s−3​if s≤3,if s>3,​

with no reduction modulo 22562^{256}2256 in the second branch (so it can be as large as (223−1)⋅256252(2^{23}-1)\cdot 256^{252}(223−1)⋅256252). The first branch coincides literally with the first branch of setCompact\mathrm{setCompact}setCompact (floor division by 2563−s256^{3-s}2563−s equals a right shift by 8(3−s)8(3-s)8(3−s) bits). Below we abbreviate it T(c)T(c)T(c).

bitLength. For a natural number vvv, bitLength(v)\mathrm{bitLength}(v)bitLength(v) is the natural number

bitLength(v)={0if v=0,⌊log⁡2v⌋+1if v≠0,\mathrm{bitLength}(v) = \begin{cases} 0 & \text{if } v = 0, \\ \lfloor \log_2 v \rfloor + 1 & \text{if } v \ne 0, \end{cases}bitLength(v)={0⌊log2​v⌋+1​if v=0,if v=0,​

where ⌊log⁡2v⌋\lfloor \log_2 v\rfloor⌊log2​v⌋ is the natural-number base-2 logarithm (the largest kkk with 2k≤v2^k \le v2k≤v). The case v=0v = 0v=0 is handled explicitly, so the convention for the logarithm of 000 is never used. For v≠0v \ne 0v=0 this is the number of binary digits of vvv, i.e. the unique β\betaβ with 2β−1≤v<2β2^{\beta-1} \le v < 2^{\beta}2β−1≤v<2β. Below we abbreviate it β(v)\beta(v)β(v).

getCompact. For a natural number vvv (any natural number; no upper bound is imposed by the definition), getCompact(v)\mathrm{getCompact}(v)getCompact(v) is the 32-bit word computed as follows. Let

n=⌊β(v)+78⌋n = \Big\lfloor \frac{\beta(v) + 7}{8} \Big\rfloorn=⌊8β(v)+7​⌋

(the number of bytes needed to write vvv; n=0n = 0n=0 when v=0v = 0v=0). Let

k={((v mod 264)⋅28(3−n)) mod 232if n≤3,(⌊v/28(n−3)⌋ mod 264) mod 232if n>3,k = \begin{cases} \big( (v \bmod 2^{64}) \cdot 2^{8(3-n)} \big) \bmod 2^{32} & \text{if } n \le 3, \\[2pt] \big( \lfloor v / 2^{8(n-3)} \rfloor \bmod 2^{64} \big) \bmod 2^{32} & \text{if } n > 3, \end{cases}k={((vmod264)⋅28(3−n))mod232(⌊v/28(n−3)⌋mod264)mod232​if n≤3,if n>3,​

where in the first branch 3−n3-n3−n is a non-truncating subtraction (as n≤3n \le 3n≤3). Let aaa be the Boolean "bit 23 of kkk is set", i.e. (k AND 223)≠0(k \text{ AND } 2^{23}) \ne 0(k AND 223)=0 as natural numbers. Let k′=⌊k/28⌋k' = \lfloor k / 2^{8} \rfloork′=⌊k/28⌋ if aaa holds and k′=kk' = kk′=k otherwise, and let n′=n+1n' = n + 1n′=n+1 if aaa holds and n′=nn' = nn′=n otherwise. The result is the 32-bit word

getCompact(v)=(k′ OR (n′⋅224)) mod 232,\mathrm{getCompact}(v) = \big( k' \ \text{OR}\ (n' \cdot 2^{24}) \big) \bmod 2^{32},getCompact(v)=(k′ OR (n′⋅224))mod232,

where OR is bitwise-or of natural numbers, n′⋅224n' \cdot 2^{24}n′⋅224 is a left shift on unbounded natural numbers, and the final reduction modulo 2322^{32}232 is the conversion of that natural number to a 32-bit word. Facts about the ranges implied by the definition: since v<28nv < 2^{8n}v<28n in both branches, k<224k < 2^{24}k<224, so the reductions modulo 2642^{64}264 and 2322^{32}232 in the definition of kkk never change the value; consequently k′<224k' < 2^{24}k′<224, the OR with n′⋅224n' \cdot 2^{24}n′⋅224 touches disjoint bits, and the final reduction modulo 2322^{32}232 is the identity unless n′≥256n' \ge 256n′≥256 (which requires v≥22032v \ge 2^{2032}v≥22032). For v<2256v < 2^{256}v<2256 one has n≤32n \le 32n≤32 and n′≤33n' \le 33n′≤33. For v=0v = 0v=0: n=0n = 0n=0, k=0k = 0k=0, aaa is false, and the result is the word 000. Below we abbreviate getCompact(v)\mathrm{getCompact}(v)getCompact(v) as G(v)G(v)G(v).

deriveTarget. For a 32-bit word ccc, deriveTarget(c)\mathrm{deriveTarget}(c)deriveTarget(c) is an optional natural number: with t=S(c)=setCompact(c)t = S(c) = \mathrm{setCompact}(c)t=S(c)=setCompact(c), it is "none" (no value) if

N(c)=true  ∨  t=0  ∨  O(c)=true  ∨  2224−1<t,N(c) = \text{true} \ \ \vee\ \ t = 0 \ \ \vee\ \ O(c) = \text{true} \ \ \vee\ \ 2^{224}-1 < t,N(c)=true  ∨  t=0  ∨  O(c)=true  ∨  2224−1<t,

and otherwise it is "some ttt". Note the test on ttt uses setCompact\mathrm{setCompact}setCompact (with its modulo-22562^{256}2256 reduction), not specTarget\mathrm{specTarget}specTarget, and the cap test is the strict inequality powLimit<t\mathrm{powLimit} < tpowLimit<t (so t=2224−1t = 2^{224}-1t=2224−1 is accepted).

checkProofOfWork. For a natural number hash\mathrm{hash}hash (any natural number; it is not required to be below 22562^{256}2256) and a 32-bit word ccc, checkProofOfWork(hash,c)\mathrm{checkProofOfWork}(\mathrm{hash}, c)checkProofOfWork(hash,c) is the Boolean value which is false if deriveTarget(c)\mathrm{deriveTarget}(c)deriveTarget(c) is "none", and is [hash≤t][\mathrm{hash} \le t][hash≤t] (non-strict) if deriveTarget(c)\mathrm{deriveTarget}(c)deriveTarget(c) is "some ttt". Unfolded: it is true exactly when N(c)=falseN(c) = \text{false}N(c)=false, O(c)=falseO(c) = \text{false}O(c)=false, S(c)≠0S(c) \ne 0S(c)=0, S(c)≤2224−1S(c) \le 2^{224}-1S(c)≤2224−1, and hash≤S(c)\mathrm{hash} \le S(c)hash≤S(c).

clampTimespan. For an integer xxx (possibly negative), clampTimespan(x)\mathrm{clampTimespan}(x)clampTimespan(x) is the integer

clampTimespan(x)={302400if x<302400,4838400if 4838400<x,xotherwise,\mathrm{clampTimespan}(x) = \begin{cases} 302400 & \text{if } x < 302400, \\ 4838400 & \text{if } 4838400 < x, \\ x & \text{otherwise,} \end{cases}clampTimespan(x)=⎩⎨⎧​3024004838400x​if x<302400,if 4838400<x,otherwise,​

where 302400=⌊1209600/4⌋302400 = \lfloor 1209600/4 \rfloor302400=⌊1209600/4⌋ and 4838400=1209600⋅44838400 = 1209600 \cdot 44838400=1209600⋅4, both computed as natural numbers and then cast to integers. The first test is checked first, so for every integer xxx the result satisfies 302400≤clampTimespan(x)≤4838400302400 \le \mathrm{clampTimespan}(x) \le 4838400302400≤clampTimespan(x)≤4838400; in particular it is always strictly positive.

calculateNextWork. For a 32-bit word ccc and integers tℓt_\elltℓ​ and tft_ftf​ (both arbitrary integers), calculateNextWork(c,tℓ,tf)\mathrm{calculateNextWork}(c, t_\ell, t_f)calculateNextWork(c,tℓ​,tf​) is the 32-bit word computed as follows. Let τ\tauτ be the natural number obtained from the integer clampTimespan(tℓ−tf)\mathrm{clampTimespan}(t_\ell - t_f)clampTimespan(tℓ​−tf​) by the "to-natural" conversion (which sends negative integers to 000); since the clamp is always ≥302400\ge 302400≥302400, τ=clampTimespan(tℓ−tf)\tau = \mathrm{clampTimespan}(t_\ell - t_f)τ=clampTimespan(tℓ​−tf​) exactly and 302400≤τ≤4838400302400 \le \tau \le 4838400302400≤τ≤4838400. Let

b1=(S(c)⋅τ) mod 2256,b2=⌊b1/1209600⌋,b3={2224−1if 2224−1<b2,b2otherwise.b_1 = \big( S(c) \cdot \tau \big) \bmod 2^{256}, \qquad b_2 = \lfloor b_1 / 1209600 \rfloor, \qquad b_3 = \begin{cases} 2^{224}-1 & \text{if } 2^{224}-1 < b_2, \\ b_2 & \text{otherwise.} \end{cases}b1​=(S(c)⋅τ)mod2256,b2​=⌊b1​/1209600⌋,b3​={2224−1b2​​if 2224−1<b2​,otherwise.​

The result is G(b3)=getCompact(b3)G(b_3) = \mathrm{getCompact}(b_3)G(b3​)=getCompact(b3​). No condition is placed on ccc: S(c)S(c)S(c) is used even if N(c)N(c)N(c) or O(c)O(c)O(c) is true or S(c)=0S(c) = 0S(c)=0 (in which case b1=b2=b3=0b_1 = b_2 = b_3 = 0b1​=b2​=b3​=0 and the result is the word 000). The product S(c)⋅τS(c)\cdot\tauS(c)⋅τ is reduced modulo 22562^{256}2256 before the division.

permittedTransition. For a natural number hhh and 32-bit words cold,cnewc_{\mathrm{old}}, c_{\mathrm{new}}cold​,cnew​, permittedTransition(h,cold,cnew)\mathrm{permittedTransition}(h, c_{\mathrm{old}}, c_{\mathrm{new}})permittedTransition(h,cold​,cnew​) is a Boolean value. If h mod 2016=0h \bmod 2016 = 0hmod2016=0 (this includes h=0h = 0h=0), define

observed=S(cnew),\mathrm{observed} = S(c_{\mathrm{new}}),observed=S(cnew​), L0=⌊(S(cold)⋅4838400) mod 22561209600⌋,L={2224−1if 2224−1<L0L0otherwise,maximum=S(G(L)),L_0 = \Big\lfloor \frac{\big( S(c_{\mathrm{old}}) \cdot 4838400 \big) \bmod 2^{256}}{1209600} \Big\rfloor, \qquad L = \begin{cases} 2^{224}-1 & \text{if } 2^{224}-1 < L_0 \\ L_0 & \text{otherwise} \end{cases}, \qquad \mathrm{maximum} = S(G(L)),L0​=⌊1209600(S(cold​)⋅4838400)mod2256​⌋,L={2224−1L0​​if 2224−1<L0​otherwise​,maximum=S(G(L)), ℓ0=⌊(S(cold)⋅302400) mod 22561209600⌋,ℓ={2224−1if 2224−1<ℓ0ℓ0otherwise,minimum=S(G(ℓ)),\ell_0 = \Big\lfloor \frac{\big( S(c_{\mathrm{old}}) \cdot 302400 \big) \bmod 2^{256}}{1209600} \Big\rfloor, \qquad \ell = \begin{cases} 2^{224}-1 & \text{if } 2^{224}-1 < \ell_0 \\ \ell_0 & \text{otherwise} \end{cases}, \qquad \mathrm{minimum} = S(G(\ell)),ℓ0​=⌊1209600(S(cold​)⋅302400)mod2256​⌋,ℓ={2224−1ℓ0​​if 2224−1<ℓ0​otherwise​,minimum=S(G(ℓ)),

(here 4838400=1209600⋅44838400 = 1209600 \cdot 44838400=1209600⋅4 and 302400=⌊1209600/4⌋302400 = \lfloor 1209600/4 \rfloor302400=⌊1209600/4⌋; in each case the product is reduced modulo 22562^{256}2256 first and then divided), and the result is

¬[maximum<observed] ∧ ¬[minimum>observed],i.e.minimum≤observed≤maximum.\neg[\mathrm{maximum} < \mathrm{observed}] \ \wedge\ \neg[\mathrm{minimum} > \mathrm{observed}], \quad \text{i.e.} \quad \mathrm{minimum} \le \mathrm{observed} \le \mathrm{maximum}.¬[maximum<observed] ∧ ¬[minimum>observed],i.e.minimum≤observed≤maximum.

If h mod 2016≠0h \bmod 2016 \ne 0hmod2016=0, the result is [cold=cnew][c_{\mathrm{old}} = c_{\mathrm{new}}][cold​=cnew​], equality of the two 32-bit words bit for bit (not equality of the values S(cold)S(c_{\mathrm{old}})S(cold​) and S(cnew)S(c_{\mathrm{new}})S(cnew​)). No validity condition (negativity, overflow, zero, cap) is checked on either word in either branch; both branches use setCompact\mathrm{setCompact}setCompact, never specTarget\mathrm{specTarget}specTarget, and the negative bit (bit 23) of cnewc_{\mathrm{new}}cnew​ is ignored by SSS.

nextWorkRequired. For a natural number hℓh_\ellhℓ​, a 32-bit word ccc, and integers tℓ,tft_\ell, t_ftℓ​,tf​, nextWorkRequired(hℓ,c,tℓ,tf)\mathrm{nextWorkRequired}(h_\ell, c, t_\ell, t_f)nextWorkRequired(hℓ​,c,tℓ​,tf​) is the 32-bit word

nextWorkRequired(hℓ,c,tℓ,tf)={cif (hℓ+1) mod 2016≠0,calculateNextWork(c,tℓ,tf)if (hℓ+1) mod 2016=0.\mathrm{nextWorkRequired}(h_\ell, c, t_\ell, t_f) = \begin{cases} c & \text{if } (h_\ell + 1) \bmod 2016 \ne 0, \\ \mathrm{calculateNextWork}(c, t_\ell, t_f) & \text{if } (h_\ell + 1) \bmod 2016 = 0. \end{cases}nextWorkRequired(hℓ​,c,tℓ​,tf​)={ccalculateNextWork(c,tℓ​,tf​)​if (hℓ​+1)mod2016=0,if (hℓ​+1)mod2016=0.​

The second branch applies when hℓ∈{2015,4031,6047,… }h_\ell \in \{2015, 4031, 6047, \dots\}hℓ​∈{2015,4031,6047,…}. The word ccc is returned unchanged in the first branch, whatever its negative/overflow bits are; tℓ,tft_\ell, t_ftℓ​,tf​ are unused there.

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