Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

VerifyScript: P2SH, native and wrapped SegWit v0, unknown witness versions, and the taproot hand-off

Definition
BitcoinVerify

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

bip141bitcoinbitcoin-mainnetconsensusformal-verificationp2shsegwitverifyscript

Context 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). MAX_SCRIPT_SIZE=10,000\mathrm{MAX\_SCRIPT\_SIZE} = 10{,}000MAX_SCRIPT_SIZE=10,000.

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.

Definition code
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
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyScript, VerifyWitnessProgram, ExecuteWitnessScript, src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; CScript::IsPayToScriptHash, IsWitnessProgram, IsPushOnly, IsPayToAnchor, DecodeOP_N, src/script/script.cpp and script.h; MAX_SCRIPT_SIZE, WITNESS_V0_SCRIPTHASH_SIZE, WITNESS_V0_KEYHASH_SIZE, WITNESS_V1_TAPROOT_SIZE; BIP16, BIP141, BIP143 at bips revision 100ba872c808946155b1eeb8c4568058f2eea0a7
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: 100001000010000, 323232, 202020, 323232 respectively.

scriptFlagsOf. Given a consensus flag record fff, produces the interpreter's three-field flag record ⟨f.cltv, f.csv, f.nulldummy⟩\langle f.\mathrm{cltv},\ f.\mathrm{csv},\ f.\mathrm{nulldummy}\rangle⟨f.cltv, f.csv, f.nulldummy⟩. The fields p2sh, witness, taproot, dersig of fff are not forwarded to the interpreter.

sigFlagsOf. Given a consensus flag record fff, produces the signature layer's four-field record ⟨dersig=f.dersig, lowS=false, strictenc=false, witnessPubkeyType=false⟩\langle \mathrm{dersig} = f.\mathrm{dersig},\ \mathrm{lowS} = \mathrm{false},\ \mathrm{strictenc} = \mathrm{false},\ \mathrm{witnessPubkeyType} = \mathrm{false}\rangle⟨dersig=f.dersig, lowS=false, strictenc=false, witnessPubkeyType=false⟩. 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 −1-1−1 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 ccc, a signature version v∈{base,witnessV0}v \in \{\mathrm{base}, \mathrm{witnessV0}\}v∈{base,witnessV0}, a top-first stack, and a byte string script; returns either "failure" (none) or a resulting top-first stack. It proceeds:

  1. If 10000<∣script∣10000 < |\mathrm{script}|10000<∣script∣ (strictly), failure. A script of exactly 100001000010000 bytes is allowed.
  2. Otherwise parse script byte-wise with BitcoinSig.parseScript; if parsing fails (a truncated push), failure.
  3. Otherwise run the interpreter BitcoinScript.evalScript with flags scriptFlagsOf c.flags, with the oracle BitcoinSig.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 (sig,pk)(\mathrm{sig}, \mathrm{pk})(sig,pk) 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 v=basev = \mathrm{base}v=base, and unchanged when v=witnessV0v = \mathrm{witnessV0}v=witnessV0); 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 sss: true exactly when ∣s∣=23|s| = 23∣s∣=23 and s0=0xa9s_0 = \mathtt{0xa9}s0​=0xa9 and s1=0x14s_1 = \mathtt{0x14}s1​=0x14 and s22=0x87s_{22} = \mathtt{0x87}s22​=0x87. (Out-of-range indices read as 000, but with ∣s∣=23|s| = 23∣s∣=23 all three indices are in range.) The 20 bytes s2…s21s_2 \ldots s_{21}s2​…s21​ are unconstrained.

decodeOpN. On a natural number bbb: 000 if b=0b = 0b=0, else b−0x50b - \mathtt{0x50}b−0x50 with truncated natural subtraction (so any 0<b<0x500 < b < \mathtt{0x50}0<b<0x50 yields 000 as well). It is only ever applied, below, to b=0b = 0b=0 or b∈[0x51,0x60]b \in [\mathtt{0x51}, \mathtt{0x60}]b∈[0x51,0x60].

