Taproot Is Coming To Bitcoin: How It Works, Its History And Implications

Taproot and Schnorr signatures are going live on Bitcoin at block 709,632. This is going to be a massive foundational achievement to continue building on into the future. It’s been four years since Segregated Witness went live on the network, our last major protocol upgrade. That’s as long as a halvening cycle!

Think about that. Four years from SegWit going live to Taproot going live. Slow, methodical patience, as it should be. But Taproot/Schnorr’s history goes back a lot further than that.

The History Of Taproot

Some who have been here a while might find this ironic, but the first mention of Schnorr signatures that I’m aware of was actually from former Bitcoin Core developer turned enterprise blockchain builder Mike Hearn. In 2012, he brought up the idea of a new cryptographic curve in relation to the batch verification of signatures to make node validation less computationally expensive. Ultimately, the scheme he was proposing was dependent on Schnorr signatures.

Adam Back was discussing naive schemes to do a multisig addresses that looked like a singlesig ones back in 2014, utilizing Schnorr signatures. Even Gavin Andresen included Schnorr instead of ECDSA on his wish list of changes that he would make to Bitcoin if he could wave a magic wand.

Since pretty near the very beginning of Bitcoin, most developers actively involved in Bitcoin Core have wanted Schnorr signatures, and there has always been a pretty solid consensus on their superiority to ECDSA signatures. It could in fact be argued that ECDSA was created specifically because the Schnorr signature scheme was patented, and there was a massive need for an open-source cryptographic signature scheme not encumbered by patents.

Schnorr is much more efficient and easily manipulatable (things can be added, subtracted, etc. from signatures, and if done correctly, can still leave users with valid signatures when they should have them) than ECDSA. Using ECDSA was a matter of necessity rather than desire in most cryptographic applications over the years.

Merkelized Abstract Syntax Trees (MAST), the Taproot half of this upcoming Taproot upgrade, has a similar long-standing history. I’m unable to find the citation, but I quite clearly remember seeing that phrase thrown around by the likes of Peter Todd on Bitcointalk.org back around 2013 or 2014.

The original BIP for MAST was proposed by Johnson Lau in 2016. This proposal also saw some activity around 2017 when Mark Friedenbach, BTCDrak and Kalle Alm broke it up into two separate BIPs (116 and 117) and expanded upon Lau’s original proposal.

MAST kind of sat around in limbo for the next year until Greg Maxwell came up with the initial Taproot idea and published it to the bitcoin-dev mailing list. His key insight was that in any contract case between multiple participants he could think of, there was an “optimal outcome” where the contract could be settled by everyone just signing the appropriate outcome instead of enforcing the outcome with more advanced scripts and transactions. This is the foundational assertion that Taproot is based on, i.e., tweaking the MAST tree to a regular top-level key that can be spent without revealing whether a Merkle tree of other spending conditions even exists.

The last little stretch of this history lesson starts with Pieter Wiulle announcing draft BIPs for Schnorr and Taproot in tandem to the mailing list on May 6, 2019. By January 2020, this was formally finalized into BIPs 340, 341 and 342. From this point on, it was just a lot of small detail refining at the implementation level, some review period, and then the long drawn out battle over activation mechanisms. That leads us to now, just shy of activation.

The Importance Of Schnorr Signatures

So, what’s the big deal with Schnorr signatures? Well, to start, they make transactions smaller. An ECDSA signature is usually about 72 bytes in size for a single signature in a transaction. Schnorr signatures clock in at a maximum of 64 bytes per signature. That’s a roughly 12% savings in size compared to ECDSA for every Schnorr signature. This is both a direct benefit to the person using Schnorr who will pay less in fees than an ECDSA user, but it’s also a direct benefit to people not using Schnorr by requiring slightly less data be stored in the blockchain to process and validate someone else’s Schnorr signatures.

Storing less data is always good, but what’s even better is increasing the efficiency of validating the data you have to store. One of the nice properties of Schnorr, the linearity of the math behind it, also allows for a nice property you want in Bitcoin data: batch validation. When your node receives a block from the network, it parses through each individual transaction and validates each signature one by one.

This is a huge part of why validating blocks consumes a lot of CPU power. Schnorr signatures can be all batched together and validated mathematically at once, kind of like smashing them together and doing one math operation instead of a bunch of individual ones. So, the more Schnorr signatures there are, the bigger the computational savings. This is a massive scaling win for the network.

Another massive improvement Schnorr brings is to multisignature scripts. Every multisig address has to explicitly reveal all of the individual public keys involved in a multisig script at spending time, and a signature has to be provided for every key involved in the spending process. With Schnorr’s mathematical properties, the door opens for MuSig, a multisignature standard. You can just add keys together and wind up with a single public key that everyone’s private key shares can sign for using new signature protocols. Jonas Nick of Blockstream benchmarked MuSig2 at taking two minutes for one million participants in a multisig address to sign. The scaling improvement to multisignature scripts cannot be understated.

This huge leap forward for multisignature scripts also has a huge implication for the privacy profile and cost of numerous applications built on top of Bitcoin. MuSig-based Lightning channels can now blend into the entire anonymity set of Schnorr/Taproot UTXOs on chain because no one will be able to distinguish the fact that they are a two-of-two multisig output anymore.

They’ll blend in and look just like a single signature script. The same thing goes for any multisig UTXO in general. This will have a lot of implications for people who use multisignature scripts to better protect their cold storage with a more robust security and recovery model than a single signature script.

Firstly, it won’t be obvious that they are using a multisig setup by watching the blockchain, so this will, like in the case of Lightning, make them blend in with everything else. A key win though is in regards to the economics: using multisignature right now requires providing a separate signature for every key involved in eventually spending a UTXO. With Schnorr/MuSig, things will be compressed into a single signature for the single combined public key, meaning spending multisig UTXOs using MuSig will become much cheaper as it’s pushing less data to the blockchain.

