Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof-of-work acceptance, characterized

Proved
BitcoinPow.checkProofOfWork_iff

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

bitcoinbitcoin-mainnetconsensusdifficultyformal-verificationproof-of-work

For every hash value h∈Nh \in \mathbb Nh∈N and every 32-bit word ccc,

checkProofOfWork(h,c)=true  ⟺  ¬negative(c)∧¬overflow(c)∧0<specTarget(c)∧specTarget(c)≤2224−1∧h≤specTarget(c).\mathrm{checkProofOfWork}(h, c) = \mathtt{true} \iff \neg\mathrm{negative}(c) \wedge \neg\mathrm{overflow}(c) \wedge 0 < \mathrm{specTarget}(c) \wedge \mathrm{specTarget}(c) \le 2^{224}-1 \wedge h \le \mathrm{specTarget}(c).checkProofOfWork(h,c)=true⟺¬negative(c)∧¬overflow(c)∧0<specTarget(c)∧specTarget(c)≤2224−1∧h≤specTarget(c).

This is DeriveTarget followed by the comparison in CheckProofOfWorkImpl, restated on the exact value of the word. A header passes exactly when its nBits is a well-formed, in-range, positive target and the hash is at most that target.

Preamble
import Definitions.Def_BitcoinPow
Formal statement
theorem BitcoinPow.checkProofOfWork_iff (hash : Nat) (nBits : BitVec 32) :
    BitcoinPow.checkProofOfWork hash nBits = true ↔
      BitcoinPow.compactNegative nBits = false ∧ BitcoinPow.compactOverflow nBits = false ∧
      0 < BitcoinPow.specTarget nBits ∧ BitcoinPow.specTarget nBits ≤ BitcoinPow.powLimit ∧
      hash ≤ BitcoinPow.specTarget nBits := 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 hash\mathrm{hash}hash (any natural number; no bound such as hash<2256\mathrm{hash} < 2^{256}hash<2256 is assumed) and every 32-bit word ccc ("nBits"), with top byte s=⌊c/224⌋s = \lfloor c/2^{24} \rfloors=⌊c/224⌋ (0≤s≤2550 \le s \le 2550≤s≤255) and low 23 bits m=c mod 223m = c \bmod 2^{23}m=cmod223, the Boolean value checkProofOfWork(hash,c)\mathrm{checkProofOfWork}(\mathrm{hash}, c)checkProofOfWork(hash,c) is true if and only if all five of the following hold:

  1. the "compact negative" flag [m≠0]∧[(c AND 223)≠0][m \ne 0] \wedge [(c \text{ AND } 2^{23}) \ne 0][m=0]∧[(c AND 223)=0] is false;
  2. the "compact overflow" flag [m≠0]∧([s>34]∨([m>255]∧[s>33])∨([m>65535]∧[s>32]))[m \ne 0] \wedge \big([s > 34] \vee ([m > 255] \wedge [s > 33]) \vee ([m > 65535] \wedge [s > 32])\big)[m=0]∧([s>34]∨([m>255]∧[s>33])∨([m>65535]∧[s>32])) is false;
  3. 0<T(c)0 < T(c)0<T(c);
  4. T(c)≤2224−1T(c) \le 2^{224} - 1T(c)≤2224−1;
  5. hash≤T(c)\mathrm{hash} \le T(c)hash≤T(c);

where

T(c)={⌊m/256 3−s⌋if s≤3,m⋅256 s−3if s>3T(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}T(c)={⌊m/2563−s⌋m⋅256s−3​if s≤3,if s>3​

is the custom "specTarget" value, computed on unbounded natural numbers with no reduction modulo 22562^{256}2256. All inequalities in 3–5 are exactly as written: strict in 3, non-strict in 4 and 5.

The left-hand side, unfolded. checkProofOfWork(hash,c)\mathrm{checkProofOfWork}(\mathrm{hash}, c)checkProofOfWork(hash,c) is defined through a different quantity, the "setCompact" value

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,​

as follows: it is false if (negative flag is true) or S(c)=0S(c) = 0S(c)=0 or (overflow flag is true) or 2224−1<S(c)2^{224}-1 < S(c)2224−1<S(c); otherwise it equals [hash≤S(c)][\mathrm{hash} \le S(c)][hash≤S(c)]. So the statement equates a condition phrased with SSS (reduced modulo 22562^{256}2256) on the left with a condition phrased with TTT (unreduced) on the right.

Binders and hypotheses. Two universally quantified variables, hash\mathrm{hash}hash and ccc; no hypotheses. The claim is a biconditional between "the Boolean equals true" and a five-fold conjunction of propositions. Both directions are asserted: whenever the check returns true, conditions 1–5 hold; and whenever 1–5 hold, the check returns true.

Edge cases visible in the statement. If m=0m = 0m=0 then both flags are false, T(c)=0T(c) = 0T(c)=0, condition 3 fails, and the right side is false. If s≤3s \le 3s≤3, both flags are false and T(c)=S(c)≤m<223T(c) = S(c) \le m < 2^{23}T(c)=S(c)≤m<223. The right side permits T(c)=2224−1T(c) = 2^{224}-1T(c)=2224−1 exactly (non-strict cap) and hash=T(c)\mathrm{hash} = T(c)hash=T(c) exactly. Because hash\mathrm{hash}hash is unbounded, the statement covers hash≥2256\mathrm{hash} \ge 2^{256}hash≥2256, where condition 5 forces the right side false since T(c)≤2224−1T(c) \le 2^{224}-1T(c)≤2224−1 under condition 4.

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