Taproot and Tapscript: the version-1 witness branch, BIP341 signature hash, commitment check, and the Tapscript interpreter rules
DefinitionBitcoinTaprootConstants. TAPROOT_LEAF_MASK = 0xfe, TAPROOT_LEAF_TAPSCRIPT = 0xc0, control-block sizes 33 + 32·k for , 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 . 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: , , is the 32-byte key q and the parity of 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 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 , 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.
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
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 ); a byte string is a finite list of bytes, written with for concatenation, for length, for the -th byte read as a natural number (the "default" value is used wherever the file reads a position that does not exist), for "drop bytes then take up to bytes". is the big-endian natural value of a byte string of any length. and are the 4- and 8-byte little-endian encodings of and . is if , if , if , and otherwise. . , , , and are the bundle's own implementations on byte lists. A transaction has a natural , a list of inputs (each: an outpoint consisting of a byte-string and a natural index ; a scriptSig byte string; a natural ; a witness list of byte strings), a list of outputs (each: an integer and a byte-string ), and a natural . and (two's complement for negative ). The secp256k1 constants are , the group order , and the base point ; points are either the point at infinity ("none") or affine pairs of naturals, added with the bundle's affine formulas and multiplied by scalars with its 257-step double-and-add (so is the point at infinity). "None" is the failure value of an optional result; Boolean results are .
TAPROOT_LEAF_MASK — the natural number .
TAPROOT_LEAF_TAPSCRIPT — the natural number .
TAPROOT_CONTROL_BASE_SIZE — the natural number .
TAPROOT_CONTROL_NODE_SIZE — the natural number .
TAPROOT_CONTROL_MAX_NODE_COUNT — the natural number .
TAPROOT_CONTROL_MAX_SIZE — the natural number .
ANNEX_TAG — the natural number .
VALIDATION_WEIGHT_OFFSET — the integer .
VALIDATION_WEIGHT_PER_SIGOP_PASSED — the integer .
SIGHASH_DEFAULT — the natural number .
OP_CHECKSIGADD — the byte .
tagged — for a string and a byte string , where is the UTF-8 byte encoding of (the bundle's taggedHash applied to ascii tag).
tapleafHash — for a byte (the leaf version) and a byte string , . No bound on is imposed; an empty script gives as the message.
lexLt — a Boolean strict lexicographic order on byte strings, defined by recursion: ; ; ; is if (as naturals), if , and if . Thus a proper prefix is less than its extension, and equal strings are not less.
tapbranchHash — for byte strings : if , and otherwise (including when , where both concatenations coincide). No length requirement on or .
controlNodes — for a byte string , the list of its "path nodes": let , where is natural-number subtraction (so whenever , and also ignores any trailing fewer-than-32 bytes), and let be with its first bytes dropped (all of it dropped if shorter). The result is the list of chunks , produced by an inner recursion that, with counter and remaining string , emits "take of " and recurses on "drop of " with counter , and emits nothing at counter . Because is the floor, every emitted chunk has exactly bytes.
taprootMerkleRoot — for byte strings and , the left fold of over starting at : , for the nodes in order, result . With no nodes it is itself.
tapTweakHash — for byte strings and (of any lengths), .
be32 — for a natural , the -byte big-endian encoding of (the reverse of the -byte little-endian encoding, which truncates modulo ).
xonlyTweakAddCheck — for a byte string , a Boolean , an affine point given as a pair of naturals (no on-curve check is made here), and a byte string : let ; if the result is ; otherwise compute ; if is the point at infinity the result is ; otherwise, with , the result is iff (so must have exactly bytes) and the proposition "" has the same truth value as . When , is the point at infinity and .
checkTapTweak — for byte strings , , and a Boolean : let (no length check on ); if , or if is not a quadratic residue modulo (tested by and ), the result is ; otherwise let be the point with abscissa and even ordinate ( if is even, otherwise) and return .
verifyTaprootCommitment — for byte strings , , : where is "drop one byte, take up to " (shorter if is short, empty if ) and is the Boolean "" with when is empty. No length constraint on or is checked in this function itself.
ExecData — a record with four fields: (Boolean), (byte string), (byte string), (natural number). No invariant ties the fields together (e.g. may be non-empty while is false).
sigHashSchnorr — a function of a transaction , a list of outputs, naturals and , a Boolean and an , returning an optional byte string. If , i.e. (in particular is excluded), the result is none. Otherwise: if , else ; ; if else ; ; the input , or, when , the default input with outpoint (empty hash, index ), empty scriptSig, sequence , empty witness. If : when the whole result is none, otherwise (the default written in the code is unreachable here because of the length test); if , . The result is then of
where if and otherwise (the list is hashed in full, whatever its length relative to ); if and otherwise (so for nothing); if , and otherwise; if and otherwise. The default value serializes as .
checkSchnorrSignature — a Boolean function of a transaction , a list , a natural , byte strings and , a Boolean and an . If and : . Otherwise the last byte of (as a natural) if , else ; without its last byte if , else . If and : . Otherwise evaluate : if none, ; if , the result is , the bundle's BIP340 verifier: unless and ; with , , if or ; if does not lift (as in checkTapTweak) to a point with even ordinate; else with and , if is the point at infinity, else iff is even and . This function itself imposes no length condition on .
isOpSuccess — for a natural , the Boolean " or or or or or or or ".
opSuccessScan — a function of a fuel and a byte string returning an optional Boolean, by recursion: if , (whatever ); else if , none; else read one instruction from with the bundle's getOp (first byte : if it is a push — of bytes when , or of a length given by the next 1, 2 or 4 little-endian bytes for — and the read fails if the length bytes or the data are missing; if it is the opcode with no data); if the read fails, none; if it is a push, recurse on the remainder with fuel ; if it is an opcode with , ; otherwise recurse on the remainder with fuel .
TapCtx — a record with fields (the Script-layer flag record: Booleans , , ), (a transaction), (a list of outputs), (a natural).
tapOracle — for a , the Script-layer oracle record whose hash fields are the bundle's , , , , ; whose field is the constant function returning none for every (signature, key) pair (a script failure if ever consulted); whose is the bundle's checkLockTime for , (an integer lock time is accepted iff and are on the same side of , , and the sequence of input — default input if out of range — is not ); and whose is the bundle's checkSequence for , (rejects if or the input's sequence has bit set; otherwise compares the masked (bits – and ) values, requiring same type flag and , where the script operand is converted to a natural by truncating negatives to ).
TapState — a record with fields (the Script-layer interpreter state: main , , condition stack — all lists with the top first — and a natural ), (an integer), (a natural) and (a natural).
evalChecksigTapscript — for a , an , byte strings and , and an integer , an optional pair (Boolean, integer): ; if else (integer arithmetic, may be negative); if and : none; else if : none; else if : none if and is , otherwise ; else (any other non-zero key length) with no verification. With an empty signature, no verification is performed for any key length, and the weight is unchanged.
tapExecOp — for a , an , a Boolean , an opcode byte and a with state , an optional ; let be with . Cases in order. (1) (OP_IF, OP_NOTIF): if , then none if the main stack is empty, none if its top has or ( and ), and otherwise the legacy execOp result (pop , push " is true" — any non-zero byte except a lone final — negated for OP_NOTIF, onto ) placed into ; if not , the legacy result (push onto ) placed into . (2) (OP_CHECKSIG, OP_CHECKSIGVERIFY), regardless of : none unless the stack is ; then : none gives none; gives, for OP_CHECKSIGVERIFY, with stack and weight if , else none; for OP_CHECKSIG, with stack ( or ) and weight . (3) (OP_CHECKSIGADD), regardless of : none unless the stack is ; none if ; otherwise is the script-number value of (little-endian magnitude with sign bit in the last byte, no minimality requirement, empty is ); then : none gives none, else with stack (minimal script-number encoding) and weight . (4) (OP_CHECKMULTISIG(VERIFY)): none, regardless of everything else. (5) (OP_CODESEPARATOR), regardless of : with and nothing else changed. (6) Any other byte: the legacy execOp with flags , oracle , , and , placed into (none when it fails; it fails for unknown opcodes, OP_RETURN, OP_VERIF/OP_VERNOTIF, etc., and treats – as number pushes). Only is touched in case (6); , , are preserved there.
tapStep — for , , a and one parsed instruction, an optional . For a push of data : none if ; otherwise with pushed on the main stack if all entries of are (vacuously so when empty), else ; none if ; else with and incremented by . For an opcode byte : all entries of are ; none if is one of the fifteen disabled opcodes (–, –, , , –); otherwise if or (this range includes , ), and otherwise; if is none, none; else, for , none if , else with incremented by . No operation count is kept.
tapRun — for , , a and a parsed script (list of instructions), an optional : on the empty script, if is empty and none otherwise; on , apply to , propagate none, and continue on from the new state.
executeTapscript — a Boolean function of a , an , a list of byte strings (top first), a byte string and an integer . Evaluate : none gives ; gives at once (no further checks of any kind); continues: if ; if some element of is longer than bytes; if the bundle's parseScript of fails (it cannot, given the scan returned , but the branch is present); otherwise run from the initial (main stack , empty alt stack, empty condition stack, op count , , , ) over the parsed script: none gives ; 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 of byte strings, the natural number , i.e. the length of the CompactSize count followed by each element with its own CompactSize length prefix.
hasAnnex — for a list of byte strings, the Boolean ", and the last element of is of the form (non-empty) with as a natural". An empty last element, or a list of fewer than two elements, gives .
taprootHandler — for a list of outputs, the function (of type BitcoinVerify.TaprootHandler) taking a verification context (fields: consensus flags ; a transaction ; a natural ; an integer ), a witness list (last element on top) and a byte string , and returning a Boolean. If : . Otherwise: ; if , the annex is the last element of and without its last element, otherwise there is no annex and ; . If (key path): the result is , where is the unique element. Otherwise (script path): if is empty (unreachable given , since an annex is only removed when ); the last element, removed; if nothing remains (likewise unreachable, as here); the new last element, removed; if or or ; ; ; if is ; if , the result is (the size is that of the whole original witness , annex included, coerced to an integer); if , the result is . The fields , , , and are not consulted; the length of is not checked here (a non-32-byte program can only fail inside the tweak check or the signature check).
verifyScriptFull — for a list , a context , byte strings , and a witness list : the Boolean BitcoinVerify.verifyScript with the Taproot handler plugged in. Unfolded from the imported file, that is: evaluate with the legacy interpreter from an empty stack (failing — — if longer than bytes, unparsable, or if execution fails), then from the resulting stack; if the resulting top is not true; if and is a witness program (length –, first byte or –, second byte equal to length ), then if , else the verdict of the witness-program verifier — which for version , a -byte program and not-P2SH returns if is off and otherwise , and otherwise handles version (P2WSH/P2WPKH) or returns for other versions; otherwise, if and 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 , in which case version is not routed to the Taproot handler but accepted as , and a non-empty witness without a witness program is ); otherwise if and , else .
p2trBytes — for a byte string , the byte string , where is the bundle's canonical push encoding of (witnessBytes 1 q); for a -byte this is . No length constraint on is imposed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.