# [[Taproot]], [[Schnorr Signatures]] and [[SIGHASH_ANYPREVOUT|SIGHASH_NOINPUT]], Oh My! Video: https://www.youtube.com/watch?v=YSUVRj8iznU&t=350s Transcript: https://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2018-07-09-taproot-schnorr-signatures-and-sighash-noinput-oh-my/ [[Pieter Wuille]] July 9th 2018 ## Introduction I am Pieter Wuille. I will just dive in. Today I want to talk about improvements to the [bitcoin scripting language](https://en.bitcoin.it/wiki/Script). There is feedback in the microphone. Okay. I will mostly be talking about improvements to the bitcoin scripting language. This is by no means an exhaustive list of all the things that are going on. It's more my personal focus in the things that I am interested in and excited about seeing happen. I will first start with some general ideas about how we should think about a scripting language, then go into two kinds of topics. In particular, signatures and structure of the bitcoin scripting system and changes to that. And then conclude with some remarks about how this can be brought into production which is a non-trivial thing. ## Script system goals Much of what's going on is that I want to convince you that there are many things going on and that we need to prioritize in how we work on these things because there are engineering tradeoffs. I'll get to that in the end. First of all, we should think about bitcoin scripting language as a way for specifying conditions for spending a transaction output. Bitcoin uses a UTXO model. It has significant advantages in terms of privacy. Really everything that our scripting language does is specifying under what conditions can you spend an output. We want to do that under various constraints. One of them is privacy. You don't really want to reveal to the world who you are or really what you were doing, which is contradictory because we want a scripting language where you don't say what you want to do. You also want to be space efficient because space on the blockchain is expensive and there's a price to it so everyone is incentivized to keep things as small as possible. And of course there's the computational efficiency- we want things that are efficient to verify so that it's easy to run full nodes to fully audit the system. All of these concerns are related, not perfectly, but generally, if you try to reveal less about what you're doing then you will be saying less and using less storage and as a result there will be less data to verify. All of these things generally go hand-in-hand. An important concern here is to not think about a scripting language as a programming language that describes execution. We're working in a strange model where any time a transaction is included in the blockchain, every node in the world forever will be validating that transaction, executing the same steps and coming to the same conclusion. **We don't want it to compute anything. I already know the outcome- I don't need 100,000 computers in the world to replicate this behavior. The only thing I am trying to do is convince them that the thing I'm doing is authorized.** It's really about not so much computing things, but more verifying that a computation was done correctly. This has many similarities with proof systems. **In the extreme, we can aim for a zero-knowledge proof system really where all you say is I have some condition and its hash was X and here is a proof that this condition was satisfied and nothing else.** Unfortunately there are computational and other difficulties right now. I think that should be our ultimate goal, for building things where we're looking at things that way. ## Signature system improvements Regarding improvements, I want to talk about three things. One is [Schnorr signatures](https://diyhpl.us/wiki/transcripts/blockchain-protocol-analysis-security-engineering/2018/schnorr-signatures-for-bitcoin-challenges-opportunities/). Some of you may have seen that I recently a couple days ago published a [draft BIP for incorporating Schnorr signatures into bitcoin](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html). I'll talk a bit about that. I will also be talking about [signature aggregation](https://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2017-09-06-signature-aggregation/) (or [here](https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregation/)), in particular aggregation across multiple inputs in a transaction. There's really two separate things, I believe. There's the signature system and then the integration and we should talk about them separately. Lots of the interest in the media on this topic are easily conflated between the two issues. Third, I also want to talk about SIGHASH_NOINPUT and signature hashing. There's a number of developments there as well. # Schnorr signatures [https://www.youtube.com/watch?v=YSUVRj8iznU&t=5m50s](https://www.youtube.com/watch?v=YSUVRj8iznU&t=5m50s) Schnorr signatures are the prototypical [digital signature system](https://en.wikipedia.org/wiki/Digital_signature) that has been around for a long time, building on the [discrete logarithm problem](https://en.wikipedia.org/wiki/Discrete_logarithm). This is the same security assumption as [ECDSA](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm) has. The two have an interesting history where [DSA](https://en.wikipedia.org/wiki/Digital_Signature_Algorithm), the predecessor to ECDSA was created as a way to avoid the patents that Schnorr had on his signature scheme. The Schnorr signature scheme is better in almost every way. There's no reason not to use it, apart from the fact that due to it being patented until 2008, standardization focused mostly on ECDSA and we should see if that can be improved. In particular, I'm not going into [the](http://diyhpl.us/wiki/transcripts/scalingbitcoin/milan/schnorr-signatures/) [real](http://diyhpl.us/wiki/transcripts/blockchain-protocol-analysis-security-engineering/2018/schnorr-signatures-for-bitcoin-challenges-opportunities/) [details](https://github.com/sipa/secp256k1/blob/968e2f415a5e764d159ee03e95815ea11460854e/src/modules/schnorr/schnorr.md) of the verification equation. I'm just putting them on the slide here to show that they are very similar in structure. It's just re-arranging the variables a little bit and putting a hash in there. The interesting thing is that Schnorr signatures have a security proof: we know that if the discrete log problem of our group is hard in the random oracle model, then there is a proof that the Schnorr signatures cannot be forged. There is no such proof for ECDSA. This is a nice-to-have. - Schnorr is sG = R + H(R,P,m)*P - ECDSA is sR = mG + rP As we are potentially introducing a new signature scheme anyway, we have the opportunity to make a number of changes really unrelated to the theoretical foundations of the signature scheme. We can get rid of the dumb DER encoding from ECDSA signatures. There's some six, seven bytes of overhead just stuff like "there's an integer that follows that are this long" and we really just want 64 bytes so let's just use 64 bytes. ## Batch verification Another thing that we can do is focusing on this too, we want [batch verifiability](https://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2017-09-06-signature-aggregation/), which means the ability to take a number of triplets of (public key, message, signature) and throwing them all at a verification algorithm and the algorithm can tell you all of them are valid or not all of them valid. You wouldn't learn where the faults are, but generally during block validation we don't care about that. We only care whether the block is valid or not. This seems like an almost perfect match for what we want to do. This batch verifiability is an interesting property that we want to maintain. ## Schnorr signature BIP draft A few days ago, I published a [Schnorr signature BIP draft](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html) which was the combined work of a number of people including Greg Maxwell. And many other people who are listed in the BIP draft. This BIP accomplishes all of those goals. It's really just a signature scheme, it doesn't talk about how we might go about integrating that into bitcoin. I'm going to talk about my ideas about that integration problem later. ## Schnorr signature properties One of the most interesting properties that Schnorr signatures have, and the reason why we looked into them in the first place, is the fact that they are linear. The linearity property is that you can take roughly speaking it's a bit more complex than this but generally you can take multiple Schnorr signatures by different keys on the same message and add them together in a certain way and the result is a valid signature for the sum of those keys. This is a remarkable property which is the basis for all the cool things we want to do on top of them. The most obvious one is that we can change how many of our multisignature policies work. In bitcoin, you have the ability to have k-of-n signatures. There's a built-in construction to do this. Especially when it's n-of-n, where you have a group of people and you require all of them to sign before an output can be spent, that reduces in the Schnorr signatures to a single signature. Roughly speaking, you just send money to the sum of their keys, and now all of them need to sign in order to be able to spend with this. It's a bit more complex than that, please don't do exactly that, there will be specifications for how to deal with this.