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_p2wsh_spend
Statement. Let tap be any Taproot handler (any function from a context, a list of byte strings and a byte string to a Boolean), c any verification context (a consensus flag set c.flags, a transaction c.tx, an input index c.nIn and an amount c.amount∈Z) with the hypothesis c.flags.witness=true, r,Kr,Kl,h any four byte strings with ∣r∣≤520, ∣Kr∣≤520, ∣Kl∣≤520, ∣h∣≤520, and ws any list of byte strings (possibly empty; its elements are not bounded by any hypothesis). Write B=OffB(r,Kr,Kl,h) for the serialized offered script and H=SHA256(B) for its concrete SHA-256 digest (32 bytes). The theorem asserts
verifyScript(tap, c, [], witnessBytes(0,H), ws++[B])=true⟺castToBool(H)=true ∧ (∀x∈ws, ∣x∣≤520) ∧ OfferedSpend(F,OB,r,Kr,Kl,h,reverse(ws)),
where: the scriptSig is the empty byte string; the scriptPubKey is witnessBytes(0,H)=[0x00,0x20]++H; the witness list is ws followed by the script bytes B as last element (so the witness is never empty, and when ws=[] it is just [B]); F=scriptFlagsOf(c.flags)=(c.flags.cltv,c.flags.csv,c.flags.nulldummy); and OB=O(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,witnessV0,B) is the concrete legacy oracle with signature flags (c.flags.dersig,false,false,false), signature version witnessV0 and script code B, so that in the right-hand side OB.hash160 is the concrete RIPEMD160∘SHA256 (not an arbitrary function) and OB.checkSig is the concrete BIP143 ECDSA check described below. The stack handed to OfferedSpend is reverse(ws), the list ws in reverse order (so the last element of ws is the top of the stack), which is empty when ws is empty, in which case OfferedSpend is false since every disjunct requires a stack of length 2 or 4. The conjunct castToBool(H)=true says the 32-byte digest is not all zero bytes and not all zero bytes with last byte 0x80. The parameters r,Kr,Kl,h are arbitrary byte strings within the size bound; nothing requires r or h to be 20 bytes or to be hashes of anything.
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 byte strings. OffB(r,Kr,Kl,h) is the byte string
[0x76,0xa9]++pushBytes(r)++[0x87,0x63,0xac,0x67]++pushBytes(Kr)++[0x7c,0x82]++numBytes(32)++[0x87,0x64,0x75]++numBytes(2)++[0x7c]++pushBytes(Kl)++numBytes(2)++[0xae,0x67,0xa9]++pushBytes(h)++[0x88,0xac,0x68,0x68]
(the opcode bytes are OP_DUP OP_HASH160 … OP_EQUAL OP_IF OP_CHECKSIG OP_ELSE … OP_SWAP OP_SIZE … OP_EQUAL OP_NOTIF OP_DROP … OP_SWAP … OP_CHECKMULTISIG OP_ELSE OP_HASH160 … OP_EQUALVERIFY OP_CHECKSIG OP_ENDIF OP_ENDIF; numBytes(32)=[0x01,0x20] and numBytes(2)=[0x52]). RecB(r,Kr,Kl,h,e) is the byte string
[0x76,0xa9]++pushBytes(r)++[0x87,0x63,0xac,0x67]++pushBytes(Kr)++[0x7c,0x82]++numBytes(32)++[0x87,0x63,0xa9]++pushBytes(h)++[0x88]++numBytes(2)++[0x7c]++pushBytes(Kl)++numBytes(2)++[0xae,0x67,0x75]++numBytes(e)++[0xb1,0x75,0xac,0x68,0x68]
(… OP_EQUAL OP_IF OP_HASH160 … OP_EQUALVERIFY … OP_SWAP … OP_CHECKMULTISIG OP_ELSE OP_DROP <e> OP_CHECKLOCKTIMEVERIFY OP_DROP OP_CHECKSIG OP_ENDIF OP_ENDIF), where numBytes(e) is the single byte e+0x50 if e=−1 or 1≤e≤16 and pushBytes(ser(e)) otherwise.
Byte-level parsing parse(s). parse reads a byte string instruction by instruction with a fuel of ∣s∣ steps and yields none on any malformed push and some of the instruction list otherwise. One instruction is read from a first byte b as follows: if b≤0x4e it is a data push, whose length is b itself when b<0x4c, the next one byte when b=0x4c, the next two bytes little-endian when b=0x4d, and the next four bytes little-endian when b=0x4e (failing if those length bytes are missing), and the push fails if fewer bytes than the announced length remain; otherwise (b>0x4e) it is the non-push opcode b. The empty string parses to the empty instruction list.
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 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.
The concrete oracle O(sf,tx,n,a,v,sc) ("legacy oracle") for signature-layer flags sf, a transaction tx, an input index n, an amount a∈Z, a signature version v∈{base,witnessV0} and a script-code byte string sc is the oracle whose five hash functions are the concrete transcriptions of SHA-1, SHA-256, RIPEMD-160, hash256=SHA256∘SHA256 and hash160=RIPEMD160∘SHA256; whose checkLockTime is CLT(tx,n,⋅) and checkSequence the analogous transcription of CheckSequence; and whose checkSig(sig,pk) is the pre-tapscript check: for v=witnessV0 the script code is used as is (for v=base every push of sig is first deleted from it); it is none if the signature-encoding check or the public-key-encoding check under sf fails, and otherwise some of the ECDSA verdict. The signature-layer flags are four Booleans dersig,lowS,strictenc,witnessPubkeyType; the signature-encoding check accepts an empty signature, otherwise rejects a non-strict-DER encoding when any of dersig,lowS,strictenc is set, rejects a high-S signature when lowS is set, and rejects an undefined hash-type byte when strictenc is set; the public-key-encoding check rejects a key that is neither compressed nor uncompressed when strictenc is set and a non-compressed key under witnessV0 when witnessPubkeyType is set. The ECDSA verdict is false when the key's header byte does not announce its length (0x02/0x03 for 33 bytes, 0x04/0x06/0x07 for 65 bytes, anything else invalid), when the signature is empty, or when v=witnessV0 and a<0; otherwise the last byte of the signature is the hash type, the signature hash is the BIP143 digest (for witnessV0, over tx, input n, the script code, the amount a and the hash type) or the legacy digest (for base), and the verdict is secp256k1 ECDSA verification of the remaining signature bytes (lax DER parsing, S normalised to the low half, the digest reduced modulo the group order) against the parsed key. CLT(tx,n,t), for t∈Z, is: false unless either both tx.nLockTime<500000000 and t<500000000, or both tx.nLockTime≥500000000 and t≥500000000; then false if tx.nLockTime<t; then false if the nSequence of input n of tx equals 0xffffffff, where, if n is not a valid input index, a default input with nSequence 0 is used; and true otherwise. When the oracle comes from a consensus flag set F (Booleans p2sh,witness,taproot,dersig,cltv,csv,nulldummy), the interpreter flags are scriptFlagsOf(F)=(F.cltv,F.csv,F.nulldummy) and the signature-layer flags are sigFlagsOf(F)=(F.dersig,false,false,false), so under sigFlagsOf(F) the public-key-encoding check always passes and the signature-encoding check only rejects non-empty, non-strict-DER signatures when F.dersig is set.
Script verification verifyScript(tap,c,ss,spk,w). A verification context c consists of a consensus flag set c.flags (Booleans p2sh,witness,taproot,dersig,cltv,csv,nulldummy), a transaction c.tx, an input index c.nIn and an amount c.amount∈Z; tap is an arbitrary function (a "Taproot handler") from a context, a witness stack and a program to a Boolean. evalBytes(c,v,st,s) for a byte-level script s is none if ∣s∣>10000 or s does not parse, and otherwise evalf,o(st,parse(s)) with f=scriptFlagsOf(c.flags) and o=O(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,v,s). verifyScript with scriptSig ss, scriptPubKey spk and witness list w (in transaction order, last element on top) is the Boolean computed as: run evalBytes(c,base,[],ss), false on failure; run evalBytes(c,base,⋅,spk) on the resulting stack, false on failure; false if the resulting stack is empty or its top is not castToBool-true; then, if c.flags.witness is set and spk is a witness program (length between 4 and 42, first byte 0 or in 0x51..0x60, second byte plus 2 equal to the length; version 0 for first byte 0, else first byte minus 0x50; program the bytes after the second), the verdict is false if ss=[] and otherwise verifyWitnessProgram(tap,c,w,version,program,false); if spk is not a witness program the P2SH and bare-script branches follow (not reached by the statements here). verifyWitnessProgram at version 0 with a 32-byte program is: false if w is empty; otherwise, with script the last element of w, false if SHA256(script)=program, and otherwise execV0(c,reverse(w without its last element),script); at version 0 with a 20-byte program it is the P2WPKH case, at version 1 with a 32-byte non-P2SH program it is true if c.flags.taproot is off and tap(c,w,program) otherwise, and every other version is true. execV0(c,st,s) is false if some element of st is longer than 520 bytes, false if evalBytes(c,witnessV0,st,s) fails, and otherwise true iff the final stack has exactly one element and topTrue of it, where topTrue(st) is false for an empty stack and castToBool of the top element otherwise. The output script witnessBytes(0,p) is the byte string [0x00]++pushBytes(p) (for a 32-byte p: [0x00,0x20]++p).
Confirmed by the moderator at approval.