Miniscript fragments, their translation to Script, the type system, and a satisfaction semantics
DefinitionBitcoinMiniscriptA Miniscript core over the script mission's interpreter.
Ms — 23 fragments: pk_k, pk_h, older, after, sha256, hash256, ripemd160, hash160, and_v, and_b, or_b, or_c, or_d, or_i, andor, multi, and the wrappers a:, s:, c:, d:, v:, j:, n:. compile — the reference's translation table into the script mission's instruction lists (numbers through CScript << int64; v: appends an explicit OP_VERIFY, the reference's folding into a preceding *VERIFY opcode is not modelled). size, opsMax — the instruction count and an upper bound on counted opcodes.
Ty — the basic types B, V, K, W; Props, props — the modifiers z, o, n, d, u computed by the reference's table; HasType — the typing rules (with size bounds on pushed data, 1 ≤ n < 2^31 for time locks, 1 ≤ k ≤ |keys| ≤ 20 for multi); typeOf — a decidable type checker.
Sem f o m w out — the witness w (top first) drives m to the output out left above the untouched stack: [v] for B/W (nonzero for a satisfaction, empty for a dissatisfaction), [] for V, [key, sig] for K. It follows the reference's satisfaction and dissatisfaction tables and includes the non-canonical combinations the script also accepts. Sat, Dsat, SatV — satisfaction (a true output), dissatisfaction (the empty output), and V satisfaction (no output). GoodVal v — v is the script number of some . runSeq — the interpreter's instruction loop without the final unbalanced-conditional check, so that it composes.
Formalization Note. numInstr, CsvPasses are the to_local mission's; CltvPasses the HTLC mission's; the interpreter, Oracle and Flags the script mission's. Only Std is imported.
import Definitions.Def_BitcoinHtlc
/-!
# A core of Miniscript under Bitcoin's script interpreter
Miniscript (https://bitcoin.sipa.be/miniscript/) is a structured language of spending
conditions, each fragment of which has a fixed translation to Bitcoin Script, a correctness type
(`B`, `V`, `K`, `W`) with type modifiers (`z o n d u`), and a satisfaction table describing the
witness stacks that make the translated script succeed. This file states, for a core subset of
the fragments, the language (`Ms`), the translation (`compile`), the correctness types and the
syntactic type modifiers (`Ty`, `props`, `HasType`), and a satisfaction semantics (`Sem`,
`Sat`, `Dsat`, `SatV`) over the abstract `Oracle` and `Flags` of the script interpreter, so that
the compiler can be proved sound: a witness that satisfies a well-typed fragment makes its
compiled script succeed in the interpreter `BitcoinScript.evalScript`.
Witness stacks are lists with the top element first, as `evalScript` takes them; the Miniscript
tables list witness elements in push order (last pushed on top), so `and_v(X,Y)`'s `satY satX`
is `wX ++ wY` here.
-/
namespace BitcoinMiniscript
open BitcoinScript BitcoinToLocal BitcoinHtlc
/-! ### The language -/
/-- The fragments of the core. The two key fragments `pk_k` and `pk_h` are of type `K` and
become `B` with the `c:` wrapper (`pk(key)` is `c:pk_k(key)`); `pk_h` carries the key hash. -/
inductive Ms where
| pk_k (key : Bytes)
| pk_h (keyHash : Bytes)
| older (n : Int)
| after (n : Int)
| sha256 (h : Bytes)
| hash256 (h : Bytes)
| ripemd160 (h : Bytes)
| hash160 (h : Bytes)
| and_v (x y : Ms)
| and_b (x y : Ms)
| or_b (x z : Ms)
| or_c (x z : Ms)
| or_d (x z : Ms)
| or_i (x z : Ms)
| andor (x y z : Ms)
| multi (k : Nat) (keys : List Bytes)
| wrap_a (x : Ms)
| wrap_s (x : Ms)
| wrap_c (x : Ms)
| wrap_d (x : Ms)
| wrap_v (x : Ms)
| wrap_j (x : Ms)
| wrap_n (x : Ms)
deriving DecidableEq, Repr
/-- The translation table. Numbers are pushed as `CScript << int64` (`BitcoinToLocal.numInstr`);
`v:` appends an explicit `OP_VERIFY` (the folding of `OP_VERIFY` into the preceding `*VERIFY`
opcode is not modeled). -/
def compile : Ms → Script
| .pk_k key => [.push key]
| .pk_h h => [.op OP_DUP] ++ [.op OP_HASH160] ++ [.push h] ++ [.op OP_EQUALVERIFY]
| .older n => [numInstr n] ++ [.op OP_CHECKSEQUENCEVERIFY]
| .after n => [numInstr n] ++ [.op OP_CHECKLOCKTIMEVERIFY]
| .sha256 h => [.op OP_SIZE] ++ [numInstr 32] ++ [.op OP_EQUALVERIFY] ++ [.op OP_SHA256] ++ [.push h] ++ [.op OP_EQUAL]
| .hash256 h => [.op OP_SIZE] ++ [numInstr 32] ++ [.op OP_EQUALVERIFY] ++ [.op OP_HASH256] ++ [.push h] ++ [.op OP_EQUAL]
| .ripemd160 h => [.op OP_SIZE] ++ [numInstr 32] ++ [.op OP_EQUALVERIFY] ++ [.op OP_RIPEMD160] ++ [.push h] ++ [.op OP_EQUAL]
| .hash160 h => [.op OP_SIZE] ++ [numInstr 32] ++ [.op OP_EQUALVERIFY] ++ [.op OP_HASH160] ++ [.push h] ++ [.op OP_EQUAL]
| .and_v x y => compile x ++ compile y
| .and_b x y => compile x ++ compile y ++ [.op OP_BOOLAND]
| .or_b x z => compile x ++ compile z ++ [.op OP_BOOLOR]
| .or_c x z => compile x ++ [.op OP_NOTIF] ++ compile z ++ [.op OP_ENDIF]
| .or_d x z => compile x ++ [.op OP_IFDUP] ++ [.op OP_NOTIF] ++ compile z ++ [.op OP_ENDIF]
| .or_i x z => [.op OP_IF] ++ compile x ++ [.op OP_ELSE] ++ compile z ++ [.op OP_ENDIF]
| .andor x y z => compile x ++ [.op OP_NOTIF] ++ compile z ++ [.op OP_ELSE] ++ compile y ++ [.op OP_ENDIF]
| .multi k keys => [numInstr k] ++ keys.map Instr.push ++ [numInstr keys.length] ++ [.op OP_CHECKMULTISIG]
| .wrap_a x => [.op OP_TOALTSTACK] ++ compile x ++ [.op OP_FROMALTSTACK]
| .wrap_s x => [.op OP_SWAP] ++ compile x
| .wrap_c x => compile x ++ [.op OP_CHECKSIG]
| .wrap_d x => [.op OP_DUP] ++ [.op OP_IF] ++ compile x ++ [.op OP_ENDIF]
| .wrap_v x => compile x ++ [.op OP_VERIFY]
| .wrap_j x => [.op OP_SIZE] ++ [.op OP_0NOTEQUAL] ++ [.op OP_IF] ++ compile x ++ [.op OP_ENDIF]
| .wrap_n x => compile x ++ [.op OP_0NOTEQUAL]
/-- The number of instructions of the translation; also a bound on the stack growth while it
runs, since every instruction used pushes at most one element. -/
def size : Ms → Nat
| .pk_k _ => 1
| .pk_h _ => 4
| .older _ => 2
| .after _ => 2
| .sha256 _ => 6
| .hash256 _ => 6
| .ripemd160 _ => 6
| .hash160 _ => 6
| .and_v x y => size x + size y
| .and_b x y => size x + size y + 1
| .or_b x z => size x + size z + 1
| .or_c x z => size x + size z + 2
| .or_d x z => size x + size z + 3
| .or_i x z => size x + size z + 3
| .andor x y z => size x + size y + size z + 3
| .multi _ keys => keys.length + 3
| .wrap_a x => size x + 2
| .wrap_s x => size x + 1
| .wrap_c x => size x + 1
| .wrap_d x => size x + 3
| .wrap_v x => size x + 1
| .wrap_j x => size x + 4
| .wrap_n x => size x + 1
/-- An upper bound on what the translation adds to `nOpCount`: its non-push opcodes above
`OP_16`, plus the number of keys for `OP_CHECKMULTISIG` (counted only when executed). -/
def opsMax : Ms → Nat
| .pk_k _ => 0
| .pk_h _ => 3
| .older _ => 1
| .after _ => 1
| .sha256 _ => 4
| .hash256 _ => 4
| .ripemd160 _ => 4
| .hash160 _ => 4
| .and_v x y => opsMax x + opsMax y
| .and_b x y => opsMax x + opsMax y + 1
| .or_b x z => opsMax x + opsMax z + 1
| .or_c x z => opsMax x + opsMax z + 2
| .or_d x z => opsMax x + opsMax z + 3
| .or_i x z => opsMax x + opsMax z + 3
| .andor x y z => opsMax x + opsMax y + opsMax z + 3
| .multi _ keys => keys.length + 1
| .wrap_a x => opsMax x + 2
| .wrap_s x => opsMax x + 1
| .wrap_c x => opsMax x + 1
| .wrap_d x => opsMax x + 3
| .wrap_v x => opsMax x + 1
| .wrap_j x => opsMax x + 4
| .wrap_n x => opsMax x + 1
/-! ### Types -/
/-- The correctness types: `B` (base: leaves a nonzero value or exactly `[]`), `V` (verify: leaves
nothing), `K` (key: leaves a public key above its signature), `W` (wrapped: a `B` that takes its
input from below the top element). -/
inductive Ty where
| B | V | K | W
deriving DecidableEq, Repr
/-- The type modifiers of the reference's correctness table: `z` (consumes no stack element),
`o` (consumes exactly one), `n` (the top consumed element is nonempty when satisfied), `d`
(has a dissatisfaction), `u` (satisfaction leaves exactly `1`). -/
structure Props where
z : Bool
o : Bool
n : Bool
d : Bool
u : Bool
deriving DecidableEq, Repr
/-- The modifiers of a fragment, computed syntactically by the reference's table. -/
def props : Ms → Props
| .pk_k _ => ⟨false, true, true, true, true⟩
| .pk_h _ => ⟨false, false, true, true, true⟩
| .older _ => ⟨true, false, false, false, false⟩
| .after _ => ⟨true, false, false, false, false⟩
| .sha256 _ => ⟨false, true, true, true, true⟩
| .hash256 _ => ⟨false, true, true, true, true⟩
| .ripemd160 _ => ⟨false, true, true, true, true⟩
| .hash160 _ => ⟨false, true, true, true, true⟩
| .and_v x y =>
let px := props x; let py := props y
⟨px.z && py.z, (px.z && py.o) || (px.o && py.z), px.n || (px.z && py.n), false, py.u⟩
| .and_b x y =>
let px := props x; let py := props y
⟨px.z && py.z, (px.z && py.o) || (px.o && py.z), px.n || (px.z && py.n), px.d && py.d, true⟩
| .or_b x z =>
let px := props x; let pz := props z
⟨px.z && pz.z, (px.z && pz.o) || (px.o && pz.z), false, true, true⟩
| .or_c x z =>
let px := props x; let pz := props z
⟨px.z && pz.z, px.o && pz.z, false, false, false⟩
| .or_d x z =>
let px := props x; let pz := props z
⟨px.z && pz.z, px.o && pz.z, false, pz.d, pz.u⟩
| .or_i x z =>
let px := props x; let pz := props z
⟨false, px.z && pz.z, false, px.d || pz.d, px.u && pz.u⟩
| .andor x y z =>
let px := props x; let py := props y; let pz := props z
⟨px.z && py.z && pz.z, (px.z && py.o && pz.o) || (px.o && py.z && pz.z), false, pz.d, py.u && pz.u⟩
| .multi _ _ => ⟨false, false, true, true, true⟩
| .wrap_a x => let px := props x; ⟨false, false, false, px.d, px.u⟩
| .wrap_s x => let px := props x; ⟨false, px.o, false, px.d, px.u⟩
| .wrap_c x => let px := props x; ⟨false, px.o, px.n, px.d, true⟩
| .wrap_d _ => ⟨false, true, true, true, false⟩
| .wrap_v x => let px := props x; ⟨px.z, px.o, px.n, false, false⟩
| .wrap_j x => let px := props x; ⟨false, px.o, true, true, px.u⟩
| .wrap_n x => let px := props x; ⟨px.z, px.o, px.n, px.d, true⟩
/-- The typing rules of the reference's correctness table, with the resource facts the
translation needs (pushed data within `MAX_SCRIPT_ELEMENT_SIZE`, time-lock operands in
`1 … 2^31 - 1`, at most `MAX_PUBKEYS_PER_MULTISIG` keys). -/
inductive HasType : Ms → Ty → Prop
| pk_k (key : Bytes) : key.length ≤ MAX_SCRIPT_ELEMENT_SIZE → HasType (.pk_k key) .K
| pk_h (h : Bytes) : h.length ≤ MAX_SCRIPT_ELEMENT_SIZE → HasType (.pk_h h) .K
| older (n : Int) : 1 ≤ n → n < 2 ^ 31 → HasType (.older n) .B
| after (n : Int) : 1 ≤ n → n < 2 ^ 31 → HasType (.after n) .B
| sha256 (h : Bytes) : h.length ≤ MAX_SCRIPT_ELEMENT_SIZE → HasType (.sha256 h) .B
| hash256 (h : Bytes) : h.length ≤ MAX_SCRIPT_ELEMENT_SIZE → HasType (.hash256 h) .B
| ripemd160 (h : Bytes) : h.length ≤ MAX_SCRIPT_ELEMENT_SIZE → HasType (.ripemd160 h) .B
| hash160 (h : Bytes) : h.length ≤ MAX_SCRIPT_ELEMENT_SIZE → HasType (.hash160 h) .B
| and_v {x y : Ms} {ty : Ty} : HasType x .V → HasType y ty → ty ≠ .W → HasType (.and_v x y) ty
| and_b {x y : Ms} : HasType x .B → HasType y .W → HasType (.and_b x y) .B
| or_b {x z : Ms} : HasType x .B → (props x).d = true → HasType z .W → (props z).d = true →
HasType (.or_b x z) .B
| or_c {x z : Ms} : HasType x .B → (props x).d = true → (props x).u = true → HasType z .V →
HasType (.or_c x z) .V
| or_d {x z : Ms} : HasType x .B → (props x).d = true → (props x).u = true → HasType z .B →
HasType (.or_d x z) .B
| or_i {x z : Ms} {ty : Ty} : HasType x ty → HasType z ty → ty ≠ .W → HasType (.or_i x z) ty
| andor {x y z : Ms} {ty : Ty} : HasType x .B → (props x).d = true → (props x).u = true →
HasType y ty → HasType z ty → ty ≠ .W → HasType (.andor x y z) ty
| multi (k : Nat) (keys : List Bytes) : 1 ≤ k → k ≤ keys.length →
keys.length ≤ MAX_PUBKEYS_PER_MULTISIG → (∀ key ∈ keys, key.length ≤ MAX_SCRIPT_ELEMENT_SIZE) →
HasType (.multi k keys) .B
| wrap_a {x : Ms} : HasType x .B → HasType (.wrap_a x) .W
| wrap_s {x : Ms} : HasType x .B → (props x).o = true → HasType (.wrap_s x) .W
| wrap_c {x : Ms} : HasType x .K → HasType (.wrap_c x) .B
| wrap_d {x : Ms} : HasType x .V → (props x).z = true → HasType (.wrap_d x) .B
| wrap_v {x : Ms} : HasType x .B → HasType (.wrap_v x) .V
| wrap_j {x : Ms} : HasType x .B → (props x).n = true → HasType (.wrap_j x) .B
| wrap_n {x : Ms} : HasType x .B → HasType (.wrap_n x) .B
/-- A decidable type checker for `HasType`: the type of a well-typed fragment, `none` otherwise
(`typeOf_sound` in the solutions shows `typeOf m = some ty → HasType m ty`). -/
def typeOf : Ms → Option Ty
| .pk_k key => if key.length ≤ MAX_SCRIPT_ELEMENT_SIZE then some .K else none
| .pk_h h => if h.length ≤ MAX_SCRIPT_ELEMENT_SIZE then some .K else none
| .older n => if 1 ≤ n ∧ n < 2 ^ 31 then some .B else none
| .after n => if 1 ≤ n ∧ n < 2 ^ 31 then some .B else none
| .sha256 h => if h.length ≤ MAX_SCRIPT_ELEMENT_SIZE then some .B else none
| .hash256 h => if h.length ≤ MAX_SCRIPT_ELEMENT_SIZE then some .B else none
| .ripemd160 h => if h.length ≤ MAX_SCRIPT_ELEMENT_SIZE then some .B else none
| .hash160 h => if h.length ≤ MAX_SCRIPT_ELEMENT_SIZE then some .B else none
| .and_v x y =>
match typeOf x, typeOf y with
| some .V, some ty => if ty ≠ .W then some ty else none
| _, _ => none
| .and_b x y =>
match typeOf x, typeOf y with
| some .B, some .W => some .B
| _, _ => none
| .or_b x z =>
match typeOf x, typeOf z with
| some .B, some .W => if (props x).d && (props z).d then some .B else none
| _, _ => none
| .or_c x z =>
match typeOf x, typeOf z with
| some .B, some .V => if (props x).d && (props x).u then some .V else none
| _, _ => none
| .or_d x z =>
match typeOf x, typeOf z with
| some .B, some .B => if (props x).d && (props x).u then some .B else none
| _, _ => none
| .or_i x z =>
match typeOf x, typeOf z with
| some tx, some tz => if tx = tz ∧ tx ≠ .W then some tx else none
| _, _ => none
| .andor x y z =>
match typeOf x, typeOf y, typeOf z with
| some .B, some ty, some tz =>
if (props x).d && (props x).u && decide (ty = tz) && decide (ty ≠ .W) then some ty else none
| _, _, _ => none
| .multi k keys =>
if 1 ≤ k ∧ k ≤ keys.length ∧ keys.length ≤ MAX_PUBKEYS_PER_MULTISIG ∧
keys.all (fun key => key.length ≤ MAX_SCRIPT_ELEMENT_SIZE) then some .B else none
| .wrap_a x => match typeOf x with | some .B => some .W | _ => none
| .wrap_s x => match typeOf x with | some .B => if (props x).o then some .W else none | _ => none
| .wrap_c x => match typeOf x with | some .K => some .B | _ => none
| .wrap_d x => match typeOf x with | some .V => if (props x).z then some .B else none | _ => none
| .wrap_v x => match typeOf x with | some .B => some .V | _ => none
| .wrap_j x => match typeOf x with | some .B => if (props x).n then some .B else none | _ => none
| .wrap_n x => match typeOf x with | some .B => some .B | _ => none
/-! ### Satisfaction semantics -/
/-- `Sem f o m w out`: the witness `w` (top first) drives the fragment `m` to the output `out`,
the stack elements the translated script leaves above the untouched stack below: `[v]` for a `B`
or `W` fragment (`v` nonzero for a satisfaction, `[]` for a dissatisfaction), `[]` for a `V`
fragment, `[key, sig]` for a `K` fragment. This is the reference's satisfaction and
dissatisfaction table in one relation; the non-canonical combinations the script also accepts
(both sides of an `or_b` satisfied, a selector other than `1`) are included. -/
def Sem (f : Flags) (o : Oracle) : Ms → List Bytes → List Bytes → Prop
| .pk_k key, w, out => ∃ sig, w = [sig] ∧ out = [key, sig]
| .pk_h h, w, out => ∃ key sig, w = [key, sig] ∧ o.hash160 key = h ∧ out = [key, sig]
| .older n, w, out => w = [] ∧ CsvPasses f o n ∧ out = [serialize n]
| .after n, w, out => w = [] ∧ CltvPasses f o n ∧ out = [serialize n]
| .sha256 h, w, out => ∃ pre, w = [pre] ∧ pre.length = 32 ∧ out = [boolBytes (decide (o.sha256 pre = h))]
| .hash256 h, w, out => ∃ pre, w = [pre] ∧ pre.length = 32 ∧ out = [boolBytes (decide (o.hash256 pre = h))]
| .ripemd160 h, w, out => ∃ pre, w = [pre] ∧ pre.length = 32 ∧ out = [boolBytes (decide (o.ripemd160 pre = h))]
| .hash160 h, w, out => ∃ pre, w = [pre] ∧ pre.length = 32 ∧ out = [boolBytes (decide (o.hash160 pre = h))]
| .and_v x y, w, out => ∃ wx wy, w = wx ++ wy ∧ Sem f o x wx [] ∧ Sem f o y wy out
| .and_b x y, w, out => ∃ wx wy vx vy, w = wx ++ wy ∧ Sem f o x wx [vx] ∧ Sem f o y wy [vy] ∧
out = [boolBytes (castToBool vx && castToBool vy)]
| .or_b x z, w, out => ∃ wx wz vx vz, w = wx ++ wz ∧ Sem f o x wx [vx] ∧ Sem f o z wz [vz] ∧
out = [boolBytes (castToBool vx || castToBool vz)]
| .or_c x z, w, out => out = [] ∧ ∃ wx vx, Sem f o x wx [vx] ∧
((castToBool vx = true ∧ w = wx) ∨ (castToBool vx = false ∧ ∃ wz, w = wx ++ wz ∧ Sem f o z wz []))
| .or_d x z, w, out => ∃ wx vx, Sem f o x wx [vx] ∧
((castToBool vx = true ∧ w = wx ∧ out = [vx]) ∨
(castToBool vx = false ∧ ∃ wz, w = wx ++ wz ∧ Sem f o z wz out))
| .or_i x z, w, out => ∃ b w', w = b :: w' ∧
((castToBool b = true ∧ Sem f o x w' out) ∨ (castToBool b = false ∧ Sem f o z w' out))
| .andor x y z, w, out => ∃ wx vx, Sem f o x wx [vx] ∧
((castToBool vx = true ∧ ∃ wy, w = wx ++ wy ∧ Sem f o y wy out) ∨
(castToBool vx = false ∧ ∃ wz, w = wx ++ wz ∧ Sem f o z wz out))
| .multi k keys, w, out => ∃ sigs dummy ok, w = sigs ++ [dummy] ∧ sigs.length = k ∧
multisigLoop o sigs keys.reverse = some ok ∧ (f.nulldummy = true → dummy = []) ∧ out = [boolBytes ok]
| .wrap_a x, w, out => Sem f o x w out
| .wrap_s x, w, out => Sem f o x w out
| .wrap_c x, w, out => ∃ key sig ok, Sem f o x w [key, sig] ∧ o.checkSig sig key = some ok ∧ out = [boolBytes ok]
| .wrap_d x, w, out => (w = [[1]] ∧ Sem f o x [] [] ∧ out = [[1]]) ∨ (w = [[]] ∧ out = [[]])
| .wrap_v x, w, out => ∃ v, Sem f o x w [v] ∧ castToBool v = true ∧ out = []
| .wrap_j x, w, out => (∃ e w', w = e :: w' ∧ e ≠ [] ∧ e.length ≤ MAX_SCRIPT_ELEMENT_SIZE ∧ Sem f o x w out) ∨
(w = [[]] ∧ out = [[]])
| .wrap_n x, w, out => ∃ v, Sem f o x w [v] ∧ out = [boolBytes (castToBool v)]
/-- Satisfaction of a `B` (or `W`) fragment: some output value that `CastToBool` accepts. -/
def Sat (f : Flags) (o : Oracle) (m : Ms) (w : List Bytes) : Prop :=
∃ v, Sem f o m w [v] ∧ castToBool v = true
/-- Dissatisfaction of a `B` (or `W`) fragment: the output is exactly the empty element. -/
def Dsat (f : Flags) (o : Oracle) (m : Ms) (w : List Bytes) : Prop := Sem f o m w [[]]
/-- Satisfaction of a `V` fragment: nothing is left. -/
def SatV (f : Flags) (o : Oracle) (m : Ms) (w : List Bytes) : Prop := Sem f o m w []
/-- The values a `B` or `W` fragment can leave: the script number of some `n` in
`0 … 2^31 - 1` (so a valid 4-byte `CScriptNum`; `[]` is `0`, `[1]` is `1`). -/
def GoodVal (v : Bytes) : Prop := ∃ n : Int, 0 ≤ n ∧ n < 2 ^ 31 ∧ v = serialize n
/-! ### Sequential execution -/
/-- The instruction loop of `EvalScript` without the final unbalanced-conditional check, so
that it composes sequentially. -/
def runSeq (f : Flags) (o : Oracle) : State → Script → Option State
| s, [] => some s
| s, i :: rest =>
match step f o s i with
| none => none
| some s' => runSeq f o s' rest
end BitcoinMiniscript
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: Def_BitcoinMiniscript.lean
The file introduces, in order, fifteen definitions: the fragment syntax , the translation , the counts and , the type labels , the modifier record , the modifier function , the typing relation , the checker , the semantics relation , its three specialisations , , , the value predicate , and the loop . It asserts no theorems. The preamble notions it builds on are unfolded first; then each definition of the file gets its own paragraph, in file order.
Preamble notions used (from the other definition files)
Basic data (from the script-interpreter preamble)
Byte strings, stacks, witnesses. A byte string is a finite list of 8-bit bytes (values –); is the empty byte string and the length of . Stacks, witnesses and outputs are finite lists of byte strings written top element first. For such lists, is the list with placed on top of , is concatenation (in all elements of lie above all elements of , the first element of being the top of the stack), and is the number of elements.
Constants.
. For a byte string: ; ; for a string with at least two bytes, . So it is true exactly when some byte other than the last is nonzero, or the last byte is neither nor ; the empty string, all-zero strings, and strings of zero bytes followed by a final are false.
. , .
(script-number encoding of an integer ). . For , let be the little-endian base-256 digits of with no most-significant zero bytes. If the last (most significant) byte of has bit set, the result is followed by one extra byte, if and if ; otherwise the result is with bit of its last byte set if , and itself if . Examples: , , , , .
Flags . A record of three independent booleans , , ; every combination is allowed.
Oracle . 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):
- : byte strings byte strings;
- , an arbitrary function of a signature and a public key ("none" means the script fails);
- : integers booleans.
(both lists top-first), with result none, some(true) or some(false):
- if : some(true);
- if is nonempty and : some(false);
- if and : compute . If none, the result is none. If some(true): the result is some(false) when , and otherwise . If some(false): the result is some(false) when , and otherwise .
The script interpreter (from the script-interpreter preamble)
Instructions and scripts. An instruction is either for a byte string , or for an opcode byte . A script is a finite list of instructions. Opcode bytes used below: OP_1NEGATE , OP_RESERVED , OP_1…OP_16 …, OP_NOP , OP_IF , OP_NOTIF , OP_ELSE , OP_ENDIF , OP_VERIFY , OP_RETURN , OP_TOALTSTACK , OP_FROMALTSTACK , OP_IFDUP , OP_DUP , OP_SWAP , OP_SIZE , OP_EQUAL , OP_EQUALVERIFY , OP_0NOTEQUAL , OP_BOOLAND , OP_BOOLOR , OP_RIPEMD160 , OP_SHA1 , OP_SHA256 , OP_HASH160 , OP_HASH256 , OP_CODESEPARATOR , OP_CHECKSIG , OP_CHECKSIGVERIFY , OP_CHECKMULTISIG , OP_CHECKMULTISIGVERIFY , OP_NOP1 , OP_CHECKLOCKTIMEVERIFY , OP_CHECKSEQUENCEVERIFY , OP_NOP4…OP_NOP10 … (plus the other standard stack/arithmetic opcodes named below).
is the number of instructions in the script with (pushes and opcodes are not counted).
States. A state is a quadruple : the main stack and the alt stack (lists of byte strings, top first), the condition stack (a list of booleans, innermost first) and the operation counter . . means every entry of is true (so it is true for , and false exactly when contains at least one false). The state is executing when .
Decoding numbers. "Decode with limit " fails if ; otherwise it gives the sign–magnitude little-endian value of : if the last byte has bit set, minus the little-endian value of with that bit cleared, else the little-endian value of ( decodes to ). No minimal-encoding requirement is applied anywhere.
— one instruction; result is a new state or failure.
- : fail if . If executing, put on top of the main stack; otherwise leave the state unchanged. Then fail if .
- : (1) if and , fail; if , increase by one (this happens also in non-executed branches). (2) If 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 , apply (below, with the flag "executing" passed in); fail if it fails, and otherwise fail if the resulting . (4) Otherwise the state is unchanged apart from , and it fails if .
. "Top" is the first stack element, "second" the next; whenever a required element is missing the result is failure.
OP_1NEGATEorOP_1…OP_16: push , i.e. of .OP_NOP,OP_NOP1,OP_NOP4…OP_NOP10,OP_CODESEPARATOR: no change.OP_CHECKLOCKTIMEVERIFY: if is false, no change. Otherwise decode the top with limit (not removing it); fail if that fails, if the value , or if is false; else no change.OP_CHECKSEQUENCEVERIFY: if is false, no change. Otherwise decode the top with limit (not removing it); fail if that fails or ; if bit of is set, no change; otherwise fail if is false, else no change.OP_IF/OP_NOTIF: if , remove the top and put (negated forOP_NOTIF) in front of ; if not , put false in front of and leave the stack alone.OP_ELSE: fail if is empty, else negate its first entry.OP_ENDIF: fail if is empty, else remove its first entry.OP_VERIFY: remove the top; fail if 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 of it is true, else no change.OP_DEPTH: push .OP_PICK/OP_ROLL: remove the top, decode it (limit ) as , require a nonempty remainder with its length, and copy (PICK) or move (ROLL) its element of index (0 = top) to the top.OP_SIZE: push for the top , which stays.OP_EQUAL/OP_EQUALVERIFY: remove the top and second ;OP_EQUALpushes ;OP_EQUALVERIFYfails unless .OP_1ADD,OP_1SUB,OP_NEGATE,OP_ABS,OP_NOT,OP_0NOTEQUAL: remove the top, decode it with limit as (fail if longer), push of , , , , ( if else ), ( if else ) 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 and second , decode from and from with limit (fail if either is longer), and push of the result: , , ( if and else ), ( if or else ), and for , then , ;OP_NUMEQUALVERIFYpushes nothing and fails unless .OP_WITHIN: remove three elements (top), , , decode each with limit , push of the decoded values.OP_RIPEMD160,OP_SHA1,OP_SHA256,OP_HASH160,OP_HASH256: replace the top by , , , , respectively.OP_CHECKSIG/OP_CHECKSIGVERIFY: with the top and the second, let ; fail if is none;OP_CHECKSIGreplaces both by ;OP_CHECKSIGVERIFYremoves both and fails unless is true.OP_CHECKMULTISIG/OP_CHECKMULTISIGVERIFY: remove the top and decode it (limit ) as ; fail if or ; let and fail if ; the next elements (top-first) are the keys (fail if fewer); the following element is decoded (limit ) as , failing if absent, if or ; the next elements (top-first) are the signatures (fail if fewer); let and fail if none; one more element, the dummy, must be present and is removed; fail if is true and the dummy is not ; the counter becomes ;OP_CHECKMULTISIGpushes onto what remains, the VERIFY form pushes nothing and fails unless is true.- Every other byte (including
OP_RESERVED, , and any byte used as an opcode): fail.
: is if its condition stack is empty and failure otherwise; fails if fails and is otherwise.
: if succeeds with final state , the result is "some" of the main stack of ; 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 is not checked against any size limit.
Number pushes and time-lock predicates
(from the to_local preamble), for an integer : if or , it is the opcode instruction , i.e. OP_1NEGATE for and OP_1…OP_16 for (these opcodes are , so they are not counted by the operation counter, and when executed they push ); otherwise it is — in particular , , and for .
(from the to_local preamble), for : , or ( and (bit of is set, or )).
(from the HTLC preamble), for : , or ( and ).
The definitions of the file, in order
1. Ms
Miniscript fragments . 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):
- , a byte string (a key);
- , a byte string (a key hash);
- , ;
- , ;
- , 6. , 7. , 8. , each with a byte string;
- , 10. , with fragments;
- , 12. , 13. , 14. , with fragments;
- , with fragments;
- , and a finite list of byte strings; 17.–23. the wrappers , , , , , , , with a fragment.
Two fragments are equal exactly when they are built identically.
2. compile
, the script of a fragment , written ; opcode instructions are written by name, is concatenation of instruction lists:
- .
OP_DUP,OP_HASH160, ,OP_EQUALVERIFY(noOP_CHECKSIG).- ,
OP_CHECKSEQUENCEVERIFY. - ,
OP_CHECKLOCKTIMEVERIFY. OP_SIZE, ,OP_EQUALVERIFY,OP_SHA256, ,OP_EQUAL.- : the same with
OP_HASH256in place ofOP_SHA256. - : the same with
OP_RIPEMD160(the size check is still against ). - : the same with
OP_HASH160(the size check is still against ). - .
OP_BOOLAND.OP_BOOLOR.OP_NOTIFOP_ENDIF.OP_IFDUP,OP_NOTIFOP_ENDIF.OP_IFOP_ELSEOP_ENDIF.OP_NOTIFOP_ELSEOP_ENDIF(note comes before ).- ,
OP_CHECKMULTISIG( and read as integers). OP_TOALTSTACKOP_FROMALTSTACK.OP_SWAP.OP_CHECKSIG.OP_DUP,OP_IFOP_ENDIF.OP_VERIFY(always a separateOP_VERIFY).OP_SIZE,OP_0NOTEQUAL,OP_IFOP_ENDIF.OP_0NOTEQUAL.
Opcode bytes: OP_IF , OP_NOTIF , OP_ELSE , OP_ENDIF , OP_VERIFY , OP_TOALTSTACK , OP_FROMALTSTACK , OP_IFDUP , OP_DUP , OP_SWAP , OP_SIZE , OP_EQUAL , OP_EQUALVERIFY , OP_0NOTEQUAL , OP_BOOLAND , OP_BOOLOR , OP_RIPEMD160 , OP_SHA256 , OP_HASH160 , OP_HASH256 , OP_CHECKSIG , OP_CHECKMULTISIG , OP_CHECKLOCKTIMEVERIFY , OP_CHECKSEQUENCEVERIFY .
3. size
, defined by: ; ; ; of each of , , , is ; ; ; ; ; ; ; ; ; ; ; .
4. opsMax
, defined by: ; ; ; of each of , , , is ; ; ; ; ; ; ; ; ; ; ; .
5. Ty
Correctness types . A four-element set of distinct labels (no meaning is attached to them other than through the rules below).
6. Props
Modifier records . A record of five booleans .
7. props
, computed syntactically. Write for the components of (similarly for , ), for boolean and/or, T/F for true/false. (The modifier letter is unrelated to the oracle , and the modifier letter is unrelated to a sub-fragment named ; e.g. is the -modifier of the sub-fragment .)
| fragment | |||||
|---|---|---|---|---|---|
| F | T | T | T | T | |
| F | F | T | T | T | |
| , | T | F | F | F | F |
| , , , | F | T | T | T | T |
| F | |||||
| T | |||||
| F | T | T | |||
| F | F | F | |||
| F | |||||
| F | F | ||||
| F | |||||
| F | F | T | T | T | |
| F | F | F | |||
| F | F | ||||
| F | T | ||||
| F | T | T | T | F | |
| F | F | ||||
| F | T | T | |||
| T |
(The components do not depend on the byte-string, integer or list parameters of the leaves.)
8. HasType
, " has type ", is the smallest relation closed under the following 23 rules (one per constructor; there is no other way to derive it). Throughout, and .
- if .
- if .
- if .
- if . 5.–8. , , , if (no condition on being any particular hash length).
- if , and .
- if and .
- if , , , .
- if , , , .
- if , , , .
- if , and .
- if , , , , and .
- if and every key in has length .
- if .
- if and .
- if .
- if and .
- if .
- if and .
- if .
Here , , , , mean the corresponding component of is true. Read off the rules: type is concluded only by rules 17–18 (, ); type only by rules 1, 2, 9 (with ), 14 and 15 (with both branches ); type only by rules 9, 12, 14, 15, 21. No rule constrains the modifiers of or beyond those listed, and no rule bounds the depth or total size of the fragment.
9. typeOf
, a recursive checker:
- : some() if , else none. : some() if , else none.
- , : some() if , else none.
- , , , : some() if , else none.
- : if some() and some() with , then some(); otherwise none.
- : some() if some() and some(); otherwise none.
- : some() if checks to , to , and ; otherwise none.
- : some() if checks to , to , and ; otherwise none.
- : some() if and both check to and ; otherwise none.
- : if checks to some(), to some(), and , then some(); otherwise none.
- : if checks to , to some(), to some(), and , , , all hold, then some(); otherwise none.
- : some() if and all keys have length ; otherwise none.
- : some() if checks to . : some() if checks to and . : some() if checks to . : some() if checks to and . : some() if checks to . : some() if checks to and . : some() if checks to . In every other case: none.
(Here "checks to " means returns some(), and etc. are components of .)
10. Sem
— a relation between a fragment , a witness and an output (both lists of byte strings, top first), for fixed flags and oracle ; it is defined by recursion on , and nothing in it refers to the type of or to any size or operation-count limit except where stated. "" ranges over arbitrary byte strings / lists of byte strings / booleans as appropriate.
- : with and .
- : with , and .
- : , and .
- : , and .
- : with , and — so if the oracle hash of equals and otherwise (any 32-byte is accepted either way). 6.–8. , , : the same with , , respectively (and still ).
- : with , and .
- : with , , and .
- : with , , and (both sides may be true simultaneously).
- : and with and either ( true and ) or ( false and with and ). ( in the second alternative is any value with false, not necessarily .)
- : with and either ( true, and ) or ( false and with and ).
- : with and either ( true and ) or ( false and ). The selector is any byte string (not only / ), with no length bound.
- : with and either ( true and with and ) or ( false and with and ).
- : a list , a byte string and a boolean with (the dummy is the deepest witness element), , (keys taken last-listed first), ( true ), and . Both true and false are allowed.
- : .
- : .
- : with , and ( may be false).
- : either (, and ) or ( and ). The selector must be exactly the one-byte string or exactly the empty string.
- : with , true, and .
- : either ( for some with , , and — note receives the whole , including ) or ( and ).
- : with and .
11. Sat
: there is a byte string with and .
12. Dsat
: , i.e. the output is the single empty byte string.
13. SatV
: , i.e. the output is the empty list.
14. GoodVal
, for a byte string : there is an integer with and . (So () and () qualify; negative encodings, non-minimal encodings such as or , and strings longer than 4 bytes do not.)
15. runSeq
, for a state and a script : ; and is failure (none) if fails, and if . It is the instruction loop of the interpreter without the final check that the condition stack is empty.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.