BIP68 input data, declarative eligibility, and arithmetic domain
DefinitionBIP68_ModelAn input consists of an unsigned 32-bit sequence word and a natural-number coin height . A context consists of a natural-number candidate height and a total function supplying median times. Put , , and let and be the tests for bits 31 and 22, expressed by quotient and remainder. Enforcement means that the unsigned version is at least two and the flags value is odd. A single input satisfies its delay when
The transaction-level predicate holds when is false or every input satisfies that condition. The expected output height list replaces an input height by zero exactly when and both hold, preserving order and repetitions.
The admissible-context predicate requires , every input height at most , and for all . A separate no-overflow predicate requires the selected pre-subtraction sum to be at most for an enforced height input, or 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.
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
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 through , inclusive; the coin height can be any natural number, including , 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 that is a natural number and a total function . The height may be , 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 .
int64Max. This natural-number constant is defined to be .
specEnabled. For any two 32-bit vectors called version and flags, let and be their unsigned integer values, each between and , inclusive. The proposition defined here holds exactly when and the remainder of on division by is . 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 , the proposition defined here holds exactly when the integer quotient of by is . Equivalently, it holds exactly for ; no condition is imposed on the lower 31 bits.
specTimeBased. For any 32-bit sequence vector with unsigned integer value , the proposition defined here holds exactly when the remainder modulo of the integer quotient of by is . 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 , this function returns the natural number . Its value therefore ranges from through , 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 , where and 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 , this declaration supplies a decision of the proposition . The decision contains either a proof of this equality or a proof that it is false, including all sequence values from through .
Decidability instance for specTimeBased. For every 32-bit sequence vector with unsigned integer value , this declaration supplies a decision of the proposition . 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 and a total function , and any input consisting of a 32-bit sequence with unsigned value and a natural-number coin height , write . The defined proposition holds exactly when either , or the following selected inequality holds: if , the inequality is ; otherwise it is . These are non-strict inequalities in natural-number arithmetic, with no overflow or wrapping. In particular, subtraction of from yields , a zero delay is allowed, and the first alternative makes the proposition true regardless of the selected inequality. There is no assumption that is positive, that , or that is bounded or monotone.
satisfiesBIP68. Given arbitrary 32-bit version and flags vectors with unsigned values and , any context with natural-number height and total function , and any finite list of inputs, the defined proposition holds exactly when either is false, or every input in the list meets the following condition. For that input's unsigned sequence value and natural-number coin height , either , or, writing , the inequality holds when , and 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 is included.
expectedHeights. Given arbitrary 32-bit version and flags vectors with unsigned values and 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 and natural-number coin height , the corresponding output is chosen to be when both and hold; otherwise that output is . An empty input list returns an empty list. Repeated inputs remain repeated, coin heights may already be , 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 and total function and any finite list of inputs, the defined proposition holds exactly when all four requirements hold: ; ; for every natural number , the implication holds; and every input in the list has coin height at most . The function bound includes and , and imposes no condition at arguments greater than . Coin heights may be , input sequences are unrestricted, and no monotonicity of 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 and , any context with natural-number height and total function , and any finite list of inputs, the defined proposition requires the following for every input in the list. Let be its unsigned sequence value and its natural-number coin height: if holds and is false, then, writing , one must have when , and otherwise. All arithmetic is in the unbounded natural numbers, and makes the function argument . 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 , no separate requirement that , and no bounds or monotonicity for beyond the stated conditional bounds on these sums.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.