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.received_spends_iff
Statement. Let f be any flag set, o any oracle, r,Kr,Kl,h any four byte strings with ∣r∣≤520, ∣Kr∣≤520, ∣Kl∣≤520, ∣h∣≤520, e any integer with ∣e∣<232, and st any list of byte strings (an initial stack, top first, of any length including zero, elements of any size). The theorem asserts
(∃res, evalf,o(st,Rec(r,Kr,Kl,h,e))=someres ∧ ∣res∣=1 ∧ topTrue(res)=true)⟺ReceivedSpend(f,o,r,Kr,Kl,h,e,st),
where the left side says that the interpreter run with flags f and oracle o on st and the received script does not fail, leaves exactly one element, and that element is castToBool-true (topTrue is false on an empty stack and castToBool of the top otherwise), and the right side is the three-way disjunction unfolded below.
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 set f consists of three Booleans f.cltv, f.csv, f.nulldummy. An oracle o 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 script Off(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
OP_DUP OP_HASH160 ⟨r⟩ OP_EQUAL OP_IF OP_CHECKSIG OP_ELSE ⟨Kr⟩ OP_SWAP OP_SIZE ⟨[0x20]⟩ OP_EQUALOP_NOTIF OP_DROP OP_2 OP_SWAP ⟨Kl⟩ OP_2 OP_CHECKMULTISIG OP_ELSE OP_HASH160 ⟨h⟩ OP_EQUALVERIFY OP_CHECKSIG OP_ENDIF OP_ENDIF,
where ⟨[0x20]⟩ is numInstr(32) and OP_2 is numInstr(2), the opcode byte 0x52. The received script Rec(r,Kr,Kl,h,e) additionally takes an integer e (the "expiry", any integer, possibly negative or zero) and is the 28-instruction list
OP_DUP OP_HASH160 ⟨r⟩ OP_EQUAL OP_IF OP_CHECKSIG OP_ELSE ⟨Kr⟩ OP_SWAP OP_SIZE ⟨[0x20]⟩ OP_EQUALOP_IF OP_HASH160 ⟨h⟩ OP_EQUALVERIFY OP_2 OP_SWAP ⟨Kl⟩ OP_2 OP_CHECKMULTISIGOP_ELSE OP_DROP numInstr(e) OP_CHECKLOCKTIMEVERIFY OP_DROP OP_CHECKSIG OP_ENDIF OP_ENDIF,
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.
The lock-time predicate. CltvPasses(f,o,e), for a flag set f, an oracle o and an integer e, is the proposition
f.cltv=false ∨ (0≤e ∧ o.checkLockTime(e)=true),
so it holds unconditionally when the cltv flag is off, and otherwise requires e non-negative and the oracle's lock-time check to accept e.
The spend predicates. OfferedSpend(f,o,r,Kr,Kl,h,st), for a flag set f, an oracle o, byte strings r,Kr,Kl,h and a list of byte strings st (a stack, top first), is the disjunction of the following three propositions:
- (revocation form) there exist byte strings pk,sig with st=[pk,sig], o.hash160(pk)=r and o.checkSig(sig,pk)=sometrue;
- (preimage form) there exist byte strings pre,sig with st=[pre,sig], o.hash160(pre)=r, ∣pre∣=32, o.hash160(pre)=h and o.checkSig(sig,Kr)=sometrue;
- (timeout form) there exist byte strings x,σl,σr,d with st=[x,σl,σr,d], o.hash160(x)=r, ∣x∣=32, msLoopo([σl,σr],[Kl,Kr])=sometrue, and (f.nulldummy=true implies d=[]).
In particular the predicate is false whenever st has a length other than 2 or 4 (e.g. the empty stack), and no size bound is placed on pk,sig,pre,x,σl,σr,d by the predicate itself. ReceivedSpend(f,o,r,Kr,Kl,h,e,st), with additionally an integer e, is the disjunction of:
- (revocation form) there exist pk,sig with st=[pk,sig], o.hash160(pk)=r and o.checkSig(sig,pk)=sometrue;
- (success form) there exist pre,σl,σr,d with st=[pre,σl,σr,d], o.hash160(pre)=r, ∣pre∣=32, o.hash160(pre)=h, msLoopo([σl,σr],[Kl,Kr])=sometrue, and (f.nulldummy=true implies d=[]);
- (timeout form) there exist x,sig with st=[x,sig], o.hash160(x)=r, ∣x∣=32, CltvPasses(f,o,e) and o.checkSig(sig,Kr)=sometrue.
Confirmed by the moderator at approval.