Timewarp bound: the next required target is at most four times the tip's
ProvedBitcoinDifficulty.requiredBits_leFor 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.
import Definitions.Def_BitcoinDifficulty import Definitions.Def_BitcoinPow open BitcoinDifficulty BitcoinPow
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 sorryRead-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).
- , a chain state: a record consisting of a finite list of headers (, possibly empty) and a ledger. No validity, chaining, ordering or length property of is assumed.
Write for the compact word formed from the bits field of the tip header (the last header of the list, or the genesis header if the list is empty).
Hypothesis.
- (hb) .
Conclusion.
with the plain natural-number product and a non-strict inequality. Unfolding : let (truncated, so if ), let (truncated, so if ), let if and otherwise. Then
- if : , and the conclusion reads ;
- if : (times read as integers), and the conclusion reads .
Definitions used
Constants (from the imported proof-of-work definitions).
- (the modulus called
width). - (the value called
powLimit). - (the value called
targetTimespan); hence and .
Decoding a compact word, (the function called setCompact). A compact word is a 32-bit word, i.e. an integer with . Put
- , the top byte of , an integer in ;
- , the low 23 bits of (bit 23, worth , and the top byte are discarded).
Then is the natural number
Consequences of this definition that the quantifiers below silently include: always; whenever , whenever , and whenever (the shift then exceeds 256 bits and the reduction modulo leaves ); for or only the low 16 or low 8 bits of survive the reduction; a word whose bit 23 ("sign" bit) is set decodes to the same value as the word with that bit cleared. never consults the overflow or sign conditions of the original code; it is a total function on all words.
Encoding a natural number, (the function called getCompact). For a natural number let be its bit length (, and for ) and let (the number of bytes of ). Put
If bit 23 of is set (i.e. , bitwise and), let and ; otherwise and . Then is the 32-bit word (bitwise or, then reduction modulo ).
Consequences: for every one has and , so the reductions modulo and change nothing and the bitwise or is a plain sum ; the word then has top byte and low 23 bits (bit 23 of is clear). Composing with : for , equals with its lowest bits set to zero (lowest bits when the bit-23 adjustment fired; nothing zeroed when and no adjustment), so in particular , and .
Clamping a timespan, (the function called clampTimespan). For an integer (positive, zero or negative),
always lies in , so it is positive and its conversion to a natural number (written below as well) is lossless.
The next encoded target, (the function called calculateNextWork). For a compact word and integers ("last time") and ("first time"), put and
i.e. . Then , a compact word. The product is reduced modulo before the floor division by ; the cap at 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 is the fixed header with version , zero previous hash, time , bits , nonce .
- A chain state is a record with two fields: a finite list of headers (possibly empty, ) and a ledger (not used by the statement below). No property of (chaining of headers, validity, length, time ordering, reachability from genesis) is assumed.
- with truncated natural-number subtraction, so when as well as when .
- , the last header of the list, or if the list is empty.
- (the value called
difficultyAdjustmentInterval). - for a natural number , a compact word and integers is itself if , and if .
- : let with truncated subtraction (so whenever ), and let if , else (this default case arises only when the header list is empty). Then
where the two times (natural numbers) are read as integers and the tip's bits field is reduced modulo to form a compact word.
Edge cases and what the quantifiers include
- The header list may be empty: then , , , , so and the conclusion is .
- The retarget branch is taken exactly when with , i.e. ; for such , and is the header 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 enters, both in the hypothesis and in the conclusion.
- The header times are natural numbers with no ordering assumed: may exceed , in which case the difference is negative and clamped to ; a difference above 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 , or that any header's bits decode to a non-zero or non-overflowing target; only is assumed. If the right-hand side is .
- The ledger component of plays no role in the statement.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.