Schnorr Signatures
Speakers: Elichai Turkel
Date: August 16, 2019
Transcript By: Michael Folkson
Tags: Schnorr signatures
Media: https://www.youtube.com/watch?v=XKatSGCZ-gE
Slides: https://residency.chaincode.com/presentations/Schnorr_Signatures.pdf
https://twitter.com/kanzure/status/1165618718677917698
Introduction
I’m Elichai, I’m a resident here at Chaincode. Thanks to Chaincode for having us and having me. Most of you have probably heard about Taproot and Schnorr which are new technologies that we want to integrate into Bitcoin. Today I am going to explain what is Schnorr and why do we even want this?
Digital Signatures
Before that we need to define what are digital signatures. In 1976 Whitfield Diffie and Martin Hellman published a seminal paper called New Directions in Cryptography. They defined a protocol which is known today as Diffie-Hellman of course. They also defined a need for digital signatures. Basically they were saying that computers are common enough and there is enough digital communications that they need a replacement for written signatures in contracts, something digital. There they came to define what exactly is a digital signature and they said it must be easy for anyone to recognize the signature as authentic but impossible for anyone other than the legitimate signer to produce it. Digital signatures should be unforgeable but easy to verify. A year later there was another paper published called A Method for Obtaining Digital Signatures and Public Key Cryptosystems by Rivest, Shamir and Adleman which you probably know as RSA. That paper described an algorithm to encrypt, sign and decrypt arbitrary amounts of data. That was a bit of history. Now let’s see something more related to us.
History of Digital signatures
Please don’t be afraid of the algebra, most of this is very high school algebra. I will try to give a quick overview of the glossary first. In every slide we will have a message which is m. We have e which is the hash of the message. In reality it may be more stuff than just the hash of the message but for the sake of simplicity I try to ignore some attacks and the way to counter those attacks so that everything is simple and understandable. The private key is d and k is the random nonce. There is G which is a Generator Point. Think of some group and there’s scalars which are numbers, nothing fancy, just a math name for numbers. Then there are points. Points on a graph, they have x and y. The way to convert something to a point is by multiplying it by the Generator Point. You multiply some number, a scalar by the Generator and then you get a point. For example, your private key is actually a scalar, a number and your public key is a point, that scalar times the generator. As you can here that’s your public key, that simple. We can see in 1985 there was a paper that described Elgamal Signatures. I actually changed the formula because that was before elliptic curves were recognized as a way to use cryptography. That used modular cryptography but I changed it to look very similar. Then in 1997 ECDSA was standardized by NIST. Six years’ earlier Schnorr was published. As you can see it is earlier than ECDSA so what happened? Why didn’t we use Schnorr from the beginning? The major reason is because it was patented. Schnorr did a patent and we couldn’t use it before 2008 which was the year Satoshi published Bitcoin. There was no standard so no one really used it. The interesting thing to see is Elgamal and ECSDA look almost exactly the same. The only difference between them is first of all ECDSA describes a way to do it over elliptic curves and it is a plus instead of a minus. Just by looking at it, Schnorr is way simpler. There is no division because k is on the left side so if you want to solve for s you need to divide. With Schnorr there is no division, it is way simpler. This simplicity gives us two things. First you can see that in ECDSA there is a multiplication by G, we take the x of that point and multiply it by the private key which is weird. You mix up points and scalars and that is really weird. Because of that there is no security proof that proves that ECDSA is actually discrete log hard. If you have a public key d times G, to get the private key of that public key that is a very hard problem. Otherwise everyone could know your private key. There is no proof that ECDSA is actually that hard although we have no reason to assume it is not that hard. Still we have no proof and it is very nice to have a proof. Another thing that is weird is k is on the left side as I said before. If you solve for s you need to divide. All of this math is over some modulus, dividing over modulo is a big performance hit because you need to use some algorithm like Extended Euclidean or Fermat’s Little Theorem which requires a lot of multiplication. That’s not a nice thing. This is a performance hit and we don’t have a security proof. For Schnorr, first of all there is a proof that if someone can break Schnorr they can break the discrete log problem. We have a proof for that. Technically he could break an implementation but assuming the implementation is correct, breaking Schnorr is breaking the discrete log problem. Then the actual signature is the s from the equation and R which is the public point of k. k was our random nonce. e was our message and d is the private key. The signature is s and k times G. The signature is s and R. k times G is known as R. Now that we’ve seen this and we have a better understanding of what are Schnorr signatures we can do some very nice things with the fact that these are linear. Linear means that here there is a division, adding two ECDSA signatures is a bit weird because they are both dividing over different nonces so they don’t easily add up. Schnorr because there is no division there we can easily add two Schnorr signatures and this gives us some very nice things. So let’s see what we can do with it.
Multi Signatures
Don’t get scared, it is pretty easy. The first thing that we can do is multisignatures. Let’s say we have two public keys. Every public key is just the private key times the generator. We have two signatures, they are the same Schnorr signatures but this signature is for that public key and this signature is for that. If we simply add them up we’ll get something like that (k1 + k2) + e(d1 + d2). Again just high school algebra. We can call of this k’ and all of this d’ and we end up with s’ = k’ + ed’ which as you can see is exactly the same as the regular Schnorr signature. We ended up with a valid Schnorr signatures for this private key. This private key as you can see here is the addition of these two private keys. We ended up with P’ which is the addition of these two public keys. We can easily create a multisignature just by adding two public keys and two signatures. That’s it. In reality there is always problems and there are attacks against it and mitigations. Let’s not go over them. It is still pretty awesome.
Pay to Contract
Another very cool thing called pay to contract. Pay to contract again uses the linearity property and you can for example take your public key and add to it a hash of s. Let’s say s is a Bitcoin script. We’re adding to the public key the hash of a Bitcoin script. That way we can sign for P’ which is the new public key we got by just adding the same thing to the private key. If you just sign by d’ for a Bitcoin transaction for P’ then no one knows this has been there. It looks like a regular transaction. Right now the Bitcoin consensus doesn’t allow for it but we could create a way to let’s say I want to send someone some Bitcoin and if he doesn’t claim them in a year I want them back. That’s pretty fair, he doesn’t know nothing about Bitcoin. I want to give them but if he doesn’t want them I want them back, they’re worth money. I can put in s a script that is a locktime script meaning a regular Bitcoin script that says after a year I can take the money. I hide it inside the public key and I need to tell him that because when I tell him this he can easily change his private key to sign for the new public key. But if a year passed and he didn’t claim his money I can reveal the original public key in the script and now I can execute the script and take my money back. There’s no way this script was accidentally embedded in the public key because in the hash there is the original public key. The only way to create some pay to contract is intentionally. There is no way to accidentally have a script, at least a negligible probability. This is pretty cool. Right now you cannot do what I described in Bitcoin yet but Taproot proposes something very similar to that.
Sign to contract
As a reminder this is the Schnorr signature. Another cool thing we can do is something very similar to the pay to contract but for the nonce instead of the public key, meaning that we can take some commitment, we can hash it and add to the nonce. That will affect the public nonce R which is as you remember part of the signature. The signature is s and R. What does this give us? The first thing is timestamps. I can take a hash of my article pdf and put it in the commitment, hash it and add to the nonce. Now no one knows it is there. They see just the regular Bitcoin transaction. If I reveal the original R and the commitment I can prove that when I sent the transaction I had this hash. I can timestamp the article in there. You can even take OpenTimestamps and put a root of a lot of hashes. This is pretty cool. Another thing you can put here, you can use it for a sidechain. You have a sidechain, you can put in there some contract for that sidechain. I won’t give examples but you can imagine. You can put a contract in there, some script. Then I send money to that sidechain and the consensus for that sidechain can rely on the commitment to spend. Anyone that wants this money on the sidechain needs to reveal the commitment. Now this commitment can be a contract in that sidechain. It can be something complicated with a lot of rules that aren’t valid in Bitcoin but are valid there. The last thing that this can give us which I think is the most cool of them all is something called anti covert channel attack. Let’s say you have a hardware wallet. What happens if this hardware wallet gets compromised? The way you communicate with a hardware wallet is you give it a transaction, it gives you a signature. There is no other communication. How can that hardware wallet leak your private key if it has been compromised? What the hardware wallet can do is let’s say it puts in k=1, it puts in the nonce because the nonce is a random number. What happens if it puts 1 in k? You can easily see that because we know s, that is the signature, we know e which is the message. We can divide s by e and get the private key. If it puts a malicious nonce in k it reveals the private key. First of all this malicious nonce might be something secret that only the attacker knows. You wouldn’t be able to know and worse than that it might not even be malicious. If the hardware wallet doesn’t use deterministic nonces and it uses random nonces and this randomness is biased, even with a few bits biased and a bunch of signatures there are papers showing you can calculate the private key out. Randomness inside of hardware stuff is a known problem. It is not easy. It might be totally by accident. What can we do about it? If our hardware wallet supports sign to contract we can use that to add our own randomness into the wallet. That way if either the host or the hardware wallet is honest the signature will be fine. How do we do this?
Anti Nonce Covert Channel
We have a hardware wallet. The first thing it needs to do is commit to the R. The way it commits to it is it gives you the public R. That way it cannot change the k which is the nonce. Then we send it our sign to contract commitment. Now it creates the commitment and it gives us the signature. We can validate that the commitment is really inside the signature by using this. We have our R and we have our commitment so we can easily calculate R’ and verify that it validates the signature. That way we know the signature actually has the commitment in it. You can easily see that if k is 1, if you take 1 and add to it a hash of some random number you get a random number. Adding 1 to a random number still makes it random. That way even if the hardware wallet is compromised we’re adding our own randomness. Another nice thing about this is that this doesn’t compromise the wallet. Let’s say the host is the malicious party. It gives it 1 as c. A biased nonce 1. The hash of 1 plus a random number because the hardware wallet is non-malicious, gives you a random nonce. At the very least one of them needs to be honest and that way the signature is going to be valid and secure and won’t reveal anything. I think this was first thought up by Greg Maxwell. In reality there is a bit more complication to it but nothing too serious. This isn’t an implementation guide. I think that is awesome.
Adaptor Signatures
Now to the last thing we have, adaptor signatures. Adaptor signatures are a way to add something to the signature that makes the signature technically invalid but you can verify that inside of that invalid signature there exists a valid one. Regularly we’re giving s and kG which is R as the signature. Now we’re adding another thing called tG. If we get this signature we can easily verify. We have tG, we have dG which is our public key again and we have kG which is the public nonce. All we need is to multiply s’ by G and we can verify that this equation works. We can verify that this actually contains a valid signature but we need to know t. This signature is not valid with t in it. We need to somehow know t so we can remove it. How does this help us? For example we can use this to do atomic swaps.
Atomic Swap
How does it work? Let’s say Alice and Bob want to do an atomic swap. They create a multisignature as I showed at the start, just an addition between their public keys. They lock Bitcoin and Litecoin. They create a multisig and Bob sends his Bitcoin to that multisig and Alice sends her Litecoin to the multisig. They create a transaction that gives to the correct person the money but they don’t sign it. Now what Alice does is she computes two adaptor signatures; one for the Litecoin transaction and another for the Bitcoin transaction that she gives to Bob. When Bob gets it he validates that inside of that signature there is a valid signature but he needs to know t. Now he has that he can send Alice her valid Bitcoin signature. Alice gets the valid signature from Bob. She has access to her own because she knows t, she created it. She adds it to his one and she creates a s’_combined which is the regular multisignature. After she does that she sends it to the Bitcoin that’s valid, she gets her Bitcoin. What Bob can do is something interesting. He knows this s’_combined, he knows his signature and he knows the offset signature by Alice with t. He can remove his signature from the public valid one sent to Bitcoin. He removes his k2 and d2 because he knows them, he can easily subtract. There is remaining k1 + e * d1. If he removes that from this adaptor signature s1’ he is now left with t. These two t, they need to be the same, that’s important. If he takes this t and subtracts it from the adaptor signature. This is an adaptor signature. If you remove t from it you get a valid regular signature. Now he can take that and add to it his own signature and send to the Litecoin blockchain and get his Litecoin. That way we created an atomic swap. No one ever knows there has been an atomic swap because there are no HTLCs or fancy stuff. If we take that and combine it with the pay to contract we can add an locktime branch because what happens if one of them disappears? We can add a locktime branch and then if someone disappears they can reveal that s from the pay to contract and take their money. As long as everyone cooperates no one ever knows there has been an atomic swap here. It looks like regular pay-to-pubkey. There is nothing fancy on the blockchain, nothing, no scripts, no anything. That is also pretty cool.