VerifyScript: P2SH, native and wrapped SegWit v0, unknown witness versions, and the taproot hand-off
DefinitionBitcoinVerifyContext and flags. A Ctx is the spending transaction, the input index, the amount spent and the consensus flag set (BitcoinActivation.ScriptFlags, the output of GetBlockScriptFlags); scriptFlagsOf and sigFlagsOf project the interpreter and signature-layer flags (DERSIG is the only signature flag on mainnet). .
Byte-level evaluation. evalBytes ctx v stack script is EvalScript on a byte string: the size test, the GetOp parse (none on a malformed push), and the Script mission's interpreter with the concrete oracle of the signature mission for signature version v and this script code.
Predicates. isPayToScriptHash is CScript::IsPayToScriptHash (23 bytes a9 14 … 87); isWitnessProgram is IsWitnessProgram (OP_0/OP_1..16 then one push of 2–40 bytes, nothing else; returns the version and program); isPushOnly is IsPushOnly (every instruction parses and has opcode at most OP_16); isPayToAnchor is the version-1 two-byte 4e73 program; topTrue is CastToBool of the top, false on an empty stack.
Witness execution. executeWitnessScriptV0 is ExecuteWitnessScript for version 0: every element within 520 bytes, the script run under WITNESS_V0, exactly one element left and it true. verifyWitnessProgram is VerifyWitnessProgram: version 0 with a 32-byte program is P2WSH (last witness element is the script, its SHA-256 must equal the program, the rest is the initial stack), with a 20-byte program is P2WPKH (exactly two elements, the implied DUP HASH160 <program> EQUALVERIFY CHECKSIG), other lengths fail; version 1 with a 32-byte program outside P2SH is Taproot, delegated to the TaprootHandler parameter when the TAPROOT flag is set and accepted otherwise; pay-to-anchor and every other version/size combination succeed. Witness stacks are in CScriptWitness order (last element on top), reversed into the interpreter's top-first stacks.
verifyScript is VerifyScript with the consensus flags: the scriptSig and then the output script on the same stack, a true top; with WITNESS, a witness-program output requires an empty scriptSig and runs the program; with P2SH, a P2SH output requires a push-only scriptSig, restores the scriptSig's stack, pops the serialized redeem script and runs it, requires a true top, and, with WITNESS, a witness-program redeem script requires the scriptSig to be exactly its single push and runs the program as P2SH-wrapped; finally, with WITNESS, a non-empty witness that nothing consumed fails. SIGPUSHONLY and CLEANSTACK are policy and off.
Templates. p2shBytes h, witnessBytes v program, pushesBytes (a push-only scriptSig), p2wpkhExec.
Formalization Note. Policy flags are off; the Taproot branch is a parameter supplied by the Taproot development; the oracle's script code is the executed script, exact for scripts without OP_CODESEPARATOR. Only Std is imported.
import Std
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinScript
import Definitions.Def_BitcoinSig
import Definitions.Def_BitcoinActivation
namespace BitcoinVerify
/-! Transcription of `VerifyScript`, `VerifyWitnessProgram` (witness version 0, unknown versions,
pay-to-anchor) and `ExecuteWitnessScript` of `script/interpreter.cpp`, and `IsPayToScriptHash`,
`IsWitnessProgram`, `IsPushOnly`, `IsPayToAnchor` of `script/script.cpp`, at Bitcoin Core revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`, with the mainnet consensus flag set of
`GetBlockScriptFlags` (`BitcoinActivation.ScriptFlags`). The Taproot (version 1, 32-byte, non-P2SH)
branch is a parameter `taproot`, supplied by the Taproot development. -/
open BitcoinSer (Byte Bytes Tx)
open BitcoinSig (SigVersion)
/-- `MAX_SCRIPT_SIZE = 10000`. -/
def MAX_SCRIPT_SIZE : Nat := 10000
def WITNESS_V0_SCRIPTHASH_SIZE : Nat := 32
def WITNESS_V0_KEYHASH_SIZE : Nat := 20
def WITNESS_V1_TAPROOT_SIZE : Nat := 32
/-- The interpreter flags carried by the consensus flag set. -/
def scriptFlagsOf (f : BitcoinActivation.ScriptFlags) : BitcoinScript.Flags := ⟨f.cltv, f.csv, f.nulldummy⟩
/-- The signature-layer flags: `DERSIG` is the only consensus one; the policy flags are off. -/
def sigFlagsOf (f : BitcoinActivation.ScriptFlags) : BitcoinSig.SigFlags := ⟨f.dersig, false, false, false⟩
/-- The context of one script verification: the spending transaction, the input index and the amount
spent (`-1` where unknown, as for legacy inputs validated without amounts). -/
structure Ctx where
flags : BitcoinActivation.ScriptFlags
tx : Tx
nIn : Nat
amount : Int
/-- `EvalScript(stack, script, flags, checker, sigversion)` on a byte-level script: the
`MAX_SCRIPT_SIZE` test, the `GetOp` parse, and the Script mission's interpreter with the concrete
oracle for this script code. `stack` is top-first. -/
def evalBytes (c : Ctx) (v : SigVersion) (stack : List Bytes) (script : Bytes) : Option (List Bytes) :=
if MAX_SCRIPT_SIZE < script.length then none
else match BitcoinSig.parseScript script with
| none => none
| some s =>
BitcoinScript.evalScript (scriptFlagsOf c.flags)
(BitcoinSig.legacyOracle (sigFlagsOf c.flags) c.tx c.nIn c.amount v script) stack s
/-- `CScript::IsPayToScriptHash`: `OP_HASH160 <20 bytes> OP_EQUAL`, 23 bytes. -/
def isPayToScriptHash (s : Bytes) : Bool :=
decide (s.length = 23) && decide ((s.getD 0 0).toNat = 0xa9) && decide ((s.getD 1 0).toNat = 0x14) &&
decide ((s.getD 22 0).toNat = 0x87)
/-- `DecodeOP_N`. -/
def decodeOpN (b : Nat) : Nat := if b = 0 then 0 else b - 0x50
/-- `CScript::IsWitnessProgram`: `OP_0`/`OP_1..OP_16`, a direct push of 2..40 bytes, nothing else. -/
def isWitnessProgram (s : Bytes) : Option (Nat × Bytes) :=
if s.length < 4 ∨ 42 < s.length then none
else
let b0 := (s.getD 0 0).toNat
if b0 ≠ 0 ∧ (b0 < 0x51 ∨ 0x60 < b0) then none
else if (s.getD 1 0).toNat + 2 = s.length then some (decodeOpN b0, s.drop 2)
else none
/-- `CScript::IsPushOnly`: every instruction parses and is a push or `OP_RESERVED`/`OP_1NEGATE`/`OP_n`
(opcode at most `OP_16`). -/
def isPushOnlyAux : Nat → Bytes → Bool
| _, [] => true
| 0, _ => false
| fuel + 1, s =>
match BitcoinSig.getOp s with
| none => false
| some (.push _, r) => isPushOnlyAux fuel r
| some (.op c, r) => if BitcoinScript.OP_16 < c then false else isPushOnlyAux fuel r
def isPushOnly (s : Bytes) : Bool := isPushOnlyAux s.length s
/-- `CScript::IsPayToAnchor(version, program)`. -/
def isPayToAnchor (version : Nat) (program : Bytes) : Bool :=
decide (version = 1) && decide (program = [0x4e, 0x73])
/-- `CastToBool` of the top of a top-first stack; an empty stack is `false` (`SCRIPT_ERR_EVAL_FALSE`). -/
def topTrue (stack : List Bytes) : Bool :=
match stack with
| [] => false
| top :: _ => BitcoinScript.castToBool top
/-- `ExecuteWitnessScript` for witness version 0: every witness element within
`MAX_SCRIPT_ELEMENT_SIZE`, the script run with `SigVersion::WITNESS_V0`, exactly one element left,
and it true. `stack` is top-first. -/
def executeWitnessScriptV0 (c : Ctx) (stack : List Bytes) (exec : Bytes) : Bool :=
if stack.any (fun e => BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE < e.length) then false
else match evalBytes c .witnessV0 stack exec with
| none => false
| some st => decide (st.length = 1) && topTrue st
/-- The implied P2WPKH script `OP_DUP OP_HASH160 <program> OP_EQUALVERIFY OP_CHECKSIG`. -/
def p2wpkhExec (program : Bytes) : Bytes := BitcoinSig.p2pkhBytes program
/-- A Taproot handler: given the witness stack (in `CScriptWitness` order, last element on top)
and the 32-byte program, the verdict of the BIP341 branch. -/
abbrev TaprootHandler := Ctx → List Bytes → Bytes → Bool
/-- `VerifyWitnessProgram(witness, witversion, program, flags, checker, is_p2sh)`. The witness
stack is in `CScriptWitness` order (last element on top). -/
def verifyWitnessProgram (tap : TaprootHandler) (c : Ctx) (witness : List Bytes) (version : Nat)
(program : Bytes) (isP2sh : Bool) : Bool :=
if version = 0 then
if program.length = WITNESS_V0_SCRIPTHASH_SIZE then
-- P2WSH: the last element is the script, its SHA-256 must be the program
match witness.getLast? with
| none => false
| some script =>
if BitcoinSer.sha256 script ≠ program then false
else executeWitnessScriptV0 c witness.dropLast.reverse script
else if program.length = WITNESS_V0_KEYHASH_SIZE then
if witness.length ≠ 2 then false
else executeWitnessScriptV0 c witness.reverse (p2wpkhExec program)
else false
else if version = 1 ∧ program.length = WITNESS_V1_TAPROOT_SIZE ∧ !isP2sh then
if !c.flags.taproot then true else tap c witness program
else if !isP2sh && isPayToAnchor version program then true
else true
/-- `VerifyScript(scriptSig, scriptPubKey, witness, flags, checker)` with the consensus flags
(`SIGPUSHONLY` and `CLEANSTACK` are policy and off). -/
def verifyScript (tap : TaprootHandler) (c : Ctx) (scriptSig scriptPubKey : Bytes) (witness : List Bytes) : Bool :=
match evalBytes c .base [] scriptSig with
| none => false
| some stackSig =>
match evalBytes c .base stackSig scriptPubKey with
| none => false
| some stack =>
if !topTrue stack then false
else
-- bare witness programs
let native : Option Bool :=
if c.flags.witness then
match isWitnessProgram scriptPubKey with
| some (version, program) =>
if scriptSig ≠ [] then some false
else some (verifyWitnessProgram tap c witness version program false)
| none => none
else none
match native with
| some false => false
| some true => true
| none =>
if c.flags.p2sh && isPayToScriptHash scriptPubKey then
if !isPushOnly scriptSig then false
else
match stackSig with
| [] => false
| redeem :: rest =>
match evalBytes c .base rest redeem with
| none => false
| some stack2 =>
if !topTrue stack2 then false
else
if c.flags.witness then
match isWitnessProgram redeem with
| some (version, program) =>
if scriptSig ≠ BitcoinSig.pushBytes redeem then false
else verifyWitnessProgram tap c witness version program true
| none => if c.flags.witness && !witness.isEmpty then false else true
else true
else if c.flags.witness && !witness.isEmpty then false
else true
/-- The P2SH output script `OP_HASH160 <h> OP_EQUAL`. -/
def p2shBytes (h : Bytes) : Bytes := [0xa9] ++ BitcoinSig.pushBytes h ++ [0x87]
/-- A witness output script `OP_n <program>`. -/
def witnessBytes (version : Nat) (program : Bytes) : Bytes :=
BitVec.ofNat 8 (if version = 0 then 0 else 0x50 + version) :: BitcoinSig.pushBytes program
/-- A push-only scriptSig: the canonical pushes of the given elements, in order. -/
def pushesBytes (ps : List Bytes) : Bytes := ps.flatMap BitcoinSig.pushBytes
end BitcoinVerify
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_BitcoinVerify
Scope and notation. This file lives in a namespace BitcoinVerify and depends on four earlier files: BitcoinSer (byte strings, transactions, SHA-256, RIPEMD-160, hash160), BitcoinScript (the stack interpreter evalScript, its Flags, its Oracle, castToBool, the constants MAX_SCRIPT_ELEMENT_SIZE = 520, MAX_STACK_SIZE = 1000, OP_16 = 0x60), BitcoinSig (the byte-level parser getOp/parseScript, the canonical push encoder pushBytes, the signature flags SigFlags, the two signature versions base/witnessV0, the concrete legacyOracle, and p2pkhBytes), and BitcoinActivation (the seven-field consensus flag record ScriptFlags with Boolean fields p2sh, witness, taproot, dersig, cltv, csv, nulldummy). Throughout, a byte is an 8-bit bit-vector, a byte string (Bytes) is a finite list of bytes, and a stack is a finite list of byte strings. Every stack handed to the interpreter is top-first: the head of the list is the top of the stack. Nothing in this file is a theorem; every declaration is a computable definition. The declarations are described below in file order.
MAX_SCRIPT_SIZE, WITNESS_V0_SCRIPTHASH_SIZE, WITNESS_V0_KEYHASH_SIZE, WITNESS_V1_TAPROOT_SIZE. Four natural-number constants: , , , respectively.
scriptFlagsOf. Given a consensus flag record , produces the interpreter's three-field flag record . The fields p2sh, witness, taproot, dersig of are not forwarded to the interpreter.
sigFlagsOf. Given a consensus flag record , produces the signature layer's four-field record . Only dersig is carried over; the other three are hard-wired to false.
Ctx. A record of four fields: flags (a consensus flag record), tx (a transaction: version, inputs, outputs, lock time), nIn (a natural number, the input index), and amount (an integer; the docstring says is used where the amount is unknown). Nothing constrains nIn to be a valid index of tx, and nothing constrains amount to be non-negative.
evalBytes. Takes a context , a signature version , a top-first stack, and a byte string script; returns either "failure" (none) or a resulting top-first stack. It proceeds:
- If (strictly), failure. A script of exactly bytes is allowed.
- Otherwise parse
scriptbyte-wise withBitcoinSig.parseScript; if parsing fails (a truncated push), failure. - Otherwise run the interpreter
BitcoinScript.evalScriptwith flagsscriptFlagsOf c.flags, with the oracleBitcoinSig.legacyOracle (sigFlagsOf c.flags) c.tx c.nIn c.amount v script, on the given stack and the parsed instruction list; the interpreter's own failure or success is the result.
Unfolding the oracle: its hash functions are the concrete SHA-256/RIPEMD-160/SHA-1/hash160/hash256; its signature check on is checkSigPreTapscript (sigFlagsOf c.flags) c.tx c.nIn c.amount v script sig pk, in which the script code is the entire byte string script being executed (with the push of sig removed by findAndDelete when , and unchanged when ); its lock-time and sequence checks are those of c.tx at input c.nIn. There is no handling of OP_CODESEPARATOR at this level (the interpreter treats that opcode as a no-op), so the script code is always the whole script.
isPayToScriptHash. For a byte string : true exactly when and and and . (Out-of-range indices read as , but with all three indices are in range.) The 20 bytes are unconstrained.
decodeOpN. On a natural number : if , else with truncated natural subtraction (so any yields as well). It is only ever applied, below, to or .
isWitnessProgram. For a byte string , returns either nothing or a pair (version, program):
- If or : nothing. So is required.
- Let . If and ( or ): nothing. So ; in particular (
OP_RESERVED) and all push opcodes other than are rejected. - If : the pair . Otherwise nothing. Given the length bound, and the returned program has exactly bytes. The version is for and otherwise.
isPushOnlyAux, isPushOnly. isPushOnlyAux takes a fuel counter and a byte string: an empty string is push-only (true); with zero fuel and a non-empty string, false; otherwise it parses one instruction with getOp: a parse failure gives false; a push instruction recurses on the remainder with one less fuel; a non-push opcode gives false if , else recurses. isPushOnly s calls this with fuel . Since getOp always consumes at least one byte, fuel suffices to reach the end; the result is: every instruction parses and is either a data push (any of OP_0, direct pushes, OP_PUSHDATA1/2/4) or an opcode byte in (OP_1NEGATE, OP_RESERVED, OP_1…OP_16). Push sizes are not bounded here.
isPayToAnchor. For a natural number version and a byte string program: true exactly when version and program is the two-byte string .
topTrue. For a top-first stack: false if the stack is empty; otherwise castToBool of the top element. castToBool of a byte string is: false for the empty string; for a string, true iff some byte is nonzero, except that a string whose only nonzero byte is a final (negative zero) is false.
executeWitnessScriptV0. Takes a context , a top-first stack and a byte string exec; returns a Boolean:
- If some element of the stack has length strictly greater than : false. (The size check is on the stack elements only;
execitself is not checked here.) - Otherwise run
evalBytes c witnessV0 stack exec. Failure gives false. - Otherwise, with resulting stack : true iff (exactly one element) and
topTrue st.
p2wpkhExec. For a byte string program: BitcoinSig.p2pkhBytes program, i.e. the byte string (OP_DUP OP_HASH160 <push> OP_EQUALVERIFY OP_CHECKSIG). For a 20-byte program the push is followed by the 20 bytes, so the script has 26 bytes.
TaprootHandler. A type abbreviation: a function from (context, list of byte strings, byte string) to Boolean. Per the docstring, the list is the witness stack in serialized order (last element on top) and the byte string is the 32-byte program. The file places no constraint whatsoever on such a function.
verifyWitnessProgram. Takes a handler tap, a context , a witness stack witness (a list of byte strings in serialized order, i.e. last element of the list is the top, the opposite convention from the interpreter's stacks), a natural number version, a byte string program, and a Boolean isP2sh. Control flow, in order:
- Case version .
- If (P2WSH): take the last element of
witness(getLast?). Ifwitnessis empty: false. Otherwise call itscript; if : false; else the result isexecuteWitnessScriptV0 c (witness.dropLast.reverse) script— the witness with its last element removed and then reversed, so the second-to-last serialized element becomes the interpreter's top. Notescriptis exempt from the 520-byte element check insideexecuteWitnessScriptV0, since it has been removed from the stack. - Else if (P2WPKH): if : false; else the result is
executeWitnessScriptV0 c witness.reverse (p2wpkhExec program), i.e. the two-element witness is reversed (its second serialized element becomes the top) and run againstOP_DUP OP_HASH160 <program> OP_EQUALVERIFY OP_CHECKSIGunder signature versionwitnessV0. - Else (version 0 with any other program length): false.
- If (P2WSH): take the last element of
- Case version and and
isP2shis false (Taproot): ifc.flags.taprootis false: true unconditionally (the witness is not inspected at all, even if empty); else the result istap c witness program— the handler receives the witness in serialized (unreversed) order. - Otherwise: if
isP2shis false andisPayToAnchor version program: true; else: true. Both arms yield true, so every remaining case — unknown versions … (and any other natural number), version with a program length other than , version with a 32-byte program under P2SH, and pay-to-anchor — succeeds regardless of the witness. TheisPayToAnchortest has no effect on the result.
The taproot flag is the only flag consulted here; the witness flag is not (it gates the callers). The isP2sh argument matters only to exclude the Taproot branch.
verifyScript. Takes a handler tap, a context , byte strings scriptSig and scriptPubKey, and a witness stack witness (serialized order). Control flow, in order:
- Evaluate
scriptSigwithevalBytes c base []on the empty stack. Failure: false. Call the resulting top-first stackstackSig. - Evaluate
scriptPubKeywithevalBytes c base stackSig(same stack carried over, same signature versionbase). Failure: false. Call the resultstack. - If
topTrue stackis false (empty, or top casts to false): false. - Compute
native, an optional Boolean: ifc.flags.witnessis true andisWitnessProgram scriptPubKeyyields : ifscriptSigis non-empty thensome false, elsesome (verifyWitnessProgram tap c witness version program false). If thewitnessflag is false, orscriptPubKeyis not a witness program:none. - If
nativeissome false: false. Ifsome true: true (the function returns here; the P2SH and the "unexpected witness" checks below are never reached for a native witness program). - If
nativeisnone, andc.flags.p2shis true andisPayToScriptHash scriptPubKey:- If
scriptSigis not push-only (isPushOnly): false. - Restore the stack
stackSig— the stack as it stood after step 1, beforescriptPubKeyran. If it is empty: false. Otherwise its top element isredeemand the remainder isrest. - Evaluate
redeemas a script:evalBytes c base rest redeem, signature versionbase, on the stackrest(with the redeem script popped). Failure: false. Call the resultstack2. - If
topTrue stack2is false: false. - If
c.flags.witnessis true: ifisWitnessProgram redeemyields : ifscriptSigis not byte-for-byte equal topushBytes redeem(the single canonical push of the redeem script): false; else the result isverifyWitnessProgram tap c witness version program true. Ifredeemis not a witness program: false if (c.flags.witnessandwitnessis non-empty) — the repeatedwitness-flag test is redundant here — else true. - If
c.flags.witnessis false: true (the witness is never consulted).
- If
- If
nativeisnoneand the P2SH branch is not taken (flag off or not a P2SH script): false ifc.flags.witnessis true andwitnessis non-empty; else true.
Summary of the stack conventions: the interpreter's stacks (stackSig, stack, rest, stack2, and the arguments to executeWitnessScriptV0) are top-first; the witness list is bottom-first and is converted by reverse (P2WPKH) or dropLast then reverse (P2WSH); the Taproot handler gets the unconverted list. The witness stack is consulted only inside verifyWitnessProgram and in the two "non-empty witness" rejections. There is no "clean stack" requirement anywhere, and no restriction of scriptSig to pushes outside the P2SH branch.
p2shBytes. For a byte string : (OP_HASH160 <push h> OP_EQUAL). For this is , 23 bytes; for other lengths of the result is generally not accepted by isPayToScriptHash.
witnessBytes. For a natural number version and byte string program: the single byte if version , else the byte reduced modulo , followed by . For and this is OP_n, the direct-push length byte, then the program. For version the first byte lies outside (and wraps for version ); for pushBytes emits an OP_PUSHDATA prefix.
pushesBytes. For a list of byte strings: the concatenation, in list order, of the canonical push pushBytes of each element. For the empty list, the empty byte string.
Points a reader may find notable (descriptions only). (a) evalBytes allows a script of exactly bytes (, not ). (b) In verifyWitnessProgram, every non-version-0, non-Taproot case returns true, so the isPayToAnchor branch is indistinguishable from the fallthrough. (c) When the taproot flag is off, a version-1 32-byte native program is accepted with any witness, including an empty one, without calling the handler. (d) In verifyScript, a native witness program that passes returns true before any P2SH consideration, and a scriptPubKey can never be both a P2SH script and a witness program (first byte vs. ). (e) The P2SH branch restores stackSig, not stack. (f) The 520-byte check in executeWitnessScriptV0 applies to the stack elements only; for P2WSH the script element is removed first. (g) Inside the P2SH-wrapped-witness branch, the redundant c.flags.witness && in the non-witness-redeem case is always true. (h) sigFlagsOf forwards only dersig; scriptFlagsOf forwards only cltv, csv, nulldummy. (i) The script code for signature checks is always the whole executed script. (j) decodeOpN uses truncated subtraction.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.