Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A typed fragment in a non-executing branch is skipped

Proved
BitcoinMiniscript.compile_skip

by pitimespi · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitcoinbitcoin-mainnetcompiler-correctnessformal-verificationminiscriptpolicyscripttype-system

For a well-typed fragment and a state whose condition stack is not all true, with room for its operations: runSeq over compile m leaves the stacks and condition stack unchanged and adds at most opsMax m to the operation count.

Preamble
import Definitions.Def_BitcoinMiniscript
import Definitions.Def_BitcoinScript
open BitcoinMiniscript BitcoinToLocal BitcoinHtlc BitcoinScript BitcoinSig BitcoinVerify
Formal statement
theorem BitcoinMiniscript.compile_skip (f : BitcoinScript.Flags) (o : BitcoinScript.Oracle) (m : BitcoinMiniscript.Ms)
    (ty : BitcoinMiniscript.Ty) (ht : BitcoinMiniscript.HasType m ty) (st alt : List BitcoinScript.Bytes)
    (vf : List Bool) (k : Nat) (hvf : BitcoinScript.allTrue vf = false)
    (hk : k + BitcoinMiniscript.opsMax m ≤ BitcoinScript.MAX_OPS_PER_SCRIPT)
    (hsz : st.length + alt.length ≤ BitcoinScript.MAX_STACK_SIZE) :
    ∃ k', BitcoinMiniscript.runSeq f o ⟨st, alt, vf, k⟩ (BitcoinMiniscript.compile m) = some ⟨st, alt, vf, k'⟩ ∧
      k' ≤ k + BitcoinMiniscript.opsMax m := by sorry
Source
Miniscript reference (P. Wuille, A. Poelstra, S. Kanjalkar): translation table, type system and correctness/malleability properties, https://bitcoin.sipa.be/miniscript/; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: src/script/miniscript.h, src/script/miniscript.cpp (https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/miniscript.h); EvalScript (src/script/interpreter.cpp)
Read-back

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_skip

Statement. Let fff be any flags, ooo any oracle (arbitrary functions, see below), mmm any fragment and ttt any of the four types B,V,K,W\mathsf{B},\mathsf{V},\mathsf{K},\mathsf{W}B,V,K,W such that HasType(m,t)\mathrm{HasType}(m, t)HasType(m,t) holds. Let st\mathit{st}st and alt\mathit{alt}alt be any lists of byte strings (main stack and alt stack, top first; their elements may have any length), vf\mathit{vf}vf any list of booleans, and k∈Nk \in \mathbb{N}k∈N. Assume

  • allTrue(vf)=false\mathrm{allTrue}(\mathit{vf}) = \text{false}allTrue(vf)=false, i.e. vf\mathit{vf}vf contains at least one entry false (so vf\mathit{vf}vf is nonempty and the interpreter is in a non-executing branch);
  • k+opsMax(m)≤201k + \mathrm{opsMax}(m) \le 201k+opsMax(m)≤201 (the current operation counter plus the static bound opsMax(m)\mathrm{opsMax}(m)opsMax(m) is at most MAX_OPS_PER_SCRIPT\mathrm{MAX\_OPS\_PER\_SCRIPT}MAX_OPS_PER_SCRIPT);
  • ∣st∣+∣alt∣≤1000|\mathit{st}| + |\mathit{alt}| \le 1000∣st∣+∣alt∣≤1000 (the number of elements on the two stacks is at most MAX_STACK_SIZE\mathrm{MAX\_STACK\_SIZE}MAX_STACK_SIZE).

Then there exists k′∈Nk' \in \mathbb{N}k′∈N such that

runSeqf,o((st,alt,vf,k), compile(m))=some((st,alt,vf,k′))andk′≤k+opsMax(m).\mathrm{runSeq}_{f,o}\big((\mathit{st}, \mathit{alt}, \mathit{vf}, k),\ \mathrm{compile}(m)\big) = \text{some}\big((\mathit{st}, \mathit{alt}, \mathit{vf}, k')\big) \quad\text{and}\quad k' \le k + \mathrm{opsMax}(m).runSeqf,o​((st,alt,vf,k), compile(m))=some((st,alt,vf,k′))andk′≤k+opsMax(m).

That is, executing the compiled script instruction by instruction from that state never fails, and ends in a state with exactly the same main stack, alt stack and condition stack, and an operation counter k′k'k′ that is at most k+opsMax(m)k + \mathrm{opsMax}(m)k+opsMax(m) (no lower bound on k′k'k′ is stated). The type ttt itself does not appear in the conclusion.

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\mathtt{0x00}0x00–0xff\mathtt{0xff}0xff); [ ][\,][] is the empty byte string and ∣b∣|b|∣b∣ the length of bbb. Stacks, witnesses and outputs are finite lists of byte strings written top element first. For such lists, x::lx :: lx::l is the list with xxx placed on top of lll, l1+ ⁣ ⁣+l2l_1 \mathbin{+\!\!+} l_2l1​++l2​ is concatenation (in w+ ⁣ ⁣+restw \mathbin{+\!\!+} \mathit{rest}w++rest all elements of www lie above all elements of rest\mathit{rest}rest, the first element of www being the top of the stack), and ∣l∣|l|∣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.\mathrm{MAX\_SCRIPT\_ELEMENT\_SIZE}=520,\quad \mathrm{MAX\_OPS\_PER\_SCRIPT}=201,\quad \mathrm{MAX\_PUBKEYS\_PER\_MULTISIG}=20,\quad \mathrm{MAX\_STACK\_SIZE}=1000.MAX_SCRIPT_ELEMENT_SIZE=520,MAX_OPS_PER_SCRIPT=201,MAX_PUBKEYS_PER_MULTISIG=20,MAX_STACK_SIZE=1000.

castToBool\mathrm{castToBool}castToBool. For a byte string: castToBool([ ])=false\mathrm{castToBool}([\,])=\text{false}castToBool([])=false; castToBool([b0])=(b0≠0x00∧b0≠0x80)\mathrm{castToBool}([b_0]) = (b_0\neq \mathtt{0x00} \wedge b_0 \neq \mathtt{0x80})castToBool([b0​])=(b0​=0x00∧b0​=0x80); for a string with at least two bytes, castToBool(b0::r)=(b0≠0)∨castToBool(r)\mathrm{castToBool}(b_0 :: r) = (b_0 \neq 0) \vee \mathrm{castToBool}(r)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\mathtt{0x00}0x00 nor 0x80\mathtt{0x80}0x80; the empty string, all-zero strings, and strings of zero bytes followed by a final 0x80\mathtt{0x80}0x80 are false.

boolBytes\mathrm{boolBytes}boolBytes. boolBytes(true)=[0x01]\mathrm{boolBytes}(\text{true}) = [\mathtt{0x01}]boolBytes(true)=[0x01], boolBytes(false)=[ ]\mathrm{boolBytes}(\text{false}) = [\,]boolBytes(false)=[].

