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

Question

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 on May 18th 2022.)

Answer 1

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 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 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 for 2-of-3 threshold signature.

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