For flags with WITNESS, a ledger u and two transactions with the same intent (same version, prevouts, sequence numbers, outputs and lock time), both of whose scripts verify against u, where the inputs spend native witness programs: txid tx = txid tx'. No choice of signatures or witnesses — by the signer, or by a third party re-encoding them — changes the identifier of a valid spend. This is the BIP141 property that second-layer protocols (payment channels) rely on to refer to unconfirmed transactions by txid.
Preamble
import Definitions.Def_BitcoinMalleability
import Definitions.Def_BitcoinActivation
import Definitions.Def_BitcoinSer
open BitcoinMalleability BitcoinSer BitcoinBlockV2
Formal statement
theorem BitcoinMalleability.txid_determined (f : BitcoinActivation.ScriptFlags) (u : Ledger)
(tx tx' : BitcoinSer.Tx) (hf : f.witness = true)
(hI : BitcoinMalleability.intentOf tx = BitcoinMalleability.intentOf tx')
(h : BitcoinBlockV2.inputScriptsOk f u tx = true) (h' : BitcoinBlockV2.inputScriptsOk f u tx' = true)
(hw : BitcoinMalleability.SpendsWitnessPrograms u tx) :
BitcoinSer.txid tx = BitcoinSer.txid 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_determined
Statement in words
For every consensus flag set f, every ledger u and every two transactions tx,tx′: if the witness flag of f is on, tx and tx′ have the same intent, each of tx and tx′ has all its input scripts verifying against u under f, and every input of tx (the hypothesis is stated for tx only) spends in u an output whose script is a witness program, then tx and tx′ have the same transaction identifier.
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 (outpoint, coin) pairs; outpoint (h,n) with h a byte string of any length and n∈N; coin (out,height,isCoinbase) with out=(nValue∈Z,scriptPubKey). Keys need not be distinct.
tx,tx′: transactions (version∈N,vin,vout,nLockTime∈N) with inputs (prevout,scriptSig,nSequence,witness) and outputs (nValue∈Z,scriptPubKey). No well-formedness is assumed.
hf: f.witness=true.
hI: intentOf(tx)=intentOf(tx′).
h: inputScriptsOk(f,u,tx)=true.
h′: inputScriptsOk(f,u,tx′)=true (same f, same u).
hw: SpendsWitnessPrograms(u,tx). There is no corresponding hypothesis for tx′.
Conclusion
txid(tx)=txid(tx′),
an equality of 32-byte digests.
The notions, unfolded
Same intent.intentOf(t)=(t.version,[(i.prevout,i.nSequence)∣i∈t.vin],t.vout,t.nLockTime). So hI says exactly: tx.version=tx′.version; tx and tx′ have the same number m of inputs and, for each position j<m, the j-th inputs have equal outpoints and equal sequence numbers; tx.vout=tx′.vout as lists (same values and scripts in the same order); tx.nLockTime=tx′.nLockTime. The j-th inputs may have different scriptSigs and different witness lists; nothing else may differ. In particular the two transactions reference the same outpoints at the same positions, so the coins accessCoin(u,⋅) looked up for position j are the same for both.
Transaction identifier.txid(t)=SHA256(SHA256(ser0(t))) with
where LE4(x) is the 4-byte little-endian encoding of xmod232, LE8±(z) the 8-byte two's-complement little-endian encoding of zmod264, CS the CompactSize encoding, and the outpoint hash is written raw at whatever length it has. Witnesses never appear; every scriptSig appears with its length prefix. Under hI the serializations of tx and tx′ can differ only in the scriptSig fields (and their length prefixes), so the conclusion asserts the double-SHA-256 digests agree despite any such difference.
Lookup.accessCoin(u,o) is the coin of the first pair of u whose outpoint equals o, or the dummy coin ((−1,[]),0,false).
Witness program. For s of length k: defined iff 4≤k≤42, s0=0 or 0x51≤s0≤0x60, and s1+2=k; version 0 or s0−0x50; program s2…sk−1. hw says every input of tx (by membership) has a looked-up output script of this shape; since the empty script is not of this shape, every input's outpoint has an entry in u.
Input scripts OK for a transaction t with inputs [i0,…,im−1], cn=accessCoin(u,in.prevout), spent=[c0.out,…,cm−1.out]: for every 0≤n<m,
For h the context carries t=tx and for h′ it carries t=tx′ (the spending transaction enters signature hashing and lock-time checks through the context); spent is the same list for both.
verifyScript(T,c,σ,π,w): (1) evaluate σ (signature version base) on the empty stack; failure gives false; result Sσ; (2) evaluate π on Sσ; failure gives false; result S; false if S is empty or its top is not true (true iff some byte non-zero, except a string whose only non-zero byte is a final 0x80); (3) if c.flags.witness is on and isWitnessProgram(π)=(v,p): false if σ=[], else verifyWitnessProgram(T,c,w,v,p,false), final; (4) else if c.flags.p2sh is on and π=0xa90x14⟨20 bytes⟩0x87: σ must be push-only, Sσ non-empty with top r (the redeem script), r evaluated on the rest must succeed with a true top; then with the witness flag on: if r is a witness program (v,p), σ must equal pushBytes(r) and verifyWitnessProgram(T,c,w,v,p,true) decides, otherwise w must be empty; with the witness flag off, true; (5) else false if the witness flag is on and w=[], else true. Script evaluation is undefined if the script exceeds 10000 bytes or fails to parse, and otherwise is the Script interpreter's final stack under flags (cltv,csv,nulldummy) of c with the legacy oracle for (c.flags.dersig,c.tx,c.nIn,c.amount, signature version, script code). pushBytes(d) is the canonical push (∣d∣ as one byte then d if ∣d∣<0x4c; 0x4c/0x4d/0x4e with 1/2/4 little-endian length bytes otherwise). verifyWitnessProgram(T,c,w,v,p,isP2sh): v=0,∣p∣=32: last element of w must SHA-256 to p and is run as a witness-v0 script on the reversed remaining elements (all ≤520 bytes, exactly one element left, true); v=0,∣p∣=20: ∣w∣=2 and the implied P2PKH script is run on w reversed; v=0 other lengths: false; v=1,∣p∣=32, not P2SH: true if c.flags.taproot is off, else T(c,w,p); all other cases: true. Tspent(c,w,p): false on empty w; else strip an optional annex; one element: Schnorr key-path check against p over c.tx, spent, c.nIn; more: control block of length 33+32k (0≤k≤128) committing p to the leaf script, tapscript executed for leaf version 0xc0, true for other leaf versions.
Edge cases made explicit
If tx.vin=[] then by hI also tx′.vin=[]; h, h′, hw hold vacuously and tx=tx′ outright.
hw is asserted for tx only. Because hI makes the outpoint sequences of tx and tx′ identical, the looked-up scripts for tx′ are the same strings; but the statement does not itself assert SpendsWitnessPrograms(u,tx′).
hI allows tx and tx′ to differ in every scriptSig and every witness, including having different numbers of witness elements and non-empty versus empty scriptSigs; it forbids any difference elsewhere.
h and h′ each require every input to verify; both use the same ledger u and the same flags f; the amount passed to each context is the looked-up coin's value, −1 for a missing coin.
Any witness version 0–16 and program length 2–40 satisfies hw, including versions and lengths for which verifyWitnessProgram returns true without inspecting the witness.
txid reduces 32-bit fields modulo 232 and values modulo 264; outpoint hashes of any length are written raw.
The conclusion is equality of digests, not of transactions and not of witness-including identifiers; nothing is said about wtxid.
No constraint on f.p2sh, f.taproot, f.dersig, f.cltv, f.csv, f.nulldummy, on distinctness of ledger keys, on coinbase status, or on well-formedness is assumed.
Confirmed by the moderator at approval.