For keys of at most 520 bytes: evalScript f o [sig2, sig1, dummy] (fundingScript pubkey1 pubkey2) is the 2-of-2 loop's verdict multisigLoop o [sig2, sig1] [pubkey2, pubkey1] as a single stack element, none if the loop errors or if NULLDUMMY is on and the dummy is nonempty.
Preamble
import Definitions.Def_BitcoinFunding
import Definitions.Def_BitcoinScript
open BitcoinFunding BitcoinHtlc
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinFunding.funding_witness (f : Flags) (o : Oracle) (pubkey1 pubkey2 sig1 sig2 dummy : Bytes)
(h1 : pubkey1.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (h2 : pubkey2.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) :
BitcoinScript.evalScript f o [sig2, sig1, dummy] (BitcoinFunding.fundingScript pubkey1 pubkey2) =
match BitcoinScript.multisigLoop o [sig2, sig1] [pubkey2, pubkey1] with
| none => none
| some ok => if f.nulldummy && !dummy.isEmpty then none else some [BitcoinScript.boolBytes ok] := 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: BitcoinFunding.funding_witness
A byte is an 8-bit word; a byte string (Bytes) is a finite list of bytes; a stack is a finite list of byte strings whose first entry is the top.
Statement
The theorem quantifies over:
a flag record f with exactly three boolean fields f.cltv, f.csv, f.nulldummy;
an oracleo: a record of abstract functions o.ripemd160,o.sha1,o.sha256,o.hash160,o.hash256:Bytes→Bytes; o.checkSig:Bytes×Bytes→Option(Bool) (first argument "signature", second "public key"; value none, sometrue or somefalse); o.checkLockTime,o.checkSequence:Z→Bool. Nothing is assumed about any of these functions;
five byte strings k1,k2,s1,s2,d (pubkey1, pubkey2, sig1, sig2, dummy), unconstrained in content;
and assumes the two hypotheses ∣k1∣≤520 and ∣k2∣≤520 (520 = MAX_SCRIPT_ELEMENT_SIZE). No bound is placed on ∣s1∣, ∣s2∣ or ∣d∣.
Under these, the theorem asserts an equality of two values in Option(stack):
evalScript(f,o,[s2,s1,d],fundingScript(k1,k2))=⎩⎨⎧nonenonesome[boolBytes(ok)]if multisigLoop(o,[s2,s1],[k2,k1])=none,if multisigLoop(o,[s2,s1],[k2,k1])=some(ok) and f.nulldummy=true and d=[],if multisigLoop(o,[s2,s1],[k2,k1])=some(ok) otherwise,
where boolBytes(true)=[0x01] and boolBytes(false)=[] (the empty byte string). The initial stack on the left has s2 on top, s1 beneath it, and d at the bottom. On the right, the result stack (when not none) has exactly one element, either [0x01] or [].
where op(0x52) is numInstr(2) (for n=−1 or 1≤n≤16, numInstr(n)=op(n+0x50); otherwise a push of the script-number encoding of n) and 0xae is OP_CHECKMULTISIG.
The right-hand side: multisigLoop
multisigLoop(o,sigs,keys), with both lists top-first, is defined by:
sigs=[]: sometrue (whatever keys is).
sigs=[] and keys=[]: somefalse.
sigs=s::sigs′ and keys=k::keys′: compute o.checkSig(s,k):
none⇒ result none;
sometrue⇒ if ∣keys′∣<∣sigs′∣ then somefalse, else multisigLoop(o,sigs′,keys′) (both the signature and the key are consumed);
somefalse⇒ if ∣keys′∣<∣sigs∣ then somefalse, else multisigLoop(o,sigs,keys′) (only the key is consumed; the same signature is retried against the next key).
Applied to sigs=[s2,s1] and keys=[k2,k1], the definition unrolls as follows. First o.checkSig(s2,k2) is evaluated:
if none: the loop returns none;
if somefalse: the remaining keys [k1] number 1<2=∣[s2,s1]∣, so the loop returns somefalse — s2 is not retried against k1, and s1 is never examined;
if sometrue: since ∣[k1]∣=1<1=∣[s1]∣, the loop continues with ([s1],[k1]) and evaluates o.checkSig(s1,k1): none⇒none; somefalse⇒ (0<1) somefalse; sometrue⇒ (0<0) continue with ([],[]), which is sometrue.
So the loop is sometrue iff o.checkSig(s2,k2)=sometrue and o.checkSig(s1,k1)=sometrue; it is none iff o.checkSig(s2,k2)=none, or o.checkSig(s2,k2)=sometrue and o.checkSig(s1,k1)=none; and somefalse in the remaining cases. The pairing is: the top signature s2 with the top key k2; the second signature s1 with the second key k1. The order of evaluation is s2 against k2 first.
The outer match on the right-hand side then returns none when the loop is none; otherwise, with the loop's boolean ok, it returns none if f.nulldummy is true andd is non-empty, and some[boolBytes(ok)] otherwise. When f.nulldummy is false, d is never inspected on the right-hand side; when it is true, a non-empty d yields none even if ok=false.
The left-hand side: the interpreter evalScript
evalScript(f,o,st0,S) is none (failure) or some(st) for a stack st. The machine state is a tuple (main stack, alternate stack, condition stack vfExec — a list of booleans — , opcode counter), initially (st0,[],[],0). The instructions of S are run in order by the one-step rule below; any failure makes the whole result none. After the last instruction, the run fails if vfExec is non-empty; otherwise the result is some of the final main stack (the alternate stack and counter are discarded).
One step:
push(x): fail if ∣x∣>520. Otherwise, if every entry of vfExec is true (vacuously true when vfExec is empty), x is placed on top of the main stack; else the state is unchanged. Then fail if ∣main∣+∣alt∣>1000.
op(c): the opcode is counted iff c>0x60. If counted and counter+1>201: fail; else if counted, the counter is incremented. Fail if c is one of the fifteen disabled opcodes (0x7e–0x81, 0x83–0x86, 0x8d, 0x8e, 0x95–0x99). Then, if every entry of vfExec is true or 0x63≤c≤0x68: apply the one-opcode executor execOp (fail if it fails), then fail if ∣main∣+∣alt∣>1000; otherwise skip the opcode (same size check).
The one-opcode executor on the two opcodes occurring in the funding script (its branches for other opcodes are not reproduced):
c=0x52 (branch for c=0x4f or 0x51≤c≤0x60; not counted): push serialize(c−0x50) onto the main stack, where serialize(n) is [] for n=0, and otherwise the little-endian bytes of ∣n∣ without trailing zero bytes, followed by an extra byte 0x80 (if n<0) or 0x00 (if n>0) when the top bit of the last magnitude byte is set, or else with the top bit of the last byte set when n<0. For 0x52 this pushes [0x02].
c=0xae (OP_CHECKMULTISIG; counted). With main stack st and the already-incremented counter κ:
Fail if st=[]. Else st=nk::r.
Nk:=toNum(nk): fail if ∣nk∣>4; otherwise Nk is the signed little-endian value of nk (sign bit = top bit of the last byte; magnitude = little-endian value with that bit cleared; the empty string is 0). Fail if Nk<0 or Nk>20.
κ′:=κ+Nk; fail if κ′>201.
keys:= the first Nk entries of r, r:= the rest; fail if fewer than Nk entries were available.
Fail if r=[]; else r=ns::r. Ns:=toNum(ns) (fail if ∣ns∣>4); fail if Ns<0 or Ns>Nk.
sigs:= the first Ns entries of r, r:= the rest; fail if fewer than Ns were available.
Compute multisigLoop(o,sigs,keys) (defined above): fail if none; else let ok be its boolean.
Fail if r=[]; else r=d′::r′. Fail if f.nulldummy=true and d′=[].
New main stack boolBytes(ok)::r′, counter κ′.
The left-hand side of the theorem is this interpreter run on the initial main stack [s2,s1,d] over the five instructions op(0x52),push(k1),push(k2),op(0x52),op(0xae), with the flags f and the oracle o. Note that the interpreter imposes the 520-byte bound only on pushed data (here k1,k2, which the hypotheses already bound) and not on the elements s2,s1,d of the initial stack; that only f.nulldummy among the flags is consulted by these opcodes; and that only o.checkSig among the oracle's fields is consulted by them.
Confirmed by the moderator at approval.