Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bitcoin Core sequence locks agree with the BIP68 specification

Proved
BitcoinBIP68.core_correct

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

bip68bitcoinbitcoin-mainnetconsensusformal-verification

Let v,fv,fv,f be unsigned 32-bit transaction-version and flag words, HHH the candidate height, MMM the supplied ancestor median-time function, and I=[(si,ci)]I=[(s_i,c_i)]I=[(si​,ci​)] a finite input list. Assume 0<H≤231−10<H\le2^{31}-10<H≤231−1, ci≤Hc_i\le Hci​≤H, and 0≤M(h)≤263−10\le M(h)\le2^{63}-10≤M(h)≤263−1 for h≤Hh\le Hh≤H. For each non-disabled input when enforcement is active, also assume the pre-subtraction sum selected by bit 22 fits its signed destination: ci+di≤231−1c_i+d_i\le2^{31}-1ci​+di​≤231−1 when bit 22 is clear (height lock), and M(max⁡(ci−1,0))+512di≤263−1M(\max(c_i-1,0))+512d_i\le2^{63}-1M(max(ci​−1,0))+512di​≤263−1 when bit 22 is set (time lock), with di=si mod 65536d_i=s_i\bmod65536di​=si​mod65536. Each input is held to the bound of its own lock type, not to either bound.

Let EEE mean v≥2v\ge2v≥2 and f mod 2=1f\bmod2=1fmod2=1. Let P(i)P(i)P(i) mean that bit 31 is set, or that the delay selected by bit 22 has elapsed: ci+di≤Hc_i+d_i\le Hci​+di​≤H for a height lock and M(max⁡(ci−1,0))+512di≤M(H−1)M(\max(c_i-1,0))+512d_i\le M(H-1)M(max(ci​−1,0))+512di​≤M(H−1) for a time lock. This component theorem has two conclusions:

SequenceLocksLean(v,f,H,M,I)=true⟺¬E ∨ ∀i∈I, P(i),\mathrm{SequenceLocks}_{\mathrm{Lean}}(v,f,H,M,I)=\mathrm{true} \quad\Longleftrightarrow\quad \neg E\ \lor\ \forall i\in I,\ P(i),SequenceLocksLean​(v,f,H,M,I)=true⟺¬E ∨ ∀i∈I, P(i),

and the returned height list is the original ordered list with cic_ici​ replaced by zero exactly when EEE holds and input iii has bit 31 set. No clock monotonicity, nonempty-list assumption, or prior acceptance assumption is imposed.

This is the correctness contract for a Lean transcription of the pinned Core helpers, relative to separately defined arithmetic eligibility and height-list specifications. Coinbase exclusion, supplying the ancestor clocks and spent-output heights, activation selection, and the manual C++-to-Lean correspondence are explicit external boundaries. It does not claim verification of a compiled Bitcoin Core binary.

Within the whole-mainnet mission this is a supporting component. Its caller assumptions must be discharged by the wider validation development; proving this theorem alone does not complete that mission.

Preamble
import Definitions.Def_BIP68_Model
import Definitions.Def_BIP68_Core
Formal statement
theorem BitcoinBIP68.core_correct (version flags : BitVec 32)
    (ctx : BitcoinBIP68.Context) (inputs : List BitcoinBIP68.Input)
    (hctx : BitcoinBIP68.admissible ctx inputs)
    (hsafe : BitcoinBIP68.noOverflow version flags ctx inputs) :
    (BitcoinBIP68.sequenceLocks version flags ctx inputs = true ↔
      BitcoinBIP68.satisfiesBIP68 version flags ctx inputs) ∧
    BitcoinBIP68.returnedHeights (BitcoinBIP68.calculate version flags ctx inputs) =
      BitcoinBIP68.expectedHeights version flags inputs := by sorry
Source
BIP68, Specification and Implementation: https://github.com/bitcoin/bips/blob/100ba872c808946155b1eeb8c4568058f2eea0a7/bip-0068.mediawiki; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48, CalculateSequenceLocks (lines 45–101), EvaluateSequenceLocks (103–111), SequenceLocks (113–116): https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/consensus/tx_verify.cpp#L45-L116. Functional contract extracted from these routines; the BIP does not number these claims as mathematical theorems.
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 of BitcoinBIP68.core_correct