One last cool thing that Schnorr signatures do is drastically simplify the implementation of adapter signatures. Think of an adapter signature that is “encrypted” by a value that has been added or subtracted from a valid signature. It’s not valid until you reverse that mathematical operation, or “decrypt it” with the “key” the was used to manipulate it. This is possible with ECDSA, but because of the math being non-linear compared to Schnorr, it’s relatively complicated and there are a lot of security concerns to consider in implementing it.

Because of Schnorr’s linear properties though, an adapter signature is as simple as taking a single (say, the number 9,300,030) and subtracting a value from it (say 30). Once the party holding the adapter signature learns the subtracted value, they can simply add it back and voila, they have a valid signature again.

The Implications Of Taproot

As discussed a bit above, Taproot in reality is essentially just MAST, except instead of it working like P2SH (where you hash the script, or in MAST’s case, the Merkle root of the top of the script tree), you “tweak” a Schnorr public key by the root of the Merkle tree.

Tweaking works because of Schnorr’s linear properties — when you “tweak” a public key with a Merkle root (add that Merkle root to the public key), then you can simply add the Merkle root to the original private key and generate the spending key for the new tweaked public key. I.e., you add the same thing to both public and private key, and they are still a valid key pair. This hides the existence of a MAST tree, unless a branch of it is used, but fundamentally it’s still just a MAST tree, just one committed to in a more efficient and private way.

The ability to commit to different spending scripts in a Merkle tree and only reveal the used script is a massive scalability win in terms of smart contract complexity that is possible to build on Bitcoin.

Just like how the block size limits the number of transactions per block, there is a transaction size restriction limit of 100 kilobytes. The only difference is that instead of being a consensus rule, it’s a policy rule. That means a miner can mine a transaction bigger than 100 kilobytes, but by default, no one’s node on the network will relay a transaction bigger than that to the miner in the first place.

This inherently limits the size of the script used to lock up a Bitcoin UTXO. Even with P2SH, where the UTXO is locked to a hash of the script which isn’t revealed until you spend it, you still eventually have to reveal the full script at spend time. Taproot increases this scalability limit of script by not requiring you to reveal the entire script when you use it. Instead of the total size of all the ways you can spend the UTXO being restricted to the transaction size limit, you only have to make sure that any single way you can spend a Taproot UTXO respects this limitation.

There are also plenty of privacy benefits that come along with Taproot. One of the big benefits of a MAST tree is the ability to create all kinds of conditional situations where coins can be spent by other parties.

Imagine things like inheritance schemes where after a year or so your children can spend your coins, or in the event that you refuse to sign, your wife and a lawyer have a potential path to recover coins. Nothing about these spending conditions is revealed to the public unless they are actually used. This two-fold process provides plausible deniability for other parties involved in different spending branches you construct as to their involvement in that UTXO, as well as protects them from a thief or attacker pre-emptively targeting them knowing they have some degree of control over their target’s UTXOs.

On a technical level, Taproot has been relatively well engineered as well. Anyone reading who is familiar with Segregated Witness on any deep level should be familiar with the witness version.

When Segregated Witness was implemented, it created the new “witness” section of a transaction where signature data was moved to. Witness data had a version flag so that it could be upgraded to new functionality without having to use up undefined OP_CODEs on the base layer for new features.

This is actually how Taproot/Schnorr have been implemented. Segregated Witness transactions use witness version zero. When Taproot/Schnorr goes live soon, they will use the new witness version one to distinguish them from older Segregated Witness transactions. The same way that SegWit introduced witness versions, Taproot introduces “tapleaf version” for the tapscripts used in the MAST trees for UTXOs using Taproot. This not only allows the scripts buried in MAST to upgrade without using new OP_CODEs on the base layer, but also without having to upgrade witness versions either! So Taproot was designed to be as efficient as possible to upgrade in the future without limiting other unrelated upgrades to the protocol.

Taproot will bring many varying use cases. To start, all of the non-cooperative clauses in a Lightning channel such as penalty keys, or timelocks to allow them to be used, can be buried under a MAST with Taproot. No one will ever know they exist unless they need to be used, further obscuring which UTXOs are actually Lightning channels or not.

Inheritance schemes are another use case. Imagine a Taproot tree structured so that after six months of you not moving your money, your entire family can come together and spend the UTXO however they want. Then, six months later, everyone minus one person can spend it (so imagine if you had your wife, two kids, and parents as key holders, then imagine that after the extra six months, your wife, one kid, and parents can sign, or your two kids and parents can sign without your wife, and so on).

Then, six months after that, everyone minus two people can spend it. Eventually, it could boil down to just one person with the help of a lawyer (to make sure no shenanigans occurred) being able to spend the UTXO.

Or, what if you use multisig to secure your cold storage, but you only have one place that you consider secure and predictable long term? You could create a MAST where eventually, after a few years, the key at that secure location can spend those coins alone, just in case other keys were lost or destroyed, but without putting your coins immediately at risk of theft in the present if that one key were compromised.

This is an amazing and comprehensive upgrade to Bitcoin that has arguably been in the works since almost the birth of Bitcoin itself, not just the last few years in which the actual implementation details have been worked out and implemented.

It really is a win in so many ways for the scalability and utility of the Bitcoin protocol that it is hard to convey because of how subtle and “un-sexy” some of them are. But that doesn’t detract from the win. So, everyone get buckled in and ready to play with the new toys that we will have to use soon, because Taproot is coming!

This is a guest post by Shinobi. Opinions expressed are entirely their own and do not necessarily reflect those of BTC Inc or Bitcoin Magazine.

Source: https://bitcoinmagazine.com/technical/bitcoin-taproot-explainer