What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: BitcoinMiniscript.compile_length
Statement. For every Miniscript fragment m (no typing hypothesis: m may be any of the syntax trees described below, including ones that are not well typed, e.g. multi(k,keys) with any k and any key list, or leaves with arbitrarily long byte strings or arbitrary integers), the number of instructions in the compiled script equals the syntactic size:
∣compile(m)∣=size(m).
Here ∣⋅∣ counts instructions of the script (each push, each opcode, and each numInstr(⋅) counts as exactly one instruction, whatever bytes it carries). Nothing is asserted about execution.
Definitions used in the statement, unfolded
Basic data (from the script-interpreter preamble)
Byte strings, stacks, witnesses. A byte string is a finite list of 8-bit bytes (values 0x00–0xff); [] is the empty byte string and ∣b∣ the length of b. Stacks, witnesses and outputs are finite lists of byte strings written top element first. For such lists, x::l is the list with x placed on top of l, l1++l2 is concatenation (in w++rest all elements of w lie above all elements of rest, the first element of w being the top of the stack), and ∣l∣ is the number of elements.
Constants.
MAX_SCRIPT_ELEMENT_SIZE=520,MAX_OPS_PER_SCRIPT=201,MAX_PUBKEYS_PER_MULTISIG=20,MAX_STACK_SIZE=1000.
castToBool. For a byte string: castToBool([])=false; castToBool([b0])=(b0=0x00∧b0=0x80); for a string with at least two bytes, castToBool(b0::r)=(b0=0)∨castToBool(r). So it is true exactly when some byte other than the last is nonzero, or the last byte is neither 0x00 nor 0x80; the empty string, all-zero strings, and strings of zero bytes followed by a final 0x80 are false.
boolBytes. boolBytes(true)=[0x01], boolBytes(false)=[].
serialize (script-number encoding of an integer n). serialize(0)=[]. For n=0, let mag be the little-endian base-256 digits of ∣n∣ with no most-significant zero bytes. If the last (most significant) byte of mag has bit 0x80 set, the result is mag followed by one extra byte, 0x80 if n<0 and 0x00 if n>0; otherwise the result is mag with bit 0x80 of its last byte set if n<0, and mag itself if n>0. Examples: serialize(1)=[0x01], serialize(−1)=[0x81], serialize(32)=[0x20], serialize(128)=[0x80,0x00], serialize(231−1)=[0xff,0xff,0xff,0x7f].
Flags f. A record of three independent booleans f.cltv, f.csv, f.nulldummy; every combination is allowed.
Oracle o. A record of completely arbitrary functions, with no property assumed of any of them (they are not required to be the real hash functions or a real signature check, need not produce outputs of any particular length, and need not be injective or collision resistant):
- o.ripemd160, o.sha1, o.sha256, o.hash160, o.hash256: byte strings → byte strings;
- o.checkSig(sig,pubkey)∈{none,some(true),some(false)}, an arbitrary function of a signature and a public key ("none" means the script fails);
- o.checkLockTime, o.checkSequence: integers → booleans.
multisigLoopo(sigs,keys) (both lists top-first), with result none, some(true) or some(false):
- if sigs=[]: some(true);
- if sigs is nonempty and keys=[]: some(false);
- if sigs=s::S and keys=k::K: compute o.checkSig(s,k). If none, the result is none. If some(true): the result is some(false) when ∣K∣<∣S∣, and otherwise multisigLoopo(S,K). If some(false): the result is some(false) when ∣K∣<∣S∣+1, and otherwise multisigLoopo(s::S,K).
The script interpreter (from the script-interpreter preamble)
Instructions and scripts. An instruction is either push(d) for a byte string d, or op(c) for an opcode byte c. A script is a finite list of instructions. Opcode bytes used below: OP_1NEGATE =0x4f, OP_RESERVED =0x50, OP_1…OP_16 =0x51…0x60, OP_NOP =0x61, OP_IF =0x63, OP_NOTIF =0x64, OP_ELSE =0x67, OP_ENDIF =0x68, OP_VERIFY =0x69, OP_RETURN =0x6a, OP_TOALTSTACK =0x6b, OP_FROMALTSTACK =0x6c, OP_IFDUP =0x73, OP_DUP =0x76, OP_SWAP =0x7c, OP_SIZE =0x82, OP_EQUAL =0x87, OP_EQUALVERIFY =0x88, OP_0NOTEQUAL =0x92, OP_BOOLAND =0x9a, OP_BOOLOR =0x9b, OP_RIPEMD160 =0xa6, OP_SHA1 =0xa7, OP_SHA256 =0xa8, OP_HASH160 =0xa9, OP_HASH256 =0xaa, OP_CODESEPARATOR =0xab, OP_CHECKSIG =0xac, OP_CHECKSIGVERIFY =0xad, OP_CHECKMULTISIG =0xae, OP_CHECKMULTISIGVERIFY =0xaf, OP_NOP1 =0xb0, OP_CHECKLOCKTIMEVERIFY =0xb1, OP_CHECKSEQUENCEVERIFY =0xb2, OP_NOP4…OP_NOP10 =0xb3…0xb9 (plus the other standard stack/arithmetic opcodes named below).
opsIn(sc) is the number of instructions op(c) in the script sc with c>0x60 (pushes and opcodes ≤0x60 are not counted).
States. A state is a quadruple (stack,alt,vf,k): the main stack and the alt stack (lists of byte strings, top first), the condition stack vf (a list of booleans, innermost first) and the operation counter k∈N. initial(st)=(st,[],[],0). allTrue(vf) means every entry of vf is true (so it is true for vf=[], and false exactly when vf contains at least one false). The state is executing when allTrue(vf).
Decoding numbers. "Decode v with limit L" fails if ∣v∣>L; otherwise it gives the sign–magnitude little-endian value of v: if the last byte has bit 0x80 set, minus the little-endian value of v with that bit cleared, else the little-endian value of v ([] decodes to 0). No minimal-encoding requirement is applied anywhere.
stepf,o(s,i) — one instruction; result is a new state or failure.
- i=push(d): fail if ∣d∣>520. If executing, put d on top of the main stack; otherwise leave the state unchanged. Then fail if ∣stack∣+∣alt∣>1000.
- i=op(c): (1) if c>0x60 and k+1>201, fail; if c>0x60, increase k by one (this happens also in non-executed branches). (2) If c is one 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), fail, executing or not. (3) If executing, or 0x63≤c≤0x68, apply execOp (below, with the flag "executing" passed in); fail if it fails, and otherwise fail if the resulting ∣stack∣+∣alt∣>1000. (4) Otherwise the state is unchanged apart from k, and it fails if ∣stack∣+∣alt∣>1000.
execOpf,o(fExec,c,s). "Top" is the first stack element, "second" the next; whenever a required element is missing the result is failure.
OP_1NEGATE or OP_1…OP_16: push serialize(c−0x50), i.e. of −1,1,…,16.
OP_NOP, OP_NOP1, OP_NOP4…OP_NOP10, OP_CODESEPARATOR: no change.
OP_CHECKLOCKTIMEVERIFY: if f.cltv is false, no change. Otherwise decode the top with limit 5 (not removing it); fail if that fails, if the value n<0, or if o.checkLockTime(n) is false; else no change.
OP_CHECKSEQUENCEVERIFY: if f.csv is false, no change. Otherwise decode the top with limit 5 (not removing it); fail if that fails or n<0; if bit 231 of n is set, no change; otherwise fail if o.checkSequence(n) is false, else no change.
OP_IF / OP_NOTIF: if fExec, remove the top t and put castToBool(t) (negated for OP_NOTIF) in front of vf; if not fExec, put false in front of vf and leave the stack alone.
OP_ELSE: fail if vf is empty, else negate its first entry. OP_ENDIF: fail if vf is empty, else remove its first entry.
OP_VERIFY: remove the top; fail if castToBool of it is false. OP_RETURN: fail.
OP_TOALTSTACK: move the top of the main stack onto the alt stack. OP_FROMALTSTACK: move the top of the alt stack onto the main stack.
OP_2DROP, OP_2DUP, OP_3DUP, OP_2OVER, OP_2ROT, OP_2SWAP, OP_DROP, OP_NIP, OP_OVER, OP_ROT, OP_TUCK: the standard rearrangements of the top two to six elements. OP_DUP: duplicate the top. OP_SWAP: exchange top and second. OP_IFDUP: duplicate the top if castToBool of it is true, else no change. OP_DEPTH: push serialize(∣stack∣). OP_PICK/OP_ROLL: remove the top, decode it (limit 4) as n, require a nonempty remainder with 0≤n< its length, and copy (PICK) or move (ROLL) its element of index n (0 = top) to the top.
OP_SIZE: push serialize(∣t∣) for the top t, which stays.
OP_EQUAL / OP_EQUALVERIFY: remove the top a and second b; OP_EQUAL pushes boolBytes(a=b); OP_EQUALVERIFY fails unless a=b.
OP_1ADD, OP_1SUB, OP_NEGATE, OP_ABS, OP_NOT, OP_0NOTEQUAL: remove the top, decode it with limit 4 as n (fail if longer), push serialize of n+1, n−1, −n, ∣n∣, (1 if n=0 else 0), (1 if n=0 else 0) respectively.
OP_ADD, OP_SUB, OP_BOOLAND, OP_BOOLOR, OP_NUMEQUAL, OP_NUMEQUALVERIFY, OP_NUMNOTEQUAL, OP_LESSTHAN, OP_GREATERTHAN, OP_LESSTHANOREQUAL, OP_GREATERTHANOREQUAL, OP_MIN, OP_MAX: remove the top a and second b, decode n1 from b and n2 from a with limit 4 (fail if either is longer), and push serialize of the result: n1+n2, n1−n2, (1 if n1=0 and n2=0 else 0), (1 if n1=0 or n2=0 else 0), and 1/0 for =,=,=,<,>,≤,≥, then min, max; OP_NUMEQUALVERIFY pushes nothing and fails unless n1=n2.
OP_WITHIN: remove three elements a (top), b, d, decode each with limit 4, push boolBytes(b≤d<a) of the decoded values.
OP_RIPEMD160, OP_SHA1, OP_SHA256, OP_HASH160, OP_HASH256: replace the top t by o.ripemd160(t), o.sha1(t), o.sha256(t), o.hash160(t), o.hash256(t) respectively.
OP_CHECKSIG / OP_CHECKSIGVERIFY: with pubkey the top and sig the second, let r=o.checkSig(sig,pubkey); fail if r is none; OP_CHECKSIG replaces both by boolBytes(r); OP_CHECKSIGVERIFY removes both and fails unless r is true.
OP_CHECKMULTISIG / OP_CHECKMULTISIGVERIFY: remove the top and decode it (limit 4) as nK; fail if nK<0 or nK>20; let k′=k+nK and fail if k′>201; the next nK elements (top-first) are the keys (fail if fewer); the following element is decoded (limit 4) as nS, failing if absent, if nS<0 or nS>nK; the next nS elements (top-first) are the signatures (fail if fewer); let r=multisigLoopo(sigs,keys) and fail if none; one more element, the dummy, must be present and is removed; fail if f.nulldummy is true and the dummy is not []; the counter becomes k′; OP_CHECKMULTISIG pushes boolBytes(r) onto what remains, the VERIFY form pushes nothing and fails unless r is true.
- Every other byte (including
OP_RESERVED, 0x65, 0x66 and any byte ≤0x4e used as an opcode): fail.
runf,o(s,sc): run(s,[]) is s if its condition stack is empty and failure otherwise; run(s,i::sc′) fails if step(s,i) fails and is run(step(s,i),sc′) otherwise.
evalScriptf,o(st,sc): if run(initial(st),sc) succeeds with final state s′, the result is "some" of the main stack of s′; otherwise it is failure (none). Nothing about the alt stack, the operation counter, or the truth of the top element is checked; the initial stack st is not checked against any size limit.
runSeqf,o(s,sc) (defined in the Miniscript file): exactly like run but without the final check: runSeq(s,[])=some(s) (whatever its condition stack), and runSeq(s,i::sc′) fails if step(s,i) fails and is runSeq(step(s,i),sc′) otherwise.
Miniscript definitions used
numInstr(n) (from the to_local preamble), for an integer n: if n=−1 or 1≤n≤16, it is the opcode instruction op(n+0x50), i.e. OP_1NEGATE for −1 and OP_1…OP_16 for 1,…,16 (these opcodes are ≤0x60, so they are not counted by the operation counter, and when executed they push serialize(n)); otherwise it is push(serialize(n)) — in particular numInstr(0)=push([]), numInstr(32)=push([0x20]), and numInstr(n)=push(serialize(n)) for n≥17.
Miniscript fragments Ms. The set of finite syntax trees built from exactly the following 23 constructors (byte-string, integer, natural-number and list parameters are arbitrary; no well-formedness is built in):
- pk_k(κ), κ a byte string (a key);
- pk_h(h), h a byte string (a key hash);
- older(n), n∈Z;
- after(n), n∈Z;
- sha256(h), 6. hash256(h), 7. ripemd160(h), 8. hash160(h), each with h a byte string;
- and_v(x,y), 10. and_b(x,y), with x,y fragments;
- or_b(x,z), 12. or_c(x,z), 13. or_d(x,z), 14. or_i(x,z), with x,z fragments;
- andor(x,y,z), with x,y,z fragments;
- multi(k,keys), k∈N and keys a finite list of byte strings;
17.–23. the wrappers wrap_a(x), wrap_s(x), wrap_c(x), wrap_d(x), wrap_v(x), wrap_j(x), wrap_n(x), with x a fragment.
Two fragments are equal exactly when they are built identically.
compile(m), the script of a fragment m, written C(m); opcode instructions are written by name, ++ is concatenation of instruction lists:
- C(pk_k(κ))=[push(κ)].
- C(pk_h(h))=[
OP_DUP, OP_HASH160, push(h), OP_EQUALVERIFY] (no OP_CHECKSIG).
- C(older(n))=[numInstr(n),
OP_CHECKSEQUENCEVERIFY].
- C(after(n))=[numInstr(n),
OP_CHECKLOCKTIMEVERIFY].
- C(sha256(h))=[
OP_SIZE, numInstr(32), OP_EQUALVERIFY, OP_SHA256, push(h), OP_EQUAL].
- C(hash256(h)): the same with
OP_HASH256 in place of OP_SHA256.
- C(ripemd160(h)): the same with
OP_RIPEMD160 (the size check is still against 32).
- C(hash160(h)): the same with
OP_HASH160 (the size check is still against 32).
- C(and_v(x,y))=C(x)++C(y).
- C(and_b(x,y))=C(x)++C(y)++[
OP_BOOLAND].
- C(or_b(x,z))=C(x)++C(z)++[
OP_BOOLOR].
- C(or_c(x,z))=C(x)++[
OP_NOTIF]++C(z)++[OP_ENDIF].
- C(or_d(x,z))=C(x)++[
OP_IFDUP, OP_NOTIF]++C(z)++[OP_ENDIF].
- C(or_i(x,z))=[
OP_IF]++C(x)++[OP_ELSE]++C(z)++[OP_ENDIF].
- C(andor(x,y,z))=C(x)++[
OP_NOTIF]++C(z)++[OP_ELSE]++C(y)++[OP_ENDIF] (note z comes before y).
- C(multi(k,[κ1,…,κℓ]))=[numInstr(k),push(κ1),…,push(κℓ),numInstr(ℓ),
OP_CHECKMULTISIG] (k and ℓ read as integers).
- C(wrap_a(x))=[
OP_TOALTSTACK]++C(x)++[OP_FROMALTSTACK].
- C(wrap_s(x))=[
OP_SWAP]++C(x).
- C(wrap_c(x))=C(x)++[
OP_CHECKSIG].
- C(wrap_d(x))=[
OP_DUP, OP_IF]++C(x)++[OP_ENDIF].
- C(wrap_v(x))=C(x)++[
OP_VERIFY] (always a separate OP_VERIFY).
- C(wrap_j(x))=[
OP_SIZE, OP_0NOTEQUAL, OP_IF]++C(x)++[OP_ENDIF].
- C(wrap_n(x))=C(x)++[
OP_0NOTEQUAL].
Opcode bytes: OP_IF 0x63, OP_NOTIF 0x64, OP_ELSE 0x67, OP_ENDIF 0x68, OP_VERIFY 0x69, OP_TOALTSTACK 0x6b, OP_FROMALTSTACK 0x6c, OP_IFDUP 0x73, OP_DUP 0x76, OP_SWAP 0x7c, OP_SIZE 0x82, OP_EQUAL 0x87, OP_EQUALVERIFY 0x88, OP_0NOTEQUAL 0x92, OP_BOOLAND 0x9a, OP_BOOLOR 0x9b, OP_RIPEMD160 0xa6, OP_SHA256 0xa8, OP_HASH160 0xa9, OP_HASH256 0xaa, OP_CHECKSIG 0xac, OP_CHECKMULTISIG 0xae, OP_CHECKLOCKTIMEVERIFY 0xb1, OP_CHECKSEQUENCEVERIFY 0xb2.
size(m)∈N, defined by: size(pk_k(⋅))=1; size(pk_h(⋅))=4; size(older(⋅))=size(after(⋅))=2; size of each of sha256(⋅), hash256(⋅), ripemd160(⋅), hash160(⋅) is 6; size(and_v(x,y))=size(x)+size(y); size(and_b(x,y))=size(x)+size(y)+1; size(or_b(x,z))=size(x)+size(z)+1; size(or_c(x,z))=size(x)+size(z)+2; size(or_d(x,z))=size(or_i(x,z))=size(x)+size(z)+3; size(andor(x,y,z))=size(x)+size(y)+size(z)+3; size(multi(k,keys))=∣keys∣+3; size(wrap_a(x))=size(x)+2; size(wrap_s(x))=size(wrap_c(x))=size(wrap_v(x))=size(wrap_n(x))=size(x)+1; size(wrap_d(x))=size(x)+3; size(wrap_j(x))=size(x)+4.
Confirmed by the moderator at approval.