Notation used throughout

  • A 32-bit word is a bit-vector of width 32. For such a word bbb, write val(b)∈{0,1,…,232−1}\mathrm{val}(b) \in \{0, 1, \dots, 2^{32}-1\}val(b)∈{0,1,…,232−1} for the natural number it encodes, and b[k]b[k]b[k] for its kkk-th bit (k=0k = 0k=0 is the least significant bit). "b&cb \mathbin{\&} cb&c" is bitwise AND of two 32-bit words, and "≠0\ne 0=0" on words means "is not the all-zero word".
  • All quotients ⌊a/m⌋\lfloor a / m \rfloor⌊a/m⌋ and remainders a mod ma \bmod mamodm are on natural numbers (floor division). Subtraction on natural numbers is truncated: a−1a - 1a−1 equals 000 when a=0a = 0a=0; where this matters I write max⁡(a−1,0)\max(a-1,0)max(a−1,0) explicitly. Subtraction written inside Z\mathbb{Z}Z is ordinary integer subtraction.
  • N32:=2147483647=231−1N_{32} := 2147483647 = 2^{31}-1N32​:=2147483647=231−1 and N64:=9223372036854775807=263−1N_{64} := 9223372036854775807 = 2^{63}-1N64​:=9223372036854775807=263−1 (these are the constants named int32Max and int64Max).
  • n≥0n \ge 0n≥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\mathit{version}version and flags\mathit{flags}flags; write v:=val(version)v := \mathrm{val}(\mathit{version})v:=val(version) and f:=val(flags)f := \mathrm{val}(\mathit{flags})f:=val(flags);
  • a context CCC, consisting of a natural number HHH (the field height) and a total function M:N→NM : \mathbb{N} \to \mathbb{N}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,…,xnx_1, \dots, x_nx1​,…,xn​ (n≥0n \ge 0n≥0), where each input xix_ixi​ consists of a 32-bit word sis_isi​ (the field sequence) and a natural number hih_ihi​ (the field coinHeight); write σi:=val(si)\sigma_i := \mathrm{val}(s_i)σi​:=val(si​).

Auxiliary notions, unfolded

"Spec-side" predicates (propositions, defined arithmetically on val\mathrm{val}val):

  • specEnabled(version,flags)\mathrm{specEnabled}(\mathit{version}, \mathit{flags})specEnabled(version,flags) :  ⟺  \iff⟺ 2≤v  ∧  f mod 2=12 \le v \;\wedge\; f \bmod 2 = 12≤v∧fmod2=1. (The second conjunct says the least significant bit of flags\mathit{flags}flags is 111.)

  • specDisabled(s)\mathrm{specDisabled}(s)specDisabled(s) :  ⟺  \iff⟺ ⌊val(s)/2147483648⌋=1\lfloor \mathrm{val}(s) / 2147483648 \rfloor = 1⌊val(s)/2147483648⌋=1, i.e. ⌊val(s)/231⌋=1\lfloor \mathrm{val}(s)/2^{31}\rfloor = 1⌊val(s)/231⌋=1. Since val(s)<232\mathrm{val}(s) < 2^{32}val(s)<232, this quotient is 000 or 111, so this holds exactly when val(s)≥231\mathrm{val}(s) \ge 2^{31}val(s)≥231, i.e. bit 31 of sss is set.

  • specTimeBased(s)\mathrm{specTimeBased}(s)specTimeBased(s) :  ⟺  \iff⟺ ⌊val(s)/4194304⌋ mod 2=1\lfloor \mathrm{val}(s)/4194304 \rfloor \bmod 2 = 1⌊val(s)/4194304⌋mod2=1, i.e. ⌊val(s)/222⌋\lfloor \mathrm{val}(s)/2^{22}\rfloor⌊val(s)/222⌋ is odd, i.e. bit 22 of sss is set.

  • specDelay(s):=val(s) mod 65536=val(s) mod 216\mathrm{specDelay}(s) := \mathrm{val}(s) \bmod 65536 = \mathrm{val}(s) \bmod 2^{16}specDelay(s):=val(s)mod65536=val(s)mod216, a natural number in [0,65535][0, 65535][0,65535] (the low 16 bits of sss read as a number).

  • inputSatisfied(C,xi)\mathrm{inputSatisfied}(C, x_i)inputSatisfied(C,xi​) :  ⟺  \iff⟺

