Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The legacy script interpreter with the signature script code tracked exactly (closing limits L1 and L10)

Definition
BitcoinScriptV2

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

bitcoinbitcoin-mainnetcheckmultisigcodeseparatorconsensusfindanddeleteformal-verificationinterpreterscriptsighash

A 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 iii: 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.

Definition code
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
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: EvalScript (pbegincodehash, OP_CODESEPARATOR at interpreter.cpp:1058-1066, OP_CHECKSIG's scriptCode and FindAndDelete at :339-343 / the CHECKSIG case, OP_CHECKMULTISIG's deletion of every signature at :1152-1159), SignatureHash (SigVersion::BASE), VerifyScript (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); Core's script_tests.json, tx_valid.json, tx_invalid.json at the same revision
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 (getOp\mathrm{getOp}getOp, findAndDelete\mathrm{findAndDelete}findAndDelete, pushBytes\mathrm{pushBytes}pushBytes, toNum\mathrm{toNum}toNum, the published step\mathrm{step}step/run\mathrm{run}run/evalScript\mathrm{evalScript}evalScript, 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 B∗→B∗\mathcal B^* \to \mathcal B^*B∗→B∗ (named RIPEMD-160, SHA-1, SHA-256, HASH160, HASH256), a function checkSig(sc,sig,pk)\mathrm{checkSig}(\mathit{sc}, \mathit{sig}, \mathit{pk})checkSig(sc,sig,pk) from three byte strings (script code, signature, public key) to {none,some(true),some(false)}\{\mathsf{none}, \mathsf{some}(\mathrm{true}), \mathsf{some}(\mathrm{false})\}{none,some(true),some(false)}, and two predicates checkLockTime,checkSequence\mathrm{checkLockTime}, \mathrm{checkSequence}checkLockTime,checkSequence on Z\mathbb ZZ. Nothing constrains these components.

2. toOracle. toOracle(o)\mathrm{toOracle}(o)toOracle(o) is the published oracle (whose signature check takes only (sig,pk)(\mathit{sig}, \mathit{pk})(sig,pk)) with the five hash functions and two predicates of ooo, and the signature check that returns none\mathsf{none}none on every input.

3. fadSig. For a signature version vvv and byte strings sc,sig\mathit{sc}, \mathit{sig}sc,sig: fadSig(base,sc,sig)\mathrm{fadSig}(\mathsf{base}, \mathit{sc}, \mathit{sig})fadSig(base,sc,sig) is the first component of findAndDelete(sc,pushBytes(sig))\mathrm{findAndDelete}(\mathit{sc}, \mathrm{pushBytes}(\mathit{sig}))findAndDelete(sc,pushBytes(sig)) (sc\mathit{sc}sc with every occurrence of the canonical push of sig\mathit{sig}sig at instruction boundaries removed), and fadSig(witnessV0,sc,sig)=sc\mathrm{fadSig}(\mathsf{witnessV0}, \mathit{sc}, \mathit{sig}) = \mathit{sc}fadSig(witnessV0,sc,sig)=sc.

4. fadAll. fadAll(v,sc,[σ1,…,σm])\mathrm{fadAll}(v, \mathit{sc}, [\sigma_1,\dots,\sigma_m])fadAll(v,sc,[σ1​,…,σm​]) is the left fold fadSig(v,⋯fadSig(v,fadSig(v,sc,σ1),σ2)⋯ ,σm)\mathrm{fadSig}(v, \cdots \mathrm{fadSig}(v, \mathrm{fadSig}(v, \mathit{sc}, \sigma_1), \sigma_2)\cdots, \sigma_m)fadSig(v,⋯fadSig(v,fadSig(v,sc,σ1​),σ2​)⋯,σm​) — deletion of each listed signature's push in list order; it is sc\mathit{sc}sc for the empty list.

5. withCode. withCode(o,sc)\mathrm{withCode}(o, \mathit{sc})withCode(o,sc) is toOracle(o)\mathrm{toOracle}(o)toOracle(o) with its signature check replaced by (sig,pk)↦o.checkSig(sc,sig,pk)(\mathit{sig}, \mathit{pk}) \mapsto o.\mathrm{checkSig}(\mathit{sc}, \mathit{sig}, \mathit{pk})(sig,pk)↦o.checkSig(sc,sig,pk) (a fixed script code, independent of the signature).

6. withCodeSig. withCodeSig(o,v,sc)\mathrm{withCodeSig}(o, v, \mathit{sc})withCodeSig(o,v,sc) is toOracle(o)\mathrm{toOracle}(o)toOracle(o) with its signature check replaced by (sig,pk)↦o.checkSig(fadSig(v,sc,sig),sig,pk)(\mathit{sig}, \mathit{pk}) \mapsto o.\mathrm{checkSig}(\mathrm{fadSig}(v, \mathit{sc}, \mathit{sig}), \mathit{sig}, \mathit{pk})(sig,pk)↦o.checkSig(fadSig(v,sc,sig),sig,pk).

7. multisigSigs. For a stack Σ\SigmaΣ (list of byte strings, top first): if Σ\SigmaΣ is empty, [ ][\,][]. If Σ=[nk]+ ⁣ ⁣+R\Sigma = [n_k] \mathbin{+\!\!+} RΣ=[nk​]++R: if toNum(nk)\mathrm{toNum}(n_k)toNum(nk​) fails (∣nk∣>4|n_k| > 4∣nk​∣>4), [ ][\,][]; otherwise with NK=toNum(nk)N_K = \mathrm{toNum}(n_k)NK​=toNum(nk​) let R′=dropmax⁡(NK,0)(R)R' = \mathrm{drop}_{\max(N_K,0)}(R)R′=dropmax(NK​,0)​(R) (empty if RRR is too short); if R′R'R′ is empty, [ ][\,][]; if R′=[ns]+ ⁣ ⁣+R′′R' = [n_s] \mathbin{+\!\!+} R''R′=[ns​]++R′′: if toNum(ns)\mathrm{toNum}(n_s)toNum(ns​) fails, [ ][\,][]; otherwise the result is takemax⁡(NS,0)(R′′)\mathrm{take}_{\max(N_S,0)}(R'')takemax(NS​,0)​(R′′) with NS=toNum(ns)N_S = \mathrm{toNum}(n_s)NS​=toNum(ns​) (all of R′′R''R′′ if it is shorter). No range checks on NK,NSN_K, N_SNK​,NS​.

8. StateV2. A structure with two components: a published interpreter state st\mathrm{st}st (main stack, alt stack, condition stack vfExec\mathrm{vfExec}vfExec, operation counter) and a byte string sc\mathrm{sc}sc (the script code).

9. oracleAt. oracleAt(v,o,S,i)\mathrm{oracleAt}(v, o, S, i)oracleAt(v,o,S,i) for an instruction iii: if i=op(c)i = \mathrm{op}(c)i=op(c) with c=0xaec = \texttt{0xae}c=0xae (OP_CHECKMULTISIG\texttt{OP\_CHECKMULTISIG}OP_CHECKMULTISIG) or c=0xafc = \texttt{0xaf}c=0xaf (OP_CHECKMULTISIGVERIFY\texttt{OP\_CHECKMULTISIGVERIFY}OP_CHECKMULTISIGVERIFY), it is withCode(o,fadAll(v,S.sc,multisigSigs(main stack of S.st)))\mathrm{withCode}\big(o, \mathrm{fadAll}(v, S.\mathrm{sc}, \mathrm{multisigSigs}(\text{main stack of } S.\mathrm{st}))\big)withCode(o,fadAll(v,S.sc,multisigSigs(main stack of S.st))); for every other opcode and for every push it is withCodeSig(o,v,S.sc)\mathrm{withCodeSig}(o, v, S.\mathrm{sc})withCodeSig(o,v,S.sc).

10. stepV2. stepV2(f,v,o,S,(i,r))\mathrm{stepV2}(f, v, o, S, (i, r))stepV2(f,v,o,S,(i,r)), for flags fff, version vvv, V2 oracle ooo, V2 state SSS, instruction iii and byte string rrr: run the published step(f,oracleAt(v,o,S,i),S.st,i)\mathrm{step}(f, \mathrm{oracleAt}(v,o,S,i), S.\mathrm{st}, i)step(f,oracleAt(v,o,S,i),S.st,i); if it returns none\mathsf{none}none, so does stepV2\mathrm{stepV2}stepV2; if it returns some(T)\mathsf{some}(T)some(T), the result is some(T,sc′)\mathsf{some}(T, \mathit{sc}')some(T,sc′) with sc′=r\mathit{sc}' = rsc′=r if i=op(0xab)i = \mathrm{op}(\texttt{0xab})i=op(0xab) (OP_CODESEPARATOR\texttt{OP\_CODESEPARATOR}OP_CODESEPARATOR) and every entry of S.st.vfExecS.\mathrm{st}.\mathrm{vfExec}S.st.vfExec (the condition stack before the step) is true, and sc′=S.sc\mathit{sc}' = S.\mathrm{sc}sc′=S.sc otherwise.

11. runV2. runV2(f,v,o,S,l)\mathrm{runV2}(f, v, o, S, l)runV2(f,v,o,S,l): for lll empty, some(S)\mathsf{some}(S)some(S) if S.st.vfExecS.\mathrm{st}.\mathrm{vfExec}S.st.vfExec is empty and none\mathsf{none}none otherwise; for l=[x]+ ⁣ ⁣+l′l = [x] \mathbin{+\!\!+} l'l=[x]++l′, none\mathsf{none}none if stepV2(f,v,o,S,x)=none\mathrm{stepV2}(f,v,o,S,x) = \mathsf{none}stepV2(f,v,o,S,x)=none, and runV2(f,v,o,S′,l′)\mathrm{runV2}(f, v, o, S', l')runV2(f,v,o,S′,l′) if it is some(S′)\mathsf{some}(S')some(S′).

12. annotateAux. With a natural-number fuel nnn and bytes xxx: some([ ])\mathsf{some}([\,])some([]) if x=εx = \varepsilonx=ε (any fuel); none\mathsf{none}none if n=0n = 0n=0 and x≠εx \ne \varepsilonx=ε; otherwise none\mathsf{none}none if getOp(x)=none\mathrm{getOp}(x) = \mathsf{none}getOp(x)=none, and if getOp(x)=some(i,r)\mathrm{getOp}(x) = \mathsf{some}(i, r)getOp(x)=some(i,r), then none\mathsf{none}none if annotateAux(n−1,r)=none\mathrm{annotateAux}(n-1, r) = \mathsf{none}annotateAux(n−1,r)=none and some([(i,r)]+ ⁣ ⁣+L)\mathsf{some}([(i, r)] \mathbin{+\!\!+} L)some([(i,r)]++L) if it is some(L)\mathsf{some}(L)some(L). Each instruction is paired with the bytes remaining after it.

13. annotate. annotate(s)=annotateAux(∣s∣,s)\mathrm{annotate}(s) = \mathrm{annotateAux}(|s|, s)annotate(s)=annotateAux(∣s∣,s). On success it lists (i1,r1),…,(in,rn)(i_1, r_1), \dots, (i_n, r_n)(i1​,r1​),…,(in​,rn​) with rn=εr_n = \varepsilonrn​=ε; it is some([ ])\mathsf{some}([\,])some([]) for s=εs = \varepsilons=ε. Since every successful getOp\mathrm{getOp}getOp consumes at least one byte, the fuel suffices, so it is none\mathsf{none}none exactly when some getOp\mathrm{getOp}getOp fails (malformed push).

14. evalScriptV2. evalScriptV2(f,v,o,Σ,script)\mathrm{evalScriptV2}(f, v, o, \Sigma, \mathit{script})evalScriptV2(f,v,o,Σ,script): none\mathsf{none}none if annotate(script)=none\mathrm{annotate}(\mathit{script}) = \mathsf{none}annotate(script)=none; otherwise, with annotate(script)=some(l)\mathrm{annotate}(\mathit{script}) = \mathsf{some}(l)annotate(script)=some(l), the main stack of the final state of runV2(f,v,o,(initial(Σ),script),l)\mathrm{runV2}(f, v, o, (\mathrm{initial}(\Sigma), \mathit{script}), l)runV2(f,v,o,(initial(Σ),script),l), or none\mathsf{none}none if that run fails. Here initial(Σ)\mathrm{initial}(\Sigma)initial(Σ) has main stack Σ\SigmaΣ, empty alt and condition stacks, counter 000; the initial script code is all of script\mathit{script}script. No size limit on script\mathit{script}script is applied.

15. legacyOracleV2. For signature flags ggg, transaction tx\mathit{tx}tx, input index ninn_{\mathrm{in}}nin​, amount a∈Za \in \mathbb Za∈Z and version vvv: the V2 oracle with Bitcoin Core's five hash functions, checkLockTime\mathrm{checkLockTime}checkLockTime and checkSequence\mathrm{checkSequence}checkSequence of tx\mathit{tx}tx at input ninn_{\mathrm{in}}nin​, and checkSig(sc,sig,pk)=none\mathrm{checkSig}(\mathit{sc}, \mathit{sig}, \mathit{pk}) = \mathsf{none}checkSig(sc,sig,pk)=none if the signature-encoding check SigEncg(sig)\mathrm{SigEnc}_g(\mathit{sig})SigEncg​(sig) or the key-encoding check PkEncg,v(pk)\mathrm{PkEnc}_{g,v}(\mathit{pk})PkEncg,v​(pk) fails, and some(ECDSA(tx,nin,a,v,sig,pk,sc))\mathsf{some}(\mathrm{ECDSA}(\mathit{tx}, n_{\mathrm{in}}, a, v, \mathit{sig}, \mathit{pk}, \mathit{sc}))some(ECDSA(tx,nin​,a,v,sig,pk,sc)) otherwise, with sc\mathit{sc}sc used as given.

16. evalBytesV2. For a context ccc (flags, transaction, input index, amount), version vvv, stack Σ\SigmaΣ and byte string script\mathit{script}script: none\mathsf{none}none if ∣script∣>10000|\mathit{script}| > 10000∣script∣>10000; otherwise evalScriptV2(fc,v,legacyOracleV2(gc,c.tx,c.nin,c.a,v),Σ,script)\mathrm{evalScriptV2}(f_c, v, \mathrm{legacyOracleV2}(g_c, c.\mathrm{tx}, c.n_{\mathrm{in}}, c.a, v), \Sigma, \mathit{script})evalScriptV2(fc​,v,legacyOracleV2(gc​,c.tx,c.nin​,c.a,v),Σ,script), where fc=(cltv,csv,nulldummy)f_c = (\mathrm{cltv}, \mathrm{csv}, \mathrm{nulldummy})fc​=(cltv,csv,nulldummy) of ccc's flags and gc=(dersig,false,false,false)g_c = (\mathrm{dersig}, \mathrm{false}, \mathrm{false}, \mathrm{false})gc​=(dersig,false,false,false).

17. executeWitnessScriptV0V2. For ccc, a stack Σ\SigmaΣ and a script ex\mathit{ex}ex: false\mathrm{false}false if some element of Σ\SigmaΣ is longer than 520520520 bytes; otherwise false\mathrm{false}false if evalBytesV2(c,witnessV0,Σ,ex)=none\mathrm{evalBytesV2}(c, \mathsf{witnessV0}, \Sigma, \mathit{ex}) = \mathsf{none}evalBytesV2(c,witnessV0,Σ,ex)=none, and if it is some(Σ′)\mathsf{some}(\Sigma')some(Σ′), true iff Σ′\Sigma'Σ′ has exactly one element and topTrue(Σ′)\mathrm{topTrue}(\Sigma')topTrue(Σ′).

18. verifyWitnessProgramV2. For a Taproot handler τ\tauτ, context ccc, witness www, version number ver\mathit{ver}ver, program ppp and boolean isP2sh\mathit{isP2sh}isP2sh: if ver=0\mathit{ver} = 0ver=0 and ∣p∣=32|p| = 32∣p∣=32: false if www is empty; else with ws\mathit{ws}ws the last element of www, false if SHA256(ws)≠p\mathrm{SHA256}(\mathit{ws}) \ne pSHA256(ws)=p, otherwise executeWitnessScriptV0V2(c,w↓,ws)\mathrm{executeWitnessScriptV0V2}(c, w^{\downarrow}, \mathit{ws})executeWitnessScriptV0V2(c,w↓,ws) with w↓w^{\downarrow}w↓ = www without its last element, reversed. If ver=0\mathit{ver} = 0ver=0 and ∣p∣=20|p| = 20∣p∣=20: false if ∣w∣≠2|w| \ne 2∣w∣=2, else executeWitnessScriptV0V2(c,rev(w),p2wpkhExec(p))\mathrm{executeWitnessScriptV0V2}(c, \mathrm{rev}(w), \mathrm{p2wpkhExec}(p))executeWitnessScriptV0V2(c,rev(w),p2wpkhExec(p)). If ver=0\mathit{ver} = 0ver=0 and ∣p∣|p|∣p∣ is neither: false. If ver=1\mathit{ver} = 1ver=1, ∣p∣=32|p| = 32∣p∣=32 and not isP2sh\mathit{isP2sh}isP2sh: true if the taproot flag is off, else τ(c,w,p)\tau(c, w, p)τ(c,w,p). In every other case (including pay-to-anchor): true.

19. verifyScriptV2. verifyScriptV2(τ,c,scriptSig,spk,w)\mathrm{verifyScriptV2}(\tau, c, \mathit{scriptSig}, \mathit{spk}, w)verifyScriptV2(τ,c,scriptSig,spk,w) is the procedure verifyE\mathrm{verify}_EverifyE​ described in Part 2 with E=evalBytesV2E = \mathrm{evalBytesV2}E=evalBytesV2, XE=executeWitnessScriptV0V2X_E = \mathrm{executeWitnessScriptV0V2}XE​=executeWitnessScriptV0V2 and WE=verifyWitnessProgramV2W_E = \mathrm{verifyWitnessProgramV2}WE​=verifyWitnessProgramV2: evaluate scriptSig\mathit{scriptSig}scriptSig (version base\mathsf{base}base, empty stack), then spk\mathit{spk}spk on the result, require a true top; then the native witness-program branch, else the P2SH branch (push-only scriptSig\mathit{scriptSig}scriptSig, 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 PPP: the instruction op(0xab)\mathrm{op}(\texttt{0xab})op(0xab) does not occur in PPP.

21. NoMultisig. For a parsed script PPP: neither op(0xae)\mathrm{op}(\texttt{0xae})op(0xae) nor op(0xaf)\mathrm{op}(\texttt{0xaf})op(0xaf) occurs in PPP.

22. StepOk. StepOk(v,S,i)\mathrm{StepOk}(v, S, i)StepOk(v,S,i): true for every push. For i=op(c)i = \mathrm{op}(c)i=op(c): if every entry of S.st.vfExecS.\mathrm{st}.\mathrm{vfExec}S.st.vfExec is true, then c≠0xabc \ne \texttt{0xab}c=0xab and, if c∈{0xae,0xaf}c \in \{\texttt{0xae}, \texttt{0xaf}\}c∈{0xae,0xaf}, every sig\mathit{sig}sig in multisigSigs(main stack of S)\mathrm{multisigSigs}(\text{main stack of } S)multisigSigs(main stack of S) satisfies fadSig(v,S.sc,sig)=S.sc\mathrm{fadSig}(v, S.\mathrm{sc}, \mathit{sig}) = S.\mathrm{sc}fadSig(v,S.sc,sig)=S.sc. Thus it holds for every opcode (including 0xab\texttt{0xab}0xab) when some condition-stack entry is false; it fails for an executed 0xab\texttt{0xab}0xab; the multisig clause is automatic for witnessV0\mathsf{witnessV0}witnessV0 and when multisigSigs\mathrm{multisigSigs}multisigSigs is empty; nothing is required of 0xac/0xad\texttt{0xac}/\texttt{0xad}0xac/0xad.

23. RunOk. RunOk(f,v,o,S,l)\mathrm{RunOk}(f, v, o, S, l)RunOk(f,v,o,S,l): true for lll empty; for l=[(i,r)]+ ⁣ ⁣+l′l = [(i, r)] \mathbin{+\!\!+} l'l=[(i,r)]++l′, StepOk(v,S,i)\mathrm{StepOk}(v, S, i)StepOk(v,S,i) and, for every S′S'S′ with stepV2(f,v,o,S,(i,r))=some(S′)\mathrm{stepV2}(f, v, o, S, (i,r)) = \mathsf{some}(S')stepV2(f,v,o,S,(i,r))=some(S′), RunOk(f,v,o,S′,l′)\mathrm{RunOk}(f, v, o, S', l')RunOk(f,v,o,S′,l′). So StepOk\mathrm{StepOk}StepOk 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. EvalOk(c,v,Σ,script)\mathrm{EvalOk}(c, v, \Sigma, \mathit{script})EvalOk(c,v,Σ,script): for every lll with annotate(script)=some(l)\mathrm{annotate}(\mathit{script}) = \mathsf{some}(l)annotate(script)=some(l), RunOk(fc,v,legacyOracleV2(gc,c.tx,c.nin,c.a,v),(initial(Σ),script),l)\mathrm{RunOk}(f_c, v, \mathrm{legacyOracleV2}(g_c, c.\mathrm{tx}, c.n_{\mathrm{in}}, c.a, v), (\mathrm{initial}(\Sigma), \mathit{script}), l)RunOk(fc​,v,legacyOracleV2(gc​,c.tx,c.nin​,c.a,v),(initial(Σ),script),l). At most one such lll exists; vacuous when annotate(script)=none\mathrm{annotate}(\mathit{script}) = \mathsf{none}annotate(script)=none; no length bound on script\mathit{script}script.

(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 {0,…,255}\{0,\dots,255\}{0,…,255} and written in hexadecimal (e.g. 0xab\texttt{0xab}0xab). B∗\mathcal B^*B∗ is the set of finite byte strings (lists of bytes); ∣x∣|x|∣x∣ is the length, x+ ⁣ ⁣+yx \mathbin{+\!\!+} yx++y concatenation, ε\varepsilonε the empty string.
  • takek(x)\mathrm{take}_k(x)takek​(x) is the first min⁡(k,∣x∣)\min(k,|x|)min(k,∣x∣) entries of a list xxx; dropk(x)\mathrm{drop}_k(x)dropk​(x) is what is left after removing the first kkk entries, which is the empty list when k≥∣x∣k \ge |x|k≥∣x∣.
  • For a 0-based index ppp, the statement "x[p]=cx[p] = cx[p]=c" means: p<∣x∣p < |x|p<∣x∣ and the entry of xxx at index ppp is ccc. Indexing out of range yields no value, so such an equation can only hold with p<∣x∣p<|x|p<∣x∣.
  • A partial result is either none\mathsf{none}none or some(y)\mathsf{some}(y)some(y). Applying a function ggg "under some\mathsf{some}some" (mapg\mathrm{map}_gmapg​) sends none↦none\mathsf{none}\mapsto\mathsf{none}none↦none and some(y)↦some(g(y))\mathsf{some}(y)\mapsto\mathsf{some}(g(y))some(y)↦some(g(y)).
  • An instruction is either push(d)\mathrm{push}(d)push(d), carrying a data string d∈B∗d\in\mathcal B^*d∈B∗, or op(c)\mathrm{op}(c)op(c), carrying an opcode byte ccc. A script (parsed) is a finite list of instructions.
  • Opcode bytes named below: OP_16=0x60\texttt{OP\_16}=\texttt{0x60}OP_16=0x60, OP_IF=0x63\texttt{OP\_IF}=\texttt{0x63}OP_IF=0x63, OP_ENDIF=0x68\texttt{OP\_ENDIF}=\texttt{0x68}OP_ENDIF=0x68, OP_CODESEPARATOR=0xab\texttt{OP\_CODESEPARATOR}=\texttt{0xab}OP_CODESEPARATOR=0xab, OP_CHECKSIG=0xac\texttt{OP\_CHECKSIG}=\texttt{0xac}OP_CHECKSIG=0xac, OP_CHECKSIGVERIFY=0xad\texttt{OP\_CHECKSIGVERIFY}=\texttt{0xad}OP_CHECKSIGVERIFY=0xad, OP_CHECKMULTISIG=0xae\texttt{OP\_CHECKMULTISIG}=\texttt{0xae}OP_CHECKMULTISIG=0xae, OP_CHECKMULTISIGVERIFY=0xaf\texttt{OP\_CHECKMULTISIGVERIFY}=\texttt{0xaf}OP_CHECKMULTISIGVERIFY=0xaf.
  • A signature version vvv is one of exactly two values: base\mathsf{base}base (legacy) or witnessV0\mathsf{witnessV0}witnessV0.

Reading one instruction from bytes: getOp\mathrm{getOp}getOp

getOp(x)\mathrm{getOp}(x)getOp(x) returns either none\mathsf{none}none or some(i,y)\mathsf{some}(i, y)some(i,y) with iii an instruction and yyy the remaining bytes:

  • x=εx = \varepsilonx=ε: none\mathsf{none}none.
  • Otherwise let bbb be the first byte and y0y_0y0​ the rest.
    • If b≤0x4eb \le \texttt{0x4e}b≤0x4e (a push opcode), a data length nnn and a position are determined: if b<0x4cb < \texttt{0x4c}b<0x4c, n=bn = bn=b and the data starts right after bbb; if b=0x4cb = \texttt{0x4c}b=0x4c, nnn is the next byte (none\mathsf{none}none if there is none); if b=0x4db = \texttt{0x4d}b=0x4d, nnn is the little-endian value of the next 2 bytes (none\mathsf{none}none if fewer than 2 remain); if b=0x4eb=\texttt{0x4e}b=0x4e, nnn is the little-endian value of the next 4 bytes (none\mathsf{none}none if fewer than 4 remain). Then, if fewer than nnn bytes remain, none\mathsf{none}none; otherwise some(push(next n bytes), the bytes after them)\mathsf{some}(\mathrm{push}(\text{next } n \text{ bytes}),\ \text{the bytes after them})some(push(next n bytes), the bytes after them). (So b=0x00b=\texttt{0x00}b=0x00 gives push(ε)\mathrm{push}(\varepsilon)push(ε).)
    • If b>0x4eb > \texttt{0x4e}b>0x4e: some(op(b),y0)\mathsf{some}(\mathrm{op}(b), y_0)some(op(b),y0​).

On success the remainder is a suffix of xxx that is at least one byte shorter than xxx. getOp\mathrm{getOp}getOp never returns op(c)\mathrm{op}(c)op(c) with c≤0x4ec \le \texttt{0x4e}c≤0x4e.

The annotated parse: annotate\mathrm{annotate}annotate

annotate(s)=annotateAux(∣s∣,s)\mathrm{annotate}(s) = \mathrm{annotateAux}(|s|, s)annotate(s)=annotateAux(∣s∣,s), where, with a fuel counter nnn:

  • annotateAux(n,ε)=some([ ])\mathrm{annotateAux}(n, \varepsilon) = \mathsf{some}([\,])annotateAux(n,ε)=some([]) for every nnn;
  • annotateAux(0,x)=none\mathrm{annotateAux}(0, x) = \mathsf{none}annotateAux(0,x)=none for x≠εx \neq \varepsilonx=ε;
  • annotateAux(n+1,x)\mathrm{annotateAux}(n+1, x)annotateAux(n+1,x) for x≠εx\ne\varepsilonx=ε: if getOp(x)=none\mathrm{getOp}(x)=\mathsf{none}getOp(x)=none then none\mathsf{none}none; if getOp(x)=some(i,r)\mathrm{getOp}(x) = \mathsf{some}(i, r)getOp(x)=some(i,r) then, if annotateAux(n,r)=none\mathrm{annotateAux}(n, r) = \mathsf{none}annotateAux(n,r)=none the result is none\mathsf{none}none, and if it is some(L)\mathsf{some}(L)some(L) the result is some([(i,r)]+ ⁣ ⁣+L)\mathsf{some}([(i,r)] \mathbin{+\!\!+} L)some([(i,r)]++L).

So on success annotate(s)=some([(i1,r1),…,(in,rn)])\mathrm{annotate}(s) = \mathsf{some}([(i_1, r_1), \dots, (i_n, r_n)])annotate(s)=some([(i1​,r1​),…,(in​,rn​)]), where i1i_1i1​ is read from sss leaving r1r_1r1​, ij+1i_{j+1}ij+1​ is read from rjr_jrj​ leaving rj+1r_{j+1}rj+1​, and rn=εr_n = \varepsilonrn​=ε: each instruction is paired with the bytes that follow it in sss. annotate(ε)=some([ ])\mathrm{annotate}(\varepsilon) = \mathsf{some}([\,])annotate(ε)=some([]). Since every successful getOp\mathrm{getOp}getOp consumes at least one byte, the fuel ∣s∣|s|∣s∣ never runs out while input remains; hence annotate(s)=none\mathrm{annotate}(s) = \mathsf{none}annotate(s)=none exactly when getOp\mathrm{getOp}getOp fails at some instruction boundary, i.e. on a malformed push (a truncated length field, or fewer data bytes than announced).

The plain parse: parseScript\mathrm{parseScript}parseScript

parseScript(s)=parseScriptAux(∣s∣,s)\mathrm{parseScript}(s) = \mathrm{parseScriptAux}(|s|, s)parseScript(s)=parseScriptAux(∣s∣,s) follows exactly the same recursion as annotateAux\mathrm{annotateAux}annotateAux (empty input gives some([ ])\mathsf{some}([\,])some([]); fuel 000 on non-empty input gives none\mathsf{none}none; a failing getOp\mathrm{getOp}getOp gives none\mathsf{none}none), but on success records only the instructions: some([i1,…,in])\mathsf{some}([i_1,\dots,i_n])some([i1​,…,in​]).

Signature-push deletion: pushBytes\mathrm{pushBytes}pushBytes, findAndDelete\mathrm{findAndDelete}findAndDelete, fadSig\mathrm{fadSig}fadSig, fadAll\mathrm{fadAll}fadAll

  • pushBytes(d)\mathrm{pushBytes}(d)pushBytes(d), the canonical push of ddd: if ∣d∣<0x4c|d| < \texttt{0x4c}∣d∣<0x4c it is the byte ∣d∣|d|∣d∣ followed by ddd; else if ∣d∣≤255|d| \le 255∣d∣≤255 it is 0x4c\texttt{0x4c}0x4c, the byte ∣d∣|d|∣d∣, then ddd; else if ∣d∣≤65535|d| \le 65535∣d∣≤65535 it is 0x4d\texttt{0x4d}0x4d, ∣d∣|d|∣d∣ as 2 little-endian bytes, then ddd; otherwise 0x4e\texttt{0x4e}0x4e, ∣d∣ mod 232|d| \bmod 2^{32}∣d∣mod232 as 4 little-endian bytes, then ddd. It is never empty (pushBytes(ε)=[0x00]\mathrm{pushBytes}(\varepsilon) = [\texttt{0x00}]pushBytes(ε)=[0x00]).
  • findAndDelete(x,b)\mathrm{findAndDelete}(x, b)findAndDelete(x,b) returns a pair (resulting string, count); only the first component (written FD(x,b)\mathrm{FD}(x,b)FD(x,b)) is used here. If b=εb = \varepsilonb=ε the result is (x,0)(x, 0)(x,0). Otherwise xxx is scanned from the start: at the current instruction boundary, copies of bbb are removed as long as the remaining string begins with bbb (each removal counted); then one instruction is read with getOp\mathrm{getOp}getOp: 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 ∣x∣+1|x|+1∣x∣+1, and when fuel is exhausted the remaining bytes are kept verbatim; every iteration of the scan consumes at least one byte.)
  • fadSig(v,sc,sig)\mathrm{fadSig}(v, \mathit{sc}, \mathit{sig})fadSig(v,sc,sig):
fadSig(base,sc,sig)=FD(sc,pushBytes(sig)),fadSig(witnessV0,sc,sig)=sc.\mathrm{fadSig}(\mathsf{base}, \mathit{sc}, \mathit{sig}) = \mathrm{FD}\big(\mathit{sc}, \mathrm{pushBytes}(\mathit{sig})\big), \qquad \mathrm{fadSig}(\mathsf{witnessV0}, \mathit{sc}, \mathit{sig}) = \mathit{sc}.fadSig(base,sc,sig)=FD(sc,pushBytes(sig)),fadSig(witnessV0,sc,sig)=sc.
  • fadAll(v,sc,[σ1,…,σm])\mathrm{fadAll}(v, \mathit{sc}, [\sigma_1,\dots,\sigma_m])fadAll(v,sc,[σ1​,…,σm​]) is the left fold of fadSig(v,⋅,⋅)\mathrm{fadSig}(v,\cdot,\cdot)fadSig(v,⋅,⋅) over the list, in list order:
fadAll(v,sc,[σ1,…,σm])=fadSig(v,⋯fadSig(v,fadSig(v,sc,σ1),σ2)⋯ ,σm),\mathrm{fadAll}(v, \mathit{sc}, [\sigma_1,\dots,\sigma_m]) = \mathrm{fadSig}\big(v, \cdots \mathrm{fadSig}(v, \mathrm{fadSig}(v, \mathit{sc}, \sigma_1), \sigma_2) \cdots, \sigma_m\big),fadAll(v,sc,[σ1​,…,σm​])=fadSig(v,⋯fadSig(v,fadSig(v,sc,σ1​),σ2​)⋯,σm​),

and fadAll(v,sc,[ ])=sc\mathrm{fadAll}(v, \mathit{sc}, [\,]) = \mathit{sc}fadAll(v,sc,[])=sc.

Script numbers and multisigSigs\mathrm{multisigSigs}multisigSigs

  • toNum(x)\mathrm{toNum}(x)toNum(x) (the call with "minimal encoding not required" and maximum size 444): none\mathsf{none}none if ∣x∣>4|x| > 4∣x∣>4; otherwise some(z)\mathsf{some}(z)some(z) with z∈Zz \in \mathbb Zz∈Z obtained by reading xxx little-endian, the bit 0x80\texttt{0x80}0x80 of the last byte being a sign bit: if it is set, zzz is minus the little-endian value of xxx with that bit cleared; else zzz is the little-endian value of xxx. toNum(ε)=some(0)\mathrm{toNum}(\varepsilon) = \mathsf{some}(0)toNum(ε)=some(0). No minimality check is performed.

  • For an integer zzz, z+:=max⁡(z,0)z^{+} := \max(z, 0)z+:=max(z,0) (negative integers convert to the natural number 000).

  • multisigSigs(Σ)\mathrm{multisigSigs}(\Sigma)multisigSigs(Σ), for a stack Σ\SigmaΣ listed top first, is a list of byte strings:

    • Σ\SigmaΣ empty: [ ][\,][].
    • Σ=[nk]+ ⁣ ⁣+R\Sigma = [n_k] \mathbin{+\!\!+} RΣ=[nk​]++R: if toNum(nk)=none\mathrm{toNum}(n_k) = \mathsf{none}toNum(nk​)=none, [ ][\,][]. If toNum(nk)=some(NK)\mathrm{toNum}(n_k) = \mathsf{some}(N_K)toNum(nk​)=some(NK​), let R′=dropNK+(R)R' = \mathrm{drop}_{N_K^{+}}(R)R′=dropNK+​​(R). If R′R'R′ is empty, [ ][\,][]. If R′=[ns]+ ⁣ ⁣+R′′R' = [n_s] \mathbin{+\!\!+} R''R′=[ns​]++R′′: if toNum(ns)=none\mathrm{toNum}(n_s) = \mathsf{none}toNum(ns​)=none, [ ][\,][]; if toNum(ns)=some(NS)\mathrm{toNum}(n_s) = \mathsf{some}(N_S)toNum(ns​)=some(NS​), the result is takeNS+(R′′)\mathrm{take}_{N_S^{+}}(R'')takeNS+​​(R′′) (all of R′′R''R′′ if it has fewer than NS+N_S^{+}NS+​ elements).

    No range checks are made on NKN_KNK​, NSN_SNS​ (e.g. NS>NKN_S > N_KNS​>NK​, or negative counts, are accepted).

Oracles

  • A published oracle OOO consists of five functions B∗→B∗\mathcal B^*\to\mathcal B^*B∗→B∗ (RIPEMD-160, SHA-1, SHA-256, HASH160, HASH256), a function O.checkSig(sig,pk)∈{none,some(true),some(false)}O.\mathrm{checkSig}(\mathit{sig}, \mathit{pk}) \in \{\mathsf{none}, \mathsf{some}(\mathrm{true}), \mathsf{some}(\mathrm{false})\}O.checkSig(sig,pk)∈{none,some(true),some(false)}, and two predicates checkLockTime,checkSequence:Z→{true,false}\mathrm{checkLockTime}, \mathrm{checkSequence} : \mathbb Z \to \{\mathrm{true},\mathrm{false}\}checkLockTime,checkSequence:Z→{true,false}.
  • A V2 oracle ooo has the same five hash functions and two predicates, but its signature check takes a script code as an extra first argument: o.checkSig(sc,sig,pk)∈{none,some(true),some(false)}o.\mathrm{checkSig}(\mathit{sc}, \mathit{sig}, \mathit{pk}) \in \{\mathsf{none}, \mathsf{some}(\mathrm{true}), \mathsf{some}(\mathrm{false})\}o.checkSig(sc,sig,pk)∈{none,some(true),some(false)}. All components are arbitrary functions.
  • toOracle(o)\mathrm{toOracle}(o)toOracle(o): the published oracle with ooo's hashes and predicates and the signature check that always returns none\mathsf{none}none.
  • withCode(o,sc)\mathrm{withCode}(o, \mathit{sc})withCode(o,sc): toOracle(o)\mathrm{toOracle}(o)toOracle(o) with signature check (sig,pk)↦o.checkSig(sc,sig,pk)(\mathit{sig}, \mathit{pk}) \mapsto o.\mathrm{checkSig}(\mathit{sc}, \mathit{sig}, \mathit{pk})(sig,pk)↦o.checkSig(sc,sig,pk).
  • withCodeSig(o,v,sc)\mathrm{withCodeSig}(o, v, \mathit{sc})withCodeSig(o,v,sc): toOracle(o)\mathrm{toOracle}(o)toOracle(o) with signature check (sig,pk)↦o.checkSig(fadSig(v,sc,sig),sig,pk)(\mathit{sig}, \mathit{pk}) \mapsto o.\mathrm{checkSig}\big(\mathrm{fadSig}(v, \mathit{sc}, \mathit{sig}), \mathit{sig}, \mathit{pk}\big)(sig,pk)↦o.checkSig(fadSig(v,sc,sig),sig,pk).

V2 states and oracleAt\mathrm{oracleAt}oracleAt

  • A V2 state SSS is a pair (S.st,S.sc)(S.\mathrm{st}, S.\mathrm{sc})(S.st,S.sc) of a published interpreter state S.stS.\mathrm{st}S.st (a main stack and an alt stack of byte strings listed top first, a boolean condition stack vfExec\mathrm{vfExec}vfExec, and an operation counter) and a byte string S.scS.\mathrm{sc}S.sc, the script code. Write stack(S)\mathrm{stack}(S)stack(S) and vfExec(S)\mathrm{vfExec}(S)vfExec(S) for the main stack and condition stack of S.stS.\mathrm{st}S.st.
  • oracleAt(v,o,S,i)\mathrm{oracleAt}(v, o, S, i)oracleAt(v,o,S,i), the published oracle used for instruction iii from state SSS:
    • if i=op(c)i = \mathrm{op}(c)i=op(c) with c=0xaec = \texttt{0xae}c=0xae or c=0xafc = \texttt{0xaf}c=0xaf: withCode(o, fadAll(v,S.sc,multisigSigs(stack(S))))\mathrm{withCode}\big(o,\ \mathrm{fadAll}(v, S.\mathrm{sc}, \mathrm{multisigSigs}(\mathrm{stack}(S)))\big)withCode(o, fadAll(v,S.sc,multisigSigs(stack(S))));
    • for every other op(c)\mathrm{op}(c)op(c), and for every push(d)\mathrm{push}(d)push(d): withCodeSig(o,v,S.sc)\mathrm{withCodeSig}(o, v, S.\mathrm{sc})withCodeSig(o,v,S.sc).

The published interpreter: step\mathrm{step}step, run\mathrm{run}run, evalScript\mathrm{evalScript}evalScript

  • Flags fff are three booleans (f.cltv,f.csv,f.nulldummy)(f.\mathrm{cltv}, f.\mathrm{csv}, f.\mathrm{nulldummy})(f.cltv,f.csv,f.nulldummy).
  • A published state is a tuple (main stack, alt stack, vfExec\mathrm{vfExec}vfExec, opCount\mathrm{opCount}opCount): two stacks of byte strings listed top first, a list of booleans, and a natural number. initial(Σ)=(Σ,[ ],[ ],0)\mathrm{initial}(\Sigma) = (\Sigma, [\,], [\,], 0)initial(Σ)=(Σ,[],[],0). allTrue(L)\mathrm{allTrue}(L)allTrue(L) is true iff every entry of the boolean list LLL is true (in particular allTrue([ ])\mathrm{allTrue}([\,])allTrue([]) is true).
  • step(f,O,T,i)\mathrm{step}(f, O, T, i)step(f,O,T,i), one instruction from published state TTT with published oracle OOO:
    • i=push(d)i = \mathrm{push}(d)i=push(d): none\mathsf{none}none if ∣d∣>520|d| > 520∣d∣>520; otherwise T′T'T′ is TTT with ddd pushed on the main stack if allTrue(T.vfExec)\mathrm{allTrue}(T.\mathrm{vfExec})allTrue(T.vfExec), and T′=TT' = TT′=T otherwise; the result is none\mathsf{none}none if the two stacks of T′T'T′ together hold more than 100010001000 elements, else some(T′)\mathsf{some}(T')some(T′). The oracle is not used.
    • i=op(c)i = \mathrm{op}(c)i=op(c): let e=allTrue(T.vfExec)e = \mathrm{allTrue}(T.\mathrm{vfExec})e=allTrue(T.vfExec). If c>0x60c > \texttt{0x60}c>0x60 and T.opCount+1>201T.\mathrm{opCount} + 1 > 201T.opCount+1>201, none\mathsf{none}none; otherwise the counter is incremented when c>0x60c > \texttt{0x60}c>0x60. Then: if ccc 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), none\mathsf{none}none (whether or not executing). Else if eee is true or 0x63≤c≤0x68\texttt{0x63} \le c \le \texttt{0x68}0x63≤c≤0x68, the result is execOp(f,O,e,c,T)\mathrm{execOp}(f, O, e, c, T)execOp(f,O,e,c,T) 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.
  • execOp\mathrm{execOp}execOp is the opcode switch (one case per opcode; any opcode not handled gives none\mathsf{none}none). Its use of the oracle and the cases relevant here:
    • the hash opcodes 0xa6\texttt{0xa6}0xa6–0xaa\texttt{0xaa}0xaa replace the top element by the corresponding hash function of OOO; 0xb1\texttt{0xb1}0xb1 (when f.cltvf.\mathrm{cltv}f.cltv) consults O.checkLockTimeO.\mathrm{checkLockTime}O.checkLockTime and 0xb2\texttt{0xb2}0xb2 (when f.csvf.\mathrm{csv}f.csv) O.checkSequenceO.\mathrm{checkSequence}O.checkSequence;
    • 0xab\texttt{0xab}0xab (OP_CODESEPARATOR\texttt{OP\_CODESEPARATOR}OP_CODESEPARATOR) returns the state unchanged;
    • 0xac\texttt{0xac}0xac/0xad\texttt{0xad}0xad: the main stack must be [pk,sig]+ ⁣ ⁣+R[\mathit{pk}, \mathit{sig}] \mathbin{+\!\!+} R[pk,sig]++R (else none\mathsf{none}none); O.checkSig(sig,pk)O.\mathrm{checkSig}(\mathit{sig}, \mathit{pk})O.checkSig(sig,pk) is called; none\mathsf{none}none gives none\mathsf{none}none; some(b)\mathsf{some}(b)some(b): for 0xad\texttt{0xad}0xad the stack becomes RRR if bbb, else none\mathsf{none}none; for 0xac\texttt{0xac}0xac the stack becomes [ [0x01] ]+ ⁣ ⁣+R[\,[\texttt{0x01}]\,] \mathbin{+\!\!+} R[[0x01]]++R if bbb and [ε]+ ⁣ ⁣+R[\varepsilon] \mathbin{+\!\!+} R[ε]++R if not;
    • 0xae\texttt{0xae}0xae/0xaf\texttt{0xaf}0xaf: the main stack must be [nk]+ ⁣ ⁣+R[n_k] \mathbin{+\!\!+} R[nk​]++R; NK=toNum(nk)N_K = \mathrm{toNum}(n_k)NK​=toNum(nk​) must exist with 0≤NK≤200 \le N_K \le 200≤NK​≤20; opCount+NK≤201\mathrm{opCount} + N_K \le 201opCount+NK​≤201; the next NKN_KNK​ elements are the keys (there must be that many); then an element nsn_sns​ with NS=toNum(ns)N_S = \mathrm{toNum}(n_s)NS​=toNum(ns​) existing and 0≤NS≤NK0 \le N_S \le N_K0≤NS​≤NK​; the next NSN_SNS​ elements are the signatures (there must be that many); then the matching loop below must not return none\mathsf{none}none; then one more element (the dummy) must exist, and if f.nulldummyf.\mathrm{nulldummy}f.nulldummy it must be empty; the stack becomes the elements below the dummy, with [ [0x01] ][\,[\texttt{0x01}]\,][[0x01]] or [ε][\varepsilon][ε] pushed for 0xae\texttt{0xae}0xae according to the loop's verdict, while for 0xaf\texttt{0xaf}0xaf a false verdict gives none\mathsf{none}none; opCount\mathrm{opCount}opCount becomes opCount+NK\mathrm{opCount}+N_KopCount+NK​. Any failed requirement gives none\mathsf{none}none. The matching loop on signatures and keys (both top first): no signatures left gives true\mathrm{true}true; signatures left but no keys gives false\mathrm{false}false; otherwise O.checkSig(current sig,current key)O.\mathrm{checkSig}(\text{current sig}, \text{current key})O.checkSig(current sig,current key) is called, none\mathsf{none}none aborts with none\mathsf{none}none; on success both advance, on failure only the key advances; whenever fewer keys than signatures remain the verdict is false\mathrm{false}false.
  • run(f,O,T,[i1,…,in])\mathrm{run}(f, O, T, [i_1,\dots,i_n])run(f,O,T,[i1​,…,in​]) applies step\mathrm{step}step to i1,…,ini_1, \dots, i_ni1​,…,in​ in turn, giving none\mathsf{none}none as soon as a step does; after the last instruction it returns some(final state)\mathsf{some}(\text{final state})some(final state) if the final vfExec\mathrm{vfExec}vfExec is empty and none\mathsf{none}none otherwise.
  • evalScript(f,O,Σ,P)=mapmain stack(run(f,O,initial(Σ),P))\mathrm{evalScript}(f, O, \Sigma, P) = \mathrm{map}_{\text{main stack}}\big(\mathrm{run}(f, O, \mathrm{initial}(\Sigma), P)\big)evalScript(f,O,Σ,P)=mapmain stack​(run(f,O,initial(Σ),P)): the final main stack, or none\mathsf{none}none.

The V2 interpreter: stepV2\mathrm{stepV2}stepV2, runV2\mathrm{runV2}runV2, evalScriptV2\mathrm{evalScriptV2}evalScriptV2

  • stepV2(f,v,o,S,(i,r))\mathrm{stepV2}(f, v, o, S, (i, r))stepV2(f,v,o,S,(i,r)), for a V2 state SSS and a pair of an instruction iii and a byte string rrr:
stepV2(f,v,o,S,(i,r))=map T↦(T, sc′)(step(f,oracleAt(v,o,S,i),S.st,i)),\mathrm{stepV2}(f,v,o,S,(i,r)) = \mathrm{map}_{\,T \mapsto (T,\ \mathit{sc}')}\Big(\mathrm{step}\big(f, \mathrm{oracleAt}(v,o,S,i), S.\mathrm{st}, i\big)\Big),stepV2(f,v,o,S,(i,r))=mapT↦(T, sc′)​(step(f,oracleAt(v,o,S,i),S.st,i)),

where sc′=r\mathit{sc}' = rsc′=r if i=op(0xab)i = \mathrm{op}(\texttt{0xab})i=op(0xab) and allTrue(vfExec(S))\mathrm{allTrue}(\mathrm{vfExec}(S))allTrue(vfExec(S)) (the condition stack before the step), and sc′=S.sc\mathit{sc}' = S.\mathrm{sc}sc′=S.sc otherwise. So it fails exactly when the published step fails, and otherwise the published part is the published step's result.

  • runV2(f,v,o,S,[x1,…,xn])\mathrm{runV2}(f, v, o, S, [x_1,\dots,x_n])runV2(f,v,o,S,[x1​,…,xn​]) applies stepV2\mathrm{stepV2}stepV2 to x1,…,xnx_1,\dots,x_nx1​,…,xn​ in turn, giving none\mathsf{none}none as soon as a step does; after the last one it returns some(final V2 state)\mathsf{some}(\text{final V2 state})some(final V2 state) if the final vfExec\mathrm{vfExec}vfExec is empty and none\mathsf{none}none otherwise.
  • evalScriptV2(f,v,o,Σ,script)\mathrm{evalScriptV2}(f, v, o, \Sigma, \mathit{script})evalScriptV2(f,v,o,Σ,script) for a byte string script\mathit{script}script: if annotate(script)=none\mathrm{annotate}(\mathit{script}) = \mathsf{none}annotate(script)=none the result is none\mathsf{none}none; if it is some(l)\mathsf{some}(l)some(l), the result is the main stack of runV2(f,v,o,(initial(Σ),script),l)\mathrm{runV2}\big(f, v, o, (\mathrm{initial}(\Sigma), \mathit{script}), l\big)runV2(f,v,o,(initial(Σ),script),l) under map\mathrm{map}map (so none\mathsf{none}none if that run fails). The initial script code is the whole byte string script\mathit{script}script.

Side conditions: StepOk\mathrm{StepOk}StepOk, RunOk\mathrm{RunOk}RunOk

  • StepOk(v,S,i)\mathrm{StepOk}(v, S, i)StepOk(v,S,i) for a V2 state SSS and instruction iii:

    • i=push(d)i = \mathrm{push}(d)i=push(d): always true.
    • i=op(c)i = \mathrm{op}(c)i=op(c): if allTrue(vfExec(S))\mathrm{allTrue}(\mathrm{vfExec}(S))allTrue(vfExec(S)) is true, then both (a) c≠0xabc \ne \texttt{0xab}c=0xab, and (b) if c=0xaec = \texttt{0xae}c=0xae or c=0xafc = \texttt{0xaf}c=0xaf, then for every sig\mathit{sig}sig in the list multisigSigs(stack(S))\mathrm{multisigSigs}(\mathrm{stack}(S))multisigSigs(stack(S)), fadSig(v,S.sc,sig)=S.sc\mathrm{fadSig}(v, S.\mathrm{sc}, \mathit{sig}) = S.\mathrm{sc}fadSig(v,S.sc,sig)=S.sc.

    Consequences of the definition: when allTrue(vfExec(S))\mathrm{allTrue}(\mathrm{vfExec}(S))allTrue(vfExec(S)) is false (inside a non-executed branch), StepOk\mathrm{StepOk}StepOk holds for every instruction, including op(0xab)\mathrm{op}(\texttt{0xab})op(0xab). When it is true, StepOk(v,S,op(0xab))\mathrm{StepOk}(v,S,\mathrm{op}(\texttt{0xab}))StepOk(v,S,op(0xab)) is false. For v=witnessV0v = \mathsf{witnessV0}v=witnessV0, fadSig\mathrm{fadSig}fadSig is the identity, so clause (b) always holds. Clause (b) also holds when multisigSigs(stack(S))\mathrm{multisigSigs}(\mathrm{stack}(S))multisigSigs(stack(S)) is empty. No condition is placed on 0xac\texttt{0xac}0xac/0xad\texttt{0xad}0xad.

  • RunOk(f,v,o,S,l)\mathrm{RunOk}(f, v, o, S, l)RunOk(f,v,o,S,l) for a list lll of (instruction, bytes) pairs:

    • lll empty: true.
    • l=[(i1,r1)]+ ⁣ ⁣+l′l = [(i_1, r_1)] \mathbin{+\!\!+} l'l=[(i1​,r1​)]++l′: StepOk(v,S,i1)\mathrm{StepOk}(v, S, i_1)StepOk(v,S,i1​) holds, and for every V2 state S′S'S′ with stepV2(f,v,o,S,(i1,r1))=some(S′)\mathrm{stepV2}(f, v, o, S, (i_1,r_1)) = \mathsf{some}(S')stepV2(f,v,o,S,(i1​,r1​))=some(S′), RunOk(f,v,o,S′,l′)\mathrm{RunOk}(f, v, o, S', l')RunOk(f,v,o,S′,l′) holds.

    Unwound: along the V2 run from SSS over lll, StepOk\mathrm{StepOk}StepOk holds at each instruction that is reached (the state before instruction jjj being the result of the j−1j-1j−1 preceding successful steps), including the instruction whose step fails; once a step returns none\mathsf{none}none, nothing is required of the later instructions. The final empty-vfExec\mathrm{vfExec}vfExec check of runV2\mathrm{runV2}runV2 plays no role. RunOk\mathrm{RunOk}RunOk depends on fff and ooo only through which states the steps reach.

Static conditions: NoCodeSep\mathrm{NoCodeSep}NoCodeSep, NoMultisig\mathrm{NoMultisig}NoMultisig

For a parsed script PPP (a list of instructions): NoCodeSep(P)\mathrm{NoCodeSep}(P)NoCodeSep(P) means op(0xab)\mathrm{op}(\texttt{0xab})op(0xab) does not occur in PPP; NoMultisig(P)\mathrm{NoMultisig}(P)NoMultisig(P) means neither op(0xae)\mathrm{op}(\texttt{0xae})op(0xae) nor op(0xaf)\mathrm{op}(\texttt{0xaf})op(0xaf) occurs in PPP. (Occurrences anywhere count, including inside branches that would not be executed.)

Concrete oracles

  • Signature flags g=(g.dersig,g.lowS,g.strictenc,g.witnessPubkeyType)g = (g.\mathrm{dersig}, g.\mathrm{lowS}, g.\mathrm{strictenc}, g.\mathrm{witnessPubkeyType})g=(g.dersig,g.lowS,g.strictenc,g.witnessPubkeyType), four booleans. SigEncg(sig)\mathrm{SigEnc}_g(\mathit{sig})SigEncg​(sig) (signature-encoding check): true if sig=ε\mathit{sig} = \varepsilonsig=ε; false if one of dersig,lowS,strictenc\mathrm{dersig}, \mathrm{lowS}, \mathrm{strictenc}dersig,lowS,strictenc is set and sig\mathit{sig}sig is not strict DER plus a hash-type byte; false if lowS\mathrm{lowS}lowS is set and the signature does not have low SSS; false if strictenc\mathrm{strictenc}strictenc is set and the hash type is undefined; true otherwise. PkEncg,v(pk)\mathrm{PkEnc}_{g,v}(\mathit{pk})PkEncg,v​(pk) (public-key encoding check): false if strictenc\mathrm{strictenc}strictenc is set and pk\mathit{pk}pk is not a 33-byte compressed (02/03\texttt{02}/\texttt{03}02/03) or 65-byte uncompressed (04\texttt{04}04) key; false if witnessPubkeyType\mathrm{witnessPubkeyType}witnessPubkeyType is set, v=witnessV0v=\mathsf{witnessV0}v=witnessV0 and pk\mathit{pk}pk is not compressed; true otherwise.
  • ECDSA(tx,nin,a,v,sig,pk,sc)\mathrm{ECDSA}(\mathit{tx}, n_{\mathrm{in}}, a, v, \mathit{sig}, \mathit{pk}, \mathit{sc})ECDSA(tx,nin​,a,v,sig,pk,sc) (the transaction checker's ECDSA check, with tx\mathit{tx}tx a transaction, nin∈Nn_{\mathrm{in}}\in\mathbb Nnin​∈N an input index, a∈Za\in\mathbb Za∈Z an amount): false if pk\mathit{pk}pk's length does not match its header byte or sig=ε\mathit{sig} = \varepsilonsig=ε; otherwise the last byte of sig\mathit{sig}sig is the hash type, the signature hash of tx\mathit{tx}tx for input ninn_{\mathrm{in}}nin​ with script code sc\mathit{sc}sc is computed (legacy algorithm for base\mathsf{base}base, BIP143 algorithm with amount aaa for witnessV0\mathsf{witnessV0}witnessV0), the result is false if v=witnessV0v = \mathsf{witnessV0}v=witnessV0 and a<0a < 0a<0, and otherwise it is the secp256k1 ECDSA verification of sig\mathit{sig}sig without its last byte against pk\mathit{pk}pk and that hash.
  • legacyOracleV2(g,tx,nin,a,v)\mathrm{legacyOracleV2}(g, \mathit{tx}, n_{\mathrm{in}}, a, v)legacyOracleV2(g,tx,nin​,a,v) is the V2 oracle with Bitcoin Core's RIPEMD-160, SHA-1, SHA-256, HASH160, HASH256, the lock-time and sequence checks of tx\mathit{tx}tx at input ninn_{\mathrm{in}}nin​, and
checkSig(sc,sig,pk)=noneif ¬SigEncg(sig) or ¬PkEncg,v(pk),\mathrm{checkSig}(\mathit{sc}, \mathit{sig}, \mathit{pk}) = \mathsf{none} \quad \text{if } \neg\mathrm{SigEnc}_g(\mathit{sig}) \text{ or } \neg\mathrm{PkEnc}_{g,v}(\mathit{pk}),checkSig(sc,sig,pk)=noneif ¬SigEncg​(sig) or ¬PkEncg,v​(pk),

and otherwise

checkSig(sc,sig,pk)=some(ECDSA(tx,nin,a,v,sig,pk,sc)).\mathrm{checkSig}(\mathit{sc}, \mathit{sig}, \mathit{pk}) = \mathsf{some}\big(\mathrm{ECDSA}(\mathit{tx}, n_{\mathrm{in}}, a, v, \mathit{sig}, \mathit{pk}, \mathit{sc})\big).checkSig(sc,sig,pk)=some(ECDSA(tx,nin​,a,v,sig,pk,sc)).

The script code sc\mathit{sc}sc is used as given (no deletion inside the oracle).

  • legacyOracle(g,tx,nin,a,v,sc)\mathrm{legacyOracle}(g, \mathit{tx}, n_{\mathrm{in}}, a, v, \mathit{sc})legacyOracle(g,tx,nin​,a,v,sc) is the published oracle with the same hashes and lock-time/sequence checks and signature check checkSigPreTapscript\mathrm{checkSigPreTapscript}checkSigPreTapscript: for (sig,pk)(\mathit{sig}, \mathit{pk})(sig,pk), let sc′=FD(sc,pushBytes(sig))\mathit{sc}' = \mathrm{FD}(\mathit{sc}, \mathrm{pushBytes}(\mathit{sig}))sc′=FD(sc,pushBytes(sig)) if v=basev=\mathsf{base}v=base and sc′=sc\mathit{sc}' = \mathit{sc}sc′=sc if v=witnessV0v = \mathsf{witnessV0}v=witnessV0; the result is none\mathsf{none}none if ¬SigEncg(sig)\neg\mathrm{SigEnc}_g(\mathit{sig})¬SigEncg​(sig) or ¬PkEncg,v(pk)\neg\mathrm{PkEnc}_{g,v}(\mathit{pk})¬PkEncg,v​(pk), and some(ECDSA(tx,nin,a,v,sig,pk,sc′))\mathsf{some}(\mathrm{ECDSA}(\mathit{tx}, n_{\mathrm{in}}, a, v, \mathit{sig}, \mathit{pk}, \mathit{sc}'))some(ECDSA(tx,nin​,a,v,sig,pk,sc′)) otherwise.

Verification context and byte-level evaluators

  • A context ccc consists of consensus flags c.flagsc.\mathrm{flags}c.flags (seven booleans 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 c.txc.\mathrm{tx}c.tx, an input index c.nin∈Nc.n_{\mathrm{in}} \in \mathbb Nc.nin​∈N and an amount c.a∈Zc.a \in \mathbb Zc.a∈Z. From it: interpreter flags fc=(cltv,csv,nulldummy)f_c = (\mathrm{cltv}, \mathrm{csv}, \mathrm{nulldummy})fc​=(cltv,csv,nulldummy) and signature flags gc=(dersig,false,false,false)g_c = (\mathrm{dersig}, \mathrm{false}, \mathrm{false}, \mathrm{false})gc​=(dersig,false,false,false); write oc,v=legacyOracleV2(gc,c.tx,c.nin,c.a,v)o_{c,v} = \mathrm{legacyOracleV2}(g_c, c.\mathrm{tx}, c.n_{\mathrm{in}}, c.a, v)oc,v​=legacyOracleV2(gc​,c.tx,c.nin​,c.a,v).
  • evalBytesV2(c,v,Σ,script)\mathrm{evalBytesV2}(c, v, \Sigma, \mathit{script})evalBytesV2(c,v,Σ,script): none\mathsf{none}none if ∣script∣>10000|\mathit{script}| > 10000∣script∣>10000; otherwise evalScriptV2(fc,v,oc,v,Σ,script)\mathrm{evalScriptV2}(f_c, v, o_{c,v}, \Sigma, \mathit{script})evalScriptV2(fc​,v,oc,v​,Σ,script).
  • evalBytes(c,v,Σ,script)\mathrm{evalBytes}(c, v, \Sigma, \mathit{script})evalBytes(c,v,Σ,script) (published): none\mathsf{none}none if ∣script∣>10000|\mathit{script}| > 10000∣script∣>10000; otherwise, if parseScript(script)=none\mathrm{parseScript}(\mathit{script}) = \mathsf{none}parseScript(script)=none then none\mathsf{none}none, and if it is some(P)\mathsf{some}(P)some(P) then evalScript(fc, legacyOracle(gc,c.tx,c.nin,c.a,v,script), Σ, P)\mathrm{evalScript}\big(f_c,\ \mathrm{legacyOracle}(g_c, c.\mathrm{tx}, c.n_{\mathrm{in}}, c.a, v, \mathit{script}),\ \Sigma,\ P\big)evalScript(fc​, legacyOracle(gc​,c.tx,c.nin​,c.a,v,script), Σ, P) — i.e. the signature check always uses the whole byte string script\mathit{script}script as script code, with only the checked signature's push deleted (for base\mathsf{base}base).

EvalOk\mathrm{EvalOk}EvalOk

EvalOk(c,v,Σ,script)\mathrm{EvalOk}(c, v, \Sigma, \mathit{script})EvalOk(c,v,Σ,script) means: for every list lll with annotate(script)=some(l)\mathrm{annotate}(\mathit{script}) = \mathsf{some}(l)annotate(script)=some(l),

RunOk(fc,v,oc,v,(initial(Σ),script),l).\mathrm{RunOk}\big(f_c, v, o_{c,v}, (\mathrm{initial}(\Sigma), \mathit{script}), l\big).RunOk(fc​,v,oc,v​,(initial(Σ),script),l).

Since annotate\mathrm{annotate}annotate is a function there is at most one such lll; if annotate(script)=none\mathrm{annotate}(\mathit{script}) = \mathsf{none}annotate(script)=none (malformed push), EvalOk\mathrm{EvalOk}EvalOk holds vacuously. No bound on ∣script∣|\mathit{script}|∣script∣ is involved (it is also required of scripts longer than 100001000010000 bytes, on which evalBytesV2\mathrm{evalBytesV2}evalBytesV2 returns none\mathsf{none}none without running).

Script verification: verifyScript\mathrm{verifyScript}verifyScript and verifyScriptV2\mathrm{verifyScriptV2}verifyScriptV2

Both are the same procedure, parameterised by an evaluator EEE: verifyScript\mathrm{verifyScript}verifyScript uses E=evalBytesE = \mathrm{evalBytes}E=evalBytes, verifyScriptV2\mathrm{verifyScriptV2}verifyScriptV2 uses E=evalBytesV2E = \mathrm{evalBytesV2}E=evalBytesV2 (also inside the witness helpers). Auxiliary notions:

  • topTrue(Σ)\mathrm{topTrue}(\Sigma)topTrue(Σ): 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 0x80\texttt{0x80}0x80 is false).
  • isP2SH(x)\mathrm{isP2SH}(x)isP2SH(x): ∣x∣=23|x| = 23∣x∣=23, x[0]=0xa9x[0] = \texttt{0xa9}x[0]=0xa9, x[1]=0x14x[1] = \texttt{0x14}x[1]=0x14, x[22]=0x87x[22] = \texttt{0x87}x[22]=0x87.
  • isWitnessProgram(x)\mathrm{isWitnessProgram}(x)isWitnessProgram(x): none\mathsf{none}none if ∣x∣<4|x| < 4∣x∣<4 or ∣x∣>42|x| > 42∣x∣>42; with b0=x[0]b_0 = x[0]b0​=x[0], none\mathsf{none}none if b0≠0b_0 \ne 0b0​=0 and b0∉[0x51,0x60]b_0 \notin [\texttt{0x51}, \texttt{0x60}]b0​∈/[0x51,0x60]; if x[1]+2=∣x∣x[1] + 2 = |x|x[1]+2=∣x∣ then some(version,drop2(x))\mathsf{some}(\text{version}, \mathrm{drop}_2(x))some(version,drop2​(x)) with version 000 if b0=0b_0 = 0b0​=0 and b0−0x50b_0 - \texttt{0x50}b0​−0x50 otherwise; else none\mathsf{none}none.
  • isPushOnly(x)\mathrm{isPushOnly}(x)isPushOnly(x): xxx parses (via getOp\mathrm{getOp}getOp) completely and every instruction is a push or an op(c)\mathrm{op}(c)op(c) with c≤0x60c \le \texttt{0x60}c≤0x60.
  • p2wpkhExec(p)=[0x76,0xa9]+ ⁣ ⁣+pushBytes(p)+ ⁣ ⁣+[0x88,0xac]\mathrm{p2wpkhExec}(p) = [\texttt{0x76}, \texttt{0xa9}] \mathbin{+\!\!+} \mathrm{pushBytes}(p) \mathbin{+\!\!+} [\texttt{0x88}, \texttt{0xac}]p2wpkhExec(p)=[0x76,0xa9]++pushBytes(p)++[0x88,0xac].
  • A Taproot handler τ\tauτ is an arbitrary function (context, list of byte strings, byte string) →\to→ boolean.
  • For a witness list w=[w1,…,wm]w = [w_1, \dots, w_m]w=[w1​,…,wm​]: last(w)=wm\mathrm{last}(w) = w_mlast(w)=wm​ (undefined, i.e. none\mathsf{none}none, when m=0m = 0m=0); w↓:=[wm−1,…,w1]w^{\downarrow} := [w_{m-1}, \dots, w_1]w↓:=[wm−1​,…,w1​] is www without its last element, reversed (so it is a top-first stack with wm−1w_{m-1}wm−1​ on top); rev(w)=[wm,…,w1]\mathrm{rev}(w) = [w_m,\dots,w_1]rev(w)=[wm​,…,w1​].
  • XE(c,Σ,ex)X_E(c, \Sigma, \mathit{ex})XE​(c,Σ,ex) (execute witness-v0 script): false if some element of Σ\SigmaΣ is longer than 520520520 bytes; otherwise false if E(c,witnessV0,Σ,ex)=noneE(c, \mathsf{witnessV0}, \Sigma, \mathit{ex}) = \mathsf{none}E(c,witnessV0,Σ,ex)=none, and if it is some(Σ′)\mathsf{some}(\Sigma')some(Σ′) the result is: ∣Σ′∣=1|\Sigma'| = 1∣Σ′∣=1 and topTrue(Σ′)\mathrm{topTrue}(\Sigma')topTrue(Σ′).
  • WE(τ,c,w,ver,p,isP2sh)W_E(\tau, c, w, \mathit{ver}, p, \mathit{isP2sh})WE​(τ,c,w,ver,p,isP2sh) (verify witness program):
    • ver=0\mathit{ver} = 0ver=0, ∣p∣=32|p| = 32∣p∣=32: false if www is empty; else with ws=last(w)\mathit{ws} = \mathrm{last}(w)ws=last(w): false if SHA256(ws)≠p\mathrm{SHA256}(\mathit{ws}) \ne pSHA256(ws)=p, else XE(c,w↓,ws)X_E(c, w^{\downarrow}, \mathit{ws})XE​(c,w↓,ws).
    • ver=0\mathit{ver} = 0ver=0, ∣p∣=20|p| = 20∣p∣=20: false if ∣w∣≠2|w| \ne 2∣w∣=2, else XE(c,rev(w),p2wpkhExec(p))X_E(c, \mathrm{rev}(w), \mathrm{p2wpkhExec}(p))XE​(c,rev(w),p2wpkhExec(p)).
    • ver=0\mathit{ver} = 0ver=0, other lengths: false.
    • ver=1\mathit{ver} = 1ver=1, ∣p∣=32|p| = 32∣p∣=32, not isP2sh\mathit{isP2sh}isP2sh: true if c.flags.taprootc.\mathrm{flags.taproot}c.flags.taproot is off, else τ(c,w,p)\tau(c, w, p)τ(c,w,p).
    • every other case: true.
  • verifyE(τ,c,scriptSig,spk,w)\mathrm{verify}_E(\tau, c, \mathit{scriptSig}, \mathit{spk}, w)verifyE​(τ,c,scriptSig,spk,w):
    1. If E(c,base,[ ],scriptSig)=noneE(c, \mathsf{base}, [\,], \mathit{scriptSig}) = \mathsf{none}E(c,base,[],scriptSig)=none: false. Else call the result Σsig\Sigma_{\mathrm{sig}}Σsig​.
    2. If E(c,base,Σsig,spk)=noneE(c, \mathsf{base}, \Sigma_{\mathrm{sig}}, \mathit{spk}) = \mathsf{none}E(c,base,Σsig​,spk)=none: false. Else call it Σ\SigmaΣ. If not topTrue(Σ)\mathrm{topTrue}(\Sigma)topTrue(Σ): false.
    3. If c.flags.witnessc.\mathrm{flags.witness}c.flags.witness and isWitnessProgram(spk)=some(ver,p)\mathrm{isWitnessProgram}(\mathit{spk}) = \mathsf{some}(\mathit{ver}, p)isWitnessProgram(spk)=some(ver,p): the result is false if scriptSig≠ε\mathit{scriptSig} \neq \varepsilonscriptSig=ε, and WE(τ,c,w,ver,p,false)W_E(\tau, c, w, \mathit{ver}, p, \mathrm{false})WE​(τ,c,w,ver,p,false) otherwise.
    4. Otherwise, if c.flags.p2shc.\mathrm{flags.p2sh}c.flags.p2sh and isP2SH(spk)\mathrm{isP2SH}(\mathit{spk})isP2SH(spk): false if not isPushOnly(scriptSig)\mathrm{isPushOnly}(\mathit{scriptSig})isPushOnly(scriptSig); false if Σsig\Sigma_{\mathrm{sig}}Σsig​ is empty; else write Σsig=[redeem]+ ⁣ ⁣+rest\Sigma_{\mathrm{sig}} = [\mathit{redeem}] \mathbin{+\!\!+} \mathit{rest}Σsig​=[redeem]++rest (top first); false if E(c,base,rest,redeem)=noneE(c, \mathsf{base}, \mathit{rest}, \mathit{redeem}) = \mathsf{none}E(c,base,rest,redeem)=none or its result Σ2\Sigma_2Σ2​ has not topTrue(Σ2)\mathrm{topTrue}(\Sigma_2)topTrue(Σ2​); then, if c.flags.witnessc.\mathrm{flags.witness}c.flags.witness: if isWitnessProgram(redeem)=some(ver,p)\mathrm{isWitnessProgram}(\mathit{redeem}) = \mathsf{some}(\mathit{ver}, p)isWitnessProgram(redeem)=some(ver,p), false if scriptSig≠pushBytes(redeem)\mathit{scriptSig} \ne \mathrm{pushBytes}(\mathit{redeem})scriptSig=pushBytes(redeem) and WE(τ,c,w,ver,p,true)W_E(\tau, c, w, \mathit{ver}, p, \mathrm{true})WE​(τ,c,w,ver,p,true) otherwise; if it is none\mathsf{none}none, false if www is non-empty and true otherwise. If c.flags.witnessc.\mathrm{flags.witness}c.flags.witness is off: true.
    5. Otherwise: false if c.flags.witnessc.\mathrm{flags.witness}c.flags.witness is on and www is non-empty; true otherwise.
Human review
  • Endorsed by Shuze Chen · Oct 30, 2026

    Confirmed by the moderator at approval.

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