Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Transaction intent: the signature-free content of a transaction, and spends of native witness programs

Definition
BitcoinMalleability

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

bip141bitcoinbitcoin-mainnetconsensusformal-verificationlightningmalleabilitysegwittxid

Three names over the serialization mission's Tx, the block mission's ledger, and the VerifyScript mission's isWitnessProgram; nothing is re-transcribed.

Intent — a record of a version, a list of (outpoint, sequence number) pairs, a list of outputs, and a lock time: what the sender decides. scriptSigs and witnesses are not part of it.

intentOf tx — the intent of a transaction: its version, the (prevout, nSequence) of each input in order, its outputs, its lock time.

ofIntent t — the canonical transaction of an intent: the same fields, every scriptSig empty, every witness empty.

SpendsWitnessPrograms u tx — every input of tx spends, in the ledger u, an output whose scriptPubKey is a native witness program (CScript::IsWitnessProgram: OP_0 or OP_1..OP_16 followed by a single push of 2 to 40 bytes).

Formalization Note. txid is the serialization mission's double SHA-256 of the witness-stripped serialization; inputScriptsOk is the block mission's CheckInputScripts (the complete VerifyScript for every input against the spent outputs); verifyScript is the VerifyScript mission's dispatch. Only Std is imported.

Definition code
import Definitions.Def_BitcoinBlockV2
import Definitions.Def_BitcoinVerify

/-!
# Transaction identifiers under SegWit

The txid of a transaction hashes its witness-stripped serialization, which still contains every
`scriptSig`. Before SegWit a third party could alter a signature's encoding inside a `scriptSig`
and change the txid of a valid transaction without invalidating it. For an input that spends a
native witness program, `VerifyScript` requires the `scriptSig` to be empty
(`SCRIPT_ERR_WITNESS_MALLEATED`), so nothing a signer or a third party chooses remains in the
hashed bytes. This file names the sender's intent, the part of a transaction that is not a
signature, so that the theorems can say: for such spends the txid is a function of the intent.
-/

namespace BitcoinMalleability

open BitcoinSer BitcoinBlockV2

/-- What the sender decides: the version, the outpoint and sequence number of every input, the
outputs, and the lock time. The `scriptSig`s and witnesses are not part of it. -/
structure Intent where
  version : Nat
  inputs : List (OutPoint × Nat)
  vout : List TxOut
  nLockTime : Nat
  deriving DecidableEq, Repr

/-- The intent of a transaction. -/
def intentOf (tx : Tx) : Intent :=
  ⟨tx.version, tx.vin.map fun i => (i.prevout, i.nSequence), tx.vout, tx.nLockTime⟩

/-- The canonical transaction of an intent: empty `scriptSig`s and empty witnesses. -/
def ofIntent (t : Intent) : Tx :=
  ⟨t.version, t.inputs.map fun p => ⟨p.1, [], p.2, []⟩, t.vout, t.nLockTime⟩

/-- Every input of `tx` spends, in the ledger `u`, an output whose script is a native witness
program (`CScript::IsWitnessProgram`). -/
def SpendsWitnessPrograms (u : Ledger) (tx : Tx) : Prop :=
  ∀ i ∈ tx.vin, BitcoinVerify.isWitnessProgram (accessCoin u i.prevout).out.scriptPubKey ≠ none

end BitcoinMalleability
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: Def_BitcoinMalleability.lean

The file declares one structure and three definitions, inside a namespace BitcoinMalleability, on top of the transaction and ledger types of the imported files. The notions those declarations use are unfolded first; then each declaration is read back, in file order.

