Threshold Signatures and Accountability
Speakers: Andrew Poelstra
Date: February 4, 2019
Transcript By: Bryan Bishop
Tags: Schnorr signatures, Threshold signature
Category: Meetup
Media: https://www.youtube.com/watch?v=j9Wvz7zI_Ac
Slides: https://download.wpsoftware.net/bitcoin/wizardry/2019-02-sfdevs-threshold/slides.pdf
Transcript completed by: Bryan Bishop Edited by: Michael Folkson
Twitter announcement: https://twitter.com/kanzure/status/1092665108960968704
Introduction (Mark Erhardt)
Sorry for the delays. We’re finally ready to talk. Welcome to our talk. We’d like to thank our sponsors including Blockstream and Digital Garage. Today we have Andrew Poelstra to talk about threshold signatures and accountability. He is known for working on Mimblewimble, Bitcoin Core, libsecp256k1, and at Blockstream.
Introduction (Andrew Poelstra)
Today I am here to talk about threshold signatures and accountable signatures and a whole bunch of signature work I’ve been doing with Pieter Wuille, Jonas Nick and Tim Ruffing and a few other people over the last year or so. I am going to start by going over what a Schnorr signature is. That has been the buzzword for all of 2018 and probably all of 2019 as well. Then I will talk about how Schnorr signatures generalize to multisignatures, to threshold signatures and then some cool tricks around threshold signatures. I am going to do it in a very algebraic fashion. Almost all of my slides look something like this. They are going to get increasingly complicated but I am going to pay a decreasing amount of attention to what is actually written there.
Schnorr signatures
This slide I am going to explain every line in some detail. As we get going I am going to start pointing vaguely and say “This means that. Don’t worry about it.” You won’t have to worry about it. Nobody needs to worry about this stuff. The point is the shapes and the colors which I hope will communicate how much fun it is to work on this kind of stuff. This is a Schnorr signature.
P = xG
R = kG
e = H(P,R,m)
s = k + ex
A Schnorr signature consists of these two values s and R which are computed by the shown equations there. The way this works is that we start with a key pair. The way all these signatures work is you start with a key pair. You have got a secret key which I have denoted x. I will keep all my secret values in red. A secret key called x and a public key called P. The way you get from this secret key to the public key is you have some elliptic curve group generator. Some object that you can add to itself in some formal sense of add that is not too important, very many times. x is a random number. We add G to itself that number of times and then you get a public key. It turns out that if I give you some curve point and I say “I got this by adding G to itself a whole bunch of times” you can’t tell me how many times I added it. It preserves the secrecy. To produce this Schnorr signature what we do is we create this ephemeral key pair called a nonce. This is the equation R here. I think up a new secret key k that I am going to use just for this signature. I am going to do the key derivation to get this object R. Then I am going to do something a bit funny. I am going to hash up all of this data: my public key, my nonce and this extra auxiliary input called the message. In a signature the message is the most important part. I am going to throw all of this into a hash function, a SHA2 or something. The result is what is called a challenge. I am getting a random number out of the hash function. What I am going to do with this random number is produce a signature. I am going to compute this equation here, this s = k + ex, this linear equation using this challenge and my two secret keys. To verify this equation you do the following. This is the verification equation.
sG = kG + exG
The verification equation is the same except that we have multiplied every term in the equation by G. We are going to see this over and over again. I am going to have increasingly complicated equations up there. Every time when I want something to verifiable I am going to stick G in a bunch of places. You can see the signing equation has these two secret values. I don’t want anyone to know them. I am adding them together in this weighted sum to produce this single value s. There is nothing being revealed about either of them. When I multiply everything by G, the public knows s, they can multiply s by G. kG is my public nonce, xG is my public key and e the public knows. You can see that the components of the verification equation are all things that everybody can verify. That means that I, the knower of x and G can produce this signature but everybody who knows my public key can verify. That’s a Schnorr signature.
Sign-to-Contract
I am going to do a little bit of a diversion now from Schnorr signatures to talk about sign-to-contract. Here is my Schnorr signature equation.
P = xG
R_0 = kG
R = R_0 + H(R_0|c)G
e = H(P,R,m)
s = (k + H(R_0|c)) + ex
Now I have added this extra step. I said I was going to create a public nonce by thinking up this ephemeral secret key k. I am going to do that but now I am going to take another message called c and I am going to tweak both my public nonce and my secret nonce by a hash of my original public nonce and this extra message. What the third line is doing is it it turning this quantity R from just being an ephemeral public key, an elliptic curve point, to also being a commitment to some auxiliary datac. This is useful in a few different situations. One of them is notably for timestamping. This lets you turn a signature into a commitment. This lets you put that signature onto the blockchain and because a signature itself is a commitment you have now committed some data in the blockchain without any additional space being used. The cool feature of R = R_0 + H(R_0|c)G is that the resulting point is just a point. The resulting signature is exactly the same as a signature without a commitment. So that’s useful for timestamping. It is useful for another thing that I will get to at the end of my talk. It is useful for a weird application which I am going to try to describe here. First here is my verification equation. See that nothing has changed, multiply everything by G.
sG = (k + H(R_0|c))G + exG
Sign-to-contract replay attack
Suppose you have a hardware wallet producing these signatures. Normally you give your hardware wallet a message, it knows the secret key, it will produce these secret nonces, it is going to compute this ephemeral secret k. There are a couple of important properties that k needs to have if it is going to work as an ephemeral secret key. All those properties can be summarized by saying that k needs to be uniformly random. If k deviates from uniform at all, if there is even a little bit of bias, if the highest order bit is 0.1 percent more often than one that is a problem. If you produce enough signatures and you publish enough of those then somebody can take that small amount of bias and eventually exploit that to solve for all the different ks and the secret key. Then you lose all your coins. It is really important that k is uniformly random. The way this is done typically is in a hardware wallet you take your message and you take your secret key, or some other secret data you have got on your hardware wallet, and you hash all of that up to produce k. The output of a hash we believe is a random function. That is an assumption we use throughout Bitcoin and a lot of cryptography. That gives us a way to uniformly produce a value k assuming that our hash function is secure. We get a random number but we don’t need a random number generator. They are difficult to implement in hardware. They are impossible to verify. It is not nice to require a random number generator. It is also nice because it is stateless. There are some other ways to generate random numbers where you require your hardware wallet to make sure that is not reusing the same random seed, incrementing something or doing something like that. If all you are doing is hashing up your message and your secret then you get this stateless random number generator that doesn’t require any hardware random number generation which is great. But this interacts badly with sign-to-contract if you try to do it naively.
Suppose you have your hardware wallet and up top I am saying it is producing this value k by hashing up the secret and the message like a good hardware wallet should be doing.
k = H(x|m)
You ask it to do a sign-to-contract with this commitment c. It produces this value k, it hashes up the secret and the message and then tweaks k by adding this extra hash. Then it produces a signature. That’s great.
s = (k + H(R_0|c)) + ex
Suppose you go to the hardware wallet and ask it to re-sign the same message. I am not going to change m here, the same message. I ask it to commit to a different c’. The hardware wallet will produce two signatures which we see here. These two s equations.
s = (k + H(R_0|c)) + ex
s = (k + H(R_0|c’)) + e’x
Because I have tweaked the commitment I have managed to change the public nonce. I have changed the signature in a way that the hash challenge is going to change but these two equations both use the same secret nonce k. The difference between these two equations does not have k anymore. You can see by counting the number of red entities, the last equation only has one red entry. If you shuffle everything except the red x onto the left hand side of that you can solve for x. This is a problem. If you have a hardware wallet that supports sign-to-contract and you ask it to sign the same message twice with different commitments you would be able to extract the secret key this way. There is a simple fix to this. There is always a simple fix. That is going to be the lesson of this talk. I am going to bring this up time and time again. You do this, the secret key is lost but there is always a simple fix. The simple fix in this case is that when the hardware wallet is generating its nonce it should not only hash the secret key and the message, it should also hash the commitment. You give it this commitment, it takes that commitment and it can use that to generate a unique nonce even if you change the commitment. If you change the message or the commitment it will use a different k value. If you try to do this subtraction you will have different ks in the two signature equations and they are going to cancel out like this.
Sign-to-contract as an Anti-Nonce-Sidechannel Measure
Now let me talk about a cool application of sign-to-contract and it too why it does not quite work. But there is a simple fix. The technique I want to talk about I believe originates with Greg Maxwell. It is to use sign-to-contract as a way to prevent nonce sidechannel attacks. I mentioned that if these nonces k are biased in the sense that the individual bits have detectable deviations from uniform then you will leak your secret key. It is a bit more insidious than this actually. The hardware wallet could do something like producing random nonces and then HMAC that nonce with some secret key that only some attacker knows. Thereby introduce a bias in individual bits that is only detectable by somebody who knows this HMAC key. It is possible to produce signatures that appear uniformly random that are resilient to whatever analysis you can do but which nonetheless are slightly biased in ways that only some bad guy can tell. If you have hardware generating signatures there is not really any way to verify that this isn’t happening. This is the risk right now for every single hardware wallet that is currently in use. The random numbers it is generating might not be being generated perfectly honestly. In general the way to detect this is to create some dummy signatures with the secret key that you extract from the hardware wallet. Then you can solve for k and check it was produced deterministically. That is very difficult to do and you can’t do it with signatures that you actually want to use. If you have keys that you are actually using on the blockchain you don’t want to be pulling those secret keys out of your hardware wallet and then doing a bunch of analysis and plugging them in, that’s not prudent. Instead there is a way where if you trust your host computer you can ask the host computer to insert some additional randomness into your nonce. So that even if your hardware wallet is somehow compromised and is trying to produce nonces that have this detectable bias we can totally clear out that bias. Just using the sign-to-contract equation up there.
(If the hardware device knows c before producing R_0 it can grind k so that (k + H(R_0|c)) has detectable bias)
The trick is that even if k is biased that hash is not biased. You have something of questionable uniformity added to something that is unquestionably uniform and you’re great.
Q - …
A - You just need c to be unique or mutually independent.
There are some specific things that I can say here. All I am going to say is that I need c to be unique. Your host generates some value c. It needs to have high enough entropy. It needs to be something that someone can’t guess. So you give the hardware wallet something to commit to, some c. This even could be something that you want to commit to in the blockchain where you put it in a Merkle tree with some other uniformly random data. The point is you are going to require the hardware wallet to produce a commitment to something sufficiently random. Then you aren’t going to publish what that commitment is. Unlike the timestamping application and some of the other applications I am going to talk about we aren’t going to publish everything about c. We just throw that away. The resulting nonce will have no trace of c being in there. Nobody can tell that this is done. But as long as your host was acting honestly the resulting nonce will be useless to anybody trying to attack this. The security comes down to either k is working correctly, which we can hope is happening today, or your host is ok and it is able to reliably produce some randomness with enough entropy. Again this is subtle and if you do it in the naive way it doesn’t work. If you give some uniformly random thing to your hardware wallet it does this k = H(x | m | H(c)). If you give it c in advance, rather than using a hash function it can just keep trying a bunch of ks until it finds one such that k + H(R_0|c) has a detectable bias. If it is trying to produce one bit of bias it only has to try twice on average. So that is no good. You don’t want to tell the hardware wallet c, what it is committing to, until it is already decided what its original nonce is going to be. We don’t trust the original nonce. We want to make the hardware wallet commit to that and then we want to re-randomize that. The way we do this is instead of sending the hardware wallet c to begin with we send it a commitment to c. A commitment to the randomness we want it to commit to. The hardware wallet will reply with its untweaked nonce. Then we say “Now I am going to give you the actual data I want you to commit to.” The hardware wallet will go and do everything the way you expect it to. It will output a signature. Because you gave it a commitment to c it is able to ensure that if you tweak c in some way that it is not susceptible to replay attacks. But because it doesn’t know c itself it is unable to predict what the nonce it will eventually produce is. And it will be unable to insert any bias into that. It is implicit in this slide that you wind up having this three step protocol with a hardware wallet. This allows you to eliminate any possibility of a nonce sidechannel using a biased nonce.
Schnorr Multisignatures
I am going to move on from sign-to-contract to talk about Schnorr multisignatures. Recall the Schnorr equation from the first slide. It is in there, I’ve interspersed it with a whole bunch of other equations now. What have I done here to change the Schnorr verification equation is introduce a whole bunch of parties. Let’s say there is n of them. Each of them has their own secret key. They are going to produce a joint key by adding together all their secret keys and adding together all their public keys. Because of the linearity of my private, public mapping function I can just add secrets together and I can add the corresponding public things together and all the algebra will work out. This is actually a way to produce a Schnorr multisignature. During key setup time everybody produces a secret key, everyone throws their public keys together at each other. We add them up. P is the sum of everyone’s individual public keys. During signing time everyone produces a nonce, an ephemeral public key as though they are going to produce a signature. But instead of using that directly they throw that in the pot and everyone adds this up. R is the sum of everybody’s contributions to R.
P_i = x_i .G
P = sum of P_i
R_i = k_i .G
R = sum of R_i
e = H(P, R, m)
s_i = k_i + e.x_i
s = sum of k_i + sum of e.x_i
Then we have a public key, a public nonce, a message and we can compute this challenge e = H(P, R, m). Once everybody throws their nonce in the pot everybody can compute e. Then they all produce a signature. Then you can add all the signatures together. To get the final public key everyone added their public keys, to get the final nonce everyone added their nonces together. To get the final scalar part of the signature everyone adds their scalar parts of the signature together. It is great. Our verification equation as always just involves adding a whole bunch of Gs to that.
s_i. G = k_i.G + e.x_i.G
s = sum of k_i.G + sum of e.x_i.G
We can see our partial signatures are the second to last line here. These can be verified by everyone. If the final signature doesn’t verify it is possible to look at the individual partial signatures and see which party was misbehaving. Identify that person and kick them out or restart or something. If you have already started the multisignature protocol, it depends what your protocol is what you do about cheaters. It is certainty detectable which one no matter how many parties you have. But there is a problem here. In the first two lines here where I generated the public key, if some party knows everybody else’s public keys and they choose their public key to cancel out everyone else’s public keys you can see that the second line here, where you add everything together, if somebody poisoned the well there they can produce a final public key that is entirely controlled by them. The sum of all these secret keys should have contributions from every single signer. But if somebody maliciously cancels out everyone else’s contribution, they just have their own contribution, the result is something that looks like a multisignature key but actually is just one party who can produce signatures. That’s no good.
There’s a simple solution. Here the word simple is false in two senses. One is that it is not actually that simple an equation and the other is that it took us over a year to get this. Two failed papers, one of which was rejected in peer review, the other got through peer review and then someone else wrote a paper proving that our paper couldn’t be correct because it was impossible to write that paper. That’s quite a strong mathematical result. I don’t know how many of y’all are academics and have published papers. If you have gotten through peer review and then found somebody produced an impossibility result, not of your result but of the proof that you made. It claimed that it was impossible for our proof to be correct. We fixed it, it’s fine. There’s a simple fix. Always a simple fix. I got the email today, it went through peer review again and it is published today. That’s great. Let me start with the simple fix and then the simple fix to the simple fix.
mu_i = H( H(P_1 | P_2 | …| P_n) | i)
P_i = mu_i. x_i. G
P = sum of P_i
The first part of the simple fix that we’re actually going to deploy. That’s not a detour, thank you Greg. We’re going to hash up everyone’s public keys here. You can see in the middle of that first line there is this hash of public key 1, public key 2, public key 3 and so on. We are going to get this thing that is re-randomized whenever anyone changes their public keys. Every individual signer is going to produce this object called a MuSig coefficient, this mu_i. They take the hash of everyone’s public keys, they hash that up alongside their index in the signing protocol. If anybody tries to change their public key in response to the other people’s chosen public keys in an attempt to cancel them out or something, this giant hash of everyone’s public keys will change and everybody’s MuSig’s coefficient is going to change. And then our sum, lines 2 and 3, has a random scaling factor on everyone’s public keys. Whenever anyone tweaks their public key everybody’s scaling factor changes. There is no way to cancel out. You can prove this in the sense of provable security. There is a paper that was published today that goes through all the gory details. It is very involved. If you change your key you mess up everybody’s randomizers and whatever equation you were hoping to achieve there you’ve destroyed because you’ve re-randomized everything. We run through the exact same equations. You add up all your nonces, you add up all your signatures, everything is golden. You publish a signature and it is all great. I’ve added mu_i twice here. I should have added it three times, there is still a gap there.
Verifiable Secret Sharing
I am going to do an even further diversion into something called verifiable secret sharing. Here is where I really don’t expect y’all to be following the algebra exactly. Even if you were ok up to the last slide, this one has a quadratic number of secret values that I’m going to throw into a matrix. In a matrix you can imagine repeating this line a lot of times. Suppose that somebody wants to shard their secret key. One of the participants in this giant multisignature wants to give the other participants some objects that will allow the other people to reconstruct their secret key. Nobody is ever going to reconstruct secret keys. They are actually going to just produce signatures. Suppose you’ve got 10 parties who all want to produce a signature. Somebody maybe doesn’t want to participate necessarily. They want to give the other 9 parties enough data so those 9 parties together can reproduce their secret. The way they do it is with something called Shamir secret sharing. They choose this giant random polynomial p_i(X). This random formal polynomial. They choose a whole bunch of these coefficients, all these gamma_i,k, uniformly random things. They choose this polynomial of order k-1 where k is the number of people they want to split their secret to. If they want 9 participants to be able to reconstruct it they have to use degree 8. Then they evaluate this polynomial at some small integers: 1,2,3,4,… They give each of these evaluations to individual people. That’s the middle of the slide here. We’ve got this zeta_i,j which is the evaluation at j of participant i’s secret polynomial.
p_i(X) = x_i + gamma_i,1. X + gamma_i,2 . X^2 + …. + gamma_i,k . X^(k-1)
zeta_i,j = p_i(j) = x_i + j_gamma_i, 1 + (j_gamma_i,2)^2 + …. + (j_gamma_i,k-1)^(k-1)
If you can imagine this middle equation being written over and over you’ll see a matrix of all these random values. You can imagine inverting this matrix and solving for the secret x_i from all these equations. I’m handwaving through this but it is a possible thing to do. This is called Lagrange interpolation. What you get is this final equation at the bottom here.
p_i(0) = x_i = sum of lambda_i,j. zeta_i,j
Given any subset of k parties, rather than 9-of-10 imagine you’ve got 5-of-10. You’ve got 10 choose 5 different possible subsets. If once you choose a subset of 5 participants you can compute these Lagrange coefficients. There’s this sum, these Lagrange coefficients lambda_i,j, you multiply those the secret zeta_i,j, you sum all those up and you will reconstruct the original secret key. You’ll see all my sums from here on are going to specify where I’m summing over the people who are signing which is going to be a subset of the total participants. That’s Shamir’s Secret Sharing. Verifiable Secret Sharing is this, I am going to throw some G’s on here.
zeta_i,j . G= p_i(j). G= x_i. G + j_gamma_i, 1.G + (j_gamma_i,2)^2. G + …. + (j_gamma_i,k-1)^(k-1). G
One issue with using Shamir’s Secret Sharing for threshold signatures, which is what I am going to do in the next couple of slides, is that if one party gives shards to all the other participants and they do so in an inconsistent way such that it is not actually possible to reproduce their public key this can be very difficult to detect. You need extra rounds of interaction. If multiple people are doing this sharding at once, which they will, and you are combining things you wind up either needing to use a whole bunch of memory and a whole bunch of extra communication or you find you are unable to tell who is misbehaving. A goal in these kinds of schemes is we want a way for people to take all their secret coefficients from their secret polynomial, these gamma_i,j, they multiply those by G to get a whole bunch of public coefficients and they publish those. They publish those to all the other participants using some sort of broadcast channel or message board or IRC channel or Signal group. They should not use a blockchain, please. They could, it would work, there would be no consequences for them but don’t do it. However they do it they publish their public coefficients. They all see that and then they can verify. Everybody who receives on of these zeta_i,j can just run this equation. They multiply their zeta_i,j by G, the left most term is the participant’s public key and they have all these public coefficients. They add it up, they multiply it by their index, index squared, index cubed and so on and they get an equation which hopefully should be true if the issuing party is being honest. That’s verifiable secret sharing.
Using verifiable secret sharing it is possible to do a multisignature. It is kind of cool. What this slide is showing is if we start from a joint public key that is owned by all the participants, the first equation on this slide is just my original MuSig equation. I have a whole bunch of parties, they all contribute some secret key, they add up all their contributions to the key and they get a final key. The bottom most equation here is saying that rather than summing contributions from everybody I can take just a subset of signers which might be much smaller, it might be like 5 signers out of the 10 parties, and that set of signers is now somehow able to sum up their contribution. I’ve got this red box object, it is this sum thing in the second to last line, I’m just going to call it the box object from now on. Everyone who is signing has this box object and it depends on the secret that they were issued during key setup. Implicitly every party does this verifiable secret share. They all give shares to every other party and then using all the shares that everyone has communicated around, there’s quadratically many shares floating around here. These equations work out and now a subset of the original set of signers is able to sign. What is cool about this is that it looks like after you multiply by these Lagrange coefficients and you produce these red box objects, it looks like is my original multisignature equation.
Signing with VSS
We can see this in this slide. This is my Schnorr multisignature slide from a little while ago except everywhere that I had somebody’s secret key I have now replaced it with this red box object. The way that threshold signatures extend multisignatures is these two extra steps. Firstly a key setup, everyone has to do the sharding, you get all these shards passing around. Secondly when they start a signing session everybody who is participating in the signature, which now is a subset of the total set of possible signers, everyone participating computes these red box objects. There is a very straightforward way to compute that. It is just this sum that looks complicated on a slide but you are literally just doing a couple of multiplications and adding up the contributions from everybody. It doesn’t take a lot of time, it doesn’t take a lot of memory. It is very straightforward. Once again we throw in our G here. If you want to verify these things you can verify the partial signatures, you can verify the final signature. What is cool here is that I already showed you guys this. The extension to threshold signatures is conceptually, once you are past the key setup, threshold signatures aren’t different from multisignatures in terms of implementation complexity or in terms of how you think about security of the multisigning protocol. That’s something I might go into later afterwards if I feel like I still want to talk. The signing protocol here, I’ve been waving my hands a little about how everybody throw nonces into the pot and how they compute this challenge. That is a whole other set of irritating things that leak keys but which have simple solutions that took us quite a while to get through. Rather than saying more about that I am going to move on and talk about accountability.
Accountability
In the last slide I mentioned this cool feature that once you decide who is producing the signature, you throw these Lagrange coefficients in and everybody creates their red box objects, it is great. After you add up all the red box objects you get the original public key. And when you use these red box objects to produce these threshold signatures and you add those all up you get a signature with the total public key. The thing is that the sum doesn’t actually depend on the specific set that was used. These red box objects depend on your set of signers but they somehow go away. They all conspire to add up to the same thing no matter how they were computed. The result is the signature has no trace of the original set of signers in it. In fact there is no way to tweak this such that the signature is going to have a trace of which signers. Given a signature produced by some total public key, even if you know what all the red box objects would have been, even if you know all the signers participating and how many of them are required, you can’t distinguish one that was created with one subset from one that was created with a different subset. This is something called accountability, the ability to do this. Somewhere you might want accountability, say you’ve got a 2-of-3, some Bitcoin held by a 2-of-3 threshold signing policy, one of your 3 keys is a cold wallet key, it would be nice if there was some evidence after the fact that that cold wallet key was used. You don’t want people pulling that out of storage, I see some BitGo employees nodding at me, you want some evidence of this key being used. With unaccountable threshold signatures you don’t get that. You can’t distinguish between a signature that was created using the hot keys honestly, using whatever your correct signing protocol is, and one that was created in an illegitimate way.
So if this is an unaccountable threshold signature what would an accountable threshold signature look like? We have one in Bitcoin. It is possible to create a threshold signature by taking a bunch of individual signatures and just concatenating them, it turns out that is a threshold signature. If you want to require that any 5 of a fixed set of 10 people sign some message you can just ask 5 of them to sign the message separately. Take all their signatures in a row and there you go, you can validate each one, one after the other. If you are Satoshi maybe you validate them against different public keys all over the place, validation is cheap right… That’s one way to get it. The thing is that ignoring all the goofiness around the CHECKMULTISIG opcode, this is large. If you want to do a 5-of-10 signature it is 5 times as large as a single signature because you’ve literally got 5 signatures there. It is possible to do better than having this linear growth in your threshold signature size, every time you add a signer you add an entire other signature by doing stuff like combining keys in various ways and putting it into Merkle trees. You can get a poly-log sized threshold signature. But constant sized… The really cool thing about these Schnorr multisignatures that I’ve been describing so far is they are constant size. The resulting signature looks the same as a single signature. It seems like you can’t get an accountable signature that has this. There’s vague intuitive information theoretical reasons you might think that should be impossible. As you increase your threshold size, if you are doing 500 of 1000 signers there is 1000 choose 500 different possibilities there. You get this combinatorial explosion in how many different admissible signing sets there are. If you’ve got a constant size signature coming out of there it is not clear how you could fit combinatorially much information into that if that makes sense. It is just an intuition. Already by having constant size signatures it seems like we are violating similar unviable information theoretical bounds. But it does really seem like we can’t get a constant sized accountable signature which sucks. You’ve got to choose between constant size which is awesome for efficiency and also awesome for privacy, it hides your total signing set and your threshold policy, and accountability.
Semi accountability: Sign to contract for accountability in threshold signatures
In my next slide I am going to describe a compromise. This is what a compromise looks like in mathematics, between accountability and unaccountability. What I am going to do is bring back that sign-to-contract construction, I was talking about it at the beginning. I am now going to do a sign-to-contract in a multisignature. What is exciting about this is that all of your signers can check that the final signature is doing a sign-to-contract and what data it is committing to before they produce their partial signature. The second to last line as always is a partial signature. Notice this is computed by every signer after they know e. e here is a hash of all this data, in particular the public nonce R.
e = H(P, R, m)
If anybody doesn’t like what is being committed to, they will see what is committed to because otherwise they can’t compute R, they will refuse to produce their partial signature and they will refuse to participate in this signature. This multi-signing business gives this cool ability where you can say not only this signature commits to something but it is committing to in a way that every person who contributed to the signature agreed to. You can formalize this, you can prove that if you extend a Schnorr signature by adding this auxiliary sign-to-contract data, the commitment c, you get a strong signature on the auxiliary data. A Schnorr signature on the actual message you are signing, it is also a signature on the committed data. This is a cool feature that I’m going to exploit here. What I am going to do is take my unaccountable constant size threshold signature and I am going to, in parallel to producing this, produce an accountable signature. I am going to have everyone individually sign the data. Then I’m going to take that giant accountable signature that’s growing with the set of signers and I’m going to commit that inside my unaccountable signature. The individual signers can enforce this data is there. If you have a HSM or something that you’re willing to trust to enforce some business logic, this is a very simple piece of extra signing logic, then you can get accountability assuming that your hardware is not completely borked. Assuming that at least one party in this threshold is being honest and is willing to reveal the commitment to an auditor or the public or somewhere, then you get basically an accountable signature, a hardware enforced accountable signature. That’s another thing I need a name for. One reason you might want accountability is if you are worried nobody is producing this signature is honest. You are worried that someone has stolen your keys and run away with them and is producing signatures. This is not going to help with that. They can just not do the commitment if they have actually stolen the keys. But if your keys are on hardware tokens that will enforce this extra accountability side channel thing and that extra accountability requirement is upheld, this seems perfectly reasonable for a hardware token to be able to uphold that at least against a non nation state attacker, there is certainly a benefit here. It will satisfy whatever auditability requirements that you might have that make you want to have accountable signatures.
Open questions
(Can we construct a commitment that can be reconstructed or brute forced by third parties? Can we get deniability i.e. can a non-participant prove non-participation without help? Extension to BLS which has no space for committing data?)
In closing, let me close with a bunch of open problems I have related to this. This construction is kind of neat, it is not something that I have heard about before. It has got a weird security model that nobody in academia should care about but it is still useful in practice. There are a couple of issues with it though. One is that suppose that this commitment is upheld, you have a 2-of-3 threshold and 2 people who shouldn’t be producing a signature go ahead and produce a signature. They have got the audit logs that prove they produced that signature. But the third person is maybe the jilted person in some escrow arrangement has no way of seeing what that commitment is. The third party can’t produce the accountable signature, it can’t produce the commitment. What is worse is that the third party can’t even prove that they weren’t involved. It would be cool for one thing if it was possible for somebody not involved with the signature to reproduce the commitment and actually figure out which 2 of the 3 parties were involved. That seems impossible, it would literally be a constant size, accountable threshold signature if that were possible. But there is a second thing that seems less impossible, can you just get deniability? Can one of the people who has some secret key material, who in principle could have been involved in the signature, somehow prove that none of their data went into the commitment. A third open problem that people like to talk about outside of Bitcoin but within the cryptocurrency space, what happens if you bring in these BLS signatures, these pairing based signatures? These are kind of neat objects. BLS signatures let you do non-interactive threshold signatures. It is unaccountability on steroids. You produce a contribution to a threshold signature, other people can take that contribution and just add their signature. You don’t even have to know who they were or that they were involved or anything like that. The result is this constant size signature that hits the blockchain. You were involved, your public key is part of the aggregate, but there is no way to prove that or control that. A neat open question is is there any way to add a form of accountability in this weighted BLS? I don’t know, it is not the kind of problem that I worry about. I don’t spend a lot of time thinking about pairings these days but a lot of people in this space do. They might find that interesting. I have a fourth open problem that occurred to me while I was talking. I mentioned that one example of an accountable threshold signature is if you just concatenate individual signatures. But here’s a fun question. Instead of creating a separate signature during threshold signing, what if we just use these partial signatures on the second to last line? Do you think those count as signatures for the purpose of being accountable? If you committed to all of those s_j? Would that do it? People are saying yes. So we have a social proof that actually you don’t even need to do a separate signature. You just sign-to-contract all of the partial signatures. There’s a circularity here. There’s a simple fix. The issue is that these partial signatures are using this hash e which itself depends on the commitment. If I want to commit to the partial signatures then I’m kind of stuck. I can’t produce a partial signature without having already committed. There are multiple simple fixes that I heard from the audience there. So it is salvageable. Happy to take questions. Thank you all.
Q&A
Chaincode Labs just announced their Summer Residency for this summer of 2019. You really should apply.
Q - You talked about deniability. Is there a way even to force the other two parties to make the commitment if you’re not involved?
A - No. The other two parties have the ability to produce signatures that commit to anything at all or nothing at all. There’s no way to prevent that. There’s no way to tweak the keys or tweak the signature verification algorithm that would actually enforce that whilst still having this threshold policy property.
Q - Also on deniability, you were saying maybe it is possible because none of the non-signer information leaks into the public key. Theoretically some of it leaks through the Lagrange multipliers? You were saying that I should be able to deny that I was part of signing, actually I was part of signing because I gave up the Lagrange multipliers.
A - The issue is that no matter what set of Lagrange multipliers were used you will still get all these same final equations. The signature would be produced even if you were lying about the Lagrange multipliers, that’s the problem. You need to say “I was part of this” and then “Here are the Lagrange multipliers for if I was part of it”. They would still work, they would still add up but you weren’t part of it. All sets of Lagrange multipliers will work equally.
Q - I have a question about the commitments to the polynomial terms, the gammas. I remember there was a paper by Gennaro that was sort of a follow up to Feldman’s Verifiable Shamir’s Secret Sharing where they used Pedersen commitments with extra blinding factors to all of these terms trying to solve a security problem with the initial key setup?
Greg Maxwell: I think that’s a rogue key attack that you can have with Verifiable Secret Sharing. I don’t think it arises in the construction you are describing because of using it on top of MuSig, authenticated keys. That’s a good question to check.
A - We believe that because our original key was produced using MuSig there’s no way to do key cancellation even within the sharding procedure. That’s a pretty non-trivial claim that we haven’t worked through. It would be better to use a threshold secret sharing scheme that was inherently protected against that. This is the original Pedersen 1990 Verifiable Secret Sharing here.
Q - I have a question about the paper you published in May 2018. I was looking at Figure 3 in the MuSig paper. It was the size of the Bitcoin blockchain with and without multisignatures. Comparing what it would be like in 2018 if they had implemented MuSig from the beginning. I think the comparison was today it stands at 130GB and if we had implemented it it would have been 90GB today. But you also mentioned on storage savings that if we had also implemented key aggregation that would be more storage savings. Could you talk about that?
A - There are two things here. There is key aggregation and signature aggregation. Key aggregation is what I’m talking about here, this is where you get the constant size multisignatures. The other thing, signature aggregation, is what you are referring to. It would be possible to aggregate signatures themselves after they’ve already been added to a transaction. Then you can get some further savings that way. Signature aggregation has some complicated interactions with a whole bunch of other parts of the protocol, in particular how soft forks are implemented and also some stuff to do with blind signatures. Signature aggregation is probably quite a long way away relative to key aggregation where we just have a couple of minor engineering things to work out.
Pieter Wuille: That is all correct what you are saying. To answer your question if I recall correctly that figure only accounts for cross input signature aggregation and not for key aggregation because we can’t predict how people would have…
Greg Maxwell: There’s two disadvantages of the key aggregate approach that Andrew is talking about that are relevant here. One is you lose accountability. Even if Bitcoin had key aggregation from the start just the loss of accountability might mean that not everyone would use it. The other limitation is that it requires at least one extra round of interaction while signing which is kind of inconvenient if you are using a hardware wallet stored in a safe. So even with the ability to use key aggregation based multisignature and threshold signatures some users may not use it and it is difficult for us to estimate what the actual usage of those things would be.
Pieter Wuille: That’s also correct but also not an answer to the question. That same argument equally makes cross input signature aggregation harder. The reason is just that figure was produced by counting the number of signatures in every transaction and reducing it to one. It is very hard to count how many public keys are involved because those are in scripts that are committed to by the output. Plus what you would see in practice if multisignatures were involved is you wouldn’t use multisignatures anymore on the chain, you would use single key signatures. There’s a problem that people will change behavior in a non-observable way.
A - There’s kind of a meta thing about the way Pieter, Greg and I work. We often can come to agreement on the solution to these problems but we almost never agree on what the problems themselves are. We are all independently trying to fix our own hobby horse. Depending on which one of us gets the mic the talk comes out differently. Unless there are two mics and all three of us in the room. Pieter drew figure 3 so he had every right to answer a question about figure 3.
Q - About constant size multisig. Practically speaking what is the average or median amount for n for multisig on the blockchain? Even in worst case scenario when you have 10 parties, 5-of-10, different combinations.
A - If you are putting 5 signatures onto the blockchain you have to pay the transaction fees.
Q - I am speaking about constant size. The problem is if you have a lot of parties from a combinatorial point of view. There are so many possible valid signatures, if n is sufficiently large it would be possible to guess the signature.
Pieter Wuille: The number of valid signatures does not depend on the number of parties involved.
A - Every possible signature, there are roughly 2^256 possible signatures and every one of them individually could have been produced by every possible set. When I talk about not being accountable I mean something way stronger, literally every possible signature could have come from every possible subset. The Lagrange multipliers will conspire to make that possible.
Greg Maxwell: The protocol is zero knowledge in the technical sense. Every possible output could have been produced by every possible set of participants.
A - The question is about the signature that hits the chain, the signature doesn’t reveal any information about that.
Russell O’Connor: You are arguing information theoretically that we can’t have constant size so how big does k choose n have to be before it exceeds 2^256 or 2^512. It must be the case that you can hit a collision in the number of validations.
Greg Maxwell: If you increase the size of the signature then yes. But if you don’t increase the size of the signature there is no way to add any information unless you break the zero knowledge property of the signature. Which potentially you could do. I can probably in 5 minutes write down a scheme where you restrict the range of nonces and then you can prove which set of signers signed. But if you did that the signature would also be insecure in practice, not just in theory. Maybe there is a scheme where it is not insecure in practice but you would either have to break zero knowledge or add data.
A - That’s my intuition.
Q - I heard differing opinions about committing the public key in the hash. I even heard that a zero knowledge proof is when you commit the public key and the signature protocol is when you don’t. It sounds a little bit crazy. But some people were saying not committing the public key leads to tweaking the signature to be a signature under a different public key. What’s the story about this? Is there a consensus on what you should do and whether not committing to the public key gives some useful features?
A - There’s consensus amongst everyone who is standing behind the podium right here. The distinction between a signature and a proof of knowledge. This is something that came up before this talk. The security property of a signature, if you give an adversary a public key and as many signatures on whatever the adversary wants you to sign can the adversary produce a signature on a new message? That’s something called a strong signature, where it is allowed to reuse one of the messages but it has to somehow change the signature. The property of a zero knowledge proof of knowledge is much stronger. Given a signer and some sort of simulator for the signer that is playing with the random oracle and forking it or doing other stuff, can you actually somehow extract the private key? Conceptually these are very different things. In practice it is interesting that if you took this Schnorr signature and I dropped the P from this hash e here, if I didn’t commit to the public key in the signature I would get a strong signature, it would satisfy that property that nobody could forge a signature if I gave them a public key and a pile of signatures. But it would not be a proof of knowledge. By adding this commitment to P I get a proof of knowledge. The distinction in practice is not just academic, what this security property is. If you have a Schnorr signature that does not commit to the public key and is not a proof of knowledge it is possible to tweak a Schnorr signature thereby changing the public key and changing the message. You can change the message to whatever you want, you will get a valid signature but with a different public key. The public key will be the original public key plus something that kind of looks like a BIP32 tweak but definitely is not.
Pieter Wuille: It works with BIP32.
Greg Maxwell: Not changing the message but if you hold the message constant.
Pieter Wuille: If you take a Schnorr signature that has not committed to the public key and you know the chaincode, public key of the parent you can turn it into a signature for any leaf in the same tree.
A - Of course, I can see that. If you see the red x in the bottom equation, if you add junk to that equation you are basically adding whatever junk to x. If you know a BIP32 path you can tweak e. You can get a signature with a parent key and from there get a signature from a child key. Even from a child key you can get it from other children. This is maybe useful in some cases, people talk about using key recovery to do all sorts of weird crypto tricks, come up with a signature and then later learn a message, somehow they’ll have a public key corresponding to that message, the public key will kind of behave like what the signature should have been except it gets committed to a different part of the blockchain so you can do stuff in other orders. It is really cool, why wouldn’t you want the ability to do this? The reason is because otherwise you can forge signatures by changing your BIP32 path. The result is really footgun-ny and dangerous. My feeling is that we should always commit to the public key even though it disables this cool crypto protocol. Some of them are pretty cool and pretty appealing but it is so dangerous.
Pieter Wuille: I have two more arguments. One is that I believe the MuSig security proof requires committing to the public key. Another one is, this is something I picked up from a Twitter discussion between… and Gregory Neven, even though we have a security proof that reduces MuSig to discrete logarithm, if you had something that could forge a MuSig signature it could be used to produce a discrete logarithm break, the same is true for Schnorr signatures in general. But if you commit to the public key then you can reduce the security of a multisignature to an actual single signature security. This theoretical reduction to discrete logarithm has a weakness factor built in, it doesn’t actually give you the same security level. This reduction if you have the public key does not. With the public key you can state that the multisignature is as secure as the single signature construction.
Greg Maxwell: Without it there is a constant factor difference in the security so theoretically it has better security from that perspective.
A - There are a few other arguments I can think of but I think those are pretty thorough already.