Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BIP68 input data, declarative eligibility, and arithmetic domain

Definition
BIP68_Model

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

bip68bitcoinbitcoin-mainnetconsensusformal-verification

An input consists of an unsigned 32-bit sequence word sss and a natural-number coin height ccc. A context consists of a natural-number candidate height HHH and a total function M:N→NM:\mathbb N\to\mathbb NM:N→N supplying median times. Put h−=max⁡(h−1,0)h^-=\max(h-1,0)h−=max(h−1,0), d=s mod 65536d=s\bmod 65536d=smod65536, and let DDD and TTT be the tests for bits 31 and 22, expressed by quotient and remainder. Enforcement EEE means that the unsigned version is at least two and the flags value is odd. A single input satisfies its delay when

D ∨ {M(c−)+512d≤M(H−),T,c+d≤H,¬T.D\ \lor\ \begin{cases}M(c^-)+512d\le M(H^-),&T,\\ c+d\le H,&\neg T.\end{cases}D ∨ {M(c−)+512d≤M(H−),c+d≤H,​T,¬T.​

The transaction-level predicate holds when EEE is false or every input satisfies that condition. The expected output height list replaces an input height by zero exactly when EEE and DDD both hold, preserving order and repetitions.

The admissible-context predicate requires 0<H≤231−10<H\le2^{31}-10<H≤231−1, every input height at most HHH, and M(h)≤263−1M(h)\le2^{63}-1M(h)≤263−1 for all h≤Hh\le Hh≤H. A separate no-overflow predicate requires the selected pre-subtraction sum to be at most 231−12^{31}-1231−1 for an enforced height input, or 263−12^{63}-1263−1 for an enforced time input. It imposes no sum condition on disabled inputs or when enforcement is off. Heights and clocks are nonnegative by type; no clock monotonicity is assumed. Empty input lists are included. The records alone impose no validity conditions: the predicates supply them when a theorem needs them.

These definitions separate per-input eligibility from the implementation's threshold-accumulation algorithm. Decidable instances are supplied for the three flag predicates.

Definition code
import Std

namespace BitcoinBIP68

structure Input where
  sequence : BitVec 32
  coinHeight : Nat
  deriving Repr, DecidableEq

structure Context where
  height : Nat
  mtp : Nat → Nat

def int32Max : Nat := 2147483647
def int64Max : Nat := 9223372036854775807

def specEnabled (version flags : BitVec 32) : Prop :=
  2 ≤ version.toNat ∧ flags.toNat % 2 = 1

def specDisabled (sequence : BitVec 32) : Prop :=
  sequence.toNat / 2147483648 = 1

def specTimeBased (sequence : BitVec 32) : Prop :=
  (sequence.toNat / 4194304) % 2 = 1

def specDelay (sequence : BitVec 32) : Nat :=
  sequence.toNat % 65536

instance (version flags : BitVec 32) : Decidable (specEnabled version flags) :=
  inferInstanceAs (Decidable (2 ≤ version.toNat ∧ flags.toNat % 2 = 1))

instance (sequence : BitVec 32) : Decidable (specDisabled sequence) :=
  inferInstanceAs (Decidable (sequence.toNat / 2147483648 = 1))

instance (sequence : BitVec 32) : Decidable (specTimeBased sequence) :=
  inferInstanceAs (Decidable ((sequence.toNat / 4194304) % 2 = 1))

def inputSatisfied (ctx : Context) (input : Input) : Prop :=
  specDisabled input.sequence ∨
    if specTimeBased input.sequence then
      ctx.mtp (input.coinHeight - 1) + 512 * specDelay input.sequence ≤
        ctx.mtp (ctx.height - 1)
    else
      input.coinHeight + specDelay input.sequence ≤ ctx.height

def satisfiesBIP68 (version flags : BitVec 32) (ctx : Context)
    (inputs : List Input) : Prop :=
  ¬ specEnabled version flags ∨ ∀ input ∈ inputs, inputSatisfied ctx input

def expectedHeights (version flags : BitVec 32) (inputs : List Input) : List Nat :=
  inputs.map fun input =>
    if specEnabled version flags ∧ specDisabled input.sequence then 0
    else input.coinHeight

def admissible (ctx : Context) (inputs : List Input) : Prop :=
  0 < ctx.height ∧ ctx.height ≤ int32Max ∧
  (∀ h, h ≤ ctx.height → ctx.mtp h ≤ int64Max) ∧
  ∀ input ∈ inputs, input.coinHeight ≤ ctx.height

def noOverflow (version flags : BitVec 32) (ctx : Context)
    (inputs : List Input) : Prop :=
  ∀ input ∈ inputs, specEnabled version flags → ¬ specDisabled input.sequence →
    if specTimeBased input.sequence then
      ctx.mtp (input.coinHeight - 1) + 512 * specDelay input.sequence ≤ int64Max
    else
      input.coinHeight + specDelay input.sequence ≤ int32Max

end BitcoinBIP68
Source
BIP68, Specification and Implementation sections: https://github.com/bitcoin/bips/blob/100ba872c808946155b1eeb8c4568058f2eea0a7/bip-0068.mediawiki; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48, CalculateSequenceLocks/EvaluateSequenceLocks/SequenceLocks, lines 45–116: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/consensus/tx_verify.cpp#L45-L116; constants: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/primitives/transaction.h#L86-L115.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex independent sub-agent)

Input. An input is a record consisting of a sequence value represented by a 32-bit vector and a coin height that is a natural number. The unsigned integer represented by the sequence can be any integer from 000 through 232−12^{32}-1232−1, inclusive; the coin height can be any natural number, including 000, with no bound or relationship to the sequence imposed. The declaration also supplies a printable representation and decidable equality for these records.

Context. A context is a record consisting of a height HHH that is a natural number and a total function M:N→NM:\mathbb N\to\mathbb NM:N→N. The height may be 000, and the function has a natural-number value at every natural-number argument. This declaration imposes no bound, monotonicity, or other relationship on the height or the function.

int32Max. This natural-number constant is defined to be 2,147,483,6472{,}147{,}483{,}6472,147,483,647.

int64Max. This natural-number constant is defined to be 9,223,372,036,854,775,8079{,}223{,}372{,}036{,}854{,}775{,}8079,223,372,036,854,775,807.

specEnabled. For any two 32-bit vectors called version and flags, let vvv and fff be their unsigned integer values, each between 000 and 232−12^{32}-1232−1, inclusive. The proposition defined here holds exactly when 2≤v2\le v2≤v and the remainder of fff on division by 222 is 111. Thus the comparison uses the unsigned value of the version, and there are no further restrictions on either vector.

specDisabled. For any 32-bit sequence vector with unsigned integer value s∈{0,…,232−1}s\in\{0,\ldots,2^{32}-1\}s∈{0,…,232−1}, the proposition defined here holds exactly when the integer quotient of sss by 2,147,483,6482{,}147{,}483{,}6482,147,483,648 is 111. Equivalently, it holds exactly for 231≤s≤232−12^{31}\le s\le 2^{32}-1231≤s≤232−1; no condition is imposed on the lower 31 bits.

specTimeBased. For any 32-bit sequence vector with unsigned integer value s∈{0,…,232−1}s\in\{0,\ldots,2^{32}-1\}s∈{0,…,232−1}, the proposition defined here holds exactly when the remainder modulo 222 of the integer quotient of sss by 4,194,3044{,}194{,}3044,194,304 is 111. Equivalently, bit 22, with the least significant bit numbered 0, is set; the other bits are unrestricted, including bit 31.

specDelay. For any 32-bit sequence vector with unsigned integer value s∈{0,…,232−1}s\in\{0,\ldots,2^{32}-1\}s∈{0,…,232−1}, this function returns the natural number s mod 65,536s\bmod 65{,}536smod65,536. Its value therefore ranges from 000 through 65,53565{,}53565,535, inclusive, and is unaffected by any of the upper 16 bits.

Decidability instance for specEnabled. For every version vector and flags vector, both of width 32 bits, this declaration supplies a decision of the proposition 2≤v  ∧  f mod 2=12\le v\;\land\;f\bmod 2=12≤v∧fmod2=1, where vvv and fff are the corresponding unsigned integer values. The decision contains either a proof that both conditions hold or a proof that their conjunction does not hold; it does not assert that the conjunction is true for all vectors.

Decidability instance for specDisabled. For every 32-bit sequence vector with unsigned integer value sss, this declaration supplies a decision of the proposition ⌊s/2,147,483,648⌋=1\lfloor s/2{,}147{,}483{,}648\rfloor=1⌊s/2,147,483,648⌋=1. The decision contains either a proof of this equality or a proof that it is false, including all sequence values from 000 through 232−12^{32}-1232−1.

Decidability instance for specTimeBased. For every 32-bit sequence vector with unsigned integer value sss, this declaration supplies a decision of the proposition ⌊s/4,194,304⌋ mod 2=1\lfloor s/4{,}194{,}304\rfloor\bmod 2=1⌊s/4,194,304⌋mod2=1. The decision contains either a proof of this equality or a proof that it is false, with no restriction on the remaining bits of the sequence.

inputSatisfied. Given any context consisting of a natural-number height HHH and a total function M:N→NM:\mathbb N\to\mathbb NM:N→N, and any input consisting of a 32-bit sequence with unsigned value sss and a natural-number coin height ccc, write d=s mod 65,536d=s\bmod 65{,}536d=smod65,536. The defined proposition holds exactly when either ⌊s/2,147,483,648⌋=1\lfloor s/2{,}147{,}483{,}648\rfloor=1⌊s/2,147,483,648⌋=1, or the following selected inequality holds: if ⌊s/4,194,304⌋ mod 2=1\lfloor s/4{,}194{,}304\rfloor\bmod 2=1⌊s/4,194,304⌋mod2=1, the inequality is M(max⁡(c−1,0))+512d≤M(max⁡(H−1,0))M(\max(c-1,0))+512d\le M(\max(H-1,0))M(max(c−1,0))+512d≤M(max(H−1,0)); otherwise it is c+d≤Hc+d\le Hc+d≤H. These are non-strict inequalities in natural-number arithmetic, with no overflow or wrapping. In particular, subtraction of 111 from 000 yields 000, a zero delay is allowed, and the first alternative makes the proposition true regardless of the selected inequality. There is no assumption that HHH is positive, that c≤Hc\le Hc≤H, or that MMM is bounded or monotone.

satisfiesBIP68. Given arbitrary 32-bit version and flags vectors with unsigned values vvv and fff, any context with natural-number height HHH and total function M:N→NM:\mathbb N\to\mathbb NM:N→N, and any finite list of inputs, the defined proposition holds exactly when either 2≤v  ∧  f mod 2=12\le v\;\land\;f\bmod 2=12≤v∧fmod2=1 is false, or every input in the list meets the following condition. For that input's unsigned sequence value sss and natural-number coin height ccc, either ⌊s/2,147,483,648⌋=1\lfloor s/2{,}147{,}483{,}648\rfloor=1⌊s/2,147,483,648⌋=1, or, writing d=s mod 65,536d=s\bmod65{,}536d=smod65,536, the inequality M(max⁡(c−1,0))+512d≤M(max⁡(H−1,0))M(\max(c-1,0))+512d\le M(\max(H-1,0))M(max(c−1,0))+512d≤M(max(H−1,0)) holds when ⌊s/4,194,304⌋ mod 2=1\lfloor s/4{,}194{,}304\rfloor\bmod2=1⌊s/4,194,304⌋mod2=1, and c+d≤Hc+d\le Hc+d≤H holds otherwise. All additions and multiplications are in the unbounded natural numbers and the displayed maxima express subtraction truncated at zero. The empty list makes the universal condition true, and failure of the version-and-flags conjunction makes the entire proposition true for any list. No bound or positivity condition on heights, no bound on the sums, and no monotonicity condition on MMM is included.

expectedHeights. Given arbitrary 32-bit version and flags vectors with unsigned values vvv and fff and any finite list of inputs, this function returns a list of natural numbers of the same length and in the same order. For each input with unsigned 32-bit sequence value sss and natural-number coin height ccc, the corresponding output is chosen to be 000 when both 2≤v  ∧  f mod 2=12\le v\;\land\;f\bmod2=12≤v∧fmod2=1 and ⌊s/2,147,483,648⌋=1\lfloor s/2{,}147{,}483{,}648\rfloor=1⌊s/2,147,483,648⌋=1 hold; otherwise that output is ccc. An empty input list returns an empty list. Repeated inputs remain repeated, coin heights may already be 000, and failure of the version-and-flags conjunction causes every coin height to be copied as given.

admissible. Given any context with natural-number height HHH and total function M:N→NM:\mathbb N\to\mathbb NM:N→N and any finite list of inputs, the defined proposition holds exactly when all four requirements hold: 0<H0<H0<H; H≤2,147,483,647H\le2{,}147{,}483{,}647H≤2,147,483,647; for every natural number hhh, the implication h≤H⇒M(h)≤9,223,372,036,854,775,807h\le H\Rightarrow M(h)\le9{,}223{,}372{,}036{,}854{,}775{,}807h≤H⇒M(h)≤9,223,372,036,854,775,807 holds; and every input in the list has coin height at most HHH. The function bound includes h=0h=0h=0 and h=Hh=Hh=H, and imposes no condition at arguments greater than HHH. Coin heights may be 000, input sequences are unrestricted, and no monotonicity of MMM or bound on a delay-added sum is required. An empty list makes only the requirement on input coin heights vacuous; the three context requirements still apply.

noOverflow. Given arbitrary 32-bit version and flags vectors with unsigned values vvv and fff, any context with natural-number height HHH and total function M:N→NM:\mathbb N\to\mathbb NM:N→N, and any finite list of inputs, the defined proposition requires the following for every input in the list. Let sss be its unsigned sequence value and ccc its natural-number coin height: if 2≤v  ∧  f mod 2=12\le v\;\land\;f\bmod2=12≤v∧fmod2=1 holds and ⌊s/2,147,483,648⌋=1\lfloor s/2{,}147{,}483{,}648\rfloor=1⌊s/2,147,483,648⌋=1 is false, then, writing d=s mod 65,536d=s\bmod65{,}536d=smod65,536, one must have M(max⁡(c−1,0))+512d≤9,223,372,036,854,775,807M(\max(c-1,0))+512d\le9{,}223{,}372{,}036{,}854{,}775{,}807M(max(c−1,0))+512d≤9,223,372,036,854,775,807 when ⌊s/4,194,304⌋ mod 2=1\lfloor s/4{,}194{,}304\rfloor\bmod2=1⌊s/4,194,304⌋mod2=1, and c+d≤2,147,483,647c+d\le2{,}147{,}483{,}647c+d≤2,147,483,647 otherwise. All arithmetic is in the unbounded natural numbers, and c=0c=0c=0 makes the function argument 000. The proposition is true for an empty list, imposes no requirement on an input whose sequence satisfies the excluded equality, and is true for every list if the version-and-flags conjunction fails. It includes no condition on HHH, no separate requirement that c≤Hc\le Hc≤H, and no bounds or monotonicity for MMM beyond the stated conditional bounds on these sums.

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