Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

An input spending a native witness program has an empty scriptSig when its script verifies

Proved
BitcoinMalleability.native_scriptSig_empty

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

bip141bitcoinbitcoin-mainnetconsensusformal-verificationlightningmalleabilitysegwittxid

For script flags with WITNESS set, a ledger uuu and a transaction whose CheckInputScripts succeeds: every input whose spent output is a native witness program has scriptSig = []. (VerifyScript returns SCRIPT_ERR_WITNESS_MALLEATED otherwise; the VerifyScript mission's native_witness_malleated lifted to the block mission's per-input loop.)

Preamble
import Definitions.Def_BitcoinMalleability
import Definitions.Def_BitcoinActivation
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinVerify
open BitcoinMalleability BitcoinSer BitcoinBlockV2
Formal statement
theorem BitcoinMalleability.native_scriptSig_empty (f : BitcoinActivation.ScriptFlags) (u : Ledger)
    (tx : BitcoinSer.Tx) (hf : f.witness = true) (h : BitcoinBlockV2.inputScriptsOk f u tx = true) :
    ∀ i ∈ tx.vin, BitcoinVerify.isWitnessProgram (BitcoinBlockV2.accessCoin u i.prevout).out.scriptPubKey ≠ none →
      i.scriptSig = [] := 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.native_scriptSig_empty

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 and every input script of tx\mathrm{tx}tx verifies against uuu under fff (in the sense of inputScriptsOk\mathrm{inputScriptsOk}inputScriptsOk, unfolded below), then every input iii occurring in tx.vin\mathrm{tx}.\mathrm{vin}tx.vin whose spent output script (looked up in uuu) is a witness program has an empty scriptSig\mathrm{scriptSig}scriptSig.

Binders and hypotheses

Universally quantified, with no other constraints than those listed:

  • 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). Only witness\mathrm{witness}witness is constrained (below); the other six are arbitrary.
  • uuu: a ledger, i.e. a finite association list of pairs (outpoint, coin), where an outpoint is (h,n)(h, n)(h,n) with hhh a byte string of any length and n∈Nn \in \mathbb Nn∈N, and 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), where each input is (prevout,scriptSig,nSequence,witness)(\mathrm{prevout}, \mathrm{scriptSig}, \mathrm{nSequence}, \mathrm{witness})(prevout,scriptSig,nSequence,witness) (outpoint, byte string, natural number, list of byte strings) and each output is (nValue∈Z,scriptPubKey)(\mathrm{nValue} \in \mathbb Z, \mathrm{scriptPubKey})(nValue∈Z,scriptPubKey). No well-formedness is assumed.
  • Hypothesis hfh_fhf​: f.witness=truef.\mathrm{witness} = \mathrm{true}f.witness=true.
  • Hypothesis hhh: inputScriptsOk(f,u,tx)=true\mathrm{inputScriptsOk}(f, u, \mathrm{tx}) = \mathrm{true}inputScriptsOk(f,u,tx)=true.

Conclusion

∀ i∈tx.vin:isWitnessProgram(accessCoin(u,i.prevout).out.scriptPubKey) is defined  ⟹  i.scriptSig=[ ].\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} \;\Longrightarrow\; i.\mathrm{scriptSig} = [\,].∀i∈tx.vin:isWitnessProgram(accessCoin(u,i.prevout).out.scriptPubKey) is defined⟹i.scriptSig=[].

Membership "i∈tx.vini \in \mathrm{tx}.\mathrm{vin}i∈tx.vin" is list membership: the input equals some element of the list (its position does not matter).

The notions, unfolded

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

Witness program. For a byte string sss of length kkk, isWitnessProgram(s)\mathrm{isWitnessProgram}(s)isWitnessProgram(s) is defined iff 4≤k≤424 \le k \le 424≤k≤42, the first byte s0s_0s0​ is 000 or in [0x51,0x60][\mathrm{0x51}, \mathrm{0x60}][0x51,0x60], and s1+2=ks_1 + 2 = ks1​+2=k; it then yields (version,program)(\mathrm{version}, \mathrm{program})(version,program) with version=0\mathrm{version} = 0version=0 if s0=0s_0 = 0s0​=0 else s0−0x50s_0 - \mathrm{0x50}s0​−0x50, and program=s2…sk−1\mathrm{program} = s_2 \ldots s_{k-1}program=s2​…sk−1​ (length 222 to 404040). The empty string is not a witness program, so the conclusion's antecedent fails for any input whose outpoint is absent from uuu.

