From the buried gold of Treasure Island to the seven missing Fabergé eggs, lost and stolen treasure has long been the stuff of legend and romance. In Bitcoin, though, there are no princesses, dragons, or (seafaring) pirates, and not much romance. Fortunes are often lost simply because private keys are wiped from laptops, the slips of paper they’re printed on go missing, or they’re stolen by hackers.
Mundane as it may seem, key management is critically important in any cryptographic system. Cryptocurrencies like Bitcoin and Ethereum are no exception. Lost or stolen keys can be catastrophic, but handling keys well is notoriously hard. Users need to protect their keys against theft by wily hackers, without securing them so aggressively that they might be lost. Key management is especially challenging in business settings, where often no one person is trusted with complete control of resources.
A common, powerful approach to key management for cryptocurrencies is multisig transactions, a way to distribute keys across multiple users. Such key distribution is referred to more generally as secret sharing.
We have just released a paper addressing a critical problem with secret sharing in general and in cryptocurrencies in particular. We refer to this problem as access-control paralysis.
A few months ago, an acquaintance approached us with a simple but intriguing problem, a good example of real-world key distribution challenges.
This person---we’ll call our whale friend Richie---shared ownership of a large stash of Bitcoin with two business partners. Richie and his partners naturally didn’t want any one partner to be able to make off with the BTC. They wanted to ensure that the BTC could only be spent if they all agreed. There’s a simple solution, right? They could use 3-out-of-3 multisig where all three would then need to sign a transaction involving the BTC. Problem solved! Or is it?
However, that’s not the whole story. Richie and his partners were also worried, naturally, about what would happen in one of their keys was lost. The device storing a key might fail, a key might be deleted by mistake, or, in some very unfortunate cases, such as a car accident, a shareholder might physically lose the ability to access her key. The result would be a complete loss of all of their BTC.
This isn’t the only bad scenario. It’s also possible that Richie and his partners have different ideas about how the money should be spent, and can’t come to an agreement. Worse still, one malicious or piggish shareholder might blackmail the others by withholding her key share until they pay her. In this case, the BTC could be lost, temporarily or permanently, to indecision or malice.
We use the term paralysis to denote any of these awkward situations where the BTC can’t be spent. Unfortunately, N-out-of-N multisig doesn’t solve the paralysis problem. In fact, it makes the problem worse, as loss of any one key is fatal.
Richie and his business partners.
For this reason, avoiding paralysis while meeting the goal of Richie and his partners---i.e., requiring full agreement to spend the BTC---seems impossible. Actually, it is impossible with secret sharing alone, because of a basic paradox. Suppose we have an N-out-of-N multisig scheme, which we clearly need to enforce full partner agreement for transactions. If N-1 shareholders can somehow gain access to the BTC when one share goes missing, they can simply pretend that one share has gone missing and access the fund on their own. In other words, what we had to begin with was really some kind of (N-1)-out-of-N multisig, which is a contradiction.
Richie’s problem seems to have left us in a state of paralysis...
Thanks to the advent of two powerful technologies, blockchain and trusted hardware--Intel SGX, in particular---it turns out that we can actually resolve this paradox. We can do so efficiently and in a very general setting---to the best of our knowledge, for the first time. Toward this end, we introduce a novel technique called a Paralysis Proof System.
As you’ll see, fairly general Paralysis Proof Systems can be realized relatively easily in Ethereum using a smart contract---no SGX required. We present an example Ethereum contract in our paper. Scripting constraints in Bitcoin, however, necessitate the use of SGX and also introduce some technical challenges. Prime among these is the fact that without significant bloat in its trusted computing base, an SGX application cannot easily sync securely with the Bitcoin blockchain.
Our approach leverages a novel combination of SGX with a blockchain that avoids the need for an SGX application to have a trustworthy view of the blockchain.
The intuition is fairly simple. A trusted third party holds all of the keys in escrow. If one or more parties cannot or will not sign transactions, leading to the paralysis described above, the others generate a Paralysis Proof showing that this is the case. Given this proof, the third party uses the keys it holds to authorize transactions.
If we have a trusted third party, though, we’re clearly not achieving the security goal set forth by Richie and his friends. One party controls all the keys!
This is where SGX comes into play. An SGX application can behave essentially like a trusted third party with predetermined constraints. For example, it can be programmed so that it is only able to sign transactions when presented with a valid proof. (In this sense, SGX applications behave a lot like smart contracts.) Thanks to SGX, we can ensure that the BTC can only be touched by a subset of parties when provable paralysis occurs.
Of course, even given this magic that is SGX, we still need to ensure that Paralysis Proofs can only be generated legitimately. We don’t want Richie’s partners to be able to “accuse” him, falsely claiming that he’s dead by, say, mounting an eclipse attack against the host running the SGX application. Happily, blockchains themselves provide a robust way to transmit messages and for a party to signal that she is alive. To implement a Paralysis Proof System for Bitcoin, we take advantage of this fact, along with a few tricks. For the sake of simplicity, we’ll focus on the problem of inaccessible keys, setting aside other forms of paralysis for the time being.
A Paralysis Proof is constructed by showing that a party P is not responding in a timely way and thus appears to be unable to sign transactions. The system emits a challenge that the “accused” party must respond to with what we call a life signal. If there’s no life signal in response to a challenge for some predetermined period of time (say, 24 hours), this absence constitutes the Paralysis Proof.
For Bitcoin, a life signal for party P can take the form of a UTXO of a negligible amount of Bitcoin (e.g. 0.00001 BTC), that can be spent either by P — thereby signaling her liveness — or by pk_SGX---but only after a delay. Note that sk_SGX is only known to the SGX application.
Let’s take our example of three shareholders again. Let’s say each of them possesses a key pair (sk_i, pk_i). First they escrow their BTC fund---let’s suppose it’s 5000 BTC---to UXTO_0 -- an output spendable by either all of them or pk_SGX. Suppose now that P_2 and P_3 decide to accuse P_1. Upon receiving their request, the SGX application prepares the following two transactions and sends them to P_2 and P_3:
The shareholders that accused P_1 should therefore broadcast t_1 to the Bitcoin network, wait until t_1 is added to the blockchain, then wait for the next 144 blocks, and then broadcast t_2 to the Bitcoin network. There are two possible outcomes:
The security of life signals stems from the use of a relative timeout (CheckSequenceVerify) in the fresh t_1, and the atomicity of the signed transaction t_2. To elaborate, t_2 will be valid only if the witness (known as ScriptSig in Bitcoin) of each of its inputs is correct. The witness that the SGX enclave produced for spending the escrow fund is immediately valid, but the witness for spending t_1 becomes valid only after t_1 has been incorporated into a Bitcoin block that has been extended by 144 additional blocks (due to the CSV condition). Thus, setting the timeout parameter to a large value serves two purposes: (1) giving P1 enough time to respond, and (2) making sure that it is infeasible for an attacker to create a secret chain of 144 blocks faster than the Bitcoin miners, and then broadcast this chain (in which t_2 is valid) to overtake the public blockchain.
Although we use Bitcoin as a running example, the power of Paralysis Proof Systems extends beyond cryptocurrencies and the techniques behind them support a range of interesting new access-control policies for problems other than paralysis. Some of these policies are easy to enforce in smart contract systems like Ethereum, but others aren’t because they rely on access-controlled management of private keys, which can’t be maintained on a blockchain.
For example, Paralysis Proof Systems can be applied to credentials for decryption. You can use Paralysis Proofs to create a deadman’s switch for the release of a document, allowing it to be decrypted if a person or group of people disappear. Here are some other examples of access-control policies other than paralysis that can be realized thanks to a combination of blockchains (censorship-resistant channels) plus SGX:
In general, the combination of SGX and blockchains supports a fundamental revisitation of access-control policies in decentralized systems and introduces powerful new access-control capabilities---capabilities that are otherwise impossible to achieve.
To learn more, read our paper at here.
Many interesting extensions of the above are discussed in our paper. Here are a couple.
As mentioned, it is the scripting constraint of Bitcoin that necessitates the use of SGX. In fact, we also present a (somewhat less efficient) approach without trusted hardware that makes use of covenants, a proposed Bitcoin feature. We refer readers to our paper for a covenant-based protocol. The bottom line is, the complexity of the covenants approach is significantly higher than that of an SGX implementation (in terms of conceptual as well as on-chain complexity). As there have been recent proposals to support stateless covenants in Ethereum, the comparative advantages of our SGX-based design may prove useful in other contexts too.
In the aforementioned example, the fund can be spent by pk_SGX alone, but it’s important to note that’s not the only option. In fact, one can tune the knob between security and paralysis-tolerance to the best fit their needs.
For example, if the three shareholders only desire to tolerate up to one missing key share, what they can do is to move the funds into 3-out-of-4 address where the 4th player is the SGX enclave. If all of them are alive, then they can spend without SGX. If one of them of being incapacitated, the enclave will release its share if the rest two of players can show a Paralysis Proof. Therefore, even if the secret of SGX is leaked via a successful side-channel attack, the attacker cannot spend the fund unless colluded two malicious players.
This is an interesting line of future research we intend to pursue.
Fan Zhang is a PhD candidate in CS at Cornell University. His research interest is in blockchains, trusted hardware, system security and applied cryptography. more...
Iddo Bentov is a postdoc at Cornell University, and author of a number of academic papers on cryptography and cryptocurrency. more...
Ari Juels is a Professor at the Jacobs Technion-Cornell Institute at Cornell Tech in NYC and Co-Director of IC3. more...
bitcoin / security / ethereum / hyperdex / release / nosql / selfish-mining / blocksize / dao / surveillance / privacy / mongo / broken / weaver / nsa / meta / leveldb / blockchain / 51% / voting / smart contracts / graph stores / decentralization / bitcoin-ng / vaults / snowden / satoshi / philosophy / mt. gox / mining pools
