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.runOk_of_static
Statement. For all interpreter flags f, every signature version v (base or witnessV0), every V2 oracle o, every list l=[(i1,r1),…,(in,rn)] of (instruction, byte string) pairs and every V2 state S: if
NoCodeSep([i1,…,in])andNoMultisig([i1,…,in]),
i.e. none of the instructions ij is op(0xab), op(0xae) or op(0xaf), then
RunOk(f,v,o,S,l).
The list l is arbitrary — it is not required to come from annotate of any byte string, and the byte strings rj are unconstrained — and the starting state S is arbitrary (any stacks, condition stack, counter and script code).
Unfolded definitions used above
Basic objects and notation
- A byte is an 8-bit word, identified with its value in {0,…,255} and written in hexadecimal (e.g. 0xab). B∗ is the set of finite byte strings (lists of bytes); ∣x∣ is the length, x++y concatenation, ε the empty string.
- takek(x) is the first min(k,∣x∣) entries of a list x; dropk(x) is what is left after removing the first k entries, which is the empty list when k≥∣x∣.
- For a 0-based index p, the statement "x[p]=c" means: p<∣x∣ and the entry of x at index p is c. Indexing out of range yields no value, so such an equation can only hold with p<∣x∣.
- A partial result is either none or some(y). Applying a function g "under some" (mapg) sends none↦none and some(y)↦some(g(y)).
- An instruction is either push(d), carrying a data string d∈B∗, or op(c), carrying an opcode byte c. A script (parsed) is a finite list of instructions.
- Opcode bytes named below: OP_16=0x60, OP_IF=0x63, OP_ENDIF=0x68, OP_CODESEPARATOR=0xab, OP_CHECKSIG=0xac, OP_CHECKSIGVERIFY=0xad, OP_CHECKMULTISIG=0xae, OP_CHECKMULTISIGVERIFY=0xaf.
- A signature version v is one of exactly two values: base (legacy) or witnessV0.
Reading one instruction from bytes: getOp
getOp(x) returns either none or some(i,y) with i an instruction and y the remaining bytes:
- x=ε: none.
- Otherwise let b be the first byte and y0 the rest.
- If b≤0x4e (a push opcode), a data length n and a position are determined: if b<0x4c, n=b and the data starts right after b; if b=0x4c, n is the next byte (none if there is none); if b=0x4d, n is the little-endian value of the next 2 bytes (none if fewer than 2 remain); if b=0x4e, n is the little-endian value of the next 4 bytes (none if fewer than 4 remain). Then, if fewer than n bytes remain, none; otherwise some(push(next n bytes), the bytes after them). (So b=0x00 gives push(ε).)
- If b>0x4e: some(op(b),y0).
On success the remainder is a suffix of x that is at least one byte shorter than x. getOp never returns op(c) with c≤0x4e.
The annotated parse: annotate
annotate(s)=annotateAux(∣s∣,s), where, with a fuel counter n:
- annotateAux(n,ε)=some([]) for every n;
- annotateAux(0,x)=none for x=ε;
- annotateAux(n+1,x) for x=ε: if getOp(x)=none then none; if getOp(x)=some(i,r) then, if annotateAux(n,r)=none the result is none, and if it is some(L) the result is some([(i,r)]++L).
So on success annotate(s)=some([(i1,r1),…,(in,rn)]), where i1 is read from s leaving r1, ij+1 is read from rj leaving rj+1, and rn=ε: each instruction is paired with the bytes that follow it in s. annotate(ε)=some([]). Since every successful getOp consumes at least one byte, the fuel ∣s∣ never runs out while input remains; hence annotate(s)=none exactly when getOp fails at some instruction boundary, i.e. on a malformed push (a truncated length field, or fewer data bytes than announced).
Signature-push deletion: pushBytes, findAndDelete, fadSig, fadAll
- pushBytes(d), the canonical push of d: if ∣d∣<0x4c it is the byte ∣d∣ followed by d; else if ∣d∣≤255 it is 0x4c, the byte ∣d∣, then d; else if ∣d∣≤65535 it is 0x4d, ∣d∣ as 2 little-endian bytes, then d; otherwise 0x4e, ∣d∣mod232 as 4 little-endian bytes, then d. It is never empty (pushBytes(ε)=[0x00]).
- findAndDelete(x,b) returns a pair (resulting string, count); only the first component (written FD(x,b)) is used here. If b=ε the result is (x,0). Otherwise x is scanned from the start: at the current instruction boundary, copies of b are removed as long as the remaining string begins with b (each removal counted); then one instruction is read with 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, 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):
fadSig(base,sc,sig)=FD(sc,pushBytes(sig)),fadSig(witnessV0,sc,sig)=sc.
- fadAll(v,sc,[σ1,…,σm]) is the left fold of fadSig(v,⋅,⋅) over the list, in list order:
fadAll(v,sc,[σ1,…,σm])=fadSig(v,⋯fadSig(v,fadSig(v,sc,σ1),σ2)⋯,σm),
and fadAll(v,sc,[])=sc.
Script numbers and multisigSigs
-
toNum(x) (the call with "minimal encoding not required" and maximum size 4): none if ∣x∣>4; otherwise some(z) with z∈Z obtained by reading x little-endian, the bit 0x80 of the last byte being a sign bit: if it is set, z is minus the little-endian value of x with that bit cleared; else z is the little-endian value of x. toNum(ε)=some(0). No minimality check is performed.
-
For an integer z, z+:=max(z,0) (negative integers convert to the natural number 0).
-
multisigSigs(Σ), for a stack Σ listed top first, is a list of byte strings:
- Σ empty: [].
- Σ=[nk]++R: if toNum(nk)=none, []. If toNum(nk)=some(NK), let R′=dropNK+(R). If R′ is empty, []. If R′=[ns]++R′′: if toNum(ns)=none, []; if toNum(ns)=some(NS), the result is takeNS+(R′′) (all of R′′ if it has fewer than NS+ elements).
No range checks are made on NK, NS (e.g. NS>NK, or negative counts, are accepted).
Oracles
- A published oracle O consists of five functions B∗→B∗ (RIPEMD-160, SHA-1, SHA-256, HASH160, HASH256), a function O.checkSig(sig,pk)∈{none,some(true),some(false)}, and two predicates checkLockTime,checkSequence:Z→{true,false}.
- A V2 oracle o 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)}. All components are arbitrary functions.
- toOracle(o): the published oracle with o's hashes and predicates and the signature check that always returns none.
- withCode(o,sc): toOracle(o) with signature check (sig,pk)↦o.checkSig(sc,sig,pk).
- withCodeSig(o,v,sc): toOracle(o) with signature check (sig,pk)↦o.checkSig(fadSig(v,sc,sig),sig,pk).
V2 states and oracleAt
- A V2 state S is a pair (S.st,S.sc) of a published interpreter state S.st (a main stack and an alt stack of byte strings listed top first, a boolean condition stack vfExec, and an operation counter) and a byte string S.sc, the script code. Write stack(S) and vfExec(S) for the main stack and condition stack of S.st.
- oracleAt(v,o,S,i), the published oracle used for instruction i from state S:
- if i=op(c) with c=0xae or c=0xaf: withCode(o, fadAll(v,S.sc,multisigSigs(stack(S))));
- for every other op(c), and for every push(d): withCodeSig(o,v,S.sc).
The published interpreter: step, run, evalScript
- Flags f are three booleans (f.cltv,f.csv,f.nulldummy).
- A published state is a tuple (main stack, alt stack, vfExec, opCount): two stacks of byte strings listed top first, a list of booleans, and a natural number. initial(Σ)=(Σ,[],[],0). allTrue(L) is true iff every entry of the boolean list L is true (in particular allTrue([]) is true).
- step(f,O,T,i), one instruction from published state T with published oracle O:
- i=push(d): none if ∣d∣>520; otherwise T′ is T with d pushed on the main stack if allTrue(T.vfExec), and T′=T otherwise; the result is none if the two stacks of T′ together hold more than 1000 elements, else some(T′). The oracle is not used.
- i=op(c): let e=allTrue(T.vfExec). If c>0x60 and T.opCount+1>201, none; otherwise the counter is incremented when c>0x60. Then: if c is one of the fifteen disabled opcodes (0x7e–0x81, 0x83–0x86, 0x8d, 0x8e, 0x95–0x99), none (whether or not executing). Else if e is true or 0x63≤c≤0x68, the result is 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 is the opcode switch (one case per opcode; any opcode not handled gives none). Its use of the oracle and the cases relevant here:
- the hash opcodes 0xa6–0xaa replace the top element by the corresponding hash function of O; 0xb1 (when f.cltv) consults O.checkLockTime and 0xb2 (when f.csv) O.checkSequence;
- 0xab (OP_CODESEPARATOR) returns the state unchanged;
- 0xac/0xad: the main stack must be [pk,sig]++R (else none); O.checkSig(sig,pk) is called; none gives none; some(b): for 0xad the stack becomes R if b, else none; for 0xac the stack becomes [[0x01]]++R if b and [ε]++R if not;
- 0xae/0xaf: the main stack must be [nk]++R; NK=toNum(nk) must exist with 0≤NK≤20; opCount+NK≤201; the next NK elements are the keys (there must be that many); then an element ns with NS=toNum(ns) existing and 0≤NS≤NK; the next NS elements are the signatures (there must be that many); then the matching loop below must not return none; then one more element (the dummy) must exist, and if f.nulldummy it must be empty; the stack becomes the elements below the dummy, with [[0x01]] or [ε] pushed for 0xae according to the loop's verdict, while for 0xaf a false verdict gives none; opCount becomes opCount+NK. Any failed requirement gives none. The matching loop on signatures and keys (both top first): no signatures left gives true; signatures left but no keys gives false; otherwise O.checkSig(current sig,current key) is called, none aborts with none; on success both advance, on failure only the key advances; whenever fewer keys than signatures remain the verdict is false.
- run(f,O,T,[i1,…,in]) applies step to i1,…,in in turn, giving none as soon as a step does; after the last instruction it returns some(final state) if the final vfExec is empty and none otherwise.
- evalScript(f,O,Σ,P)=mapmain stack(run(f,O,initial(Σ),P)): the final main stack, or none.
The V2 interpreter: stepV2, runV2, evalScriptV2
- stepV2(f,v,o,S,(i,r)), for a V2 state S and a pair of an instruction i and a byte string r:
stepV2(f,v,o,S,(i,r))=mapT↦(T, sc′)(step(f,oracleAt(v,o,S,i),S.st,i)),
where sc′=r if i=op(0xab) and allTrue(vfExec(S)) (the condition stack before the step), and 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]) applies stepV2 to x1,…,xn in turn, giving none as soon as a step does; after the last one it returns some(final V2 state) if the final vfExec is empty and none otherwise.
- evalScriptV2(f,v,o,Σ,script) for a byte string script: if annotate(script)=none the result is none; if it is some(l), the result is the main stack of runV2(f,v,o,(initial(Σ),script),l) under map (so none if that run fails). The initial script code is the whole byte string script.
Side conditions: StepOk, RunOk
-
StepOk(v,S,i) for a V2 state S and instruction i:
- i=push(d): always true.
- i=op(c): if allTrue(vfExec(S)) is true, then both (a) c=0xab, and (b) if c=0xae or c=0xaf, then for every sig in the list multisigSigs(stack(S)), fadSig(v,S.sc,sig)=S.sc.
Consequences of the definition: when allTrue(vfExec(S)) is false (inside a non-executed branch), StepOk holds for every instruction, including op(0xab). When it is true, StepOk(v,S,op(0xab)) is false. For v=witnessV0, fadSig is the identity, so clause (b) always holds. Clause (b) also holds when multisigSigs(stack(S)) is empty. No condition is placed on 0xac/0xad.
-
RunOk(f,v,o,S,l) for a list l of (instruction, bytes) pairs:
- l empty: true.
- l=[(i1,r1)]++l′: StepOk(v,S,i1) holds, and for every V2 state S′ with stepV2(f,v,o,S,(i1,r1))=some(S′), RunOk(f,v,o,S′,l′) holds.
Unwound: along the V2 run from S over l, StepOk holds at each instruction that is reached (the state before instruction j being the result of the j−1 preceding successful steps), including the instruction whose step fails; once a step returns none, nothing is required of the later instructions. The final empty-vfExec check of runV2 plays no role. RunOk depends on f and o only through which states the steps reach.
Static conditions: NoCodeSep, NoMultisig
For a parsed script P (a list of instructions): NoCodeSep(P) means op(0xab) does not occur in P; NoMultisig(P) means neither op(0xae) nor op(0xaf) occurs in P. (Occurrences anywhere count, including inside branches that would not be executed.)
Confirmed by the moderator at approval.