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.eval_agree
Statement. Let f be interpreter flags, v a signature version (base or witnessV0), o an arbitrary V2 oracle, Σ an initial stack (list of byte strings, top first), script a byte string and l a list of (instruction, byte string) pairs. Assume
- annotate(script)=some(l);
- RunOk(f,v,o,(initial(Σ),script),l).
Then
evalScriptV2(f,v,o,Σ,script)=evalScript(f, withCodeSig(o,v,script), Σ, π1(l)),
where π1(l) is the list of instructions of l (first components, in order). The right side is the published interpreter run on those instructions with a published oracle whose signature check is (sig,pk)↦o.checkSig(fadSig(v,script,sig),sig,pk) — the whole byte string script as script code, with (for base) only the checked signature's push deleted — for every instruction, multisig included. The equality is of partial results (both none or both some of the same final main stack).
Hypothesis 2 unfolds to: along the V2 run with oracle o from the V2 state (initial(Σ),script) over l, at each reached instruction that is executed (allTrue of the current condition stack), the instruction is not op(0xab), and if it is op(0xae) or op(0xaf) then every string sig in multisigSigs of the current main stack satisfies fadSig(v,current script code,sig)=current script code; nothing is required after the first failing step.
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.
Confirmed by the moderator at approval.