Imported notions, unfolded

  • A byte is an 8-bit value; a byte string is a finite list of bytes (possibly empty).

  • An outpoint is a pair (h,n)(h, n)(h,n) with hhh a byte string (of any length; no 32-byte constraint is part of the type) and n∈Nn \in \mathbb Nn∈N (no 2322^{32}232 bound is part of the type).

  • A transaction input is a quadruple (prevout,scriptSig,nSequence,witness)(\mathrm{prevout}, \mathrm{scriptSig}, \mathrm{nSequence}, \mathrm{witness})(prevout,scriptSig,nSequence,witness): an outpoint, a byte string, a natural number, and a list of byte strings.

  • A transaction output is a pair (nValue,scriptPubKey)(\mathrm{nValue}, \mathrm{scriptPubKey})(nValue,scriptPubKey) with nValue∈Z\mathrm{nValue} \in \mathbb ZnValue∈Z (any integer) and scriptPubKey\mathrm{scriptPubKey}scriptPubKey a byte string.

  • A transaction tx\mathrm{tx}tx is a quadruple (version,vin,vout,nLockTime)(\mathrm{version}, \mathrm{vin}, \mathrm{vout}, \mathrm{nLockTime})(version,vin,vout,nLockTime): a natural number, a list of inputs, a list of outputs, a natural number. Nothing in the type requires vin\mathrm{vin}vin or vout\mathrm{vout}vout to be non-empty or any field to be in range.

  • A coin is a triple (out,height,isCoinbase)(\mathrm{out}, \mathrm{height}, \mathrm{isCoinbase})(out,height,isCoinbase): an output, a natural number, a Boolean. The dummy coin is ((−1,[ ]),0,false)\big((-1, [\,]), 0, \mathrm{false}\big)((−1,[]),0,false): value −1-1−1, empty script.

  • A ledger uuu is a finite list of pairs (outpoint, coin). It is an association list; keys are not required to be distinct and the order matters for lookup.

  • getCoin(u,o)\mathrm{getCoin}(u, o)getCoin(u,o) walks uuu from the front and returns the coin of the first pair whose outpoint equals ooo exactly (same hash bytes, same index), or nothing if no pair matches.

  • accessCoin(u,o)\mathrm{accessCoin}(u, o)accessCoin(u,o) is getCoin(u,o)\mathrm{getCoin}(u,o)getCoin(u,o) when it exists, and otherwise the dummy coin. In particular, for an outpoint absent from uuu, accessCoin(u,o).out.scriptPubKey=[ ]\mathrm{accessCoin}(u,o).\mathrm{out}.\mathrm{scriptPubKey} = [\,]accessCoin(u,o).out.scriptPubKey=[] and accessCoin(u,o).out.nValue=−1\mathrm{accessCoin}(u,o).\mathrm{out}.\mathrm{nValue} = -1accessCoin(u,o).out.nValue=−1.

  • isWitnessProgram(s)\mathrm{isWitnessProgram}(s)isWitnessProgram(s), for a byte string s=s0s1…sk−1s = s_0 s_1 \ldots s_{k-1}s=s0​s1​…sk−1​ of length kkk, is defined (returns a pair) exactly when all three hold:

    1. 4≤k≤424 \le k \le 424≤k≤42;
    2. s0=0s_0 = 0s0​=0, or 0x51≤s0≤0x60\mathrm{0x51} \le s_0 \le \mathrm{0x60}0x51≤s0​≤0x60;
    3. s1+2=ks_1 + 2 = ks1​+2=k (so 2≤s1≤402 \le s_1 \le 402≤s1​≤40).

    When defined, it returns (version,program)(\mathrm{version}, \mathrm{program})(version,program) with version=0\mathrm{version} = 0version=0 if s0=0s_0 = 0s0​=0 and version=s0−0x50\mathrm{version} = s_0 - \mathrm{0x50}version=s0​−0x50 otherwise (so 0≤version≤160 \le \mathrm{version} \le 160≤version≤16), and program=s2…sk−1\mathrm{program} = s_2 \ldots s_{k-1}program=s2​…sk−1​. Otherwise it is undefined ("none"). Note that the empty string and every string of length <4< 4<4 are not witness programs.

Declaration 1: structure Intent

An intent is a record with exactly four fields and no constraints between them:

t=(version, inputs, vout, nLockTime)t = (\mathrm{version},\ \mathrm{inputs},\ \mathrm{vout},\ \mathrm{nLockTime})t=(version, inputs, vout, nLockTime)

where version∈N\mathrm{version} \in \mathbb Nversion∈N; inputs\mathrm{inputs}inputs is a finite list of pairs (o,q)(o, q)(o,q) with ooo an outpoint and q∈Nq \in \mathbb Nq∈N; vout\mathrm{vout}vout is a finite list of transaction outputs (nValue∈Z,scriptPubKey)(\mathrm{nValue} \in \mathbb Z, \mathrm{scriptPubKey})(nValue∈Z,scriptPubKey); and nLockTime∈N\mathrm{nLockTime} \in \mathbb NnLockTime∈N. Equality of intents is decidable and is field-wise equality: two intents are equal if and only if their versions are equal, their input lists are equal as lists (same length, same pairs in the same order), their output lists are equal as lists, and their lock times are equal. There is no field for script signatures, witnesses, or any ledger. The lists may be empty; there are no range bounds on any natural number and no length bound on any byte string. Nothing in the structure refers to a transaction.

Declaration 2: intentOf

For a transaction tx=(v,vin,vout,ℓ)\mathrm{tx} = (v, \mathrm{vin}, \mathrm{vout}, \ell)tx=(v,vin,vout,ℓ) with vin=[i1,…,im]\mathrm{vin} = [i_1, \ldots, i_m]vin=[i1​,…,im​],

