Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Transactions round-trip in both formats

Proved
BitcoinSer.tx_roundtrip

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

bitcoinbitcoin-mainnetconsensusformal-verificationgenesismerkleserializationsha256

For every well-formed transaction txtxtx, witness mode awawaw with (awawaw ⇒ vin non-empty), and remainder rrr:

readTx(aw,serTx(aw,tx)++r)=some(if aw then tx else stripWitness(tx), r).\mathrm{readTx}(aw, \mathrm{serTx}(aw, tx) ++ r) = \mathrm{some}(\text{if } aw \text{ then } tx \text{ else } \mathrm{stripWitness}(tx),\ r).readTx(aw,serTx(aw,tx)++r)=some(if aw then tx else stripWitness(tx), r).

With witnesses allowed the extended format (dummy, flag byte, witness stacks) is parsed back exactly; without, the basic format returns the transaction with cleared witnesses. The non-empty-vin side condition is genuine: UnserializeTransaction reads an empty vin as the BIP144 dummy, so a witness-less, input-less transaction does not round-trip through the witness-aware reader.

Preamble
import Definitions.Def_BitcoinSer
Formal statement
theorem BitcoinSer.tx_roundtrip (aw : Bool) (tx : Tx) (rest : Bytes) (hw : tx.wf)
    (hv : aw = true → tx.vin ≠ []) :
    BitcoinSer.readTx aw (BitcoinSer.serTx aw tx ++ rest) =
      some (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.tx_roundtrip

Binders and hypothesis. A Boolean awawaw ("allow witness", either value), a transaction record txtxtx, a byte string rest\texttt{rest}rest (arbitrary), and two hypotheses:

  • hw:tx.wfhw : tx.\texttt{wf}hw:tx.wf, which unfolds to: tx.version<232tx.\texttt{version} < 2^{32}tx.version<232; tx.nLockTime<232tx.\texttt{nLockTime} < 2^{32}tx.nLockTime<232; ∣tx.vin∣≤MAX_SIZE|tx.\texttt{vin}| \le \texttt{MAX\_SIZE}∣tx.vin∣≤MAX_SIZE; ∣tx.vout∣≤MAX_SIZE|tx.\texttt{vout}| \le \texttt{MAX\_SIZE}∣tx.vout∣≤MAX_SIZE; every input iii satisfies ∣i.prevout.hash∣=32|i.\texttt{prevout.hash}| = 32∣i.prevout.hash∣=32, i.prevout.n<232i.\texttt{prevout.n} < 2^{32}i.prevout.n<232, ∣i.scriptSig∣≤MAX_SIZE|i.\texttt{scriptSig}| \le \texttt{MAX\_SIZE}∣i.scriptSig∣≤MAX_SIZE, i.nSequence<232i.\texttt{nSequence} < 2^{32}i.nSequence<232, ∣i.witness∣≤MAX_SIZE|i.\texttt{witness}| \le \texttt{MAX\_SIZE}∣i.witness∣≤MAX_SIZE and every witness item has length ≤MAX_SIZE\le \texttt{MAX\_SIZE}≤MAX_SIZE; every output ooo satisfies −263≤o.nValue<263-2^{63} \le o.\texttt{nValue} < 2^{63}−263≤o.nValue<263 and ∣o.scriptPubKey∣≤MAX_SIZE|o.\texttt{scriptPubKey}| \le \texttt{MAX\_SIZE}∣o.scriptPubKey∣≤MAX_SIZE. Here MAX_SIZE=225\texttt{MAX\_SIZE} = 2^{25}MAX_SIZE=225 and all bounds on lengths are non-strict.
  • hv:aw=true⇒tx.vin≠[ ]hv : aw = \mathrm{true} \Rightarrow tx.\texttt{vin} \ne [\,]hv:aw=true⇒tx.vin=[]: if witness mode is on, the transaction has at least one input. When awawaw is false this hypothesis is vacuous and txtxtx may have no inputs.

Conclusion.

readTx  aw  (serTx  aw  tx+ ⁣ ⁣+rest)=some ( (if aw then tx else stripWitness  tx), rest ).\texttt{readTx}\;aw\;\big(\texttt{serTx}\;aw\;tx \mathbin{+\!\!+} \texttt{rest}\big) = \mathrm{some}\,\big(\,(\text{if } aw \text{ then } tx \text{ else } \texttt{stripWitness}\;tx),\ \texttt{rest}\,\big).readTxaw(serTxawtx++rest)=some((if aw then tx else stripWitnesstx), rest).

That is: parsing, in mode awawaw, the mode-awawaw serialization of txtxtx followed by arbitrary trailing bytes succeeds; the parsed record equals txtxtx itself when awawaw is true and equals txtxtx with all witness lists emptied when awawaw is false; and the remainder is exactly rest\texttt{rest}rest.

Unfolding the serializer. Let ϕ=1\phi = 1ϕ=1 if awawaw and hasWitness(tx)\texttt{hasWitness}(tx)hasWitness(tx) (some input has a non-empty witness), else 000. serTx  aw  tx\texttt{serTx}\;aw\;txserTxawtx is the 4-byte little-endian version, then [0,1][0, 1][0,1] if ϕ=1\phi = 1ϕ=1, then the CompactSize count of inputs and each input (32 raw hash bytes, 4-byte index, CompactSize-prefixed script, 4-byte sequence), then the count of outputs and each output (8-byte two's-complement value, prefixed script), then, if ϕ=1\phi = 1ϕ=1, for each input a CompactSize count of witness items followed by each item length-prefixed, then the 4-byte lock time.

Unfolding the parser. readTx  aw\texttt{readTx}\;awreadTxaw reads the 4-byte version (unsigned), then a range-checked input list vin0\texttt{vin}_0vin0​. If vin0\texttt{vin}_0vin0​ is empty and awawaw is true, it consumes one byte flflfl: if fl≠0fl \ne 0fl=0 it re-reads an input list and reads an output list; if fl=0fl = 0fl=0 it sets the output list to [ ][\,][] without reading one. Otherwise it reads the output list directly with flags 000. Then, if the flags value is odd and awawaw is true, it reads one witness stack per input, attaches them in order, and fails unless at least one stack is non-empty, decrementing the flags. Then it fails if the flags are still non-zero, and finally reads the 4-byte lock time.

How the cases play out. (i) aw=falseaw = \mathrm{false}aw=false: ϕ=0\phi = 0ϕ=0, no marker; the parser never enters the flag branch; all fields are recovered and every parsed input has witness [ ][\,][], which is why the conclusion names stripWitness  tx\texttt{stripWitness}\;txstripWitnesstx — this is an equality even if txtxtx had witnesses. (ii) aw=trueaw = \mathrm{true}aw=true and hasWitness(tx)\texttt{hasWitness}(tx)hasWitness(tx): ϕ=1\phi = 1ϕ=1; the parser reads the input count 000 from the marker, consumes fl=1fl = 1fl=1, re-reads inputs and outputs, reads ∣vin∣|\texttt{vin}|∣vin∣ witness stacks, the non-empty-witness test passes, flags become 000, lock time is read; the result is txtxtx with witnesses attached, i.e. txtxtx. (iii) aw=trueaw = \mathrm{true}aw=true, no witness: ϕ=0\phi = 0ϕ=0, the encoding is the legacy one; by hvhvhv the input list is non-empty, so the parser takes the direct branch; result txtxtx. The hypothesis hvhvhv excludes exactly the case aw=trueaw = \mathrm{true}aw=true, vin=[ ]\texttt{vin} = [\,]vin=[], where the serialization begins with an input count of 000 and the parser would read the output count byte as the flags byte (for ≥1\ge 1≥1 outputs it would then try to re-parse inputs from output bytes; for 000 outputs it would consume the count and still succeed with empty outputs); the theorem makes no claim there. The wf\texttt{wf}wf bounds ensure that the truncating encoders and the range-checked, canonical readers recover every value; the signed range on values ensures the two's-complement decode is exact; the 32-byte hash lengths ensure the raw hash bytes are cut at the right place.

What is not said. Nothing about aw=trueaw = \mathrm{true}aw=true with no inputs. Nothing about parsing a witness serialization in non-witness mode or vice versa. No converse (parsed transactions need not be well-formed, and nothing says a successful parse came from serTx\texttt{serTx}serTx). Nothing about wf\texttt{wf}wf of the result, about txid\texttt{txid}txid, or about lengths. It is the one-directional parse-after-serialize statement, per mode, under wf\texttt{wf}wf and hvhvhv.

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