Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A script number below 2^(8k) in magnitude serializes to at most k + 1 bytes

Proved
BitcoinToLocal.serialize_length

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

bip112bitcoinbitcoin-mainnetbolt3csvformal-verificationlightningp2wshscript

For an integer nnn and kkk with ∣n∣<256k|n| < 256^k∣n∣<256k: (serialize n).length ≤ k + 1. In particular a delay below 2322^{32}232 fits the 5-byte limit of OP_CHECKSEQUENCEVERIFY.

Preamble
import Definitions.Def_BitcoinToLocal
import Definitions.Def_BitcoinScript
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinToLocal.serialize_length (n : Int) (k : Nat) (h : n.natAbs < 256 ^ k) :
    (BitcoinScript.serialize n).length ≤ k + 1 := by sorry
Source
BOLT #3, Bitcoin Transaction and Script Formats, 'to_local Output': https://github.com/lightning/bolts/blob/master/03-transactions.md#to_local-output; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: EvalScript (OP_IF/OP_ELSE/OP_ENDIF, OP_CHECKSEQUENCEVERIFY, OP_CHECKSIG), GenericTransactionSignatureChecker::CheckSequence, ExecuteWitnessScript, VerifyWitnessProgram (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); CScript::operator<<(int64_t) (script/script.h); BIP68, BIP112, BIP141
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: BitcoinToLocal.serialize_length

Statement. For every integer nnn and every natural number kkk such that

∣n∣<256k|n| < 256^{k}∣n∣<256k

(where ∣n∣|n|∣n∣ is the absolute value of nnn taken as a natural number), the byte string serialize(n)\mathrm{serialize}(n)serialize(n) has length at most k+1k + 1k+1:

∣serialize(n)∣≤k+1.\big|\mathrm{serialize}(n)\big| \le k + 1 .​serialize(n)​≤k+1.

The function serialize. It is the script-number encoding Z→\mathbb{Z} \toZ→ byte strings defined as follows.

  • serialize(0)=[ ]\mathrm{serialize}(0) = [\,]serialize(0)=[], the empty byte string.
  • For n≠0n \ne 0n=0: let mmm be the list of base-256256256 digits of ∣n∣|n|∣n∣ in little-endian order with no trailing zero bytes (the digit list is produced by repeatedly taking the remainder and quotient by 256256256 until the value is 000, so mmm is non-empty with non-zero last byte). Let neg\mathrm{neg}neg be the truth of n<0n < 0n<0.
    • If the last byte of mmm has its 0x80\mathtt{0x80}0x80 bit set, the result is mmm followed by one extra byte: 0x80\mathtt{0x80}0x80 if neg\mathrm{neg}neg, and 0x00\mathtt{0x00}0x00 otherwise.
    • Otherwise, if neg\mathrm{neg}neg, the result is mmm with the 0x80\mathtt{0x80}0x80 bit set on its last byte.
    • Otherwise the result is mmm itself.

Edge cases. For k=0k = 0k=0 the hypothesis reads ∣n∣<1|n| < 1∣n∣<1, which forces n=0n = 0n=0, and the conclusion is 0≤10 \le 10≤1. For k≥1k \ge 1k≥1 the hypothesis admits negative nnn with ∣n∣≤256k−1|n| \le 256^{k} - 1∣n∣≤256k−1, and the conclusion allows the encoding to be one byte longer than kkk (accounting for a possible extra sign byte). The theorem bounds the length only from above; it says nothing about a lower bound or about the content of the bytes.

Human review
  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 29, 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