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.typeOf_sound
Statement. For every fragment m and every type t∈{B,V,K,W}: if the checker returns typeOf(m)=some(t), then HasType(m,t). (Only this direction is asserted; nothing is said about fragments for which typeOf returns none, nor about uniqueness of types.)
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.
typeOf(m)∈{none}∪{some(t):t∈Ty}, a recursive checker:
- pk_k(κ): some(K) if ∣κ∣≤520, else none. pk_h(h): some(K) if ∣h∣≤520, else none.
- older(n), after(n): some(B) if 1≤n<231, else none.
- sha256(h), hash256(h), ripemd160(h), hash160(h): some(B) if ∣h∣≤520, else none.
- and_v(x,y): if typeOf(x)= some(V) and typeOf(y)= some(t) with t=W, then some(t); otherwise none.
- and_b(x,y): some(B) if typeOf(x)= some(B) and typeOf(y)= some(W); otherwise none.
- or_b(x,z): some(B) if x checks to B, z to W, and dx∧dz; otherwise none.
- or_c(x,z): some(V) if x checks to B, z to V, and dx∧ux; otherwise none.
- or_d(x,z): some(B) if x and z both check to B and dx∧ux; otherwise none.
- or_i(x,z): if x checks to some(tx), z to some(tz), tx=tz and tx=W, then some(tx); otherwise none.
- andor(x,y,z): if x checks to B, y to some(ty), z to some(tz), and dx, ux, ty=tz, ty=W all hold, then some(ty); otherwise none.
- multi(k,keys): some(B) if 1≤k≤∣keys∣≤20 and all keys have length ≤520; otherwise none.
- wrap_a(x): some(W) if x checks to B. wrap_s(x): some(W) if x checks to B and ox. wrap_c(x): some(B) if x checks to K. wrap_d(x): some(B) if x checks to V and zx. wrap_v(x): some(V) if x checks to B. wrap_j(x): some(B) if x checks to B and nx. wrap_n(x): some(B) if x checks to B. In every other case: none.
(Here "checks to t" means typeOf returns some(t), and dx etc. are components of props(x).)
Confirmed by the moderator at approval.