Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

At constant difficulty, Core's chain work is the number of blocks times one block's proof

Proved
BitcoinBackbone.chainWork_const_bits

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

backbonebitcoinchain-growthchain-qualitycommon-prefixformal-verificationgaray-kiayias-leonardosmathlibnakamoto-consensus

For a block-mission chain state all of whose headers carry the same bits: S.chainWork = S.headers.length * blockProof bits. The link between the paper's "length" and Core's nChainWork.

Preamble
import Definitions.Def_BitcoinBackbone
Formal statement
theorem BitcoinBackbone.chainWork_const_bits (S : BitcoinBlockV2.ChainState) (bits : ℕ)
    (h : ∀ hd ∈ S.headers, hd.bits = bits) :
    S.chainWork = S.headers.length * BitcoinBlockV2.blockProof bits := by sorry
Source
J. Garay, A. Kiayias, N. Leonardos, The Bitcoin Backbone Protocol: Analysis and Applications, EUROCRYPT 2015 (full version ePrint 2014/765): https://eprint.iacr.org/2014/765; Lemmas 7, 14, 15, Theorem 16, the chain-quality theorem; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: GetBlockProof (chain.cpp) through the block mission's chainWork
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: BitcoinBackbone.chainWork_const_bits

This declaration is stated inside the BitcoinBackbone namespace but refers only to objects from the block-validation preamble (BitcoinBlockV2, BitcoinSer, BitcoinPow); none of the backbone definitions (executions, chains of abstract blocks, typicality, …) occur in it.

Statement. Let SSS be a chain state: a pair S=(headers,utxo)S=(\mathit{headers}, \mathit{utxo})S=(headers,utxo) where headers=[h0,…,hℓ−1]\mathit{headers}=[h_0,\dots,h_{\ell-1}]headers=[h0​,…,hℓ−1​] is a finite list of block headers and utxo\mathit{utxo}utxo is a ledger (unconstrained here and not used by the statement). A header hhh is a record with fields version∈Z\mathit{version}\in\mathbb{Z}version∈Z, prevBlock\mathit{prevBlock}prevBlock and merkleRoot\mathit{merkleRoot}merkleRoot (byte strings), time∈N\mathit{time}\in\mathbb{N}time∈N, bits∈N\mathit{bits}\in\mathbb{N}bits∈N (an unbounded natural number, not a 32-bit word) and nonce∈N\mathit{nonce}\in\mathbb{N}nonce∈N. Let bits∈N\mathit{bits}\in\mathbb{N}bits∈N and assume every header in the list has that bits-field:

∀h∈headers,h.bits=bits.\forall h\in\mathit{headers},\quad h.\mathit{bits}=\mathit{bits}.∀h∈headers,h.bits=bits.

Then

chainWork⁡(S)  =  ℓ⋅blockProof⁡(bits),\operatorname{chainWork}(S) \;=\; \ell\cdot\operatorname{blockProof}(\mathit{bits}),chainWork(S)=ℓ⋅blockProof(bits),

where ℓ=∣headers∣\ell=|\mathit{headers}|ℓ=∣headers∣ and multiplication is on natural numbers.

Unfolding chainWork⁡\operatorname{chainWork}chainWork. chainWork⁡(S)=∑k=0ℓ−1blockProof⁡(hk.bits)\operatorname{chainWork}(S)=\sum_{k=0}^{\ell-1}\operatorname{blockProof}(h_k.\mathit{bits})chainWork(S)=∑k=0ℓ−1​blockProof(hk​.bits), the natural-number sum of blockProof⁡\operatorname{blockProof}blockProof applied to each header's bits-field, in list order; the sum of the empty list is 000.

Unfolding blockProof⁡(b)\operatorname{blockProof}(b)blockProof(b) for b∈Nb\in\mathbb{N}b∈N. First bbb is reduced to a 32-bit word c=b mod 232c = b \bmod 2^{32}c=bmod232. From ccc one computes nSize=⌊c/224⌋\mathit{nSize}=\lfloor c/2^{24}\rfloornSize=⌊c/224⌋ (the top byte) and nWord=c∧0x007fffff\mathit{nWord}=c \wedge \mathtt{0x007fffff}nWord=c∧0x007fffff (the low 23 bits), and the candidate target

t={⌊nWord/28(3−nSize)⌋if nSize≤3,(nWord⋅28(nSize−3)) mod 2256if nSize>3.t=\begin{cases}\lfloor \mathit{nWord}/2^{8(3-\mathit{nSize})}\rfloor & \text{if } \mathit{nSize}\le3,\\[2pt] \bigl(\mathit{nWord}\cdot 2^{8(\mathit{nSize}-3)}\bigr)\bmod 2^{256} & \text{if } \mathit{nSize}>3.\end{cases}t={⌊nWord/28(3−nSize)⌋(nWord⋅28(nSize−3))mod2256​if nSize≤3,if nSize>3.​

The target is rejected (the derivation returns "none") if any of the following holds: (i) nWord≠0\mathit{nWord}\ne0nWord=0 and bit 0x00800000\mathtt{0x00800000}0x00800000 of ccc is set ("negative"); (ii) t=0t=0t=0; (iii) nWord≠0\mathit{nWord}\ne0nWord=0 and (nSize>34\mathit{nSize}>34nSize>34, or nWord>0xff\mathit{nWord}>\mathtt{0xff}nWord>0xff and nSize>33\mathit{nSize}>33nSize>33, or nWord>0xffff\mathit{nWord}>\mathtt{0xffff}nWord>0xffff and nSize>32\mathit{nSize}>32nSize>32) ("overflow"); (iv) t>2224−1t>2^{224}-1t>2224−1. Then

blockProof⁡(b)={0if the target is rejected,⌊2256−1−tt+1⌋+1otherwise, with t the derived target.\operatorname{blockProof}(b)=\begin{cases}0 & \text{if the target is rejected},\\[2pt] \left\lfloor\dfrac{2^{256}-1-t}{t+1}\right\rfloor+1 & \text{otherwise, with } t \text{ the derived target}.\end{cases}blockProof(b)=⎩⎨⎧​0⌊t+12256−1−t​⌋+1​if the target is rejected,otherwise, with t the derived target.​

Since an accepted ttt satisfies 1≤t≤2224−11\le t\le 2^{224}-11≤t≤2224−1, the subtraction 2256−1−t2^{256}-1-t2256−1−t is an ordinary one and the division is integer (floor) division.

Edge cases. If headers=[ ]\mathit{headers}=[\,]headers=[] the hypothesis is vacuous and both sides are 000. The hypothesis says nothing about the headers beyond their bits-field: they need not be chained by prevBlock\mathit{prevBlock}prevBlock, need not begin with the genesis header, need not satisfy proof-of-work, and the common value bits\mathit{bits}bits need not encode an acceptable target (if it does not, both sides are 000). Two values of bits\mathit{bits}bits that agree modulo 2322^{32}232 give the same blockProof⁡\operatorname{blockProof}blockProof, but the hypothesis demands literal equality of the natural numbers h.bits=bitsh.\mathit{bits}=\mathit{bits}h.bits=bits. Equality in the conclusion is equality of natural numbers.

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