Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Blocks round-trip

Proved
BitcoinSer.block_roundtrip

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

bitcoinbitcoin-mainnetconsensusformal-verificationgenesismerkleserializationsha256

For every well-formed block bbb, witness mode awawaw and remainder rrr:

readBlock(aw,serBlock(aw,b)++r)=some(⟨b.header, b.vtx mapped by (if aw then id else stripWitness)⟩, r).\mathrm{readBlock}(aw, \mathrm{serBlock}(aw, b) ++ r) = \mathrm{some}\big(\langle b.\mathrm{header},\ b.\mathrm{vtx}\text{ mapped by (if } aw \text{ then id else stripWitness)}\rangle,\ r\big).readBlock(aw,serBlock(aw,b)++r)=some(⟨b.header, b.vtx mapped by (if aw then id else stripWitness)⟩, r).

Deserialization is a left inverse of serialization on well-formed blocks in both formats: a block read back from its own bytes is the block (with witnesses, in the witness-aware reader; without, in the legacy one). This is the "interpretation of serialized data" that every hash commitment — merkle root, block hash, txid — refers to.

Formalization Note. Well-formedness is the field-range predicate of the definition (32-bit fields, 32-byte hashes, 64-bit amounts, vector lengths at most MAX_SIZE\mathrm{MAX\_SIZE}MAX_SIZE, every transaction with an input or a witness); the last condition reflects the dummy-vin reinterpretation of the source.

