By Pieter Wuille & Andrew Poelstra
Introduction
Bitcoin Script
Bitcoin has always had a mechanism for making coins spendable by more complex policies than just a single key: the Script system. While Script is primarily used for single-key payments, it is also the basis for a variety of multisig wallets, atomic swap constructions, and the Lightning network.
That’s not all it can do, however. Script can be used to represent complex conditions required to release a transaction — e.g. (two of A, B, C) and (D or (E and F)), where A-F each represent a unique key — as well as hash preimage checks, timelocks, and a few more exotic constructions.
Difficult to Verify
One reason that we’re not anywhere close to using Script’s full potential is that actually constructing scripts for nontrivial tasks is cumbersome: it’s hard to verify their correctness and security, and even harder to find the most economical way to write things.
That’s only part of the problem: even when you know the right script, designing applications and protocols to negotiate and construct transactions using it needs a lot of ad-hoc development work each time a new construction is designed. Any kind of flexibility often resorts to ugly template-matching to detect compatible scripts, and each addition requires more engineering resources for analysis and quality assurance.
What if instead Bitcoin applications could work with any script, not just the few scripts they were designed for? We wouldn’t be restricted to using one-off designs, and could start designing applications that build and use on-the-fly generated scripts, based on user-specified requirements. Wallet developers could also introduce more script-based options while retaining interoperability with other wallets.
Miniscript
Enter Miniscript, a language for representing Bitcoin Scripts in a structured way, enabling efficient analysis, composition, generic signing and more.
For example the Bitcoin script
where A and B are public keys, can be converted to Miniscript notation as
This notation makes it clear that the semantics of the script are permitting spending when either A signs, or when B signs after 144 blocks. A large portion of meaningful scripts can be written this way.
Making scripts human (or engineer…) readable is just one of Miniscript’s features. Its primary purpose is enabling automated reasoning over Script, as demonstrated by the use cases below.
Use Cases
Using Bitcoin Script today for building sophisticated spending conditions is far harder than it needs to be, requiring special-purpose software to be developed, tested, and deployed for each new use case. Miniscript can cover these cases in a way that generalizes across arbitrary sets of spending conditions, and is frequently much simpler and more reliable than a special-purpose solution would be.
Optimized Script
One such case is finding an optimal script which implements a given set of spending conditions. In Bitcoin Script, there are many different ways to require a signature, describe a conjunction or disjunction, or implement a threshold. Even for an experienced Bitcoin Script developer, the correct choice may depend on the relative probabilities of different conditions being satisfied, and be difficult to calculate. Our online compiler, also available as C++ source, or implemented as part of the rust-miniscript library, can instantly find the optimal Miniscript corresponding to a given spending policy.
The example in the introduction can be obtained by compiling the policy
which is a way of writing that the left side of the or (A signs) has a 99% probability of being taken, and the right side (B signs after 144 blocks) has a 1% chance of being taken.
Generic Spending
Once an efficient script has been found, a common barrier to many uses of Script is the lack of interoperability between different spending mechanisms. Users who wish to implement long-term timelocks or complex multisignature requirements may be blocked by the fear that their counterparties do not (or will not) have the software to recognize and spend the coins controlled by the policy.
Miniscript, by virtue of directly representing spending conditions, allows arbitrary policies to be expressed such that anyone can:
- compute the associated address(es) to the script;
- determine which signers are necessary or sufficient to signing at a given time;
- produce a valid transaction, given a sufficient set of signatures.
Users do not need to worry that all participants are using compatible software, or that such software will continue to exist by the time such timelocks are needed.
They also do not need to worry that their needs may change in a way incompatible with their signing software, assuring them that their use of Bitcoin Script will not constrain them.
Proof-of-Reserves
Related to the problem of signing is the problem of proving reserves, a process by which a company proves that it can spend a set of bitcoins without actually spending them. While tools exist for this, such as Blockstream’s Proof of Reserves Tool, there is not yet a common standard used within the industry. Absent Miniscript, there was probably no possibility of achieving a standard that could encompass the diversity of custody solutions in use today.
Composition of Spending Policies
Let’s take a look at a specific example of a Bitcoin Script developer constrained by the need for interoperability. Consider the case of a company which is custodying a large number of bitcoins, and wishes for these coins to be spendable only with the consent of a majority of its directors. However, some individual directors want to use their own existing wallet software and hardware, with complex signing setups involving multiple keys across disparate locations, and don’t want to participate in a scheme that requires they sign using a single key provided by a dedicated application.
Without Miniscript, producing a script that encompassed all signers’ requirements, while assuring all signers that the complete script was sound and complete, and that their wallet software was compatible with the result, would present an insurmountable problem.
Using Miniscript, these directors can simply compose their policies in their own wallet software, constructing a single policy which describes a threshold requirement, then compile this to Miniscript. They can straightforwardly verify that the output from the compiler matches the original policy, and that the original policy meets everyone’s requirements. They can then use any Miniscript-compatible software to compute addresses on which to receive coins, collect signatures at the time of spending, and assemble these signatures into a valid transaction.
As a simple hypothetical example: a company is setting up custom multisig storage with two directors. One director is already using Blockstream Green (configured as a 2-of-2 which becomes a 1-of-2 after some delay), and the other is using Electrum (standard 1-of-1). Without tools that allow for the composition of secure, interoperable script policies, it would not be possible for the director using Green to add his policy as a “participant” to the company multisig. If Green and the software used to construct the company multisig both supported Miniscript, both directors could continue to use their preferred wallets directly, and without anyone even needing to know there are scripts under the hood.
Dynamic Federations
A specific example of the power of Miniscript can be found in Blockstream’s Liquid sidechain. A feature currently under development, known internally as dynamic federations, allows the existing Liquid members to manage the addition of new members or to update the script which controls spendability of the bitcoin under custody by the federation. Miniscript gives members the tooling to quickly and efficiently construct such scripts — indeed, the Miniscript compiler found a 22-byte shorter version of the existing Liquid script, a zero-effort 5% saving over our original, painstakingly hand-optimized script. But more importantly, it allows members to automatically verify important properties of proposed scripts, reducing the need for members to coordinate with each other or to execute expensive manual security audits of proposed scripts.
In particular, members can automatically verify that any script proposal includes:
- their own key;
- a timelocked emergency spending condition that is correct and sufficiently far in the future.
It also allows them to verify that the participants in a new federation are capable of spending coins controlled by the old federation. This check is essential to ensure that transitions do not result in loss of coins, even for users who were moving coins into the system at the time of transition, and would have been practically impossible without Miniscript.
History
The idea of Miniscript came together in the summer of 2018 as the culmination of several ideas that were then in development. In the middle of July, Pieter Wuille introduced output descriptors to Bitcoin Core, a universal way to describe the multitude of different address types that Core supported. Meanwhile, Partially Signed Bitcoin Transaction (PSBT, described in BIP 174), a wallet interoperability protocol developed by Andy Chow while he was interning at Blockstream that summer, was gaining traction in the wallet space.
An important component of PSBT is the finalizer, a participant who assembles an actual Bitcoin transaction from the collection of signers’ data contained in the PSBT. This assembly requires an understanding of the scripts being satisfied, meaning that PSBT-enabled wallets doing nontrivial things must implement their own special-purpose finalizers, requiring redundant development and limiting interoperability.
Blockstream’s Andrew Poelstra was struggling to accept an implementation of PSBT for rust-bitcoin, a general-purpose Bitcoin library for the Rust programming language. Such an implementation had been proposed by Carl Dong, but did not include a finalizer general enough to support all users of the library. Poelstra observed on IRC that “if you have highly structured script templates you can get away with not really understanding script”, an idea which became the kernel of Miniscript.
Unrelatedly, Poelstra and Wuille had been working on a custody-related project, and were frustrated by the lack of standard tooling available for complex multi-participant scripts. The two met to discuss this in August 2018. Wuille suggested implementing these “highly structured script templates” as an extension of Bitcoin Core’s output descriptors.
As the extension took form, it was split into a structured subset of Bitcoin Script, which became Miniscript, as well as a simpler “policy language” to directly represent spending conditions, and which could be compiled to Miniscript. In January 2019, Wuille presented the preliminary results at the Stanford Blockchain Conference.
The following May, Sanket Kanjalkar joined Blockstream for a three-month internship, focused on implementing tooling for Miniscript and helping to integrate it with Bitcoin Core. With his help, Miniscript was completely and repeatedly redesigned to be smaller, more efficient, more easily analyzable, and better protected against malleability. A final set of changes was made verifying a large set of random Miniscript-compatible scripts against the Bitcoin consensus and standardness rules. The result of these iterations is the Miniscript of today.
Related Work
Miniscript builds upon and integrates with many other projects in the Bitcoin ecosystem. In particular, as described above, Miniscript extends Bitcoin Core’s wallet’s output descriptors and complements PSBT to enable fully general updaters and finalizers.
Miniscript can be compared to Ivy, another language designed to make the advanced features of Bitcoin Script accessible. However, while Ivy compiles to Script, Miniscript is a direct representation of a (subset of) Script, meaning that the correctness and soundness of “miniscripts” can be computationally efficiently verified. Miniscript is also amenable to many other forms of static analysis that neither Script nor Ivy are.
Miniscript’s policy language is similar to Ivy in that both are abstractions which must be compiled to (Mini)Script in order to be used on the blockchain. However, Miniscript’s policy language is so structurally similar to Miniscript itself that the compiler’s output can be easily verified to match the compiler’s input — in fact, this can even be checked by hand — and easily verified to match the user’s expectations.
Another blockchain language related to Miniscript is Blockstream’s Simplicity. Like Miniscript, Simplicity is a low-level language designed to be directly embedded in blockchain transactions. Also like Miniscript, Simplicity supports many forms of static analysis that are critical when deploying blockchain contracts, but which nonetheless are very hard or impossible by design in alternatives such as Ethereum’s EVM.
Unlike Simplicity, which is powerful enough to express any computable function, Miniscript is very limited in scope: it can express signature requirements, timelocks, hash preimages, and arbitrary combinations of these. This reduction in scope makes Miniscript easier to reason about for the use cases that it covers, and importantly, allows it to work on the existing Bitcoin blockchain. Simplicity, in contrast, is a radical departure from Bitcoin Script and is still in the early stages of its development.
Future Work and Conclusions
When designing Miniscript we set out to make Bitcoin Script more accessible. While a lot of work is focusing on investigating and proposing future changes to Script and Bitcoin’s consensus rules to add extra features, we felt that infrastructure was missing to even use the features that are already there in a generic, safe, composable, and interoperable way.
This work is not done yet. We have two functional implementations of Miniscript (C++ and Rust) and of the policy compiler, but to make this technology accessible we’ll need integration in commonly used pieces of software. With a Miniscript-compatible PSBT implementation (updater and finalizer), many PSBT signers (including hardware wallet-based ones) could become usable for complex scripts, even without explicit support. The compilers can also be improved, as there are many optimizations in the policy to script conversions that aren’t considered yet.
Along the way, we learned a number of things:
- Script resource limits complicate policy optimization: The multitude of consensus- and standardness-imposed resource limits (max opcodes, max script size, max stack size, …) make it much harder to find the optimal script for a given policy once it comes close to hitting these limits. This is an interesting insight, as it may guide suggested improvements to Script in the future. Relatedly, we were also surprised to learn that the Bitcoin consensus rules actually count the number of keys participating in an executed
OP_CHECKMULTISIG(VERIFY)towards the 201 non-push opcodes per script limit. - Variable witness sizes complicate fee estimation: Simple payments and multisig constructions have a witness size that is independent from the exact set of keys that is present. Once we move to more complicated scripts, the witness size becomes variable and may complicate fee estimation. Prospective signers for a particular transaction output may need to guess optimistically that a cheap path will be taken, and construct a corresponding transaction. If not all keys or hashes for that path end up being available, the transaction itself may need to be changed to account for the increased fees.
- Segwit’s stack encoding complicates optimization: Since Segwit the input stack is no longer encoded as a script, but as a list of stack elements directly. This had the unfortunate side effect of changing the encoding of “true” from 1 byte to 2 bytes. Due to this, Miniscript needs to care about what subexpressions go into what side of an IF/ELSE/ENDIF structure.
- Malleability: Since Segwit, transaction malleability is no longer a deal breaker for the correctness of protocols, but it may still have undesirable effects (such as uncertainty about the fee rate while propagating a transaction, slowing down compact block propagation, and interfering with the usage of hash locks are global publication mechanism). Because of these reasons, we designed Miniscript with non-malleability in mind, and learned how to reason about non-malleability of witnesses in general. To achieve that, Miniscript relies on certain Segwit-specific rules as non-malleability is very cumbersome to achieve in pre-Segwit transaction rules.
- Common subexpression elimination is hard: Despite various attempts, Miniscript does not support optimizing out repeated subexpressions. While this is possible in certain specific cases, it seems this is very hard to do in Script in general. The addition of certain stack manipulation opcodes could change this.
Start Building on Miniscript
Developers interested in working with Miniscript can start by exploring Miniscript constructs with our online compiler and analyzer. You might also want to check out some of our rust-miniscript usage examples.
Contributions are very welcome at the C++ miniscript and rust-miniscript GitHub repositories, and you can often catch our team at IRC ##miniscript on Freenode for miniscript-related discussion!
Note: This blog was originally posted at https://medium.com/p/3aeff3853620