For flags with WITNESS, a ledger u, 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
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 f, every ledger u and every transaction tx: if the witness flag of f is on, every input script of tx verifies against u under f (in the sense of inputScriptsOk), and every input of tx spends, in u, an output whose script is a witness program, then the transaction identifier of tx equals the transaction identifier of the transaction obtained from tx by emptying every input's scriptSig and witness.
Binders and hypotheses
f: a record of seven Booleans (p2sh,witness,taproot,dersig,cltv,csv,nulldummy); arbitrary except as stated.
u: a ledger: a finite association list of pairs (outpoint, coin). An outpoint is (h,n), h a byte string of any length, n∈N. A coin is (out,height,isCoinbase) with out=(nValue∈Z,scriptPubKey). Keys need not be distinct.
tx: a transaction (version∈N,vin,vout,nLockTime∈N); each input is (prevout,scriptSig,nSequence,witness), each output (nValue∈Z,scriptPubKey). No well-formedness or range condition is assumed.
hf: f.witness=true.
h: inputScriptsOk(f,u,tx)=true (unfolded below).
hw: SpendsWitnessPrograms(u,tx), i.e. for every input i occurring in tx.vin, isWitnessProgram(accessCoin(u,i.prevout).out.scriptPubKey) is defined.
Conclusion
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), and ofIntent of that is the transaction tx∘ with the same version, outputs and lock time as tx, and whose j-th input has the same outpoint and sequence number as the j-th input of tx but scriptSig=[] and witness=[]. So the conclusion is txid(tx)=txid(tx∘).
Transaction identifier.txid(t)=SHA256(SHA256(ser0(t))), where ser0 is the witness-stripped serialization:
Here LE4(x) is the 4-byte little-endian encoding of xmod232; LE8±(z) is the 8-byte little-endian encoding of zmod264 (two's complement); CS is Bitcoin's CompactSize encoding; the outpoint hash h is emitted as its raw bytes, whatever its length. Witness stacks never contribute to ser0, and no marker/flag bytes are written. The 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 scriptSigs equals the one computed with every scriptSig replaced by the empty string (whose length prefix is the single byte 0).
Lookup.accessCoin(u,o) is the coin of the first pair of u whose outpoint equals o, or the dummy coin ((−1,[]),0,false) if none.
Witness program. For s of length k, isWitnessProgram(s) is defined iff 4≤k≤42, s0=0 or 0x51≤s0≤0x60, and s1+2=k; it yields version 0 (if s0=0) or s0−0x50, and program s2…sk−1. The empty script is not a witness program, so hw forces every input's outpoint to have an entry in u.
Input scripts OK. With vin=[i0,…,im−1], cn=accessCoin(u,in.prevout) and spent=[c0.out,…,cm−1.out], the hypothesis h says that for every 0≤n<m,
where Tspent is the Taproot file's BIP341 handler for the spent outputs, and (f,tx,n,a) is a verification context (flags, spending transaction, input index, amount).
verifyScript(T,c,σ,π,w): (1) evaluate σ (signature version base) on the empty stack, failing gives false, result Sσ; (2) evaluate π on Sσ, failing gives false, result S; false if S 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 is false); (3) if c.flags.witness is on and isWitnessProgram(π)=(v,p): false if σ=[], else the verdict of verifyWitnessProgram(T,c,w,v,p,isP2sh=false), final; (4) else if c.flags.p2sh is on and π is 0xa90x14⟨20 bytes⟩0x87: the P2SH path (push-only σ, top of Sσ is the redeem script r, evaluated on the rest with a true top; if the witness flag is on and r is a witness program then σ must equal pushBytes(r) and verifyWitnessProgram(T,c,w,v,p,true) decides; if the witness flag is on and r is not a witness program then w must be empty; with the witness flag off, true); (5) else false if the witness flag is on and w=[], else true. Evaluation ("evalBytes") of a script s from stack S in context c is undefined if ∣s∣>10000 or s does not parse, and otherwise is the Script interpreter's final stack under flags (c.flags.cltv,c.flags.csv,c.flags.nulldummy) with the legacy oracle for (c.flags.dersig,c.tx,c.nIn,c.amount, the signature version, script code s). verifyWitnessProgram(T,c,w,v,p,isP2sh): for v=0, ∣p∣=32, the last element of w must hash (SHA-256) to p and is executed as a witness-v0 script on the reversed remaining elements (every element ≤520 bytes, exactly one element left, true); for v=0, ∣p∣=20, ∣w∣ must be 2 and the implied P2PKH script 0x760xa9pushBytes(p)0x880xac is executed on w reversed; v=0 with other lengths is false; v=1, ∣p∣=32, not P2SH is true when c.flags.taproot is off and otherwise T(c,w,p); every other case is true. Tspent(c,w,p) is false on an empty w; otherwise it strips an optional annex, checks a single remaining element as a Schnorr key-path signature against p over c.tx, spent, c.nIn, or, with more elements, checks a control block (length 33+32k, 0≤k≤128) committing p to the leaf script and executes the tapscript for leaf version 0xc0 (true for other leaf versions).
Edge cases made explicit
If tx.vin=[]: h and hw hold vacuously, tx∘=tx, and the conclusion is an identity.
hw is by membership and h by position; both cover every input, so duplicated inputs are covered at each occurrence.
hw admits every witness version 0–16 and program length 2–40 (version-0 programs of length other than 20 or 32, version 1 of any length, versions 2–16), not only those for which verifyWitnessProgram performs a check.
txid reduces version, prevout.n, nSequence and nLockTime modulo 232 and nValue modulo 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∘ nor that every scriptSig of tx is empty.
Nothing constrains f.p2sh, f.taproot, f.dersig, f.cltv, f.csv, f.nulldummy, the distinctness of ledger keys, coinbase status, or the well-formedness of tx.
Confirmed by the moderator at approval.