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.checksig_deletes_one
Statement. For every signature version v (base or witnessV0), every V2 oracle o, every V2 state S, every byte c with
c=0xac (OP_CHECKSIG)orc=0xad (OP_CHECKSIGVERIFY),
and all byte strings sig,pk:
oracleAt(v,o,S,op(c)).checkSig(sig,pk)=o.checkSig(fadSig(v,S.sc,sig), sig, pk).
In words: the published-oracle signature check that the V2 interpreter supplies for OP_CHECKSIG/OP_CHECKSIGVERIFY at state S, applied to (sig,pk), equals the V2 oracle's check on the script code obtained from the state's current script code S.sc by deleting the canonical push of sig (for v=base), or on S.sc itself (for v=witnessV0). The equation is about the oracle only; it involves neither the stack contents nor whether the opcode is executed (vfExec), and sig,pk are arbitrary (not required to be the stack elements). Only the checkSig component of the oracle is compared.
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.
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).
Confirmed by the moderator at approval.