Preamble
import Definitions.Def_BitcoinSer
Formal statement
theorem BitcoinSer.block_roundtrip (aw : Bool) (b : Block) (rest : Bytes) (hw : b.wf) :
    BitcoinSer.readBlock aw (BitcoinSer.serBlock aw b ++ rest) =
      some (⟨b.header, b.vtx.map (fun tx => if aw then tx else tx.stripWitness)⟩, 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.block_roundtrip

Binders and hypothesis. A Boolean awawaw (either value), a block record bbb (a header and a list b.vtxb.\texttt{vtx}b.vtx of transactions), a byte string rest\texttt{rest}rest (arbitrary), and the hypothesis hw:b.wfhw : b.\texttt{wf}hw:b.wf, which unfolds to:

  • b.headerb.\texttt{header}b.header is well-formed: −231≤version<231-2^{31} \le \texttt{version} < 2^{31}−231≤version<231, ∣prevBlock∣=32|\texttt{prevBlock}| = 32∣prevBlock∣=32, ∣merkleRoot∣=32|\texttt{merkleRoot}| = 32∣merkleRoot∣=32, time,bits,nonce<232\texttt{time}, \texttt{bits}, \texttt{nonce} < 2^{32}time,bits,nonce<232;
  • ∣b.vtx∣≤MAX_SIZE|b.\texttt{vtx}| \le \texttt{MAX\_SIZE}∣b.vtx∣≤MAX_SIZE (with MAX_SIZE=225\texttt{MAX\_SIZE} = 2^{25}MAX_SIZE=225, equality allowed);
  • for every txtxtx in b.vtxb.\texttt{vtx}b.vtx: tx.wftx.\texttt{wf}tx.wf (version and lock time <232< 2^{32}<232; input and output counts ≤MAX_SIZE\le \texttt{MAX\_SIZE}≤MAX_SIZE; each input has a 32-byte outpoint hash, index and sequence <232< 2^{32}<232, script length ≤MAX_SIZE\le \texttt{MAX\_SIZE}≤MAX_SIZE, at most MAX_SIZE\texttt{MAX\_SIZE}MAX_SIZE witness items each of length ≤MAX_SIZE\le \texttt{MAX\_SIZE}≤MAX_SIZE; each output has value in [−263,263)[-2^{63}, 2^{63})[−263,263) and script length ≤MAX_SIZE\le \texttt{MAX\_SIZE}≤MAX_SIZE) and (tx.vin≠[ ]tx.\texttt{vin} \ne [\,]tx.vin=[] or hasWitness(tx)=true\texttt{hasWitness}(tx) = \mathrm{true}hasWitness(tx)=true). The second disjunct implies the first (a non-empty witness lives on some input), so this says every transaction in the block has at least one input — and this is demanded for both values of awawaw.

Conclusion.

readBlock  aw  (serBlock  aw  b+ ⁣ ⁣+rest)=some (⟨b.header, map  (tx↦if aw then tx else stripWitness  tx)  b.vtx⟩, rest).\texttt{readBlock}\;aw\;\big(\texttt{serBlock}\;aw\;b \mathbin{+\!\!+} \texttt{rest}\big) = \mathrm{some}\,\Big(\big\langle b.\texttt{header},\ \texttt{map}\;(tx \mapsto \text{if } aw \text{ then } tx \text{ else } \texttt{stripWitness}\;tx)\;b.\texttt{vtx}\big\rangle,\ \texttt{rest}\Big).readBlockaw(serBlockawb++rest)=some(⟨b.header, map(tx↦if aw then tx else stripWitnesstx)b.vtx⟩, rest).

Parsing in mode awawaw the mode-awawaw serialization of bbb, followed by arbitrary bytes, succeeds; the parsed header equals bbb's header exactly; the parsed transaction list has the same length and order as b.vtxb.\texttt{vtx}b.vtx, with the iii-th parsed transaction equal to the iii-th original when awawaw is true and to its witness-stripped copy (all witness lists emptied, everything else unchanged) when awawaw is false; and the remainder is exactly rest\texttt{rest}rest. When awawaw is true the right side is some (b,rest)\mathrm{some}\,(b, \texttt{rest})some(b,rest) up to the trivial identity map.

Unfolding. serBlock  aw  b=serHeader(b.header)+ ⁣ ⁣+writeCompactSize(∣b.vtx∣)+ ⁣ ⁣+serTx  aw  tx1+ ⁣ ⁣+⋯+ ⁣ ⁣+serTx  aw  txn\texttt{serBlock}\;aw\;b = \texttt{serHeader}(b.\texttt{header}) \mathbin{+\!\!+} \texttt{writeCompactSize}(|b.\texttt{vtx}|) \mathbin{+\!\!+} \texttt{serTx}\;aw\;tx_1 \mathbin{+\!\!+} \cdots \mathbin{+\!\!+} \texttt{serTx}\;aw\;tx_nserBlockawb=serHeader(b.header)++writeCompactSize(∣b.vtx∣)++serTxawtx1​++⋯++serTxawtxn​. readBlock  aw\texttt{readBlock}\;awreadBlockaw parses an 80-byte header (signed version, two 32-byte hashes, three unsigned 4-byte fields), then a range-checked CompactSize count, then exactly that many transactions with readTx  aw\texttt{readTx}\;awreadTxaw, each consuming its own bytes and handing the remainder to the next. Each readTx  aw\texttt{readTx}\;awreadTxaw behaves as described for tx_roundtrip: in mode false it ignores the flags logic and returns inputs with empty witnesses; in mode true it reads the marker [0,1][0,1][0,1] and the witness stacks when the transaction has a witness, and takes the direct path when the input list is non-empty. The per-transaction "at least one input" condition plays the role of hvhvhv in tx_roundtrip for each transaction when awawaw is true (it is assumed but unused when awawaw is false). The header wf\texttt{wf}wf bounds make the header parse exact, and ∣b.vtx∣≤MAX_SIZE|b.\texttt{vtx}| \le \texttt{MAX\_SIZE}∣b.vtx∣≤MAX_SIZE makes the range-checked count readable. The degenerate block with b.vtx=[ ]b.\texttt{vtx} = [\,]b.vtx=[] is included: the count byte 000 is read and zero transactions follow.

What is not said. Nothing about blocks violating wf\texttt{wf}wf, in particular blocks containing a transaction with no inputs — even in mode false, where such a block would in fact parse, the theorem makes no claim. No converse: nothing says a parsed block is well-formed or arose from serBlock\texttt{serBlock}serBlock. Nothing about mixed modes (serialize with one awawaw, parse with the other). Nothing about headerHash\texttt{headerHash}headerHash, blockWeight\texttt{blockWeight}blockWeight, MAX_BLOCK_WEIGHT\texttt{MAX\_BLOCK\_WEIGHT}MAX_BLOCK_WEIGHT, merkle roots (the header's merkle-root field is parsed as 32 opaque bytes; no relation to b.vtxb.\texttt{vtx}b.vtx is assumed or concluded), or lengths. It is the one-directional parse-after-serialize statement for blocks, per mode, under wf\texttt{wf}wf.

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