For pushed strings of at most 520 bytes, hash160 x ≠ revHash and x not 32 bytes: on [x, localSig, remoteSig, dummy] the script fails if the 2-of-2 loop errors, fails if NULLDUMMY is on and the dummy is nonempty, and otherwise leaves the loop's verdict.
Preamble
import Definitions.Def_BitcoinHtlc
import Definitions.Def_BitcoinScript
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinHtlc.offered_timeout (f : Flags) (o : Oracle) (revHash remoteKey localKey payHash x localSig remoteSig dummy : Bytes)
(hrev : revHash.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (hrem : remoteKey.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
(hloc : localKey.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (hpay : payHash.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
(hb : o.hash160 x ≠ revHash) (h32 : x.length ≠ 32) :
BitcoinScript.evalScript f o [x, localSig, remoteSig, dummy] (BitcoinHtlc.offeredScript revHash remoteKey localKey payHash) =
match BitcoinScript.multisigLoop o [localSig, remoteSig] [localKey, remoteKey] 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: BitcoinHtlc.offered_timeout
Statement. Let f be any flag set, o any oracle, and r,Kr,Kl,h,x,σl,σr,d any eight byte strings, under the hypotheses ∣r∣≤520, ∣Kr∣≤520, ∣Kl∣≤520, ∣h∣≤520 (bounding only the four script parameters; x,σl,σr,d are unbounded), o.hash160(x)=r and ∣x∣=32. The theorem asserts
evalf,o([x,σl,σr,d],Off(r,Kr,Kl,h))=⎩⎨⎧nonenonesome[boolBytes(ok)]if msLoopo([σl,σr],[Kl,Kr])=none,if msLoopo([σl,σr],[Kl,Kr])=someok and f.nulldummy=true and d=[],if msLoopo([σl,σr],[Kl,Kr])=someok and not (f.nulldummy=true and d=[]),
i.e. the interpreter run on the four-element initial stack [x,σl,σr,d] (x on top, d at the bottom) and the offered script equals the following: compute the multisignature loop on signatures [σl,σr] against keys [Kl,Kr]; if it is none the result is none; if it is someok the result is none when the Boolean f.nulldummy&&¬(d is empty) is true, and otherwise the one-element stack [boolBytes(ok)], which is [[0x01]] for ok=true and [[]] for ok=false (a non-failing run whose single element is the empty string). Note that ok=false is a successful run with a false result, distinct from none.
Definitions unfolded
Basic notions used throughout. A byte is an 8-bit word and a byte string (written Bytes) is a finite list of bytes; ∣b∣ denotes the length of a byte string b. The constant Lmax=520 is the interpreter's maximum size of one stack element. A flag setf consists of three Booleans f.cltv, f.csv, f.nulldummy. An oracleo is an arbitrary structure supplying eight functions with no constraints whatsoever on their behaviour: o.ripemd160,o.sha1,o.sha256,o.hash160,o.hash256:Bytes→Bytes (so in particular o.hash160 is any function from byte strings to byte strings, not necessarily RIPEMD160∘SHA256, not necessarily 20-byte-valued), o.checkSig:Bytes→Bytes→OptionBool (first argument the signature, second the public key; the value none represents a script-aborting failure, someb a verdict b), o.checkLockTime:Z→Bool and o.checkSequence:Z→Bool. Stacks are lists written top element first. castToBool(b) is: false for the empty string; for a one-byte string [x], true iff x=0 and x=0x80; for x::r with r non-empty, true iff x=0 or castToBool(r) (so a string of zero bytes whose last byte is 0x80 is false). boolBytes(true)=[0x01] and boolBytes(false)=[] (the empty string). The script-number encoding ser(v) of an integer v is: [] if v=0; otherwise the little-endian bytes of ∣v∣ with no trailing zero byte, then, if the last of those bytes has its top bit (0x80) set, an extra byte 0x80 (for v<0) or 0x00 (for v>0) is appended, and otherwise, for v<0, the top bit of the last byte is set. For example ser(2)=[0x02] and ser(32)=[0x20]. The decoding numk(b) ("script number of at most k bytes, non-minimal encodings allowed") is none if ∣b∣>k, and otherwise some of the little-endian value of b with the top bit of the last byte read as a sign (the empty string decodes to 0).
The number push numInstr(n) / numBytes(n). For an integer n, numInstr(n) is the single opcode with byte value n+0x50 when n=−1 or 1≤n≤16 (so numInstr(−1) is the opcode 0x4f, numInstr(2) is the opcode 0x52, i.e. OP_2), and otherwise it is the data push of ser(n) (so numInstr(32) is the push of the one-byte string [0x20], and numInstr(0) is the push of the empty string). numBytes(n) is the byte-level form: the one opcode byte n+0x50 in the first case, and pushBytes(ser(n)) otherwise, where pushBytes(d) is the canonical push encoding of a byte string d: [∣d∣]++d if ∣d∣<0x4c; [0x4c,∣d∣]++d if ∣d∣≤0xff; [0x4d]++(2 little-endian bytes of ∣d∣)++d if ∣d∣≤0xffff; and [0x4e]++(4 little-endian bytes of ∣d∣)++d otherwise.
The two witness scripts as instruction lists. Writing ⟨d⟩ for the data push of the byte string d, the offered scriptOff(r,Kr,Kl,h), for byte strings r (the "revocation hash"), Kr (the "remote key"), Kl (the "local key") and h (the "payment hash"), all four being completely unconstrained parameters (any byte strings, not necessarily 20 bytes, not necessarily hashes of anything), is the 26-instruction list
where ⟨[0x20]⟩ is numInstr(32) and OP_2 is numInstr(2), the opcode byte 0x52. The received scriptRec(r,Kr,Kl,h,e) additionally takes an integer e (the "expiry", any integer, possibly negative or zero) and is the 28-instruction list
where numInstr(e) is the opcode e+0x50 if e=−1 or 1≤e≤16, and the data push of ser(e) otherwise (the empty push when e=0; a push carrying a sign bit when e<−1).
The interpreter evalf,o(st,script). This is the transcription of Bitcoin Core's legacy EvalScript: starting from the state (main stack st, empty alt stack, empty condition stack, operation count 0), it processes the instructions of script in order and returns none ("script failure") or some of the final main stack. One instruction is processed as follows. A data push of d fails if ∣d∣>520; otherwise d is pushed onto the main stack when every entry of the condition stack is true (otherwise the state is unchanged), and the step fails if the main and alt stacks then hold more than 1000 elements together. An opcode c is "counted" when c>0x60 (OP_16); a counted opcode fails if the count already equals 201, and otherwise increments the count; any of the fifteen disabled opcodes (OP_CAT, OP_SUBSTR, OP_LEFT, OP_RIGHT, OP_INVERT, OP_AND, OP_OR, OP_XOR, OP_2MUL, OP_2DIV, OP_MUL, OP_DIV, OP_MOD, OP_LSHIFT, OP_RSHIFT) fails even when not executed; then, if every entry of the condition stack is true ("executing") or c is one of OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF (any byte from 0x63 to 0x68 inclusive, which also includes the bytes 0x65 and 0x66, for which execution fails), the opcode is executed and the 1000-element stack bound re-checked; an unexecuted opcode leaves the state alone. After the last instruction the run fails if the condition stack is non-empty. The executed opcodes relevant here behave as follows (with "fail" meaning none): OP_1…OP_16 push ser(c−0x50) (so OP_2 pushes [0x02]; these are not counted); OP_DUP fails on an empty stack and otherwise duplicates the top; OP_DROP fails on an empty stack and otherwise removes the top; OP_SWAP fails with fewer than two elements and otherwise exchanges the top two; OP_SIZE fails on an empty stack and otherwise pushes ser(∣top∣) above the unchanged top; OP_HASH160 fails on an empty stack and otherwise replaces the top t by o.hash160(t); OP_EQUAL fails with fewer than two elements and otherwise pops the top two a (top) and b and pushes boolBytes(b=a) (byte-string equality), while OP_EQUALVERIFY pops them and fails unless b=a; OP_IF (resp. OP_NOTIF), when executing, fails on an empty stack and otherwise pops the top t and pushes castToBool(t) (resp. its negation) onto the condition stack, and when not executing pushes false onto the condition stack without touching the main stack; OP_ELSE fails on an empty condition stack and otherwise negates its top; OP_ENDIF fails on an empty condition stack and otherwise pops it; OP_CHECKSIG fails with fewer than two elements and otherwise pops pk (top) and sig, fails if o.checkSig(sig,pk)=none, and pushes boolBytes(b) if it is someb; OP_CHECKLOCKTIMEVERIFY is a no-op if f.cltv is false, and otherwise fails on an empty stack, decodes the top as num5 (failing if it has more than 5 bytes), fails if the value n is negative or o.checkLockTime(n) is false, and otherwise leaves the state unchanged (the operand stays on the stack); OP_CHECKMULTISIG fails on an empty stack and otherwise pops nk decoded as num4 (failing if undecodable, negative or >20), adds the value to the operation count (failing if that exceeds 201), takes exactly that many keys from the stack (failing if too few), pops ns decoded as num4 (failing if undecodable, negative or >nk), takes exactly that many signatures (failing if too few), computes msLoopo(sigs,keys) (failing if it is none), then pops one more element dummy (failing if the stack is empty), fails if f.nulldummy is true and dummy is non-empty, and finally pushes boolBytes of the loop's verdict.
The multisignature matching loop.msLoopo(sigs,keys), for lists of signatures and keys (top first), is defined by recursion: it is sometrue when sigs is empty; somefalse when sigs is non-empty and keys is empty; and for sigs=s::S, keys=k::K it evaluates o.checkSig(s,k): if that is none the loop is none; if it is sometrue the loop is somefalse when ∣K∣<∣S∣ and otherwise msLoopo(S,K); if it is somefalse the loop is somefalse when ∣K∣<∣S∣+1 and otherwise msLoopo(s::S,K). Unfolded on exactly two signatures and two keys, msLoopo([s1,s2],[k1,k2]) is: none if o.checkSig(s1,k1)=none; somefalse if o.checkSig(s1,k1)=somefalse (since 1<2; the second signature is then never checked); and if o.checkSig(s1,k1)=sometrue it is none, sometrue or somefalse according as o.checkSig(s2,k2) is none, sometrue or somefalse.
Confirmed by the moderator at approval.