Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

For native-SegWit spends the txid is the txid of the intent's canonical transaction

Proved
BitcoinMalleability.txid_of_intent

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

bip141bitcoinbitcoin-mainnetconsensusformal-verificationlightningmalleabilitysegwittxid

For flags with WITNESS, a ledger uuu, and a transaction whose scripts verify and whose inputs all spend native witness programs: txid tx = txid (ofIntent (intentOf tx)). The txid hashes the witness-stripped serialization; with every scriptSig forced empty, nothing chosen by a signer or a third party remains in the hashed bytes.

Preamble
import Definitions.Def_BitcoinMalleability
import Definitions.Def_BitcoinActivation
import Definitions.Def_BitcoinSer
open BitcoinMalleability BitcoinSer BitcoinBlockV2
Formal statement
theorem BitcoinMalleability.txid_of_intent (f : BitcoinActivation.ScriptFlags) (u : Ledger) (tx : BitcoinSer.Tx)
    (hf : f.witness = true) (h : BitcoinBlockV2.inputScriptsOk f u tx = true)
    (hw : BitcoinMalleability.SpendsWitnessPrograms u tx) :
    BitcoinSer.txid tx = BitcoinSer.txid (BitcoinMalleability.ofIntent (BitcoinMalleability.intentOf tx)) := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyScript (SCRIPT_ERR_WITNESS_MALLEATED, SCRIPT_ERR_WITNESS_MALLEATED_P2SH), src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; CTransaction::ComputeHash, SerializeTransaction (primitives/transaction.h, transaction.cpp); CheckInputScripts (validation.cpp); BIP141 (Transaction ID)
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: BitcoinMalleability.txid_of_intent

Statement in words

For every consensus flag set fff, every ledger uuu and every transaction tx\mathrm{tx}tx: if the witness flag of fff is on, every input script of tx\mathrm{tx}tx verifies against uuu under fff (in the sense of inputScriptsOk\mathrm{inputScriptsOk}inputScriptsOk), and every input of tx\mathrm{tx}tx spends, in uuu, an output whose script is a witness program, then the transaction identifier of tx\mathrm{tx}tx equals the transaction identifier of the transaction obtained from tx\mathrm{tx}tx by emptying every input's scriptSig\mathrm{scriptSig}scriptSig and witness.

Binders and hypotheses

  • fff: a record of seven Booleans (p2sh,witness,taproot,dersig,cltv,csv,nulldummy)(\mathrm{p2sh}, \mathrm{witness}, \mathrm{taproot}, \mathrm{dersig}, \mathrm{cltv}, \mathrm{csv}, \mathrm{nulldummy})(p2sh,witness,taproot,dersig,cltv,csv,nulldummy); arbitrary except as stated.
  • uuu: a ledger: a finite association list of pairs (outpoint, coin). An outpoint is (h,n)(h, n)(h,n), hhh a byte string of any length, n∈Nn \in \mathbb Nn∈N. A coin is (out,height,isCoinbase)(\mathrm{out}, \mathrm{height}, \mathrm{isCoinbase})(out,height,isCoinbase) with out=(nValue∈Z,scriptPubKey)\mathrm{out} = (\mathrm{nValue} \in \mathbb Z, \mathrm{scriptPubKey})out=(nValue∈Z,scriptPubKey). Keys need not be distinct.
  • tx\mathrm{tx}tx: a transaction (version∈N,vin,vout,nLockTime∈N)(\mathrm{version} \in \mathbb N, \mathrm{vin}, \mathrm{vout}, \mathrm{nLockTime} \in \mathbb N)(version∈N,vin,vout,nLockTime∈N); each input is (prevout,scriptSig,nSequence,witness)(\mathrm{prevout}, \mathrm{scriptSig}, \mathrm{nSequence}, \mathrm{witness})(prevout,scriptSig,nSequence,witness), each output (nValue∈Z,scriptPubKey)(\mathrm{nValue} \in \mathbb Z, \mathrm{scriptPubKey})(nValue∈Z,scriptPubKey). No well-formedness or range condition is assumed.
  • hfh_fhf​: f.witness=truef.\mathrm{witness} = \mathrm{true}f.witness=true.
  • hhh: inputScriptsOk(f,u,tx)=true\mathrm{inputScriptsOk}(f, u, \mathrm{tx}) = \mathrm{true}inputScriptsOk(f,u,tx)=true (unfolded below).
  • hwh_whw​: SpendsWitnessPrograms(u,tx)\mathrm{SpendsWitnessPrograms}(u, \mathrm{tx})SpendsWitnessPrograms(u,tx), i.e. for every input iii occurring in tx.vin\mathrm{tx}.\mathrm{vin}tx.vin, isWitnessProgram(accessCoin(u,i.prevout).out.scriptPubKey)\mathrm{isWitnessProgram}(\mathrm{accessCoin}(u, i.\mathrm{prevout}).\mathrm{out}.\mathrm{scriptPubKey})isWitnessProgram(accessCoin(u,i.prevout).out.scriptPubKey) is defined.

