For keys of at most 520 bytes, ∣delay∣<232 and tl.length + 1 ≤ 1000: evalScript f o (b :: tl) (toLocalScript rev delay dpk) is none when tl is empty, and for tl = sig :: rest it is (o.checkSig sig rev).map (fun ok => boolBytes ok :: rest) when castToBool b, else (o.checkSig sig dpk).map (…) when CsvPasses f o delay, else none. The whole interpreter run, instruction by instruction, with the skipped branch's pushes and opcodes accounted for.
Preamble
import Definitions.Def_BitcoinToLocal
import Definitions.Def_BitcoinScript
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinToLocal.eval_cons (f : Flags) (o : Oracle) (rev dpk b : Bytes) (delay : Int) (tl : List Bytes)
(hrev : rev.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (hdpk : dpk.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
(hd : delay.natAbs < 2 ^ 32) (htl : tl.length + 1 ≤ BitcoinScript.MAX_STACK_SIZE) :
BitcoinScript.evalScript f o (b :: tl) (BitcoinToLocal.toLocalScript rev delay dpk) =
match tl with
| [] => none
| sig :: rest =>
if BitcoinScript.castToBool b then (o.checkSig sig rev).map (fun ok => BitcoinScript.boolBytes ok :: rest)
else if BitcoinToLocal.CsvPasses f o delay then (o.checkSig sig dpk).map (fun ok => BitcoinScript.boolBytes ok :: rest)
else none := by sorry
What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: BitcoinToLocal.eval_cons
Statement. Let f be a script flag record (booleans f.cltv,f.csv,f.nulldummy), o an oracle (a record of five arbitrary hash functions on byte strings, an arbitrary o.checkSig:bytes×bytes→OptionBool taking the signature first and the key second, and arbitrary o.checkLockTime,o.checkSequence:Z→Bool; nothing is assumed about them), R (rev), D (dpk) and b byte strings, δ∈Z (delay), and tl a list of byte strings. Assume
∣R∣≤520,∣D∣≤520,∣δ∣<232,∣tl∣+1≤1000.
(520 and 1000 are the preamble's MAX_SCRIPT_ELEMENT_SIZE and MAX_STACK_SIZE; ∣δ∣ is the absolute value as a natural.) Then the result of evaluating the to_local script on the initial stack b::tl (top-first, so b is on top) is
evalScript(f,o,b::tl,toLocalScript(R,δ,D))=⎩⎨⎧nonemap(ok↦boolBytes(ok)::rest)(o.checkSig(sig,R))map(ok↦boolBytes(ok)::rest)(o.checkSig(sig,D))noneif tl=[],if tl=sig::rest and castToBool(b)=true,if tl=sig::rest,castToBool(b)=false,and CsvPasses(f,o,δ),if tl=sig::rest,castToBool(b)=false,and not CsvPasses(f,o,δ).
Here "map(g)" applied to an optional value sends none to none and someok to some(g(ok)); so in the second and third cases the result is none when the oracle's signature check returns none, and otherwise the stack boolBytes(ok)::rest, where boolBytes(true)=[0x01] and boolBytes(false)=[]. Note that rest (everything below the second element) is preserved untouched, and the result is some of a stack of length ∣rest∣+1=∣tl∣ in the successful cases. Note also that no hypothesis bounds ∣b∣ or the lengths of the elements of tl; only the count ∣tl∣+1≤1000 of initial stack elements is assumed.
Unfolded notions.
castToBool(x): false for x=[]; for x=[y], true iff y=0 and y=0x80; for x=y::rest with rest=[], true iff y=0 or castToBool(rest).
CsvPasses(f,o,δ) is f.csv=false∨(0≤δ∧((toNat(δ)&231)=0∨o.checkSequence(δ)=true)), with toNat truncating negatives to 0 and & bitwise AND on naturals.
toLocalScript(R,δ,D) is the nine-instruction list [op0x63,pushR,op0x67,numInstr(δ),op0xb2,op0x75,pushD,op0x68,op0xac], where numInstr(δ) is the opcode with byte δ+80 if δ=−1 or 1≤δ≤16 (bytes 0x4f, 0x51–0x60), and otherwise the data push of serialize(δ) (serialize(0)=[]; for δ=0, the little-endian magnitude bytes of ∣δ∣ without trailing zeros, with an appended 0x80 or 0x00 byte when the top bit of the last byte is set, otherwise the top bit set on the last byte when δ<0).
The interpreter evalScript.evalScript(f,o,S,P) starts from the state (main stack =S, alt-stack =[], condition stack vfExec=[], opCount=0), applies one step per instruction of P in order, and, if every step succeeds and the condition stack is empty at the end, returns some of the final main stack; any step failure, or a non-empty condition stack at the end, gives none. A step is:
Push of data x. Fail if ∣x∣>520. Otherwise, if every entry of vfExec is true, place x on top of the main stack; if some entry is false, leave the state unchanged. Then fail if ∣stack∣+∣alt-stack∣>1000.
Opcode c. Let e be "every entry of vfExec is true". If c>0x60, the opcode is counted: fail if opCount+1>201, else increment opCount. Fail if c is one of the fifteen disabled opcodes (0x7e–0x81, 0x83–0x86, 0x8d, 0x8e, 0x95–0x99; none occur here). If e holds or 0x63≤c≤0x68, apply execOp below with flag e, then fail if ∣stack∣+∣alt-stack∣>1000. Otherwise leave the state unchanged apart from that same size check.
execOp for the opcodes that can occur in this script:
0x4f, 0x51–0x60 (the opcode form of numInstr(δ)): push serialize(c−80) onto the main stack.
0x63 (OP_IF): if e is true, fail on an empty main stack, else pop the top x and push castToBool(x) onto vfExec; if e is false, push false onto vfExec without touching the main stack.
0x67 (OP_ELSE): fail if vfExec is empty, else negate its head.
0x68 (OP_ENDIF): fail if vfExec is empty, else remove its head.
0xb2 (OP_CHECKSEQUENCEVERIFY): if f.csv=false, unchanged. Else fail on an empty main stack; let x be the top (not removed); fail if ∣x∣>5; let n be the signed little-endian value of x (top bit of the last byte is the sign; the empty string is 0); fail if n<0; if (toNat(n)&231)=0, unchanged; else fail if o.checkSequence(n)=false; else unchanged.
0x75 (OP_DROP): fail on an empty main stack, else remove the top.
0xac (OP_CHECKSIG): the main stack must have the form pk::sg::rest (pk on top), else fail; then o.checkSig(sg,pk): none gives failure, someok replaces the two elements by boolBytes(ok), giving boolBytes(ok)::rest.
The theorem thus equates the outcome of this nine-step run on b::tl with the four-case expression displayed above.
Confirmed by the moderator at approval.