Highlights from Jimmy Song’s new technical workshop, Programming Taproot.
Last month I attended the first trip of Programming Taproot, a new workshop that Bitcoin developer Jimmy Song just launched. He held the one-day workshop at Bitcoin Commons in downtown Austin. It is a follow-up to his successful two-day Programming Blockchain workshop that he teaches around the world and which eventually became the basis for his excellent book Programming Bitcoin. I 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 of Taproot is that it enables much greater complexity and privacy in Bitcoin scripts. Transactions using Taproot look no different on-chain than the most basic Bitcoin transactions, where Alice sends money to Bob. Complex transactions were possible with the Bitcoin script pre-Taproot, but they reveal a lot of information about the transaction and bloat the chain. Taproot uses smart Merkle trees and new signatures to hide all this information from the blockchain, and instead works at the wallet and node level. This is a natural evolution of software, pushing back-end processing out of sight of the public layer.
Schnorr signatures
The first step of Taproot is the Schnorr signature. Currently, Bitcoin uses Elliptic Curve Digital Signature Algorithm (ECDSA) signatures, which requires expensive computing and 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’s what Schnorr uses. In fact, Schnorr was invented when Satoshi wrote Bitcoin, but it was under patent protection. Schnorr’s simplicity is attractive and serves the same function as the original Bitcoin ECDSA signature: it proves that a bitcoin owner knows her private key without revealing that private key. Full nodes perform that verification every time the owner sends bitcoin over the network, and these verifications (signature operations or SigOps) are now much faster under Schnorr signatures.
Taproot
Taproot allows scripts now called Tap scripts to be turned into a Merkle tree with Tap leaves and Tap branches. A Merkle tree is a data structure already used in Bitcoin, designed for lightweight clients to verify transactions without keeping the entire blockchain on disk. In my lesson I show exactly how a lightweight client can perform a proof of inclusion using this Merkle tree. In short, Merkle trees are useful data structures to easily prove that certain data is stored in the tree. Because Merkle trees are binary search trees, they can efficiently store large amounts of data: they can 2128 levels deep, allowing many different scripts in the tree. This enables complex scripts in much more sophisticated financial transactions, where the calculations take place off-chain.
MuSig
A multisig transaction in Bitcoin allows Bitcoin to be spent if multiple signatures unlock multiple public keys. Multisig is a great innovation that greatly improves usability and user experience because 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 of the keys.
The problem with multisig pre-Taproot is that it is clunky. It reveals all the spending terms for the chain, and it also bloats the chain because all those signatures and keys now have to be part of every transaction.
MuSig makes multisig possible, where everything 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 would then require signatures from all the people in order to send the money in a transaction. For example, large transfers of money from company to company may require the signatures of both the CEO and CFO, or transfers from a family estate may require the signatures of all members of the family. MuSig generates a group public key based on the individual public keys, then generates individual signatures based on the group public key, and finally a group signature based on the individual signatures. Ultimately, a single group signature can sign off on the group transaction to unlock the group’s public key. The most important innovation is that signing and verification are done within one Taproot transaction.
Why is this a big problem? Pre-Taproot required two types of authentication for multisig. 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 be done at the signature layer, and this is conceptually better. A multisig transaction is simply a more complex version of a single signature transaction and therefore should be treated conceptually the same way: at the signature layer. MuSig avoids the need to call complex scripts for a multisig transaction. And then there’s the privacy benefit, as these MuSig transactions look no different than peer-to-peer transactions between individuals on the Bitcoin network.
FROST
Flexible Round-Optimized Schnorr Threshold Signatures (FROST) was the last topic, a way to implement threshold signatures. This is the complete development of multisig on Taproot. The novelty here is that it uses Shamir’s secret exchange, a clever way to share a private key with a group using threshold technology. Shamir, the S in RSA, developed a clever approach to allow any group of people to discover a secret among the distributed shares, with the caveat that any smaller group would not be able to discover the private key (hence the threshold condition). There’s some elegant math in the background, using Lagrange interpolation to fit a polynomial to a set of discrete points. I liked this part of the workshop the most because it reminded me of how Bitcoin uses cool math to create new financial applications.
There is a very simple geometry that conveys the basic idea. Given any two points on a plane, you can find the line connecting the two points by solving for the slope and intersecting the point. 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’s secret sharing applies it to private key recovery. FROST implements this, to show that any fixed number of shared values of a private key can reveal that private key, but no less.
Final thoughts
The Taproot Upgrade is a few years old, but I never really understood it until now. It is a tour de force of applied mathematics. I’m optimistic that this will unleash new financial applications, more privacy and better wallets. For me, it has inspired a path to rethink bank-to-bank transactions using this new toolkit that I will explore this year.
Jimmy is an excellent educator. He has done the hard work of taking all the information in the Bitcoin Improvement Proposals (BIPs) and putting it into his slides for you. If you are considering this workshop, I definitely recommend you take his two-day Blockchain Programming workshop, spend over 100 hours reading and absorbing his book Programming Bitcoin, or take my upcoming online class on Bitcoin Fundamentals. Jimmy focused his classes on developers, and in between mini-lectures we spent half the time coding Taproot in Python. If you are comfortable with coding and open to learning all Bitcoin specific infrastructure, I recommend the course. If you still want to know what’s going on under the hood without coding yourself, stay tuned to this newsletter as I communicate these ideas to a broader, non-technical audience. I conclude with some technical footnotes.
Technical footnotes
- One of Taproot’s most important principles is to minimize the footprint in the chain. There is one example where I think it 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 ay coordinate. There is a clever way to represent a public key in compressed form using only the x coordinate and the sign of the y coordinate. This uses Fermat’s little theorem and the unique symmetry of the elliptic curve over the x-axis. Taproot went even further by using as a baseline that the y-coordinate is even. If the y-coordinate is ever odd, the developer can reverse the sign of the private key so that the resulting y-coordinate of the public key will turn out to be even. This requires constant testing of the sign of the y-coordinate on the back end, which becomes tedious. I feel like this costs more overhead for developers with minimal benefit, which is a saving of just one byte on the blockchain.
- The Taproot Merkle tree is now sorted. Pre-taproot, the Merkle trees used for light client authentication were unsorted and required a fairly verbose message sent between the full node and the light client, something called flag bits. All this is easier if the tree is sorted at the start. It makes proof of inclusion much easier. I wish the earlier Merkle trees were sorted too!
- The main distinction between MuSig and FROST is the generation of the individual keys. At MuSig, the people with the keys come to the MuSig coordinator, while at FROST the dealer hands out the keys. This need for a trusted FROST dealer is not trivial and is probably the only downside I see at this point. Over time there will be ways to deliver the keys in a distributed manner, but that is still being explored.
- Ordinal numbers and inscriptions are the main use of Taproot these days, but I expect/hope this will change as Bitcoin grows.
I answer Bitcoin questions in the paid version of this newsletter, so send them to korok@tamu.edu