Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Taproot and Tapscript: the version-1 witness branch, BIP341 signature hash, commitment check, and the Tapscript interpreter rules

Definition
BitcoinTaproot

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

bip341bip342bitcoinbitcoin-mainnetconsensusformal-verificationschnorrtaproottapscript

Constants. TAPROOT_LEAF_MASK = 0xfe, TAPROOT_LEAF_TAPSCRIPT = 0xc0, control-block sizes 33 + 32·k for k≤128k \le 128k≤128, ANNEX_TAG = 0x50, VALIDATION_WEIGHT_OFFSET = 50, VALIDATION_WEIGHT_PER_SIGOP_PASSED = 50, SIGHASH_DEFAULT = 0, OP_CHECKSIGADD = 0xba.

Hashes and the tweak. tagged t m is the BIP340 tagged hash SHA256(SHA256(t) ∥ SHA256(t) ∥ m)\mathrm{SHA256}(\mathrm{SHA256}(t)\,\|\,\mathrm{SHA256}(t)\,\|\,m)SHA256(SHA256(t)∥SHA256(t)∥m). tapleafHash v s = TapLeaf(v ‖ compactSize(|s|) ‖ s); tapbranchHash a b = TapBranch of the two children in lexicographic order (lexLt is std::lexicographical_compare); controlNodes cuts the 32-byte path nodes after the 33-byte base; taprootMerkleRoot control leaf folds tapbranchHash over them from the leaf; tapTweakHash p r = TapTweak(p ‖ r). xonlyTweakAddCheck q parity P t is secp256k1_xonly_pubkey_tweak_add_check: t<nt < nt<n, Q=P+tG≠OQ = P + tG \ne \mathcal{O}Q=P+tG=O, x(Q)x(Q)x(Q) is the 32-byte key q and the parity of y(Q)y(Q)y(Q) is parity; checkTapTweak lifts the internal key with the signature mission's liftX first; verifyTaprootCommitment control program leafHash is VerifyTaprootCommitment (parity from bit 0 of the control byte, internal key bytes 1–32, root from the path).

BIP341 signature hash. sigHashSchnorr tx spent inPos hashType tapscript ed is SignatureHashSchnorr with ExecData (annex presence and hash, tapleaf hash, code-separator position): none for a hash type outside {0,1,2,3,0x81,0x82,0x83}\{0,1,2,3,0x81,0x82,0x83\}{0,1,2,3,0x81,0x82,0x83} and for SIGHASH_SINGLE without a matching output; otherwise the TapSighash tagged hash of the epoch byte, hash type, version, locktime, the four precomputed hashes unless ANYONECANPAY, the outputs hash for ALL, the spend-type byte, the input (index, or outpoint ‖ spent output ‖ sequence), the annex hash, the single-output hash and the Tapscript extension. spent lists the spent outputs, one per input.

Schnorr check. checkSchnorrSignature tx spent nIn sig q tapscript ed is CheckSchnorrSignature: 64 bytes (SIGHASH_DEFAULT) or 65 bytes whose last byte is a non-zero hash type, then BIP340 schnorrVerify of the signature mission over the BIP341 hash.

Tapscript (BIP342). isOpSuccess is IsOpSuccess; opSuccessScan is the pre-scan of ExecuteWitnessScript (a malformed push before any success opcode fails). TapCtx carries the interpreter flags, transaction, spent outputs and input index; tapOracle supplies the hash and locktime oracles of the Script mission (its checkSig is never consulted). TapState is the interpreter state plus the remaining validation weight, the code-separator position and the opcode position. evalChecksigTapscript is EvalChecksigTapscript: a non-empty signature costs 50 weight and fails on a negative budget, an empty key fails, a 32-byte key runs the Schnorr check, other key lengths succeed (upgradable). tapExecOp is one executed opcode under TAPSCRIPT: MINIMALIF on OP_IF/OP_NOTIF, OP_CHECKSIG(VERIFY) and OP_CHECKSIGADD via evalChecksigTapscript, OP_CHECKMULTISIG(VERIFY) fail, OP_CODESEPARATOR records the opcode position, everything else is the Script mission's execOp. tapStep/tapRun are the loop (no operation count, push-size and stack-size limits, conditional skipping, opcode position); executeTapscript c ed stack script weight is ExecuteWitnessScript under TAPSCRIPT (scan, initial limits, run, exactly one true element).

The version-1 branch. hasAnnex (two or more elements and a last element starting with 0x50), witnessSerializedSize; taprootHandler spent : BitcoinVerify.TaprootHandler is the version-1 branch of VerifyWitnessProgram: an empty witness fails; one element after the annex is the key path (Schnorr check of the output key, no tapleaf, code separator 0xFFFFFFFF); otherwise the control block and script are popped, the control size is checked, the leaf version is masked, the commitment verified, and leaf version 0xc0 runs Tapscript on the remaining elements with the weight budget ∣ser(witness)∣+50|\mathrm{ser}(\text{witness})| + 50∣ser(witness)∣+50, other leaf versions succeed. verifyScriptFull spent is the complete VerifyScript with this handler; p2trBytes q = OP_1 <q>.

Formalization Note. Policy flags (DISCOURAGE_UPGRADABLE_TAPROOT_VERSION, DISCOURAGE_UPGRADABLE_PUBKEYTYPE, DISCOURAGE_OP_SUCCESS) are off, as in block validation. Only Std is imported.

Definition code
import Std
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinScript
import Definitions.Def_BitcoinSig
import Definitions.Def_BitcoinVerify

namespace BitcoinTaproot

/-! Transcription of Bitcoin Core's Taproot and Tapscript validation at revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`: the version-1 branch of `VerifyWitnessProgram` (annex,
key path, script path), `ComputeTapleafHash`, `ComputeTapbranchHash`, `ComputeTaprootMerkleRoot`,
`VerifyTaprootCommitment` (`script/interpreter.cpp`), `XOnlyPubKey::CheckTapTweak` and
`ComputeTapTweakHash` (`pubkey.cpp`) with `secp256k1_xonly_pubkey_tweak_add_check`,
`SignatureHashSchnorr` (BIP341), `CheckSchnorrSignature`, `EvalChecksigTapscript`, the Tapscript
rules of `EvalScript` and `ExecuteWitnessScript` (BIP342: `OP_SUCCESSx`, `MINIMALIF`,
`OP_CHECKSIGADD`, no `OP_CHECKMULTISIG`, the validation-weight budget, `OP_CODESEPARATOR`
positions, no operation count), and `IsOpSuccess` (`script/script.cpp`). -/

open BitcoinSer (Byte Bytes Tx TxIn TxOut)
open BitcoinScript (Instr Script State Flags Oracle)

def TAPROOT_LEAF_MASK : Nat := 0xfe
def TAPROOT_LEAF_TAPSCRIPT : Nat := 0xc0
def TAPROOT_CONTROL_BASE_SIZE : Nat := 33
def TAPROOT_CONTROL_NODE_SIZE : Nat := 32
def TAPROOT_CONTROL_MAX_NODE_COUNT : Nat := 128
def TAPROOT_CONTROL_MAX_SIZE : Nat := TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT
def ANNEX_TAG : Nat := 0x50
def VALIDATION_WEIGHT_OFFSET : Int := 50
def VALIDATION_WEIGHT_PER_SIGOP_PASSED : Int := 50
def SIGHASH_DEFAULT : Nat := 0
/-- `OP_CHECKSIGADD = 0xba` (BIP342). -/
def OP_CHECKSIGADD : Byte := 0xba

/-! ### Tagged hashes, leaves, branches, the tweak -/

def tagged (tag : String) (m : Bytes) : Bytes := BitcoinSig.taggedHash (BitcoinSig.ascii tag) m

/-- `ComputeTapleafHash(leaf_version, script)`. -/
def tapleafHash (leafVersion : Byte) (script : Bytes) : Bytes :=
  tagged "TapLeaf" ([leafVersion] ++ BitcoinSer.writeCompactSize script.length ++ script)

/-- `std::lexicographical_compare` on byte strings. -/
def lexLt : Bytes → Bytes → Bool
  | [], [] => false
  | [], _ :: _ => true
  | _ :: _, [] => false
  | a :: as, b :: bs => if a.toNat < b.toNat then true else if b.toNat < a.toNat then false else lexLt as bs

/-- `ComputeTapbranchHash(a, b)`: the lexicographically smaller first. -/
def tapbranchHash (a b : Bytes) : Bytes :=
  tagged "TapBranch" (if lexLt a b then a ++ b else b ++ a)

