Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Outside the two limits the V2 byte-level evaluator is the published one

Proved
BitcoinScriptV2.evalBytes_agree

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

bitcoinbitcoin-mainnetcheckmultisigcodeseparatorconsensusfindanddeleteformal-verificationinterpreterscriptsighash

Under EvalOk c v stack script: evalBytesV2 c v stack script = evalBytes c v stack script.

Preamble
import Definitions.Def_BitcoinScriptV2
import Definitions.Def_BitcoinVerify
import Definitions.Def_BitcoinSig
import Definitions.Def_BitcoinScript
open BitcoinScriptV2 BitcoinScript BitcoinSig BitcoinVerify
Formal statement
theorem BitcoinScriptV2.evalBytes_agree (c : BitcoinVerify.Ctx) (v : BitcoinSig.SigVersion)
    (stack : List BitcoinScript.Bytes) (script : BitcoinScript.Bytes) (h : BitcoinScriptV2.EvalOk c v stack script) :
    BitcoinScriptV2.evalBytesV2 c v stack script = BitcoinVerify.evalBytes c v stack script := by sorry
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: BitcoinScriptV2.evalBytes_agree

Statement. For every verification context ccc, every signature version vvv (base\mathsf{base}base or witnessV0\mathsf{witnessV0}witnessV0), every initial stack Σ\SigmaΣ (a list of byte strings, top first) and every byte string script\mathit{script}script: if

EvalOk(c,v,Σ,script)\mathrm{EvalOk}(c, v, \Sigma, \mathit{script})EvalOk(c,v,Σ,script)

holds, then

evalBytesV2(c,v,Σ,script)=evalBytes(c,v,Σ,script)\mathrm{evalBytesV2}(c, v, \Sigma, \mathit{script}) = \mathrm{evalBytes}(c, v, \Sigma, \mathit{script})evalBytesV2(c,v,Σ,script)=evalBytes(c,v,Σ,script)

as partial results (both none\mathsf{none}none, or both some\mathsf{some}some of the same final main stack).

Unfolded: the left side is none\mathsf{none}none if ∣script∣>10000|\mathit{script}| > 10000∣script∣>10000, else the V2 run of the annotated parse of script\mathit{script}script from (initial(Σ),script)(\mathrm{initial}(\Sigma), \mathit{script})(initial(Σ),script) with the oracle oc,vo_{c,v}oc,v​ (script code tracked through executed OP_CODESEPARATOR\texttt{OP\_CODESEPARATOR}OP_CODESEPARATORs; all signature pushes deleted for multisig in base\mathsf{base}base). The right side is none\mathsf{none}none if ∣script∣>10000|\mathit{script}| > 10000∣script∣>10000, else the published run of the plain parse with legacyOracle(…,script)\mathrm{legacyOracle}(\dots, \mathit{script})legacyOracle(…,script) (script code always the whole script\mathit{script}script, only the checked signature's push deleted in base\mathsf{base}base). The hypothesis EvalOk\mathrm{EvalOk}EvalOk requires, along the V2 run with oracle oc,vo_{c,v}oc,v​ from (initial(Σ),script)(\mathrm{initial}(\Sigma), \mathit{script})(initial(Σ),script) over the annotated parse, that no reached executed instruction is OP_CODESEPARATOR\texttt{OP\_CODESEPARATOR}OP_CODESEPARATOR and that at every reached executed OP_CHECKMULTISIG(VERIFY)\texttt{OP\_CHECKMULTISIG(VERIFY)}OP_CHECKMULTISIG(VERIFY) each string of multisigSigs\mathrm{multisigSigs}multisigSigs of the current stack has fadSig(v,current script code,⋅)\mathrm{fadSig}(v, \text{current script code}, \cdot)fadSig(v,current script code,⋅) equal to the current script code. It holds vacuously when annotate(script)=none\mathrm{annotate}(\mathit{script}) = \mathsf{none}annotate(script)=none, and is required even for ∣script∣>10000|\mathit{script}| > 10000∣script∣>10000.


Unfolded definitions used above

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.

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).

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