specDisabled(si)  ∨  {M(max⁡(hi−1,0))+512⋅specDelay(si)  ≤  M(max⁡(H−1,0))if specTimeBased(si),hi+specDelay(si)  ≤  Hotherwise.\mathrm{specDisabled}(s_i) \;\vee\; \begin{cases} M\big(\max(h_i - 1, 0)\big) + 512 \cdot \mathrm{specDelay}(s_i) \;\le\; M\big(\max(H-1,0)\big) & \text{if } \mathrm{specTimeBased}(s_i),\\[4pt] h_i + \mathrm{specDelay}(s_i) \;\le\; H & \text{otherwise.} \end{cases}specDisabled(si​)∨{M(max(hi​−1,0))+512⋅specDelay(si​)≤M(max(H−1,0))hi​+specDelay(si​)≤H​if specTimeBased(si​),otherwise.​

Here the arithmetic is on natural numbers; the arguments hi−1h_i - 1hi​−1 and H−1H - 1H−1 passed to MMM are truncated natural subtractions (so if hi=0h_i = 0hi​=0, the argument is M(0)M(0)M(0)). The disjunction is inclusive: if specDisabled(si)\mathrm{specDisabled}(s_i)specDisabled(si​) holds, the input is satisfied regardless of the case analysis.

  • satisfiesBIP68(version,flags,C,[x1,…,xn])\mathrm{satisfiesBIP68}(\mathit{version}, \mathit{flags}, C, [x_1,\dots,x_n])satisfiesBIP68(version,flags,C,[x1​,…,xn​]) :  ⟺  \iff⟺
¬ specEnabled(version,flags)  ∨  ∀i∈{1,…,n}, inputSatisfied(C,xi).\neg\,\mathrm{specEnabled}(\mathit{version}, \mathit{flags}) \;\vee\; \forall i \in \{1,\dots,n\},\ \mathrm{inputSatisfied}(C, x_i).¬specEnabled(version,flags)∨∀i∈{1,…,n}, inputSatisfied(C,xi​).

If n=0n = 0n=0 the universal clause is vacuously true, so this proposition holds for the empty input list whatever version\mathit{version}version, flags\mathit{flags}flags, CCC are.

  • expectedHeights(version,flags,[x1,…,xn])\mathrm{expectedHeights}(\mathit{version}, \mathit{flags}, [x_1,\dots,x_n])expectedHeights(version,flags,[x1​,…,xn​]) is the list of natural numbers [e1,…,en][e_1, \dots, e_n][e1​,…,en​] (same length nnn, same order) with
ei:={0if specEnabled(version,flags)∧specDisabled(si),hiotherwise.e_i := \begin{cases} 0 & \text{if } \mathrm{specEnabled}(\mathit{version},\mathit{flags}) \wedge \mathrm{specDisabled}(s_i),\\ h_i & \text{otherwise.}\end{cases}ei​:={0hi​​if specEnabled(version,flags)∧specDisabled(si​),otherwise.​

"Core-side" functions (Boolean-valued, defined by bitwise operations):

  • coreEnabled(version,flags)\mathrm{coreEnabled}(\mathit{version}, \mathit{flags})coreEnabled(version,flags) is the Boolean that is true exactly when 2≤v2 \le v2≤v and the word flags&1\mathit{flags} \mathbin{\&} 1flags&1 is nonzero (i.e. bit 0 of flags\mathit{flags}flags is set).

  • coreDisabled(s)\mathrm{coreDisabled}(s)coreDisabled(s) is true exactly when s&0x80000000≠0s \mathbin{\&} \mathtt{0x80000000} \ne 0s&0x80000000=0 (bit 31 of sss is set).

  • coreTimeBased(s)\mathrm{coreTimeBased}(s)coreTimeBased(s) is true exactly when s&0x00400000≠0s \mathbin{\&} \mathtt{0x00400000} \ne 0s&0x00400000=0 (bit 22 of sss is set).

  • coreDelay(s):=val(s&0x0000ffff)\mathrm{coreDelay}(s) := \mathrm{val}(s \mathbin{\&} \mathtt{0x0000ffff})coreDelay(s):=val(s&0x0000ffff), the low 16 bits of sss as a natural number in [0,65535][0, 65535][0,65535].

  • coreSeconds(s):=val((s&0x0000ffff)≪9)\mathrm{coreSeconds}(s) := \mathrm{val}\big((s \mathbin{\&} \mathtt{0x0000ffff}) \ll 9\big)coreSeconds(s):=val((s&0x0000ffff)≪9), where ≪9\ll 9≪9 is a left shift by 9 positions inside a 32-bit word. Because the masked word is below 2162^{16}216, shifting it left by 999 stays below 225<2322^{25} < 2^{32}225<232, so no bits are lost and coreSeconds(s)=512⋅coreDelay(s)\mathrm{coreSeconds}(s) = 512 \cdot \mathrm{coreDelay}(s)coreSeconds(s)=512⋅coreDelay(s).

  • An accumulator is a triple A=(mH,mT,L)A = (m_H, m_T, L)A=(mH​,mT​,L) with mH∈Zm_H \in \mathbb{Z}mH​∈Z (minHeight), mT∈Zm_T \in \mathbb{Z}mT​∈Z (minTime), and LLL a list of natural numbers (heightsRev). The initial accumulator is A0:=(−1,−1,[ ])A_0 := (-1, -1, [\,])A0​:=(−1,−1,[]).

  • One step coreStep(C,A,xi)\mathrm{coreStep}(C, A, x_i)coreStep(C,A,xi​), for A=(mH,mT,L)A = (m_H, m_T, L)A=(mH​,mT​,L), yields:

    • if coreDisabled(si)\mathrm{coreDisabled}(s_i)coreDisabled(si​): (mH, mT, 0::L)(m_H,\ m_T,\ 0 :: L)(mH​, mT​, 0::L) — the minima are untouched and 000 is prepended to LLL;
    • else if coreTimeBased(si)\mathrm{coreTimeBased}(s_i)coreTimeBased(si​): (mH, max⁡(mT, M(max⁡(hi−1,0))+coreSeconds(si)−1), hi::L)\big(m_H,\ \max\big(m_T,\ M(\max(h_i-1,0)) + \mathrm{coreSeconds}(s_i) - 1\big),\ h_i :: L\big)(mH​, max(mT​, M(max(hi​−1,0))+coreSeconds(si​)−1), hi​::L), where the sum and the "−1-1−1" are computed in Z\mathbb{Z}Z after casting the two natural numbers to integers (so the result can be −1-1−1 when both summands are 000), while the argument hi−1h_i - 1hi​−1 of MMM is a truncated natural subtraction;
    • else: (max⁡(mH, hi+coreDelay(si)−1), mT, hi::L)\big(\max\big(m_H,\ h_i + \mathrm{coreDelay}(s_i) - 1\big),\ m_T,\ h_i :: L\big)(max(mH​, hi​+coreDelay(si​)−1), mT​, hi​::L), again with the sum and "−1-1−1" in Z\mathbb{Z}Z.
  • calculate(version,flags,C,[x1,…,xn])\mathrm{calculate}(\mathit{version}, \mathit{flags}, C, [x_1,\dots,x_n])calculate(version,flags,C,[x1​,…,xn​]) is the accumulator

    • AnA_nAn​, where Ak:=coreStep(C,Ak−1,xk)A_k := \mathrm{coreStep}(C, A_{k-1}, x_k)Ak​:=coreStep(C,Ak−1​,xk​) for k=1,…,nk = 1,\dots,nk=1,…,n (a left fold, processing inputs in list order starting from A0A_0A0​), if coreEnabled(version,flags)\mathrm{coreEnabled}(\mathit{version}, \mathit{flags})coreEnabled(version,flags) is true;
    • (−1, −1, reverse([h1,…,hn]))\big(-1,\ -1,\ \mathrm{reverse}([h_1,\dots,h_n])\big)(−1, −1, reverse([h1​,…,hn​])) otherwise.

    Unwinding the fold in the enabled case: An=(mH∗,mT∗,L∗)A_n = (m_H^\ast, m_T^\ast, L^\ast)An​=(mH∗​,mT∗​,L∗) where

mH∗=max⁡({−1}∪{ hi+coreDelay(si)−1:¬coreDisabled(si), ¬coreTimeBased(si) }),m_H^\ast = \max\Big(\{-1\} \cup \{\, h_i + \mathrm{coreDelay}(s_i) - 1 : \neg\mathrm{coreDisabled}(s_i),\ \neg\mathrm{coreTimeBased}(s_i) \,\}\Big),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) }),m_T^\ast = \max\Big(\{-1\} \cup \{\, M(\max(h_i-1,0)) + \mathrm{coreSeconds}(s_i) - 1 : \neg\mathrm{coreDisabled}(s_i),\ \mathrm{coreTimeBased}(s_i) \,\}\Big),mT∗​=max({−1}∪{M(max(hi​−1,0))+coreSeconds(si​)−1:¬coreDisabled(si​), coreTimeBased(si​)}),

(maxima in Z\mathbb{Z}Z) and L∗L^\astL∗ is the list [gn,gn−1,…,g1][g_n, g_{n-1}, \dots, g_1][gn​,gn−1​,…,g1​] with gi:=0g_i := 0gi​:=0 if coreDisabled(si)\mathrm{coreDisabled}(s_i)coreDisabled(si​) and gi:=hig_i := h_igi​:=hi​ otherwise.

  • returnedHeights(A):=reverse(L)\mathrm{returnedHeights}(A) := \mathrm{reverse}(L)returnedHeights(A):=reverse(L) for A=(mH,mT,L)A = (m_H, m_T, L)A=(mH​,mT​,L).

  • evaluate(C,A)\mathrm{evaluate}(C, A)evaluate(C,A) is the Boolean that is true exactly when, in Z\mathbb{Z}Z,

mH<H∧mT<M(max⁡(H−1,0)),m_H < H \quad\wedge\quad m_T < M\big(\max(H-1,0)\big),mH​<H∧mT​<M(max(H−1,0)),

with HHH and M(⋅)M(\cdot)M(⋅) cast from N\mathbb{N}N to Z\mathbb{Z}Z.

  • sequenceLocks(version,flags,C,inputs):=evaluate(C, calculate(version,flags,C,inputs))\mathrm{sequenceLocks}(\mathit{version}, \mathit{flags}, C, \mathit{inputs}) := \mathrm{evaluate}\big(C,\ \mathrm{calculate}(\mathit{version}, \mathit{flags}, C, \mathit{inputs})\big)sequenceLocks(version,flags,C,inputs):=evaluate(C, calculate(version,flags,C,inputs)), a Boolean.

The two hypotheses

Hypothesis hctx\mathrm{hctx}hctx — admissible(C,[x1,…,xn])\mathrm{admissible}(C, [x_1,\dots,x_n])admissible(C,[x1​,…,xn​]): all four of

  1. 0<H0 < H0<H;
  2. H≤N32=231−1H \le N_{32} = 2^{31}-1H≤N32​=231−1;
  3. for every natural number hhh with h≤Hh \le Hh≤H: M(h)≤N64=263−1M(h) \le N_{64} = 2^{63}-1M(h)≤N64​=263−1 (nothing is assumed about M(h)M(h)M(h) for h>Hh > Hh>H);
  4. for every i∈{1,…,n}i \in \{1,\dots,n\}i∈{1,…,n}: hi≤Hh_i \le Hhi​≤H.

Because of (1), H−1H - 1H−1 is an honest subtraction (H−1≥0H - 1 \ge 0H−1≥0 and (H−1)+1=H(H-1)+1 = H(H−1)+1=H). Nothing forces hi>0h_i > 0hi​>0, so hi−1h_i - 1hi​−1 may still truncate to 000.

Hypothesis hsafe\mathrm{hsafe}hsafe — noOverflow(version,flags,C,[x1,…,xn])\mathrm{noOverflow}(\mathit{version}, \mathit{flags}, C, [x_1,\dots,x_n])noOverflow(version,flags,C,[x1​,…,xn​]): for every i∈{1,…,n}i \in \{1,\dots,n\}i∈{1,…,n}, if specEnabled(version,flags)\mathrm{specEnabled}(\mathit{version},\mathit{flags})specEnabled(version,flags) holds and specDisabled(si)\mathrm{specDisabled}(s_i)specDisabled(si​) does not hold, then

{M(max⁡(hi−1,0))+512⋅specDelay(si)  ≤  N64if specTimeBased(si),hi+specDelay(si)  ≤  N32otherwise\begin{cases} M\big(\max(h_i-1,0)\big) + 512 \cdot \mathrm{specDelay}(s_i) \;\le\; N_{64} & \text{if } \mathrm{specTimeBased}(s_i),\\[4pt] h_i + \mathrm{specDelay}(s_i) \;\le\; N_{32} & \text{otherwise} \end{cases}{M(max(hi​−1,0))+512⋅specDelay(si​)≤N64​hi​+specDelay(si​)≤N32​​if specTimeBased(si​),otherwise​

(natural-number arithmetic). This hypothesis is vacuous for inputs whose sequence word has bit 31 set, is vacuous when specEnabled\mathrm{specEnabled}specEnabled fails, and is vacuous when n=0n = 0n=0. Both hypotheses are expressed with the spec-side (arithmetic) predicates, not the core-side (bitwise) ones.

Both hypotheses are satisfiable (e.g. H=1H = 1H=1, M≡0M \equiv 0M≡0, no inputs), so the theorem is not vacuous as a whole; but it asserts nothing about any (version,flags,C,inputs)(\mathit{version}, \mathit{flags}, C, \mathit{inputs})(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]).\mathrm{sequenceLocks}(\mathit{version}, \mathit{flags}, C, [x_1,\dots,x_n]) = \mathtt{true} \quad\Longleftrightarrow\quad \mathrm{satisfiesBIP68}(\mathit{version}, \mathit{flags}, C, [x_1,\dots,x_n]).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)A = (m_H, m_T, L)A=(mH​,mT​,L) be calculate(…)\mathrm{calculate}(\ldots)calculate(…) as described above (the fold AnA_nAn​ if coreEnabled\mathrm{coreEnabled}coreEnabled is true, else (−1,−1,reverse[h1,…,hn])(-1,-1,\mathrm{reverse}[h_1,\dots,h_n])(−1,−1,reverse[h1​,…,hn​])), one has mH<Hm_H < HmH​<H and mT<M(H−1)m_T < M(H-1)mT​<M(H−1) in Z\mathbb{Z}Z. The right-hand side is the proposition: either ¬(2≤v∧f mod 2=1)\neg(2 \le v \wedge f \bmod 2 = 1)¬(2≤v∧fmod2=1), or every input xix_ixi​ satisfies inputSatisfied(C,xi)\mathrm{inputSatisfied}(C, x_i)inputSatisfied(C,xi​) as unfolded above.

Edge cases contained in (A):

  • If coreEnabled\mathrm{coreEnabled}coreEnabled is false, the left side reads −1<H∧−1<M(H−1)-1 < H \wedge -1 < M(H-1)−1<H∧−1<M(H−1), which holds because HHH and M(H−1)M(H-1)M(H−1) are casts of natural numbers.
  • If n=0n = 0n=0, the left side reads −1<H∧−1<M(H−1)-1 < H \wedge -1 < M(H-1)−1<H∧−1<M(H−1) (the fold returns A0A_0A0​), and the right side holds vacuously.
  • On the core side, comparisons are strict (<<<) against thresholds of the form "…−1\ldots - 1…−1" in Z\mathbb{Z}Z; on the spec side, comparisons are non-strict (≤\le≤) in N\mathbb{N}N without the "−1-1−1".
  • On the core side an input with coreDisabled(si)\mathrm{coreDisabled}(s_i)coreDisabled(si​) contributes nothing to mH,mTm_H, m_TmH​,mT​; on the spec side an input with specDisabled(si)\mathrm{specDisabled}(s_i)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]).\mathrm{returnedHeights}\big(\mathrm{calculate}(\mathit{version}, \mathit{flags}, C, [x_1,\dots,x_n])\big) \;=\; \mathrm{expectedHeights}(\mathit{version}, \mathit{flags}, [x_1,\dots,x_n]).returnedHeights(calculate(version,flags,C,[x1​,…,xn​]))=expectedHeights(version,flags,[x1​,…,xn​]).

