What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: BitcoinAnchors.parseScript_anchor
Declaration. For every byte string K (fundingKey) with ∣K∣≤520 (hfk),
parseScript(anchorBytes(K))=some(anchorScript(K)),
i.e. the byte-level parser applied to the byte string pushBytes(K)++[0xac,0x73,0x64,0x60,0xb2,0x68] does not fail and returns exactly the seven-instruction list push(K), op(0xac) (OP_CHECKSIG), op(0x73) (OP_IFDUP), op(0x64) (OP_NOTIF), op(0x60) (OP_16), op(0xb2) (OP_CHECKSEQUENCEVERIFY), op(0x68) (OP_ENDIF). Here pushBytes(K) is the canonical push of K (a one-byte length prefix for ∣K∣<76, the prefix 0x4c plus a length byte for 76≤∣K∣≤255, 0x4d plus two length bytes for 256≤∣K∣≤520); parseScript and pushBytes are unfolded in part P below, and anchorScript in part A. The only hypothesis is the length bound on K; K may be empty. There is no oracle, flag or transaction involved: this is a statement about two pure functions on byte strings.
Common unfolded definitions, part A: the script interpreter
Everything below is a literal unfolding of the definitions the statement depends on. Nothing here is a claim about the theorem; it only says what the symbols mean.
Bytes and stacks. A byte is an 8-bit word, i.e. a value in {0,…,255}. A byte string is a finite list of bytes; ∣v∣ is its length and [] is the empty byte string. A stack is a finite list of byte strings written top first: in [a,b,c] the element a is on top. The constants are MAX_SCRIPT_ELEMENT_SIZE=520, MAX_STACK_SIZE=1000, MAX_OPS_PER_SCRIPT=201, MAX_PUBKEYS_PER_MULTISIG=20.
Truth value of a byte string, castToBool(v): [] is false; a one-byte string [b] is true iff b=0 and b=0x80; a string b::r of length at least two is true iff b=0 or castToBool(r). Equivalently, v is true iff some byte of v is nonzero, except that a string consisting of zero bytes followed by a final byte 0x80 is false.
boolBytes: boolBytes(true)=[0x01] (the single byte 1) and boolBytes(false)=[] (the empty byte string).
Stack literals used in the statements. [[1]] is the stack with exactly one element, the one-byte string 0x01; [[16]] is the stack with exactly one element, the one-byte string 0x10 (decimal 16); [[]] is the stack with exactly one element, the empty byte string; [] is the empty stack. A stack written [σ] has exactly one element σ; [x,σ] has exactly two, x on top.
Flags f: a record of three Booleans f.cltv, f.csv, f.nulldummy. No other verification flag exists in this model. Where f is a parameter of a theorem, all three values are unconstrained.
Oracle o: a record of arbitrary functions with no axioms relating them to each other or to anything else: five byte-string-to-byte-string functions o.ripemd160, o.sha1, o.sha256, o.hash160, o.hash256; a function o.checkSig(σ,k) from pairs of byte strings (first the signature, second the key) to the three values none, some true, some false; and two functions o.checkLockTime,o.checkSequence:Z→{true,false}. In particular, in a theorem that takes o as a parameter, o.hash160 is an arbitrary function (its outputs need not be 20 bytes long, it need not be injective, and it has no relation to o.sha256), and o.checkSig is an arbitrary three-valued function.
Script numbers. serialize(v) for v∈Z: [] if v=0; otherwise the little-endian bytes of ∣v∣ with no trailing zero byte, after which: if the last byte has its top bit (0x80) set, one extra byte is appended (0x80 if v<0, 0x00 if v>0); otherwise, if v<0, the top bit of the last byte is set. Thus serialize(1)=[0x01], serialize(2)=[0x02], serialize(16)=[0x10], serialize(32)=[0x20]. The decoding setVch(v) is 0 for [], and otherwise the little-endian value of v with the top bit of the last byte removed and read as a minus sign. toNum(false,m,v) is none if m<∣v∣ and somesetVch(v) otherwise (no minimal-encoding check is made).
Instructions and scripts. An instruction is either a push push(d) of a byte string d, or an opcode op(c) for a byte c. A script is a finite list of instructions. Opcode bytes that occur: OP_1NEGATE =0x4f, OP_1 =0x51, OP_2 =0x52, OP_16 =0x60, OP_IF =0x63, OP_NOTIF =0x64, OP_ELSE =0x67, OP_ENDIF =0x68, OP_IFDUP =0x73, OP_DROP =0x75, OP_DUP =0x76, OP_SWAP =0x7c, OP_SIZE =0x82, OP_EQUAL =0x87, OP_EQUALVERIFY =0x88, OP_HASH160 =0xa9, OP_CHECKSIG =0xac, OP_CHECKSIGVERIFY =0xad, OP_CHECKMULTISIG =0xae, OP_CHECKLOCKTIMEVERIFY =0xb1, OP_CHECKSEQUENCEVERIFY =0xb2.
numInstr(n) for n∈Z: if n=−1 or 1≤n≤16, the opcode op(n+0x50) (so numInstr(1)=op(OP_1), numInstr(2)=op(OP_2), numInstr(16)=op(OP_16), numInstr(−1)=op(0x4f)); otherwise the push push(serialize(n)) (so numInstr(32)=push([0x20]) and numInstr(0)=push([])).
The parsed scripts of the anchors file, for arbitrary byte strings K (funding key), R (remote key), L (local key), H (revocation hash), P (payment hash) and an integer e (expiry):
toRemoteScript(R)=[push(R), op(OP_CHECKSIGVERIFY), op(OP_1), op(OP_CHECKSEQUENCEVERIFY)].
anchorScript(K)=[push(K), op(OP_CHECKSIG), op(OP_IFDUP), op(OP_NOTIF), op(OP_16), op(OP_CHECKSEQUENCEVERIFY), op(OP_ENDIF)].
offeredScript(H,R,L,P) is the 30-instruction list: OP_DUP, OP_HASH160, push(H), OP_EQUAL, OP_IF, OP_CHECKSIG, OP_ELSE, push(R), OP_SWAP, OP_SIZE, push([0x20]), OP_EQUAL, OP_NOTIF, OP_DROP, OP_2, OP_SWAP, push(L), OP_2, OP_CHECKMULTISIG, OP_ELSE, OP_HASH160, push(P), OP_EQUALVERIFY, OP_CHECKSIG, OP_ENDIF, OP_1, OP_CHECKSEQUENCEVERIFY, OP_DROP, OP_ENDIF.
receivedScript(H,R,L,P,e) is the 32-instruction list: OP_DUP, OP_HASH160, push(H), OP_EQUAL, OP_IF, OP_CHECKSIG, OP_ELSE, push(R), OP_SWAP, OP_SIZE, push([0x20]), OP_EQUAL, OP_IF, OP_HASH160, push(P), OP_EQUALVERIFY, OP_2, OP_SWAP, push(L), OP_2, OP_CHECKMULTISIG, OP_ELSE, OP_DROP, numInstr(e), OP_CHECKLOCKTIMEVERIFY, OP_DROP, OP_CHECKSIG, OP_ENDIF, OP_1, OP_CHECKSEQUENCEVERIFY, OP_DROP, OP_ENDIF.
Execution state: a main stack, an alt stack, a condition stack vfExec (a list of Booleans) and an op counter. The initial state for a stack st has main stack st, empty alt stack, empty vfExec, counter 0. The machine is executing when every entry of vfExec is true (vacuously, when vfExec is empty).
evalScript(f,o,st,S): starting from the initial state of st, apply step to the instructions of S in order; if any step returns none the result is none; after the last instruction the result is none if vfExec is non-empty and otherwise some of the final main stack. So the value is either none (script failure) or somest′ for a stack st′ (the alt stack and the counter are discarded).
step on push(d): none if 520<∣d∣; otherwise, if executing, d is placed on top of the main stack (if not executing, nothing changes); then none if the main-stack size plus the alt-stack size exceeds 1000, else the new state.
step on op(c): c is counted when 0x60<c; if counted and the counter plus one exceeds 201, none; otherwise the counter is incremented when counted; none if c is one of the fifteen disabled opcodes (none of the opcodes listed above is disabled); otherwise, if executing or 0x63≤c≤0x68 (the conditionals), execOp is applied and the result is none if it is none or if the stack-size sum then exceeds 1000; otherwise (not executing, not a conditional) the state is unchanged, again subject to the size check.
execOp(f,o,fExec,c,s) for the opcodes that occur ("none" means script failure; "no change" means the state is returned unchanged):
- OP_1NEGATE, OP_1, …, OP_16: push serialize(c−0x50); so OP_1 pushes [0x01], OP_2 pushes [0x02], OP_16 pushes [0x10]. These bytes are ≤0x60, so they are not counted.
- OP_CHECKLOCKTIMEVERIFY: if f.cltv=false, no change. Otherwise none on an empty stack; else with top t (not popped): none if ∣t∣>5; with n=setVch(t), none if n<0, none if o.checkLockTime(n)=false, else no change.
- OP_CHECKSEQUENCEVERIFY: if f.csv=false, no change. Otherwise none on an empty stack; else with top t (not popped): none if ∣t∣>5; with n=setVch(t), none if n<0; no change if bit 31 of n is set (precisely: max(n,0)&231=0); else none if o.checkSequence(n)=false, else no change.
- OP_IF / OP_NOTIF: if executing, none on an empty stack; else the top t is popped, v=castToBool(t) (negated for OP_NOTIF) and v is pushed onto vfExec. If not executing, false is pushed onto vfExec and the stack is untouched.
- OP_ELSE: none if vfExec is empty; else its top entry is negated.
- OP_ENDIF: none if vfExec is empty; else its top entry is removed.
- OP_IFDUP: none on an empty stack; else if castToBool of the top is true the top is duplicated, otherwise no change.
- OP_DROP: none on an empty stack; else the top is removed. OP_DUP: none on an empty stack; else the top is duplicated. OP_SWAP: none with fewer than two elements; else the top two are exchanged. OP_SIZE: none on an empty stack; else serialize(∣t∣) is pushed above the top t, which stays.
- OP_EQUAL / OP_EQUALVERIFY: none with fewer than two elements; else the top a and the next b are popped and eq is the proposition "a and b are the same byte string"; OP_EQUAL pushes boolBytes(eq); OP_EQUALVERIFY pushes nothing and is none when eq is false.
- OP_HASH160: none on an empty stack; else the top t is replaced by o.hash160(t).
- OP_CHECKSIG / OP_CHECKSIGVERIFY: none with fewer than two elements; else the top k (the key) and the next σ (the signature) are popped and o.checkSig(σ,k) is consulted: none gives none; someok: OP_CHECKSIG pushes boolBytes(ok), while OP_CHECKSIGVERIFY pushes nothing and is none when ok=false.
- OP_CHECKMULTISIG: none on an empty stack; the top nk is popped and decoded by toNum(false,4,⋅) (none if longer than 4 bytes); none if nk<0 or 20<nk; the counter becomes counter +nk, none if that exceeds 201; the next nk elements are the keys (none if fewer remain); the next element ns is popped (none if none remains) and decoded likewise, none if ns<0 or nk<ns; the next ns elements are the signatures (none if fewer remain); multisigLoop(o,sigs,keys) is computed: none gives none; someok: none if no element remains, else one more element dummy is popped, none if f.nulldummy=true and dummy=[], else boolBytes(ok) is pushed.
multisigLoop(o,sigs,keys) (both lists top first): some true if sigs is empty; some false if sigs is non-empty and keys is empty; otherwise, with σ the first signature and k the first key, o.checkSig(σ,k): none gives none; some true gives some false if fewer keys than signatures remain after removing both, else the loop on the remaining signatures and remaining keys; some false gives some false if the remaining keys are fewer than all the current signatures, else the loop on the same signatures and the remaining keys. For the only instance that occurs, multisigLoop(o,[σL,σR],[L,R]) unfolds to: none if o.checkSig(σL,L)=none; some false if o.checkSig(σL,L)=some false; and, if o.checkSig(σL,L)=some true, the value o.checkSig(σR,R) itself. Hence it equals some true iff o.checkSig(σL,L)=some true and o.checkSig(σR,R)=some true; the signature σR is never checked against L, nor σL against R.
CsvPasses(f,o,d) for d∈Z:
f.csv=false ∨ (0≤d ∧ (max(d,0)&231=0 ∨ o.checkSequence(d)=true)).
For d=1 and d=16 the bit-31 disjunct is false (1&231=0 and 16&231=0), so CsvPasses(f,o,1)⟺f.csv=false∨o.checkSequence(1)=true and CsvPasses(f,o,16)⟺f.csv=false∨o.checkSequence(16)=true. When f and o are arbitrary parameters, o.checkSequence is an arbitrary function of an integer.
CltvPasses(f,o,e) for e∈Z: f.cltv=false ∨ (0≤e ∧ o.checkLockTime(e)=true).
topTrue(st): false for the empty stack; castToBool of the top element otherwise.
The spend predicates of the anchors file (all stacks top first; σ,σL,σR,pk,x,d range over byte strings):
ToRemoteSpend(f,o,R,st): there is σ with st=[σ], o.checkSig(σ,R)=some true and CsvPasses(f,o,1).
AnchorSpend(f,o,K,st): there is σ with st=[σ] and either o.checkSig(σ,K)=some true, or both o.checkSig(σ,K)=some false and CsvPasses(f,o,16).
OfferedSpend(f,o,H,R,L,P,st) is the disjunction of
- there are pk,σ with st=[pk,σ], o.hash160(pk)=H and o.checkSig(σ,pk)=some true;
- there are x,σ with st=[x,σ], o.hash160(x)=H, ∣x∣=32, o.hash160(x)=P, o.checkSig(σ,R)=some true and CsvPasses(f,o,1);
- there are x,σL,σR,d with st=[x,σL,σR,d], o.hash160(x)=H, ∣x∣=32, multisigLoop(o,[σL,σR],[L,R])=some true, (f.nulldummy=true⇒d=[]) and CsvPasses(f,o,1).
ReceivedSpend(f,o,H,R,L,P,e,st) is the disjunction of
- there are pk,σ with st=[pk,σ], o.hash160(pk)=H and o.checkSig(σ,pk)=some true;
- there are x,σL,σR,d with st=[x,σL,σR,d], o.hash160(x)=H, ∣x∣=32, o.hash160(x)=P, multisigLoop(o,[σL,σR],[L,R])=some true, (f.nulldummy=true⇒d=[]) and CsvPasses(f,o,1);
- there are x,σ with st=[x,σ], o.hash160(x)=H, ∣x∣=32, CltvPasses(f,o,e), o.checkSig(σ,R)=some true and CsvPasses(f,o,1).
Common unfolded definitions, part P: byte-level scripts and parsing
Canonical push, pushBytes(d) for a byte string d: if ∣d∣<76 (= 0x4c), the single byte ∣d∣ followed by d; else if ∣d∣≤255, the bytes 0x4c, ∣d∣, then d; else if ∣d∣≤65535, the byte 0x4d, the two little-endian bytes of ∣d∣, then d; else the byte 0x4e, the four little-endian bytes of ∣d∣, then d.
numBytes(n) for n∈Z: if n=−1 or 1≤n≤16, the single byte n+0x50 (so numBytes(1)=[0x51], numBytes(2)=[0x52], numBytes(16)=[0x60]); otherwise pushBytes(serialize(n)) (so numBytes(32)=[0x01,0x20] and numBytes(0)=[0x00], the empty push).
The serialized scripts of the anchors file (byte strings, ++ is concatenation):
toRemoteBytes(R)=pushBytes(R)++[0xad]++[0x51]++[0xb2].
anchorBytes(K)=pushBytes(K)++[0xac,0x73,0x64]++[0x60]++[0xb2,0x68].
offeredBytes(H,R,L,P)=[0x76,0xa9]++pushBytes(H)++[0x87,0x63,0xac,0x67]++pushBytes(R)++[0x7c,0x82]++[0x01,0x20]++[0x87,0x64,0x75]++[0x52]++[0x7c]++pushBytes(L)++[0x52]++[0xae,0x67,0xa9]++pushBytes(P)++[0x88,0xac,0x68]++[0x51]++[0xb2,0x75,0x68].
receivedBytes(H,R,L,P,e)=[0x76,0xa9]++pushBytes(H)++[0x87,0x63,0xac,0x67]++pushBytes(R)++[0x7c,0x82]++[0x01,0x20]++[0x87,0x63,0xa9]++pushBytes(P)++[0x88]++[0x52]++[0x7c]++pushBytes(L)++[0x52]++[0xae,0x67,0x75]++numBytes(e)++[0xb1,0x75,0xac,0x68]++[0x51]++[0xb2,0x75,0x68].
getOp(s), one instruction off the front of a byte string: none if s is empty. Otherwise let c be the first byte and r the rest. If c≤0x4e: the push size is c itself when c<0x4c; the next byte when c=0x4c (none if r is empty); the little-endian value of the next two bytes when c=0x4d (none if fewer than two remain); the little-endian value of the next four bytes when c=0x4e (none if fewer than four remain); then, with the size bytes removed from r, none if fewer than size bytes remain, else the pair (push of the next size bytes, the remainder). If c>0x4e: the pair (op(c), r).
parseScript(s): an auxiliary recursion with fuel ∣s∣: on the empty string, some[]; with fuel 0 and a non-empty string, none; otherwise getOp (none propagates) and the instruction is prepended to the parse of the remainder with one less fuel. The value is either none or some of a list of instructions.
Confirmed by the moderator at approval.