Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The raw next target of a retarget period and the target after a sequence of periods

Definition
BitcoinDifficulty

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

bitcoinbitcoin-mainnetconsensusdifficultyformal-verificationproof-of-workretargettimewarp

Two names over the proof-of-work mission's BitcoinPow; nothing is re-transcribed.

rawNextTarget t lastTime firstTime — the value CalculateNextWorkRequired encodes: the last target ttt times the clamped actual timespan (clampTimespan (lastTime − firstTime), between targetTimespan/4 and 4·targetTimespan), taken modulo 22562^{256}2256, divided by targetTimespan (1,209,600 s), and capped at powLimit. calculateNextWork bits lastTime firstTime is by definition getCompact (rawNextTarget (setCompact bits) lastTime firstTime).

targetAfter bits periods — the encoded target after applying calculateNextWork once per element of periods, a list of (last time, first time) pairs, starting from bits.

Formalization Note. setCompact, getCompact, clampTimespan, calculateNextWork, nextWorkRequired, powLimit, width are the proof-of-work mission's; ChainState.requiredBits is the block mission's GetNextWorkRequired on a chain. Only Std is imported.

Definition code
import Definitions.Def_BitcoinPow
import Definitions.Def_BitcoinBlockV2

/-!
# How fast the difficulty can move

`CalculateNextWorkRequired` multiplies the last target by the clamped actual timespan of the
period and divides by two weeks, caps at `powLimit`, and re-encodes. The clamp bounds the ratio
by a factor of four in either direction; this file names the raw (unencoded) next target so the
theorems can state that bound exactly, before the compact rounding, and then transfer it to the
encoded value and along a chain of periods. These are the limits on what an adversary who controls
timestamps can do to the difficulty: a "timewarp" moves the target by at most this much per period.
-/

namespace BitcoinDifficulty

open BitcoinPow

/-- The raw next target of a period: the last target times the clamped timespan, divided by the
target timespan, capped at `powLimit` — the value `CalculateNextWorkRequired` encodes. -/
def rawNextTarget (lastTarget : Nat) (lastTime firstTime : Int) : Nat :=
  let ts := (clampTimespan (lastTime - firstTime)).toNat
  let bn := (lastTarget * ts) % width / targetTimespan
  if powLimit < bn then powLimit else bn

/-- The encoded target after `m` retargets starting from `bits`, with the given sequence of
(last time, first time) pairs, one per period. -/
def targetAfter : BitVec 32 → List (Int × Int) → BitVec 32
  | bits, [] => bits
  | bits, (lastTime, firstTime) :: rest => targetAfter (calculateNextWork bits lastTime firstTime) rest

end BitcoinDifficulty
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: CalculateNextWorkRequired, GetNextWorkRequired, src/pow.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/pow.cpp; arith_uint256::SetCompact/GetCompact (arith_uint256.cpp); 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: Def_BitcoinDifficulty.lean

This file introduces two definitions, rawNextTarget and targetAfter, in terms of the imported proof-of-work definitions. The imported notions they use are expanded first; then one paragraph per declaration, in file order.

Imported notions used

Constants (from the imported proof-of-work definitions).

  • W=2256W = 2^{256}W=2256 (the modulus called width).
  • L=2224−1L = 2^{224} - 1L=2224−1 (the value called powLimit).
  • 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 (the value called targetTimespan); hence ⌊T/4⌋=302,400\lfloor T/4 \rfloor = 302{,}400⌊T/4⌋=302,400 and 4T=4,838,4004T = 4{,}838{,}4004T=4,838,400.

Decoding a compact word, D(c)D(c)D(c) (the function called setCompact). A compact word ccc is a 32-bit word, i.e. an integer with 0≤c<2320 \le c < 2^{32}0≤c<232. Put

  • e(c)=⌊c/224⌋e(c) = \lfloor c / 2^{24} \rfloore(c)=⌊c/224⌋, the top byte of ccc, an integer in [0,255][0, 255][0,255];
  • m(c)=c mod 223m(c) = c \bmod 2^{23}m(c)=cmod223, the low 23 bits of ccc (bit 23, worth 2232^{23}223, and the top byte are discarded).

Then D(c)D(c)D(c) is the natural number