serialize\mathrm{serialize}serialize (script-number encoding of an integer nnn). serialize(0)=[ ]\mathrm{serialize}(0) = [\,]serialize(0)=[]. For n≠0n\neq 0n=0, let mag\mathit{mag}mag be the little-endian base-256 digits of ∣n∣|n|∣n∣ with no most-significant zero bytes. If the last (most significant) byte of mag\mathit{mag}mag has bit 0x80\mathtt{0x80}0x80 set, the result is mag\mathit{mag}mag followed by one extra byte, 0x80\mathtt{0x80}0x80 if n<0n<0n<0 and 0x00\mathtt{0x00}0x00 if n>0n>0n>0; otherwise the result is mag\mathit{mag}mag with bit 0x80\mathtt{0x80}0x80 of its last byte set if n<0n<0n<0, and mag\mathit{mag}mag itself if n>0n>0n>0. Examples: serialize(1)=[0x01]\mathrm{serialize}(1)=[\mathtt{0x01}]serialize(1)=[0x01], serialize(−1)=[0x81]\mathrm{serialize}(-1)=[\mathtt{0x81}]serialize(−1)=[0x81], serialize(32)=[0x20]\mathrm{serialize}(32)=[\mathtt{0x20}]serialize(32)=[0x20], serialize(128)=[0x80,0x00]\mathrm{serialize}(128)=[\mathtt{0x80},\mathtt{0x00}]serialize(128)=[0x80,0x00], serialize(231−1)=[0xff,0xff,0xff,0x7f]\mathrm{serialize}(2^{31}-1)=[\mathtt{0xff},\mathtt{0xff},\mathtt{0xff},\mathtt{0x7f}]serialize(231−1)=[0xff,0xff,0xff,0x7f].

Flags fff. A record of three independent booleans f.cltvf.\mathrm{cltv}f.cltv, f.csvf.\mathrm{csv}f.csv, f.nulldummyf.\mathrm{nulldummy}f.nulldummy; every combination is allowed.

Oracle ooo. 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.hash256o.\mathrm{ripemd160},\ o.\mathrm{sha1},\ o.\mathrm{sha256},\ o.\mathrm{hash160},\ o.\mathrm{hash256}o.ripemd160, o.sha1, o.sha256, o.hash160, o.hash256: byte strings →\to→ byte strings;
  • o.checkSig(sig,pubkey)∈{none,some(true),some(false)}o.\mathrm{checkSig}(\mathit{sig}, \mathit{pubkey}) \in \{\text{none}, \text{some}(\text{true}), \text{some}(\text{false})\}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.checkSequenceo.\mathrm{checkLockTime},\ o.\mathrm{checkSequence}o.checkLockTime, o.checkSequence: integers →\to→ booleans.

multisigLoopo(sigs,keys)\mathrm{multisigLoop}_o(\mathit{sigs}, \mathit{keys})multisigLoopo​(sigs,keys) (both lists top-first), with result none, some(true) or some(false):

  • if sigs=[ ]\mathit{sigs} = [\,]sigs=[]: some(true);
  • if sigs\mathit{sigs}sigs is nonempty and keys=[ ]\mathit{keys} = [\,]keys=[]: some(false);
  • if sigs=s::S\mathit{sigs} = s :: Ssigs=s::S and keys=k::K\mathit{keys} = k :: Kkeys=k::K: compute o.checkSig(s,k)o.\mathrm{checkSig}(s, k)o.checkSig(s,k). If none, the result is none. If some(true): the result is some(false) when ∣K∣<∣S∣|K| < |S|∣K∣<∣S∣, and otherwise multisigLoopo(S,K)\mathrm{multisigLoop}_o(S, K)multisigLoopo​(S,K). If some(false): the result is some(false) when ∣K∣<∣S∣+1|K| < |S| + 1∣K∣<∣S∣+1, and otherwise multisigLoopo(s::S,K)\mathrm{multisigLoop}_o(s :: S, K)multisigLoopo​(s::S,K).

The script interpreter (from the script-interpreter preamble)

Instructions and scripts. An instruction is either push(d)\mathrm{push}(d)push(d) for a byte string ddd, or op(c)\mathrm{op}(c)op(c) for an opcode byte ccc. A script is a finite list of instructions. Opcode bytes used below: OP_1NEGATE =0x4f=\mathtt{0x4f}=0x4f, OP_RESERVED =0x50=\mathtt{0x50}=0x50, OP_1…OP_16 =0x51=\mathtt{0x51}=0x51…0x60\mathtt{0x60}0x60, OP_NOP =0x61=\mathtt{0x61}=0x61, OP_IF =0x63=\mathtt{0x63}=0x63, OP_NOTIF =0x64=\mathtt{0x64}=0x64, OP_ELSE =0x67=\mathtt{0x67}=0x67, OP_ENDIF =0x68=\mathtt{0x68}=0x68, OP_VERIFY =0x69=\mathtt{0x69}=0x69, OP_RETURN =0x6a=\mathtt{0x6a}=0x6a, OP_TOALTSTACK =0x6b=\mathtt{0x6b}=0x6b, OP_FROMALTSTACK =0x6c=\mathtt{0x6c}=0x6c, OP_IFDUP =0x73=\mathtt{0x73}=0x73, OP_DUP =0x76=\mathtt{0x76}=0x76, OP_SWAP =0x7c=\mathtt{0x7c}=0x7c, OP_SIZE =0x82=\mathtt{0x82}=0x82, OP_EQUAL =0x87=\mathtt{0x87}=0x87, OP_EQUALVERIFY =0x88=\mathtt{0x88}=0x88, OP_0NOTEQUAL =0x92=\mathtt{0x92}=0x92, OP_BOOLAND =0x9a=\mathtt{0x9a}=0x9a, OP_BOOLOR =0x9b=\mathtt{0x9b}=0x9b, OP_RIPEMD160 =0xa6=\mathtt{0xa6}=0xa6, OP_SHA1 =0xa7=\mathtt{0xa7}=0xa7, OP_SHA256 =0xa8=\mathtt{0xa8}=0xa8, OP_HASH160 =0xa9=\mathtt{0xa9}=0xa9, OP_HASH256 =0xaa=\mathtt{0xaa}=0xaa, OP_CODESEPARATOR =0xab=\mathtt{0xab}=0xab, OP_CHECKSIG =0xac=\mathtt{0xac}=0xac, OP_CHECKSIGVERIFY =0xad=\mathtt{0xad}=0xad, OP_CHECKMULTISIG =0xae=\mathtt{0xae}=0xae, OP_CHECKMULTISIGVERIFY =0xaf=\mathtt{0xaf}=0xaf, OP_NOP1 =0xb0=\mathtt{0xb0}=0xb0, OP_CHECKLOCKTIMEVERIFY =0xb1=\mathtt{0xb1}=0xb1, OP_CHECKSEQUENCEVERIFY =0xb2=\mathtt{0xb2}=0xb2, OP_NOP4…OP_NOP10 =0xb3=\mathtt{0xb3}=0xb3…0xb9\mathtt{0xb9}0xb9 (plus the other standard stack/arithmetic opcodes named below).

opsIn(sc)\mathrm{opsIn}(\mathit{sc})opsIn(sc) is the number of instructions op(c)\mathrm{op}(c)op(c) in the script sc\mathit{sc}sc with c>0x60c > \mathtt{0x60}c>0x60 (pushes and opcodes ≤0x60\le \mathtt{0x60}≤0x60 are not counted).