Input scripts OK. Let vin=[i0,…,im−1]\mathrm{vin} = [i_0, \ldots, i_{m-1}]vin=[i0​,…,im−1​] and spent=[accessCoin(u,i0.prevout).out,…,accessCoin(u,im−1.prevout).out]\mathrm{spent} = [\mathrm{accessCoin}(u, i_0.\mathrm{prevout}).\mathrm{out}, \ldots, \mathrm{accessCoin}(u, i_{m-1}.\mathrm{prevout}).\mathrm{out}]spent=[accessCoin(u,i0​.prevout).out,…,accessCoin(u,im−1​.prevout).out]. Then inputScriptsOk(f,u,tx)=true\mathrm{inputScriptsOk}(f,u,\mathrm{tx}) = \mathrm{true}inputScriptsOk(f,u,tx)=true means: for every index nnn with 0≤n<m0 \le n < m0≤n<m, writing cn=accessCoin(u,in.prevout)c_n = \mathrm{accessCoin}(u, i_n.\mathrm{prevout})cn​=accessCoin(u,in​.prevout),

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 (f,tx,n,a)(f, \mathrm{tx}, n, a)(f,tx,n,a) is a verification context (flags, spending transaction, input index, amount a∈Za \in \mathbb Za∈Z; for a missing coin, a=−1a = -1a=−1), and TspentT_{\mathrm{spent}}Tspent​ is the Taproot handler of the Taproot file for the spent-output list (described below). When m=0m = 0m=0 the condition is vacuously true.

verifyScript (T,c,σ,π,w)(T, c, \sigma, \pi, w)(T,c,σ,π,w) for a handler TTT, context ccc, scriptSig σ\sigmaσ, scriptPubKey π\piπ and witness stack www (a list of byte strings in serialized order, last element on top) is the Boolean computed as follows:

  1. Evaluate σ\sigmaσ with signature version base on the empty stack: Ecbase([ ],σ)E_c^{\mathrm{base}}([\,], \sigma)Ecbase​([],σ). If this fails, the result is false; otherwise let SσS_\sigmaSσ​ be the resulting stack (top first).
  2. Evaluate π\piπ on SσS_\sigmaSσ​: Ecbase(Sσ,π)E_c^{\mathrm{base}}(S_\sigma, \pi)Ecbase​(Sσ​,π). If this fails, false; otherwise let SSS be the resulting stack. If SSS is empty or its top element is "false" under castToBool\mathrm{castToBool}castToBool (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), the result is false.
  3. Native witness branch, taken only 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) is defined: the result is false if σ≠[ ]\sigma \ne [\,]σ=[], and otherwise is 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). This verdict is final.
  4. Otherwise, if c.flags.p2shc.\mathrm{flags}.\mathrm{p2sh}c.flags.p2sh is on and π\piπ is pay-to-script-hash (∣π∣=23|\pi| = 23∣π∣=23, π0=0xa9\pi_0 = \mathrm{0xa9}π0​=0xa9, π1=0x14\pi_1 = \mathrm{0x14}π1​=0x14, π22=0x87\pi_{22} = \mathrm{0x87}π22​=0x87): false unless σ\sigmaσ is push-only (every instruction of σ\sigmaσ parses and is a data push or an opcode ≤0x60\le \mathrm{0x60}≤0x60); false if SσS_\sigmaSσ​ is empty; otherwise with Sσ=r::restS_\sigma = r :: \mathrm{rest}Sσ​=r::rest (rrr the top), evaluate Ecbase(rest,r)E_c^{\mathrm{base}}(\mathrm{rest}, r)Ecbase​(rest,r); false on failure or on a non-true top; then, if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness is on and isWitnessProgram(r)=(v,p)\mathrm{isWitnessProgram}(r) = (v, p)isWitnessProgram(r)=(v,p): false unless σ=pushBytes(r)\sigma = \mathrm{pushBytes}(r)σ=pushBytes(r), else verifyWitnessProgram(T,c,w,v,p,true)\mathrm{verifyWitnessProgram}(T, c, w, v, p, \mathrm{true})verifyWitnessProgram(T,c,w,v,p,true); if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness is on and rrr is not a witness program: false if w≠[ ]w \ne [\,]w=[], else true; if the witness flag is off: true.
  5. Otherwise (neither branch): false if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness is on and w≠[ ]w \ne [\,]w=[]; else true.

