Bitcoins are managed by computer programs that unlock funds in exchange for a valid witness. These Bitcoin scripts encode spending conditions that define what is and what is not a valid witness. Every transaction rests on this mechanism. Making sure that this works means making sure that transactions work. How do we ensure that these programs are correct, especially when they encode complex spending conditions? How can we keep track of the complexity? Tree-shaped programs like Miniscript are a solution to this problem.
As a collection of nodes connected via edges, trees are one of the most fundamental data structures. Each node is connected to zero or more children but only to one parent. The tree “grows” from a special root node that has no parent. As a result, we can take any node and look at its descendants: It is a smaller tree! A tree is recursively made up of many smaller trees. This means that if we can represent data as a tree, we can process it via recursive algorithms, which break it down bit by bit. This makes things like data analysis easier for us.
The Search for Trees in Bitcoin
Miniscript is a subset of Bitcoin Script. It imposes a tree structure on scripts, which identifies what each part of the script does. Some parts ask for a signature, others for a hash preimage; some enforce a timelock, and others combine parts to form a larger condition. By looking at the tree structure, the meaning of a script is made explicit. Each part fulfills a role which can be seen in the tree.
Here is an example of a Bitcoin script and the Miniscript tree structure that sits “on top”.
The added structure turns out to be really helpful: Properties of a script can be statically analyzed and inductively proven by moving along the tree. We can easily show that a script admits or rejects a given witness, that it incurs a given fee, or that it will reach resource limits during its execution. We can even combine two scripts into one that encodes the composition of their spending conditions. With this toolkit, we can encode complex spending conditions while being confident that the resulting script is correct.
Raw Bitcoin Script lacks the above conveniences and is thus trickier to use. The meaning of a script is implicitly defined by a C++ implementation. Scripts, in general, lack a clear structure and are difficult to reason about. On top of that, Bitcoin Script itself cannot express even fundamental operations like multiplication or concatenation. These obstacles make it hard to freely encode spending conditions as we might like.
Miniscript improves Bitcoin Script's core functionality by enforcing that scripts resemble a tree structure. With this requirement, we include small, well-behaved scripts that encode key, hash, or time locks while excluding exotic scripts that do other things. Because Miniscript is ultimately Bitcoin Script with a structure on top, you can use it now without a soft fork. Only wallets and other software that want to make use of this structure need to be updated to add support.
Pushing the Limit
How can we do more than Miniscript while preserving its useful properties? How can we make the system more powerful while preserving its structure? These thoughts lead us to Simplicity, an entirely new blockchain language designed from the ground up as an alternative to Bitcoin Script.
Simplicity programs are trees: The root node represents the overall program while each node does some part of the computation. Concretely, a parent node has access to the computations of its children and aggregates their results according to some function. This starts at the leaves, where constant values such as public keys or witness data are returned. The aggregation continues from bottom to top until the overall result is computed at the root.
Here is a sketch of a Simplicity program that matches the Bitcoin script from above. Notice how its structure equals the Miniscript tree structure. Real Simplicity programs are more detailed (and, or, key and older consist of smaller program fragments called combinators), but if we zoom out, then Simplicity and Miniscript look alike.
Simplicity is general enough to compute arbitrary Boolean functions. Each of these can be thought of as a spending condition, a function that accepts or rejects witnesses. Simplicity can do covenants, delegation, zero-knowledge proofs, and much more. This expressive power might seem daunting, but we can check for programmatic correctness. Simplicity has explicit semantics, so it is clear what a program does. There are no nasty surprises. The tree structure, again, makes it easy to statically analyze and prove properties. We can show that a given program is cheap to execute and that it correctly encodes a given spending condition. We have the same toolkit as for Miniscript, but for a much larger set of programs.
Unlike Miniscript, Simplicity would require a soft fork to be usable on Bitcoin. It would exist next to Bitcoin Script (Miniscript) in a new kind of Taproot leaf. The next step is to first implement Simplicity in Elements, the open-source platform Liquid is built on, to prove its potential for Bitcoin. This will also inform the final language design.
Bridging the Languages
We are building a bridge between Miniscript and Simplicity. The Miniscript tree structure is easy to replicate in Simplicity so that we can convert Bitcoin scripts to Simplicity programs and Miniscript becomes a subset of Simplicity. You can generate programs from existing scripts, check if a program and a script are semantically equivalent, and later refine your programs to go beyond what Miniscript can express. For those familiar with Miniscript, this will be a great introduction to the world of Simplicity. Our next post in this series will describe this bridge in greater detail.
A Tree-Shaped Future
Tree-shaped programs like Miniscript are easy to read and analyze. A range of tools works on these programs and helps us keep track of their correctness. Simplicity follows in these footsteps and enables arbitrary computation using a tree. It is much more powerful than Miniscript but still well-behaved, thanks to its structure. What is great about Miniscript carries over to Simplicity. The result is a language that enjoys the benefits of a tree while still enabling arbitrary computation.
The future is hopefully tree-shaped. We are working steadily to make Simplicity a reality. Converting Miniscript to Simplicity via a bridge is a great way to get started. Stay tuned for a follow-up on how to use the bridge yourself!
Subscribe below to have the latest announcements and most bleeding-edge research from Blockstream delivered to your inbox. For further updates, follow us @Blockstream and join the conversation in our Finance, Green, Jade, Liquid, and Satellite community Telegram channels.