States. A state is a quadruple (stack,alt,vf,k)(\mathit{stack}, \mathit{alt}, \mathit{vf}, k)(stack,alt,vf,k): the main stack and the alt stack (lists of byte strings, top first), the condition stack vf\mathit{vf}vf (a list of booleans, innermost first) and the operation counter k∈Nk\in\mathbb{N}k∈N. initial(st)=(st,[ ],[ ],0)\mathrm{initial}(\mathit{st}) = (\mathit{st}, [\,], [\,], 0)initial(st)=(st,[],[],0). allTrue(vf)\mathrm{allTrue}(\mathit{vf})allTrue(vf) means every entry of vf\mathit{vf}vf is true (so it is true for vf=[ ]\mathit{vf} = [\,]vf=[], and false exactly when vf\mathit{vf}vf contains at least one false). The state is executing when allTrue(vf)\mathrm{allTrue}(\mathit{vf})allTrue(vf).

Decoding numbers. "Decode vvv with limit LLL" fails if ∣v∣>L|v| > L∣v∣>L; otherwise it gives the sign–magnitude little-endian value of vvv: if the last byte has bit 0x80\mathtt{0x80}0x80 set, minus the little-endian value of vvv with that bit cleared, else the little-endian value of vvv ([ ][\,][] decodes to 000). No minimal-encoding requirement is applied anywhere.

stepf,o(s,i)\mathrm{step}_{f,o}(s, i)stepf,o​(s,i) — one instruction; result is a new state or failure.

  • i=push(d)i = \mathrm{push}(d)i=push(d): fail if ∣d∣>520|d| > 520∣d∣>520. If executing, put ddd on top of the main stack; otherwise leave the state unchanged. Then fail if ∣stack∣+∣alt∣>1000|\mathit{stack}| + |\mathit{alt}| > 1000∣stack∣+∣alt∣>1000.
  • i=op(c)i = \mathrm{op}(c)i=op(c): (1) if c>0x60c > \mathtt{0x60}c>0x60 and k+1>201k + 1 > 201k+1>201, fail; if c>0x60c > \mathtt{0x60}c>0x60, increase kkk by one (this happens also in non-executed branches). (2) If ccc 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\mathtt{0x63} \le c \le \mathtt{0x68}0x63≤c≤0x68, apply execOp\mathrm{execOp}execOp (below, with the flag "executing" passed in); fail if it fails, and otherwise fail if the resulting ∣stack∣+∣alt∣>1000|\mathit{stack}| + |\mathit{alt}| > 1000∣stack∣+∣alt∣>1000. (4) Otherwise the state is unchanged apart from kkk, and it fails if ∣stack∣+∣alt∣>1000|\mathit{stack}| + |\mathit{alt}| > 1000∣stack∣+∣alt∣>1000.

execOpf,o(fExec,c,s)\mathrm{execOp}_{f,o}(\mathit{fExec}, c, s)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)\mathrm{serialize}(c - \mathtt{0x50})serialize(c−0x50), i.e. of −1,1,…,16-1, 1, \dots, 16−1,1,…,16.
  • OP_NOP, OP_NOP1, OP_NOP4…OP_NOP10, OP_CODESEPARATOR: no change.
  • OP_CHECKLOCKTIMEVERIFY: if f.cltvf.\mathrm{cltv}f.cltv is false, no change. Otherwise decode the top with limit 555 (not removing it); fail if that fails, if the value n<0n<0n<0, or if o.checkLockTime(n)o.\mathrm{checkLockTime}(n)o.checkLockTime(n) is false; else no change.
  • OP_CHECKSEQUENCEVERIFY: if f.csvf.\mathrm{csv}f.csv is false, no change. Otherwise decode the top with limit 555 (not removing it); fail if that fails or n<0n < 0n<0; if bit 2312^{31}231 of nnn is set, no change; otherwise fail if o.checkSequence(n)o.\mathrm{checkSequence}(n)o.checkSequence(n) is false, else no change.
  • OP_IF / OP_NOTIF: if fExec\mathit{fExec}fExec, remove the top ttt and put castToBool(t)\mathrm{castToBool}(t)castToBool(t) (negated for OP_NOTIF) in front of vf\mathit{vf}vf; if not fExec\mathit{fExec}fExec, put false in front of vf\mathit{vf}vf and leave the stack alone.
  • OP_ELSE: fail if vf\mathit{vf}vf is empty, else negate its first entry. OP_ENDIF: fail if vf\mathit{vf}vf is empty, else remove its first entry.
  • OP_VERIFY: remove the top; fail if castToBool\mathrm{castToBool}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\mathrm{castToBool}castToBool of it is true, else no change. OP_DEPTH: push serialize(∣stack∣)\mathrm{serialize}(|\mathit{stack}|)serialize(∣stack∣). OP_PICK/OP_ROLL: remove the top, decode it (limit 444) as nnn, require a nonempty remainder with 0≤n<0 \le n <0≤n< its length, and copy (PICK) or move (ROLL) its element of index nnn (0 = top) to the top.
  • OP_SIZE: push serialize(∣t∣)\mathrm{serialize}(|t|)serialize(∣t∣) for the top ttt, which stays.
  • OP_EQUAL / OP_EQUALVERIFY: remove the top aaa and second bbb; OP_EQUAL pushes boolBytes(a=b)\mathrm{boolBytes}(a=b)boolBytes(a=b); OP_EQUALVERIFY fails unless a=ba=ba=b.
  • OP_1ADD, OP_1SUB, OP_NEGATE, OP_ABS, OP_NOT, OP_0NOTEQUAL: remove the top, decode it with limit 444 as nnn (fail if longer), push serialize\mathrm{serialize}serialize of n+1n+1n+1, n−1n-1n−1, −n-n−n, ∣n∣|n|∣n∣, (111 if n=0n=0n=0 else 000), (111 if n≠0n\neq 0n=0 else 000) 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 aaa and second bbb, decode n1n_1n1​ from bbb and n2n_2n2​ from aaa with limit 444 (fail if either is longer), and push serialize\mathrm{serialize}serialize of the result: n1+n2n_1+n_2n1​+n2​, n1−n2n_1-n_2n1​−n2​, (111 if n1≠0n_1\neq0n1​=0 and n2≠0n_2\neq 0n2​=0 else 000), (111 if n1≠0n_1\neq 0n1​=0 or n2≠0n_2\neq0n2​=0 else 000), and 1/01/01/0 for =,=,≠,<,>,≤,≥=,=,\neq,<,>,\le,\ge=,=,=,<,>,≤,≥, then min⁡\minmin, max⁡\maxmax; OP_NUMEQUALVERIFY pushes nothing and fails unless n1=n2n_1 = n_2n1​=n2​.
  • OP_WITHIN: remove three elements aaa (top), bbb, ddd, decode each with limit 444, push boolBytes(b≤d<a)\mathrm{boolBytes}(b \le d < a)boolBytes(b≤d<a) of the decoded values.
  • OP_RIPEMD160, OP_SHA1, OP_SHA256, OP_HASH160, OP_HASH256: replace the top ttt by o.ripemd160(t)o.\mathrm{ripemd160}(t)o.ripemd160(t), o.sha1(t)o.\mathrm{sha1}(t)o.sha1(t), o.sha256(t)o.\mathrm{sha256}(t)o.sha256(t), o.hash160(t)o.\mathrm{hash160}(t)o.hash160(t), o.hash256(t)o.\mathrm{hash256}(t)o.hash256(t) respectively.
  • OP_CHECKSIG / OP_CHECKSIGVERIFY: with pubkey\mathit{pubkey}pubkey the top and sig\mathit{sig}sig the second, let r=o.checkSig(sig,pubkey)r = o.\mathrm{checkSig}(\mathit{sig}, \mathit{pubkey})r=o.checkSig(sig,pubkey); fail if rrr is none; OP_CHECKSIG replaces both by boolBytes(r)\mathrm{boolBytes}(r)boolBytes(r); OP_CHECKSIGVERIFY removes both and fails unless rrr is true.
  • OP_CHECKMULTISIG / OP_CHECKMULTISIGVERIFY: remove the top and decode it (limit 444) as nKn_KnK​; fail if nK<0n_K<0nK​<0 or nK>20n_K>20nK​>20; let k′=k+nKk' = k + n_Kk′=k+nK​ and fail if k′>201k' > 201k′>201; the next nKn_KnK​ elements (top-first) are the keys (fail if fewer); the following element is decoded (limit 444) as nSn_SnS​, failing if absent, if nS<0n_S<0nS​<0 or nS>nKn_S>n_KnS​>nK​; the next nSn_SnS​ elements (top-first) are the signatures (fail if fewer); let r=multisigLoopo(sigs,keys)r = \mathrm{multisigLoop}_o(\mathit{sigs}, \mathit{keys})r=multisigLoopo​(sigs,keys) and fail if none; one more element, the dummy, must be present and is removed; fail if f.nulldummyf.\mathrm{nulldummy}f.nulldummy is true and the dummy is not [ ][\,][]; the counter becomes k′k'k′; OP_CHECKMULTISIG pushes boolBytes(r)\mathrm{boolBytes}(r)boolBytes(r) onto what remains, the VERIFY form pushes nothing and fails unless rrr is true.
  • Every other byte (including OP_RESERVED, 0x65\mathtt{0x65}0x65, 0x66\mathtt{0x66}0x66 and any byte ≤0x4e\le \mathtt{0x4e}≤0x4e used as an opcode): fail.

