Taproot Proposal

TaprootProposal.md

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 a 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 unique descriptor to output script mapping at a minor cost of excluding certain tree structures with equivalent tapscript leaf depths. Since we believe the user is mostly focused on cost and not

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 descriptor/depth pairs ordered by leaf depth and lexicographically (tapscript descriptor string).

tap(descriptor₀(keys), depth₀, descriptor₁(keys), depth₁, ... , descriptor_i(keys), depth_i)

Description:

• There can only be one encapsulating tap() descriptor for a given taproot output.
• The subscriptors in the tap descriptor describes a tapscript and are each followed by a corresponding leaf depth.
• The Tapscript subscriptors can be any valid output descriptor.
• The Tapscript subscriptors 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).

Examples:

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

The third example respresents the following taptree:

                 Taproot *   
                        / \ 
                       *   *
                      / \ / \
                     *  | | |
                    / \ | | |
            pk(key) * | | | | 
                      | | | |
              pk(key) * | | |
                        | | |
       p2wpkh(pk0, pk1) * | |
                          | |
                  pk(key) * |
                            |
             p2wsh(pk(key)) *

We propose the following algorithm to derive the intended taptree from a given taproot descriptor.

... ELICHAI'S ALGO ...

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 permutations.

Non-interactive n-of-m multisig:

• multisig(2, PK0, PK1, PK2) expands to:
  • multisig(PK0+PK1) or <PK0> CHECKSIGADD <PK1> CHECKSIG 2 EQUAL
  • multisig(PK0+PK2) or <PK0> CHECKSIGADD <PK2> CHECKSIG 2 EQUAL
  • multisig(PK1+PK2) or <PK1> CHECKSIGADD <PK2> CHECKSIG 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.

Interactive musig n-of-m musig:

• musig(2, PK0, PK1, PK2) 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 descriptors and multisig subscriptors will always order the multisig subscriptors last, and in lexicographic string order if multiple n-of-m multisig or musig subscriptors are included.

Multi/Musig tapscript subscriptors will

Tap(..., Multisig₀(keys), Depth₀,..., Multisig_i(keys), Depth_i, Musig₀(keys), Depth₀,..., Musig_j(keys), Depth_j)