Communications of the ACM
Home/Magazine Archive/April 2016 (Vol. 59, No. 4)/Technical Perspective: Fairness and the Coin Flip/Full Text
Research highlights
Technical Perspective: Fairness and the Coin Flip
To view the accompanying paper, visit doi.acm.org/10.1145/2896386
Alice and Bob have a pleasant dinner together, and want to randomly choose who will have to wash the dishes afterward. How can they fairly choose? One time-honored method is for Alice to flip a coin (hiding it from Bob). Bob calls his guess, and then Alice can reveal the coin, revealing who is stuck washing dishes. Both can verify for themselves whether the procedure was fair.
What if Alice and Bob are on opposite sides of the globe, able to communicate only via the Internet? Over three decades ago, cryptographers designed a clever scheme for solving this coin-tossing problem: roughly, Alice flips a coin and sends Bob a cryptographic hash of the outcome; Bob sends Alice his guess; and then Alice can reveal the coin toss outcome, allowing both Alice and Bob to verify who won and who lost. This protocol is useful in distributed settings where multiple parties who do not trust each other want to jointly generate random values that no one can influence or bias.
The following paper introduces an exciting new idea for how to provide fairness: leverage Bitcoin's existing infrastructure for distributed consensus.
Unfortunately, this scheme has one shortcoming. Alice learns the outcome of the coin toss before Bob does. If Alice is dishonest or a poor loser, she can gain an unfair advantage. After Bob sends his guess, Alice knows whether she won or lost; if she won, she can continue to reveal the coin toss outcome and claim her winnings, but if she lost, she can refuse to continue the protocol, break the connection with Bob, and if necessary claim her computer crashed. This way, a dishonest Alice can ensure either she wins or no one does, which is unfair to Bob. This is known as the fairness problem.
In some applications, unfairness can be tolerated, for instance, if there is a way to punish cheaters or if the parties must place a deposit with a trusted escrow service before beginning the coin-flip process. In others, though, this is a serious problem. Researchers have explored various methods for providing fairness, but none are fully satisfactory. Moreover, there are negative results: in a general setting where there is no trusted third party for dispute resolution, the fairness problem appears to be unsolvable. The general view seemed to be that this is simply an unavoidable problem.
The following paper introduces an exciting new idea for how to provide fairness: leverage Bitcoin's existing infrastructure for distributed consensus. Bitcoin is a sophisticated distributed system that was designed to resist manipulation even by sophisticated, well-resourced attackers. The authors illustrate how we can build cryptographic protocols whose security rests on the foundation provided by Bitcoin: breaking the cryptographic protocol would require breaking Bitcoin, something that is believed to be difficult to do.
The paper exploits a fascinating feature of Bitcoin technology. Bitcoin provides an audit log of transactions, and it allows transactions to contain scripts—programs that determine whether the transaction will happen. The authors use this aspect of Bitcoin to achieve fairness: scripts implement the functionality that would otherwise need to be provided by a trusted third-party escrow service.
More broadly, distributed coin flipping is not the only task we might want to perform in a distributed world. Decades ago, cryptographers studied the general problem of multi-party secure computation, where Alice and Bob want to jointly perform some computation on their data, but without revealing their own data to each other. Coin flipping is just one instance of this paradigm. Cryptographers have shown a very strong result: essentially every task of this form can be done securely. However, again these protocols suffer from an unavoidable fairness problem: one party learns the result of the computation before the other, and can terminate the protocol early and prevent the other from learning the output. One especially exciting aspect of this paper is that it suggests a direction for achieving fairness for general multiparty secure computation, if the parties are willing to use Bitcoin. Who would have predicted Bitcoin could have such implications for secure distributed computation?
The Digital Library is published by the Association for Computing Machinery. Copyright © 2016 ACM, Inc.
No entries found