runf,o(s,sc)\mathrm{run}_{f,o}(s, \mathit{sc})runf,o​(s,sc): run(s,[ ])\mathrm{run}(s, [\,])run(s,[]) is sss if its condition stack is empty and failure otherwise; run(s,i::sc′)\mathrm{run}(s, i :: \mathit{sc}')run(s,i::sc′) fails if step(s,i)\mathrm{step}(s,i)step(s,i) fails and is run(step(s,i),sc′)\mathrm{run}(\mathrm{step}(s,i), \mathit{sc}')run(step(s,i),sc′) otherwise.

evalScriptf,o(st,sc)\mathrm{evalScript}_{f,o}(\mathit{st}, \mathit{sc})evalScriptf,o​(st,sc): if run(initial(st),sc)\mathrm{run}(\mathrm{initial}(\mathit{st}), \mathit{sc})run(initial(st),sc) succeeds with final state s′s's′, the result is "some" of the main stack of s′s'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\mathit{st}st is not checked against any size limit.

runSeqf,o(s,sc)\mathrm{runSeq}_{f,o}(s, \mathit{sc})runSeqf,o​(s,sc) (defined in the Miniscript file): exactly like run\mathrm{run}run but without the final check: runSeq(s,[ ])=some(s)\mathrm{runSeq}(s, [\,]) = \text{some}(s)runSeq(s,[])=some(s) (whatever its condition stack), and runSeq(s,i::sc′)\mathrm{runSeq}(s, i :: \mathit{sc}')runSeq(s,i::sc′) fails if step(s,i)\mathrm{step}(s,i)step(s,i) fails and is runSeq(step(s,i),sc′)\mathrm{runSeq}(\mathrm{step}(s,i), \mathit{sc}')runSeq(step(s,i),sc′) otherwise.

Miniscript definitions used

numInstr(n)\mathrm{numInstr}(n)numInstr(n) (from the to_local preamble), for an integer nnn: if n=−1n = -1n=−1 or 1≤n≤161 \le n \le 161≤n≤16, it is the opcode instruction op(n+0x50)\mathrm{op}(n + \mathtt{0x50})op(n+0x50), i.e. OP_1NEGATE for −1-1−1 and OP_1…OP_16 for 1,…,161,\dots,161,…,16 (these opcodes are ≤0x60\le \mathtt{0x60}≤0x60, so they are not counted by the operation counter, and when executed they push serialize(n)\mathrm{serialize}(n)serialize(n)); otherwise it is push(serialize(n))\mathrm{push}(\mathrm{serialize}(n))push(serialize(n)) — in particular numInstr(0)=push([ ])\mathrm{numInstr}(0) = \mathrm{push}([\,])numInstr(0)=push([]), numInstr(32)=push([0x20])\mathrm{numInstr}(32) = \mathrm{push}([\mathtt{0x20}])numInstr(32)=push([0x20]), and numInstr(n)=push(serialize(n))\mathrm{numInstr}(n) = \mathrm{push}(\mathrm{serialize}(n))numInstr(n)=push(serialize(n)) for n≥17n \ge 17n≥17.

Miniscript fragments Ms\mathrm{Ms}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):

  1. pk_k(κ)\mathrm{pk\_k}(\kappa)pk_k(κ), κ\kappaκ a byte string (a key);
  2. pk_h(h)\mathrm{pk\_h}(h)pk_h(h), hhh a byte string (a key hash);
  3. older(n)\mathrm{older}(n)older(n), n∈Zn \in \mathbb{Z}n∈Z;
  4. after(n)\mathrm{after}(n)after(n), n∈Zn \in \mathbb{Z}n∈Z;
  5. sha256(h)\mathrm{sha256}(h)sha256(h), 6. hash256(h)\mathrm{hash256}(h)hash256(h), 7. ripemd160(h)\mathrm{ripemd160}(h)ripemd160(h), 8. hash160(h)\mathrm{hash160}(h)hash160(h), each with hhh a byte string;
  6. and_v(x,y)\mathrm{and\_v}(x, y)and_v(x,y), 10. and_b(x,y)\mathrm{and\_b}(x, y)and_b(x,y), with x,yx, yx,y fragments;
  7. or_b(x,z)\mathrm{or\_b}(x, z)or_b(x,z), 12. or_c(x,z)\mathrm{or\_c}(x, z)or_c(x,z), 13. or_d(x,z)\mathrm{or\_d}(x, z)or_d(x,z), 14. or_i(x,z)\mathrm{or\_i}(x, z)or_i(x,z), with x,zx, zx,z fragments;
  8. andor(x,y,z)\mathrm{andor}(x, y, z)andor(x,y,z), with x,y,zx, y, zx,y,z fragments;
  9. multi(k,keys)\mathrm{multi}(k, \mathit{keys})multi(k,keys), k∈Nk \in \mathbb{N}k∈N and keys\mathit{keys}keys a finite list of byte strings; 17.–23. the wrappers wrap_a(x)\mathrm{wrap\_a}(x)wrap_a(x), wrap_s(x)\mathrm{wrap\_s}(x)wrap_s(x), wrap_c(x)\mathrm{wrap\_c}(x)wrap_c(x), wrap_d(x)\mathrm{wrap\_d}(x)wrap_d(x), wrap_v(x)\mathrm{wrap\_v}(x)wrap_v(x), wrap_j(x)\mathrm{wrap\_j}(x)wrap_j(x), wrap_n(x)\mathrm{wrap\_n}(x)wrap_n(x), with xxx a fragment.

