What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back of BitcoinBIP68.core_correct
Notation used throughout
- A 32-bit word is a bit-vector of width 32. For such a word b, write val(b)∈{0,1,…,232−1} for the natural number it encodes, and b[k] for its k-th bit (k=0 is the least significant bit). "b&c" is bitwise AND of two 32-bit words, and "=0" on words means "is not the all-zero word".
- All quotients ⌊a/m⌋ and remainders amodm are on natural numbers (floor division). Subtraction on natural numbers is truncated: a−1 equals 0 when a=0; where this matters I write max(a−1,0) explicitly. Subtraction written inside Z is ordinary integer subtraction.
- N32:=2147483647=231−1 and N64:=9223372036854775807=263−1 (these are the constants named
int32Max and int64Max).
- n≥0 is arbitrary; the list of inputs may be empty.
The objects quantified over
The theorem is universally quantified over:
- two 32-bit words version and flags; write v:=val(version) and f:=val(flags);
- a context C, consisting of a natural number H (the field
height) and a total function M:N→N (the field mtp), defined on every natural number with no constraint beyond those in the hypotheses below;
- a finite list of inputs x1,…,xn (n≥0), where each input xi consists of a 32-bit word si (the field
sequence) and a natural number hi (the field coinHeight); write σi:=val(si).
Auxiliary notions, unfolded
"Spec-side" predicates (propositions, defined arithmetically on val):
-
specEnabled(version,flags) :⟺ 2≤v∧fmod2=1. (The second conjunct says the least significant bit of flags is 1.)
-
specDisabled(s) :⟺ ⌊val(s)/2147483648⌋=1, i.e. ⌊val(s)/231⌋=1. Since val(s)<232, this quotient is 0 or 1, so this holds exactly when val(s)≥231, i.e. bit 31 of s is set.
-
specTimeBased(s) :⟺ ⌊val(s)/4194304⌋mod2=1, i.e. ⌊val(s)/222⌋ is odd, i.e. bit 22 of s is set.
-
specDelay(s):=val(s)mod65536=val(s)mod216, a natural number in [0,65535] (the low 16 bits of s read as a number).
-
inputSatisfied(C,xi) :⟺
specDisabled(si)∨{M(max(hi−1,0))+512⋅specDelay(si)≤M(max(H−1,0))hi+specDelay(si)≤Hif specTimeBased(si),otherwise.
Here the arithmetic is on natural numbers; the arguments hi−1 and H−1 passed to M are truncated natural subtractions (so if hi=0, the argument is M(0)). The disjunction is inclusive: if specDisabled(si) holds, the input is satisfied regardless of the case analysis.
- satisfiesBIP68(version,flags,C,[x1,…,xn]) :⟺
¬specEnabled(version,flags)∨∀i∈{1,…,n}, inputSatisfied(C,xi).
If n=0 the universal clause is vacuously true, so this proposition holds for the empty input list whatever version, flags, C are.
- expectedHeights(version,flags,[x1,…,xn]) is the list of natural numbers [e1,…,en] (same length n, same order) with
ei:={0hiif specEnabled(version,flags)∧specDisabled(si),otherwise.
"Core-side" functions (Boolean-valued, defined by bitwise operations):
-
coreEnabled(version,flags) is the Boolean that is true exactly when 2≤v and the word flags&1 is nonzero (i.e. bit 0 of flags is set).
-
coreDisabled(s) is true exactly when s&0x80000000=0 (bit 31 of s is set).
-
coreTimeBased(s) is true exactly when s&0x00400000=0 (bit 22 of s is set).
-
coreDelay(s):=val(s&0x0000ffff), the low 16 bits of s as a natural number in [0,65535].
-
coreSeconds(s):=val((s&0x0000ffff)≪9), where ≪9 is a left shift by 9 positions inside a 32-bit word. Because the masked word is below 216, shifting it left by 9 stays below 225<232, so no bits are lost and coreSeconds(s)=512⋅coreDelay(s).
-
An accumulator is a triple A=(mH,mT,L) with mH∈Z (minHeight), mT∈Z (minTime), and L a list of natural numbers (heightsRev). The initial accumulator is A0:=(−1,−1,[]).
-
One step coreStep(C,A,xi), for A=(mH,mT,L), yields:
- if coreDisabled(si): (mH, mT, 0::L) — the minima are untouched and 0 is prepended to L;
- else if coreTimeBased(si): (mH, max(mT, M(max(hi−1,0))+coreSeconds(si)−1), hi::L), where the sum and the "−1" are computed in Z after casting the two natural numbers to integers (so the result can be −1 when both summands are 0), while the argument hi−1 of M is a truncated natural subtraction;
- else: (max(mH, hi+coreDelay(si)−1), mT, hi::L), again with the sum and "−1" in Z.
-
calculate(version,flags,C,[x1,…,xn]) is the accumulator
- An, where Ak:=coreStep(C,Ak−1,xk) for k=1,…,n (a left fold, processing inputs in list order starting from A0), if coreEnabled(version,flags) is
true;
- (−1, −1, reverse([h1,…,hn])) otherwise.
Unwinding the fold in the enabled case: An=(mH∗,mT∗,L∗) where
mH∗=max({−1}∪{hi+coreDelay(si)−1:¬coreDisabled(si), ¬coreTimeBased(si)}),
mT∗=max({−1}∪{M(max(hi−1,0))+coreSeconds(si)−1:¬coreDisabled(si), coreTimeBased(si)}),
(maxima in Z) and L∗ is the list [gn,gn−1,…,g1] with gi:=0 if coreDisabled(si) and gi:=hi otherwise.
-
returnedHeights(A):=reverse(L) for A=(mH,mT,L).
-
evaluate(C,A) is the Boolean that is true exactly when, in Z,
mH<H∧mT<M(max(H−1,0)),
with H and M(⋅) cast from N to Z.
- sequenceLocks(version,flags,C,inputs):=evaluate(C, calculate(version,flags,C,inputs)), a Boolean.
The two hypotheses
Hypothesis hctx — admissible(C,[x1,…,xn]): all four of
- 0<H;
- H≤N32=231−1;
- for every natural number h with h≤H: M(h)≤N64=263−1 (nothing is assumed about M(h) for h>H);
- for every i∈{1,…,n}: hi≤H.
Because of (1), H−1 is an honest subtraction (H−1≥0 and (H−1)+1=H). Nothing forces hi>0, so hi−1 may still truncate to 0.
Hypothesis hsafe — noOverflow(version,flags,C,[x1,…,xn]): for every i∈{1,…,n}, if specEnabled(version,flags) holds and specDisabled(si) does not hold, then
{M(max(hi−1,0))+512⋅specDelay(si)≤N64hi+specDelay(si)≤N32if specTimeBased(si),otherwise
(natural-number arithmetic). This hypothesis is vacuous for inputs whose sequence word has bit 31 set, is vacuous when specEnabled fails, and is vacuous when n=0. Both hypotheses are expressed with the spec-side (arithmetic) predicates, not the core-side (bitwise) ones.
Both hypotheses are satisfiable (e.g. H=1, M≡0, no inputs), so the theorem is not vacuous as a whole; but it asserts nothing about any (version,flags,C,inputs) that violates either hypothesis.
The conclusion
Under the hypotheses above, the theorem asserts the conjunction of two statements.
(A) Lock-evaluation agreement (an "if and only if"):
sequenceLocks(version,flags,C,[x1,…,xn])=true⟺satisfiesBIP68(version,flags,C,[x1,…,xn]).
The left-hand side is the proposition that a Boolean equals true; fully unfolded it says: letting A=(mH,mT,L) be calculate(…) as described above (the fold An if coreEnabled is true, else (−1,−1,reverse[h1,…,hn])), one has mH<H and mT<M(H−1) in Z. The right-hand side is the proposition: either ¬(2≤v∧fmod2=1), or every input xi satisfies inputSatisfied(C,xi) as unfolded above.
Edge cases contained in (A):
- If coreEnabled is
false, the left side reads −1<H∧−1<M(H−1), which holds because H and M(H−1) are casts of natural numbers.
- If n=0, the left side reads −1<H∧−1<M(H−1) (the fold returns A0), and the right side holds vacuously.
- On the core side, comparisons are strict (<) against thresholds of the form "…−1" in Z; on the spec side, comparisons are non-strict (≤) in N without the "−1".
- On the core side an input with coreDisabled(si) contributes nothing to mH,mT; on the spec side an input with specDisabled(si) is satisfied outright.
(B) Returned-heights agreement (an equality of lists of natural numbers):
returnedHeights(calculate(version,flags,C,[x1,…,xn]))=expectedHeights(version,flags,[x1,…,xn]).
Unfolded, the left-hand list is:
- [g1,…,gn] with gi=0 if bit 31 of si is set and gi=hi otherwise, if coreEnabled(version,flags) is
true (i.e. 2≤v and bit 0 of flags is set);
- [h1,…,hn] (the reverse of the reversed coin-height list) otherwise.
The right-hand list is [e1,…,en] with ei=0 if (2≤v∧fmod2=1) and ⌊σi/231⌋=1, and ei=hi otherwise. Both lists have length n and preserve input order; for n=0 both are the empty list. Note that expectedHeights does not depend on the context C, whereas the left-hand side is computed from calculate, which takes C as an argument (though C only enters the mH,mT components, not L).
Summary in one sentence
For all 32-bit words version,flags, every context C=(H,M) with M a total function N→N, and every finite (possibly empty) list of inputs (si,hi)i=1n, if 0<H≤231−1, M(h)≤263−1 for all h≤H, every hi≤H, and for every input with 2≤v, f odd, and bit 31 of si clear the quantity M(max(hi−1,0))+512(σimod216) (if bit 22 of si is set) resp. hi+(σimod216) (otherwise) is at most 263−1 resp. 231−1, then (A) the Boolean sequenceLocks computed by the bitwise/integer-accumulator fold is true exactly when the arithmetic proposition satisfiesBIP68 holds, and (B) the list of heights read off that fold's accumulator equals, entry by entry, the list expectedHeights defined arithmetically.
Confirmed by the moderator at approval.