/-- The path nodes of a control block: 32-byte chunks after the 33-byte base. -/
def controlNodes (control : Bytes) : List Bytes :=
  let rec go : Nat → Bytes → List Bytes
    | 0, _ => []
    | k + 1, s => s.take TAPROOT_CONTROL_NODE_SIZE :: go k (s.drop TAPROOT_CONTROL_NODE_SIZE)
  go ((control.length - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE) (control.drop TAPROOT_CONTROL_BASE_SIZE)

/-- `ComputeTaprootMerkleRoot(control, tapleaf_hash)`. -/
def taprootMerkleRoot (control : Bytes) (leafHash : Bytes) : Bytes :=
  (controlNodes control).foldl tapbranchHash leafHash

/-- `XOnlyPubKey::ComputeTapTweakHash(&merkle_root)`. -/
def tapTweakHash (internal32 merkleRoot : Bytes) : Bytes := tagged "TapTweak" (internal32 ++ merkleRoot)

/-- The 32-byte big-endian encoding of a coordinate. -/
def be32 (x : Nat) : Bytes := BitcoinSer.beBytes 32 x

/-- `secp256k1_xonly_pubkey_tweak_add_check(output32, parity, internal, tweak32)`: with `P` the
even-`y` point of the internal key and `t` the tweak scalar (below `n`), `Q = P + tG` is not infinity,
its abscissa is `output32` and the parity of its ordinate is `parity`. -/
def xonlyTweakAddCheck (output32 : Bytes) (parity : Bool) (P : Nat × Nat) (tweak32 : Bytes) : Bool :=
  let t := BitcoinSig.beVal tweak32
  if BitcoinSig.n ≤ t then false
  else match BitcoinSig.padd (some P) (BitcoinSig.pmul t BitcoinSig.G) with
    | none => false
    | some (qx, qy) => decide (be32 qx = output32) && decide ((qy % 2 = 1) = parity)

/-- `XOnlyPubKey::CheckTapTweak(internal, merkle_root, parity)` on the output key `q`. -/
def checkTapTweak (q internal32 merkleRoot : Bytes) (parity : Bool) : Bool :=
  match BitcoinSig.liftX (BitcoinSig.beVal internal32) with
  | none => false
  | some P => xonlyTweakAddCheck q parity P (tapTweakHash internal32 merkleRoot)

/-- `VerifyTaprootCommitment(control, program, tapleaf_hash)`. -/
def verifyTaprootCommitment (control program leafHash : Bytes) : Bool :=
  checkTapTweak program ((control.drop 1).take 32) (taprootMerkleRoot control leafHash)
    (decide ((control.getD 0 0).toNat % 2 = 1))

/-! ### The BIP341 signature hash -/

/-- `ScriptExecutionData` as far as the signature hash reads it. -/
structure ExecData where
  annexPresent : Bool
  annexHash : Bytes
  tapleafHash : Bytes
  codeseparatorPos : Nat
  deriving Repr

/-- `SignatureHashSchnorr(tx, in_pos, hash_type, sigversion, cache)`: `none` where it returns `false`
(an undefined hash type, or `SIGHASH_SINGLE` without a matching output). `spent` lists the outputs
being spent, one per input. -/
def sigHashSchnorr (tx : Tx) (spent : List TxOut) (inPos : Nat) (hashType : Nat) (tapscript : Bool)
    (ed : ExecData) : Option Bytes :=
  if ¬ (hashType ≤ 3 ∨ (0x81 ≤ hashType ∧ hashType ≤ 0x83)) then none
  else
    let outputType := if hashType = SIGHASH_DEFAULT then BitcoinSig.SIGHASH_ALL else hashType &&& 3
    let inputType := hashType &&& 0x80
    let extFlag : Nat := if tapscript then 1 else 0
    let spendType : Nat := extFlag * 2 + (if ed.annexPresent then 1 else 0)
    let dfltIn : TxIn := ⟨⟨[], 0⟩, [], 0, []⟩
    let i := tx.vin.getD inPos dfltIn
    let single? : Option Bytes :=
      if outputType = BitcoinSig.SIGHASH_SINGLE then
        if tx.vout.length ≤ inPos then none
        else some (BitcoinSer.sha256 (BitcoinSer.serTxOut (tx.vout.getD inPos ⟨-1, []⟩)))
      else some []
    match single? with
    | none => none
    | some singleOut =>
      some (tagged "TapSighash" (
        [0, BitVec.ofNat 8 hashType] ++ BitcoinSer.ser32 tx.version ++ BitcoinSer.ser32 tx.nLockTime ++
        (if inputType ≠ BitcoinSig.SIGHASH_ANYONECANPAY then
          BitcoinSer.sha256 (tx.vin.flatMap fun i => BitcoinSer.serOutPoint i.prevout) ++
          BitcoinSer.sha256 (spent.flatMap fun o => BitcoinSer.serInt64 o.nValue) ++
          BitcoinSer.sha256 (spent.flatMap fun o => BitcoinSer.serBytes o.scriptPubKey) ++
          BitcoinSer.sha256 (tx.vin.flatMap fun i => BitcoinSer.ser32 i.nSequence)
         else []) ++
        (if outputType = BitcoinSig.SIGHASH_ALL then BitcoinSer.sha256 (tx.vout.flatMap BitcoinSer.serTxOut) else []) ++
        [BitVec.ofNat 8 spendType] ++
        (if inputType = BitcoinSig.SIGHASH_ANYONECANPAY then
          BitcoinSer.serOutPoint i.prevout ++ BitcoinSer.serTxOut (spent.getD inPos ⟨-1, []⟩) ++ BitcoinSer.ser32 i.nSequence
         else BitcoinSer.ser32 inPos) ++
        (if ed.annexPresent then ed.annexHash else []) ++
        singleOut ++
        (if tapscript then ed.tapleafHash ++ [0] ++ BitcoinSer.ser32 ed.codeseparatorPos else [])))

/-- `CheckSchnorrSignature(sig, pubkey, sigversion, execdata)`: 64 or 65 bytes, an explicit hash
type must not be `0`, the BIP341 hash, then BIP340 verification. `false` is a script error. -/
def checkSchnorrSignature (tx : Tx) (spent : List TxOut) (nIn : Nat) (sig pubkey32 : Bytes) (tapscript : Bool)
    (ed : ExecData) : Bool :=
  if sig.length ≠ 64 ∧ sig.length ≠ 65 then false
  else
    let hashType : Nat := if sig.length = 65 then (sig.getLast?.getD 0).toNat else SIGHASH_DEFAULT
    let sig' := if sig.length = 65 then sig.dropLast else sig
    if sig.length = 65 ∧ hashType = SIGHASH_DEFAULT then false
    else match sigHashSchnorr tx spent nIn hashType tapscript ed with
      | none => false
      | some h => BitcoinSig.schnorrVerify pubkey32 h sig'

/-! ### Tapscript (BIP342) -/

/-- `IsOpSuccess`. -/
def isOpSuccess (c : Nat) : Bool :=
  decide (c = 80 ∨ c = 98 ∨ (126 ≤ c ∧ c ≤ 129) ∨ (131 ≤ c ∧ c ≤ 134) ∨ (137 ≤ c ∧ c ≤ 138) ∨
    (141 ≤ c ∧ c ≤ 142) ∨ (149 ≤ c ∧ c ≤ 153) ∨ (187 ≤ c ∧ c ≤ 254))

/-- The `OP_SUCCESSx` pre-scan of `ExecuteWitnessScript`: `some true` when a success opcode is
reached, `some false` when the whole script parses without one, `none` on a malformed push first. -/
def opSuccessScan : Nat → Bytes → Option Bool
  | _, [] => some false
  | 0, _ => none
  | fuel + 1, s =>
    match BitcoinSig.getOp s with
    | none => none
    | some (.push _, r) => opSuccessScan fuel r
    | some (.op c, r) => if isOpSuccess c.toNat then some true else opSuccessScan fuel r

/-- The context of a Tapscript execution. -/
structure TapCtx where
  flags : BitcoinScript.Flags
  tx : Tx
  spent : List TxOut
  nIn : Nat

/-- The hash oracle for the non-signature opcodes (signature opcodes are handled by the Tapscript
loop itself; the oracle's `checkSig` is never consulted). -/
def tapOracle (c : TapCtx) : Oracle where
  ripemd160 := BitcoinSer.ripemd160
  sha1 := BitcoinSer.sha1
  sha256 := BitcoinSer.sha256
  hash160 := BitcoinSer.hash160
  hash256 := BitcoinSer.hash256
  checkSig := fun _ _ => none
  checkLockTime := BitcoinSig.checkLockTime c.tx c.nIn
  checkSequence := BitcoinSig.checkSequence c.tx c.nIn

/-- The Tapscript execution state: the interpreter state, the validation weight left, the
code-separator position, and the opcode position. -/
structure TapState where
  st : State
  weightLeft : Int
  codeseparatorPos : Nat
  opcodePos : Nat

/-- `EvalChecksigTapscript`: `none` is a script error; otherwise the `success` flag and the new
weight. -/
def evalChecksigTapscript (c : TapCtx) (ed : ExecData) (sig pubkey : Bytes) (weightLeft : Int) : Option (Bool × Int) :=
  let success := !sig.isEmpty
  let weight := if success then weightLeft - VALIDATION_WEIGHT_PER_SIGOP_PASSED else weightLeft
  if success ∧ weight < 0 then none
  else if pubkey.length = 0 then none
  else if pubkey.length = 32 then
    if success ∧ !checkSchnorrSignature c.tx c.spent c.nIn sig pubkey true ed then none
    else some (success, weight)
  else some (success, weight)   -- unknown public key type: `DISCOURAGE_UPGRADABLE_PUBKEYTYPE` is policy

/-- One opcode of `EvalScript` under `SigVersion::TAPSCRIPT`, when executing or a conditional. -/
def tapExecOp (c : TapCtx) (ed : ExecData) (fExec : Bool) (op : Byte) (ts : TapState) : Option TapState :=
  let s := ts.st
  let ed' := { ed with codeseparatorPos := ts.codeseparatorPos }
  if op == BitcoinScript.OP_IF || op == BitcoinScript.OP_NOTIF then
    -- `MINIMALIF` is consensus in Tapscript
    if fExec then
      match s.stack with
      | [] => none
      | top :: _ =>
        if 1 < top.length ∨ (top.length = 1 ∧ (top.getD 0 0).toNat ≠ 1) then none
        else (BitcoinScript.execOp c.flags (tapOracle c) fExec op s).map fun s' => { ts with st := s' }
    else (BitcoinScript.execOp c.flags (tapOracle c) fExec op s).map fun s' => { ts with st := s' }
  else if op == BitcoinScript.OP_CHECKSIG || op == BitcoinScript.OP_CHECKSIGVERIFY then
    match s.stack with
    | pubkey :: sig :: rest =>
      match evalChecksigTapscript c ed' sig pubkey ts.weightLeft with
      | none => none
      | some (success, weight) =>
        if op == BitcoinScript.OP_CHECKSIGVERIFY then
          if success then some { ts with st := { s with stack := rest }, weightLeft := weight } else none
        else some { ts with st := { s with stack := BitcoinScript.boolBytes success :: rest }, weightLeft := weight }
    | _ => none
  else if op == OP_CHECKSIGADD then
    -- (sig num pubkey -- num)
    match s.stack with
    | pubkey :: numv :: sig :: rest =>
      match BitcoinScript.toNum false 4 numv with
      | none => none
      | some num =>
        match evalChecksigTapscript c ed' sig pubkey ts.weightLeft with
        | none => none
        | some (success, weight) =>
          some { ts with st := { s with stack := BitcoinScript.serialize (num + (if success then 1 else 0)) :: rest },
                         weightLeft := weight }
    | _ => none
  else if op == BitcoinScript.OP_CHECKMULTISIG || op == BitcoinScript.OP_CHECKMULTISIGVERIFY then none
  else if op == BitcoinScript.OP_CODESEPARATOR then
    some { ts with codeseparatorPos := ts.opcodePos }
  else (BitcoinScript.execOp c.flags (tapOracle c) fExec op s).map fun s' => { ts with st := s' }

