DOI: 10.1145/2898429
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 multi-party secure computation, if the parties are willing to use Bitcoin. Who
would have predicted Bitcoin could
have such implications for secure
distributed computation?
David Wagner is a professor of computer science at the
University of California, Berkeley.
Copyright held by author.
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.
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
Technical Perspective
Fairness and
the Coin Flip
By David Wagner
To view the accompanying paper,
visit doi.acm.org/10.1145/2896386
The following
paper introduces
an exciting new
idea for how to
provide fairness:
leverage
Bitcoin’s existing
infrastructure
for distributed
consensus.