Conclusion

txid(tx)  =  txid(ofIntent(intentOf(tx))),\mathrm{txid}(\mathrm{tx}) \;=\; \mathrm{txid}\big(\mathrm{ofIntent}(\mathrm{intentOf}(\mathrm{tx}))\big),txid(tx)=txid(ofIntent(intentOf(tx))),

an equality of byte strings (the 32-byte double-SHA-256 digests).

The notions, unfolded

Intent round trip. intentOf(tx)=(version,[(i.prevout,i.nSequence)∣i∈vin],vout,nLockTime)\mathrm{intentOf}(\mathrm{tx}) = (\mathrm{version}, [(i.\mathrm{prevout}, i.\mathrm{nSequence}) \mid i \in \mathrm{vin}], \mathrm{vout}, \mathrm{nLockTime})intentOf(tx)=(version,[(i.prevout,i.nSequence)∣i∈vin],vout,nLockTime), and ofIntent\mathrm{ofIntent}ofIntent of that is the transaction tx∘\mathrm{tx}^\circtx∘ with the same version, outputs and lock time as tx\mathrm{tx}tx, and whose jjj-th input has the same outpoint and sequence number as the jjj-th input of tx\mathrm{tx}tx but scriptSig=[ ]\mathrm{scriptSig} = [\,]scriptSig=[] and witness=[ ]\mathrm{witness} = [\,]witness=[]. So the conclusion is txid(tx)=txid(tx∘)\mathrm{txid}(\mathrm{tx}) = \mathrm{txid}(\mathrm{tx}^\circ)txid(tx)=txid(tx∘).

Transaction identifier. txid(t)=SHA256(SHA256(ser0(t)))\mathrm{txid}(t) = \mathrm{SHA256}(\mathrm{SHA256}(\mathrm{ser}_0(t)))txid(t)=SHA256(SHA256(ser0​(t))), where ser0\mathrm{ser}_0ser0​ is the witness-stripped serialization:

