Taproot Basics

Warning: This post has KaTeX enabled, so if you want to view the rendered math formulas, you’ll have to unfortunately enable JavaScript.

While attending the 2023 edition of TabConf, hosted in Atlanta, USA, from Sep 6th to Sep 9th, I also attended Base58’s intensive course on Taproot and Schnorr signatures. The course took place in the two days before the conference, on Sep 4th and Sep 5th.

Here is a very broad overview based on my notes, a bunch of readings and some of my own research. I am omitting a lot of details here. If you want to learn more, whenever you see a footnote, or a like to a Bitcoin Imporvement Proposal (BIP), go check it out.

Taproot Design Goals

Taproot was activated as a soft fork in November 2021.

The design goals of Taproot are:

• Increase privacy: hide the spending conditions and also hide the fact that you are using a multisig.
• Reduce the amount of data on-chain: you only need to commit to the root of the tree, and not the leaves.
• Use Schnorr: Schnorr signatures are more efficient and allow for signature aggregation.

Schnorr Signatures

Schnorr signatures are a type of digital signature scheme that provides security and efficiency advantages over traditional ECDSA (Elliptic Curve Digital Signature Algorithm) signatures. They were proposed by the mathematician and cryptographer Claus-Peter Schnorr. Schnorr signatures improve privacy, scalability, and security. Due to the commutativity property, Schnorr signatures can be aggregated, allowing multiple signatures to be combined into a single signature. This improves privacy by obscuring the number of participants in a multi-signature transaction. They are detailed in BIP 340. The nice thing about Schnorr signatures is that the sum of private keys is equal to the private key of the sum of public keys. This is what I call “commutativity property”, and allows for signature aggregation¹.

Here’s in a more formal way:

$$ P = p \cdot G $$

where $G$ is the generator point² and $p$ is the sum of $n$ private keys,

$$ p = \sum_{i=1}^{n} p_i $$

and $P$ is the sum of $n$ public keys³:

$$ P = \sum_{i=1}^{n} p_i \cdot G $$

Validation of Taproot Scripts

The validation of Taproot Scripts as detailed in BIP 342, that deals with OP_CHECKSIG and OP_CHECKSIGADD opcodes⁴. This does Schnorr signature aggregation during the Script execution.

A 2-of-3 multisig with Schnorr signatures spending Script with OP_CHECKSIG and OP_CHECKSIGADD would be:

pubkey1 OP_CHECKSIG pubkey2 OP_CHECKSIGADD pubkey3 OP_CHECKSIGADD OP_2 OP_EQUAL

This would reveal everyone’s public keys on-chain, and also the fact that it is a multisig, with all of the conditions. Additionally, it would be expensive to spend, due to the number of bytes required to commit to the Script on-chain.

There are more elegant ways to do this with Taproot Spending Rules and Merkle Trees, which we’ll see next.

Taproot Merkle Tree

Taproot is a series of spending conditions that are defined in a binary tree. Instead of a bunch of conditions that are visible using a Script, we have a binary tree with merkle roots.

            Root
             |
             |
         /       \
        /         \
       /           \
    Cond 1       Cond 2
                  /  \
                 /    \
             Cond 3   Cond 4

The root is a hash, and is implicity commited to on-chain. The conditions are not visible on-chain, because you just commit the hash of the root on-chain.

The way you build the root is by hashing all the intermediate states⁵, is by hashing all the leaves and branches below the root node. This is done using a $\operatorname{hash}(l \mid\mid r)$ function, where $l$ is the left node and $r$ is the right node⁶. The locking script will be:

script: <version-byte> <data>

where:

• <version-byte> is the version byte. This is the version number of our “segwit script”.
• <data> is P_x, the x-coordinate of the (tweaked) public key⁷.

Taproot Spending Rules

Taproot spending rules are detailed in BIP 341. The way Taproot works is that you have a locking script where all the spending conditions are hidden. This is just the hash of the root of the binary tree below. The way you construct the script is by using a merkle tree, and hashing all the intermediate states, i.e. all the leaves and branches below the root node. The hash is done by concatenating the string representation of the two things you want to hash and applying SHA256⁶:

hash = SHA256(left || right)

In the following example, you would hash Cond 3 with Cond 4, then hash the result with Cond 1. This is the root commitment, i.e. the root node, and the thing you publish on-chain.

       Root commitment
       (locking script)
             |
             |
         /       \
        /         \
       /           \
    Cond 1       Cond 2
    (leaf)      (branch)
                  /  \
                 /    \
             Cond 3   Cond 4
             (leaf)   (leaf)

We have 3 leaves here: Cond 1, Cond 3 and Cond 4, and 1 branch: Cond 2.

The way the spening rules work is that you have to provide a proof-of-inclusion, which depends on the leaf you want to spend. So if you want to spend Cond 3, you need to provide the hash of Cond 4 and Cond 1. Whereas, if you want to spend Cond 1, you just need to provide the hash of Cond 1 and the hash of the branch Cond 2. Hence, spending conditions that are higher in the tree are cheaper to spend, because you need to commit less data on-chain. That is why we structure the tree as most probable to be used on top.

MuSig2

MuSig2, detailed in BIP 327, is similar to OP_CHECKSIGADD. It allows for signature aggregation in the locking script, and also in the unlocking script. Hence, you can have any multisig with Schnorr signatures, without revealing anything related to the number of participants on-chain, multisig conditions, etc. However, you now need to put all the possible combinations of the pubkeys in the Script. Mind you that this is not a problem, because the resulting aggregate signature will not reveal the underlying individual signatures.

Here’s a MuSig2 example 2-of-3 threshold, you’ll need 3 spending conditions:

$$P_1 + P_2$$ $$P_1 + P_3$$ $$P_2 + P_3$$

where $P_n$ is the public key of the $n$-th participant.

Generally, for $n$ pubkeys with a threshold of $t$, you need a list of size $\binom{n}{t}$ for all possible combinations.

Continuing the example, for every two pairs of pubkeys, aggregate them using elliptic curve cryptography modular algebra, tweak them (if necessary)⁷, and create a script:

(P_1 + P_2) OP_CHECKSIG

Next, you consruct your Taproot tree listing all the possible spending conditions. (Remember to prioritize by the most plausible spending conditions on top). Calculate the root commitment by hashing all the intermediate states, which are the spending conditions on each leaf or branch, from bottom to top. Pick an internal key and if necessary, tweak⁷ it to derive an external key. Finally, lock up some bitcoin to the root commitment. That’s it! You have a Taproot tree with MuSig2 that is compact on-chain, and also private. Additionally, you can add more creative spending conditions using Script to the leaves of the tree.

To spend it, in your unlocking script, you’ll need to provide a proof-of-inclusion of the spending condition you want to spend, and the aggregated signature to unlock that spending condition.

License

This post is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.