/-- One loop iteration of `EvalScript` under Tapscript: no operation count; the push-size test; the
disabled-opcode test (never reached, every disabled opcode being an `OP_SUCCESSx`); execute or skip;
the stack-size test; the opcode position advances on every instruction. -/
def tapStep (c : TapCtx) (ed : ExecData) (ts : TapState) : Instr → Option TapState
  | .push data =>
    let s := ts.st
    if BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE < data.length then none
    else
      let s' := if BitcoinScript.allTrue s.vfExec then { s with stack := data :: s.stack } else s
      if BitcoinScript.MAX_STACK_SIZE < s'.stack.length + s'.altstack.length then none
      else some { ts with st := s', opcodePos := ts.opcodePos + 1 }
  | .op op =>
    let s := ts.st
    let fExec := BitcoinScript.allTrue s.vfExec
    if BitcoinScript.isDisabled op then none
    else
      let r : Option TapState :=
        if fExec || (BitcoinScript.OP_IF ≤ op && op ≤ BitcoinScript.OP_ENDIF) then tapExecOp c ed fExec op ts
        else some ts
      match r with
      | none => none
      | some ts' =>
        if BitcoinScript.MAX_STACK_SIZE < ts'.st.stack.length + ts'.st.altstack.length then none
        else some { ts' with opcodePos := ts'.opcodePos + 1 }

def tapRun (c : TapCtx) (ed : ExecData) : TapState → Script → Option TapState
  | ts, [] => if ts.st.vfExec.isEmpty then some ts else none
  | ts, i :: rest =>
    match tapStep c ed ts i with
    | none => none
    | some ts' => tapRun c ed ts' rest

/-- `ExecuteWitnessScript(stack, script, flags, SigVersion::TAPSCRIPT, checker, execdata)`: the
`OP_SUCCESSx` scan, the initial stack-size and element-size limits, the run, and the clean-stack
requirement of exactly one true element. `stack` is top-first; `weight` is the initial validation
weight. -/
def executeTapscript (c : TapCtx) (ed : ExecData) (stack : List Bytes) (script : Bytes) (weight : Int) : Bool :=
  match opSuccessScan script.length script with
  | none => false
  | some true => true
  | some false =>
    if BitcoinScript.MAX_STACK_SIZE < stack.length then false
    else if stack.any (fun e => BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE < e.length) then false
    else match BitcoinSig.parseScript script with
      | none => false
      | some s =>
        match tapRun c ed ⟨⟨stack, [], [], 0⟩, weight, 0xFFFFFFFF, 0⟩ s with
        | none => false
        | some ts => decide (ts.st.stack.length = 1) && BitcoinVerify.topTrue ts.st.stack

/-! ### The version-1 branch of `VerifyWitnessProgram` -/

/-- `GetSerializeSize(witness.stack)`. -/
def witnessSerializedSize (witness : List Bytes) : Nat := (BitcoinSer.serList BitcoinSer.serBytes witness).length

/-- The annex: present when at least two elements remain and the last is non-empty and starts
with `0x50`. -/
def hasAnnex (witness : List Bytes) : Bool :=
  decide (2 ≤ witness.length) && (match witness.getLast? with
    | some (b :: _) => decide (b.toNat = ANNEX_TAG)
    | _ => false)

/-- The Taproot branch (version 1, 32-byte program, not P2SH, `TAPROOT` flag set), as a
`BitcoinVerify.TaprootHandler`, for the given spent outputs. -/
def taprootHandler (spent : List TxOut) : BitcoinVerify.TaprootHandler := fun c witness program =>
  if witness.isEmpty then false
  else
    let tc : TapCtx := ⟨BitcoinVerify.scriptFlagsOf c.flags, c.tx, spent, c.nIn⟩
    let annex? : Option Bytes := if hasAnnex witness then witness.getLast? else none
    let stack := if hasAnnex witness then witness.dropLast else witness
    let ed0 : ExecData := ⟨annex?.isSome, (match annex? with
        | some a => BitcoinSer.sha256 (BitcoinSer.serBytes a)
        | none => []), [], 0xFFFFFFFF⟩
    if stack.length = 1 then
      -- key path
      checkSchnorrSignature c.tx spent c.nIn (stack.getD 0 []) program false ed0
    else
      -- script path
      match stack.getLast? with
      | none => false
      | some control =>
        let stack := stack.dropLast
        match stack.getLast? with
        | none => false
        | some script =>
          let stack := stack.dropLast
          if control.length < TAPROOT_CONTROL_BASE_SIZE ∨ TAPROOT_CONTROL_MAX_SIZE < control.length ∨
             (control.length - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE ≠ 0 then false
          else
            let leafVersion := (control.getD 0 0).toNat &&& TAPROOT_LEAF_MASK
            let leafHash := tapleafHash (BitVec.ofNat 8 leafVersion) script
            if !verifyTaprootCommitment control program leafHash then false
            else if leafVersion = TAPROOT_LEAF_TAPSCRIPT then
              executeTapscript tc { ed0 with tapleafHash := leafHash } stack.reverse script
                ((witnessSerializedSize witness : Int) + VALIDATION_WEIGHT_OFFSET)
            else true   -- unknown leaf version: `DISCOURAGE_UPGRADABLE_TAPROOT_VERSION` is policy

/-- The complete `VerifyScript`, with the Taproot branch supplied. -/
def verifyScriptFull (spent : List TxOut) (c : BitcoinVerify.Ctx) (scriptSig scriptPubKey : Bytes)
    (witness : List Bytes) : Bool :=
  BitcoinVerify.verifyScript (taprootHandler spent) c scriptSig scriptPubKey witness

/-- The output script `OP_1 <32-byte key>` of a Taproot output. -/
def p2trBytes (q : Bytes) : Bytes := BitcoinVerify.witnessBytes 1 q

end BitcoinTaproot
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyWitnessProgram (version 1), ExecuteWitnessScript, EvalScript under SigVersion::TAPSCRIPT, EvalChecksigTapscript, CheckSchnorrSignature, SignatureHashSchnorr, ComputeTapleafHash, ComputeTapbranchHash, ComputeTaprootMerkleRoot, VerifyTaprootCommitment, src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; XOnlyPubKey::CheckTapTweak, ComputeTapTweakHash, src/pubkey.cpp; secp256k1_xonly_pubkey_tweak_add_check, src/secp256k1/src/modules/extrakeys/main_impl.h; IsOpSuccess, src/script/script.cpp; BIP340, BIP341, BIP342 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_BitcoinTaproot.lean (namespace BitcoinTaproot)

Conventions used below. A byte is an 8-bit value (an element of {0,…,255}\{0,\dots,255\}{0,…,255}); a byte string is a finite list of bytes, written with ∥\Vert∥ for concatenation, ∣s∣|s|∣s∣ for length, sjs_jsj​ for the jjj-th byte read as a natural number (the "default" value 000 is used wherever the file reads a position that does not exist), s[a:b]s[a{:}b]s[a:b] for "drop aaa bytes then take up to b−ab-ab−a bytes". BE(s)\mathrm{BE}(s)BE(s) is the big-endian natural value ∑jsj 256∣s∣−1−j\sum_j s_j\,256^{|s|-1-j}∑j​sj​256∣s∣−1−j of a byte string of any length. le32(x)\mathrm{le32}(x)le32(x) and le64(x)\mathrm{le64}(x)le64(x) are the 4- and 8-byte little-endian encodings of x mod 232x \bmod 2^{32}xmod232 and x mod 264x \bmod 2^{64}xmod264. CompactSize(m)\mathrm{CompactSize}(m)CompactSize(m) is [m][m][m] if m<253m < 253m<253, [0xfd]∥le16(m)[\texttt{0xfd}] \Vert \mathrm{le16}(m)[0xfd]∥le16(m) if m≤0xffffm \le \texttt{0xffff}m≤0xffff, [0xfe]∥le32(m)[\texttt{0xfe}] \Vert \mathrm{le32}(m)[0xfe]∥le32(m) if m≤0xffffffffm \le \texttt{0xffffffff}m≤0xffffffff, and [0xff]∥le64(m)[\texttt{0xff}] \Vert \mathrm{le64}(m)[0xff]∥le64(m) otherwise. serBytes(s)=CompactSize(∣s∣)∥s\mathrm{serBytes}(s) = \mathrm{CompactSize}(|s|) \Vert sserBytes(s)=CompactSize(∣s∣)∥s. SHA256\mathrm{SHA256}SHA256, SHA1\mathrm{SHA1}SHA1, RIPEMD160\mathrm{RIPEMD160}RIPEMD160, hash160=RIPEMD160∘SHA256\mathrm{hash160} = \mathrm{RIPEMD160}\circ\mathrm{SHA256}hash160=RIPEMD160∘SHA256 and hash256=SHA256∘SHA256\mathrm{hash256} = \mathrm{SHA256}\circ\mathrm{SHA256}hash256=SHA256∘SHA256 are the bundle's own implementations on byte lists. A transaction tx\mathrm{tx}tx has a natural version\mathrm{version}version, a list vin\mathrm{vin}vin of inputs (each: an outpoint consisting of a byte-string hash\mathrm{hash}hash and a natural index nnn; a scriptSig byte string; a natural nSequence\mathrm{nSequence}nSequence; a witness list of byte strings), a list vout\mathrm{vout}vout of outputs (each: an integer nValue\mathrm{nValue}nValue and a byte-string scriptPubKey\mathrm{scriptPubKey}scriptPubKey), and a natural nLockTime\mathrm{nLockTime}nLockTime. serOutPoint(h,n)=h∥le32(n)\mathrm{serOutPoint}(h, n) = h \Vert \mathrm{le32}(n)serOutPoint(h,n)=h∥le32(n) and serTxOut(v,s)=le64(v mod 264)∥serBytes(s)\mathrm{serTxOut}(v, s) = \mathrm{le64}(v \bmod 2^{64}) \Vert \mathrm{serBytes}(s)serTxOut(v,s)=le64(vmod264)∥serBytes(s) (two's complement for negative vvv). The secp256k1 constants are p=2256−232−977p = 2^{256} - 2^{32} - 977p=2256−232−977, the group order nnn, and the base point GGG; points are either the point at infinity ("none") or affine pairs of naturals, added with the bundle's affine formulas padd\mathrm{padd}padd and multiplied by scalars with its 257-step double-and-add pmul\mathrm{pmul}pmul (so pmul(0,P)\mathrm{pmul}(0, P)pmul(0,P) is the point at infinity). "None" is the failure value of an optional result; Boolean results are true/false\mathrm{true}/\mathrm{false}true/false.


TAPROOT_LEAF_MASK — the natural number 0xfe=254\texttt{0xfe} = 2540xfe=254.

TAPROOT_LEAF_TAPSCRIPT — the natural number 0xc0=192\texttt{0xc0} = 1920xc0=192.

TAPROOT_CONTROL_BASE_SIZE — the natural number 333333.

TAPROOT_CONTROL_NODE_SIZE — the natural number 323232.

TAPROOT_CONTROL_MAX_NODE_COUNT — the natural number 128128128.

TAPROOT_CONTROL_MAX_SIZE — the natural number 33+32⋅128=412933 + 32 \cdot 128 = 412933+32⋅128=4129.

ANNEX_TAG — the natural number 0x50=80\texttt{0x50} = 800x50=80.

VALIDATION_WEIGHT_OFFSET — the integer 505050.

VALIDATION_WEIGHT_PER_SIGOP_PASSED — the integer 505050.

SIGHASH_DEFAULT — the natural number 000.

OP_CHECKSIGADD — the byte 0xba=186\texttt{0xba} = 1860xba=186.

tagged — for a string tag\mathrm{tag}tag and a byte string mmm, tagged(tag,m)=SHA256(SHA256(T)∥SHA256(T)∥m)\mathrm{tagged}(\mathrm{tag}, m) = \mathrm{SHA256}(\mathrm{SHA256}(T) \Vert \mathrm{SHA256}(T) \Vert m)tagged(tag,m)=SHA256(SHA256(T)∥SHA256(T)∥m) where TTT is the UTF-8 byte encoding of tag\mathrm{tag}tag (the bundle's taggedHash applied to ascii tag).

tapleafHash — for a byte vvv (the leaf version) and a byte string script\mathrm{script}script, tapleafHash(v,script)=tagged("TapLeaf",[v]∥CompactSize(∣script∣)∥script)\mathrm{tapleafHash}(v, \mathrm{script}) = \mathrm{tagged}(\texttt{"TapLeaf"}, [v] \Vert \mathrm{CompactSize}(|\mathrm{script}|) \Vert \mathrm{script})tapleafHash(v,script)=tagged("TapLeaf",[v]∥CompactSize(∣script∣)∥script). No bound on ∣script∣|\mathrm{script}|∣script∣ is imposed; an empty script gives [v,0x00][v, \texttt{0x00}][v,0x00] as the message.

lexLt — a Boolean strict lexicographic order on byte strings, defined by recursion: lexLt([ ],[ ])=false\mathrm{lexLt}([\,],[\,]) = \mathrm{false}lexLt([],[])=false; lexLt([ ],b::bs)=true\mathrm{lexLt}([\,], b{::}bs) = \mathrm{true}lexLt([],b::bs)=true; lexLt(a::as,[ ])=false\mathrm{lexLt}(a{::}as, [\,]) = \mathrm{false}lexLt(a::as,[])=false; lexLt(a::as,b::bs)\mathrm{lexLt}(a{::}as, b{::}bs)lexLt(a::as,b::bs) is true\mathrm{true}true if a<ba < ba<b (as naturals), false\mathrm{false}false if b<ab < ab<a, and lexLt(as,bs)\mathrm{lexLt}(as, bs)lexLt(as,bs) if a=ba = ba=b. Thus a proper prefix is less than its extension, and equal strings are not less.

tapbranchHash — for byte strings a,ba, ba,b: tapbranchHash(a,b)=tagged("TapBranch",a∥b)\mathrm{tapbranchHash}(a, b) = \mathrm{tagged}(\texttt{"TapBranch"}, a \Vert b)tapbranchHash(a,b)=tagged("TapBranch",a∥b) if lexLt(a,b)\mathrm{lexLt}(a, b)lexLt(a,b), and tagged("TapBranch",b∥a)\mathrm{tagged}(\texttt{"TapBranch"}, b \Vert a)tagged("TapBranch",b∥a) otherwise (including when a=ba = ba=b, where both concatenations coincide). No length requirement on aaa or bbb.

controlNodes — for a byte string control\mathrm{control}control, the list of its "path nodes": let k=⌊(∣control∣−˙33)/32⌋k = \lfloor (|\mathrm{control}| \dot- 33) / 32 \rfloork=⌊(∣control∣−˙​33)/32⌋, where −˙\dot-−˙​ is natural-number subtraction (so k=0k = 0k=0 whenever ∣control∣≤33|\mathrm{control}| \le 33∣control∣≤33, and also kkk ignores any trailing fewer-than-32 bytes), and let sss be control\mathrm{control}control with its first 333333 bytes dropped (all of it dropped if shorter). The result is the list of kkk chunks s[0:32], s[32:64], …, s[32(k−1):32k]s[0{:}32],\ s[32{:}64],\ \dots,\ s[32(k-1){:}32k]s[0:32], s[32:64], …, s[32(k−1):32k], produced by an inner recursion that, with counter k′+1k' + 1k′+1 and remaining string s′s's′, emits "take 323232 of s′s's′" and recurses on "drop 323232 of s′s's′" with counter k′k'k′, and emits nothing at counter 000. Because kkk is the floor, every emitted chunk has exactly 323232 bytes.

taprootMerkleRoot — for byte strings control\mathrm{control}control and leafHash\mathrm{leafHash}leafHash, the left fold of tapbranchHash\mathrm{tapbranchHash}tapbranchHash over controlNodes(control)\mathrm{controlNodes}(\mathrm{control})controlNodes(control) starting at leafHash\mathrm{leafHash}leafHash: h0=leafHashh_0 = \mathrm{leafHash}h0​=leafHash, hj+1=tapbranchHash(hj,Nj)h_{j+1} = \mathrm{tapbranchHash}(h_j, N_j)hj+1​=tapbranchHash(hj​,Nj​) for the nodes N0,…,Nk−1N_0, \dots, N_{k-1}N0​,…,Nk−1​ in order, result hkh_khk​. With no nodes it is leafHash\mathrm{leafHash}leafHash itself.

tapTweakHash — for byte strings internal32\mathrm{internal32}internal32 and merkleRoot\mathrm{merkleRoot}merkleRoot (of any lengths), tagged("TapTweak",internal32∥merkleRoot)\mathrm{tagged}(\texttt{"TapTweak"}, \mathrm{internal32} \Vert \mathrm{merkleRoot})tagged("TapTweak",internal32∥merkleRoot).

be32 — for a natural xxx, the 323232-byte big-endian encoding of x mod 2256x \bmod 2^{256}xmod2256 (the reverse of the 323232-byte little-endian encoding, which truncates modulo 22562^{256}2256).

xonlyTweakAddCheck — for a byte string output32\mathrm{output32}output32, a Boolean parity\mathrm{parity}parity, an affine point P=(Px,Py)P = (P_x, P_y)P=(Px​,Py​) given as a pair of naturals (no on-curve check is made here), and a byte string tweak32\mathrm{tweak32}tweak32: let t=BE(tweak32)t = \mathrm{BE}(\mathrm{tweak32})t=BE(tweak32); if n≤tn \le tn≤t the result is false\mathrm{false}false; otherwise compute Q=padd(P,pmul(t,G))Q = \mathrm{padd}(P, \mathrm{pmul}(t, G))Q=padd(P,pmul(t,G)); if QQQ is the point at infinity the result is false\mathrm{false}false; otherwise, with Q=(qx,qy)Q = (q_x, q_y)Q=(qx​,qy​), the result is true\mathrm{true}true iff be32(qx)=output32\mathrm{be32}(q_x) = \mathrm{output32}be32(qx​)=output32 (so output32\mathrm{output32}output32 must have exactly 323232 bytes) and the proposition "qy mod 2=1q_y \bmod 2 = 1qy​mod2=1" has the same truth value as parity\mathrm{parity}parity. When t=0t = 0t=0, pmul(0,G)\mathrm{pmul}(0, G)pmul(0,G) is the point at infinity and Q=PQ = PQ=P.

checkTapTweak — for byte strings qqq, internal32\mathrm{internal32}internal32, merkleRoot\mathrm{merkleRoot}merkleRoot and a Boolean parity\mathrm{parity}parity: let x=BE(internal32)x = \mathrm{BE}(\mathrm{internal32})x=BE(internal32) (no length check on internal32\mathrm{internal32}internal32); if x≥px \ge px≥p, or if x3+7x^3 + 7x3+7 is not a quadratic residue modulo ppp (tested by y:=(x3+7)(p+1)/4 mod py := (x^3+7)^{(p+1)/4} \bmod py:=(x3+7)(p+1)/4modp and y2≡x3+7y^2 \equiv x^3 + 7y2≡x3+7), the result is false\mathrm{false}false; otherwise let PPP be the point with abscissa xxx and even ordinate (yyy if yyy is even, (p−y) mod p(p - y) \bmod p(p−y)modp otherwise) and return xonlyTweakAddCheck(q,parity,P,tapTweakHash(internal32,merkleRoot))\mathrm{xonlyTweakAddCheck}(q, \mathrm{parity}, P, \mathrm{tapTweakHash}(\mathrm{internal32}, \mathrm{merkleRoot}))xonlyTweakAddCheck(q,parity,P,tapTweakHash(internal32,merkleRoot)).

verifyTaprootCommitment — for byte strings control\mathrm{control}control, program\mathrm{program}program, leafHash\mathrm{leafHash}leafHash: checkTapTweak(program, control[1:33], taprootMerkleRoot(control,leafHash), π)\mathrm{checkTapTweak}(\mathrm{program},\ \mathrm{control}[1{:}33],\ \mathrm{taprootMerkleRoot}(\mathrm{control}, \mathrm{leafHash}),\ \pi)checkTapTweak(program, control[1:33], taprootMerkleRoot(control,leafHash), π) where control[1:33]\mathrm{control}[1{:}33]control[1:33] is "drop one byte, take up to 323232" (shorter if control\mathrm{control}control is short, empty if ∣control∣≤1|\mathrm{control}| \le 1∣control∣≤1) and π\piπ is the Boolean "control0 mod 2=1\mathrm{control}_0 \bmod 2 = 1control0​mod2=1" with control0=0\mathrm{control}_0 = 0control0​=0 when control\mathrm{control}control is empty. No length constraint on control\mathrm{control}control or program\mathrm{program}program is checked in this function itself.

ExecData — a record with four fields: annexPresent\mathrm{annexPresent}annexPresent (Boolean), annexHash\mathrm{annexHash}annexHash (byte string), tapleafHash\mathrm{tapleafHash}tapleafHash (byte string), codeseparatorPos\mathrm{codeseparatorPos}codeseparatorPos (natural number). No invariant ties the fields together (e.g. annexHash\mathrm{annexHash}annexHash may be non-empty while annexPresent\mathrm{annexPresent}annexPresent is false).

sigHashSchnorr — a function of a transaction tx\mathrm{tx}tx, a list spent\mathrm{spent}spent of outputs, naturals inPos\mathrm{inPos}inPos and hashType\mathrm{hashType}hashType, a Boolean tapscript\mathrm{tapscript}tapscript and an ExecData\mathrm{ExecData}ExecData e=(a,A,L,κ)e = (a, A, L, \kappa)e=(a,A,L,κ), returning an optional byte string. If ¬(hashType≤3∨(0x81≤hashType≤0x83))\neg(\mathrm{hashType} \le 3 \lor (\texttt{0x81} \le \mathrm{hashType} \le \texttt{0x83}))¬(hashType≤3∨(0x81≤hashType≤0x83)), i.e. hashType∉{0,1,2,3,0x81,0x82,0x83}\mathrm{hashType} \notin \{0,1,2,3,\texttt{0x81},\texttt{0x82},\texttt{0x83}\}hashType∈/{0,1,2,3,0x81,0x82,0x83} (in particular 0x80\texttt{0x80}0x80 is excluded), the result is none. Otherwise: o:=1o := 1o:=1 if hashType=0\mathrm{hashType} = 0hashType=0, else hashType & 3\mathrm{hashType} \,\&\, 3hashType&3; ι:=hashType & 0x80\iota := \mathrm{hashType} \,\&\, \texttt{0x80}ι:=hashType&0x80; extFlag:=1\mathrm{extFlag} := 1extFlag:=1 if tapscript\mathrm{tapscript}tapscript else 000; ς:=2 extFlag+(1 if a else 0)\varsigma := 2\,\mathrm{extFlag} + (1 \text{ if } a \text{ else } 0)ς:=2extFlag+(1 if a else 0); I:=I :=I:= the input vininPos\mathrm{vin}_{\mathrm{inPos}}vininPos​, or, when inPos≥∣vin∣\mathrm{inPos} \ge |\mathrm{vin}|inPos≥∣vin∣, the default input with outpoint (empty hash, index 000), empty scriptSig, sequence 000, empty witness. If o=3o = 3o=3: when ∣vout∣≤inPos|\mathrm{vout}| \le \mathrm{inPos}∣vout∣≤inPos the whole result is none, otherwise single:=SHA256(serTxOut(voutinPos))\mathrm{single} := \mathrm{SHA256}(\mathrm{serTxOut}(\mathrm{vout}_{\mathrm{inPos}}))single:=SHA256(serTxOut(voutinPos​)) (the default (−1,[ ])(-1, [\,])(−1,[]) written in the code is unreachable here because of the length test); if o≠3o \neq 3o=3, single:=[ ]\mathrm{single} := [\,]single:=[]. The result is then some\mathrm{some}some of

tagged("TapSighash", [0x00, hashType mod 256]∥le32(version)∥le32(nLockTime)∥Hin∥Hout∥[ς]∥D∥(A if a else [ ])∥single∥E),\mathrm{tagged}\Big(\texttt{"TapSighash"},\ [\texttt{0x00},\ \mathrm{hashType} \bmod 256] \Vert \mathrm{le32}(\mathrm{version}) \Vert \mathrm{le32}(\mathrm{nLockTime}) \Vert H_{\mathrm{in}} \Vert H_{\mathrm{out}} \Vert [\varsigma] \Vert D \Vert (A \text{ if } a \text{ else } [\,]) \Vert \mathrm{single} \Vert E\Big),tagged("TapSighash", [0x00, hashTypemod256]∥le32(version)∥le32(nLockTime)∥Hin​∥Hout​∥[ς]∥D∥(A if a else [])∥single∥E),

where Hin=[ ]H_{\mathrm{in}} = [\,]Hin​=[] if ι=0x80\iota = \texttt{0x80}ι=0x80 and otherwise Hin=SHA256(∥i∈vinserOutPoint(i.prevout))∥SHA256(∥u∈spentle64(u.nValue mod 264))∥SHA256(∥u∈spentserBytes(u.scriptPubKey))∥SHA256(∥i∈vinle32(i.nSequence))H_{\mathrm{in}} = \mathrm{SHA256}(\Vert_{i \in \mathrm{vin}} \mathrm{serOutPoint}(i.\mathrm{prevout})) \Vert \mathrm{SHA256}(\Vert_{u \in \mathrm{spent}} \mathrm{le64}(u.\mathrm{nValue} \bmod 2^{64})) \Vert \mathrm{SHA256}(\Vert_{u \in \mathrm{spent}} \mathrm{serBytes}(u.\mathrm{scriptPubKey})) \Vert \mathrm{SHA256}(\Vert_{i \in \mathrm{vin}} \mathrm{le32}(i.\mathrm{nSequence}))Hin​=SHA256(∥i∈vin​serOutPoint(i.prevout))∥SHA256(∥u∈spent​le64(u.nValuemod264))∥SHA256(∥u∈spent​serBytes(u.scriptPubKey))∥SHA256(∥i∈vin​le32(i.nSequence)) (the spent\mathrm{spent}spent list is hashed in full, whatever its length relative to vin\mathrm{vin}vin); Hout=SHA256(∥u∈voutserTxOut(u))H_{\mathrm{out}} = \mathrm{SHA256}(\Vert_{u \in \mathrm{vout}} \mathrm{serTxOut}(u))Hout​=SHA256(∥u∈vout​serTxOut(u)) if o=1o = 1o=1 and [ ][\,][] otherwise (so for o∈{2,3}o \in \{2, 3\}o∈{2,3} nothing); D=serOutPoint(I.prevout)∥serTxOut(spentinPos or (−1,[ ]) if inPos≥∣spent∣)∥le32(I.nSequence)D = \mathrm{serOutPoint}(I.\mathrm{prevout}) \Vert \mathrm{serTxOut}(\mathrm{spent}_{\mathrm{inPos}} \text{ or } (-1, [\,]) \text{ if } \mathrm{inPos} \ge |\mathrm{spent}|) \Vert \mathrm{le32}(I.\mathrm{nSequence})D=serOutPoint(I.prevout)∥serTxOut(spentinPos​ or (−1,[]) if inPos≥∣spent∣)∥le32(I.nSequence) if ι=0x80\iota = \texttt{0x80}ι=0x80, and D=le32(inPos)D = \mathrm{le32}(\mathrm{inPos})D=le32(inPos) otherwise; E=L∥[0x00]∥le32(κ)E = L \Vert [\texttt{0x00}] \Vert \mathrm{le32}(\kappa)E=L∥[0x00]∥le32(κ) if tapscript\mathrm{tapscript}tapscript and [ ][\,][] otherwise. The default value −1-1−1 serializes as ff8\texttt{ff}^{8}ff8.

checkSchnorrSignature — a Boolean function of a transaction tx\mathrm{tx}tx, a list spent\mathrm{spent}spent, a natural nIn\mathrm{nIn}nIn, byte strings sig\mathrm{sig}sig and pubkey32\mathrm{pubkey32}pubkey32, a Boolean tapscript\mathrm{tapscript}tapscript and an ExecData\mathrm{ExecData}ExecData eee. If ∣sig∣≠64|\mathrm{sig}| \neq 64∣sig∣=64 and ∣sig∣≠65|\mathrm{sig}| \neq 65∣sig∣=65: false\mathrm{false}false. Otherwise hashType:=\mathrm{hashType} :=hashType:= the last byte of sig\mathrm{sig}sig (as a natural) if ∣sig∣=65|\mathrm{sig}| = 65∣sig∣=65, else 000; sig′:=sig\mathrm{sig}' := \mathrm{sig}sig′:=sig without its last byte if ∣sig∣=65|\mathrm{sig}| = 65∣sig∣=65, else sig\mathrm{sig}sig. If ∣sig∣=65|\mathrm{sig}| = 65∣sig∣=65 and hashType=0\mathrm{hashType} = 0hashType=0: false\mathrm{false}false. Otherwise evaluate sigHashSchnorr(tx,spent,nIn,hashType,tapscript,e)\mathrm{sigHashSchnorr}(\mathrm{tx}, \mathrm{spent}, \mathrm{nIn}, \mathrm{hashType}, \mathrm{tapscript}, e)sigHashSchnorr(tx,spent,nIn,hashType,tapscript,e): if none, false\mathrm{false}false; if some(h)\mathrm{some}(h)some(h), the result is schnorrVerify(pubkey32,h,sig′)\mathrm{schnorrVerify}(\mathrm{pubkey32}, h, \mathrm{sig}')schnorrVerify(pubkey32,h,sig′), the bundle's BIP340 verifier: false\mathrm{false}false unless ∣pubkey32∣=32|\mathrm{pubkey32}| = 32∣pubkey32∣=32 and ∣sig′∣=64|\mathrm{sig}'| = 64∣sig′∣=64; with r=BE(sig′[0:32])r = \mathrm{BE}(\mathrm{sig}'[0{:}32])r=BE(sig′[0:32]), s=BE(sig′[32:64])s = \mathrm{BE}(\mathrm{sig}'[32{:}64])s=BE(sig′[32:64]), false\mathrm{false}false if p≤rp \le rp≤r or n≤sn \le sn≤s; false\mathrm{false}false if BE(pubkey32)\mathrm{BE}(\mathrm{pubkey32})BE(pubkey32) does not lift (as in checkTapTweak) to a point PPP with even ordinate; else with c=BE(tagged("BIP0340/challenge",sig′[0:32]∥pubkey32∥h)) mod nc = \mathrm{BE}(\mathrm{tagged}(\texttt{"BIP0340/challenge"}, \mathrm{sig}'[0{:}32] \Vert \mathrm{pubkey32} \Vert h)) \bmod nc=BE(tagged("BIP0340/challenge",sig′[0:32]∥pubkey32∥h))modn and R=padd(pmul(s,G),pmul((n−c) mod n,P))R = \mathrm{padd}(\mathrm{pmul}(s, G), \mathrm{pmul}((n - c) \bmod n, P))R=padd(pmul(s,G),pmul((n−c)modn,P)), false\mathrm{false}false if RRR is the point at infinity, else true\mathrm{true}true iff RyR_yRy​ is even and Rx=rR_x = rRx​=r. This function itself imposes no length condition on pubkey32\mathrm{pubkey32}pubkey32.

isOpSuccess — for a natural ccc, the Boolean "c=80c = 80c=80 or c=98c = 98c=98 or 126≤c≤129126 \le c \le 129126≤c≤129 or 131≤c≤134131 \le c \le 134131≤c≤134 or 137≤c≤138137 \le c \le 138137≤c≤138 or 141≤c≤142141 \le c \le 142141≤c≤142 or 149≤c≤153149 \le c \le 153149≤c≤153 or 187≤c≤254187 \le c \le 254187≤c≤254".

opSuccessScan — a function of a fuel f∈Nf \in \mathbb{N}f∈N and a byte string sss returning an optional Boolean, by recursion: if s=[ ]s = [\,]s=[], some(false)\mathrm{some}(\mathrm{false})some(false) (whatever fff); else if f=0f = 0f=0, none; else read one instruction from sss with the bundle's getOp (first byte ooo: if o≤0x4eo \le \texttt{0x4e}o≤0x4e it is a push — of ooo bytes when o<0x4co < \texttt{0x4c}o<0x4c, or of a length given by the next 1, 2 or 4 little-endian bytes for o=0x4c,0x4d,0x4eo = \texttt{0x4c}, \texttt{0x4d}, \texttt{0x4e}o=0x4c,0x4d,0x4e — and the read fails if the length bytes or the data are missing; if o>0x4eo > \texttt{0x4e}o>0x4e it is the opcode ooo with no data); if the read fails, none; if it is a push, recurse on the remainder with fuel f−1f - 1f−1; if it is an opcode ccc with isOpSuccess(c)\mathrm{isOpSuccess}(c)isOpSuccess(c), some(true)\mathrm{some}(\mathrm{true})some(true); otherwise recurse on the remainder with fuel f−1f - 1f−1.

TapCtx — a record with fields flags\mathrm{flags}flags (the Script-layer flag record: Booleans cltv\mathrm{cltv}cltv, csv\mathrm{csv}csv, nulldummy\mathrm{nulldummy}nulldummy), tx\mathrm{tx}tx (a transaction), spent\mathrm{spent}spent (a list of outputs), nIn\mathrm{nIn}nIn (a natural).

tapOracle — for a TapCtx\mathrm{TapCtx}TapCtx ccc, the Script-layer oracle record whose hash fields are the bundle's RIPEMD160\mathrm{RIPEMD160}RIPEMD160, SHA1\mathrm{SHA1}SHA1, SHA256\mathrm{SHA256}SHA256, hash160\mathrm{hash160}hash160, hash256\mathrm{hash256}hash256; whose checkSig\mathrm{checkSig}checkSig field is the constant function returning none for every (signature, key) pair (a script failure if ever consulted); whose checkLockTime\mathrm{checkLockTime}checkLockTime is the bundle's checkLockTime for c.txc.\mathrm{tx}c.tx, c.nInc.\mathrm{nIn}c.nIn (an integer lock time λ\lambdaλ is accepted iff λ\lambdaλ and tx.nLockTime\mathrm{tx}.\mathrm{nLockTime}tx.nLockTime are on the same side of 500,000,000500{,}000{,}000500,000,000, λ≤tx.nLockTime\lambda \le \mathrm{tx}.\mathrm{nLockTime}λ≤tx.nLockTime, and the sequence of input nIn\mathrm{nIn}nIn — default input if out of range — is not 0xffffffff\texttt{0xffffffff}0xffffffff); and whose checkSequence\mathrm{checkSequence}checkSequence is the bundle's checkSequence for c.txc.\mathrm{tx}c.tx, c.nInc.\mathrm{nIn}c.nIn (rejects if tx.version<2\mathrm{tx}.\mathrm{version} < 2tx.version<2 or the input's sequence has bit 313131 set; otherwise compares the masked (bits 000–151515 and 222222) values, requiring same type flag and seqmasked≤txseqmasked\mathrm{seq}_{\text{masked}} \le \mathrm{txseq}_{\text{masked}}seqmasked​≤txseqmasked​, where the script operand is converted to a natural by truncating negatives to 000).

TapState — a record with fields st\mathrm{st}st (the Script-layer interpreter state: main stack\mathrm{stack}stack, altstack\mathrm{altstack}altstack, condition stack vfExec\mathrm{vfExec}vfExec — all lists with the top first — and a natural opCount\mathrm{opCount}opCount), weightLeft\mathrm{weightLeft}weightLeft (an integer), codeseparatorPos\mathrm{codeseparatorPos}codeseparatorPos (a natural) and opcodePos\mathrm{opcodePos}opcodePos (a natural).

evalChecksigTapscript — for a TapCtx\mathrm{TapCtx}TapCtx ccc, an ExecData\mathrm{ExecData}ExecData eee, byte strings sig\mathrm{sig}sig and pubkey\mathrm{pubkey}pubkey, and an integer www, an optional pair (Boolean, integer): success:=(sig≠[ ])\mathrm{success} := (\mathrm{sig} \neq [\,])success:=(sig=[]); w′:=w−50w' := w - 50w′:=w−50 if success\mathrm{success}success else www (integer arithmetic, may be negative); if success\mathrm{success}success and w′<0w' < 0w′<0: none; else if ∣pubkey∣=0|\mathrm{pubkey}| = 0∣pubkey∣=0: none; else if ∣pubkey∣=32|\mathrm{pubkey}| = 32∣pubkey∣=32: none if success\mathrm{success}success and checkSchnorrSignature(c.tx,c.spent,c.nIn,sig,pubkey,true,e)\mathrm{checkSchnorrSignature}(c.\mathrm{tx}, c.\mathrm{spent}, c.\mathrm{nIn}, \mathrm{sig}, \mathrm{pubkey}, \mathrm{true}, e)checkSchnorrSignature(c.tx,c.spent,c.nIn,sig,pubkey,true,e) is false\mathrm{false}false, otherwise some(success,w′)\mathrm{some}(\mathrm{success}, w')some(success,w′); else (any other non-zero key length) some(success,w′)\mathrm{some}(\mathrm{success}, w')some(success,w′) with no verification. With an empty signature, no verification is performed for any key length, and the weight is unchanged.

tapExecOp — for a TapCtx\mathrm{TapCtx}TapCtx ccc, an ExecData\mathrm{ExecData}ExecData eee, a Boolean fExec\mathrm{fExec}fExec, an opcode byte op\mathrm{op}op and a TapState\mathrm{TapState}TapState ts\mathrm{ts}ts with state s=ts.sts = \mathrm{ts}.\mathrm{st}s=ts.st, an optional TapState\mathrm{TapState}TapState; let e′e'e′ be eee with codeseparatorPos:=ts.codeseparatorPos\mathrm{codeseparatorPos} := \mathrm{ts}.\mathrm{codeseparatorPos}codeseparatorPos:=ts.codeseparatorPos. Cases in order. (1) op∈{0x63,0x64}\mathrm{op} \in \{\texttt{0x63}, \texttt{0x64}\}op∈{0x63,0x64} (OP_IF, OP_NOTIF): if fExec\mathrm{fExec}fExec, then none if the main stack is empty, none if its top ttt has ∣t∣>1|t| > 1∣t∣>1 or (∣t∣=1|t| = 1∣t∣=1 and t0≠1t_0 \neq 1t0​=1), and otherwise the legacy execOp result (pop ttt, push "ttt is true" — any non-zero byte except a lone final 0x80\texttt{0x80}0x80 — negated for OP_NOTIF, onto vfExec\mathrm{vfExec}vfExec) placed into ts\mathrm{ts}ts; if not fExec\mathrm{fExec}fExec, the legacy result (push false\mathrm{false}false onto vfExec\mathrm{vfExec}vfExec) placed into ts\mathrm{ts}ts. (2) op∈{0xac,0xad}\mathrm{op} \in \{\texttt{0xac}, \texttt{0xad}\}op∈{0xac,0xad} (OP_CHECKSIG, OP_CHECKSIGVERIFY), regardless of fExec\mathrm{fExec}fExec: none unless the stack is pubkey::sig::rest\mathrm{pubkey} :: \mathrm{sig} :: \mathrm{rest}pubkey::sig::rest; then evalChecksigTapscript(c,e′,sig,pubkey,ts.weightLeft)\mathrm{evalChecksigTapscript}(c, e', \mathrm{sig}, \mathrm{pubkey}, \mathrm{ts}.\mathrm{weightLeft})evalChecksigTapscript(c,e′,sig,pubkey,ts.weightLeft): none gives none; some(success,w′)\mathrm{some}(\mathrm{success}, w')some(success,w′) gives, for OP_CHECKSIGVERIFY, ts\mathrm{ts}ts with stack rest\mathrm{rest}rest and weight w′w'w′ if success\mathrm{success}success, else none; for OP_CHECKSIG, ts\mathrm{ts}ts with stack boolBytes(success)::rest\mathrm{boolBytes}(\mathrm{success}) :: \mathrm{rest}boolBytes(success)::rest ([1][1][1] or [ ][\,][]) and weight w′w'w′. (3) op=0xba\mathrm{op} = \texttt{0xba}op=0xba (OP_CHECKSIGADD), regardless of fExec\mathrm{fExec}fExec: none unless the stack is pubkey::numv::sig::rest\mathrm{pubkey} :: \mathrm{numv} :: \mathrm{sig} :: \mathrm{rest}pubkey::numv::sig::rest; none if ∣numv∣>4|\mathrm{numv}| > 4∣numv∣>4; otherwise num\mathrm{num}num is the script-number value of numv\mathrm{numv}numv (little-endian magnitude with sign bit in the last byte, no minimality requirement, empty is 000); then evalChecksigTapscript(c,e′,sig,pubkey,ts.weightLeft)\mathrm{evalChecksigTapscript}(c, e', \mathrm{sig}, \mathrm{pubkey}, \mathrm{ts}.\mathrm{weightLeft})evalChecksigTapscript(c,e′,sig,pubkey,ts.weightLeft): none gives none, else ts\mathrm{ts}ts with stack serialize(num+[success])::rest\mathrm{serialize}(\mathrm{num} + [\mathrm{success}]) :: \mathrm{rest}serialize(num+[success])::rest (minimal script-number encoding) and weight w′w'w′. (4) op∈{0xae,0xaf}\mathrm{op} \in \{\texttt{0xae}, \texttt{0xaf}\}op∈{0xae,0xaf} (OP_CHECKMULTISIG(VERIFY)): none, regardless of everything else. (5) op=0xab\mathrm{op} = \texttt{0xab}op=0xab (OP_CODESEPARATOR), regardless of fExec\mathrm{fExec}fExec: ts\mathrm{ts}ts with codeseparatorPos:=ts.opcodePos\mathrm{codeseparatorPos} := \mathrm{ts}.\mathrm{opcodePos}codeseparatorPos:=ts.opcodePos and nothing else changed. (6) Any other byte: the legacy execOp with flags c.flagsc.\mathrm{flags}c.flags, oracle tapOracle(c)\mathrm{tapOracle}(c)tapOracle(c), fExec\mathrm{fExec}fExec, op\mathrm{op}op and sss, placed into ts\mathrm{ts}ts (none when it fails; it fails for unknown opcodes, OP_RETURN, OP_VERIF/OP_VERNOTIF, etc., and treats 0x4f\texttt{0x4f}0x4f–0x60\texttt{0x60}0x60 as number pushes). Only st\mathrm{st}st is touched in case (6); weightLeft\mathrm{weightLeft}weightLeft, codeseparatorPos\mathrm{codeseparatorPos}codeseparatorPos, opcodePos\mathrm{opcodePos}opcodePos are preserved there.

tapStep — for ccc, eee, a TapState\mathrm{TapState}TapState ts\mathrm{ts}ts and one parsed instruction, an optional TapState\mathrm{TapState}TapState. For a push of data ddd: none if ∣d∣>520|d| > 520∣d∣>520; otherwise s′:=ss' := ss′:=s with ddd pushed on the main stack if all entries of vfExec\mathrm{vfExec}vfExec are true\mathrm{true}true (vacuously so when empty), else s′:=ss' := ss′:=s; none if ∣s′.stack∣+∣s′.altstack∣>1000|s'.\mathrm{stack}| + |s'.\mathrm{altstack}| > 1000∣s′.stack∣+∣s′.altstack∣>1000; else ts\mathrm{ts}ts with st:=s′\mathrm{st} := s'st:=s′ and opcodePos\mathrm{opcodePos}opcodePos incremented by 111. For an opcode byte op\mathrm{op}op: fExec:=\mathrm{fExec} :=fExec:= all entries of vfExec\mathrm{vfExec}vfExec are true\mathrm{true}true; none if op\mathrm{op}op is one of the fifteen disabled opcodes (0x7e\texttt{0x7e}0x7e–0x81\texttt{0x81}0x81, 0x83\texttt{0x83}0x83–0x86\texttt{0x86}0x86, 0x8d\texttt{0x8d}0x8d, 0x8e\texttt{0x8e}0x8e, 0x95\texttt{0x95}0x95–0x99\texttt{0x99}0x99); otherwise r:=tapExecOp(c,e,fExec,op,ts)r := \mathrm{tapExecOp}(c, e, \mathrm{fExec}, \mathrm{op}, \mathrm{ts})r:=tapExecOp(c,e,fExec,op,ts) if fExec\mathrm{fExec}fExec or 0x63≤op≤0x68\texttt{0x63} \le \mathrm{op} \le \texttt{0x68}0x63≤op≤0x68 (this range includes 0x65\texttt{0x65}0x65, 0x66\texttt{0x66}0x66), and r:=some(ts)r := \mathrm{some}(\mathrm{ts})r:=some(ts) otherwise; if rrr is none, none; else, for r=some(ts′)r = \mathrm{some}(\mathrm{ts}')r=some(ts′), none if ∣ts′.st.stack∣+∣ts′.st.altstack∣>1000|\mathrm{ts}'.\mathrm{st}.\mathrm{stack}| + |\mathrm{ts}'.\mathrm{st}.\mathrm{altstack}| > 1000∣ts′.st.stack∣+∣ts′.st.altstack∣>1000, else ts′\mathrm{ts}'ts′ with opcodePos\mathrm{opcodePos}opcodePos incremented by 111. No operation count is kept.

