Programming Taproot

Highlights from Jimmy Song’s new technical workshop, Programming Taproot.

Last month I attended the maiden voyage of Programming Taproot, a new workshop that Bitcoin developer Jimmy Song just launched.  He held the one-day workshop in Bitcoin Commons in downtown Austin. It is a follow-up on his successful two-day Programming Blockchain workshop that he runs around the world, which eventually became the basis for his excellent book Programming Bitcoin. I'll discuss the highlights of the workshop and the main ideas.

[This post is more technical than others. Don't be scared. Even if you don't understand everything, save this post and come back to it as your Bitcoin education develops. I'm in the process of developing an online class that will allow an educated but non-technical audience to fully understand the content of a post like this.]

The big idea in Taproot is that it allows for much greater complexity and privacy in Bitcoin scripts. Transactions using Taproot will look on chain no different than the most basic Bitcoin transactions, where Alice sends money to Bob. Complex transactions were possible using Bitcoin script pre-Taproot, but they reveal lots of information about the transaction and bloat the chain. Taproot uses clever Merkle tree structures and new signatures to hide all this information from the blockchain, and instead operates at the wallet and node level. This is a natural evolution of software, pushing the back-end processing out of view of the public layer.

Schnorr signatures

The first step of Taproot is the Schnorr signature. Right now, Bitcoin uses elliptic curve digital signature algorithm (ECDSA) signatures, which requires an expensive computational operation, finite field division. Schnorr has a simpler signing and verification algorithm using hash functions. As you might guess, Satoshi's favorite hash function is SHA-256. And that is what Schnorr uses. In fact, Schnorr was invented when Satoshi wrote Bitcoin, but it was under patent protection. The simplicity of Schnorr is appealing, and it performs the same function as the original Bitcoin ECDSA signature: it proves that an owner of bitcoins knows her private key without revealing that private key. Full nodes perform that verification each time that owner sends bitcoin across the network, and these verifications (signature operations, or SigOps) are now much faster under Schnorr signatures.

Taproot

Taproot allows scripts now called Tap scripts, into a Merkle tree with Tap leaves and Tap branches. A Merkle tree is a data structure already used in Bitcoin, designed for light clients to verify transactions without holding the entire blockchain on disk. In my class, I show exactly how a light client can perform a proof of inclusion using this Merkle tree. In short, Merkle trees are useful data structures to easily prove that some data is stored in the tree. Because Merkle trees are binary search trees, they can hold vast amounts of data efficiently: it can run 2^128 levels deep, allowing for many different scripts in the tree. This allows for complex scripts in much more sophisticated financial transactions, with computation occurring off-chain.

MuSig

A multisig transaction in Bitcoin allows spending bitcoin if multiple signatures unlock multiple public keys. Multisig is a great innovation that vastly improves usability and user experience as it avoids the stress and headache of managing a single key, which can forever prevent access to bitcoin if that key is lost. Michael Flaxman has excellent interviews on Stephen Livera’s podcast about the benefits of multisig, and several Bitcoin companies like Unchained and Casa have built their business around third-party multisig custody, where a custodian holds some number of the keys.

The problem with multisig pre-Taproot is that it is clunky. It reveals all the spending conditions on chain, and it also bloats the chain as all those signatures and keys must now be a part of each transaction.

MuSig allows for multisig that all takes place in the background. Suppose a group of individuals generate their own public keys and want to receive a payment to the group, which will then require signatures from all the people in order to send the funds in a transaction. For example, large transfers of funds from company to company may require both the CEO and CFO to sign, or transfers from a family estate may require signatures of all members of the family. MuSig generates a group public key off of the individual public keys, then generates individual signatures off of the group public key, and then finally a group signature off of the individual signatures. In the end, a single group signature can sign for the group transaction to unlock the group public key. The chief innovation is that the signing and verification happens within a single Taproot transaction.

Why is this a big deal? Pre-Taproot, multisig required two kinds of verification. The first was the verification of individual signatures, which happened at the signature layer. The second was the verification of the spending conditions, which happened at the script layer. With Taproot, it can all happen at the signature layer, and this conceptually is better. A multisig transaction is simply a more complex version of a single signature transaction and therefore conceptually should be treated the same way: at the signature layer. MuSig avoids the need to invoke complex scripts for a multisig transaction. And then there's the privacy benefit, since these MuSig transactions look no different than a peer-to-peer transactions between individuals on the Bitcoin network.

FROST

Flexible Round-Optimized Schnorr Threshold Signatures (FROST) was the final topic, a way to implement threshold signatures. This is the full development of multisig on Taproot. The novelty here is that it uses Shamir’s secret sharing, a clever way to share a private key among a group using threshold technology. Shamir, who is the S in RSA, developed a clever approach to allow any group of people to recover a secret among shares that have been distributed, with the condition that any smaller group would be unable to recover the private key (hence the threshold condition).

There is some elegant math in the background, using Lagrange Interpolation to fit a polynomial to a set of discrete points. I loved this part of the workshop the most as it reminded me how Bitcoin uses cool math to arrive at new financial applications. There is a very simple geometry that conveys the basic idea. With any two points on a plane, you can find the line that connects the two points by solving for the slope and intercept. With any three points, you can find a quadratic equation. With any four points, you can find a cubic equation, and so on. Lagrange interpolation generalizes this intuition, and Shamir secret sharing applies it to recovering a private key. FROST implements this, to show any fixed number of shares of a private key can reveal that private key, but no fewer.

Final Thoughts

The Taproot Upgrade is a few years old, but I never truly understood it until now. It is a tour de force of applied math. I'm optimistic that this will unleash new financial applications, greater privacy, and better wallets. For me, it has inspired a path to rethink bank-to-bank transactions using this new toolkit which I will explore this year.

Jimmy is an excellent educator. He has done the hard work of processing all the information inside of the Bitcoin Improvement Proposals (BIPs) and digested them for you in his slides. If you are considering this workshop, I definitely recommend you take his Programming Blockchain two-day workshop, spend 100+ hours reading and absorbing his Programming Bitcoin book, or take my future online class on Bitcoin Fundamentals. Jimmy aimed his class at developers, and we spent half the time coding Taproot in Python in between each of the mini-lectures. If you are comfortable with coding and open to learning all the Bitcoin-specific infrastructure, I recommend the class. If you still want to know what's happening under the hood without coding yourself, stay in touch with this newsletter as I communicate these ideas to a broader, non-technical audience. I'll conclude with a few technical footnotes.

Technical Footnotes

1. One of the chief principles of Taproot is to minimize the on-chain footprint. There's one example that I think went too far, namely the x-only public keys. Public keys in Bitcoin are points of an elliptic curve, so they have an x and a y coordinate. There is a clever way to represent a public key in compressed form with only the x-coordinate and the sign of the y-coordinate. This utilizes Fermat's little theorem and the unique symmetry of the elliptic curve over the x-axis. Taproot pushed it further by using as a baseline that the y-coordinate is even. If ever the y-coordinate is odd, the developer can flip the sign of the private key so that the resulting y-coordinate of the public key will turn out to be even. This requires constantly testing the sign of the y-coordinate on the back end, which ends up being annoying. I feel like this costs greater developer overhead with minimal benefit, namely, saving just one byte on the blockchain.

2. The Taproot Merkle tree is now sorted. Pre-taproot, the Merkle trees used for light client verification were not sorted, and required a fairly elaborate message sent between the full node and the light client, something called flag bits. All of this is simpler if the tree is sorted on inception. It makes the proof of inclusion much easier. I wish the earlier Merkle trees also would have been sorted!

3. The chief distinction between MuSig and FROST is the generation of the individual keys. With MuSig, the individuals arrive at the MuSig coordinator with the keys, whereas in FROST the dealer distributes the keys. This need for a trusted dealer in FROST is non-trivial and is probably the only drawback that I see at this point. Over time there will be ways to deliver the keys in a distributed way, but that is still under research.

4. Ordinals and inscriptions are the chief use of Taproot today, but I expect/hope this to change as Bitcoin grows.

I answer Bitcoin questions on the paid version of this newsletter, so submit them to korok@tamu.edu