Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Without witnesses the weight is four times the size

Proved
BitcoinSer.weight_no_witness

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

bitcoinbitcoin-mainnetconsensusformal-verificationgenesismerkleserializationsha256

For every transaction with no witness: the two serializations coincide, and txWeight(tx)=4⋅∣serTx(false,tx)∣\mathrm{txWeight}(tx) = 4 \cdot |\mathrm{serTx}(\mathtt{false}, tx)|txWeight(tx)=4⋅∣serTx(false,tx)∣.

Preamble
import Definitions.Def_BitcoinSer
Formal statement
theorem BitcoinSer.weight_no_witness (tx : Tx) (h : tx.hasWitness = false) :
    BitcoinSer.serTx true tx = BitcoinSer.serTx false tx ∧
      BitcoinSer.txWeight tx = BitcoinSer.WITNESS_SCALE_FACTOR * (BitcoinSer.serTx false tx).length := 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.weight_no_witness

Binders and hypothesis. A transaction record txtxtx and the hypothesis

h:hasWitness(tx)=false,h : \texttt{hasWitness}(tx) = \mathrm{false},h:hasWitness(tx)=false,

i.e. the Boolean "some input has a non-empty witness list" evaluates to false — every input of txtxtx has an empty witness list (vacuously so if txtxtx has no inputs). No well-formedness is assumed; field values may be arbitrary.

Conclusion. A conjunction of two equalities:

serTx  true  tx=serTx  false  txandtxWeight(tx)=WITNESS_SCALE_FACTOR⋅∣serTx  false  tx∣,\texttt{serTx}\;\mathrm{true}\;tx = \texttt{serTx}\;\mathrm{false}\;tx \qquad\text{and}\qquad \texttt{txWeight}(tx) = \texttt{WITNESS\_SCALE\_FACTOR} \cdot |\texttt{serTx}\;\mathrm{false}\;tx| ,serTxtruetx=serTxfalsetxandtxWeight(tx)=WITNESS_SCALE_FACTOR⋅∣serTxfalsetx∣,

where WITNESS_SCALE_FACTOR=4\texttt{WITNESS\_SCALE\_FACTOR} = 4WITNESS_SCALE_FACTOR=4.

Unfolding the first conjunct. serTx  aw  tx\texttt{serTx}\;aw\;txserTxawtx computes ϕ=1\phi = 1ϕ=1 if aw∧hasWitness(tx)aw \wedge \texttt{hasWitness}(tx)aw∧hasWitness(tx), else 000; the output is the 4-byte version, then [0,ϕ][0, \phi][0,ϕ] only when ϕ≠0\phi \ne 0ϕ=0, then the CompactSize-prefixed inputs, the CompactSize-prefixed outputs, then (only when ϕ≠0\phi \ne 0ϕ=0) one CompactSize-prefixed witness stack per input, then the 4-byte lock time. Under the hypothesis, ϕ=0\phi = 0ϕ=0 for both aw=trueaw = \mathrm{true}aw=true and aw=falseaw = \mathrm{false}aw=false, so the marker bytes and the witness section are absent in both and the two byte strings coincide. The first conjunct says exactly this: with no non-empty witness, the "allow witness" mode produces the legacy encoding.

Unfolding the second conjunct. txWeight(tx)=∣serTx  false  tx∣⋅(WITNESS_SCALE_FACTOR−1)+∣serTx  true  tx∣=3 ∣serTx  false  tx∣+∣serTx  true  tx∣\texttt{txWeight}(tx) = |\texttt{serTx}\;\mathrm{false}\;tx| \cdot (\texttt{WITNESS\_SCALE\_FACTOR} - 1) + |\texttt{serTx}\;\mathrm{true}\;tx| = 3\,|\texttt{serTx}\;\mathrm{false}\;tx| + |\texttt{serTx}\;\mathrm{true}\;tx|txWeight(tx)=∣serTxfalsetx∣⋅(WITNESS_SCALE_FACTOR−1)+∣serTxtruetx∣=3∣serTxfalsetx∣+∣serTxtruetx∣ (the subtraction 4−14 - 14−1 is on natural numbers and is 333). Using the first conjunct, the second summand equals ∣serTx  false  tx∣|\texttt{serTx}\;\mathrm{false}\;tx|∣serTxfalsetx∣, giving 3L+L=4L3L + L = 4L3L+L=4L with L=∣serTx  false  tx∣L = |\texttt{serTx}\;\mathrm{false}\;tx|L=∣serTxfalsetx∣. The conclusion writes the right side as WITNESS_SCALE_FACTOR⋅L\texttt{WITNESS\_SCALE\_FACTOR} \cdot LWITNESS_SCALE_FACTOR⋅L, i.e. 4L4L4L, with the constant on the left of the product.

Edge cases covered: txtxtx with no inputs (then hasWitness\texttt{hasWitness}hasWitness is false automatically and the hypothesis holds); txtxtx whose inputs all have witness [ ][\,][]; arbitrary out-of-range version/lock time (truncated identically on both sides).

What is not said. Nothing when hasWitness(tx)\texttt{hasWitness}(tx)hasWitness(tx) is true: no formula for the weight of a witness-bearing transaction, and no claim that the two serializations differ. Nothing about blockWeight\texttt{blockWeight}blockWeight, MAX_BLOCK_WEIGHT\texttt{MAX\_BLOCK\_WEIGHT}MAX_BLOCK_WEIGHT, or any bound on the weight. Nothing about wtxid\texttt{wtxid}wtxid (the definition makes wtxid=txid\texttt{wtxid} = \texttt{txid}wtxid=txid in this case, but the theorem does not mention it). No lengths are computed: the theorem relates the weight to the serialized length but does not say what that length is. It is a two-part equality under the single Boolean hypothesis.

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