tapRun — for ccc, eee, a TapState\mathrm{TapState}TapState and a parsed script (list of instructions), an optional TapState\mathrm{TapState}TapState: on the empty script, some(ts)\mathrm{some}(\mathrm{ts})some(ts) if ts.st.vfExec\mathrm{ts}.\mathrm{st}.\mathrm{vfExec}ts.st.vfExec is empty and none otherwise; on i::resti :: \mathrm{rest}i::rest, apply tapStep\mathrm{tapStep}tapStep to iii, propagate none, and continue on rest\mathrm{rest}rest from the new state.

executeTapscript — a Boolean function of a TapCtx\mathrm{TapCtx}TapCtx ccc, an ExecData\mathrm{ExecData}ExecData eee, a list stack\mathrm{stack}stack of byte strings (top first), a byte string script\mathrm{script}script and an integer weight\mathrm{weight}weight. Evaluate opSuccessScan(∣script∣,script)\mathrm{opSuccessScan}(|\mathrm{script}|, \mathrm{script})opSuccessScan(∣script∣,script): none gives false\mathrm{false}false; some(true)\mathrm{some}(\mathrm{true})some(true) gives true\mathrm{true}true at once (no further checks of any kind); some(false)\mathrm{some}(\mathrm{false})some(false) continues: false\mathrm{false}false if ∣stack∣>1000|\mathrm{stack}| > 1000∣stack∣>1000; false\mathrm{false}false if some element of stack\mathrm{stack}stack is longer than 520520520 bytes; false\mathrm{false}false if the bundle's parseScript of script\mathrm{script}script fails (it cannot, given the scan returned some(false)\mathrm{some}(\mathrm{false})some(false), but the branch is present); otherwise run tapRun\mathrm{tapRun}tapRun from the initial TapState\mathrm{TapState}TapState (main stack stack\mathrm{stack}stack, empty alt stack, empty condition stack, op count 000, weightLeft=weight\mathrm{weightLeft} = \mathrm{weight}weightLeft=weight, codeseparatorPos=0xFFFFFFFF\mathrm{codeseparatorPos} = \texttt{0xFFFFFFFF}codeseparatorPos=0xFFFFFFFF, opcodePos=0\mathrm{opcodePos} = 0opcodePos=0) over the parsed script: none gives false\mathrm{false}false; otherwise the result is "the final main stack has exactly one element, and that element is true" (non-empty with some non-zero byte, not a negative zero). No maximum script size is checked here.

