summaryrefslogtreecommitdiff
path: root/bip-0379.md
blob: 10755d4e8e1cb04562be10d9c97633267b4ea4d4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
<pre>
  BIP: 379
  Layer: Applications
  Title: Miniscript
  Author: Pieter Wuille <pieter@wuille.net>
          Andrew Poelstra <andrew.poelstra@gmail.com>
          Sanket Kanjalkar <sanket1729@gmail.com>
          Antoine Poinsot <darosior@protonmail.com>
          Ava Chow <me@achow101.com>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0379
  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 ([BIP 141](bip-0141.mediawiki)) and Tapscript ([BIP 342](bip-0342.mediawiki)) scripts, with only minor
variations between the two. Differences are noted inline. Unless explicitly stated otherwise,
specifications apply to both. P2SH and bare scripts are excluded from this specification.

### Translation Table

Miniscript consists of a set of script *fragments* which are designed to be safely and correctly composabe.

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. From a user's perspective,
Miniscript is not a separate language, but rather a significant expansion of the descriptor language.

| 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 5 type modifiers that guarantee additional
properties: "**z**" (zero-arg), "**o**" (one-arg), "**n**" (nonzero), "**d**"
(dissatisfiable), and "**u**" (unit).

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 &le; n &lt; 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 &le; k &le; 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 &le; k &le; n &le; 20                               | B           | n; d; u
| `multi_a(k,key_1,...,key_n)` | 1 &le; k &le; 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

#### Timelock Type Mixing

There is one additional correctness property that Miniscript expressions must satisfy:
the four timelock types (absolute time based, absolute height based, relative time based, and
relative height based) must not be mixed in an incompatible way.

Within `and` combinators and the `thresh` combinator where k >= 2, it is illegal for both absolute
height based and time based timelocks to appear, or for both relative height based and time based
timelocks to appear.

For all other combinators, it is legal to mix timelock types. It is also always legal to
mix absolute and relative timelocks (even if one is height based and the other is time based).

#### Malleability

Malleability is the ability for a third party (someone who does *not* hold a participating private
key) 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 inefficient and provably unnecessary to the satisfaction algorithm
described below, but are valid according to script rules and could be used by a malleator or other
non-standard actor. These are called *non-canonical* options, and 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 &le; #(sats) &ne; 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) &ne; k]~~        | 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 ("don't use") value,
together with an optional HASSIG ("has signature") 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 non-malleably satisfied under all circumstances. In many cases it is reasonable to only accept
such guaranteed-non-malleable 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
non-malleable 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.
* The attacker is constrained by common standardness rules. A miner may be able to malleate a witness considered non-malleable by Miniscript.

#### 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
[24147](https://github.com/bitcoin/bitcoin/pull/24147), [24148](https://github.com/bitcoin/bitcoin/pull/24148), and
[24149](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
[27255](https://github.com/bitcoin/bitcoin/pull/27255). This PR was merged and released in Bitcoin Core
version 26.0.