Two fragments are equal exactly when they are built identically.

compile(m)\mathrm{compile}(m)compile(m), the script of a fragment mmm, written C(m)C(m)C(m); opcode instructions are written by name, + ⁣ ⁣+\mathbin{+\!\!+}++ is concatenation of instruction lists:

  1. C(pk_k(κ))=[push(κ)]C(\mathrm{pk\_k}(\kappa)) = [\mathrm{push}(\kappa)]C(pk_k(κ))=[push(κ)].
  2. C(pk_h(h))=[C(\mathrm{pk\_h}(h)) = [C(pk_h(h))=[OP_DUP, OP_HASH160, push(h)\mathrm{push}(h)push(h), OP_EQUALVERIFY]]] (no OP_CHECKSIG).
  3. C(older(n))=[numInstr(n)C(\mathrm{older}(n)) = [\mathrm{numInstr}(n)C(older(n))=[numInstr(n), OP_CHECKSEQUENCEVERIFY]]].
  4. C(after(n))=[numInstr(n)C(\mathrm{after}(n)) = [\mathrm{numInstr}(n)C(after(n))=[numInstr(n), OP_CHECKLOCKTIMEVERIFY]]].
  5. C(sha256(h))=[C(\mathrm{sha256}(h)) = [C(sha256(h))=[OP_SIZE, numInstr(32)\mathrm{numInstr}(32)numInstr(32), OP_EQUALVERIFY, OP_SHA256, push(h)\mathrm{push}(h)push(h), OP_EQUAL]]].
  6. C(hash256(h))C(\mathrm{hash256}(h))C(hash256(h)): the same with OP_HASH256 in place of OP_SHA256.
  7. C(ripemd160(h))C(\mathrm{ripemd160}(h))C(ripemd160(h)): the same with OP_RIPEMD160 (the size check is still against 323232).
  8. C(hash160(h))C(\mathrm{hash160}(h))C(hash160(h)): the same with OP_HASH160 (the size check is still against 323232).
  9. C(and_v(x,y))=C(x)+ ⁣ ⁣+C(y)C(\mathrm{and\_v}(x,y)) = C(x) \mathbin{+\!\!+} C(y)C(and_v(x,y))=C(x)++C(y).
  10. C(and_b(x,y))=C(x)+ ⁣ ⁣+C(y)+ ⁣ ⁣+[C(\mathrm{and\_b}(x,y)) = C(x) \mathbin{+\!\!+} C(y) \mathbin{+\!\!+} [C(and_b(x,y))=C(x)++C(y)++[OP_BOOLAND]]].
  11. C(or_b(x,z))=C(x)+ ⁣ ⁣+C(z)+ ⁣ ⁣+[C(\mathrm{or\_b}(x,z)) = C(x) \mathbin{+\!\!+} C(z) \mathbin{+\!\!+} [C(or_b(x,z))=C(x)++C(z)++[OP_BOOLOR]]].
  12. C(or_c(x,z))=C(x)+ ⁣ ⁣+[C(\mathrm{or\_c}(x,z)) = C(x) \mathbin{+\!\!+} [C(or_c(x,z))=C(x)++[OP_NOTIF]+ ⁣ ⁣+C(z)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(z) \mathbin{+\!\!+} []++C(z)++[OP_ENDIF]]].
  13. C(or_d(x,z))=C(x)+ ⁣ ⁣+[C(\mathrm{or\_d}(x,z)) = C(x) \mathbin{+\!\!+} [C(or_d(x,z))=C(x)++[OP_IFDUP, OP_NOTIF]+ ⁣ ⁣+C(z)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(z) \mathbin{+\!\!+} []++C(z)++[OP_ENDIF]]].
  14. C(or_i(x,z))=[C(\mathrm{or\_i}(x,z)) = [C(or_i(x,z))=[OP_IF]+ ⁣ ⁣+C(x)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(x) \mathbin{+\!\!+} []++C(x)++[OP_ELSE]+ ⁣ ⁣+C(z)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(z) \mathbin{+\!\!+} []++C(z)++[OP_ENDIF]]].
  15. C(andor(x,y,z))=C(x)+ ⁣ ⁣+[C(\mathrm{andor}(x,y,z)) = C(x) \mathbin{+\!\!+} [C(andor(x,y,z))=C(x)++[OP_NOTIF]+ ⁣ ⁣+C(z)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(z) \mathbin{+\!\!+} []++C(z)++[OP_ELSE]+ ⁣ ⁣+C(y)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(y) \mathbin{+\!\!+} []++C(y)++[OP_ENDIF]]] (note zzz comes before yyy).
  16. C(multi(k,[κ1,…,κℓ]))=[numInstr(k),push(κ1),…,push(κℓ),numInstr(ℓ)C(\mathrm{multi}(k, [\kappa_1, \dots, \kappa_\ell])) = [\mathrm{numInstr}(k), \mathrm{push}(\kappa_1), \dots, \mathrm{push}(\kappa_\ell), \mathrm{numInstr}(\ell)C(multi(k,[κ1​,…,κℓ​]))=[numInstr(k),push(κ1​),…,push(κℓ​),numInstr(ℓ), OP_CHECKMULTISIG]]] (kkk and ℓ\ellℓ read as integers).
  17. C(wrap_a(x))=[C(\mathrm{wrap\_a}(x)) = [C(wrap_a(x))=[OP_TOALTSTACK]+ ⁣ ⁣+C(x)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(x) \mathbin{+\!\!+} []++C(x)++[OP_FROMALTSTACK]]].
  18. C(wrap_s(x))=[C(\mathrm{wrap\_s}(x)) = [C(wrap_s(x))=[OP_SWAP]+ ⁣ ⁣+C(x)] \mathbin{+\!\!+} C(x)]++C(x).
  19. C(wrap_c(x))=C(x)+ ⁣ ⁣+[C(\mathrm{wrap\_c}(x)) = C(x) \mathbin{+\!\!+} [C(wrap_c(x))=C(x)++[OP_CHECKSIG]]].
  20. C(wrap_d(x))=[C(\mathrm{wrap\_d}(x)) = [C(wrap_d(x))=[OP_DUP, OP_IF]+ ⁣ ⁣+C(x)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(x) \mathbin{+\!\!+} []++C(x)++[OP_ENDIF]]].
  21. C(wrap_v(x))=C(x)+ ⁣ ⁣+[C(\mathrm{wrap\_v}(x)) = C(x) \mathbin{+\!\!+} [C(wrap_v(x))=C(x)++[OP_VERIFY]]] (always a separate OP_VERIFY).
  22. C(wrap_j(x))=[C(\mathrm{wrap\_j}(x)) = [C(wrap_j(x))=[OP_SIZE, OP_0NOTEQUAL, OP_IF]+ ⁣ ⁣+C(x)+ ⁣ ⁣+[] \mathbin{+\!\!+} C(x) \mathbin{+\!\!+} []++C(x)++[OP_ENDIF]]].
  23. C(wrap_n(x))=C(x)+ ⁣ ⁣+[C(\mathrm{wrap\_n}(x)) = C(x) \mathbin{+\!\!+} [C(wrap_n(x))=C(x)++[OP_0NOTEQUAL]]].