witnessSerializedSize — for a list WWW of byte strings, the natural number ∣CompactSize(∣W∣)∥∥w∈WserBytes(w)∣|\mathrm{CompactSize}(|W|) \Vert \Vert_{w \in W} \mathrm{serBytes}(w)|∣CompactSize(∣W∣)∥∥w∈W​serBytes(w)∣, i.e. the length of the CompactSize count followed by each element with its own CompactSize length prefix.

hasAnnex — for a list WWW of byte strings, the Boolean "∣W∣≥2|W| \ge 2∣W∣≥2, and the last element of WWW is of the form b::_b :: \_b::_ (non-empty) with b=0x50b = \texttt{0x50}b=0x50 as a natural". An empty last element, or a list of fewer than two elements, gives false\mathrm{false}false.

taprootHandler — for a list spent\mathrm{spent}spent of outputs, the function (of type BitcoinVerify.TaprootHandler) taking a verification context ccc (fields: consensus flags 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; a transaction tx\mathrm{tx}tx; a natural nIn\mathrm{nIn}nIn; an integer amount\mathrm{amount}amount), a witness list WWW (last element on top) and a byte string program\mathrm{program}program, and returning a Boolean. If W=[ ]W = [\,]W=[]: false\mathrm{false}false. Otherwise: tc:=( (c.flags.cltv,c.flags.csv,c.flags.nulldummy), c.tx, spent, c.nIn )\mathrm{tc} := (\,(c.\mathrm{flags}.\mathrm{cltv}, c.\mathrm{flags}.\mathrm{csv}, c.\mathrm{flags}.\mathrm{nulldummy}),\ c.\mathrm{tx},\ \mathrm{spent},\ c.\mathrm{nIn}\,)tc:=((c.flags.cltv,c.flags.csv,c.flags.nulldummy), c.tx, spent, c.nIn); if hasAnnex(W)\mathrm{hasAnnex}(W)hasAnnex(W), the annex is the last element of WWW and stack:=W\mathrm{stack} := Wstack:=W without its last element, otherwise there is no annex and stack:=W\mathrm{stack} := Wstack:=W; e0:=(annex present, SHA256(serBytes(annex)) if present else [ ], [ ], 0xFFFFFFFF)e_0 := (\text{annex present},\ \mathrm{SHA256}(\mathrm{serBytes}(\mathrm{annex})) \text{ if present else } [\,],\ [\,],\ \texttt{0xFFFFFFFF})e0​:=(annex present, SHA256(serBytes(annex)) if present else [], [], 0xFFFFFFFF). If ∣stack∣=1|\mathrm{stack}| = 1∣stack∣=1 (key path): the result is checkSchnorrSignature(c.tx,spent,c.nIn,stack0,program,false,e0)\mathrm{checkSchnorrSignature}(c.\mathrm{tx}, \mathrm{spent}, c.\mathrm{nIn}, \mathrm{stack}_0, \mathrm{program}, \mathrm{false}, e_0)checkSchnorrSignature(c.tx,spent,c.nIn,stack0​,program,false,e0​), where stack0\mathrm{stack}_0stack0​ is the unique element. Otherwise (script path): false\mathrm{false}false if stack\mathrm{stack}stack is empty (unreachable given W≠[ ]W \neq [\,]W=[], since an annex is only removed when ∣W∣≥2|W| \ge 2∣W∣≥2); control:=\mathrm{control} :=control:= the last element, removed; false\mathrm{false}false if nothing remains (likewise unreachable, as ∣stack∣≥2|\mathrm{stack}| \ge 2∣stack∣≥2 here); script:=\mathrm{script} :=script:= the new last element, removed; false\mathrm{false}false if ∣control∣<33|\mathrm{control}| < 33∣control∣<33 or ∣control∣>4129|\mathrm{control}| > 4129∣control∣>4129 or (∣control∣−33) mod 32≠0(|\mathrm{control}| - 33) \bmod 32 \neq 0(∣control∣−33)mod32=0; v:=control0 & 0xfev := \mathrm{control}_0 \,\&\, \texttt{0xfe}v:=control0​&0xfe; ℓ:=tapleafHash(⟨v⟩8,script)\ell := \mathrm{tapleafHash}(\langle v \rangle_8, \mathrm{script})ℓ:=tapleafHash(⟨v⟩8​,script); false\mathrm{false}false if verifyTaprootCommitment(control,program,ℓ)\mathrm{verifyTaprootCommitment}(\mathrm{control}, \mathrm{program}, \ell)verifyTaprootCommitment(control,program,ℓ) is false\mathrm{false}false; if v=0xc0v = \texttt{0xc0}v=0xc0, the result is executeTapscript(tc, e0 with tapleafHash:=ℓ, reverse(stack), script, witnessSerializedSize(W)+50)\mathrm{executeTapscript}(\mathrm{tc},\ e_0 \text{ with } \mathrm{tapleafHash} := \ell,\ \mathrm{reverse}(\mathrm{stack}),\ \mathrm{script},\ \mathrm{witnessSerializedSize}(W) + 50)executeTapscript(tc, e0​ with tapleafHash:=ℓ, reverse(stack), script, witnessSerializedSize(W)+50) (the size is that of the whole original witness WWW, annex included, coerced to an integer); if v≠0xc0v \neq \texttt{0xc0}v=0xc0, the result is true\mathrm{true}true. The fields c.flags.taprootc.\mathrm{flags}.\mathrm{taproot}c.flags.taproot, c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness, c.flags.p2shc.\mathrm{flags}.\mathrm{p2sh}c.flags.p2sh, c.flags.dersigc.\mathrm{flags}.\mathrm{dersig}c.flags.dersig and c.amountc.\mathrm{amount}c.amount are not consulted; the length of program\mathrm{program}program is not checked here (a non-32-byte program can only fail inside the tweak check or the signature check).

