Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Timewarp bound: the next required target is at most four times the tip's

Proved
BitcoinDifficulty.requiredBits_le

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

bitcoinbitcoin-mainnetconsensusdifficultyformal-verificationproof-of-workretargettimewarp

For any chain state whose tip target is valid (setCompact (tip bits) ≤ powLimit): setCompact S.requiredBits ≤ 4 · setCompact (tip bits), whether or not the next block is at a retarget boundary, whatever the timestamps of the period's blocks. This is the whole of what an adversary who controls timestamps can do to the difficulty in one period under the mainnet rules: lower it by at most a factor of four (and, by encoded_target_lower, raise it by at most a factor of four); the known timewarp attack is the repetition of this bound across periods, which target_after_upper quantifies.

Preamble
import Definitions.Def_BitcoinDifficulty
import Definitions.Def_BitcoinPow
open BitcoinDifficulty BitcoinPow
Formal statement
theorem BitcoinDifficulty.requiredBits_le (S : BitcoinBlockV2.ChainState)
    (hb : BitcoinPow.setCompact (BitVec.ofNat 32 S.tip.bits) ≤ BitcoinPow.powLimit) :
    BitcoinPow.setCompact S.requiredBits ≤ 4 * BitcoinPow.setCompact (BitVec.ofNat 32 S.tip.bits) := by sorry
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: theorem BitcoinDifficulty.requiredBits_le

Statement

Binders (universally quantified).

  • SSS, a chain state: a record consisting of a finite list of headers [H0,…,Hn−1][H_0, \dots, H_{n-1}][H0​,…,Hn−1​] (n≥0n \ge 0n≥0, possibly empty) and a ledger. No validity, chaining, ordering or length property of SSS is assumed.

Write ctip=tip(S).bits mod 232c_{\mathrm{tip}} = \mathrm{tip}(S).\mathrm{bits} \bmod 2^{32}ctip​=tip(S).bitsmod232 for the compact word formed from the bits field of the tip header (the last header of the list, or the genesis header G0G_0G0​ if the list is empty).

Hypothesis.

  • (hb) D(ctip)≤L=2224−1D(c_{\mathrm{tip}}) \le L = 2^{224} - 1D(ctip​)≤L=2224−1.

Conclusion.

D(requiredBits(S))  ≤  4⋅D(ctip),D\big( \mathrm{requiredBits}(S) \big) \;\le\; 4 \cdot D(c_{\mathrm{tip}}),D(requiredBits(S))≤4⋅D(ctip​),

with 4⋅D(ctip)4 \cdot D(c_{\mathrm{tip}})4⋅D(ctip​) the plain natural-number product and a non-strict inequality. Unfolding requiredBits(S)\mathrm{requiredBits}(S)requiredBits(S): let h=tipHeight(S)=n−1h = \mathrm{tipHeight}(S) = n - 1h=tipHeight(S)=n−1 (truncated, so 000 if n=0n = 0n=0), let j=h−2015j = h - 2015j=h−2015 (truncated, so 000 if h≤2015h \le 2015h≤2015), let F=HjF = H_jF=Hj​ if j<nj < nj<n and F=G0F = G_0F=G0​ otherwise. Then

  • if (h+1) mod 2016≠0(h + 1) \bmod 2016 \ne 0(h+1)mod2016=0: requiredBits(S)=ctip\mathrm{requiredBits}(S) = c_{\mathrm{tip}}requiredBits(S)=ctip​, and the conclusion reads D(ctip)≤4⋅D(ctip)D(c_{\mathrm{tip}}) \le 4 \cdot D(c_{\mathrm{tip}})D(ctip​)≤4⋅D(ctip​);
  • if (h+1) mod 2016=0(h + 1) \bmod 2016 = 0(h+1)mod2016=0: requiredBits(S)=N(ctip,  tip(S).time,  F.time)\mathrm{requiredBits}(S) = N\big(c_{\mathrm{tip}},\; \mathrm{tip}(S).\mathrm{time},\; F.\mathrm{time}\big)requiredBits(S)=N(ctip​,tip(S).time,F.time) (times read as integers), and the conclusion reads D(N(ctip,tip(S).time,F.time))≤4⋅D(ctip)D\big(N(c_{\mathrm{tip}}, \mathrm{tip}(S).\mathrm{time}, F.\mathrm{time})\big) \le 4 \cdot D(c_{\mathrm{tip}})D(N(ctip​,tip(S).time,F.time))≤4⋅D(ctip​).

Definitions 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.

