Skip to content

Instantly share code, notes, and snippets.

Forked from jachiang/
Last active July 22, 2019 21:42
Show Gist options
  • Save elichai/6be93d8f6e288618a16b26c975c414e2 to your computer and use it in GitHub Desktop.
Save elichai/6be93d8f6e288618a16b26c975c414e2 to your computer and use it in GitHub Desktop.

Taproot Descriptor Proposal

Status: Proposal Co-Authors:

Output descriptor support in Bitcoin Core provide an intuitive language which simplifies how wallets determine which UTXOs they can sign and spend. A descriptor expression today expands to a single output script of a given output.

However, with the introduction of Taproot, a given output can now have multiple spending paths at different heights of the taproot tree. We wish to propose a taproot output descriptor which encapsulates both individual tapscripts and mid-level tapscript descriptors whilst encoding the intended taptree structure.

The proposed taproot descriptor design prioritizes:

  • Supporting current and foreseeable future descriptor language at the the tapscript subscriptor level.
  • Providing human-readable encoding of each tapscript depth in the taptree.
  • Enabling support for mid-level descriptor expressions which expand to multiple tapscripts (See multisig tapscript subscriptors below).
  • Maintaining a 1-to-1 mapping between taproot descriptor and output script.

The design achieves the goal of providing a unique descriptor for given output script at the minor cost of excluding certain tree structures with equivalent tapscript leaf depths. Since we believe the user is mostly interested on cost(tapscript depth) this appears to be a reasonable trade-off.

Taproot Descriptor Encoding.

The encoding of taproot output information required for solvability and spendability requires both tapscript and tree structure information to be contained in the descriptor.

The taproot descriptor encapsulates a sequence of tapscript depth/descriptor pairs ordered first by leaf depth and then lexicographically (tapscript descriptor string).

tap([depth0, descriptor0(keys)], [depth1, descriptor1(keys)], ... , [depthi, descriptori(keys)])


  • There can only be one encapsulating tap() descriptor for a given taproot output.
  • The taproot descriptor encapsulates a series of ordered [depth, tapscript descriptor] tuples.
  • The tapscript descriptors can be any valid output descriptor.
  • The depth/tapscript tuples must be first ordered by leaf depth, and then lexicographically by descriptor string, which includes the descriptor keys or arguments.
  • Tapscript depths are valid only if they are solvable into a valid binary tree structure (Described below).


  • tap([2, pk(key)], [1, pk(key)], [1, pk(key)])
  • tap([2, pk(key)], [2, pk(key)], [2, pk(key)], [2, raw(HEX)])
  • tap([3, pk(key)], [3, pk(key)], [2, p2wpkh(key)], [2, p2wsh(pk(key))], [2, pk(key)])

We illustrate the third example above as a taptree below.

                 Taproot *   
                        / \ 
                       *   *
                      / \ / \
                     *  | | |
                    / \ | | |
            pk(key) * | | | | 
                      | | | |
              pk(key) * | | |
                        | | |
            p2wpkh(key) * | |
                          | |
           p2wsh(pk(key)) * |
                    pk(key) *

Taproot Descriptor Decoding.

We introduce the following greedy algorithm to illustrate the decoding from taproot descriptor to taptree.

tap([depth0, descriptor0], [depth1, descriptor1], [depth2, descriptor2], [depth3, descriptor3])

