Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

CompactSize round-trips

Proved
BitcoinSer.compactSize_roundtrip

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

bitcoinbitcoin-mainnetconsensusformal-verificationgenesismerkleserializationsha256

For all n<264n < 2^{64}n<264 and rrr: readCompactSize(false,writeCompactSize(n)++r)=some(n,r)\mathrm{readCompactSize}(\mathtt{false}, \mathrm{writeCompactSize}(n) ++ r) = \mathrm{some}(n, r)readCompactSize(false,writeCompactSize(n)++r)=some(n,r) — the unchecked reader accepts every encoding the writer produces, in all four width classes.

Preamble
import Definitions.Def_BitcoinSer
Formal statement
theorem BitcoinSer.compactSize_roundtrip (n : Nat) (rest : Bytes) (h : n < 2 ^ 64) :
    BitcoinSer.readCompactSize false (BitcoinSer.writeCompactSize n ++ rest) = some (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_roundtrip

Binders and hypothesis. A natural number nnn, a byte string rest\texttt{rest}rest (arbitrary, possibly empty), and the hypothesis

h:n<264.h : n < 2^{64}.h:n<264.

Conclusion. Reading a CompactSize without range check from the encoding of nnn followed by rest\texttt{rest}rest succeeds and yields nnn and rest\texttt{rest}rest:

readCompactSize  false  (writeCompactSize  n+ ⁣ ⁣+rest)=some (n,rest).\texttt{readCompactSize}\;\mathrm{false}\;\big(\texttt{writeCompactSize}\;n \mathbin{+\!\!+} \texttt{rest}\big) = \mathrm{some}\,(n, \texttt{rest}).readCompactSizefalse(writeCompactSizen++rest)=some(n,rest).

The first argument of the reader is the Boolean false, i.e. the MAX_SIZE\texttt{MAX\_SIZE}MAX_SIZE bound is not enforced in this statement.

Unfolding the encoder. writeCompactSize  n\texttt{writeCompactSize}\;nwriteCompactSizen is: the single byte nnn if n<253n < 253n<253; the byte 253253253 followed by 2 little-endian bytes of nnn if 253≤n≤0xffff253 \le n \le \mathrm{0xffff}253≤n≤0xffff; the byte 254254254 followed by 4 little-endian bytes if 0xffff<n≤0xffffffff\mathrm{0xffff} < n \le \mathrm{0xffffffff}0xffff<n≤0xffffffff; and the byte 255255255 followed by 8 little-endian bytes otherwise. Under n<264n < 2^{64}n<264 the 8-byte case does not truncate.

Unfolding the decoder. readCompactSize  false  s\texttt{readCompactSize}\;\mathrm{false}\;sreadCompactSizefalses fails on empty sss; otherwise it inspects the first byte ccc: if c<253c < 253c<253 the value is ccc; if c=253c = 253c=253 it reads 2 bytes as vvv and fails if v<253v < 253v<253; if c=254c = 254c=254 it reads 4 bytes and fails if v<0x10000v < \mathrm{0x10000}v<0x10000; if c=255c = 255c=255 it reads 8 bytes and fails if v<0x100000000v < \mathrm{0x100000000}v<0x100000000; a short read in any of these fails. With the Boolean false the final range test is skipped, so the provisional result is returned as is. The theorem thus asserts, for every n<264n < 2^{64}n<264, that the prefix byte chosen by the encoder leads the decoder into the matching branch, that the fixed-width payload decodes back to nnn, that nnn passes the corresponding canonicality threshold (which holds because the encoder chose the shortest form), and that the remaining bytes are exactly rest\texttt{rest}rest.

Boundary cases included by the quantifier: n=0n = 0n=0 (one zero byte), n=252n = 252n=252 (one byte), n=253n = 253n=253 (three bytes, value exactly at the lower canonical threshold), n=0xffffn = \mathrm{0xffff}n=0xffff and n=0x10000n = \mathrm{0x10000}n=0x10000 (switch from 2 to 4 bytes), n=0xffffffffn = \mathrm{0xffffffff}n=0xffffffff and n=232n = 2^{32}n=232 (switch to 8 bytes), and n=264−1n = 2^{64} - 1n=264−1. Values above MAX_SIZE=225\texttt{MAX\_SIZE} = 2^{25}MAX_SIZE=225 are included, since no range check is applied.

What is not said. Nothing is asserted for the range-checked reader (rc=truerc = \mathrm{true}rc=true): for MAX_SIZE<n<264\texttt{MAX\_SIZE} < n < 2^{64}MAX_SIZE<n<264 that reader returns no result, and the theorem is silent on it, while for n≤MAX_SIZEn \le \texttt{MAX\_SIZE}n≤MAX_SIZE the range-checked result would agree but this is not stated. Nothing is asserted for n≥264n \ge 2^{64}n≥264, where the encoder truncates to n mod 264n \bmod 2^{64}nmod264 and the decoder may either return the truncated value or fail the canonicality check. The converse ("every successful read comes from the canonical encoding") is a separate statement, compactSize_canonical. The theorem does not state the length of the encoding, nor that the decoder fails on malformed input. It is the one-directional round trip, for the unchecked reader only, under n<264n < 2^{64}n<264.

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