Schnorr Signatures
Speakers: Andreas Antonopoulos
Date: October 7, 2018
Transcript By: Michael Folkson
Tags: Schnorr signatures
Category: Podcast
LTB Episode 378 - The Petro inside Venezuela & Schnorr Signatures
We’re currently using the elliptic curve digital signature algorithm (ECDSA) which is a specific way of doing digital signatures with elliptic curves but not the only way. Schnorr signatures have some unique characteristics that make them better in many ways than the ECDSA algorithm we use today in Bitcoin.
Schnorr signatures are better because they have certain quirks in the way the mathematics plays out. Digital signatures are numbers, they’re just numbers. The way you calculate these numbers is in such a way that someone else can verify that you calculated this number with knowledge of the private key without actually revealing this private key. They can verify that you have possession of the private key when you made the signature. A digital signature algorithm is just a mathematical function that gives you a number as a result of applying the private key to a message in such a way that someone else can verify that that number reveals you knew the private key without knowing the private key themselves. There are two aspects to it: signing and verifying.
Schnorr signatures exhibit certain characteristics that make them better. The first of these is the ability to do aggregation. What that means is that if you want to sign several different messages with several different private keys and produce several different signatures, with Schnorr what you can do is you can produce an aggregate signatures which is the equivalent of if you had signed the aggregate message with the aggregate of all the private keys. Think of it this way. It is as if the sum of all signatures is the same as if you applied one signature with the sum of all private keys on the sum of all messages. I’m using sum in a broader sense. It is not the traditional arithmetic operation of addition but it is the equivalent in elliptic curves.
In Bitcoin a transaction may have several inputs and each one of those inputs has its own signature. Let’s say you have a transaction that is spending little chunks of coins from four different addresses that your wallet controls, all of the loose change that you had and it is paying it somewhere. In a traditional Bitcoin transaction you’d have four inputs in your transaction to aggregate all of this loose change that you had. You will need to apply four signatures with four different public keys against the same transaction message in order to spend that transaction. With Schnorr signatures you can apply one aggregate signature to all four inputs which means that you use one quarter of the space in the transaction.
Now take that one step further and think about you have a block that has a thousand transactions in it signed by different people with different private keys on different transactions. What if you could aggregate all of the signatures on all of the transactions and only propagate that as part of your block verification? Someone can simply validate that the whole block signature is valid for all of the transactions that are in that block by summing up all the transactions and all of the public keys and counting once. If it is valid that’s done and they know that all of the signatures were valid. If it isn’t they’ll have to check each one independently but that’s a very rare case in Bitcoin. Most of the time what you could do is aggregate all the signatures in one transaction to one signature and then aggregate all the signatures across all of the transactions in a block into one signature for the whole block.
You’re transmitting 1/25 of the data in that particular case. It optimizes bandwidth, it optimizes disk storage, it optimizes blockchain capacity or block capacity. It optimizes verification speed. That’s only the start of it. Here’s another scenario. Let’s say you’re trying to do a multisig between 5 participants. Let’s say a 5-of-5 multisig. Today in order to do that with traditional multisig you’d have to apply 5 signatures which correspond to the 5 public keys that are known for the multisig and you’d have to verify all 5 signatures in order to confirm that multisig. WIth Schnorr signatures and a construct invented by I believe Andrew Poelstra, Greg Maxwell and Pieter Wuille called musig you can do a compound multisignature which basically means the 5 parties come together and they produce one signature that represents the aggregate of all of their 5 public keys. You validate that as a single signature on the multisig which is the unanimous vote if you like, the unanimous case of a multisig is a special case and you can do it with one signature that is constructed jointly by all 5 participants. So multisig now becomes a one signature operation. That’s step one. Now imagine if this from the public perspective was indistinguishable from a single payment where a single party signs with a single public key and a single signature which means that you can turn all multisig to look exactly the same as a straightforward one signature payment transaction on Bitcoin.
Now imagine that you can do that not just for the unanimous case of a 5-of-5 multisignature but you can do it for any type of monotonic boolean function meaning this key or these two and this one or these three plus a timelock of 30 minutes and these other two or this hashlock and these five keys. Any combination of OR, AND, OR, AND, OR, AND of any group of keys can be represented now by a single aggregate signature which shortcuts all of that. You can make all of those look like a simple payment. Your use of smart contracts effectively and complex payment solutions is invisible because it all looks as if a single payment was made with a single signature by a single public key.
It requires a soft fork and the test code has already been written up and submitted as a BIP.
First of all a lot of the research is very, very new. The musig construct which is a massive optimization of multisig for Schnorr was only invented about a year ago and written about. The implementation details were still being hashed out recently. Some of these new formulations, the hiding of multisig and making it look like a single payment which is called taproot and the equivalent property called graftroot. These are two new inventions, they’re barely a few months old since they were first discussed. Now it’s a matter of hashing out the details of creating an implementation that is both flexible enough, generic enough and efficient enough that it can encompass all of these privacy enhancements and verification enhancements. The next question was the stumbling block or major decision point was do these get launched as a series of changes that are discrete from each other and if so what they do is they create a challenge whereby people that try to use the enchanted privacy mechanisms are obvious, they’re visible. Or do you do all of them in one batch of changes so that you can immediately go to the model where your complex multisig looks like a single signature payment in which case the people using these enhanced privacy features are indistinguishable from those who are not which then makes the privacy even more powerful. The decision that seems to have come out of this is to deploy all of these features together so that privacy is not something that is distinguishable from those not using privacy. That’s a great idea in my opinion. Now taproot, graftroot and Schnorr musig are going to be deployed at the same time with a single soft fork.
I would expect that we’re probably no more than a year out from that moment. When the technology is deployed on the protocol level that doesn’t mean it’s available in a wallet that you can use with a nice user interface. That may take another year until it is broadly usable but the feature should be added to Bitcoin and create a significant increase in privacy, optimizations for scalability and better multisig probably in the next year.
You can aggregate an infinite number of signatures down to one. There is some relationship between this and the Mimblewimble approach to doing block compression that is rather interesting. The discussions are from a practical perspective. How much space do you save if you do this within a transaction? How much more space do you save if you do this within a block? Can you do this across blocks? One of the things that you have to realize is that you have to do this in a way that doesn’t break backwards compatibility for existing clients or that allows this to be an opt-in feature rather than a mandatory feature that everybody has to follow.
We’re currently in the fourth generation of multisig and the previous three generations are still very much in action. The first generation of multisig is what’s called naked multisig which is multisig without pay-to-script-hash. It’s multisig without a ‘3’ address but where you put the entire script in the UTXO. That’s very rare nowadays, you’ll probably not see it. Then you’ve got P2SH wrapped multisig which is what most of us use which is where the multisig address starts with a ‘3’. That’s the one we’re most familiar with. Most people haven’t noticed that there is now a new form of multisig which is multisig with a SegWIt address which is pay-to-witness-script-hash multisig which is a ‘bc1’ address with a new SegWit style address. That’s not even widely spread because SegWit is so new that people haven’t yet been doing SegWit multisig but it is beginning to appear now in a few wallets. Schnorr multisig would be the fourth iteration and you still have the previous three in operation. It is a rolling window.
I’m sure there’s pushback against this, there’s no such thing as a non-controversial upgrade to the Bitcoin protocol. Of course this is a non-mandatory, opt-in that is backward compatible so that you don’t have to validate or use this feature if you don’t want to but that doesn’t remove it from being controversial. In a world where vaccines are controversial I don’t think we’ll ever see a Bitcoin improvement that isn’t.