The tuples must be lexicographically ordered from left to right, first by depth then script (if descriptors are identical the ordering of them doesn't matter). We insert the tuples into the tree from left to right.
The greedy algorithm individually inserts each tapscript leaf at the desired depth. It does so by conducting a left-biased traversal beginning at the root.
If it cannot find a insertion location during the downwards traversal, it will traverse back up the tree until an alternative downwards path can be taken. An insertion of a tapscript leaf begins with a left-biased downwards traversal.

Left-biased downwards traversal:

  • Traverse downwards through the binary tree on the left until the tapscript leaf can be inserted at the desired depth.
    • If a leaf is found whilst traversing down left, continue the left-biased downwards traversal from the right sibling.
      • If the right sibling is occupied by a leaf, begin the upwards traversal.
    • If you hit an empty leaf at the left insert there and return.
    • If a left leaf is preoccupied but the right is empty insert there.

Upwards traversal:

  • At every height during the upwards traversal:
    • If not already done, continue the left-biased downwards traversal with the right sibling.

This algorithm has been designed and implemented in Python by Elichai and can be found in the appendix.

Note: A given set of tapscript/depth pairs may be solveable into multiple different tree structures satisfying the same tapscript depth requirements. That is why we have proposed an ordering of tapscript descriptor/depth pairs by height and then by string (lexicographically) above.

Multisig Tapscript Subscriptors.

We propose to support expressions which deterministically expand to a specific sequence of tapscripts. For example, there are two obvious n-of-m multisig variants which necessarily expand to a series of n-of-n tapscript permutations.

Non-interactive n-of-m multi:

  • multi(2, PK0, PK1, PK2) expands to:
    • multi(PK0+PK1) or <PK0> CHECKSIG <PK1> CHECKSIGADD 2 EQUAL
    • multi(PK0+PK2) or <PK0> CHECKSIG <PK2> CHECKSIGADD 2 EQUAL
    • multi(PK1+PK2) or <PK1> CHECKSIG <PK2> CHECKSIGADD 2 EQUAL

As implied above, a multisig tapscript subscriptor without a n-index simply implies a n-of-n multisig output descriptor.

Also note that the ordering of the n-of-n multisig tapscripts resulting from the public key subset permutations is ordered by increasing public key index, following the sequencde of the public keys expressed in the multisig descriptor. This ordering is important, as it will facilitate the indication of the leaf heights of each n-of-n multisig tapscript.

Given the number and order of n-of-n multisig descriptors resulting from an expanded multisig descriptor expression is known, we can simply indicate the depths of the individual tapscripts as a sequence following the n-of-m multisig descriptor:

For example:

  • tap([multisig(2, PK0, PK1, PK2),2, 2, 1])

Note that the order of depths is in decreasing order but rather corresponds the the respective n-of-n multisig tapscript from the expanded n-of-m multisig descriptor.

Interactive musig n-of-m musig:

  • musig(2, PK0, PK1, PK2) in short(see Musig) expands to:
    • musig(PK0+PK1) or <PK0+PK1> CHECKSIG
    • musig(PK0+PK2) or <PK0+PK2> CHECKSIG
    • musig(PK1+PK2) or <PK1+PK2> CHECKSIG

The same ordering principles of the public keys from the multisig descriptor apply here.

Taproot descriptor with multisig:

A taproot descriptor with both regular and multi tapscript descriptors will always order the multisig tapscript descriptors last, and in lexicographic string order if multiple n-of-m multisig/musig tapscript descriptors are included.


  • tap([3, pk(key)], [2, pk(key)], [[2,3,2], multi(2, PK0, PK1, PK2)]

This corresponds to the following taptree.

                 Taproot *   
                        / \ 
                       *   *
                      / \ / \
                     *  | | |
                    / \ | | |
    multi(PK0, PK2) * | | | | 
                      | | | |
              pk(key) * | | |
                        | | |
        multi(PK0, PK1) * | |
                          | |
          multi(PK2, PK3) * |
                    pk(key) * 

The ordering of the tapscripts in this example may be a little harder to follow but following the same ordering principles as previously described. In general, all tapscripts leafs in the tree are ordered from left to right by depth and then lexicographically. This applies to both regular output descriptors and n-of-n multisig descriptors.

Appendix: Implementation of Taproot Decoding Algorithm

Input: A tap() descriptor string.

  • Parse the input into a list of tuples (depth, script).
  • Assert that the tuples are lexicographically ordered, first by depth then by script (if some are equal the ordering of them doesn't matter).
  • Loop through the ordered list and call tree.insert(script, depth).
  • The insertion algorithm(tree.insert(script, d)) basically inserts scripts from left to right while always trying to default to left whenever possible.
class Node:

    def __init__(self):
        self.left = None
        self.right = None = None
        self.parent = None

    def insert(self, data, depth):
        operating = self
        for i in range(depth):
            if operating.is_leaf():
                operating.insert_right(data, depth - i)
            operating = operating.get_left_child()

        if is None:
            if operating.is_left():
                operating.get_right_sibling().insert(data, 0)
            elif operating.is_right():
                operating.insert_right(data, 0)

    def insert_right(self, data, depth):
        operating = self
        while operating.is_right():
            depth += 1
            operating = operating.parent
        operating.get_right_sibling().insert(data, depth)

    def is_right(self):
        return self is self.parent.right

    def get_left_child(self):
        if self.left is None:
            self.left = Node()
            self.left.parent = self
        return self.left

    def get_left_sibling(self):
        assert not self.is_left()
        if self.parent.left is None:
            self.parent.left = Node()
            self.parent.left.parent = self.parent
        return self.parent.left

    def get_right_sibling(self):
        assert not self.is_right()
        if self.parent.right is None:
            self.parent.right = Node()
            self.parent.right.parent = self.parent
        return self.parent.right

    def is_left(self):
        return self is self.parent.left

    def is_root(self):
        return self.parent is None

    def is_leaf(self):
        return is not None

    def set(self, data):
        assert self.right is None and self.left is None = data

def main():
    root = Node()
    root.insert("Descriptor0", 2)
    root.insert("Descriptor1", 3)
    root.insert("Descriptor2", 3)
    root.insert("Descriptor3", 3)
    root.insert("Descriptor4", 3)
    root.insert("Descriptor5", 4)
    root.insert("Descriptor6", 4)
    root.insert("Descriptor7", 4)
    root.insert("Descriptor8", 4)

    print("2 is depth 2 and should be 2 nodes to the left: ",
    print("the last 4 is depth 4 and because it was last it should be 4 nodes to the right:",

if __name__ == "__main__":
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment