Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The serializer always produces a minimal encoding

Proved
BitcoinScript.serialize_minimal

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

bitcoinbitcoin-mainnetconsensuscscriptnumformal-verificationinterpreterscript

For every integer nnn, nonMinimal(serialize(n))=false\mathrm{nonMinimal}(\mathrm{serialize}(n)) = \mathtt{false}nonMinimal(serialize(n))=false: the output of CScriptNum::serialize never has a final byte without value bits that the previous byte could absorb. Consequently the interpreter's own numeric results always pass the MINIMALDATA test.

Preamble
import Definitions.Def_BitcoinScript
Formal statement
theorem BitcoinScript.serialize_minimal (n : Int) : BitcoinScript.nonMinimal (BitcoinScript.serialize n) = false := 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.serialize_minimal

Binders and hypothesis. One universally quantified variable nnn, an integer (of either sign, any magnitude, including 000). No hypotheses.

Conclusion. The Boolean

nonMinimal(serialize(n))\mathrm{nonMinimal}\big(\mathrm{serialize}(n)\big)nonMinimal(serialize(n))

is equal to false. Since nonMinimal returns true to signal a non-minimal encoding, the claim is: the byte list produced by serialize from any integer is never flagged as non-minimal by nonMinimal.

Unfolding serialize. For n=0n = 0n=0, serialize(0)=[]\mathrm{serialize}(0) = []serialize(0)=[]. For n≠0n \neq 0n=0: let mag:=natBytes(∣n∣)\mathit{mag} := \mathrm{natBytes}(|n|)mag:=natBytes(∣n∣), the little-endian bytes of the absolute value with no trailing zero bytes (so mag\mathit{mag}mag is non-empty and its last byte is non-zero). If the last byte of mag\mathit{mag}mag has bit 0x80\mathtt{0x80}0x80 set, the output is mag\mathit{mag}mag followed by one extra byte, 0x80\mathtt{0x80}0x80 when n<0n < 0n<0 and 0x00\mathtt{0x00}0x00 when n>0n > 0n>0. Otherwise, the output is mag\mathit{mag}mag with bit 0x80\mathtt{0x80}0x80 set on its last byte when n<0n < 0n<0, and mag\mathit{mag}mag itself when n>0n > 0n>0.

Unfolding nonMinimal. Given a byte list vvv: if v=[]v = []v=[], the result is false. Otherwise let last\mathit{last}last be the final byte and consider the byte prev\mathit{prev}prev before it, if any. The result is

((last & 0x7f)=0) ∧ (no prev exists  ∨  (prev & 0x80)=0).\big((\mathit{last} \,\&\, \mathtt{0x7f}) = 0\big)\ \wedge\ \big(\text{no } \mathit{prev} \text{ exists}\ \ \vee\ \ (\mathit{prev} \,\&\, \mathtt{0x80}) = 0\big).((last&0x7f)=0) ∧ (no prev exists  ∨  (prev&0x80)=0).

That is, vvv is "non-minimal" when the last byte is 0x00\mathtt{0x00}0x00 or 0x80\mathtt{0x80}0x80 and either vvv has length one or the preceding byte has its top bit clear.

The claim, case by case (as the code determines it). The theorem asserts that for every integer nnn, the output of serialize falls outside the "non-minimal" pattern:

  • n=0n = 0n=0: the output is [][][], on which nonMinimal is false by its first clause.
  • n≠0n \neq 0n=0 with no extra byte appended: the last byte is the last byte of mag\mathit{mag}mag (non-zero, top bit clear), possibly with its top bit set by setTop; in either case its low seven bits are non-zero, so the first conjunct fails.
  • n≠0n \neq 0n=0 with an extra byte 0x00\mathtt{0x00}0x00 or 0x80\mathtt{0x80}0x80 appended: the last byte has zero low bits, so the first conjunct holds, and the claim is that the second conjunct fails: the preceding byte (the last byte of mag\mathit{mag}mag) has its top bit set. The theorem states the conclusion for all nnn at once; the above is merely the shape the definitions give it.

Edge cases included. n=0n = 0n=0; n=±1n = \pm 1n=±1 (one byte, [0x01][\mathtt{0x01}][0x01] and [0x81][\mathtt{0x81}][0x81]); n=±127n = \pm 127n=±127; n=±128n = \pm 128n=±128 (two bytes with an appended sign/padding byte); n=±255n = \pm 255n=±255, ±256\pm 256±256; arbitrarily large magnitudes (there is no bound on ∣n∣|n|∣n∣ and the output may be arbitrarily long — longer than the 4- and 5-byte limits that toNum enforces elsewhere).

What is not said. The theorem does not say that serialize produces the shortest encoding in any sense other than the specific predicate nonMinimal; it does not say that serialize is injective, nor that setVch(serialize(n))=n\mathrm{setVch}(\mathrm{serialize}(n)) = nsetVch(serialize(n))=n (that is a separate theorem in this bundle). It does not say anything about nonMinimal on lists that are not in the image of serialize, nor that every list on which nonMinimal is false is in the image of serialize (e.g. nothing is claimed about [0x80,0x00][\mathtt{0x80},\mathtt{0x00}][0x80,0x00] versus [0x80,0x80][\mathtt{0x80},\mathtt{0x80}][0x80,0x80] beyond what serialize produces). It does not bound the length of serialize(n)\mathrm{serialize}(n)serialize(n), and so says nothing about whether toNum with its size limit would accept the result. It does not involve toNum's requireMinimal flag directly, 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