A P2SH-wrapped witness spend has the single push of its witness program as scriptSig
ProvedBitcoinMalleability.p2sh_wrapped_scriptSigFor VerifyScript with the P2SH and WITNESS flags, a P2SH scriptPubKey, a non-empty witness and a scriptSig on which it succeeds: the scriptSig evaluates to a stack whose top element redeem is a witness program, and the scriptSig is exactly the single push of redeem (SCRIPT_ERR_WITNESS_MALLEATED_P2SH otherwise). The scriptSig of a wrapped witness spend is therefore determined by the redeem script the output's hash commits to.
import Definitions.Def_BitcoinMalleability import Definitions.Def_BitcoinVerify import Definitions.Def_BitcoinSer import Definitions.Def_BitcoinSig open BitcoinMalleability BitcoinSer BitcoinBlockV2
theorem BitcoinMalleability.p2sh_wrapped_scriptSig (tap : BitcoinVerify.TaprootHandler) (c : BitcoinVerify.Ctx)
(sig spk : BitcoinSer.Bytes) (w : List BitcoinSer.Bytes) (hp : c.flags.p2sh = true) (hf : c.flags.witness = true)
(hspk : BitcoinVerify.isPayToScriptHash spk = true) (hw : w ≠ [])
(hv : BitcoinVerify.verifyScript tap c sig spk w = true) :
∃ redeem rest, BitcoinVerify.evalBytes c .base [] sig = some (redeem :: rest) ∧
BitcoinVerify.isWitnessProgram redeem ≠ none ∧ sig = BitcoinSig.pushBytes redeem := by sorryRead-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.p2sh_wrapped_scriptSig
Statement in words
For every Taproot handler , every verification context whose P2SH flag and witness flag are both on, every pair of byte strings (a scriptSig) and (a scriptPubKey) with of pay-to-script-hash shape, and every non-empty witness stack : if is true, then there exist a byte string and a list of byte strings such that evaluating on the empty stack yields the stack with on top and beneath, is a witness program, and is exactly the canonical single push of .
Binders and hypotheses
- : any function from (context, list of byte strings, byte string) to Booleans. It is not required to be the Taproot file's handler; it is an arbitrary handler.
- : a verification context : is a record of seven Booleans ; is a transaction; ; . The transaction, index and amount are arbitrary and are not linked to , or by any hypothesis (e.g. need not index an input of , and need not be the script of any coin).
- : byte strings (finite lists of 8-bit values).
- : a finite list of byte strings.
- : .
- : . The remaining five flags are unconstrained.
- : , i.e. , , , (the 20 middle bytes are arbitrary).
- : (at least one witness element; the elements themselves are arbitrary).
- : .
Conclusion
where ranges over byte strings and over lists of byte strings. "" is the stack whose top element is and whose remaining elements, top to bottom, are . The existential is plain existence, not uniqueness; is not asserted to be empty.
The notions, unfolded
Evaluation. ("evalBytes" with signature version ) is undefined if ; undefined if does not parse into a sequence of script instructions; otherwise it is the final stack (top first) of the Script interpreter run from the stack on the parsed , with interpreter flags and the legacy oracle built from , script code ; undefined if the interpreter fails. In the conclusion is base and . The first conjunct says this evaluation is defined and produces a non-empty stack.
Witness program. For of length , is defined iff , or , and ; it then yields version (if ) or (–) and program (length –). Note that itself, having first byte , is never a witness program under this definition.
Canonical push. is: the single byte followed by if ; , one byte , then if ; , two little-endian bytes of , then if ; else , four little-endian bytes of , then . For a witness program () this is the byte followed by , so the third conjunct says has length , first byte , and tail .
verifyScript is computed as:
- ; undefined gives false.
- ; undefined gives false; false if is empty or its top is not true under (true iff some byte is non-zero, except that a string whose only non-zero byte is a final is false).
- If is on and : false if , else , and this verdict is final. (Under this branch is not taken, since .)
- Otherwise, if is on and : false unless is push-only (every instruction parses and is a data push or an opcode ); false if ; otherwise write and compute ; false if undefined or if is empty or its top is not true; then, since is on: if then false unless , else ; if is not a witness program then false if , else true. (If the witness flag were off the P2SH path would end with true; here it is on.)
- Otherwise: false if is on and , else true.
verifyWitnessProgram : if and : false if is empty; else the last element of must satisfy and then "execute" on the reversed remaining elements; if and : false unless , else execute the implied script on reversed; with any other : false; , , : true if is off, else ; every other case (including with , which is the case reachable through the P2SH path, versions –, and pay-to-anchor): true. "Execute" with stack and script : false if any element of exceeds bytes; else must be defined, consist of exactly one element, and that element must be true.
Edge cases made explicit
- is arbitrary; under step 3 is not reachable, and inside the P2SH path is called with , in which the handler is never consulted; so does not influence .
- , , are unconstrained; they only enter through signature and lock-time checks inside script evaluation.
- requires only that be non-empty; its elements may be anything (for instance a single empty byte string).
- The conclusion fixes the top of and the shape of ; it does not assert , does not say which witness version or program length has (any version –, any program length – is possible under the definition), and does not say anything about , about 's middle 20 bytes, or about any hash relation between and .
- may be unsatisfiable for particular (for example when is not push-only, or when the middle bytes of do not match the hash of the pushed redeem script, in which case step 2 fails); for such inputs the implication holds vacuously.
- The five flags , , , , are unconstrained.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.