Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A serialized number of at most four bytes is accepted strictly and reads back

Proved
BitcoinScript.toNum_serialize

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

bitcoinbitcoin-mainnetconsensuscscriptnumformal-verificationinterpreterscript

For every integer nnn whose serialization has at most four bytes, toNum(true,4,serialize(n))=some n\mathrm{toNum}(\mathtt{true}, 4, \mathrm{serialize}(n)) = \mathrm{some}\ ntoNum(true,4,serialize(n))=some n: the strict (fRequireMinimal) four-byte constructor accepts the serializer's output and returns the original value.

Preamble
import Definitions.Def_BitcoinScript
Formal statement
theorem BitcoinScript.toNum_serialize (n : Int) (h : (BitcoinScript.serialize n).length ≤ 4) :
    BitcoinScript.toNum true 4 (BitcoinScript.serialize n) = some n := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: CastToBool (lines 46-59), EvalScript (417-1249), EvalChecksigPreTapscript, VerifyScript (2012-2110), src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; CScriptNum (227-382), opcodetype, MAX_SCRIPT_ELEMENT_SIZE, MAX_OPS_PER_SCRIPT, MAX_PUBKEYS_PER_MULTISIG, MAX_STACK_SIZE, src/script/script.h; GetScriptOp, IsPushOnly, IsPayToScriptHash, src/script/script.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/script.h
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: BitcoinScript.toNum_serialize

Binders and hypothesis. One universally quantified integer nnn. One hypothesis, named hhh:

∣serialize(n)∣≤4,\big|\mathrm{serialize}(n)\big| \le 4,​serialize(n)​≤4,

i.e. the byte list produced by serialize from nnn has length at most 444 (lengths 0,1,2,3,40,1,2,3,40,1,2,3,4 are all allowed).

Conclusion. An equation between optional integers:

toNum(true, 4, serialize(n))=some(n).\mathrm{toNum}(\text{true},\ 4,\ \mathrm{serialize}(n)) = \mathrm{some}(n).toNum(true, 4, serialize(n))=some(n).

That is, parsing the encoding of nnn with the minimal-encoding requirement switched on and a size limit of 444 bytes succeeds (does not return "no value") and yields exactly nnn.

Unfolding toNum. toNum(requireMinimal,maxSize,v)\mathrm{toNum}(\mathit{requireMinimal}, \mathit{maxSize}, v)toNum(requireMinimal,maxSize,v) returns:

  • "no value" if maxSize<∣v∣\mathit{maxSize} < |v|maxSize<∣v∣;
  • otherwise "no value" if requireMinimal\mathit{requireMinimal}requireMinimal is true, vvv is non-empty, and nonMinimal(v)\mathrm{nonMinimal}(v)nonMinimal(v) is true;
  • otherwise some(setVch(v))\mathrm{some}(\mathrm{setVch}(v))some(setVch(v)).

With requireMinimal=true\mathit{requireMinimal} = \text{true}requireMinimal=true, maxSize=4\mathit{maxSize} = 4maxSize=4 and v=serialize(n)v = \mathrm{serialize}(n)v=serialize(n), the conclusion therefore unfolds to the conjunction of three facts: (i) ¬(4<∣serialize(n)∣)\neg(4 < |\mathrm{serialize}(n)|)¬(4<∣serialize(n)∣), which is exactly the hypothesis hhh; (ii) it is not the case that serialize(n)\mathrm{serialize}(n)serialize(n) is non-empty and nonMinimal(serialize(n))\mathrm{nonMinimal}(\mathrm{serialize}(n))nonMinimal(serialize(n)) is true; and (iii) setVch(serialize(n))=n\mathrm{setVch}(\mathrm{serialize}(n)) = nsetVch(serialize(n))=n. Facts (ii) and (iii) are, respectively, the content of the separate theorems serialize_minimal and serialize_roundtrip in this bundle, but the present statement does not refer to them; it asserts the combined equation directly.

Unfolding serialize, nonMinimal, setVch. serialize(0)=[]\mathrm{serialize}(0) = []serialize(0)=[]; for n≠0n \ne 0n=0 it is the little-endian magnitude bytes of ∣n∣|n|∣n∣ without trailing zeros, with the sign carried in bit 0x80\mathtt{0x80}0x80 of the last byte, adding an extra byte (0x80\mathtt{0x80}0x80 for negative, 0x00\mathtt{0x00}0x00 for positive) when the last magnitude byte already has that bit set. nonMinimal(v)\mathrm{nonMinimal}(v)nonMinimal(v) is true when vvv is non-empty, its last byte is 0x00\mathtt{0x00}0x00 or 0x80\mathtt{0x80}0x80, and either ∣v∣=1|v| = 1∣v∣=1 or the second-to-last byte has its top bit clear. setVch(v)\mathrm{setVch}(v)setVch(v) is −leNat(clearTop(v))-\mathrm{leNat}(\mathrm{clearTop}(v))−leNat(clearTop(v)) if the last byte's top bit is set and leNat(v)\mathrm{leNat}(v)leNat(v) otherwise, with leNat\mathrm{leNat}leNat the little-endian unsigned value.

What the hypothesis amounts to. By the definition of serialize, the output length is at most 444 exactly when ∣n∣≤231−1|n| \le 2^{31} - 1∣n∣≤231−1: the magnitude 231−12^{31}-1231−1 encodes as [0xff,0xff,0xff,0x7f][\mathtt{0xff},\mathtt{0xff},\mathtt{0xff},\mathtt{0x7f}][0xff,0xff,0xff,0x7f] (4 bytes), while 2312^{31}231 needs [0x00,0x00,0x00,0x80][\mathtt{0x00},\mathtt{0x00},\mathtt{0x00},\mathtt{0x80}][0x00,0x00,0x00,0x80] plus a fifth padding byte. So the theorem is about the integers nnn with −(231−1)≤n≤231−1-(2^{31}-1) \le n \le 2^{31}-1−(231−1)≤n≤231−1, including 000 (whose encoding is empty and is accepted by toNum because the minimality test is skipped for the empty list, and whose value is setVch([])=0\mathrm{setVch}([]) = 0setVch([])=0).

Edge cases. n=0n = 0n=0 (empty encoding, length 0≤40 \le 40≤4). n=±(231−1)n = \pm(2^{31}-1)n=±(231−1), the largest magnitudes allowed. n=±128n = \pm 128n=±128, ±32768\pm 32768±32768, ±8388608\pm 8388608±8388608 — values whose magnitude bytes end in a byte with the top bit set and so receive a padding byte; for these the length constraint bites one power of 256 earlier than one might expect from the magnitude alone.

What is not said. Nothing is claimed for integers whose encoding exceeds 4 bytes (e.g. n=231n = 2^{31}n=231 or n=−231n = -2^{31}n=−231): the theorem is silent, not negative, about them. Nothing is claimed about toNum with other size limits (such as the 5-byte limit used by CHECKLOCKTIMEVERIFY/CHECKSEQUENCEVERIFY in execOp) or with requireMinimal = false (the setting every arithmetic opcode in execOp actually uses). Nothing is claimed about toNum applied to byte lists not produced by serialize, in particular about whether non-minimal lists such as [0x01,0x00][\mathtt{0x01},\mathtt{0x00}][0x01,0x00] or [0x80][\mathtt{0x80}][0x80] are rejected. The theorem does not say that serialize(n)\mathrm{serialize}(n)serialize(n) is the only 4-byte-or-shorter list that toNum maps to nnn. It does not mention the interpreter, flags, or the oracle.

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