Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Re-encoding a target rounds it down

Proved
BitcoinPow.getCompact_le

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

bitcoinbitcoin-mainnetconsensusdifficultyformal-verificationproof-of-work

For every v<2256v < 2^{256}v<2256,

setCompact(getCompact(v))≤v.\mathrm{setCompact}(\mathrm{getCompact}(v)) \le v.setCompact(getCompact(v))≤v.

GetCompact keeps only the top three bytes of vvv (fewer when the mantissa's bit 23 forces a further byte shift), so decoding the result gives vvv with some low bits cleared, never more than vvv. The case v=0v = 0v=0 is included and gives 000.

Preamble
import Definitions.Def_BitcoinPow
Formal statement
theorem BitcoinPow.getCompact_le (v : Nat) (hv : v < BitcoinPow.width) :
    BitcoinPow.setCompact (BitcoinPow.getCompact v) ≤ v := by sorry
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)

Statement. For every natural number vvv with v<2256v < 2^{256}v<2256,

S(G(v))≤v,S\big(G(v)\big) \le v,S(G(v))≤v,

where GGG ("getCompact") maps a natural number to a 32-bit word and SSS ("setCompact") maps a 32-bit word back to a natural number, both custom functions unfolded below. The inequality is non-strict.

The encoding G(v)G(v)G(v). Let β(v)=0\beta(v) = 0β(v)=0 if v=0v = 0v=0 and β(v)=⌊log⁡2v⌋+1\beta(v) = \lfloor \log_2 v \rfloor + 1β(v)=⌊log2​v⌋+1 otherwise (the number of binary digits of vvv). Let n=⌊(β(v)+7)/8⌋n = \lfloor (\beta(v) + 7)/8 \rfloorn=⌊(β(v)+7)/8⌋ (the number of bytes of vvv; n=0n = 0n=0 for v=0v = 0v=0, and n≤32n \le 32n≤32 under the hypothesis v<2256v < 2^{256}v<2256). 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, \\ \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.​

(Since v<28nv < 2^{8n}v<28n, in fact k<224k < 2^{24}k<224 and the reductions modulo 2642^{64}264 and 2322^{32}232 do not change the value.) Let aaa be true exactly when bit 23 of kkk is set, i.e. (k AND 223)≠0(k \text{ AND } 2^{23}) \ne 0(k AND 223)=0. Put k′=⌊k/256⌋k' = \lfloor k/256 \rfloork′=⌊k/256⌋ and n′=n+1n' = n+1n′=n+1 if aaa is true, and k′=kk' = kk′=k, n′=nn' = nn′=n otherwise. Then G(v)G(v)G(v) is the 32-bit word (k′ OR (n′⋅224)) mod 232\big(k' \text{ OR } (n' \cdot 2^{24})\big) \bmod 2^{32}(k′ OR (n′⋅224))mod232, where OR is bitwise-or of natural numbers. For v=0v = 0v=0 this is the word 000.

The decoding S(c)S(c)S(c). For a 32-bit word ccc with top byte s=⌊c/224⌋s = \lfloor c/2^{24} \rfloors=⌊c/224⌋ and low 23 bits m=c mod 223m = c \bmod 2^{23}m=cmod223,

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

Note that SSS reads only bits 0–22 and 24–31 of ccc; bit 23 is ignored.

Binders and hypotheses. One universally quantified natural number vvv and one hypothesis v<2256v < 2^{256}v<2256 (strict). The claim is the single inequality S(G(v))≤vS(G(v)) \le vS(G(v))≤v; equality is permitted and nothing is said about how far below vvv the value may fall. For v=0v = 0v=0 the claim reads S(word 0)=⌊0/2563⌋=0≤0S(\text{word } 0) = \lfloor 0/256^{3} \rfloor = 0 \le 0S(word 0)=⌊0/2563⌋=0≤0. Nothing is asserted for v≥2256v \ge 2^{256}v≥2256.

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