Here Ecv(S,s)E_c^{v}(S, s)Ecv​(S,s) ("evalBytes") is: undefined if ∣s∣>10000|s| > 10000∣s∣>10000; undefined if sss does not parse into a sequence of script instructions; otherwise the final stack (top first) of the Script interpreter run from stack SSS on the parsed sss, with interpreter 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) and the legacy signature/lock-time oracle built from (c.flags.dersig(c.\mathrm{flags}.\mathrm{dersig}(c.flags.dersig, c.txc.\mathrm{tx}c.tx, c.nInc.\mathrm{nIn}c.nIn, c.amountc.\mathrm{amount}c.amount, vvv, script code s)s)s); undefined if the interpreter fails. pushBytes(d)\mathrm{pushBytes}(d)pushBytes(d) is the canonical push of ddd: a length byte then ddd if ∣d∣<0x4c|d| < \mathrm{0x4c}∣d∣<0x4c; 0x4c\mathrm{0x4c}0x4c, one length byte, ddd if ∣d∣≤0xff|d| \le \mathrm{0xff}∣d∣≤0xff; 0x4d\mathrm{0x4d}0x4d, two little-endian length bytes, ddd if ∣d∣≤0xffff|d| \le \mathrm{0xffff}∣d∣≤0xffff; else 0x4e\mathrm{0x4e}0x4e, four little-endian length bytes, ddd.

verifyWitnessProgram (T,c,w,v,p,isP2sh)(T, c, w, v, p, \mathrm{isP2sh})(T,c,w,v,p,isP2sh): if v=0v = 0v=0 and ∣p∣=32|p| = 32∣p∣=32: false if www is empty; else with sss the last element of www, false if SHA256(s)≠p\mathrm{SHA256}(s) \ne pSHA256(s)=p, else "execute witness script" with the reversed remaining elements as stack and script sss. If v=0v = 0v=0 and ∣p∣=20|p| = 20∣p∣=20: false unless ∣w∣=2|w| = 2∣w∣=2, else execute with stack www reversed and the implied script 0x76 0xa9 pushBytes(p) 0x88 0xac\mathrm{0x76}\,\mathrm{0xa9}\,\mathrm{pushBytes}(p)\,\mathrm{0x88}\,\mathrm{0xac}0x760xa9pushBytes(p)0x880xac. If v=0v = 0v=0 and ∣p∣∉{20,32}|p| \notin \{20, 32\}∣p∣∈/{20,32}: false. If v=1v = 1v=1, ∣p∣=32|p| = 32∣p∣=32 and isP2sh=false\mathrm{isP2sh} = \mathrm{false}isP2sh=false: true when c.flags.taprootc.\mathrm{flags}.\mathrm{taproot}c.flags.taproot is off, else T(c,w,p)T(c, w, p)T(c,w,p). Every other case (other versions, version-1 programs of other lengths, version 1 inside P2SH, pay-to-anchor) is true. "Execute witness script" with stack SSS and script sss is: false if any element of SSS exceeds 520520520 bytes; else EcwitnessV0(S,s)E_c^{\mathrm{witnessV0}}(S, s)EcwitnessV0​(S,s) must be defined, leave exactly one element, and that element must be true.

The Taproot handler Tspent(c,w,p)T_{\mathrm{spent}}(c, w, p)Tspent​(c,w,p): false if www is empty; otherwise an annex (a last element starting with byte 0x50\mathrm{0x50}0x50 when ∣w∣≥2|w| \ge 2∣w∣≥2) is split off; if one element remains it is checked as a Schnorr key-path signature for ppp over c.txc.\mathrm{tx}c.tx, spent\mathrm{spent}spent and c.nInc.\mathrm{nIn}c.nIn; otherwise the last element is a control block whose length must be 33+32k33 + 32k33+32k for some 0≤k≤1280 \le k \le 1280≤k≤128, the element before it is the leaf script, the control block must commit ppp to the leaf, and for leaf version 0xc0\mathrm{0xc0}0xc0 the tapscript is executed on the remaining elements with a validation-weight budget; other leaf versions give true. (The handler is consulted only in the case v=1v = 1v=1, ∣p∣=32|p| = 32∣p∣=32, not P2SH, taproot flag on.)

Edge cases made explicit

  • If tx.vin\mathrm{tx}.\mathrm{vin}tx.vin is empty, both hhh and the conclusion hold vacuously.
  • The hypothesis hhh ranges over inputs by position nnn (with the amount and context index nnn), while the conclusion ranges over inputs by membership; an input occurring twice in vin\mathrm{vin}vin is verified at both positions.
  • hhh requires every input to verify, including inputs spending non-witness-program outputs and inputs whose outpoint is absent from uuu (then the output script is [ ][\,][] and the amount is −1-1−1); the conclusion speaks only of inputs whose looked-up script is a witness program.
  • Any witness version 000–161616 and program length 222–404040 counts as a witness program in the conclusion.
  • No well-formedness of tx\mathrm{tx}tx or uuu, no distinctness of ledger keys, no coinbase exclusion, and no constraint on 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 is assumed.
  • The statement says nothing about witnesses, sequence numbers, outputs, or the transaction identifier.
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