isWitnessProgram. For a byte string sss, returns either nothing or a pair (version, program):

  1. If ∣s∣<4|s| < 4∣s∣<4 or 42<∣s∣42 < |s|42<∣s∣: nothing. So 4≤∣s∣≤424 \le |s| \le 424≤∣s∣≤42 is required.
  2. Let b0=s0b_0 = s_0b0​=s0​. If b0≠0b_0 \ne 0b0​=0 and (b0<0x51b_0 < \mathtt{0x51}b0​<0x51 or 0x60<b0\mathtt{0x60} < b_00x60<b0​): nothing. So b0∈{0}∪[0x51,0x60]b_0 \in \{0\} \cup [\mathtt{0x51}, \mathtt{0x60}]b0​∈{0}∪[0x51,0x60]; in particular 0x50\mathtt{0x50}0x50 (OP_RESERVED) and all push opcodes other than 000 are rejected.
  3. If s1+2=∣s∣s_1 + 2 = |s|s1​+2=∣s∣: the pair (decodeOpN b0, s with its first two bytes dropped)(\mathrm{decodeOpN}\ b_0,\ s \text{ with its first two bytes dropped})(decodeOpN b0​, s with its first two bytes dropped). Otherwise nothing. Given the length bound, s1∈[2,40]s_1 \in [2, 40]s1​∈[2,40] and the returned program has exactly s1s_1s1​ bytes. The version is 000 for b0=0b_0 = 0b0​=0 and b0−0x50∈[1,16]b_0 - \mathtt{0x50} \in [1, 16]b0​−0x50∈[1,16] 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 ccc gives false if 0x60<c\mathtt{0x60} < c0x60<c, else recurses. isPushOnly s calls this with fuel ∣s∣|s|∣s∣. Since getOp always consumes at least one byte, fuel ∣s∣|s|∣s∣ 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 [0x4f,0x60][\mathtt{0x4f}, \mathtt{0x60}][0x4f,0x60] (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 =1= 1=1 and program is the two-byte string [0x4e,0x73][\mathtt{0x4e}, \mathtt{0x73}][0x4e,0x73].

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 0x80\mathtt{0x80}0x80 (negative zero) is false.

executeWitnessScriptV0. Takes a context ccc, a top-first stack and a byte string exec; returns a Boolean:

  1. If some element of the stack has length strictly greater than 520520520: false. (The size check is on the stack elements only; exec itself is not checked here.)
  2. Otherwise run evalBytes c witnessV0 stack exec. Failure gives false.
  3. Otherwise, with resulting stack ststst: true iff ∣st∣=1|st| = 1∣st∣=1 (exactly one element) and topTrue st.

p2wpkhExec. For a byte string program: BitcoinSig.p2pkhBytes program, i.e. the byte string 0x76 0xa9 ∥ pushBytes(program) ∥ 0x88 0xac\mathtt{0x76}\ \mathtt{0xa9}\ \|\ \mathrm{pushBytes}(\mathrm{program})\ \|\ \mathtt{0x88}\ \mathtt{0xac}0x76 0xa9 ∥ pushBytes(program) ∥ 0x88 0xac (OP_DUP OP_HASH160 <push> OP_EQUALVERIFY OP_CHECKSIG). For a 20-byte program the push is 0x14\mathtt{0x14}0x14 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 ccc, 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 =0= 0=0.
    • If ∣program∣=32|\mathrm{program}| = 32∣program∣=32 (P2WSH): take the last element of witness (getLast?). If witness is empty: false. Otherwise call it script; if sha256(script)≠program\mathrm{sha256}(\mathrm{script}) \ne \mathrm{program}sha256(script)=program: false; else the result is executeWitnessScriptV0 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. Note script is exempt from the 520-byte element check inside executeWitnessScriptV0, since it has been removed from the stack.
    • Else if ∣program∣=20|\mathrm{program}| = 20∣program∣=20 (P2WPKH): if ∣witness∣≠2|\mathrm{witness}| \ne 2∣witness∣=2: 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 against OP_DUP OP_HASH160 <program> OP_EQUALVERIFY OP_CHECKSIG under signature version witnessV0.
    • Else (version 0 with any other program length): false.
  • Case version =1= 1=1 and ∣program∣=32|\mathrm{program}| = 32∣program∣=32 and isP2sh is false (Taproot): if c.flags.taproot is false: true unconditionally (the witness is not inspected at all, even if empty); else the result is tap c witness program — the handler receives the witness in serialized (unreversed) order.
  • Otherwise: if isP2sh is false and isPayToAnchor version program: true; else: true. Both arms yield true, so every remaining case — unknown versions 222…161616 (and any other natural number), version 111 with a program length other than 323232, version 111 with a 32-byte program under P2SH, and pay-to-anchor — succeeds regardless of the witness. The isPayToAnchor test 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 ccc, byte strings scriptSig and scriptPubKey, and a witness stack witness (serialized order). Control flow, in order:

  1. Evaluate scriptSig with evalBytes c base [] on the empty stack. Failure: false. Call the resulting top-first stack stackSig.
  2. Evaluate scriptPubKey with evalBytes c base stackSig (same stack carried over, same signature version base). Failure: false. Call the result stack.
  3. If topTrue stack is false (empty, or top casts to false): false.
  4. Compute native, an optional Boolean: if c.flags.witness is true and isWitnessProgram scriptPubKey yields (version,program)(\mathrm{version}, \mathrm{program})(version,program): if scriptSig is non-empty then some false, else some (verifyWitnessProgram tap c witness version program false). If the witness flag is false, or scriptPubKey is not a witness program: none.
  5. If native is some false: false. If some true: true (the function returns here; the P2SH and the "unexpected witness" checks below are never reached for a native witness program).
  6. If native is none, and c.flags.p2sh is true and isPayToScriptHash scriptPubKey:
    • If scriptSig is not push-only (isPushOnly): false.
    • Restore the stack stackSig — the stack as it stood after step 1, before scriptPubKey ran. If it is empty: false. Otherwise its top element is redeem and the remainder is rest.
    • Evaluate redeem as a script: evalBytes c base rest redeem, signature version base, on the stack rest (with the redeem script popped). Failure: false. Call the result stack2.
    • If topTrue stack2 is false: false.
    • If c.flags.witness is true: if isWitnessProgram redeem yields (version,program)(\mathrm{version}, \mathrm{program})(version,program): if scriptSig is not byte-for-byte equal to pushBytes redeem (the single canonical push of the redeem script): false; else the result is verifyWitnessProgram tap c witness version program true. If redeem is not a witness program: false if (c.flags.witness and witness is non-empty) — the repeated witness-flag test is redundant here — else true.
    • If c.flags.witness is false: true (the witness is never consulted).
  7. If native is none and the P2SH branch is not taken (flag off or not a P2SH script): false if c.flags.witness is true and witness is 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 hhh: [0xa9] ∥ pushBytes(h) ∥ [0x87][\mathtt{0xa9}] \,\|\, \mathrm{pushBytes}(h) \,\|\, [\mathtt{0x87}][0xa9]∥pushBytes(h)∥[0x87] (OP_HASH160 <push h> OP_EQUAL). For ∣h∣=20|h| = 20∣h∣=20 this is 0xa9 0x14 h 0x87\mathtt{0xa9}\ \mathtt{0x14}\ h\ \mathtt{0x87}0xa9 0x14 h 0x87, 23 bytes; for other lengths of hhh the result is generally not accepted by isPayToScriptHash.

witnessBytes. For a natural number version and byte string program: the single byte 0\mathtt{0}0 if version =0= 0=0, else the byte 0x50+version\mathtt{0x50} + \mathrm{version}0x50+version reduced modulo 256256256, followed by pushBytes(program)\mathrm{pushBytes}(\mathrm{program})pushBytes(program). For 1≤version≤161 \le \mathrm{version} \le 161≤version≤16 and 2≤∣program∣≤402 \le |\mathrm{program}| \le 402≤∣program∣≤40 this is OP_n, the direct-push length byte, then the program. For version ≥17\ge 17≥17 the first byte lies outside [0x51,0x60][\mathtt{0x51}, \mathtt{0x60}][0x51,0x60] (and wraps for version ≥176\ge 176≥176); for ∣program∣≥76|\mathrm{program}| \ge 76∣program∣≥76 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 100001000010000 bytes (<<<, not ≤\le≤). (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 0xa9\mathtt{0xa9}0xa9 vs. {0}∪[0x51,0x60]\{0\} \cup [\mathtt{0x51}, \mathtt{0x60}]{0}∪[0x51,0x60]). (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.

Human review
  • Endorsed by Shuze Chen · Oct 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 27, 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