Opcode bytes: OP_IF 0x63\mathtt{0x63}0x63, OP_NOTIF 0x64\mathtt{0x64}0x64, OP_ELSE 0x67\mathtt{0x67}0x67, OP_ENDIF 0x68\mathtt{0x68}0x68, OP_VERIFY 0x69\mathtt{0x69}0x69, OP_TOALTSTACK 0x6b\mathtt{0x6b}0x6b, OP_FROMALTSTACK 0x6c\mathtt{0x6c}0x6c, OP_IFDUP 0x73\mathtt{0x73}0x73, OP_DUP 0x76\mathtt{0x76}0x76, OP_SWAP 0x7c\mathtt{0x7c}0x7c, OP_SIZE 0x82\mathtt{0x82}0x82, OP_EQUAL 0x87\mathtt{0x87}0x87, OP_EQUALVERIFY 0x88\mathtt{0x88}0x88, OP_0NOTEQUAL 0x92\mathtt{0x92}0x92, OP_BOOLAND 0x9a\mathtt{0x9a}0x9a, OP_BOOLOR 0x9b\mathtt{0x9b}0x9b, OP_RIPEMD160 0xa6\mathtt{0xa6}0xa6, OP_SHA256 0xa8\mathtt{0xa8}0xa8, OP_HASH160 0xa9\mathtt{0xa9}0xa9, OP_HASH256 0xaa\mathtt{0xaa}0xaa, OP_CHECKSIG 0xac\mathtt{0xac}0xac, OP_CHECKMULTISIG 0xae\mathtt{0xae}0xae, OP_CHECKLOCKTIMEVERIFY 0xb1\mathtt{0xb1}0xb1, OP_CHECKSEQUENCEVERIFY 0xb2\mathtt{0xb2}0xb2.

