Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Without overflow, SetCompact decodes the exact value

Proved
BitcoinPow.setCompact_eq_spec

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

bitcoinbitcoin-mainnetconsensusdifficultyformal-verificationproof-of-work

For every 32-bit word ccc whose overflow flag is clear,

setCompact(c)=specTarget(c).\mathrm{setCompact}(c) = \mathrm{specTarget}(c).setCompact(c)=specTarget(c).

The 256-bit register arithmetic of SetCompact (a left shift that drops carried-out bits) loses nothing when the flag is clear, so the decoded target is the mathematical value W⋅256S−3W \cdot 256^{S-3}W⋅256S−3 (or ⌊W/2563−S⌋\lfloor W / 256^{3-S} \rfloor⌊W/2563−S⌋ for S≤3S \le 3S≤3).

Preamble
import Definitions.Def_BitcoinPow
Formal statement
theorem BitcoinPow.setCompact_eq_spec (c : BitVec 32) (h : BitcoinPow.compactOverflow c = false) :
    BitcoinPow.setCompact c = BitcoinPow.specTarget c := 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 32-bit word ccc (an integer with 0≤c<2320 \le c < 2^{32}0≤c<232), writing s=⌊c/224⌋s = \lfloor c / 2^{24} \rfloors=⌊c/224⌋ for its top byte (0≤s≤2550 \le s \le 2550≤s≤255) and m=c mod 223m = c \bmod 2^{23}m=cmod223 for its low 23 bits (0≤m≤83886070 \le m \le 83886070≤m≤8388607): if the Boolean "compact overflow" flag

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

is false — that is, if m=0m = 0m=0, or (s≤34s \le 34s≤34 and (m≤255m \le 255m≤255 or s≤33s \le 33s≤33) and (m≤65535m \le 65535m≤65535 or s≤32s \le 32s≤32)) — then the two natural numbers

S(c)={⌊m/256 3−s⌋if s≤3,(m⋅256 s−3) mod 2256if s>3andT(c)={⌊m/256 3−s⌋if s≤3,m⋅256 s−3if s>3S(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} \qquad\text{and}\qquad T(c) = \begin{cases} \lfloor m / 256^{\,3-s} \rfloor & \text{if } s \le 3, \\ m \cdot 256^{\,s-3} & \text{if } s > 3 \end{cases}S(c)={⌊m/2563−s⌋(m⋅256s−3)mod2256​if s≤3,if s>3​andT(c)={⌊m/2563−s⌋m⋅256s−3​if s≤3,if s>3​

are equal: S(c)=T(c)S(c) = T(c)S(c)=T(c). Here SSS is the custom "setCompact" value (a right shift by 8(3−s)8(3-s)8(3−s) bits when s≤3s \le 3s≤3, otherwise a left shift by 8(s−3)8(s-3)8(s−3) bits followed by reduction modulo 22562^{256}2256) and TTT is the custom "specTarget" value (the same without any modular reduction).

Binders and hypotheses. One universally quantified variable ccc ranging over all 32-bit words, and one hypothesis, namely that the overflow flag of ccc equals the Boolean false. This is a one-directional implication (hypothesis ⇒\Rightarrow⇒ equality), not an equivalence; nothing is asserted about words whose overflow flag is true. Bit 23 of ccc is irrelevant to every quantity involved.

Edge cases visible in the statement. For s≤3s \le 3s≤3 the two sides are syntactically the same computation (floor division by 2563−s256^{3-s}2563−s equals right shift by 8(3−s)8(3-s)8(3−s) bits) regardless of the hypothesis. For s>3s > 3s>3 the only possible difference is the reduction modulo 22562^{256}2256 in SSS. If m=0m = 0m=0 the hypothesis holds and both sides are 000. The hypothesis permits, for example, s=33s = 33s=33 with m≤65535m \le 65535m≤65535, s=34s = 34s=34 with m≤255m \le 255m≤255, and any s≥35s \ge 35s≥35 with m=0m = 0m=0.

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