verifyScriptFull — for a list spent\mathrm{spent}spent, a context ccc, byte strings scriptSig\mathrm{scriptSig}scriptSig, scriptPubKey\mathrm{scriptPubKey}scriptPubKey and a witness list WWW: the Boolean BitcoinVerify.verifyScript with the Taproot handler taprootHandler(spent)\mathrm{taprootHandler}(\mathrm{spent})taprootHandler(spent) plugged in. Unfolded from the imported file, that is: evaluate scriptSig\mathrm{scriptSig}scriptSig with the legacy interpreter from an empty stack (failing — false\mathrm{false}false — if longer than 10,00010{,}00010,000 bytes, unparsable, or if execution fails), then scriptPubKey\mathrm{scriptPubKey}scriptPubKey from the resulting stack; false\mathrm{false}false if the resulting top is not true; if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness and scriptPubKey\mathrm{scriptPubKey}scriptPubKey is a witness program (length 444–424242, first byte 000 or 0x51\texttt{0x51}0x51–0x60\texttt{0x60}0x60, second byte equal to length −2-2−2), then false\mathrm{false}false if scriptSig≠[ ]\mathrm{scriptSig} \neq [\,]scriptSig=[], else the verdict of the witness-program verifier — which for version 111, a 323232-byte program and not-P2SH returns true\mathrm{true}true if c.flags.taprootc.\mathrm{flags}.\mathrm{taproot}c.flags.taproot is off and otherwise taprootHandler(spent)(c,W,program)\mathrm{taprootHandler}(\mathrm{spent})(c, W, \mathrm{program})taprootHandler(spent)(c,W,program), and otherwise handles version 000 (P2WSH/P2WPKH) or returns true\mathrm{true}true for other versions; otherwise, if c.flags.p2shc.\mathrm{flags}.\mathrm{p2sh}c.flags.p2sh and scriptPubKey\mathrm{scriptPubKey}scriptPubKey is OP_HASH160 <20 bytes> OP_EQUAL, the P2SH path (push-only scriptSig, redeem script evaluation, nested witness program with the same version dispatch and isP2sh=true\mathrm{isP2sh} = \mathrm{true}isP2sh=true, in which case version 111 is not routed to the Taproot handler but accepted as true\mathrm{true}true, and a non-empty witness without a witness program is false\mathrm{false}false); otherwise false\mathrm{false}false if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness and W≠[ ]W \neq [\,]W=[], else true\mathrm{true}true.

p2trBytes — for a byte string qqq, the byte string [0x51]∥push(q)[\texttt{0x51}] \Vert \mathrm{push}(q)[0x51]∥push(q), where push(q)\mathrm{push}(q)push(q) is the bundle's canonical push encoding of qqq (witnessBytes 1 q); for a 323232-byte qqq this is [0x51,0x20]∥q[\texttt{0x51}, \texttt{0x20}] \Vert q[0x51,0x20]∥q. No length constraint on qqq is imposed.

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