Unfolded, the left-hand list is:

  • [g1,…,gn][g_1, \dots, g_n][g1​,…,gn​] with gi=0g_i = 0gi​=0 if bit 31 of sis_isi​ is set and gi=hig_i = h_igi​=hi​ otherwise, if coreEnabled(version,flags)\mathrm{coreEnabled}(\mathit{version},\mathit{flags})coreEnabled(version,flags) is true (i.e. 2≤v2 \le v2≤v and bit 0 of flags\mathit{flags}flags is set);
  • [h1,…,hn][h_1, \dots, h_n][h1​,…,hn​] (the reverse of the reversed coin-height list) otherwise.

The right-hand list is [e1,…,en][e_1,\dots,e_n][e1​,…,en​] with ei=0e_i = 0ei​=0 if (2≤v∧f mod 2=12 \le v \wedge f \bmod 2 = 12≤v∧fmod2=1) and ⌊σi/231⌋=1\lfloor \sigma_i / 2^{31}\rfloor = 1⌊σi​/231⌋=1, and ei=hie_i = h_iei​=hi​ otherwise. Both lists have length nnn and preserve input order; for n=0n = 0n=0 both are the empty list. Note that expectedHeights\mathrm{expectedHeights}expectedHeights does not depend on the context CCC, whereas the left-hand side is computed from calculate\mathrm{calculate}calculate, which takes CCC as an argument (though CCC only enters the mH,mTm_H, m_TmH​,mT​ components, not LLL).