size(m)∈N\mathrm{size}(m) \in \mathbb{N}size(m)∈N, defined by: size(pk_k(⋅))=1\mathrm{size}(\mathrm{pk\_k}(\cdot)) = 1size(pk_k(⋅))=1; size(pk_h(⋅))=4\mathrm{size}(\mathrm{pk\_h}(\cdot)) = 4size(pk_h(⋅))=4; size(older(⋅))=size(after(⋅))=2\mathrm{size}(\mathrm{older}(\cdot)) = \mathrm{size}(\mathrm{after}(\cdot)) = 2size(older(⋅))=size(after(⋅))=2; size\mathrm{size}size of each of sha256(⋅)\mathrm{sha256}(\cdot)sha256(⋅), hash256(⋅)\mathrm{hash256}(\cdot)hash256(⋅), ripemd160(⋅)\mathrm{ripemd160}(\cdot)ripemd160(⋅), hash160(⋅)\mathrm{hash160}(\cdot)hash160(⋅) is 666; size(and_v(x,y))=size(x)+size(y)\mathrm{size}(\mathrm{and\_v}(x,y)) = \mathrm{size}(x)+\mathrm{size}(y)size(and_v(x,y))=size(x)+size(y); size(and_b(x,y))=size(x)+size(y)+1\mathrm{size}(\mathrm{and\_b}(x,y)) = \mathrm{size}(x)+\mathrm{size}(y)+1size(and_b(x,y))=size(x)+size(y)+1; size(or_b(x,z))=size(x)+size(z)+1\mathrm{size}(\mathrm{or\_b}(x,z)) = \mathrm{size}(x)+\mathrm{size}(z)+1size(or_b(x,z))=size(x)+size(z)+1; size(or_c(x,z))=size(x)+size(z)+2\mathrm{size}(\mathrm{or\_c}(x,z)) = \mathrm{size}(x)+\mathrm{size}(z)+2size(or_c(x,z))=size(x)+size(z)+2; size(or_d(x,z))=size(or_i(x,z))=size(x)+size(z)+3\mathrm{size}(\mathrm{or\_d}(x,z)) = \mathrm{size}(\mathrm{or\_i}(x,z)) = \mathrm{size}(x)+\mathrm{size}(z)+3size(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\mathrm{size}(\mathrm{andor}(x,y,z)) = \mathrm{size}(x)+\mathrm{size}(y)+\mathrm{size}(z)+3size(andor(x,y,z))=size(x)+size(y)+size(z)+3; size(multi(k,keys))=∣keys∣+3\mathrm{size}(\mathrm{multi}(k,\mathit{keys})) = |\mathit{keys}| + 3size(multi(k,keys))=∣keys∣+3; size(wrap_a(x))=size(x)+2\mathrm{size}(\mathrm{wrap\_a}(x)) = \mathrm{size}(x)+2size(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\mathrm{size}(\mathrm{wrap\_s}(x)) = \mathrm{size}(\mathrm{wrap\_c}(x)) = \mathrm{size}(\mathrm{wrap\_v}(x)) = \mathrm{size}(\mathrm{wrap\_n}(x)) = \mathrm{size}(x)+1size(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\mathrm{size}(\mathrm{wrap\_d}(x)) = \mathrm{size}(x)+3size(wrap_d(x))=size(x)+3; size(wrap_j(x))=size(x)+4\mathrm{size}(\mathrm{wrap\_j}(x)) = \mathrm{size}(x)+4size(wrap_j(x))=size(x)+4.

opsMax(m)∈N\mathrm{opsMax}(m) \in \mathbb{N}opsMax(m)∈N, defined by: opsMax(pk_k(⋅))=0\mathrm{opsMax}(\mathrm{pk\_k}(\cdot)) = 0opsMax(pk_k(⋅))=0; opsMax(pk_h(⋅))=3\mathrm{opsMax}(\mathrm{pk\_h}(\cdot)) = 3opsMax(pk_h(⋅))=3; opsMax(older(⋅))=opsMax(after(⋅))=1\mathrm{opsMax}(\mathrm{older}(\cdot)) = \mathrm{opsMax}(\mathrm{after}(\cdot)) = 1opsMax(older(⋅))=opsMax(after(⋅))=1; opsMax\mathrm{opsMax}opsMax of each of sha256(⋅)\mathrm{sha256}(\cdot)sha256(⋅), hash256(⋅)\mathrm{hash256}(\cdot)hash256(⋅), ripemd160(⋅)\mathrm{ripemd160}(\cdot)ripemd160(⋅), hash160(⋅)\mathrm{hash160}(\cdot)hash160(⋅) is 444; opsMax(and_v(x,y))=opsMax(x)+opsMax(y)\mathrm{opsMax}(\mathrm{and\_v}(x,y)) = \mathrm{opsMax}(x)+\mathrm{opsMax}(y)opsMax(and_v(x,y))=opsMax(x)+opsMax(y); opsMax(and_b(x,y))=opsMax(x)+opsMax(y)+1\mathrm{opsMax}(\mathrm{and\_b}(x,y)) = \mathrm{opsMax}(x)+\mathrm{opsMax}(y)+1opsMax(and_b(x,y))=opsMax(x)+opsMax(y)+1; opsMax(or_b(x,z))=opsMax(x)+opsMax(z)+1\mathrm{opsMax}(\mathrm{or\_b}(x,z)) = \mathrm{opsMax}(x)+\mathrm{opsMax}(z)+1opsMax(or_b(x,z))=opsMax(x)+opsMax(z)+1; opsMax(or_c(x,z))=opsMax(x)+opsMax(z)+2\mathrm{opsMax}(\mathrm{or\_c}(x,z)) = \mathrm{opsMax}(x)+\mathrm{opsMax}(z)+2opsMax(or_c(x,z))=opsMax(x)+opsMax(z)+2; opsMax(or_d(x,z))=opsMax(or_i(x,z))=opsMax(x)+opsMax(z)+3\mathrm{opsMax}(\mathrm{or\_d}(x,z)) = \mathrm{opsMax}(\mathrm{or\_i}(x,z)) = \mathrm{opsMax}(x)+\mathrm{opsMax}(z)+3opsMax(or_d(x,z))=opsMax(or_i(x,z))=opsMax(x)+opsMax(z)+3; opsMax(andor(x,y,z))=opsMax(x)+opsMax(y)+opsMax(z)+3\mathrm{opsMax}(\mathrm{andor}(x,y,z)) = \mathrm{opsMax}(x)+\mathrm{opsMax}(y)+\mathrm{opsMax}(z)+3opsMax(andor(x,y,z))=opsMax(x)+opsMax(y)+opsMax(z)+3; opsMax(multi(k,keys))=∣keys∣+1\mathrm{opsMax}(\mathrm{multi}(k,\mathit{keys})) = |\mathit{keys}| + 1opsMax(multi(k,keys))=∣keys∣+1; opsMax(wrap_a(x))=opsMax(x)+2\mathrm{opsMax}(\mathrm{wrap\_a}(x)) = \mathrm{opsMax}(x)+2opsMax(wrap_a(x))=opsMax(x)+2; opsMax(wrap_s(x))=opsMax(wrap_c(x))=opsMax(wrap_v(x))=opsMax(wrap_n(x))=opsMax(x)+1\mathrm{opsMax}(\mathrm{wrap\_s}(x)) = \mathrm{opsMax}(\mathrm{wrap\_c}(x)) = \mathrm{opsMax}(\mathrm{wrap\_v}(x)) = \mathrm{opsMax}(\mathrm{wrap\_n}(x)) = \mathrm{opsMax}(x)+1opsMax(wrap_s(x))=opsMax(wrap_c(x))=opsMax(wrap_v(x))=opsMax(wrap_n(x))=opsMax(x)+1; opsMax(wrap_d(x))=opsMax(x)+3\mathrm{opsMax}(\mathrm{wrap\_d}(x)) = \mathrm{opsMax}(x)+3opsMax(wrap_d(x))=opsMax(x)+3; opsMax(wrap_j(x))=opsMax(x)+4\mathrm{opsMax}(\mathrm{wrap\_j}(x)) = \mathrm{opsMax}(x)+4opsMax(wrap_j(x))=opsMax(x)+4.

Correctness types Ty\mathrm{Ty}Ty. A four-element set {B,V,K,W}\{\mathsf{B}, \mathsf{V}, \mathsf{K}, \mathsf{W}\}{B,V,K,W} of distinct labels (no meaning is attached to them other than through the rules below).

Modifier records Props\mathrm{Props}Props. A record of five booleans (z,o,n,d,u)(z, o, n, d, u)(z,o,n,d,u).

props(m)=(z,o,n,d,u)\mathrm{props}(m) = (z, o, n, d, u)props(m)=(z,o,n,d,u), computed syntactically. Write zx,ox,nx,dx,uxz_x, o_x, n_x, d_x, u_xzx​,ox​,nx​,dx​,ux​ for the components of props(x)\mathrm{props}(x)props(x) (similarly for yyy, zzz), ∧,∨\wedge,\vee∧,∨ for boolean and/or, T/F for true/false. (The modifier letter ooo is unrelated to the oracle ooo, and the modifier letter zzz is unrelated to a sub-fragment named zzz; e.g. zzz_zzz​ is the zzz-modifier of the sub-fragment zzz.)

fragmentzzzooonnnddduuu
pk_k(κ)\mathrm{pk\_k}(\kappa)pk_k(κ)FTTTT
pk_h(h)\mathrm{pk\_h}(h)pk_h(h)FFTTT
older(n)\mathrm{older}(n)older(n), after(n)\mathrm{after}(n)after(n)TFFFF
sha256\mathrm{sha256}sha256, hash256\mathrm{hash256}hash256, ripemd160\mathrm{ripemd160}ripemd160, hash160\mathrm{hash160}hash160FTTTT
and_v(x,y)\mathrm{and\_v}(x,y)and_v(x,y)zx∧zyz_x\wedge z_yzx​∧zy​(zx∧oy)∨(ox∧zy)(z_x\wedge o_y)\vee(o_x\wedge z_y)(zx​∧oy​)∨(ox​∧zy​)nx∨(zx∧ny)n_x\vee(z_x\wedge n_y)nx​∨(zx​∧ny​)Fuyu_yuy​
and_b(x,y)\mathrm{and\_b}(x,y)and_b(x,y)zx∧zyz_x\wedge z_yzx​∧zy​(zx∧oy)∨(ox∧zy)(z_x\wedge o_y)\vee(o_x\wedge z_y)(zx​∧oy​)∨(ox​∧zy​)nx∨(zx∧ny)n_x\vee(z_x\wedge n_y)nx​∨(zx​∧ny​)dx∧dyd_x\wedge d_ydx​∧dy​T
or_b(x,z)\mathrm{or\_b}(x,z)or_b(x,z)zx∧zzz_x\wedge z_zzx​∧zz​(zx∧oz)∨(ox∧zz)(z_x\wedge o_z)\vee(o_x\wedge z_z)(zx​∧oz​)∨(ox​∧zz​)FTT
or_c(x,z)\mathrm{or\_c}(x,z)or_c(x,z)zx∧zzz_x\wedge z_zzx​∧zz​ox∧zzo_x\wedge z_zox​∧zz​FFF
or_d(x,z)\mathrm{or\_d}(x,z)or_d(x,z)zx∧zzz_x\wedge z_zzx​∧zz​ox∧zzo_x\wedge z_zox​∧zz​Fdzd_zdz​uzu_zuz​
or_i(x,z)\mathrm{or\_i}(x,z)or_i(x,z)Fzx∧zzz_x\wedge z_zzx​∧zz​Fdx∨dzd_x\vee d_zdx​∨dz​ux∧uzu_x\wedge u_zux​∧uz​
andor(x,y,z)\mathrm{andor}(x,y,z)andor(x,y,z)zx∧zy∧zzz_x\wedge z_y\wedge z_zzx​∧zy​∧zz​(zx∧oy∧oz)∨(ox∧zy∧zz)(z_x\wedge o_y\wedge o_z)\vee(o_x\wedge z_y\wedge z_z)(zx​∧oy​∧oz​)∨(ox​∧zy​∧zz​)Fdzd_zdz​uy∧uzu_y\wedge u_zuy​∧uz​
multi(k,keys)\mathrm{multi}(k,\mathit{keys})multi(k,keys)FFTTT
wrap_a(x)\mathrm{wrap\_a}(x)wrap_a(x)FFFdxd_xdx​uxu_xux​
wrap_s(x)\mathrm{wrap\_s}(x)wrap_s(x)Foxo_xox​Fdxd_xdx​uxu_xux​
wrap_c(x)\mathrm{wrap\_c}(x)wrap_c(x)Foxo_xox​nxn_xnx​dxd_xdx​T
wrap_d(x)\mathrm{wrap\_d}(x)wrap_d(x)FTTTF
wrap_v(x)\mathrm{wrap\_v}(x)wrap_v(x)zxz_xzx​oxo_xox​nxn_xnx​FF
wrap_j(x)\mathrm{wrap\_j}(x)wrap_j(x)Foxo_xox​TTuxu_xux​
wrap_n(x)\mathrm{wrap\_n}(x)wrap_n(x)zxz_xzx​oxo_xox​nxn_xnx​dxd_xdx​T

(The components do not depend on the byte-string, integer or list parameters of the leaves.)

HasType(m,t)\mathrm{HasType}(m, t)HasType(m,t), "mmm has type ttt", 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_SIZE520 = \mathrm{MAX\_SCRIPT\_ELEMENT\_SIZE}520=MAX_SCRIPT_ELEMENT_SIZE and 20=MAX_PUBKEYS_PER_MULTISIG20 = \mathrm{MAX\_PUBKEYS\_PER\_MULTISIG}20=MAX_PUBKEYS_PER_MULTISIG.

  1. pk_k(κ):K\mathrm{pk\_k}(\kappa) : \mathsf{K}pk_k(κ):K if ∣κ∣≤520|\kappa| \le 520∣κ∣≤520.
  2. pk_h(h):K\mathrm{pk\_h}(h) : \mathsf{K}pk_h(h):K if ∣h∣≤520|h| \le 520∣h∣≤520.
  3. older(n):B\mathrm{older}(n) : \mathsf{B}older(n):B if 1≤n<2311 \le n < 2^{31}1≤n<231.
  4. after(n):B\mathrm{after}(n) : \mathsf{B}after(n):B if 1≤n<2311 \le n < 2^{31}1≤n<231. 5.–8. sha256(h)\mathrm{sha256}(h)sha256(h), hash256(h)\mathrm{hash256}(h)hash256(h), ripemd160(h)\mathrm{ripemd160}(h)ripemd160(h), hash160(h)\mathrm{hash160}(h)hash160(h) :B: \mathsf{B}:B if ∣h∣≤520|h| \le 520∣h∣≤520 (no condition on ∣h∣|h|∣h∣ being any particular hash length).
  5. and_v(x,y):t\mathrm{and\_v}(x,y) : tand_v(x,y):t if x:Vx : \mathsf{V}x:V, y:ty : ty:t and t≠Wt \neq \mathsf{W}t=W.
  6. and_b(x,y):B\mathrm{and\_b}(x,y) : \mathsf{B}and_b(x,y):B if x:Bx : \mathsf{B}x:B and y:Wy : \mathsf{W}y:W.
  7. or_b(x,z):B\mathrm{or\_b}(x,z) : \mathsf{B}or_b(x,z):B if x:Bx : \mathsf{B}x:B, dxd_xdx​, z:Wz : \mathsf{W}z:W, dzd_zdz​.
  8. or_c(x,z):V\mathrm{or\_c}(x,z) : \mathsf{V}or_c(x,z):V if x:Bx : \mathsf{B}x:B, dxd_xdx​, uxu_xux​, z:Vz : \mathsf{V}z:V.
  9. or_d(x,z):B\mathrm{or\_d}(x,z) : \mathsf{B}or_d(x,z):B if x:Bx : \mathsf{B}x:B, dxd_xdx​, uxu_xux​, z:Bz : \mathsf{B}z:B.
  10. or_i(x,z):t\mathrm{or\_i}(x,z) : tor_i(x,z):t if x:tx : tx:t, z:tz : tz:t and t≠Wt \ne \mathsf{W}t=W.
  11. andor(x,y,z):t\mathrm{andor}(x,y,z) : tandor(x,y,z):t if x:Bx : \mathsf{B}x:B, dxd_xdx​, uxu_xux​, y:ty : ty:t, z:tz : tz:t and t≠Wt \ne \mathsf{W}t=W.
  12. multi(k,keys):B\mathrm{multi}(k, \mathit{keys}) : \mathsf{B}multi(k,keys):B if 1≤k≤∣keys∣≤201 \le k \le |\mathit{keys}| \le 201≤k≤∣keys∣≤20 and every key in keys\mathit{keys}keys has length ≤520\le 520≤520.
  13. wrap_a(x):W\mathrm{wrap\_a}(x) : \mathsf{W}wrap_a(x):W if x:Bx : \mathsf{B}x:B.
  14. wrap_s(x):W\mathrm{wrap\_s}(x) : \mathsf{W}wrap_s(x):W if x:Bx : \mathsf{B}x:B and oxo_xox​.
  15. wrap_c(x):B\mathrm{wrap\_c}(x) : \mathsf{B}wrap_c(x):B if x:Kx : \mathsf{K}x:K.
  16. wrap_d(x):B\mathrm{wrap\_d}(x) : \mathsf{B}wrap_d(x):B if x:Vx : \mathsf{V}x:V and zxz_xzx​.
  17. wrap_v(x):V\mathrm{wrap\_v}(x) : \mathsf{V}wrap_v(x):V if x:Bx : \mathsf{B}x:B.
  18. wrap_j(x):B\mathrm{wrap\_j}(x) : \mathsf{B}wrap_j(x):B if x:Bx : \mathsf{B}x:B and nxn_xnx​.
  19. wrap_n(x):B\mathrm{wrap\_n}(x) : \mathsf{B}wrap_n(x):B if x:Bx : \mathsf{B}x:B.

Here dxd_xdx​, uxu_xux​, oxo_xox​, zxz_xzx​, nxn_xnx​ mean the corresponding component of props(x)\mathrm{props}(x)props(x) is true. Read off the rules: type W\mathsf{W}W is concluded only by rules 17–18 (wrap_a\mathrm{wrap\_a}wrap_a, wrap_s\mathrm{wrap\_s}wrap_s); type K\mathsf{K}K only by rules 1, 2, 9 (with y:Ky : \mathsf{K}y:K), 14 and 15 (with both branches K\mathsf{K}K); type V\mathsf{V}V only by rules 9, 12, 14, 15, 21. No rule constrains the modifiers o,n,z,uo, n, z, uo,n,z,u of yyy or zzz beyond those listed, and no rule bounds the depth or total size of the fragment.

Human review
  • Endorsed by Shuze Chen · Oct 30, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 30, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me