Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A fixed-width encoding has its width

Proved
BitcoinSer.leBytes_length

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

bitcoinbitcoin-mainnetconsensusformal-verificationgenesismerkleserializationsha256

For all k,nk, nk,n: ∣leBytes(k,n)∣=k|\mathrm{leBytes}(k, n)| = k∣leBytes(k,n)∣=k.

Preamble
import Definitions.Def_BitcoinSer
Formal statement
theorem BitcoinSer.leBytes_length (k n : Nat) : (BitcoinSer.leBytes k n).length = k := 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.leBytes_length

Binders and hypothesis. Two natural numbers kkk and nnn are universally quantified, with no restriction whatsoever on either: kkk may be 000, and nnn may be any natural number, including values at or above 28k2^{8k}28k. There are no hypotheses.

Conclusion. The byte string leBytes  k  n\texttt{leBytes}\;k\;nleByteskn has length exactly kkk:

∣leBytes  k  n∣=k.|\texttt{leBytes}\;k\;n| = k .∣leByteskn∣=k.

Unfolding. leBytes\texttt{leBytes}leBytes is the little-endian fixed-width encoder from the definitions file: for k=0k = 0k=0 it returns the empty list; for k+1k + 1k+1 it returns the single byte n mod 256n \bmod 256nmod256 followed by leBytes  k  ⌊n/256⌋\texttt{leBytes}\;k\;\lfloor n / 256 \rfloorleBytesk⌊n/256⌋. The statement therefore says that this recursion produces one byte per unit of kkk, regardless of the value being encoded. In particular:

  • for k=0k = 0k=0 the claim is that the empty list has length 000;
  • for n≥28kn \ge 2^{8k}n≥28k the encoder truncates nnn modulo 28k2^{8k}28k (the discarded high bits do not add bytes), and the claim is still that exactly kkk bytes come out;
  • for n=0n = 0n=0 the result is kkk zero bytes, of length kkk.

Because ser8\texttt{ser8}ser8, ser16\texttt{ser16}ser16, ser32\texttt{ser32}ser32, ser64\texttt{ser64}ser64 are defined as leBytes\texttt{leBytes}leBytes with k=1,2,4,8k = 1, 2, 4, 8k=1,2,4,8, and beBytes  k  n\texttt{beBytes}\;k\;nbeByteskn is the reversal of leBytes  k  n\texttt{leBytes}\;k\;nleByteskn, the statement entails (though it does not itself state) that those encoders produce 1,2,4,81, 2, 4, 81,2,4,8 bytes and that beBytes  k  n\texttt{beBytes}\;k\;nbeByteskn has length kkk. Likewise serInt64\texttt{serInt64}serInt64 and serInt32\texttt{serInt32}serInt32 are leBytes\texttt{leBytes}leBytes with k=8,4k = 8, 4k=8,4 applied to a reduced natural number, so they would have lengths 8 and 4; again, this is a consequence, not the statement.

What is not said. The theorem says nothing about the content of the bytes: it does not say the value decodes back to nnn (that is the separate statement readLE_leBytes, which carries the hypothesis n<28kn < 2^{8k}n<28k), and it does not say what happens to the high bits of an over-large nnn beyond the fact that the length is unaffected. It does not state that leVal  (leBytes  k  n)=n mod 28k\texttt{leVal}\;(\texttt{leBytes}\;k\;n) = n \bmod 2^{8k}leVal(leByteskn)=nmod28k, nor anything about beBytes\texttt{beBytes}beBytes, ser32\texttt{ser32}ser32, etc. by name. It does not assert injectivity of leBytes  k\texttt{leBytes}\;kleBytesk on [0,28k)[0, 2^{8k})[0,28k), nor that two different nnn below 28k2^{8k}28k encode differently. It is purely a length statement for all k,n∈Nk, n \in \mathbb{N}k,n∈N.

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