Summary in one sentence

For all 32-bit words version,flags\mathit{version}, \mathit{flags}version,flags, every context C=(H,M)C = (H, M)C=(H,M) with MMM a total function N→N\mathbb{N}\to\mathbb{N}N→N, and every finite (possibly empty) list of inputs (si,hi)i=1n(s_i, h_i)_{i=1}^n(si​,hi​)i=1n​, if 0<H≤231−10 < H \le 2^{31}-10<H≤231−1, M(h)≤263−1M(h) \le 2^{63}-1M(h)≤263−1 for all h≤Hh \le Hh≤H, every hi≤Hh_i \le Hhi​≤H, and for every input with 2≤v2 \le v2≤v, fff odd, and bit 31 of sis_isi​ clear the quantity M(max⁡(hi−1,0))+512(σi mod 216)M(\max(h_i-1,0)) + 512(\sigma_i \bmod 2^{16})M(max(hi​−1,0))+512(σi​mod216) (if bit 22 of sis_isi​ is set) resp. hi+(σi mod 216)h_i + (\sigma_i \bmod 2^{16})hi​+(σi​mod216) (otherwise) is at most 263−12^{63}-1263−1 resp. 231−12^{31}-1231−1, then (A) the Boolean sequenceLocks\mathrm{sequenceLocks}sequenceLocks computed by the bitwise/integer-accumulator fold is true exactly when the arithmetic proposition satisfiesBIP68\mathrm{satisfiesBIP68}satisfiesBIP68 holds, and (B) the list of heights read off that fold's accumulator equals, entry by entry, the list expectedHeights\mathrm{expectedHeights}expectedHeights defined arithmetically.

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