Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

ReadCompactSize accepts only canonical encodings

Proved
BitcoinSer.compactSize_canonical

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

bitcoinbitcoin-mainnetconsensusformal-verificationgenesismerkleserializationsha256

For every mode, byte list bbb, value nnn and remainder rrr: if readCompactSize(b)=some(n,r)\mathrm{readCompactSize}(b) = \mathrm{some}(n, r)readCompactSize(b)=some(n,r) then b=writeCompactSize(n)++rb = \mathrm{writeCompactSize}(n) ++ rb=writeCompactSize(n)++r. The reader is injective on encodings: a value has exactly one accepted encoding, so a CompactSize can never be padded to a longer form.

Preamble
import Definitions.Def_BitcoinSer
Formal statement
theorem BitcoinSer.compactSize_canonical (rc : Bool) (b : Bytes) (n : Nat) (rest : Bytes)
    (h : BitcoinSer.readCompactSize rc b = some (n, rest)) : b = BitcoinSer.writeCompactSize n ++ rest := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: WriteCompactSize/ReadCompactSize and vector serialization, src/serialize.h: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/serialize.h; SerializeTransaction/UnserializeTransaction, COutPoint, CTxIn, CTxOut, ComputeHash, ComputeWitnessHash, src/primitives/transaction.h and transaction.cpp; CBlockHeader, CBlock, GetHash, src/primitives/block.h and block.cpp; Hash, Hash160, src/hash.h; CSHA256, src/crypto/sha256.cpp; CRIPEMD160, src/crypto/ripemd160.cpp; CSHA1, src/crypto/sha1.cpp; GetTransactionWeight/GetBlockWeight, src/consensus/validation.h; WITNESS_SCALE_FACTOR, MAX_BLOCK_WEIGHT, src/consensus/consensus.h; CreateGenesisBlock and hashGenesisBlock, src/kernel/chainparams.cpp
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: BitcoinSer.compactSize_canonical

Binders and hypothesis. A Boolean rcrcrc (the range-check flag, either value), a byte string bbb, a natural number nnn, a byte string rest\texttt{rest}rest, and the single hypothesis

h:readCompactSize  rc  b=some (n,rest),h : \texttt{readCompactSize}\;rc\;b = \mathrm{some}\,(n, \texttt{rest}),h:readCompactSizercb=some(n,rest),

i.e. the CompactSize reader with flag rcrcrc, applied to bbb, succeeds and returns the value nnn with unconsumed remainder rest\texttt{rest}rest.

Conclusion. The input is exactly the canonical encoding of nnn followed by the remainder:

b=writeCompactSize  n+ ⁣ ⁣+rest.b = \texttt{writeCompactSize}\;n \mathbin{+\!\!+} \texttt{rest}.b=writeCompactSizen++rest.

Unfolding. The reader, on a non-empty bbb with first byte ccc, returns ccc itself when c<253c < 253c<253; when c=253c = 253c=253 it decodes the next 2 bytes little-endian as vvv and succeeds only if v≥253v \ge 253v≥253; when c=254c = 254c=254 it decodes 4 bytes and succeeds only if v≥0x10000v \ge \mathrm{0x10000}v≥0x10000; when c=255c = 255c=255 it decodes 8 bytes and succeeds only if v≥0x100000000v \ge \mathrm{0x100000000}v≥0x100000000. If rcrcrc is true it additionally fails when MAX_SIZE<v\texttt{MAX\_SIZE} < vMAX_SIZE<v. Any short read fails. So the hypothesis tells us that bbb has one of four shapes with the value in the right band for its prefix. The encoder writeCompactSize  n\texttt{writeCompactSize}\;nwriteCompactSizen chooses: one byte when n<253n < 253n<253; prefix 253253253 plus 2 bytes when n≤0xffffn \le \mathrm{0xffff}n≤0xffff; prefix 254254254 plus 4 bytes when n≤0xffffffffn \le \mathrm{0xffffffff}n≤0xffffffff; prefix 255255255 plus 8 bytes otherwise. The conclusion asserts that the band the reader accepted is exactly the band the encoder would choose for nnn (this is where the reader's strict lower-threshold rejections matter: a value v<253v < 253v<253 under prefix 253253253, for example, is never accepted, so the equation never has to hold for such a bbb), and that re-encoding the decoded value as kkk little-endian bytes reproduces the very bytes that were read (which holds because the decoded value is below 28k2^{8k}28k for a kkk-byte payload). Together with rest\texttt{rest}rest being the tail after those bytes, bbb is reconstructed exactly.

Both values of rcrcrc are covered: when rcrcrc is true the hypothesis is stronger (it also gives n≤MAX_SIZEn \le \texttt{MAX\_SIZE}n≤MAX_SIZE) and the conclusion is the same; when rcrcrc is false, nnn can be any value below 2642^{64}264 that the reader accepts. The statement is uniform in rcrcrc.

What is not said. The theorem does not say that the reader succeeds on any input; it is conditional on success. It does not say what nnn is bounded by (that is compactSize_range), and it does not say that the encoding of nnn is readable (that is compactSize_roundtrip). It does not say the reader fails on non-canonical encodings — that is a consequence of the definition that this statement uses but does not assert. It says nothing about the length of writeCompactSize  n\texttt{writeCompactSize}\;nwriteCompactSizen. Finally, it concerns only readCompactSize\texttt{readCompactSize}readCompactSize itself, not readList\texttt{readList}readList or readBytes\texttt{readBytes}readBytes, which call it with the flag fixed to true.

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