intentOf(tx)=(v, [(i1.prevout,i1.nSequence),…,(im.prevout,im.nSequence)], vout, ℓ).\mathrm{intentOf}(\mathrm{tx}) = \big(v,\ [(i_1.\mathrm{prevout}, i_1.\mathrm{nSequence}), \ldots, (i_m.\mathrm{prevout}, i_m.\mathrm{nSequence})],\ \mathrm{vout},\ \ell\big).intentOf(tx)=(v, [(i1​.prevout,i1​.nSequence),…,(im​.prevout,im​.nSequence)], vout, ℓ).

That is: the version is copied; each input is replaced by the pair of its outpoint and its sequence number, in the same order and with the same multiplicity (duplicates are kept); the output list is copied unchanged (values and scripts included); the lock time is copied. The fields scriptSig\mathrm{scriptSig}scriptSig and witness\mathrm{witness}witness of every input are discarded. Consequently, two transactions have the same intent if and only if they have the same version, the same number of inputs with pairwise equal outpoints and sequence numbers, identical output lists, and the same lock time; they may differ arbitrarily in the scriptSig\mathrm{scriptSig}scriptSig and witness\mathrm{witness}witness of each input. For a transaction with no inputs, the intent's input list is empty. No ledger is involved and no validity is checked.

Declaration 3: ofIntent

For an intent t=(v,[(o1,q1),…,(om,qm)],vout,ℓ)t = (v, [(o_1, q_1), \ldots, (o_m, q_m)], \mathrm{vout}, \ell)t=(v,[(o1​,q1​),…,(om​,qm​)],vout,ℓ),

ofIntent(t)=(v, [(o1,[ ],q1,[ ]),…,(om,[ ],qm,[ ])], vout, ℓ),\mathrm{ofIntent}(t) = \big(v,\ [(o_1, [\,], q_1, [\,]), \ldots, (o_m, [\,], q_m, [\,])],\ \mathrm{vout},\ \ell\big),ofIntent(t)=(v, [(o1​,[],q1​,[]),…,(om​,[],qm​,[])], vout, ℓ),

a transaction whose version is vvv, whose jjj-th input has outpoint ojo_joj​, empty scriptSig\mathrm{scriptSig}scriptSig, sequence number qjq_jqj​ and empty witness list, whose outputs are exactly vout\mathrm{vout}vout, and whose lock time is ℓ\ellℓ. By construction intentOf(ofIntent(t))=t\mathrm{intentOf}(\mathrm{ofIntent}(t)) = tintentOf(ofIntent(t))=t for every intent ttt, and for every transaction tx\mathrm{tx}tx, ofIntent(intentOf(tx))\mathrm{ofIntent}(\mathrm{intentOf}(\mathrm{tx}))ofIntent(intentOf(tx)) is tx\mathrm{tx}tx with every input's scriptSig\mathrm{scriptSig}scriptSig replaced by the empty byte string and every input's witness replaced by the empty list, all other data unchanged. No validity, well-formedness or ledger condition is imposed.

Declaration 4: SpendsWitnessPrograms

For a ledger uuu and a transaction tx\mathrm{tx}tx, the proposition SpendsWitnessPrograms(u,tx)\mathrm{SpendsWitnessPrograms}(u, \mathrm{tx})SpendsWitnessPrograms(u,tx) states:

∀ i∈tx.vin:isWitnessProgram(accessCoin(u,i.prevout).out.scriptPubKey) is defined.\forall\, i \in \mathrm{tx}.\mathrm{vin}:\quad \mathrm{isWitnessProgram}\big(\mathrm{accessCoin}(u, i.\mathrm{prevout}).\mathrm{out}.\mathrm{scriptPubKey}\big) \text{ is defined}.∀i∈tx.vin:isWitnessProgram(accessCoin(u,i.prevout).out.scriptPubKey) is defined.

Unfolded: for every input iii that occurs in the input list of tx\mathrm{tx}tx (membership, so position and repetition are irrelevant), let sss be the output script of the first ledger entry whose outpoint equals i.prevouti.\mathrm{prevout}i.prevout, or the empty string if there is no such entry; then 4≤∣s∣≤424 \le |s| \le 424≤∣s∣≤42, the first byte of sss is 000 or lies in [0x51,0x60][\mathrm{0x51}, \mathrm{0x60}][0x51,0x60], and the second byte of sss equals ∣s∣−2|s| - 2∣s∣−2. Edge cases: if tx.vin\mathrm{tx}.\mathrm{vin}tx.vin is empty the proposition holds vacuously; since the empty string is not a witness program, the proposition fails for any input whose outpoint has no entry in uuu, so it entails that every input's outpoint is a key of uuu; any witness version 000 to 161616 and any program length 222 to 404040 is accepted, with no distinction among P2WPKH, P2WSH, Taproot or unknown versions; nothing is said about the inputs' scriptSig\mathrm{scriptSig}scriptSig, witness, sequence number, about coinbase status, about duplicate keys in uuu (only the first match counts), or about the transaction's outputs.

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