Shamir Secret Sharing and Quorums – MPC for Cryptocurrency Protection
[caption id="attachment_3631" align="alignnone" width="800"] MPC for Cryptocurrency Protection[/caption] This is the first blog in a series aimed at explaining the growing use of MPC and threshold signing to protect cryptocurrencies. The Problem: Key Protection is Not Enough As we all know, one of the primary features of cryptocurrencies and blockchain-based distributed ledgers is that operations are irreversible; once a validly-signed transaction is on the blockchain, it cannot be removed. Since such transactions represent transfers of money (digital coins), a single fraudulent use of a private signing key can be disastrous. That is, consider an address (public key) holding millions of dollars; if an attacker can obtain a single signature with that key, then they can steal all of the money protected by that key, and the theft cannot be reversed. Due to the above, the problem that we need to solve here is more that of fraudulent key usagethan key theft. Clearly, if an attacker steals the private key, then they can sign on a fraudulent transaction and steal all funds. However, even if they are able to just trick the system into generating a single signature of its desire, then it can achieve the same ends as stealing all coins associated with that key. Thus, even if a perfectly-secure module existed that prevented any keys inside from being stolen, if it is possible for an attacker to access that module and use it to generate a signature, then all would be lost. Quorum Authorization A quorum is an authorized set of parties, and quorum authorization refers to the definition of a set of parties, and a specified subset of those parties, who are allowed to carry out the operation. A simple m-out-of-nquorum, called a threshold quorum, defines that any subset of m of the specified set of n parties can authorize the operation (but no subset of size smaller than m can authorize it). More advanced quorums can be defined, combining multiple threshold quorums. For example, one could define that 3-out-of-5 of the parties in operations AND 2-out-of-3 of the parties in customer service AND 2-out-of-2 bots (automatic servers) need to authorizes the operation. Then, an attacker would need to breach and steal an entire quorum, in order to do anything. Note that in the above quorum, 7 parties are needed to authorize. However, if an attacker breaches all 5 of the parties in operations and both bots, it would have 7 parties, but still could not do anything. This is because it needs to breach 7 parties that fulfill the defined quorum structure. We say that a subset of parties that fulfill the structure is authorized or is just a quorum. Note also that the quorum structure can be tailored to the amount of funds protected by any given key – small amounts of funds can have a simple quorum structure, while large amounts of funds can have more complex quorum structures. What is Secret Sharing? Secret sharing is a method, invented in the 1970s, for sharing a secret among a designed quorum structure so that any authorized subset is able to reconstruct the secret, while any smaller subset that does not constitute a quorum is not able to learn anything about the secret. Consider for a moment sharing a value in the range of 0 to 99 between two parties. Then, this can be shared by providing each party random values between 0 and 99 that sum to the secret modulo 99 (which means that we just wrap around, so that 100 is the same as 0, 101 is the same as 1, and so on). For example, if the secret is 45, then the first party can have any random number (say 68) and the second party’s number would then be 77, since 68 + 77 = 145 = 45 (modulo 100). The first party knows nothing about 45 since 68 is just a random number; the second party knows nothing about 45 since it knows nothing about the first party’s number. (In fact, given 77, all secrets are possible. If the secret was 85 then the first party would have 8, and if the secret was 23 then the first party would have 46. Since the first party could have anything, all secrets are possible.) This same idea can easily be extended to secret-share a value between any m parties, requiring them all to reconstruct (in our above notation, this would be an m-out-of-mquorum structure). In order to do this, simply choose random numbers for the first m – 1 parties’ shares, and set the last party’s share to be secret minus the sum of the first m – 1 parties’ random numbers. Extending this to arbitrary threshold quorums is more of a challenge. How can I share a secret so that any subset of size m out of a set of n can reconstruct, but no smaller subset can? I can do this naively by separately sharing the secret with every subset of size m using the m-out-of-m method above. However, this would be very inefficient since even for a relatively small set of n=10 and m=5, there are 252 different subsets that each party participates in. Thus, each party would have to hold 252 different shares, which is a lot. (This number grows quickly as well; for n=20 and m=10, there are 184,756 subsets.) Shamir’s method solves this problem exactly. What is Shamir Secret Sharing? Shamir’s method is based on properties of polynomials. It is easily explained for 2-out-of-n sharing, but extends in a straightforward way to any m-out-of-n. We begin with the 2-out-of-n case. Let the value being shared be s, and define a random line that cuts the Y-axis at s. Specifically, define the equation f(x) = ax + s, where a is a random number. Then, each party is given one point on this line; specifically, we can give the i’th party the value f(i) = ix+s. Note that given any single point on the line, one can rotate the line in any direction and this point would still be valid, meaning that the line could still cut the Y-axis at any point. Thus, no single party knows anything about the secret. However, given any two points on the line, using high school mathematics, the parties can reconstruct the line and then compute s = f(0). See the diagram below, given a single point, all secrets are still possible. (We note that in order for this to actually work, all operations are over a finite field, but we can ignore that for now.) In order to extend this to any m-out-of-n sharing, the only difference is that instead of taking a line, one takes a random degree-(m – 1) polynomial f so that f(0) = s. This works since a degree-(m – 1) polynomial can be reconstructed (technically called interpolation) given any m points. Furthermore, as with the line, given any m – 1 or fewer points, all possible Y-axis values are still possible. It is possible to extend Shamir’s sharing to enable the AND/OR of multiple threshold structures in the following way. If we wish to share a secret s so that a quorum is needed both in a threshold set A and a threshold set B, then we first additively share s into s1 and s2, as shown above. Then, we share s1 amongst set A using standard Shamir sharing, and we share s2 amongst set B using standard Shamir sharing (each according to their required threshold structure). Now, in order to learn s, it is required that both a quorum of set A and a quorum of set B participate, or nothing will be learned about s at all. This can be extended to multiple ANDs by further splitting s1 or s2 in the same way, and OR can be dealt with by just sharing the same value amongst both sets (since either of them alone should be able to reconstruct). Shamir Sharing Limitations for Quorum Authorization Shamir’s sharing is a powerful idea, and it can be used to strongly protect a secret. However, a crucial property to note is that once the parties reconstruct, all secrecy properties are lost. In the cryptocurrency setting, we may want the parties to collaborate to transfer some of the funds from an address. However, once they reconstruct the secret, they can use the key multiple times and sign on anything. More notably, a quorum may be asked to authorize the transfer of $10,000. However, once the key is reconstructed, nothing can prevent one of the parties (and one of the parties alone) from using the key to transfer millions of dollars, or in general, all funds protected by that key. Thus, secret sharing solves the problem of protecting the key and requiring a quorum to get together to reconstruct it. However, once it is reconstructed, all protections are lost; a single authorization provides the parties (or any single rogue party) the capability of doing anything it wants. It is even possible for the rogue party to wait until everyone else provides their share; then it just takes all of those shares and privately reconstructs the secret using its own share. In the end, the rogue party will be the only one knowing the secret and can use it maliciously. Combing Secret Sharing with MPC In the next blog in this series, I will explain how MPC can be used in conjunction with secret sharing to carry out authorized operations without ever reconstructing the key. Read the subsequent blog posts in this series: Additional Properties of Threshold Signing, and MPC Compared to Other Approaches.