<blockquote>
<p>How would one turn a Miniscript &quot;tree&quot; into a Taproot tree with Taproot'd Miniscript?</p>
</blockquote>
<p>You wouldn't - they're incomparable things that don't get translated from one to another.</p>
<p>Miniscript is a way to represent a Bitcoin Script, to help reason about it.
Taproot trees are commitment structures that help construct taproot outputs which can be spent by satisfying one of possibly multiple scripts.</p>
<p>Both the taproot script configuration and miniscript expressions can be thought of as trees, but these exist independently, at different levels. At best you can say that a taproot output is a tree whose leaves are scripts, and these scripts may on their turn be representable as miniscript expression trees - but those are trees of a very different nature.</p>
<p>Perhaps a more useful question is:</p>
<blockquote>
<p>How can spending policies be translated to a tree of scripts, now that taproot permits outputs to be spendable using a disjunction of multiple scripts rather than a single script?</p>
</blockquote>
<p>The simplest case is something like a policy &quot;sign with key K1 OR sign with key K2&quot;. It could be implemented as:</p>
<ul>
<li>A single script <code>&lt;K1&gt; OP_CHECKSIG OP_SWAP &lt;K2&gt; OP_CHECKSIG OP_BOOLOR</code> (miniscript <code>or_b(pk(K1),s:pk(K2))</code>).</li>
<li>A disjunction of two scripts:
<ul>
<li><code>&lt;K1&gt; OP_CHECKSIG</code> (<code>pk(K1)</code>)</li>
<li><code>&lt;K2&gt; OP_CHECKSIG</code> (<code>pk(K2)</code>)</li>
</ul>
</li>
</ul>
<p>It gets more complicated when we're talking about more involved policies:</p>
<ul>
<li>&quot;K1 must sign and either K2 or K3 must sign&quot; can be implemented using:
<ul>
<li>A single script <code>&lt;K1&gt; OP_CHECKSIGVERIFY &lt;K2&gt; OP_CHECKSIG OP_SWAP &lt;K3&gt; OP_CHECKSIG OP_BOOLOR</code> (<code>and_v(v:pk(K1),or_b(pk(K2),s:pk(K3)))</code>).</li>
<li>A disjunction of two scripts:
<ul>
<li><code>&lt;K1&gt; OP_CHECKSIGVERIFY &lt;K2&gt; OP_CHECKSIG</code> (<code>and_v(v:pk(K1),pk(K2))</code>)</li>
<li><code>&lt;K1&gt; OP_CHECKSIGVERIFY &lt;K3&gt; OP_CHECKSIG</code> (<code>and_v(v:pk(K1),pk(K3))</code>)</li>
</ul>
</li>
</ul>
</li>
<li>&quot;Two out of these three conditions must be fulfilled: (1) K1 must sign (2) K2 must sign (3) both K3 and K4 must sign&quot; can be implemented using:
<ul>
<li>A single script <code>&lt;K3&gt; OP_CHECKSIG OP_SWAP &lt;K4&gt; OP_CHECKSIG OP_BOOLAND OP_SWAP &lt;K1&gt; OP_CHECKSIG OP_ADD OP_SWAP &lt;K2&gt; OP_CHECKSIG OP_ADD 2 OP_EQUAL</code> (<code>thresh(2,and_b(pk(K3),s:pk(K4)),s:pk(K1),s:pk(K2))</code>)</li>
<li>A disjunction of 3 scripts:
<ul>
<li><code>&lt;K1&gt; OP_CHECKSIGVERIFY &lt;K2&gt; OP_CHECKSIG</code> (<code>and_v(v:pk(K1),pk(K2))</code>)</li>
<li><code>&lt;K1&gt; OP_CHECKSIGVERIFY &lt;K3&gt; OP_CHECKSIGVERIFY &lt;K4&gt; OP_CHECKSIG</code> (<code>and_v(v:pk(K1),and_v(v:pk(K3),pk(K4)))</code>)</li>
<li><code>&lt;K2&gt; OP_CHECKSIGVERIFY &lt;K3&gt; OP_CHECKSIGVERIFY &lt;K4&gt; OP_CHECKSIG</code> (<code>and_v(v:pk(K2),and_v(v:pk(K3),pk(K4)))</code>)</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>Which of these options is optimal may depend on the situation:</p>
<ul>
<li>Using more script leaves is generally more private, as the unused leaves (and the spending conditions they correspond with) aren't revealed to the blockchain at spending time.</li>
<li>Using more script leaves may or may not be cheaper to spend. In simple disjunction cases (where the policy is &quot;A or B or C or ...&quot;) splitting in separate scripts is generally cheaper. When there is a huge combinatorial explosion that a policy needs to be turned into to make use of separate script, a single script may be cheaper to spend.</li>
<li>Coordination in case multiple signing parties need to cooperate may be easier in case of a single script, because they need to decide ahead of time which script they'll be signing for (due to BIP341 sighash rules committing to the actual script used).</li>
</ul>

