The legacy script interpreter with the signature script code tracked exactly (closing limits L1 and L10)
DefinitionBitcoinScriptV2A second interpreter over the script mission's BitcoinScript, whose only difference is that the signature checks see the script code exactly as Core computes it.
OracleV2 — like the script mission's Oracle, but checkSig : (scriptCode : Bytes) → (sig pk : Bytes) → Option Bool receives the script code. fadSig v sc sig — in SigVersion::BASE, FindAndDelete of the push of sig from sc; the identity in witness v0. fadAll v sc sigs — the fold of fadSig over a list of signatures. withCode o sc, withCodeSig o v sc — the published Oracle obtained by fixing the script code (and, for withCodeSig, deleting the checked signature as the published model does). multisigSigs stack — the signatures an OP_CHECKMULTISIG will consume, read off the stack layout.
StateV2 — the published State plus scriptCode : Bytes, Core's CScript(pbegincodehash, pend). oracleAt v o s i — the oracle for instruction : OP_CHECKSIG(VERIFY) see fadSig of the one signature, OP_CHECKMULTISIG(VERIFY) see fadAll of all their signatures (deleted before any check, as Core does), every other instruction sees the code unchanged. stepV2 — the published step with oracleAt, and an executed OP_CODESEPARATOR resets scriptCode to the bytes after the opcode. annotate s — the GetOp parse of a byte script paired with the byte suffix after each instruction; runV2, evalScriptV2, legacyOracleV2, evalBytesV2, executeWitnessScriptV0V2, verifyWitnessProgramV2, verifyScriptV2 — the verification mission's pipeline over the new evaluator (the Taproot handler unchanged).
Side conditions. NoCodeSep s, NoMultisig s (no such instruction in the parsed script); StepOk v s i (the instruction is not an executed code separator, and a multisig's signatures do not occur as pushes in the current script code), RunOk, EvalOk c v stack script (along the actual run).
Formalization Note. The published interpreter (BitcoinScript, BitcoinSig.legacyOracle, BitcoinVerify.verifyScript) is exact except for two documented limits: L1 (the script code does not restart after an executed OP_CODESEPARATOR) and L10 (OP_CHECKMULTISIG deletes only the checked signature). This file is the interpreter without those limits; the theorems state that it agrees with the published one wherever the limits do not bite, and its tests agree with every one of Core's 994 script and transaction vectors at the pinned revision. Only Std is imported.
import Std
import Definitions.Def_BitcoinVerify
namespace BitcoinScriptV2
/-! The legacy (`SigVersion::BASE`) and witness-v0 script interpreter of Bitcoin Core at revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`, revised to close the two documented limits of
`BitcoinScript`/`BitcoinVerify` (`REVIEW.md` L1 and L10):
* **L1** (`EvalScript`, interpreter.cpp:432, 1058–1066): the script code handed to the signature
checker is `CScript(pbegincodehash, pend)`, the bytes of the executed script from the position
just after the last *executed* `OP_CODESEPARATOR` (initially the whole script). The published
model always uses the whole script.
* **L10** (`OP_CHECKMULTISIG`, interpreter.cpp:1149–1159): in `SigVersion::BASE` the pushes of
*all* `nSigsCount` signatures are `FindAndDelete`d from that script code, in stack order from the
top, before any signature is checked; the published oracle deletes only the signature it checks.
Design. The interpreter runs over the parsed script paired with byte offsets: `annotate` is the
`GetOp` parse that pairs every instruction with the bytes that follow it (Core's `pc` after reading
it, i.e. `CScript(pc, pend)`). The state `StateV2` carries the published `State` together with
`scriptCode = CScript(pbegincodehash, pend)`. The oracle `OracleV2` receives the script code with the
`FindAndDelete`s already applied: `checkSig scriptCode sig pk` is the two encoding checks followed by
`checker.CheckECDSASignature(sig, pk, scriptCode, sigversion)`; the interpreter itself performs
Core's `FindAndDelete`s (one signature for `OP_CHECKSIG(VERIFY)`, every signature for
`OP_CHECKMULTISIG(VERIFY)`, `SigVersion::BASE` only). Every opcode is executed by the published
`BitcoinScript.execOp` through `BitcoinScript.step`, given a `BitcoinScript.Oracle` whose `checkSig`
is the V2 oracle applied to the right script code (`oracleAt`); only the bookkeeping of
`pbegincodehash` is new. -/
open BitcoinScript (Byte Bytes Instr Script Flags Oracle State allTrue toNum nDefaultMaxNumSize
OP_CODESEPARATOR OP_CHECKSIG OP_CHECKSIGVERIFY OP_CHECKMULTISIG OP_CHECKMULTISIGVERIFY)
open BitcoinSig (SigVersion SigFlags getOp pushBytes findAndDelete)
open BitcoinSer (Tx)
/-! ### The oracle -/
/-- The primitives the V2 interpreter calls out to. `checkSig scriptCode sig pk` is
`EvalChecksigPreTapscript` *after* its `FindAndDelete` (interpreter.cpp:345–349), equally the body
of the `OP_CHECKMULTISIG` loop (interpreter.cpp:1170–1177): `none` when `CheckSignatureEncoding` or
`CheckPubKeyEncoding` fails the script, otherwise `some` of
`checker.CheckECDSASignature(sig, pk, scriptCode, sigversion)` on the given script code. -/
structure OracleV2 where
ripemd160 : Bytes → Bytes
sha1 : Bytes → Bytes
sha256 : Bytes → Bytes
hash160 : Bytes → Bytes
hash256 : Bytes → Bytes
checkSig : (scriptCode : Bytes) → (sig pk : Bytes) → Option Bool
checkLockTime : Int → Bool
checkSequence : Int → Bool
/-- The published oracle with the same hash and lock-time primitives and a `checkSig` that never
answers (it is replaced by `withCode`/`withCodeSig` before any signature opcode runs). -/
def toOracle (o : OracleV2) : Oracle :=
⟨o.ripemd160, o.sha1, o.sha256, o.hash160, o.hash256, fun _ _ => none, o.checkLockTime, o.checkSequence⟩
/-- `FindAndDelete(scriptCode, CScript() << sig)` for `SigVersion::BASE`; witness v0 scripts are not
modified (interpreter.cpp:338–343, 1151–1159). -/
def fadSig (v : SigVersion) (sc sig : Bytes) : Bytes :=
match v with
| .base => (findAndDelete sc (pushBytes sig)).1
| .witnessV0 => sc
/-- The `for (int k = 0; k < nSigsCount; k++)` loop of `OP_CHECKMULTISIG` (interpreter.cpp:1152–1159):
every signature's push deleted in turn, from the top of the stack down. -/
def fadAll (v : SigVersion) (sc : Bytes) (sigs : List Bytes) : Bytes := sigs.foldl (fadSig v) sc
/-- The published oracle checking against one fixed script code (the `OP_CHECKMULTISIG` loop, whose
`scriptCode` is computed once before the loop). -/
def withCode (o : OracleV2) (sc : Bytes) : Oracle := { toOracle o with checkSig := o.checkSig sc }
/-- The published oracle for `OP_CHECKSIG(VERIFY)`: `EvalChecksigPreTapscript` on the script code
`sc = CScript(pbegincodehash, pend)`, which deletes the push of the signature being checked first. -/
def withCodeSig (o : OracleV2) (v : SigVersion) (sc : Bytes) : Oracle :=
{ toOracle o with checkSig := fun sig pk => o.checkSig (fadSig v sc sig) sig pk }
/-! ### The signatures of an `OP_CHECKMULTISIG` -/
/-- The `nSigsCount` signatures `stacktop(-isig-k)`, `k = 0 … nSigsCount-1`, of an
`OP_CHECKMULTISIG` executed on this (top-first) stack: the elements below the key count, the keys
and the signature count. (When the counts are out of range or the stack too short, `execOp` fails
before consulting the oracle and this value is irrelevant.) -/
def multisigSigs (stack : List Bytes) : List Bytes :=
match stack with
| [] => []
| nk :: rest =>
match toNum false nDefaultMaxNumSize nk with
| none => []
| some nKeys =>
match rest.drop nKeys.toNat with
| [] => []
| ns :: rest =>
match toNum false nDefaultMaxNumSize ns with
| none => []
| some nSigs => rest.take nSigs.toNat
/-! ### Execution state and steps -/
/-- The published state together with `scriptCode = CScript(pbegincodehash, pend)`. -/
structure StateV2 where
st : State
scriptCode : Bytes
/-- The published oracle the instruction `i` is executed with: at `OP_CHECKMULTISIG(VERIFY)` the
checker on the script code with every signature deleted (interpreter.cpp:1149–1177); at every other
instruction `withCodeSig`, which is `EvalChecksigPreTapscript` for `OP_CHECKSIG(VERIFY)`
(interpreter.cpp:1080, 331–349) and is not consulted by any other opcode. -/
def oracleAt (v : SigVersion) (o : OracleV2) (s : StateV2) : Instr → Oracle
| .op c =>
if c == OP_CHECKMULTISIG || c == OP_CHECKMULTISIGVERIFY then
withCode o (fadAll v s.scriptCode (multisigSigs s.st.stack))
else withCodeSig o v s.scriptCode
| .push _ => withCodeSig o v s.scriptCode
/-- One iteration of the `for (; pc < pend; …)` loop of `EvalScript` on the instruction `i` followed
by the bytes `r` (`pc` after `GetOp`): the published `step` with the oracle `oracleAt`, and
`pbegincodehash = pc` when an `OP_CODESEPARATOR` is executed (interpreter.cpp:1058–1066; the opcode
is executed iff `fExec`, since it lies outside `OP_IF … OP_ENDIF`). -/
def stepV2 (f : Flags) (v : SigVersion) (o : OracleV2) (s : StateV2) : Instr × Bytes → Option StateV2
| (i, r) =>
(BitcoinScript.step f (oracleAt v o s i) s.st i).map fun st =>
⟨st, if i = .op OP_CODESEPARATOR ∧ allTrue s.st.vfExec then r else s.scriptCode⟩
/-- The loop over the annotated instructions, followed by the unbalanced-conditional check. -/
def runV2 (f : Flags) (v : SigVersion) (o : OracleV2) : StateV2 → List (Instr × Bytes) → Option StateV2
| s, [] => if s.st.vfExec.isEmpty then some s else none
| s, x :: rest =>
match stepV2 f v o s x with
| none => none
| some s' => runV2 f v o s' rest
/-! ### Byte-level scripts with positions -/
/-- The `GetOp` parse pairing every instruction with the bytes after it: for `annotate script =
some l`, `(i, r) ∈ l` means `script = pre ++ bytes-of-i ++ r`, so `r` is `CScript(pc, pend)` once
`i` has been read. `none` on a malformed push, as `BitcoinSig.parseScript`. -/
def annotateAux : Nat → Bytes → Option (List (Instr × Bytes))
| _, [] => some []
| 0, _ => none
| fuel + 1, s =>
match getOp s with
| none => none
| some (i, r) =>
match annotateAux fuel r with
| none => none
| some l => some ((i, r) :: l)
def annotate (s : Bytes) : Option (List (Instr × Bytes)) := annotateAux s.length s
/-- `EvalScript(stack, script, flags, checker, sigversion)` for `BASE`/`WITNESS_V0` on a byte script
(without the `MAX_SCRIPT_SIZE` test): the resulting main stack. `pbegincodehash` starts at
`script.begin()`. -/
def evalScriptV2 (f : Flags) (v : SigVersion) (o : OracleV2) (stack : List Bytes) (script : Bytes) :
Option (List Bytes) :=
match annotate script with
| none => none
| some l => (runV2 f v o ⟨State.initial stack, script⟩ l).map fun s => s.st.stack
/-! ### The concrete oracle and `VerifyScript` -/
/-- The concrete V2 oracle: Core's hashes, the encoding checks and
`GenericTransactionSignatureChecker::CheckECDSASignature` on the script code the interpreter
supplies, and the lock-time checks. -/
def legacyOracleV2 (f : SigFlags) (tx : Tx) (nIn : Nat) (amount : Int) (v : SigVersion) : OracleV2 where
ripemd160 := BitcoinSer.ripemd160
sha1 := BitcoinSer.sha1
sha256 := BitcoinSer.sha256
hash160 := BitcoinSer.hash160
hash256 := BitcoinSer.hash256
checkSig := fun scriptCode sig pk =>
if !BitcoinSig.checkSignatureEncoding f sig ∨ !BitcoinSig.checkPubKeyEncoding f v pk then none
else some (BitcoinSig.checkECDSASignature tx nIn amount v sig pk scriptCode)
checkLockTime := BitcoinSig.checkLockTime tx nIn
checkSequence := BitcoinSig.checkSequence tx nIn
open BitcoinVerify (Ctx MAX_SCRIPT_SIZE scriptFlagsOf sigFlagsOf topTrue isWitnessProgram
isPayToScriptHash isPushOnly isPayToAnchor p2wpkhExec TaprootHandler
WITNESS_V0_SCRIPTHASH_SIZE WITNESS_V0_KEYHASH_SIZE WITNESS_V1_TAPROOT_SIZE)
/-- `EvalScript` on a byte-level script with the concrete oracle: the `MAX_SCRIPT_SIZE` test, then
`evalScriptV2`. Mirrors `BitcoinVerify.evalBytes`. -/
def evalBytesV2 (c : Ctx) (v : SigVersion) (stack : List Bytes) (script : Bytes) : Option (List Bytes) :=
if MAX_SCRIPT_SIZE < script.length then none
else evalScriptV2 (scriptFlagsOf c.flags) v (legacyOracleV2 (sigFlagsOf c.flags) c.tx c.nIn c.amount v) stack script
/-- `ExecuteWitnessScript` for witness version 0 with the V2 evaluator. -/
def executeWitnessScriptV0V2 (c : Ctx) (stack : List Bytes) (exec : Bytes) : Bool :=
if stack.any (fun e => BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE < e.length) then false
else match evalBytesV2 c .witnessV0 stack exec with
| none => false
| some st => decide (st.length = 1) && topTrue st
/-- `VerifyWitnessProgram` with the V2 evaluator for version 0; the Taproot branch is unchanged. -/
def verifyWitnessProgramV2 (tap : TaprootHandler) (c : Ctx) (witness : List Bytes) (version : Nat)
(program : Bytes) (isP2sh : Bool) : Bool :=
if version = 0 then
if program.length = WITNESS_V0_SCRIPTHASH_SIZE then
match witness.getLast? with
| none => false
| some script =>
if BitcoinSer.sha256 script ≠ program then false
else executeWitnessScriptV0V2 c witness.dropLast.reverse script
else if program.length = WITNESS_V0_KEYHASH_SIZE then
if witness.length ≠ 2 then false
else executeWitnessScriptV0V2 c witness.reverse (p2wpkhExec program)
else false
else if version = 1 ∧ program.length = WITNESS_V1_TAPROOT_SIZE ∧ !isP2sh then
if !c.flags.taproot then true else tap c witness program
else if !isP2sh && isPayToAnchor version program then true
else true
/-- `VerifyScript` with the V2 evaluator on the legacy and witness-v0 paths; mirrors
`BitcoinVerify.verifyScript` line by line. -/
def verifyScriptV2 (tap : TaprootHandler) (c : Ctx) (scriptSig scriptPubKey : Bytes) (witness : List Bytes) : Bool :=
match evalBytesV2 c .base [] scriptSig with
| none => false
| some stackSig =>
match evalBytesV2 c .base stackSig scriptPubKey with
| none => false
| some stack =>
if !topTrue stack then false
else
let native : Option Bool :=
if c.flags.witness then
match isWitnessProgram scriptPubKey with
| some (version, program) =>
if scriptSig ≠ [] then some false
else some (verifyWitnessProgramV2 tap c witness version program false)
| none => none
else none
match native with
| some false => false
| some true => true
| none =>
if c.flags.p2sh && isPayToScriptHash scriptPubKey then
if !isPushOnly scriptSig then false
else
match stackSig with
| [] => false
| redeem :: rest =>
match evalBytesV2 c .base rest redeem with
| none => false
| some stack2 =>
if !topTrue stack2 then false
else
if c.flags.witness then
match isWitnessProgram redeem with
| some (version, program) =>
if scriptSig ≠ BitcoinSig.pushBytes redeem then false
else verifyWitnessProgramV2 tap c witness version program true
| none => if c.flags.witness && !witness.isEmpty then false else true
else true
else if c.flags.witness && !witness.isEmpty then false
else true
/-! ### The side conditions of the agreement theorems -/
/-- The script contains no `OP_CODESEPARATOR` instruction. -/
def NoCodeSep (s : Script) : Prop := Instr.op OP_CODESEPARATOR ∉ s
/-- The script contains no `OP_CHECKMULTISIG(VERIFY)` instruction. -/
def NoMultisig (s : Script) : Prop := Instr.op OP_CHECKMULTISIG ∉ s ∧ Instr.op OP_CHECKMULTISIGVERIFY ∉ s
/-- The instruction `i`, executed from the state `s`, is outside the two limits: it is not an
executed `OP_CODESEPARATOR` (L1), and if it is an executed `OP_CHECKMULTISIG(VERIFY)` then no
signature's push occurs in the script code, so that every `FindAndDelete` is the identity (L10;
vacuous for witness v0, where there is no `FindAndDelete`). -/
def StepOk (v : SigVersion) (s : StateV2) : Instr → Prop
| .push _ => True
| .op c => allTrue s.st.vfExec = true →
c ≠ OP_CODESEPARATOR ∧
((c = OP_CHECKMULTISIG ∨ c = OP_CHECKMULTISIGVERIFY) →
∀ sig ∈ multisigSigs s.st.stack, fadSig v s.scriptCode sig = s.scriptCode)
/-- Every step of the V2 run from `s` over `l` (as far as it gets) satisfies `StepOk`. -/
def RunOk (f : Flags) (v : SigVersion) (o : OracleV2) : StateV2 → List (Instr × Bytes) → Prop
| _, [] => True
| s, x :: rest => StepOk v s x.1 ∧ ∀ s', stepV2 f v o s x = some s' → RunOk f v o s' rest
/-- The V2 evaluation of `script` from `stack` in the context `c` stays outside the two limits. -/
def EvalOk (c : Ctx) (v : SigVersion) (stack : List Bytes) (script : Bytes) : Prop :=
∀ l, annotate script = some l →
RunOk (scriptFlagsOf c.flags) v (legacyOracleV2 (sigFlagsOf c.flags) c.tx c.nIn c.amount v)
⟨State.initial stack, script⟩ l
end BitcoinScriptV2
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_BitcoinScriptV2 (namespace BitcoinScriptV2)
The file defines, in order, the following 24 declarations. Notation and the preamble definitions they rely on (, , , , the published //, the encoding and ECDSA checks, the verification helpers) are unfolded in the second part of this document.
1. OracleV2. A structure with eight components: five functions (named RIPEMD-160, SHA-1, SHA-256, HASH160, HASH256), a function from three byte strings (script code, signature, public key) to , and two predicates on . Nothing constrains these components.
2. toOracle. is the published oracle (whose signature check takes only ) with the five hash functions and two predicates of , and the signature check that returns on every input.
3. fadSig. For a signature version and byte strings : is the first component of ( with every occurrence of the canonical push of at instruction boundaries removed), and .
4. fadAll. is the left fold — deletion of each listed signature's push in list order; it is for the empty list.
5. withCode. is with its signature check replaced by (a fixed script code, independent of the signature).
6. withCodeSig. is with its signature check replaced by .
7. multisigSigs. For a stack (list of byte strings, top first): if is empty, . If : if fails (), ; otherwise with let (empty if is too short); if is empty, ; if : if fails, ; otherwise the result is with (all of if it is shorter). No range checks on .
8. StateV2. A structure with two components: a published interpreter state (main stack, alt stack, condition stack , operation counter) and a byte string (the script code).
9. oracleAt. for an instruction : if with () or (), it is ; for every other opcode and for every push it is .
10. stepV2. , for flags , version , V2 oracle , V2 state , instruction and byte string : run the published ; if it returns , so does ; if it returns , the result is with if () and every entry of (the condition stack before the step) is true, and otherwise.
11. runV2. : for empty, if is empty and otherwise; for , if , and if it is .
12. annotateAux. With a natural-number fuel and bytes : if (any fuel); if and ; otherwise if , and if , then if and if it is . Each instruction is paired with the bytes remaining after it.
13. annotate. . On success it lists with ; it is for . Since every successful consumes at least one byte, the fuel suffices, so it is exactly when some fails (malformed push).
14. evalScriptV2. : if ; otherwise, with , the main stack of the final state of , or if that run fails. Here has main stack , empty alt and condition stacks, counter ; the initial script code is all of . No size limit on is applied.
15. legacyOracleV2. For signature flags , transaction , input index , amount and version : the V2 oracle with Bitcoin Core's five hash functions, and of at input , and if the signature-encoding check or the key-encoding check fails, and otherwise, with used as given.
16. evalBytesV2. For a context (flags, transaction, input index, amount), version , stack and byte string : if ; otherwise , where of 's flags and .
17. executeWitnessScriptV0V2. For , a stack and a script : if some element of is longer than bytes; otherwise if , and if it is , true iff has exactly one element and .
18. verifyWitnessProgramV2. For a Taproot handler , context , witness , version number , program and boolean : if and : false if is empty; else with the last element of , false if , otherwise with = without its last element, reversed. If and : false if , else . If and is neither: false. If , and not : true if the taproot flag is off, else . In every other case (including pay-to-anchor): true.
19. verifyScriptV2. is the procedure described in Part 2 with , and : evaluate (version , empty stack), then on the result, require a true top; then the native witness-program branch, else the P2SH branch (push-only , evaluation of the redeem script on the rest of the stack, P2SH-wrapped witness programs), else the rule that a non-empty witness is rejected when the witness flag is on.
20. NoCodeSep. For a parsed script : the instruction does not occur in .
21. NoMultisig. For a parsed script : neither nor occurs in .
22. StepOk. : true for every push. For : if every entry of is true, then and, if , every in satisfies . Thus it holds for every opcode (including ) when some condition-stack entry is false; it fails for an executed ; the multisig clause is automatic for and when is empty; nothing is required of .
23. RunOk. : true for empty; for , and, for every with , . So is required at every instruction reached by the V2 run (including one whose step fails), and nothing after a failing step; the final condition-stack check is not involved.
24. EvalOk. : for every with , . At most one such exists; vacuous when ; no length bound on .
(The file also opens namespaces and abbreviations; these introduce no definitions.)
Part 2: unfolded preamble definitions (and the same definitions restated in unfolded form)
Basic objects and notation
- A byte is an 8-bit word, identified with its value in and written in hexadecimal (e.g. ). is the set of finite byte strings (lists of bytes); is the length, concatenation, the empty string.
- is the first entries of a list ; is what is left after removing the first entries, which is the empty list when .
- For a 0-based index , the statement "" means: and the entry of at index is . Indexing out of range yields no value, so such an equation can only hold with .
- A partial result is either or . Applying a function "under " () sends and .
- An instruction is either , carrying a data string , or , carrying an opcode byte . A script (parsed) is a finite list of instructions.
- Opcode bytes named below: , , , , , , , .
- A signature version is one of exactly two values: (legacy) or .
Reading one instruction from bytes:
returns either or with an instruction and the remaining bytes:
- : .
- Otherwise let be the first byte and the rest.
- If (a push opcode), a data length and a position are determined: if , and the data starts right after ; if , is the next byte ( if there is none); if , is the little-endian value of the next 2 bytes ( if fewer than 2 remain); if , is the little-endian value of the next 4 bytes ( if fewer than 4 remain). Then, if fewer than bytes remain, ; otherwise . (So gives .)
- If : .
On success the remainder is a suffix of that is at least one byte shorter than . never returns with .
The annotated parse:
, where, with a fuel counter :
- for every ;
- for ;
- for : if then ; if then, if the result is , and if it is the result is .
So on success , where is read from leaving , is read from leaving , and : each instruction is paired with the bytes that follow it in . . Since every successful consumes at least one byte, the fuel never runs out while input remains; hence exactly when fails at some instruction boundary, i.e. on a malformed push (a truncated length field, or fewer data bytes than announced).
The plain parse:
follows exactly the same recursion as (empty input gives ; fuel on non-empty input gives ; a failing gives ), but on success records only the instructions: .
Signature-push deletion: , , ,
- , the canonical push of : if it is the byte followed by ; else if it is , the byte , then ; else if it is , as 2 little-endian bytes, then ; otherwise , as 4 little-endian bytes, then . It is never empty ().
- returns a pair (resulting string, count); only the first component (written ) is used here. If the result is . Otherwise is scanned from the start: at the current instruction boundary, copies of are removed as long as the remaining string begins with (each removal counted); then one instruction is read with : if that fails, the whole remaining string is kept verbatim and the scan stops; if it succeeds, that instruction's bytes are kept and the scan continues right after it. The result is the concatenation of the kept bytes. (The recursion carries fuel , and when fuel is exhausted the remaining bytes are kept verbatim; every iteration of the scan consumes at least one byte.)
- :
- is the left fold of over the list, in list order:
and .
Script numbers and
-
(the call with "minimal encoding not required" and maximum size ): if ; otherwise with obtained by reading little-endian, the bit of the last byte being a sign bit: if it is set, is minus the little-endian value of with that bit cleared; else is the little-endian value of . . No minimality check is performed.
-
For an integer , (negative integers convert to the natural number ).
-
, for a stack listed top first, is a list of byte strings:
- empty: .
- : if , . If , let . If is empty, . If : if , ; if , the result is (all of if it has fewer than elements).
No range checks are made on , (e.g. , or negative counts, are accepted).
Oracles
- A published oracle consists of five functions (RIPEMD-160, SHA-1, SHA-256, HASH160, HASH256), a function , and two predicates .
- A V2 oracle has the same five hash functions and two predicates, but its signature check takes a script code as an extra first argument: . All components are arbitrary functions.
- : the published oracle with 's hashes and predicates and the signature check that always returns .
- : with signature check .
- : with signature check .
V2 states and
- A V2 state is a pair of a published interpreter state (a main stack and an alt stack of byte strings listed top first, a boolean condition stack , and an operation counter) and a byte string , the script code. Write and for the main stack and condition stack of .
- , the published oracle used for instruction from state :
- if with or : ;
- for every other , and for every : .
The published interpreter: , ,
- Flags are three booleans .
- A published state is a tuple (main stack, alt stack, , ): two stacks of byte strings listed top first, a list of booleans, and a natural number. . is true iff every entry of the boolean list is true (in particular is true).
- , one instruction from published state with published oracle :
- : if ; otherwise is with pushed on the main stack if , and otherwise; the result is if the two stacks of together hold more than elements, else . The oracle is not used.
- : let . If and , ; otherwise the counter is incremented when . Then: if is one of the fifteen disabled opcodes (–, –, , , –), (whether or not executing). Else if is true or , the result is followed by the same 1000-element check; else (a non-executed, non-conditional opcode) the state (with updated counter) is returned unchanged, subject to the 1000-element check.
- is the opcode switch (one case per opcode; any opcode not handled gives ). Its use of the oracle and the cases relevant here:
- the hash opcodes – replace the top element by the corresponding hash function of ; (when ) consults and (when ) ;
- () returns the state unchanged;
- /: the main stack must be (else ); is called; gives ; : for the stack becomes if , else ; for the stack becomes if and if not;
- /: the main stack must be ; must exist with ; ; the next elements are the keys (there must be that many); then an element with existing and ; the next elements are the signatures (there must be that many); then the matching loop below must not return ; then one more element (the dummy) must exist, and if it must be empty; the stack becomes the elements below the dummy, with or pushed for according to the loop's verdict, while for a false verdict gives ; becomes . Any failed requirement gives . The matching loop on signatures and keys (both top first): no signatures left gives ; signatures left but no keys gives ; otherwise is called, aborts with ; on success both advance, on failure only the key advances; whenever fewer keys than signatures remain the verdict is .
- applies to in turn, giving as soon as a step does; after the last instruction it returns if the final is empty and otherwise.
- : the final main stack, or .
The V2 interpreter: , ,
- , for a V2 state and a pair of an instruction and a byte string :
where if and (the condition stack before the step), and otherwise. So it fails exactly when the published step fails, and otherwise the published part is the published step's result.
- applies to in turn, giving as soon as a step does; after the last one it returns if the final is empty and otherwise.
- for a byte string : if the result is ; if it is , the result is the main stack of under (so if that run fails). The initial script code is the whole byte string .
Side conditions: ,
-
for a V2 state and instruction :
- : always true.
- : if is true, then both (a) , and (b) if or , then for every in the list , .
Consequences of the definition: when is false (inside a non-executed branch), holds for every instruction, including . When it is true, is false. For , is the identity, so clause (b) always holds. Clause (b) also holds when is empty. No condition is placed on /.
-
for a list of (instruction, bytes) pairs:
- empty: true.
- : holds, and for every V2 state with , holds.
Unwound: along the V2 run from over , holds at each instruction that is reached (the state before instruction being the result of the preceding successful steps), including the instruction whose step fails; once a step returns , nothing is required of the later instructions. The final empty- check of plays no role. depends on and only through which states the steps reach.
Static conditions: ,
For a parsed script (a list of instructions): means does not occur in ; means neither nor occurs in . (Occurrences anywhere count, including inside branches that would not be executed.)
Concrete oracles
- Signature flags , four booleans. (signature-encoding check): true if ; false if one of is set and is not strict DER plus a hash-type byte; false if is set and the signature does not have low ; false if is set and the hash type is undefined; true otherwise. (public-key encoding check): false if is set and is not a 33-byte compressed () or 65-byte uncompressed () key; false if is set, and is not compressed; true otherwise.
- (the transaction checker's ECDSA check, with a transaction, an input index, an amount): false if 's length does not match its header byte or ; otherwise the last byte of is the hash type, the signature hash of for input with script code is computed (legacy algorithm for , BIP143 algorithm with amount for ), the result is false if and , and otherwise it is the secp256k1 ECDSA verification of without its last byte against and that hash.
- is the V2 oracle with Bitcoin Core's RIPEMD-160, SHA-1, SHA-256, HASH160, HASH256, the lock-time and sequence checks of at input , and
and otherwise
The script code is used as given (no deletion inside the oracle).
- is the published oracle with the same hashes and lock-time/sequence checks and signature check : for , let if and if ; the result is if or , and otherwise.
Verification context and byte-level evaluators
- A context consists of consensus flags (seven booleans ), a transaction , an input index and an amount . From it: interpreter flags and signature flags ; write .
- : if ; otherwise .
- (published): if ; otherwise, if then , and if it is then — i.e. the signature check always uses the whole byte string as script code, with only the checked signature's push deleted (for ).
means: for every list with ,
Since is a function there is at most one such ; if (malformed push), holds vacuously. No bound on is involved (it is also required of scripts longer than bytes, on which returns without running).
Script verification: and
Both are the same procedure, parameterised by an evaluator : uses , uses (also inside the witness helpers). Auxiliary notions:
- : false for the empty stack; otherwise the boolean reading of the top element (true iff some byte is non-zero, except that a string whose only non-zero byte is a final is false).
- : , , , .
- : if or ; with , if and ; if then with version if and otherwise; else .
- : parses (via ) completely and every instruction is a push or an with .
- .
- A Taproot handler is an arbitrary function (context, list of byte strings, byte string) boolean.
- For a witness list : (undefined, i.e. , when ); is without its last element, reversed (so it is a top-first stack with on top); .
- (execute witness-v0 script): false if some element of is longer than bytes; otherwise false if , and if it is the result is: and .
- (verify witness program):
- , : false if is empty; else with : false if , else .
- , : false if , else .
- , other lengths: false.
- , , not : true if is off, else .
- every other case: true.
- :
- If : false. Else call the result .
- If : false. Else call it . If not : false.
- If and : the result is false if , and otherwise.
- Otherwise, if and : false if not ; false if is empty; else write (top first); false if or its result has not ; then, if : if , false if and otherwise; if it is , false if is non-empty and true otherwise. If is off: true.
- Otherwise: false if is on and is non-empty; true otherwise.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.