110 views

Skip to first unread message

May 16, 2024, 3:37:36 PMMay 16

to bitco...@googlegroups.com

Hi All,

Although Miniscript has been implemented and is in use by a couple of

implementations, it doesn't have a formal BIP. As such, I and a few

others have adapted the reference website's documentation to be in the

BIP format, which is provided below. The text, and any changes that may

be made, is also available at

https://github.com/achow101/bips/blob/miniscript/bip-miniscript.md.

Any feedback on this, particularly about what else should be included,

or what could be excluded, would be welcome.

Thanks,

Ava

***

<pre>

BIP: miniscript

Layer: Applications

Title: Miniscript

Author: Pieter Wuille <pie...@wuille.net>

Andrew Poelstra <andrew....@gmail.com>

Sanket Kanjalkar <sanke...@gmail.com>

Antoine Poinsot <daro...@protonmail.com>

Ava Chow <m...@achow101.com>

Comments-Summary: No comments yet.

Comments-URI:

https://github.com/bitcoin/bips/wiki/Comments:BIP-miniscript

Status: Draft

Type: Informational

Created: 2023-10-10

License: CC0-1.0

</pre>

## Abstract

This document specifies Miniscript, a language for writing (a subset of)

Bitcoin Scripts in a

structured way, enabling analysis, composition, generic signing and more.

## Copyright

This document is licensed under the Creative Commons CC0 1.0 Universal

license.

## Motivation

Bitcoin Script is an unusual stack-based language with many edge cases,

designed for implementing

spending conditions consisting of various combinations of signatures,

hash locks, and time locks.

Yet despite being limited in functionality it is still highly nontrivial to:

* Given a combination of spending conditions, finding the most

economical script to implement it.

* Given two scripts, construct a script that implements a composition of

their spending conditions (e.g. a multisig where one of the "keys" is

another multisig).

* Given a script, find out what spending conditions it permits.

* Given a script and access to a sufficient set of private keys,

construct a general satisfying witness for it.

* Given a script, be able to predict the cost of spending an output.

* Given a script, know whether particular resource limitations like the

ops limit might be hit when spending.

Miniscript functions as a representation for scripts that makes this

sort of operations possible.

It has a structure that allows composition. It is very easy to

statically analyze for various

properties (spending conditions, correctness, security properties,

malleability, ...). It can be

targeted by spending policy compilers. Finally, compatible scripts can

easily be converted to

Miniscript form - avoiding the need for additional metadata for e.g.

signing devices that support

it.

## Specification

These specifications apply to P2WSH (BIP143) and Tapscript (BIP342)

scripts, with only minor

variations between the two. Differences are noted inline. Unless

explicitly stated specifications

apply to both.

### Translation Table

This table shows all Miniscript *fragments* and their associated

semantics and Bitcoin Script.

Fragments that do not change the semantics of their subexpressions are

called *wrappers*. Normal

fragments use a `fragment(arg1, arg2, ..)` notation, while wrappers are

written using

prefixes separated from other fragments by a colon. The colon is dropped

between subsequent

wrappers; e.g. `dv:older(144)` is the `d:` wrapper applied to the

`v:` wrapper applied to the `older` fragment for 144 blocks.

The `pk`, `pkh`, and `and_n` fragments and `t:`,

`l:`, and `u:` wrappers are syntactic sugar for other Miniscripts, as listed

in the table below. Note that `<20>` are in hex representation in this

document.

Miniscript fragments are expected to be used in [BIP

382](bip-0382.mediawiki) `wsh()` descriptors

and [BIP 386](bip-0386.mediawiki) `tr()` descriptors. Key expressions

are specified in