CC BY-SA 4.0
2022-05-18T15:29:33.563Z
2022-05-18T15:29:33.563Z
Pieter Wuille
<p>A Taproot tree is a Merkle (binary) tree of (Tap)scripts. Every node (an intermediate state in the process of hashing the leaves up to the root) has at most 2 child nodes and every leaf script (at the bottom of the tree) is hashed before being hashed again with the concatenation of its hash and its sibling's hash.</p>
<p>A Miniscript tree doesn't do any hashing as it is just restructuring a single (possibly very large) script into fragments. The <strong>root</strong> of the Miniscript tree is the whole expression. Every subexpression is a <strong>node</strong> in the tree. The <strong>leaves</strong> are the expressions which don't have subexpressions, like <code>pk()</code> or <code>older()</code>. A node on the tree can have more than 2 children. For example, a node of the Miniscript tree could contain a <code>thresh()</code> which contains more than 2 subexpressions (e.g. a 2-of-3 threshold would contain three subexpressions). A node could also only have 1 child (e.g. if it contains one of the Miniscript wrappers <code>a:</code>, <code>d:</code> or <code>l:</code>).</p>
<p>The Taproot tree would be constructed at the <a href="https://bitcoin.stackexchange.com/questions/91565/what-does-bitcoin-policy-language-offer-the-developer-that-miniscript-doesnt-w">Policy</a> level rather than the Miniscript level as each (Tap)script on the leaves of the Taproot tree may be represented as an individual Miniscript (Miniscript only encodes a subset of Script in its entirety). But if we think about how a Taproot tree of policies might be constructed, if the &quot;root&quot; (highest level) of the Policy tree contained a <code>or(A,B,C)</code> this is easily deconstructed into a Taproot tree with leaves A, B and C. If the Policy root contained an <code>and</code> the whole Policy may need to go into a single leaf but there are possible exceptions (if there are disjunctions below it e.g. <code>and(or(A,B),C)</code> is equivalent to <code>or(and(A,C),and(B,C))</code>. If the Policy root contained a <code>thresh</code> (e.g. 2-of-3) it could be reconstructed as an <code>or()</code> of 3 2-of-2s as explained in this <a href="https://murchandamus.medium.com/2-of-3-multisig-inputs-using-pay-to-taproot-d5faf2312ba3" rel="nofollow noreferrer">blog post</a> for 2-of-3 threshold signature.</p>
<p>Thanks to individual(s) for answering my questions on IRC. Any mistakes are my own.</p>

CC BY-SA 4.0
2022-05-18T14:17:36.940Z
2022-05-18T14:23:09.013Z
2022-05-18T14:23:09.013Z
Michael Folkson
<p>How would one turn a Miniscript &quot;tree&quot; into a Taproot tree with Taproot'd Miniscript?</p>
<p>(To be clear unlike a Taproot tree a Miniscript tree likely would't be surfaced to the user. Breaking down a Miniscript into a tree like structure is done in the code and was discussed in the <a href="https://bitcoincore.reviews/24148" rel="nofollow noreferrer">Bitcoin Core PR review club</a> on May 18th 2022.)</p>

CC BY-SA 4.0
2022-05-18T14:24:33.087Z
Uh. Do Miniscript trees and Taproot trees have anything to do with each other except that they're both [trees](https://en.wikipedia.org/wiki/Tree_(data_structure))? Why would we want to compare them?
Murch
CC BY-SA 4.0
2022-05-18T14:35:49.823Z
Data structure question. We often think in terms of Merkle trees in Bitcoin, had to remind myself of the definitions for (non Merkle) trees, DAGs etc.
Michael Folkson
CC BY-SA 4.0
2022-05-18T14:41:53.427Z
Trees are *everywhere* in programming. Every set in C++ is represented as a tree. The directory structure of your filesystem is a tree. The blockchain with its branches is a tree. The transactions in Bitcoin blocks are hashed following a tree. The mempool in Bitcoin Core is stored as a tree. The hierarchy of elements on this website's DOM is a tree. This question I think adds more confusion than clarification; yes, both the scripts in taproot are a tree, and miniscript expressions are organized in a tree. There is nothing remarkable or interesting about those facts.
Pieter Wuille
CC BY-SA 4.0
2022-05-18T14:49:14.787Z
Fair enough. Edited the question. Hopefully you're both happy with edit.
Michael Folkson
<script><bitcoin-core-development><terminology><taproot><miniscript>
How would one turn a Miniscript tree into a Taproot tree with Taproot'd Miniscript?
Michael Folkson
# How would one turn a Miniscript tree into a Taproot tree with Taproot'd Miniscript?

(Asked by: username_0 on 2022-05-18)

How would one turn a Miniscript "tree" into a Taproot tree with Taproot'd Miniscript?

(To be clear unlike a Taproot tree a Miniscript tree likely would't be surfaced to the user. Breaking down a Miniscript into a tree like structure is done in the code and was discussed in the [Bitcoin Core PR review club](https://bitcoincore.reviews/24148) on May 18th 2022.)

**Tags:** script, bitcoin-core-development, terminology, taproot, miniscript

> **Comments:**
> **username_1**: Uh. Do Miniscript trees and Taproot trees have anything to do with each other except that they're both [trees](https://en.wikipedia.org/wiki/Tree_(data_structure))? Why would we want to compare them?  
> **username_0**: Data structure question. We often think in terms of Merkle trees in Bitcoin, had to remind myself of the definitions for (non Merkle) trees, DAGs etc.  
> **username_2**: Trees are *everywhere* in programming. Every set in C++ is represented as a tree. The directory structure of your filesystem is a tree. The blockchain with its branches is a tree. The transactions in Bitcoin blocks are hashed following a tree. The mempool in Bitcoin Core is stored as a tree. The hierarchy of elements on this website's DOM is a tree. This question I think adds more confusion than clarification; yes, both the scripts in taproot are a tree, and miniscript expressions are organized in a tree. There is nothing remarkable or interesting about those facts.  
> **username_0**: Fair enough. Edited the question. Hopefully you're both happy with edit.  

---

## 2 answers

### Answer by username_2 on 2022-05-18. Score: 2 | Accepted answer

> How would one turn a Miniscript "tree" into a Taproot tree with Taproot'd Miniscript?

You wouldn't - they're incomparable things that don't get translated from one to another.

Miniscript is a way to represent a Bitcoin Script, to help reason about it.
Taproot trees are commitment structures that help construct taproot outputs which can be spent by satisfying one of possibly multiple scripts.

Both the taproot script configuration and miniscript expressions can be thought of as trees, but these exist independently, at different levels. At best you can say that a taproot output is a tree whose leaves are scripts, and these scripts may on their turn be representable as miniscript expression trees - but those are trees of a very different nature.

Perhaps a more useful question is:

> How can spending policies be translated to a tree of scripts, now that taproot permits outputs to be spendable using a disjunction of multiple scripts rather than a single script?

The simplest case is something like a policy "sign with key K1 OR sign with key K2". It could be implemented as:

* A single script `<K1> OP_CHECKSIG OP_SWAP <K2> OP_CHECKSIG OP_BOOLOR` (miniscript `or_b(pk(K1),s:pk(K2))`).
* A disjunction of two scripts:
  + `<K1> OP_CHECKSIG` (`pk(K1)`)
  + `<K2> OP_CHECKSIG` (`pk(K2)`)

It gets more complicated when we're talking about more involved policies:

* "K1 must sign and either K2 or K3 must sign" can be implemented using:
  + A single script `<K1> OP_CHECKSIGVERIFY <K2> OP_CHECKSIG OP_SWAP <K3> OP_CHECKSIG OP_BOOLOR` (`and_v(v:pk(K1),or_b(pk(K2),s:pk(K3)))`).
  + A disjunction of two scripts:
    - `<K1> OP_CHECKSIGVERIFY <K2> OP_CHECKSIG` (`and_v(v:pk(K1),pk(K2))`)
    - `<K1> OP_CHECKSIGVERIFY <K3> OP_CHECKSIG` (`and_v(v:pk(K1),pk(K3))`)
* "Two out of these three conditions must be fulfilled: (1) K1 must sign (2) K2 must sign (3) both K3 and K4 must sign" can be implemented using:
  + A single script `<K3> OP_CHECKSIG OP_SWAP <K4> OP_CHECKSIG OP_BOOLAND OP_SWAP <K1> OP_CHECKSIG OP_ADD OP_SWAP <K2> OP_CHECKSIG OP_ADD 2 OP_EQUAL` (`thresh(2,and_b(pk(K3),s:pk(K4)),s:pk(K1),s:pk(K2))`)
  + A disjunction of 3 scripts:
    - `<K1> OP_CHECKSIGVERIFY <K2> OP_CHECKSIG` (`and_v(v:pk(K1),pk(K2))`)
    - `<K1> OP_CHECKSIGVERIFY <K3> OP_CHECKSIGVERIFY <K4> OP_CHECKSIG` (`and_v(v:pk(K1),and_v(v:pk(K3),pk(K4)))`)
    - `<K2> OP_CHECKSIGVERIFY <K3> OP_CHECKSIGVERIFY <K4> OP_CHECKSIG` (`and_v(v:pk(K2),and_v(v:pk(K3),pk(K4)))`)

Which of these options is optimal may depend on the situation:

* Using more script leaves is generally more private, as the unused leaves (and the spending conditions they correspond with) aren't revealed to the blockchain at spending time.
* Using more script leaves may or may not be cheaper to spend. In simple disjunction cases (where the policy is "A or B or C or ...") splitting in separate scripts is generally cheaper. When there is a huge combinatorial explosion that a policy needs to be turned into to make use of separate script, a single script may be cheaper to spend.
* Coordination in case multiple signing parties need to cooperate may be easier in case of a single script, because they need to decide ahead of time which script they'll be signing for (due to BIP341 sighash rules committing to the actual script used).


---

### Answer by username_0 on 2022-05-18. Score: 2

A Taproot tree is a Merkle (binary) tree of (Tap)scripts. Every node (an intermediate state in the process of hashing the leaves up to the root) has at most 2 child nodes and every leaf script (at the bottom of the tree) is hashed before being hashed again with the concatenation of its hash and its sibling's hash.

A Miniscript tree doesn't do any hashing as it is just restructuring a single (possibly very large) script into fragments. The **root** of the Miniscript tree is the whole expression. Every subexpression is a **node** in the tree. The **leaves** are the expressions which don't have subexpressions, like `pk()` or `older()`. A node on the tree can have more than 2 children. For example, a node of the Miniscript tree could contain a `thresh()` which contains more than 2 subexpressions (e.g. a 2-of-3 threshold would contain three subexpressions). A node could also only have 1 child (e.g. if it contains one of the Miniscript wrappers `a:`, `d:` or `l:`).

The Taproot tree would be constructed at the [Policy](https://bitcoin.stackexchange.com/questions/91565/what-does-bitcoin-policy-language-offer-the-developer-that-miniscript-doesnt-w) level rather than the Miniscript level as each (Tap)script on the leaves of the Taproot tree may be represented as an individual Miniscript (Miniscript only encodes a subset of Script in its entirety). But if we think about how a Taproot tree of policies might be constructed, if the "root" (highest level) of the Policy tree contained a `or(A,B,C)` this is easily deconstructed into a Taproot tree with leaves A, B and C. If the Policy root contained an `and` the whole Policy may need to go into a single leaf but there are possible exceptions (if there are disjunctions below it e.g. `and(or(A,B),C)` is equivalent to `or(and(A,C),and(B,C))`. If the Policy root contained a `thresh` (e.g. 2-of-3) it could be reconstructed as an `or()` of 3 2-of-2s as explained in this [blog post](https://murchandamus.medium.com/2-of-3-multisig-inputs-using-pay-to-taproot-d5faf2312ba3) for 2-of-3 threshold signature.

Thanks to individual(s) for answering my questions on IRC. Any mistakes are my own.


---