ser0(t)=LE4(version) ∥ CS(∣vin∣) ∥ ∥i∈vin(i.prevout.h ∥ LE4(i.prevout.n) ∥ CS(∣i.scriptSig∣) ∥ i.scriptSig ∥ LE4(i.nSequence)) ∥ CS(∣vout∣) ∥ ∥o∈vout(LE8±(o.nValue) ∥ CS(∣o.scriptPubKey∣) ∥ o.scriptPubKey) ∥ LE4(nLockTime).\mathrm{ser}_0(t) = \mathrm{LE}_4(\mathrm{version}) \,\|\, \mathrm{CS}(|\mathrm{vin}|) \,\|\, \big\|_{i \in \mathrm{vin}} \big( i.\mathrm{prevout}.h \,\|\, \mathrm{LE}_4(i.\mathrm{prevout}.n) \,\|\, \mathrm{CS}(|i.\mathrm{scriptSig}|) \,\|\, i.\mathrm{scriptSig} \,\|\, \mathrm{LE}_4(i.\mathrm{nSequence}) \big) \,\|\, \mathrm{CS}(|\mathrm{vout}|) \,\|\, \big\|_{o \in \mathrm{vout}} \big( \mathrm{LE}_8^{\pm}(o.\mathrm{nValue}) \,\|\, \mathrm{CS}(|o.\mathrm{scriptPubKey}|) \,\|\, o.\mathrm{scriptPubKey} \big) \,\|\, \mathrm{LE}_4(\mathrm{nLockTime}).ser0​(t)=LE4​(version)∥CS(∣vin∣)∥​i∈vin​(i.prevout.h∥LE4​(i.prevout.n)∥CS(∣i.scriptSig∣)∥i.scriptSig∥LE4​(i.nSequence))∥CS(∣vout∣)∥​o∈vout​(LE8±​(o.nValue)∥CS(∣o.scriptPubKey∣)∥o.scriptPubKey)∥LE4​(nLockTime).

Here LE4(x)\mathrm{LE}_4(x)LE4​(x) is the 4-byte little-endian encoding of x mod 232x \bmod 2^{32}xmod232; LE8±(z)\mathrm{LE}_8^{\pm}(z)LE8±​(z) is the 8-byte little-endian encoding of z mod 264z \bmod 2^{64}zmod264 (two's complement); CS\mathrm{CS}CS is Bitcoin's CompactSize encoding; the outpoint hash hhh is emitted as its raw bytes, whatever its length. Witness stacks never contribute to ser0\mathrm{ser}_0ser0​, and no marker/flag bytes are written. The scriptSig\mathrm{scriptSig}scriptSig of every input does contribute, with its length prefix. Thus the conclusion asserts that the double-SHA-256 of the byte string above computed with the actual scriptSig\mathrm{scriptSig}scriptSigs equals the one computed with every scriptSig\mathrm{scriptSig}scriptSig replaced by the empty string (whose length prefix is the single byte 000).

Lookup. accessCoin(u,o)\mathrm{accessCoin}(u, o)accessCoin(u,o) is the coin of the first pair of uuu whose outpoint equals ooo, or the dummy coin ((−1,[ ]),0,false)((-1,[\,]),0,\mathrm{false})((−1,[]),0,false) if none.

Witness program. For sss of length kkk, isWitnessProgram(s)\mathrm{isWitnessProgram}(s)isWitnessProgram(s) is defined iff 4≤k≤424 \le k \le 424≤k≤42, s0=0s_0 = 0s0​=0 or 0x51≤s0≤0x60\mathrm{0x51} \le s_0 \le \mathrm{0x60}0x51≤s0​≤0x60, and s1+2=ks_1 + 2 = ks1​+2=k; it yields version 000 (if s0=0s_0 = 0s0​=0) or s0−0x50s_0 - \mathrm{0x50}s0​−0x50, and program s2…sk−1s_2 \ldots s_{k-1}s2​…sk−1​. The empty script is not a witness program, so hwh_whw​ forces every input's outpoint to have an entry in uuu.

Input scripts OK. With vin=[i0,…,im−1]\mathrm{vin} = [i_0, \ldots, i_{m-1}]vin=[i0​,…,im−1​], cn=accessCoin(u,in.prevout)c_n = \mathrm{accessCoin}(u, i_n.\mathrm{prevout})cn​=accessCoin(u,in​.prevout) and spent=[c0.out,…,cm−1.out]\mathrm{spent} = [c_0.\mathrm{out}, \ldots, c_{m-1}.\mathrm{out}]spent=[c0​.out,…,cm−1​.out], the hypothesis hhh says that for every 0≤n<m0 \le n < m0≤n<m,

verifyScript(Tspent, (f,tx,n,cn.out.nValue), in.scriptSig, cn.out.scriptPubKey, in.witness)=true,\mathrm{verifyScript}\big(T_{\mathrm{spent}},\ (f, \mathrm{tx}, n, c_n.\mathrm{out}.\mathrm{nValue}),\ i_n.\mathrm{scriptSig},\ c_n.\mathrm{out}.\mathrm{scriptPubKey},\ i_n.\mathrm{witness}\big) = \mathrm{true},verifyScript(Tspent​, (f,tx,n,cn​.out.nValue), in​.scriptSig, cn​.out.scriptPubKey, in​.witness)=true,

where TspentT_{\mathrm{spent}}Tspent​ is the Taproot file's BIP341 handler for the spent outputs, and (f,tx,n,a)(f, \mathrm{tx}, n, a)(f,tx,n,a) is a verification context (flags, spending transaction, input index, amount).

verifyScript (T,c,σ,π,w)(T, c, \sigma, \pi, w)(T,c,σ,π,w): (1) evaluate σ\sigmaσ (signature version base) on the empty stack, failing gives false, result SσS_\sigmaSσ​; (2) evaluate π\piπ on SσS_\sigmaSσ​, failing gives false, result SSS; false if SSS is empty or its top is not true (a byte string is true iff some byte is non-zero, except that a string whose only non-zero byte is a final 0x80\mathrm{0x80}0x80 is false); (3) if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness is on and isWitnessProgram(π)=(v,p)\mathrm{isWitnessProgram}(\pi) = (v, p)isWitnessProgram(π)=(v,p): false if σ≠[ ]\sigma \ne [\,]σ=[], else the verdict of verifyWitnessProgram(T,c,w,v,p,isP2sh=false)\mathrm{verifyWitnessProgram}(T, c, w, v, p, \mathrm{isP2sh}=\mathrm{false})verifyWitnessProgram(T,c,w,v,p,isP2sh=false), final; (4) else if c.flags.p2shc.\mathrm{flags}.\mathrm{p2sh}c.flags.p2sh is on and π\piπ is 0xa9 0x14 ⟨20 bytes⟩ 0x87\mathrm{0xa9}\,\mathrm{0x14}\,\langle 20 \text{ bytes}\rangle\,\mathrm{0x87}0xa90x14⟨20 bytes⟩0x87: the P2SH path (push-only σ\sigmaσ, top of SσS_\sigmaSσ​ is the redeem script rrr, evaluated on the rest with a true top; if the witness flag is on and rrr is a witness program then σ\sigmaσ must equal pushBytes(r)\mathrm{pushBytes}(r)pushBytes(r) and verifyWitnessProgram(T,c,w,v,p,true)\mathrm{verifyWitnessProgram}(T, c, w, v, p, \mathrm{true})verifyWitnessProgram(T,c,w,v,p,true) decides; if the witness flag is on and rrr is not a witness program then www must be empty; with the witness flag off, true); (5) else false if the witness flag is on and w≠[ ]w \ne [\,]w=[], else true. Evaluation ("evalBytes") of a script sss from stack SSS in context ccc is undefined if ∣s∣>10000|s| > 10000∣s∣>10000 or sss does not parse, and otherwise is the Script interpreter's final stack under flags (c.flags.cltv,c.flags.csv,c.flags.nulldummy)(c.\mathrm{flags}.\mathrm{cltv}, c.\mathrm{flags}.\mathrm{csv}, c.\mathrm{flags}.\mathrm{nulldummy})(c.flags.cltv,c.flags.csv,c.flags.nulldummy) with the legacy oracle for (c.flags.dersig,c.tx,c.nIn,c.amount(c.\mathrm{flags}.\mathrm{dersig}, c.\mathrm{tx}, c.\mathrm{nIn}, c.\mathrm{amount}(c.flags.dersig,c.tx,c.nIn,c.amount, the signature version, script code s)s)s). verifyWitnessProgram(T,c,w,v,p,isP2sh)\mathrm{verifyWitnessProgram}(T,c,w,v,p,\mathrm{isP2sh})verifyWitnessProgram(T,c,w,v,p,isP2sh): for v=0v=0v=0, ∣p∣=32|p|=32∣p∣=32, the last element of www must hash (SHA-256) to ppp and is executed as a witness-v0 script on the reversed remaining elements (every element ≤520\le 520≤520 bytes, exactly one element left, true); for v=0v=0v=0, ∣p∣=20|p|=20∣p∣=20, ∣w∣|w|∣w∣ must be 222 and the implied P2PKH script 0x76 0xa9 pushBytes(p) 0x88 0xac\mathrm{0x76}\,\mathrm{0xa9}\,\mathrm{pushBytes}(p)\,\mathrm{0x88}\,\mathrm{0xac}0x760xa9pushBytes(p)0x880xac is executed on www reversed; v=0v=0v=0 with other lengths is false; v=1v=1v=1, ∣p∣=32|p|=32∣p∣=32, not P2SH is true when c.flags.taprootc.\mathrm{flags}.\mathrm{taproot}c.flags.taproot is off and otherwise T(c,w,p)T(c, w, p)T(c,w,p); every other case is true. Tspent(c,w,p)T_{\mathrm{spent}}(c,w,p)Tspent​(c,w,p) is false on an empty www; otherwise it strips an optional annex, checks a single remaining element as a Schnorr key-path signature against ppp over c.txc.\mathrm{tx}c.tx, spent\mathrm{spent}spent, c.nInc.\mathrm{nIn}c.nIn, or, with more elements, checks a control block (length 33+32k33 + 32k33+32k, 0≤k≤1280 \le k \le 1280≤k≤128) committing ppp to the leaf script and executes the tapscript for leaf version 0xc0\mathrm{0xc0}0xc0 (true for other leaf versions).

Edge cases made explicit

  • If tx.vin=[ ]\mathrm{tx}.\mathrm{vin} = [\,]tx.vin=[]: hhh and hwh_whw​ hold vacuously, tx∘=tx\mathrm{tx}^\circ = \mathrm{tx}tx∘=tx, and the conclusion is an identity.
  • hwh_whw​ is by membership and hhh by position; both cover every input, so duplicated inputs are covered at each occurrence.
  • hwh_whw​ admits every witness version 000–161616 and program length 222–404040 (version-0 programs of length other than 202020 or 323232, version 111 of any length, versions 222–161616), not only those for which verifyWitnessProgram\mathrm{verifyWitnessProgram}verifyWitnessProgram performs a check.
  • txid\mathrm{txid}txid reduces version\mathrm{version}version, prevout.n\mathrm{prevout}.nprevout.n, nSequence\mathrm{nSequence}nSequence and nLockTime\mathrm{nLockTime}nLockTime modulo 2322^{32}232 and nValue\mathrm{nValue}nValue modulo 2642^{64}264 before hashing; outpoint hashes of any length are written raw.
  • The conclusion is an equality of hash digests, not of transactions; it does not say tx=tx∘\mathrm{tx} = \mathrm{tx}^\circtx=tx∘ nor that every scriptSig\mathrm{scriptSig}scriptSig of tx\mathrm{tx}tx is empty.
  • Nothing constrains f.p2shf.\mathrm{p2sh}f.p2sh, f.taprootf.\mathrm{taproot}f.taproot, f.dersigf.\mathrm{dersig}f.dersig, f.cltvf.\mathrm{cltv}f.cltv, f.csvf.\mathrm{csv}f.csv, f.nulldummyf.\mathrm{nulldummy}f.nulldummy, the distinctness of ledger keys, coinbase status, or the well-formedness of tx\mathrm{tx}tx.
Human review
  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 29, 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