[BIP 380](bip-0380.mediawiki#user-content-Key_Expressions).

Additionally, BIPs 382 and 386 specify

restrictions on key expressions and what they resolve to - these apply

to key expressions in

Miniscript. BIP 382's key expression restrictions apply to Miniscript in

P2WSH contexts, and BIP

386's key expression restrictions apply to Miniscript in P2TR contexts.

| Semantics | Miniscript

Fragment | Bitcoin Script

|----------------------------------------------------------|-------------------------------|---------------

| false |

`0` | `0`

| true |

`1` | `1`

| check(key) |

`pk_k(key)` | `<key>`

| |

`pk_h(key)` | ` DUP HASH160 <HASH160(key)> EQUALVERIFY `

| | `pk(key)` =

`c:pk_k(key)` | `<key> CHECKSIG`

| | `pkh(key)`

= `c:pk_h(key)` | ` DUP HASH160 <HASH160(key)> EQUALVERIFY CHECKSIG`

| nSequence ≥ n (and compatible) |

`older(n)` | `<n> CHECKSEQUENCEVERIFY`

| nLockTime ≥ n (and compatible) |

`after(n)` | `<n> CHECKLOCKTIMEVERIFY`

| len(x) = 32 and SHA256(x) = h |

`sha256(h)` | `SIZE <20> EQUALVERIFY SHA256 <h> EQUAL`

| len(x) = 32 and HASH256(x) = h |

`hash256(h)` | `SIZE <20> EQUALVERIFY HASH256 <h> EQUAL`

| len(x) = 32 and RIPEMD160(x) = h |

`ripemd160(h)` | `SIZE <20> EQUALVERIFY RIPEMD160 <h> EQUAL`

| len(x) = 32 and HASH160(x) = h |

`hash160(h)` | `SIZE <20> EQUALVERIFY HASH160 <h> EQUAL`

| (X and Y) or Z |

`andor(X,Y,Z)` | `[X] NOTIF [Z] ELSE [Y] ENDIF`

| X and Y |

`and_v(X,Y)` | `[X] [Y]`

| |

`and_b(X,Y)` | `[X] [Y] BOOLAND`

| |

`and_n(X,Y)` = `andor(X,Y,0)` | `[X] NOTIF 0 ELSE [Y] ENDIF`

| X or Z |

`or_b(X,Z)` | `[X] [Z] BOOLOR`

| |

`or_c(X,Z)` | `[X] NOTIF [Z] ENDIF`

| |

`or_d(X,Z)` | `[X] IFDUP NOTIF [Z] ENDIF`

| |

`or_i(X,Z)` | `IF [X] ELSE [Z] ENDIF`

| X_1 + ... + X_n = k |

`thresh(k,X_1,...,X_n)` | `[X_1] [X_2] ADD ... [X_n] ADD ... <k>

EQUAL`

| check(key_1) + ... + check(key_n) = k *(P2WSH only)* |

`multi(k,key_1,...,key_n)` | `<k> <key_1> ... <key_n> <n> CHECKMULTISIG`

| check(key_1) + ... + check(key_n) = k *(Tapscript only)* |

`multi_a(k,key_1,...,key_n)` | `<key_1> CHECKSIG <key_2> CHECKSIGADD

... <key_n> CHECKSIGADD <k> NUMEQUAL`

| X (identities) |

`a:X` | `TOALTSTACK [X] FROMALTSTACK`

| |

`s:X` | `SWAP [X]`

| |

`c:X` | `[X] CHECKSIG`

| | `t:X` =

`and_v(X,1)` | `[X] 1`

| |

`d:X` | `DUP IF [X] ENDIF`

| |

`v:X` | `[X] VERIFY (or VERIFY version of last

opcode in [X])`

| |

`j:X` | `SIZE 0NOTEQUAL IF [X] ENDIF`

| |

`n:X` | `[X] 0NOTEQUAL`

| | `l:X` =

`or_i(0,X)` | `IF 0 ELSE [X] ENDIF`

| | `u:X` =

`or_i(X,0)` | `IF [X] ELSE 0 ENDIF`

### Type System

Not every Miniscript expression can be composed with every other. Some

return their result by

putting true or false on the stack; others can only abort or continue.

Some require subexpressions

that consume an exactly known number of arguments, while others need a

subexpression that has a

nonzero top stack element to satisfy. To model all these properties, we

define a correctness type

system for Miniscript.

#### Correctness

Every miniscript expression has one of four basic types: "**B**" (base),

"**V**" (verify),

"**K**" (key) and "**W**" (wrapped). Then there are 6 type modifiers

which guarantee additional

properties: "**z**" (zero arg), "**o**" (one-arg), "**n**" (nonzero),

"**d**"

(dissatisfiable), "**u**" (unit) and "**k**" (no timelock mixing).

The following table lists the correctness requirements for each of the

Miniscript expressions, and

its type properties in function of those of their subexpressions.

| Miniscript |

Requires | Type | Properties

|------------------------------|-------------------------------------------------------|-------------|-----------

| `0` | |

B | z; u; d

| `1` | |

B | z; u

| `pk_k(key)` | |

K | o; n; d; u

| `pk_h(key)` | |

K | n; d; u

| `older(n)`, `after(n)` | 1 ≤ n <

2<sup>31</sup> | B | z

| `sha256(h)` | |

B | o; n; d; u

| `ripemd160(h)` |

| B | o; n; d; u

| `hash256(h)` | |

B | o; n; d; u

| `hash160(h)` | |

B | o; n; d; u

| `andor(X,Y,Z)` | X is Bdu; Y and Z are both B, K, or

V | same as Y/Z |

z=z<sub>X</sub>z<sub>Y</sub>z<sub>Z</sub>;

o=z<sub>X</sub>o<sub>Y</sub>o<sub>Z</sub> or

o<sub>X</sub>z<sub>Y</sub>z<sub>Z</sub>; u=u<sub>Y</sub>u<sub>Z</sub>;

d=d<sub>Z</sub>

| `and_v(X,Y)` | X is V; Y is B, K, or

V | same as Y |

z=z<sub>X</sub>z<sub>Y</sub>; o=z<sub>X</sub>o<sub>Y</sub> or

z<sub>Y</sub>o<sub>X</sub>; n=n<sub>X</sub> or

z<sub>X</sub>n<sub>Y</sub>; u=u<sub>Y</sub>

| `and_b(X,Y)` | X is B; Y is

W | B |

z=z<sub>X</sub>z<sub>Y</sub>; o=z<sub>X</sub>o<sub>Y</sub> or

z<sub>Y</sub>o<sub>X</sub>; n=n<sub>X</sub> or

z<sub>X</sub>n<sub>Y</sub>; d=d<sub>X</sub>d<sub>Y</sub>; u

| `or_b(X,Z)` | X is Bd; Z is

Wd | B |

z=z<sub>X</sub>z<sub>Z</sub>; o=z<sub>X</sub>o<sub>Z</sub> or

z<sub>Z</sub>o<sub>X</sub>; d; u

| `or_c(X,Z)` | X is Bdu; Z is

V | V |

z=z<sub>X</sub>z<sub>Z</sub>; o=o<sub>X</sub>z<sub>Z</sub>

| `or_d(X,Z)` | X is Bdu; Z is

B | B |

z=z<sub>X</sub>z<sub>Z</sub>; o=o<sub>X</sub>z<sub>Z</sub>;

d=d<sub>Z</sub>; u=u<sub>Z</sub>

| `or_i(X,Z)` | both are B, K, or

V | same as X/Z |

o=z<sub>X</sub>z<sub>Z</sub>; u=u<sub>X</sub>u<sub>Z</sub>;

d=d<sub>X</sub> or d<sub>Z</sub>

| `thresh(k,X_1,...,X_n)` | 1 ≤ k ≤ n; X<sub>1</sub> is Bdu;

others are Wdu | B | z=all are z; o=all are z except one is o;

d; u

| `multi(k,key_1,...,key_n)` | 1 ≤ k ≤

n | B | n; d; u

| `multi_a(k,key_1,...,key_n)` | 1 ≤ k ≤

n | B | d; u

| `a:X` | X is

B | W |

d=d<sub>X</sub>; u=u<sub>X</sub>

| `s:X` | X is

Bo | W |

d=d<sub>X</sub>; u=u<sub>X</sub>

| `c:X` | X is

K | B |

o=o<sub>X</sub>; n=n<sub>X</sub>; d=d<sub>X</sub>; u

| `d:X` | X is

Vz | B | o; n;

d; *(Tapscript only)* u

| `v:X` | X is

B | V |

z=z<sub>X</sub>; o=o<sub>X</sub>; n=n<sub>X</sub>

| `j:X` | X is

Bn | B |

o=o<sub>X</sub>; n; d; u=u<sub>X</sub>

| `n:X` | X is

B | B |

z=z<sub>X</sub>; o=o<sub>X</sub>; n=n<sub>X</sub>; d=d<sub>X</sub>; u

#### Malleability

Malleability is the ability for a third party (*not* a participant in

the script) to modify an

existing satisfaction into another valid satisfaction. To analyze the

malleability guarantees of a

script we define three additional type properties: "**s**" (signed),

"**f**" (forced) and

"**e**" (expressive).

The following table lists the malleability properties and requirement of

each fragment.

| Miniscript | Requires | Properties

|------------------------------|---------------------------------------------------------------------|-----------

| `0` | | s, e

| `1` | | f

| `pk_k(key)` | | s, e

| `pk_h(key)` | | s, e

| `older(n)` | | f

| `after(n)` | | f

| `sha256(h)` | |

| `ripemd160(h)` | |

| `hash256(h)` | |

| `hash160(h)` | |

| `andor(X,Y,Z)` | e<sub>X</sub> and (s<sub>X</sub> or

s<sub>Y</sub> or s<sub>Z</sub>) | s=s<sub>Z</sub> and (s<sub>X</sub> or

s<sub>Y</sub>); f=f<sub>Z</sub> and (s<sub>X</sub> or f<sub>Y</sub>);

e=e<sub>Z</sub> and (s<sub>X</sub> or f<sub>Y</sub>)

| `and_v(X,Y)` | | s=s<sub>X</sub> or s<sub>Y</sub>; f=s<sub>X</sub> or

f<sub>Y</sub>

| `and_b(X,Y)` | | s=s<sub>X </sub>or s<sub>Y;</sub>

f=f<sub>Xf</sub><sub>Y</sub> or s<sub>X</sub>f<sub>X</sub> or

s<sub>Y</sub>f<sub>Y</sub>;

e=e<sub>X</sub>e<sub>Y</sub>s<sub>X</sub>s<sub>Y</sub>

| `or_b(X,Z)` | e<sub>Xe</sub><sub>Z </sub>and

(s<sub>X</sub> or s<sub>Z</sub>) | s=s<sub>X</sub>s<sub>Z</sub>; e

| `or_c(X,Z)` | e<sub>X</sub> and (s<sub>X</sub> or

s<sub>Z</sub>) | s=s<sub>X</sub>s<sub>Z</sub>; f

| `or_d(X,Z)` | e<sub>X</sub> and (s<sub>X</sub> or

s<sub>Z</sub>) | s=s<sub>X</sub>s<sub>Z</sub>;

f=f<sub>Z</sub>; e=e<sub>Z</sub>

| `or_i(X,Z)` | s<sub>X</sub> or

s<sub>Z</sub> |

s=s<sub>X</sub>s<sub>Z</sub>; f=f<sub>X</sub>f<sub>Z</sub>;

e=e<sub>X</sub>f<sub>Z</sub> or e<sub>Z</sub>f<sub>X</sub>

| `thresh(k,X_1,...,X_n)` | all are e; at most k are

non-s | s=at most k-1 are non-s;

e=all are s

| `multi(k,key_1,...,key_n)` | | s; e

| `multi_a(k,key_1,...,key_n)` | | s; e

| `a:X` | | s=s<sub>X</sub>; f=f<sub>X</sub>; e=e<sub>X</sub>

| `s:X` | | s=s<sub>X</sub>; f=f<sub>X</sub>; e=e<sub>X</sub>

| `c:X` | | s; f=f<sub>X</sub>; e=e<sub>X</sub>

| `d:X` | | s=s<sub>X</sub>; e

| `v:X` | | s=s<sub>X</sub>; f

| `j:X` | | s=s<sub>X</sub>; e=f<sub>X

| `n:X` | | s=s<sub>X</sub>; f=f<sub>X</sub>; e=e<sub>X</sub>

### Satisfaction

The following table shows all valid satisfactions and dissatisfactions

for every Miniscript, using

satisfactions and dissatisfactions of its subexpressions. Multiple

possibilities are separated by

semicolons. Some options are not actually necessary to produce correct

witnesses, and are called

*non-canonical* options. They are listed for completeness, but

~~[struckthrough]~~. The

fragments where a satisfaction or dissatisfaction does not exist will

contain *(none)*. The

fragments where the satisfaction or dissatisfaction is to provide no

data will contain *(empty)*.

| Miniscript | Dissatisfactions

(dsat) | Satisfactions (sat)

|------------------------------|---------------------------------------------------------|--------------------

| `0` |

*(empty)* | *(none)*

| `1` |

*(none)* | *(empty)*

| `pk_k(key)` |

0 | sig

| `pk_h(key)` | 0

key | sig key

| `older(n)` |

*(none)* | *(empty)*

| `after(n)` |

*(none)* | *(empty)*

| `sha256(h)` | any 32-byte vector except the

preimage | preimage

| `ripemd160(h)` | any 32-byte vector except the

preimage | preimage

| `hash256(h)` | any 32-byte vector except the

preimage | preimage

| `hash160(h)` | any 32-byte vector except the

preimage | preimage

| `andor(X,Y,Z)` | dsat(Z) dsat(X); ~~[dsat(Y)

sat(X)]~~ | sat(Y) sat(X); sat(Z) dsat(X)

| `and_v(X,Y)` | *(none)*; ~~[dsat(Y)

sat(X)]~~ | sat(Y) sat(X)

| `and_b(X,Y)` | dsat(Y) dsat(X); ~~[sat(Y) dsat(X)];

[dsat(Y) sat(X)]~~ | sat(Y) sat(X)

| `or_b(X,Z)` | dsat(Z)

dsat(X) | dsat(Z) sat(X); sat(Z)

dsat(X); ~~[sat(Z) sat(X)]~~

| `or_c(X,Z)` |

*(none)* | sat(X); sat(Z)

dsat(X)

| `or_d(X,Z)` | dsat(Z)

dsat(X) | sat(X); sat(Z) dsat(X)

| `or_i(X,Z)` | dsat(X) 1; dsat(Z)

0 | sat(X) 1; sat(Z) 0

| `thresh(k,X_1,...,X_n)` | All dsats; ~~[Sats/dsats with 1 ≤

#(sats) ≠ k]~~ | Sats/dsats with #(sats) = k

| `multi(k,key_1,...,key_n)` | 0 0 ... 0 (k+1

times) | 0 sig ... sig

| `multi_a(k,key_1,...,key_n)` | 0 ... 0 (n

times) | sig/0 with #(sig) = k and

#(sigs/0) = n

| `a:X` |

dsat(X) | sat(X)

| `s:X` |

dsat(X) | sat(X)

| `c:X` |

dsat(X) | sat(X)

| `d:X` |

0 | sat(X) 1

| `v:X` |

*(none)* | sat(X)

| `j:X` | 0; ~~[dsat(X) (if nonzero top

stack)]~~ | sat(X)

| `n:X` |

dsat(X) | sat(X)

#### Non-malleable Satisfaction Algorithm

In order to produce non-malleable satisfactions we make use of a

function that returns the optimal

satisfaction and dissatisfaction for a given expression (if any exist),

or a special DONTUSE value,

together with an optional HASSIG marker that tracks whether the solution

contains at least one

signature. To implement the function:

* Invoke the function recursively for all subexpressions, obtaining all

their satisfactions/dissatisfactions.

* Iterate over all the valid satisfactions/dissatisfactions in the table

above (including the non-canonical ones), taking into account:

* The dissatisfactions for `sha256`, `ripemd160`, `hash256`, and

`hash160` are always malleable, so instead use DONTUSE there.

* The non-canonical options for `and_b`, `or_b`, and `thresh` are

always overcomplete, so instead use DONTUSE there as well (with HASSIG

flag if the original non-canonical solution had one).

* The satisfactions for `pk_k`, `pk_h`, and `multi` can be marked HASSIG.

* When constructing solutions by combining results for subexpressions,

the result is DONTUSE if any of the constituent results is DONTUSE.

Furthermore, the result gets the HASSIG tag if any of the constituents does.

* If among all valid solutions (including DONTUSE ones) more than one

does not have the HASSIG marker, return DONTUSE.

* If instead exactly one does not have the HASSIG marker, return that

solution.

* If all valid solutions have the HASSIG marker, but all of them are

DONTUSE, return DONTUSE-HASSIG. The HASSIG marker is important because

while this represents a choice between multiple options that would cause

malleability if used, they are not available to the attacker, and we may

be able to avoid them entirely still.

* Otherwise, all not-DONTUSE options are valid, so return the smallest

one (in terms of witness size).

To produce an overall satisfaction, invoke the function on the toplevel

expression. If no valid

satisfaction is returned, or it is DONTUSE, fail. Otherwise, if any

timelocking is used in the

script but the result does not have the HASSIG flag, also fail. If the

satisfaction is both not

DONTUSE and HASSIG, return it.

## Discussion

## Security

Miniscript primarily aims to provide guarantees on the correctness of a

Bitcoin Script. That is, to

guarantee **consensus soundness** and **standardness completeness**.

Consensus soundness means

it is not possible to construct a consensus-valid witness for a Bitcoin

Script unless the Miniscript

spending conditions are met. Standardness completeness means a

standardness-valid witness can be

created for all spending paths of a Miniscript, assuming the resource

limits are respected and there

is no timelock mixing.

Additionally, Miniscript can guarantee the non-malleability and maximum

size of a witness. These can

assist in assessing the soundness of protocols where transaction fees

(and therefore transaction

size) are security-critical parameters.

Hash preimages are constrained to 32 bytes to disallow various forms of

griefing, including making

non-standard (un-relayable) transactions, consensus-invalid swaps across

blockchains, as well as

ensure that satisfaction cost can be accurately calculated.

In order for these properties to not just apply to script, but to an

entire transaction, it's

important that the witness commits to all data relevant for

verification. In practice this means

that scripts whose conditions can be met without any digital signature

are insecure. Besides being

trivially insecure, note how a transaction lacking a signature check

allows an attacker to change

its nLockTime and nSequence fields to meet additional timelock conditions.

### Type system

To statically verify the correctness and malleability guarantees

discussed in the previous section,

we define a type system. See the specifications above for a reference of

each fragment's

requirements and properties. Here we give more information about each type.

Every expression has one of four basic types:

* "**B**" Base expressions. These take their inputs from the top of the

stack. When satisfied, they push a nonzero value of up to 4 bytes onto

the stack. When dissatisfied, they push an exact 0 onto the stack (if

dissatisfaction without aborting is possible at all). This type is used

for most expressions, and required for the top level expression. An

example is `older(n)` = `<n> CHECKSEQUENCEVERIFY`.

* "**V**" Verify expressions. Like "B", these take their inputs from the

top of the stack. Upon satisfaction however, they continue without

pushing anything. They cannot be dissatisfied (will abort instead). A

"V" can be obtained using the `v:` wrapper on a "B" expression, or by

combining other "V" expressions using `and_v`, `or_i`, `or_c`, or

`andor`. An example is `v:pk(key)` = `<key> CHECKSIGVERIFY`.

* "**K**" Key expressions. They again take their inputs from the top of

the stack, but instead of verifying a condition directly they always

push a public key onto the stack, for which a signature is still

required to satisfy the expression. A "K" can be converted into a "B"

using the `c:` wrapper. An example is `pk_h(key)` = `DUP HASH160

<Hash160(key)> EQUALVERIFY`.

* "**W**" Wrapped expressions. They take their inputs from one below the

top of the stack, and push a nonzero (in case of satisfaction) or zero

(in case of dissatisfaction) either on top of the stack, or one below.

So for example a 3-input "W" would take the stack "A B C D E F" and turn

it into "A B F 0" or "A B 0 F" in case of dissatisfaction, and "A B F n"

or "A B n F" in case of satisfaction (with n a nonzero value). Every "W"

is either `s:B` (SWAP B) or `a:B` (TOALTSTACK B FROMALTSTACK). An

example is `s:pk(key)` = `SWAP <key> CHECKSIG`.

Then there are 6 type modifiers, which guarantee additional properties:

* "**z**" Zero-arg: this expression always consumes exactly 0 stack

elements.

* "**o**" One-arg: this expression always consumes exactly 1 stack element.

* "**n**" Nonzero: this expression always consumes at least 1 stack

element, no satisfaction for this expression requires the top input

stack element to be zero.

* "**d**" Dissatisfiable: a dissatisfaction for this expression can

unconditionally be constructed. This implies the dissatisfaction cannot

include any signature or hash preimage, and cannot rely on timelocks

being satisfied.

* "**u**" Unit: when satisfied, this expression will put an exact 1 on

the stack (as opposed to any nonzero value).

* "**k**" No timelock mixing. This expression does not contain a mix of

heightlock and timelock of the same type. If the miniscript does not

have the "k" property, the miniscript template will not match the user

expectation of the corresponding spending policy.

Finally to analyze malleability guarantees we introduce 3 new type

modifiers:

* "**s**" Signed: satisfying this expression always requires a signature

(predicting whether all satisfactions will be HASSIG).

* "**f**" Forced: dissatisfying this expression always requires a

signature (predicting whether all dissatisfactions will be HASSIG).

* "**e**" Expressive: this requires a unique unconditional

dissatisfaction to exist, and forces all conditional dissatisfactions

(if any) to require a signature.

### Malleability

Since Segwit, malleating a transaction no longer breaks the validity of

unconfirmed descendant

transactions. However, unintentional malleability may still have a

number of much weaker undesirable

effects. If a witness can be stuffed with additional data, the

transaction's feerate will go down,

potentially to the point where its ability to propagate and get

confirmed is impacted. Additionally,

malleability can be exploited to add roundtrips to BIP152 block

propagation, by trying to get

different miners to mine different versions of the same transaction.

Finally, malleability may

interfere with the usage of hash locks as a mechanism for publishing

preimages.

Using the malleability type properties it is possible to determine

statically whether a script can

be nonmalleably satisfied under all circumstances. In many cases it is

reasonable to only accept

such guaranteed-nonmalleable scripts, as unexpected behavior can occur

when using other scripts.

For example, when running the non-malleable satisfaction algorithm

above, adding available

preimages, or increasing the nLockTime/nSequence values actually may

make it fail where it succeeded

before. This is because a larger set of met conditions may mean an

existing satisfaction goes from

nonmalleable to malleable. Restricting things to scripts that are

guaranteed to be satisfiable in a

non-malleable way avoids this problem.

When analysing Miniscripts for resource limits, restricting yourself to

just non-malleable solutions

(or even non-malleable scripts) also leads to tighter bounds, as all

non-canonical satisfactions and

dissatisfactions can be left out of consideration.

The malleability analysis makes the following assumptions:

* The attacker does not have access to any of the private keys of public

keys that participate in the Script. Participants with private keys

inherently have the ability to produce different satisfactions by

creating multiple signatures. While it is also interesting to study the

impact rogue participants can have, we treat it as a distinct problem.

* The attacker only has access to hash preimages that honest users have

access to as well. This is a reasonable assumption because hash

preimages are revealed once globally, and then available to everyone. On

the other hand, making the assumption that attackers may have access to

more preimages than honest users makes a large portion of scripts

impossible to satisfy in a non-malleable way.

* The attacker gets to see exactly one satisfying witness of any

transaction. If he sees multiple, it becomes possible for the attacker

to mix and match different satisfactions. This is very hard to reason about.

* We restrict this analysis to scripts where no public key is repeated.

If signatures constructed for one part of the script can be bound to

other checks in the same script, a variant of the mixing from the

previous point becomes available that is equally hard to reason about.

Furthermore this situation can be avoided by using separate keys.

#### Non-Malleable Satisfaction

Malleable satisfactions or dissatisfactions appear whenever options are

available to attackers distinct from the one taken by honest users. This

can happen for multiple reasons:

1. Two or more options for a satisfaction or dissatisfaction are listed

in the table above which are both available to attackers directly.

Regardless of which option is used in the honest solution, the attacker

can change the solution to the other one.

2. Two or more options for a satisfaction or dissatisfaction are listed

in the table above, only one of which is available to attackers, but the

honest solution uses another one. In that case, the attacker can modify

the solution to pick the one available to him.

3. The honest users pick a solution that contains a satisfaction which

can be turned into a dissatisfaction without invalidating the overall

witness. Those are called overcomplete solutions.

Because we assume attackers never have access to private keys, we can

treat any solution that

includes a signature as one that is unavailable to attackers. For

others, the worst case is that the

attacker has access to every solution the honest users have, but no

others: for preimages this is an

explicit assumption, while timelock availability is determined by the

nLockTime and nSequence fields

in the transaction. As long as the overall satisfaction includes at

least one signature, those

values are fixed, and timelock availability is identical for attackers

and honest users.

The description of the non-malleable satisfaction algorithm can be used

to show that no

non-canonical solutions listed in the satisfaction table can occur

inside non-malleable

satisfaction:

* Some of the non-canonical options (the `or_b`, `and_b`, and `thresh`

ones) are overcomplete, and thus can clearly not appear in non-malleable

satisfactions.

* The fact that non-"d" expressions cannot be dissatisfied in valid

witnesses rules out the usage of the non-canonical `and_v` dissatisfaction.

* "d" expressions are defined to be unconditionally dissatisfiable,

which implies that for those a non-HASSIG dissatisfaction must exist.

Non-HASSIG solutions must be preferred over HASSIG ones (reason 2), and

when multiple non-HASSIG ones exist, none can be used (reason 1). This

lets us rule out the other non-canonical options in the table:

* `j:X` is always "d", its non-HASSIG dissatisfaction "0" always

exists, and thus rules out any usage of "dsat(X)".

* If `andor(X,Y,Z)` is "d", a non-HASSIG dissatisfaction "dsat(Z)

dsat(X)" must exist, and thus rules out any usage of "dsat(Y) sat(X)".

* If `and_b(X,Y)` is "d", a non-HASSIG dissatisfaction "dsat(Y)

dsat(X)" must exist, and thus rules out any usage of "dsat(Y) sat(X)"

and "sat(Y) dsat(X)". Those are also overcomplete.

* `thresh(k,...)` is always "d", a non-HASSIG dissatisfaction with

just dissatisfactions must exist due to typing rules, and thus rules out

usage of the other dissatisfactions. They are also overcomplete.

### Resource Limits

Various types of Bitcoin Scripts have different resource limitations,

either through consensus or standardness. Some of them affect otherwise

valid Miniscripts:

* In P2WSH, scripts larger than 3600 bytes are invalid by standardness.

In Tapscript scripts are implicitly bounded by the maximum size of a

block (1 million virtual bytes).

* In P2WSH, script satisfactions where the total number of non-push

opcodes plus the number of keys participating in all executed

`CHECKMULTISIG` is above 201 are invalid by consensus.

* In both Tapscript and P2WSH, script satisfactions which make the stack

exceed 1000 elements before or during execution are invalid.

* In P2WSH, satisfactions with a witness consisting of over 100 stack

elements (excluding the script itself) are invalid by standardness.

A static analysis can be performed on a Miniscript to verify if none,

all or any of the spending

paths hit any of the limits.

## Test Vectors

TBD

## Backwards Compatibility

Miniscript's syntax is compatible with BIP 380 Output Script

Descriptors, and should be considered

an extension to it that provides a new type of Script expression that is

only valid in

`wsh()` and `tr()` contexts. As these are wholly new expressions, they

are not

compatible with any existing implementation of descriptors.

Additionally, the scripts produced are

unlikely to be standard scripts.

The `pk()`, `pkh()`, `multi()`, and `multi_a()`

fragments overlap with existing descriptors. These parse to the same

semantic meanings as those

descriptors and produce the same scripts.

## Reference Implementation

A first reference implementation and documentation for Miniscript in

P2WSH was originally published at

https://github.com/sipa/miniscript .

The reference implementation for Miniscript in P2WSH was introduced in

Bitcoin Core through PRs

https://github.com/bitcoin/bitcoin/pull/24147

https://github.com/bitcoin/bitcoin/pull/24148 and

https://github.com/bitcoin/bitcoin/pull/24149 . The last one to be

merged was released in Bitcoin

Core version 25.0.

The reference implementation for Miniscript in Tapscript was introduced

in Bitcoin Core in PR

https://github.com/bitcoin/bitcoin/pull/27255 . This PR was merged and

released for Bitcoin Core

version 26.0.

Although Miniscript has been implemented and is in use by a couple of

implementations, it doesn't have a formal BIP. As such, I and a few

others have adapted the reference website's documentation to be in the

BIP format, which is provided below. The text, and any changes that may

be made, is also available at

https://github.com/achow101/bips/blob/miniscript/bip-miniscript.md.

Any feedback on this, particularly about what else should be included,

or what could be excluded, would be welcome.

Thanks,

Ava

***

<pre>

BIP: miniscript

Layer: Applications

Title: Miniscript

Author: Pieter Wuille <pie...@wuille.net>

Andrew Poelstra <andrew....@gmail.com>

Sanket Kanjalkar <sanke...@gmail.com>

Antoine Poinsot <daro...@protonmail.com>

Ava Chow <m...@achow101.com>

Comments-Summary: No comments yet.

Comments-URI:

https://github.com/bitcoin/bips/wiki/Comments:BIP-miniscript

Status: Draft

Type: Informational

Created: 2023-10-10

License: CC0-1.0

</pre>

## Abstract

This document specifies Miniscript, a language for writing (a subset of)

Bitcoin Scripts in a

structured way, enabling analysis, composition, generic signing and more.

## Copyright

This document is licensed under the Creative Commons CC0 1.0 Universal

license.

## Motivation

Bitcoin Script is an unusual stack-based language with many edge cases,

designed for implementing

spending conditions consisting of various combinations of signatures,

hash locks, and time locks.

Yet despite being limited in functionality it is still highly nontrivial to:

* Given a combination of spending conditions, finding the most

economical script to implement it.

* Given two scripts, construct a script that implements a composition of

their spending conditions (e.g. a multisig where one of the "keys" is

another multisig).

* Given a script, find out what spending conditions it permits.

* Given a script and access to a sufficient set of private keys,

construct a general satisfying witness for it.

* Given a script, be able to predict the cost of spending an output.

* Given a script, know whether particular resource limitations like the

ops limit might be hit when spending.

Miniscript functions as a representation for scripts that makes this

sort of operations possible.

It has a structure that allows composition. It is very easy to

statically analyze for various

properties (spending conditions, correctness, security properties,

malleability, ...). It can be

targeted by spending policy compilers. Finally, compatible scripts can

easily be converted to

Miniscript form - avoiding the need for additional metadata for e.g.

signing devices that support

it.

## Specification

These specifications apply to P2WSH (BIP143) and Tapscript (BIP342)

scripts, with only minor

variations between the two. Differences are noted inline. Unless

explicitly stated specifications

apply to both.

### Translation Table

This table shows all Miniscript *fragments* and their associated

semantics and Bitcoin Script.

Fragments that do not change the semantics of their subexpressions are

called *wrappers*. Normal

fragments use a `fragment(arg1, arg2, ..)` notation, while wrappers are

written using

prefixes separated from other fragments by a colon. The colon is dropped

between subsequent

wrappers; e.g. `dv:older(144)` is the `d:` wrapper applied to the

`v:` wrapper applied to the `older` fragment for 144 blocks.

The `pk`, `pkh`, and `and_n` fragments and `t:`,

`l:`, and `u:` wrappers are syntactic sugar for other Miniscripts, as listed

in the table below. Note that `<20>` are in hex representation in this

document.

Miniscript fragments are expected to be used in [BIP

382](bip-0382.mediawiki) `wsh()` descriptors

and [BIP 386](bip-0386.mediawiki) `tr()` descriptors. Key expressions

are specified in

[BIP 380](bip-0380.mediawiki#user-content-Key_Expressions).

Additionally, BIPs 382 and 386 specify

restrictions on key expressions and what they resolve to - these apply

to key expressions in

Miniscript. BIP 382's key expression restrictions apply to Miniscript in

P2WSH contexts, and BIP

386's key expression restrictions apply to Miniscript in P2TR contexts.

| Semantics | Miniscript

Fragment | Bitcoin Script

|----------------------------------------------------------|-------------------------------|---------------

| false |

`0` | `0`

| true |

`1` | `1`

| check(key) |

`pk_k(key)` | `<key>`

| |

`pk_h(key)` | ` DUP HASH160 <HASH160(key)> EQUALVERIFY `

| | `pk(key)` =

`c:pk_k(key)` | `<key> CHECKSIG`

| | `pkh(key)`

= `c:pk_h(key)` | ` DUP HASH160 <HASH160(key)> EQUALVERIFY CHECKSIG`

| nSequence ≥ n (and compatible) |

`older(n)` | `<n> CHECKSEQUENCEVERIFY`

| nLockTime ≥ n (and compatible) |

`after(n)` | `<n> CHECKLOCKTIMEVERIFY`

| len(x) = 32 and SHA256(x) = h |

`sha256(h)` | `SIZE <20> EQUALVERIFY SHA256 <h> EQUAL`

| len(x) = 32 and HASH256(x) = h |

`hash256(h)` | `SIZE <20> EQUALVERIFY HASH256 <h> EQUAL`

| len(x) = 32 and RIPEMD160(x) = h |

`ripemd160(h)` | `SIZE <20> EQUALVERIFY RIPEMD160 <h> EQUAL`

| len(x) = 32 and HASH160(x) = h |

`hash160(h)` | `SIZE <20> EQUALVERIFY HASH160 <h> EQUAL`

| (X and Y) or Z |

`andor(X,Y,Z)` | `[X] NOTIF [Z] ELSE [Y] ENDIF`

| X and Y |

`and_v(X,Y)` | `[X] [Y]`

| |

`and_b(X,Y)` | `[X] [Y] BOOLAND`

| |

`and_n(X,Y)` = `andor(X,Y,0)` | `[X] NOTIF 0 ELSE [Y] ENDIF`

| X or Z |

`or_b(X,Z)` | `[X] [Z] BOOLOR`

| |

`or_c(X,Z)` | `[X] NOTIF [Z] ENDIF`

| |

`or_d(X,Z)` | `[X] IFDUP NOTIF [Z] ENDIF`

| |

`or_i(X,Z)` | `IF [X] ELSE [Z] ENDIF`

| X_1 + ... + X_n = k |

`thresh(k,X_1,...,X_n)` | `[X_1] [X_2] ADD ... [X_n] ADD ... <k>

EQUAL`

| check(key_1) + ... + check(key_n) = k *(P2WSH only)* |

`multi(k,key_1,...,key_n)` | `<k> <key_1> ... <key_n> <n> CHECKMULTISIG`

| check(key_1) + ... + check(key_n) = k *(Tapscript only)* |

`multi_a(k,key_1,...,key_n)` | `<key_1> CHECKSIG <key_2> CHECKSIGADD

... <key_n> CHECKSIGADD <k> NUMEQUAL`

| X (identities) |

`a:X` | `TOALTSTACK [X] FROMALTSTACK`

| |

`s:X` | `SWAP [X]`

| |

`c:X` | `[X] CHECKSIG`

| | `t:X` =

`and_v(X,1)` | `[X] 1`

| |

`d:X` | `DUP IF [X] ENDIF`

| |

`v:X` | `[X] VERIFY (or VERIFY version of last

opcode in [X])`

| |

`j:X` | `SIZE 0NOTEQUAL IF [X] ENDIF`

| |

`n:X` | `[X] 0NOTEQUAL`

| | `l:X` =

`or_i(0,X)` | `IF 0 ELSE [X] ENDIF`

| | `u:X` =

`or_i(X,0)` | `IF [X] ELSE 0 ENDIF`

### Type System

Not every Miniscript expression can be composed with every other. Some

return their result by

putting true or false on the stack; others can only abort or continue.

Some require subexpressions

that consume an exactly known number of arguments, while others need a

subexpression that has a

nonzero top stack element to satisfy. To model all these properties, we

define a correctness type

system for Miniscript.

#### Correctness

Every miniscript expression has one of four basic types: "**B**" (base),

"**V**" (verify),

"**K**" (key) and "**W**" (wrapped). Then there are 6 type modifiers

which guarantee additional

properties: "**z**" (zero arg), "**o**" (one-arg), "**n**" (nonzero),

"**d**"

(dissatisfiable), "**u**" (unit) and "**k**" (no timelock mixing).

The following table lists the correctness requirements for each of the

Miniscript expressions, and

its type properties in function of those of their subexpressions.

| Miniscript |

Requires | Type | Properties

|------------------------------|-------------------------------------------------------|-------------|-----------

| `0` | |

B | z; u; d

| `1` | |

B | z; u

| `pk_k(key)` | |

K | o; n; d; u

| `pk_h(key)` | |

K | n; d; u

| `older(n)`, `after(n)` | 1 ≤ n <

2<sup>31</sup> | B | z

| `sha256(h)` | |

B | o; n; d; u

| `ripemd160(h)` |

| B | o; n; d; u

| `hash256(h)` | |

B | o; n; d; u

| `hash160(h)` | |

B | o; n; d; u

| `andor(X,Y,Z)` | X is Bdu; Y and Z are both B, K, or

V | same as Y/Z |

z=z<sub>X</sub>z<sub>Y</sub>z<sub>Z</sub>;

o=z<sub>X</sub>o<sub>Y</sub>o<sub>Z</sub> or

o<sub>X</sub>z<sub>Y</sub>z<sub>Z</sub>; u=u<sub>Y</sub>u<sub>Z</sub>;

d=d<sub>Z</sub>

| `and_v(X,Y)` | X is V; Y is B, K, or

V | same as Y |

z=z<sub>X</sub>z<sub>Y</sub>; o=z<sub>X</sub>o<sub>Y</sub> or

z<sub>Y</sub>o<sub>X</sub>; n=n<sub>X</sub> or

z<sub>X</sub>n<sub>Y</sub>; u=u<sub>Y</sub>

| `and_b(X,Y)` | X is B; Y is

W | B |

z=z<sub>X</sub>z<sub>Y</sub>; o=z<sub>X</sub>o<sub>Y</sub> or

z<sub>Y</sub>o<sub>X</sub>; n=n<sub>X</sub> or

z<sub>X</sub>n<sub>Y</sub>; d=d<sub>X</sub>d<sub>Y</sub>; u

| `or_b(X,Z)` | X is Bd; Z is

Wd | B |

z=z<sub>X</sub>z<sub>Z</sub>; o=z<sub>X</sub>o<sub>Z</sub> or

z<sub>Z</sub>o<sub>X</sub>; d; u

| `or_c(X,Z)` | X is Bdu; Z is

V | V |

z=z<sub>X</sub>z<sub>Z</sub>; o=o<sub>X</sub>z<sub>Z</sub>

| `or_d(X,Z)` | X is Bdu; Z is

B | B |

z=z<sub>X</sub>z<sub>Z</sub>; o=o<sub>X</sub>z<sub>Z</sub>;

d=d<sub>Z</sub>; u=u<sub>Z</sub>

| `or_i(X,Z)` | both are B, K, or

V | same as X/Z |

o=z<sub>X</sub>z<sub>Z</sub>; u=u<sub>X</sub>u<sub>Z</sub>;

d=d<sub>X</sub> or d<sub>Z</sub>

| `thresh(k,X_1,...,X_n)` | 1 ≤ k ≤ n; X<sub>1</sub> is Bdu;

others are Wdu | B | z=all are z; o=all are z except one is o;

d; u

| `multi(k,key_1,...,key_n)` | 1 ≤ k ≤

n | B | n; d; u

| `multi_a(k,key_1,...,key_n)` | 1 ≤ k ≤

n | B | d; u

| `a:X` | X is

B | W |

d=d<sub>X</sub>; u=u<sub>X</sub>

| `s:X` | X is

Bo | W |

d=d<sub>X</sub>; u=u<sub>X</sub>

| `c:X` | X is

K | B |

o=o<sub>X</sub>; n=n<sub>X</sub>; d=d<sub>X</sub>; u

| `d:X` | X is

Vz | B | o; n;

d; *(Tapscript only)* u

| `v:X` | X is

B | V |

z=z<sub>X</sub>; o=o<sub>X</sub>; n=n<sub>X</sub>

| `j:X` | X is

Bn | B |

o=o<sub>X</sub>; n; d; u=u<sub>X</sub>

| `n:X` | X is

B | B |

z=z<sub>X</sub>; o=o<sub>X</sub>; n=n<sub>X</sub>; d=d<sub>X</sub>; u

#### Malleability

Malleability is the ability for a third party (*not* a participant in

the script) to modify an

existing satisfaction into another valid satisfaction. To analyze the

malleability guarantees of a

script we define three additional type properties: "**s**" (signed),

"**f**" (forced) and

"**e**" (expressive).

The following table lists the malleability properties and requirement of

each fragment.

| Miniscript | Requires | Properties

|------------------------------|---------------------------------------------------------------------|-----------

| `0` | | s, e

| `1` | | f

| `pk_k(key)` | | s, e

| `pk_h(key)` | | s, e

| `older(n)` | | f

| `after(n)` | | f

| `sha256(h)` | |

| `ripemd160(h)` | |

| `hash256(h)` | |

| `hash160(h)` | |

| `andor(X,Y,Z)` | e<sub>X</sub> and (s<sub>X</sub> or

s<sub>Y</sub> or s<sub>Z</sub>) | s=s<sub>Z</sub> and (s<sub>X</sub> or

s<sub>Y</sub>); f=f<sub>Z</sub> and (s<sub>X</sub> or f<sub>Y</sub>);

e=e<sub>Z</sub> and (s<sub>X</sub> or f<sub>Y</sub>)

| `and_v(X,Y)` | | s=s<sub>X</sub> or s<sub>Y</sub>; f=s<sub>X</sub> or

f<sub>Y</sub>

| `and_b(X,Y)` | | s=s<sub>X </sub>or s<sub>Y;</sub>

f=f<sub>Xf</sub><sub>Y</sub> or s<sub>X</sub>f<sub>X</sub> or

s<sub>Y</sub>f<sub>Y</sub>;

e=e<sub>X</sub>e<sub>Y</sub>s<sub>X</sub>s<sub>Y</sub>

| `or_b(X,Z)` | e<sub>Xe</sub><sub>Z </sub>and

(s<sub>X</sub> or s<sub>Z</sub>) | s=s<sub>X</sub>s<sub>Z</sub>; e

| `or_c(X,Z)` | e<sub>X</sub> and (s<sub>X</sub> or

s<sub>Z</sub>) | s=s<sub>X</sub>s<sub>Z</sub>; f

| `or_d(X,Z)` | e<sub>X</sub> and (s<sub>X</sub> or

s<sub>Z</sub>) | s=s<sub>X</sub>s<sub>Z</sub>;

f=f<sub>Z</sub>; e=e<sub>Z</sub>

| `or_i(X,Z)` | s<sub>X</sub> or

s<sub>Z</sub> |

s=s<sub>X</sub>s<sub>Z</sub>; f=f<sub>X</sub>f<sub>Z</sub>;

e=e<sub>X</sub>f<sub>Z</sub> or e<sub>Z</sub>f<sub>X</sub>

| `thresh(k,X_1,...,X_n)` | all are e; at most k are

non-s | s=at most k-1 are non-s;

e=all are s

| `multi(k,key_1,...,key_n)` | | s; e

| `multi_a(k,key_1,...,key_n)` | | s; e

| `a:X` | | s=s<sub>X</sub>; f=f<sub>X</sub>; e=e<sub>X</sub>

| `s:X` | | s=s<sub>X</sub>; f=f<sub>X</sub>; e=e<sub>X</sub>

| `c:X` | | s; f=f<sub>X</sub>; e=e<sub>X</sub>

| `d:X` | | s=s<sub>X</sub>; e

| `v:X` | | s=s<sub>X</sub>; f

| `j:X` | | s=s<sub>X</sub>; e=f<sub>X

| `n:X` | | s=s<sub>X</sub>; f=f<sub>X</sub>; e=e<sub>X</sub>

### Satisfaction

The following table shows all valid satisfactions and dissatisfactions

for every Miniscript, using

satisfactions and dissatisfactions of its subexpressions. Multiple

possibilities are separated by

semicolons. Some options are not actually necessary to produce correct

witnesses, and are called

*non-canonical* options. They are listed for completeness, but

~~[struckthrough]~~. The

fragments where a satisfaction or dissatisfaction does not exist will

contain *(none)*. The

fragments where the satisfaction or dissatisfaction is to provide no

data will contain *(empty)*.

| Miniscript | Dissatisfactions

(dsat) | Satisfactions (sat)

|------------------------------|---------------------------------------------------------|--------------------

| `0` |

*(empty)* | *(none)*

| `1` |

*(none)* | *(empty)*

| `pk_k(key)` |

0 | sig

| `pk_h(key)` | 0

key | sig key

| `older(n)` |

*(none)* | *(empty)*

| `after(n)` |

*(none)* | *(empty)*

| `sha256(h)` | any 32-byte vector except the

preimage | preimage

| `ripemd160(h)` | any 32-byte vector except the

preimage | preimage

| `hash256(h)` | any 32-byte vector except the

preimage | preimage

| `hash160(h)` | any 32-byte vector except the

preimage | preimage

| `andor(X,Y,Z)` | dsat(Z) dsat(X); ~~[dsat(Y)

sat(X)]~~ | sat(Y) sat(X); sat(Z) dsat(X)

| `and_v(X,Y)` | *(none)*; ~~[dsat(Y)

sat(X)]~~ | sat(Y) sat(X)

| `and_b(X,Y)` | dsat(Y) dsat(X); ~~[sat(Y) dsat(X)];

[dsat(Y) sat(X)]~~ | sat(Y) sat(X)

| `or_b(X,Z)` | dsat(Z)

dsat(X) | dsat(Z) sat(X); sat(Z)

dsat(X); ~~[sat(Z) sat(X)]~~

| `or_c(X,Z)` |

*(none)* | sat(X); sat(Z)

dsat(X)

| `or_d(X,Z)` | dsat(Z)

dsat(X) | sat(X); sat(Z) dsat(X)

| `or_i(X,Z)` | dsat(X) 1; dsat(Z)

0 | sat(X) 1; sat(Z) 0

| `thresh(k,X_1,...,X_n)` | All dsats; ~~[Sats/dsats with 1 ≤

#(sats) ≠ k]~~ | Sats/dsats with #(sats) = k

| `multi(k,key_1,...,key_n)` | 0 0 ... 0 (k+1

times) | 0 sig ... sig

| `multi_a(k,key_1,...,key_n)` | 0 ... 0 (n

times) | sig/0 with #(sig) = k and

#(sigs/0) = n

| `a:X` |

dsat(X) | sat(X)

| `s:X` |

dsat(X) | sat(X)

| `c:X` |

dsat(X) | sat(X)

| `d:X` |

0 | sat(X) 1

| `v:X` |

*(none)* | sat(X)

| `j:X` | 0; ~~[dsat(X) (if nonzero top

stack)]~~ | sat(X)

| `n:X` |

dsat(X) | sat(X)

#### Non-malleable Satisfaction Algorithm

In order to produce non-malleable satisfactions we make use of a

function that returns the optimal

satisfaction and dissatisfaction for a given expression (if any exist),

or a special DONTUSE value,

together with an optional HASSIG marker that tracks whether the solution

contains at least one

signature. To implement the function:

* Invoke the function recursively for all subexpressions, obtaining all

their satisfactions/dissatisfactions.

* Iterate over all the valid satisfactions/dissatisfactions in the table

above (including the non-canonical ones), taking into account:

* The dissatisfactions for `sha256`, `ripemd160`, `hash256`, and

`hash160` are always malleable, so instead use DONTUSE there.

* The non-canonical options for `and_b`, `or_b`, and `thresh` are

always overcomplete, so instead use DONTUSE there as well (with HASSIG

flag if the original non-canonical solution had one).

* The satisfactions for `pk_k`, `pk_h`, and `multi` can be marked HASSIG.

* When constructing solutions by combining results for subexpressions,

the result is DONTUSE if any of the constituent results is DONTUSE.

Furthermore, the result gets the HASSIG tag if any of the constituents does.

* If among all valid solutions (including DONTUSE ones) more than one

does not have the HASSIG marker, return DONTUSE.

* If instead exactly one does not have the HASSIG marker, return that

solution.

* If all valid solutions have the HASSIG marker, but all of them are

DONTUSE, return DONTUSE-HASSIG. The HASSIG marker is important because

while this represents a choice between multiple options that would cause

malleability if used, they are not available to the attacker, and we may

be able to avoid them entirely still.

* Otherwise, all not-DONTUSE options are valid, so return the smallest

one (in terms of witness size).

To produce an overall satisfaction, invoke the function on the toplevel

expression. If no valid

satisfaction is returned, or it is DONTUSE, fail. Otherwise, if any

timelocking is used in the

script but the result does not have the HASSIG flag, also fail. If the

satisfaction is both not

DONTUSE and HASSIG, return it.

## Discussion

## Security

Miniscript primarily aims to provide guarantees on the correctness of a

Bitcoin Script. That is, to

guarantee **consensus soundness** and **standardness completeness**.

Consensus soundness means

it is not possible to construct a consensus-valid witness for a Bitcoin

Script unless the Miniscript

spending conditions are met. Standardness completeness means a

standardness-valid witness can be

created for all spending paths of a Miniscript, assuming the resource

limits are respected and there

is no timelock mixing.

Additionally, Miniscript can guarantee the non-malleability and maximum

size of a witness. These can

assist in assessing the soundness of protocols where transaction fees

(and therefore transaction

size) are security-critical parameters.

Hash preimages are constrained to 32 bytes to disallow various forms of

griefing, including making

non-standard (un-relayable) transactions, consensus-invalid swaps across

blockchains, as well as

ensure that satisfaction cost can be accurately calculated.

In order for these properties to not just apply to script, but to an

entire transaction, it's

important that the witness commits to all data relevant for

verification. In practice this means

that scripts whose conditions can be met without any digital signature

are insecure. Besides being

trivially insecure, note how a transaction lacking a signature check

allows an attacker to change

its nLockTime and nSequence fields to meet additional timelock conditions.

### Type system

To statically verify the correctness and malleability guarantees

discussed in the previous section,

we define a type system. See the specifications above for a reference of

each fragment's

requirements and properties. Here we give more information about each type.

Every expression has one of four basic types:

* "**B**" Base expressions. These take their inputs from the top of the

stack. When satisfied, they push a nonzero value of up to 4 bytes onto

the stack. When dissatisfied, they push an exact 0 onto the stack (if

dissatisfaction without aborting is possible at all). This type is used

for most expressions, and required for the top level expression. An

example is `older(n)` = `<n> CHECKSEQUENCEVERIFY`.

* "**V**" Verify expressions. Like "B", these take their inputs from the

top of the stack. Upon satisfaction however, they continue without

pushing anything. They cannot be dissatisfied (will abort instead). A

"V" can be obtained using the `v:` wrapper on a "B" expression, or by

combining other "V" expressions using `and_v`, `or_i`, `or_c`, or

`andor`. An example is `v:pk(key)` = `<key> CHECKSIGVERIFY`.

* "**K**" Key expressions. They again take their inputs from the top of

the stack, but instead of verifying a condition directly they always

push a public key onto the stack, for which a signature is still

required to satisfy the expression. A "K" can be converted into a "B"

using the `c:` wrapper. An example is `pk_h(key)` = `DUP HASH160

<Hash160(key)> EQUALVERIFY`.

* "**W**" Wrapped expressions. They take their inputs from one below the

top of the stack, and push a nonzero (in case of satisfaction) or zero

(in case of dissatisfaction) either on top of the stack, or one below.

So for example a 3-input "W" would take the stack "A B C D E F" and turn

it into "A B F 0" or "A B 0 F" in case of dissatisfaction, and "A B F n"

or "A B n F" in case of satisfaction (with n a nonzero value). Every "W"

is either `s:B` (SWAP B) or `a:B` (TOALTSTACK B FROMALTSTACK). An

example is `s:pk(key)` = `SWAP <key> CHECKSIG`.

Then there are 6 type modifiers, which guarantee additional properties:

* "**z**" Zero-arg: this expression always consumes exactly 0 stack

elements.

* "**o**" One-arg: this expression always consumes exactly 1 stack element.

* "**n**" Nonzero: this expression always consumes at least 1 stack

element, no satisfaction for this expression requires the top input

stack element to be zero.

* "**d**" Dissatisfiable: a dissatisfaction for this expression can

unconditionally be constructed. This implies the dissatisfaction cannot

include any signature or hash preimage, and cannot rely on timelocks

being satisfied.

* "**u**" Unit: when satisfied, this expression will put an exact 1 on

the stack (as opposed to any nonzero value).

* "**k**" No timelock mixing. This expression does not contain a mix of

heightlock and timelock of the same type. If the miniscript does not

have the "k" property, the miniscript template will not match the user

expectation of the corresponding spending policy.

Finally to analyze malleability guarantees we introduce 3 new type

modifiers:

* "**s**" Signed: satisfying this expression always requires a signature

(predicting whether all satisfactions will be HASSIG).

* "**f**" Forced: dissatisfying this expression always requires a

signature (predicting whether all dissatisfactions will be HASSIG).

* "**e**" Expressive: this requires a unique unconditional

dissatisfaction to exist, and forces all conditional dissatisfactions

(if any) to require a signature.

### Malleability

Since Segwit, malleating a transaction no longer breaks the validity of

unconfirmed descendant

transactions. However, unintentional malleability may still have a

number of much weaker undesirable

effects. If a witness can be stuffed with additional data, the

transaction's feerate will go down,

potentially to the point where its ability to propagate and get

confirmed is impacted. Additionally,

malleability can be exploited to add roundtrips to BIP152 block

propagation, by trying to get

different miners to mine different versions of the same transaction.

Finally, malleability may

interfere with the usage of hash locks as a mechanism for publishing

preimages.

Using the malleability type properties it is possible to determine

statically whether a script can

be nonmalleably satisfied under all circumstances. In many cases it is

reasonable to only accept

such guaranteed-nonmalleable scripts, as unexpected behavior can occur

when using other scripts.

For example, when running the non-malleable satisfaction algorithm

above, adding available

preimages, or increasing the nLockTime/nSequence values actually may

make it fail where it succeeded

before. This is because a larger set of met conditions may mean an

existing satisfaction goes from

nonmalleable to malleable. Restricting things to scripts that are

guaranteed to be satisfiable in a

non-malleable way avoids this problem.

When analysing Miniscripts for resource limits, restricting yourself to

just non-malleable solutions

(or even non-malleable scripts) also leads to tighter bounds, as all

non-canonical satisfactions and

dissatisfactions can be left out of consideration.

The malleability analysis makes the following assumptions:

* The attacker does not have access to any of the private keys of public

keys that participate in the Script. Participants with private keys

inherently have the ability to produce different satisfactions by

creating multiple signatures. While it is also interesting to study the

impact rogue participants can have, we treat it as a distinct problem.

* The attacker only has access to hash preimages that honest users have

access to as well. This is a reasonable assumption because hash

preimages are revealed once globally, and then available to everyone. On

the other hand, making the assumption that attackers may have access to

more preimages than honest users makes a large portion of scripts

impossible to satisfy in a non-malleable way.

* The attacker gets to see exactly one satisfying witness of any

transaction. If he sees multiple, it becomes possible for the attacker

to mix and match different satisfactions. This is very hard to reason about.

* We restrict this analysis to scripts where no public key is repeated.

If signatures constructed for one part of the script can be bound to

other checks in the same script, a variant of the mixing from the

previous point becomes available that is equally hard to reason about.

Furthermore this situation can be avoided by using separate keys.

#### Non-Malleable Satisfaction

Malleable satisfactions or dissatisfactions appear whenever options are

available to attackers distinct from the one taken by honest users. This

can happen for multiple reasons:

1. Two or more options for a satisfaction or dissatisfaction are listed

in the table above which are both available to attackers directly.

Regardless of which option is used in the honest solution, the attacker

can change the solution to the other one.

2. Two or more options for a satisfaction or dissatisfaction are listed

in the table above, only one of which is available to attackers, but the

honest solution uses another one. In that case, the attacker can modify

the solution to pick the one available to him.

3. The honest users pick a solution that contains a satisfaction which

can be turned into a dissatisfaction without invalidating the overall

witness. Those are called overcomplete solutions.

Because we assume attackers never have access to private keys, we can

treat any solution that

includes a signature as one that is unavailable to attackers. For

others, the worst case is that the

attacker has access to every solution the honest users have, but no

others: for preimages this is an

explicit assumption, while timelock availability is determined by the

nLockTime and nSequence fields

in the transaction. As long as the overall satisfaction includes at

least one signature, those

values are fixed, and timelock availability is identical for attackers

and honest users.

The description of the non-malleable satisfaction algorithm can be used

to show that no

non-canonical solutions listed in the satisfaction table can occur

inside non-malleable

satisfaction:

* Some of the non-canonical options (the `or_b`, `and_b`, and `thresh`

ones) are overcomplete, and thus can clearly not appear in non-malleable

satisfactions.

* The fact that non-"d" expressions cannot be dissatisfied in valid

witnesses rules out the usage of the non-canonical `and_v` dissatisfaction.

* "d" expressions are defined to be unconditionally dissatisfiable,

which implies that for those a non-HASSIG dissatisfaction must exist.

Non-HASSIG solutions must be preferred over HASSIG ones (reason 2), and

when multiple non-HASSIG ones exist, none can be used (reason 1). This

lets us rule out the other non-canonical options in the table:

* `j:X` is always "d", its non-HASSIG dissatisfaction "0" always

exists, and thus rules out any usage of "dsat(X)".

* If `andor(X,Y,Z)` is "d", a non-HASSIG dissatisfaction "dsat(Z)

dsat(X)" must exist, and thus rules out any usage of "dsat(Y) sat(X)".

* If `and_b(X,Y)` is "d", a non-HASSIG dissatisfaction "dsat(Y)

dsat(X)" must exist, and thus rules out any usage of "dsat(Y) sat(X)"

and "sat(Y) dsat(X)". Those are also overcomplete.

* `thresh(k,...)` is always "d", a non-HASSIG dissatisfaction with

just dissatisfactions must exist due to typing rules, and thus rules out

usage of the other dissatisfactions. They are also overcomplete.

### Resource Limits

Various types of Bitcoin Scripts have different resource limitations,

either through consensus or standardness. Some of them affect otherwise

valid Miniscripts:

* In P2WSH, scripts larger than 3600 bytes are invalid by standardness.

In Tapscript scripts are implicitly bounded by the maximum size of a

block (1 million virtual bytes).

* In P2WSH, script satisfactions where the total number of non-push

opcodes plus the number of keys participating in all executed

`CHECKMULTISIG` is above 201 are invalid by consensus.

* In both Tapscript and P2WSH, script satisfactions which make the stack

exceed 1000 elements before or during execution are invalid.

* In P2WSH, satisfactions with a witness consisting of over 100 stack

elements (excluding the script itself) are invalid by standardness.

A static analysis can be performed on a Miniscript to verify if none,

all or any of the spending

paths hit any of the limits.

## Test Vectors

TBD

## Backwards Compatibility

Miniscript's syntax is compatible with BIP 380 Output Script

Descriptors, and should be considered

an extension to it that provides a new type of Script expression that is

only valid in

`wsh()` and `tr()` contexts. As these are wholly new expressions, they

are not

compatible with any existing implementation of descriptors.

Additionally, the scripts produced are

unlikely to be standard scripts.

The `pk()`, `pkh()`, `multi()`, and `multi_a()`

fragments overlap with existing descriptors. These parse to the same

semantic meanings as those

descriptors and produce the same scripts.

## Reference Implementation

A first reference implementation and documentation for Miniscript in

P2WSH was originally published at

https://github.com/sipa/miniscript .

The reference implementation for Miniscript in P2WSH was introduced in

Bitcoin Core through PRs

https://github.com/bitcoin/bitcoin/pull/24147

https://github.com/bitcoin/bitcoin/pull/24148 and

https://github.com/bitcoin/bitcoin/pull/24149 . The last one to be

merged was released in Bitcoin

Core version 25.0.

The reference implementation for Miniscript in Tapscript was introduced

in Bitcoin Core in PR

https://github.com/bitcoin/bitcoin/pull/27255 . This PR was merged and

released for Bitcoin Core

version 26.0.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu