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.goodVal_of_sem
Statement. For any flags f, any oracle o (arbitrary functions, see below), any fragment m with HasType(m,B), any witness w and any byte string v: if Semf,o(m,w,[v]) (the semantics relates w to an output consisting of exactly one element v — whether castToBool(v) is true or false), then GoodVal(v), i.e.
∃n∈Z:0≤n<231 and v=serialize(n).
There are no resource (size or operation-count) hypotheses, and nothing is said about outputs that are not one-element lists.
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).
Miniscript definitions used
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.
Correctness types Ty. A four-element set {B,V,K,W} of distinct labels (no meaning is attached to them other than through the rules below).
Modifier records Props. A record of five booleans (z,o,n,d,u).
props(m)=(z,o,n,d,u), computed syntactically. Write zx,ox,nx,dx,ux for the components of props(x) (similarly for y, z), ∧,∨ for boolean and/or, T/F for true/false. (The modifier letter o is unrelated to the oracle o, and the modifier letter z is unrelated to a sub-fragment named z; e.g. zz is the z-modifier of the sub-fragment z.)
| fragment | z | o | n | d | u |
|---|
| pk_k(κ) | F | T | T | T | T |
| pk_h(h) | F | F | T | T | T |
| older(n), after(n) | T | F | F | F | F |
| sha256, hash256, ripemd160, hash160 | F | T | T | T | T |
| and_v(x,y) | zx∧zy | (zx∧oy)∨(ox∧zy) | nx∨(zx∧ny) | F | uy |
| and_b(x,y) | zx∧zy | (zx∧oy)∨(ox∧zy) | nx∨(zx∧ny) | dx∧dy | T |
| or_b(x,z) | zx∧zz | (zx∧oz)∨(ox∧zz) | F | T | T |
| or_c(x,z) | zx∧zz | ox∧zz | F | F | F |
| or_d(x,z) | zx∧zz | ox∧zz | F | dz | uz |
| or_i(x,z) | F | zx∧zz | F | dx∨dz | ux∧uz |
| andor(x,y,z) | zx∧zy∧zz | (zx∧oy∧oz)∨(ox∧zy∧zz) | F | dz | uy∧uz |
| multi(k,keys) | F | F | T | T | T |
| wrap_a(x) | F | F | F | dx | ux |
| wrap_s(x) | F | ox | F | dx | ux |
| wrap_c(x) | F | ox | nx | dx | T |
| wrap_d(x) | F | T | T | T | F |
| wrap_v(x) | zx | ox | nx | F | F |
| wrap_j(x) | F | ox | T | T | ux |
| wrap_n(x) | zx | ox | nx | dx | T |
(The components do not depend on the byte-string, integer or list parameters of the leaves.)
HasType(m,t), "m has type t", is the smallest relation closed under the following 23 rules (one per constructor; there is no other way to derive it). Throughout, 520=MAX_SCRIPT_ELEMENT_SIZE and 20=MAX_PUBKEYS_PER_MULTISIG.
- pk_k(κ):K if ∣κ∣≤520.
- pk_h(h):K if ∣h∣≤520.
- older(n):B if 1≤n<231.
- after(n):B if 1≤n<231.
5.–8. sha256(h), hash256(h), ripemd160(h), hash160(h) :B if ∣h∣≤520 (no condition on ∣h∣ being any particular hash length).
- and_v(x,y):t if x:V, y:t and t=W.
- and_b(x,y):B if x:B and y:W.
- or_b(x,z):B if x:B, dx, z:W, dz.
- or_c(x,z):V if x:B, dx, ux, z:V.
- or_d(x,z):B if x:B, dx, ux, z:B.
- or_i(x,z):t if x:t, z:t and t=W.
- andor(x,y,z):t if x:B, dx, ux, y:t, z:t and t=W.
- multi(k,keys):B if 1≤k≤∣keys∣≤20 and every key in keys has length ≤520.
- wrap_a(x):W if x:B.
- wrap_s(x):W if x:B and ox.
- wrap_c(x):B if x:K.
- wrap_d(x):B if x:V and zx.
- wrap_v(x):V if x:B.
- wrap_j(x):B if x:B and nx.
- wrap_n(x):B if x:B.
Here dx, ux, ox, zx, nx mean the corresponding component of props(x) is true. Read off the rules: type W is concluded only by rules 17–18 (wrap_a, wrap_s); type K only by rules 1, 2, 9 (with y:K), 14 and 15 (with both branches K); type V only by rules 9, 12, 14, 15, 21. No rule constrains the modifiers o,n,z,u of y or z beyond those listed, and no rule bounds the depth or total size of the fragment.
CsvPassesf,o(n) (from the to_local preamble), for n∈Z: f.csv=false, or (n≥0 and (bit 231 of n is set, or o.checkSequence(n)=true)).
CltvPassesf,o(n) (from the HTLC preamble), for n∈Z: f.cltv=false, or (n≥0 and o.checkLockTime(n)=true).
Semf,o(m,w,out) — a relation between a fragment m, a witness w and an output out (both lists of byte strings, top first), for fixed flags f and oracle o; it is defined by recursion on m, and nothing in it refers to the type of m or to any size or operation-count limit except where stated. "∃" ranges over arbitrary byte strings / lists of byte strings / booleans as appropriate.
- pk_k(κ): ∃sig with w=[sig] and out=[κ,sig].
- pk_h(h): ∃κ,sig with w=[κ,sig], o.hash160(κ)=h and out=[κ,sig].
- older(n): w=[], CsvPassesf,o(n) and out=[serialize(n)].
- after(n): w=[], CltvPassesf,o(n) and out=[serialize(n)].
- sha256(h): ∃p with w=[p], ∣p∣=32 and out=[boolBytes(o.sha256(p)=h)] — so out=[[0x01]] if the oracle hash of p equals h and out=[[]] otherwise (any 32-byte p is accepted either way).
6.–8. hash256(h), ripemd160(h), hash160(h): the same with o.hash256, o.ripemd160, o.hash160 respectively (and still ∣p∣=32).
- and_v(x,y): ∃wx,wy with w=wx++wy, Sem(x,wx,[]) and Sem(y,wy,out).
- and_b(x,y): ∃wx,wy,vx,vy with w=wx++wy, Sem(x,wx,[vx]), Sem(y,wy,[vy]) and out=[boolBytes(castToBool(vx)∧castToBool(vy))].
- or_b(x,z): ∃wx,wz,vx,vz with w=wx++wz, Sem(x,wx,[vx]), Sem(z,wz,[vz]) and out=[boolBytes(castToBool(vx)∨castToBool(vz))] (both sides may be true simultaneously).
- or_c(x,z): out=[] and ∃wx,vx with Sem(x,wx,[vx]) and either (castToBool(vx) true and w=wx) or (castToBool(vx) false and ∃wz with w=wx++wz and Sem(z,wz,[])). (vx in the second alternative is any value with castToBool false, not necessarily [].)
- or_d(x,z): ∃wx,vx with Sem(x,wx,[vx]) and either (castToBool(vx) true, w=wx and out=[vx]) or (castToBool(vx) false and ∃wz with w=wx++wz and Sem(z,wz,out)).
- or_i(x,z): ∃b,w′ with w=b::w′ and either (castToBool(b) true and Sem(x,w′,out)) or (castToBool(b) false and Sem(z,w′,out)). The selector b is any byte string (not only [0x01] / []), with no length bound.
- andor(x,y,z): ∃wx,vx with Sem(x,wx,[vx]) and either (castToBool(vx) true and ∃wy with w=wx++wy and Sem(y,wy,out)) or (castToBool(vx) false and ∃wz with w=wx++wz and Sem(z,wz,out)).
- multi(k,keys): ∃ a list sigs, a byte string dummy and a boolean ok with w=sigs++[dummy] (the dummy is the deepest witness element), ∣sigs∣=k, multisigLoopo(sigs,reverse(keys))=some(ok) (keys taken last-listed first), (f.nulldummy true ⇒dummy=[]), and out=[boolBytes(ok)]. Both ok true and false are allowed.
- wrap_a(x): Sem(x,w,out).
- wrap_s(x): Sem(x,w,out).
- wrap_c(x): ∃κ,sig,ok with Sem(x,w,[κ,sig]), o.checkSig(sig,κ)=some(ok) and out=[boolBytes(ok)] (ok may be false).
- wrap_d(x): either (w=[[0x01]], Sem(x,[],[]) and out=[[0x01]]) or (w=[[]] and out=[[]]). The selector must be exactly the one-byte string [0x01] or exactly the empty string.
- wrap_v(x): ∃v with Sem(x,w,[v]), castToBool(v) true, and out=[].
- wrap_j(x): either (w=e::w′ for some e,w′ with e=[], ∣e∣≤520, and Sem(x,w,out) — note x receives the whole w, including e) or (w=[[]] and out=[[]]).
- wrap_n(x): ∃v with Sem(x,w,[v]) and out=[boolBytes(castToBool(v))].
GoodVal(v), for a byte string v: there is an integer n with 0≤n<231 and v=serialize(n). (So [] (n=0) and [0x01] (n=1) qualify; negative encodings, non-minimal encodings such as [0x00] or [0x80], and strings longer than 4 bytes do not.)
Confirmed by the moderator at approval.