Chain states and the required bits (from the imported block-validation definitions).

  • A header is a record with fields: version (an integer), previous-block hash and Merkle root (byte strings), time (a natural number), bits (a natural number, unbounded — not restricted to 32 bits), nonce (a natural number). The genesis header G0G_0G0​ is the fixed header with version 111, zero previous hash, time 1,231,006,5051{,}231{,}006{,}5051,231,006,505, bits 0x1d00ffff=486,604,799\mathtt{0x1d00ffff} = 486{,}604{,}7990x1d00ffff=486,604,799, nonce 2,083,236,8932{,}083{,}236{,}8932,083,236,893.
  • A chain state SSS is a record with two fields: a finite list of headers S.headers=[H0,H1,…,Hn−1]S.\mathrm{headers} = [H_0, H_1, \dots, H_{n-1}]S.headers=[H0​,H1​,…,Hn−1​] (possibly empty, n≥0n \ge 0n≥0) and a ledger S.utxoS.\mathrm{utxo}S.utxo (not used by the statement below). No property of SSS (chaining of headers, validity, length, time ordering, reachability from genesis) is assumed.
  • tipHeight(S)=n−1\mathrm{tipHeight}(S) = n - 1tipHeight(S)=n−1 with truncated natural-number subtraction, so tipHeight(S)=0\mathrm{tipHeight}(S) = 0tipHeight(S)=0 when n=0n = 0n=0 as well as when n=1n = 1n=1.
  • tip(S)=Hn−1\mathrm{tip}(S) = H_{n-1}tip(S)=Hn−1​, the last header of the list, or G0G_0G0​ if the list is empty.
  • I=⌊T/600⌋=2016I = \lfloor T / 600 \rfloor = 2016I=⌊T/600⌋=2016 (the value called difficultyAdjustmentInterval).
  • nextWorkRequired(h,c,ℓ,f)\mathrm{nextWorkRequired}(h, c, \ell, f)nextWorkRequired(h,c,ℓ,f) for a natural number hhh, a compact word ccc and integers ℓ,f\ell, fℓ,f is ccc itself if (h+1) mod 2016≠0(h + 1) \bmod 2016 \neq 0(h+1)mod2016=0, and N(c,ℓ,f)N(c, \ell, f)N(c,ℓ,f) if (h+1) mod 2016=0(h+1) \bmod 2016 = 0(h+1)mod2016=0.
  • requiredBits(S)\mathrm{requiredBits}(S)requiredBits(S): let j=tipHeight(S)−2015j = \mathrm{tipHeight}(S) - 2015j=tipHeight(S)−2015 with truncated subtraction (so j=0j = 0j=0 whenever tipHeight(S)≤2015\mathrm{tipHeight}(S) \le 2015tipHeight(S)≤2015), and let F=HjF = H_jF=Hj​ if j<nj < nj<n, else F=G0F = G_0F=G0​ (this default case arises only when the header list is empty). Then
requiredBits(S)=nextWorkRequired(tipHeight(S),  tip(S).bits mod 232,  tip(S).time,  F.time),\mathrm{requiredBits}(S) = \mathrm{nextWorkRequired}\big(\mathrm{tipHeight}(S),\; \mathrm{tip}(S).\mathrm{bits} \bmod 2^{32},\; \mathrm{tip}(S).\mathrm{time},\; F.\mathrm{time}\big),requiredBits(S)=nextWorkRequired(tipHeight(S),tip(S).bitsmod232,tip(S).time,F.time),

where the two times (natural numbers) are read as integers and the tip's bits field is reduced modulo 2322^{32}232 to form a compact word.

Edge cases and what the quantifiers include

  • The header list may be empty: then tip(S)=G0\mathrm{tip}(S) = G_0tip(S)=G0​, h=0h = 0h=0, F=G0F = G_0F=G0​, (0+1) mod 2016≠0(0+1) \bmod 2016 \ne 0(0+1)mod2016=0, so requiredBits(S)=ctip=0x1d00ffff\mathrm{requiredBits}(S) = c_{\mathrm{tip}} = \mathtt{0x1d00ffff}requiredBits(S)=ctip​=0x1d00ffff and the conclusion is D(ctip)≤4D(ctip)D(c_{\mathrm{tip}}) \le 4 D(c_{\mathrm{tip}})D(ctip​)≤4D(ctip​).
  • The retarget branch is taken exactly when n mod 2016=0n \bmod 2016 = 0nmod2016=0 with n≥1n \ge 1n≥1, i.e. n=2016,4032,…n = 2016, 4032, \dotsn=2016,4032,…; for such nnn, j=n−2016≥0j = n - 2016 \ge 0j=n−2016≥0 and F=Hn−2016F = H_{n-2016}F=Hn−2016​ is the header 201520152015 positions before the tip. In every other case the required bits are the tip's own bits word.
  • The header's bits field is an unbounded natural number; only its residue modulo 2322^{32}232 enters, both in the hypothesis and in the conclusion.
  • The header times are natural numbers with no ordering assumed: F.timeF.\mathrm{time}F.time may exceed tip(S).time\mathrm{tip}(S).\mathrm{time}tip(S).time, in which case the difference is negative and clamped to 302,400302{,}400302,400; a difference above 4,838,4004{,}838{,}4004,838,400 is clamped to that value.
  • No assumption is made that the headers form a chain, that the tip is reachable from genesis, that the list has length ≥2016\ge 2016≥2016, or that any header's bits decode to a non-zero or non-overflowing target; only D(ctip)≤LD(c_{\mathrm{tip}}) \le LD(ctip​)≤L is assumed. If D(ctip)=0D(c_{\mathrm{tip}}) = 0D(ctip​)=0 the right-hand side is 000.
  • The ledger component of SSS plays no role in the statement.
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