D(c)={⌊m(c) / 2 8(3−e(c))⌋if e(c)≤3,(m(c)⋅2 8(e(c)−3)) mod 2256if e(c)≥4.D(c) = \begin{cases} \left\lfloor m(c) \,/\, 2^{\,8(3 - e(c))} \right\rfloor & \text{if } e(c) \le 3,\\[4pt] \left( m(c) \cdot 2^{\,8(e(c) - 3)} \right) \bmod 2^{256} & \text{if } e(c) \ge 4. \end{cases}D(c)={⌊m(c)/28(3−e(c))⌋(m(c)⋅28(e(c)−3))mod2256​if e(c)≤3,if e(c)≥4.​

Consequences of this definition that the quantifiers below silently include: D(c)<2256D(c) < 2^{256}D(c)<2256 always; D(c)=0D(c) = 0D(c)=0 whenever m(c)=0m(c) = 0m(c)=0, whenever e(c)=0e(c) = 0e(c)=0, and whenever e(c)≥35e(c) \ge 35e(c)≥35 (the shift then exceeds 256 bits and the reduction modulo 22562^{256}2256 leaves 000); for e(c)=33e(c) = 33e(c)=33 or 343434 only the low 16 or low 8 bits of m(c)m(c)m(c) survive the reduction; a word whose bit 23 ("sign" bit) is set decodes to the same value as the word with that bit cleared. DDD never consults the overflow or sign conditions of the original code; it is a total function on all 2322^{32}232 words.

Encoding a natural number, E(v)E(v)E(v) (the function called getCompact). For a natural number vvv let b(v)b(v)b(v) be its bit length (b(0)=0b(0) = 0b(0)=0, and b(v)=⌊log⁡2v⌋+1b(v) = \lfloor \log_2 v \rfloor + 1b(v)=⌊log2​v⌋+1 for v≥1v \ge 1v≥1) and let s=⌊(b(v)+7)/8⌋s = \lfloor (b(v) + 7)/8 \rfloors=⌊(b(v)+7)/8⌋ (the number of bytes of vvv). Put

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

If bit 23 of nnn is set (i.e. n∧223≠0n \wedge 2^{23} \neq 0n∧223=0, bitwise and), let n′=⌊n/28⌋n' = \lfloor n / 2^{8} \rfloorn′=⌊n/28⌋ and s′=s+1s' = s + 1s′=s+1; otherwise n′=nn' = nn′=n and s′=ss' = ss′=s. Then E(v)E(v)E(v) is the 32-bit word (n′  OR  (s′⋅224)) mod 232\left( n' \;\mathrm{OR}\; (s' \cdot 2^{24}) \right) \bmod 2^{32}(n′OR(s′⋅224))mod232 (bitwise or, then reduction modulo 2322^{32}232).

Consequences: for every v<2256v < 2^{256}v<2256 one has s≤32s \le 32s≤32 and n<224n < 2^{24}n<224, so the reductions modulo 2642^{64}264 and 2322^{32}232 change nothing and the bitwise or is a plain sum n′+s′⋅224n' + s' \cdot 2^{24}n′+s′⋅224; the word E(v)E(v)E(v) then has top byte s′s's′ and low 23 bits n′n'n′ (bit 23 of n′n'n′ is clear). Composing with DDD: for v<2256v < 2^{256}v<2256, D(E(v))D(E(v))D(E(v)) equals vvv with its lowest 8(s−3)8(s-3)8(s−3) bits set to zero (lowest 8(s−2)8(s-2)8(s−2) bits when the bit-23 adjustment fired; nothing zeroed when s≤3s \le 3s≤3 and no adjustment), so in particular D(E(v))≤vD(E(v)) \le vD(E(v))≤v, and D(E(0))=0D(E(0)) = 0D(E(0))=0.

Clamping a timespan, κ(a)\kappa(a)κ(a) (the function called clampTimespan). For an integer aaa (positive, zero or negative),

κ(a)={302,400if a<302,400,4,838,400if a>4,838,400,aotherwise.\kappa(a) = \begin{cases} 302{,}400 & \text{if } a < 302{,}400,\\ 4{,}838{,}400 & \text{if } a > 4{,}838{,}400,\\ a & \text{otherwise.} \end{cases}κ(a)=⎩⎨⎧​302,4004,838,400a​if a<302,400,if a>4,838,400,otherwise.​

κ(a)\kappa(a)κ(a) always lies in [302,400,  4,838,400][302{,}400,\; 4{,}838{,}400][302,400,4,838,400], so it is positive and its conversion to a natural number (written κ(a)\kappa(a)κ(a) below as well) is lossless.

The next encoded target, N(c,ℓ,f)N(c, \ell, f)N(c,ℓ,f) (the function called calculateNextWork). For a compact word ccc and integers ℓ\ellℓ ("last time") and fff ("first time"), put τ=κ(ℓ−f)\tau = \kappa(\ell - f)τ=κ(ℓ−f) and

u=⌊(D(c)⋅τ) mod 2256T⌋,u′={Lif L<u,uotherwise,u = \left\lfloor \frac{\left( D(c) \cdot \tau \right) \bmod 2^{256}}{T} \right\rfloor, \qquad u' = \begin{cases} L & \text{if } L < u,\\ u & \text{otherwise,}\end{cases}u=⌊T(D(c)⋅τ)mod2256​⌋,u′={Lu​if L<u,otherwise,​

i.e. u′=min⁡(u,L)u' = \min(u, L)u′=min(u,L). Then N(c,ℓ,f)=E(u′)N(c, \ell, f) = E(u')N(c,ℓ,f)=E(u′), a compact word. The product D(c)⋅τD(c)\cdot\tauD(c)⋅τ is reduced modulo 22562^{256}2256 before the floor division by TTT; the cap at LLL is applied before re-encoding, and nothing caps or checks the decoded value of the encoded result afterwards.

Declaration 1: rawNextTarget

Binders. A natural number ttt (named lastTarget; any natural number, with no upper bound — in particular not required to be below 22562^{256}2256 or LLL), and two integers ℓ\ellℓ (lastTime) and fff (firstTime), each positive, zero or negative, with no ordering between them.

Value. A natural number, defined as follows. Let τ=κ(ℓ−f)\tau = \kappa(\ell - f)τ=κ(ℓ−f), the clamped difference, a natural number in [302,400,4,838,400][302{,}400, 4{,}838{,}400][302,400,4,838,400]. Let

q=⌊(t⋅τ) mod 2256T⌋,q = \left\lfloor \frac{(t \cdot \tau) \bmod 2^{256}}{T} \right\rfloor ,q=⌊T(t⋅τ)mod2256​⌋,

where the product t⋅τt \cdot \taut⋅τ is first reduced modulo 22562^{256}2256 and the result is then divided by T=1,209,600T = 1{,}209{,}600T=1,209,600 with the remainder discarded (the source writes the two operations left to right, so the reduction precedes the division). Then

R(t,ℓ,f)={Lif L<q,qotherwise,R(t, \ell, f) = \begin{cases} L & \text{if } L < q,\\ q & \text{otherwise,} \end{cases}R(t,ℓ,f)={Lq​if L<q,otherwise,​

that is, R(t,ℓ,f)=min⁡(q,L)R(t,\ell,f) = \min(q, L)R(t,ℓ,f)=min(q,L) with L=2224−1L = 2^{224} - 1L=2224−1.

Edge cases built into the definition. If ℓ−f≤302,400\ell - f \le 302{,}400ℓ−f≤302,400 (including every case with ℓ≤f\ell \le fℓ≤f, i.e. zero or negative differences), τ=302,400\tau = 302{,}400τ=302,400; if ℓ−f≥4,838,400\ell - f \ge 4{,}838{,}400ℓ−f≥4,838,400, τ=4,838,400\tau = 4{,}838{,}400τ=4,838,400. If t=0t = 0t=0 then R=0R = 0R=0. If t⋅τ≥2256t \cdot \tau \ge 2^{256}t⋅τ≥2256 (possible for t≥2256/4,838,400t \ge 2^{256}/4{,}838{,}400t≥2256/4,838,400, which is above LLL), the reduction modulo 22562^{256}2256 discards the high part before dividing. The result is always ≤L\le L≤L, and no encoding step is applied: RRR is the value that calculateNextWork would pass to EEE, so that N(c,ℓ,f)=E(R(D(c),ℓ,f))N(c, \ell, f) = E(R(D(c), \ell, f))N(c,ℓ,f)=E(R(D(c),ℓ,f)) for every compact word ccc.

Declaration 2: targetAfter

Binders. A compact word ccc (a 32-bit word, named bits) and a finite list PPP of pairs of integers (ℓi,fi)(\ell_i, f_i)(ℓi​,fi​), where by the definition's naming the first component of each pair is the "last time" and the second the "first time" of that period.

Value. A compact word, defined by recursion on the list:

A(c,[ ])=c,A(c,(ℓ,f)::P′)=A(N(c,ℓ,f),P′).A(c, [\,]) = c, \qquad A\big(c, (\ell, f) :: P'\big) = A\big(N(c, \ell, f), P'\big).A(c,[])=c,A(c,(ℓ,f)::P′)=A(N(c,ℓ,f),P′).

Hence for P=[(ℓ1,f1),…,(ℓk,fk)]P = [(\ell_1, f_1), \dots, (\ell_k, f_k)]P=[(ℓ1​,f1​),…,(ℓk​,fk​)],

A(c,P)=N(⋯N(N(c,ℓ1,f1),ℓ2,f2)⋯ ,ℓk,fk),A(c, P) = N\big(\cdots N(N(c, \ell_1, f_1), \ell_2, f_2) \cdots, \ell_k, f_k\big),A(c,P)=N(⋯N(N(c,ℓ1​,f1​),ℓ2​,f2​)⋯,ℓk​,fk​),

where each application of NNN decodes the current word with DDD, multiplies by the clamped timespan κ(ℓi−fi)\kappa(\ell_i - f_i)κ(ℓi​−fi​) modulo 22562^{256}2256, floor-divides by TTT, caps at LLL, and re-encodes with EEE (so each step rounds the value to a compact word before the next step decodes it).

Edge cases built into the definition. For the empty list, A(c,[ ])=cA(c, [\,]) = cA(c,[])=c unchanged, whatever ccc is (no decoding or validity check). The pairs are independent integers: nothing requires fi≤ℓif_i \le \ell_ifi​≤ℓi​, nothing relates fi+1f_{i+1}fi+1​ to ℓi\ell_iℓi​, and no height or interval condition is consulted (unlike nextWorkRequired, every list element triggers a retarget). The initial word ccc is unconstrained: it may have its bit 23 set, decode to 000, or have a top byte ≥35\ge 35≥35.

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

    Confirmed by the moderator at approval.

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