78 COMMUNICATIONS OF THE ACM | APRIL 2016 | VOL. 59 | NO. 4
replacement for the traditional gambling sites. An additional
benefit would be a reduced cost of gambling since gambling
sites typically charge fees for their service.
In our opinion, there are at least two main reasons why
MPCs are not used for online gambling. The first reason is
that multiparty protocols do not provide fairness in case there
is no honest majority among the participants. Consider, for
example, a simple two-party lottery based on the coin-tossing
protocol: the parties first compute a random bit b, if b = 0,
then Alice pays $1 to Bob, if b = 1, then Bob pays $1 to Alice,
and if the protocol did not terminate correctly, then the parties do not pay any money to each other. In this case, a malicious party, say Alice, could prevent Bob from learning the
output if it is equal to 0, making 1 the only possible output
of a protocol. This means that two-party coin tossing is not
secure in practice. More generally, multiparty coin tossing
would work only if the majority is honest, which is not a realistic assumption in the fully distributed Internet environment, for instance, sybil attacks11 allow one malicious party
to create and control several “fake” identities, easily obtaining the “majority” among the participants.
The second reason is even more fundamental, as it comes
directly from the inherent limitations of the MPC security
definition: such protocols take care only of the security of the
computation and are not “responsible” for ensuring that the
users provide the “real” input to the protocol and that they
respect the output.
Consider, for example, the marriage proposal problem:
it is clear that there is no technological way to ensure that
the users honestly provide their input to the trusted party.
Nothing prevents one party, say Bob, from lying about his feelings and setting b = 1 to learn Alice’s input a. Similarly, forcing both parties to respect the outcome of the protocol and
indeed marry cannot be guaranteed in a cryptographic way.
This problem is especially important in the gambling
applications: even in the simplest “two-party lottery” example described above, there exists no cryptographic method
to force the loser to transfer the money to the winner.
One pragmatic solution to this problem, both in the digital
and the nondigital world, is to use the concept of “reputation”:
a party caught cheating (i.e., providing the wrong input or not
respecting the outcome of the game) damages her reputation
and next time may have trouble finding another party willing
to gamble with her. Reputation systems have been constructed
and analyzed in several papers.
19 However, they seem too cumbersome to use in many applications, one reason being that
it is unclear how to define the reputation of new users if users
are allowed to pick new names whenever they want.
12
Another option is to exploit the fact that the financial
transactions are done electronically. One could try to “
incorporate” the final transaction (transferring $1 from the loser
to the winner) into the protocol, in such a way that the parties
learn who won the game only when the transaction has already
been performed. It is unfortunately not obvious how to do it
within the framework of the existing electronic cash systems.
Obviously, since the parties do not trust each other, we can-
not accept solutions where the winning party learns the credit
card number or the account password of the loser. One pos-
sible solution would be to design a multiparty protocol that
simulates, in a secure way, a simultaneous access to all the
online accounts of the participants and executes a wire trans-
fers in their name. Even if theoretically possible, this solution
is very hard to implement in real life, especially since the pro-
tocol would need to be adapted to several banks used by the
players (and would need to be updated whenever they change).
The main contribution of this paper is the introduction of
a new paradigm, which we call “MPC protocols on Bitcoin,”
that provides a solution to both of the problems described
above: the lack of fairness and the lack of the link between
“real life” and the result of the cryptographic computation.
We describe our solution in Section 1. 1.
1. 1. Our contribution
We study how to do “MPCs on Bitcoin.” First of all, we show
that the Bitcoin system provides an attractive way to construct
a version of “timed commitments,”
8, 13 where the committer
has to reveal his secret within a certain time frame or pay a
fine. This, in turn, can be used to obtain fairness in certain
multiparty protocols. Hence, it can be viewed as an “applica-
tion of Bitcoin to MPCs.”
What is probably more interesting is our second idea,
which in some sense inverts the previous one by showing
an “application of the MPCs to Bitcoin,” namely we intro-
duce a concept of multiparty protocols that work directly
on Bitcoin. As explained above, the standard definition of
MPCs guarantees only that the protocol performs the com-
putation securely, but ensuring that the inputs are correct
and the parties do not interrupt the protocol execution is
beyond the scope of the security definition. Our observation
is that the Bitcoin system can be used to go beyond this
standard definition, by constructing protocols that link the
inputs and the outputs with real Bitcoin transactions. This is
possible since the Bitcoin lacks a central authority, the list of
transactions is public, and its syntax allows more advanced
transactions than simply transferring the money.
As an instantiation of this idea, we construct protocols for
secure multiparty lottery using the Bitcoin currency, without
relying on a trusted authority. By “lottery,” we mean a protocol
in which a group of parties initially invests some money, and
at the end, one of them, chosen randomly, gets all the invested
money (called the pot). Our protocol works in purely peer-to-peer environment and can be executed between players who
are anonymous and do not trust each other. Our constructions
come with a very strong security guarantee: no matter how
the dishonest parties behave, the honest parties will never get
cheated. More precisely, each honest party can be sure that,
once the game starts, it will always terminate and will be fair.
Our main construction is presented in Section 4. Its
security is obtained via deposits: each user is required to
initially put aside a certain amount of money, which will
be paid back to her once she completes the protocol honestly. Otherwise, the deposit is given to the other parties and
“compensates” them for the fact that the game terminated
prematurely. This protocol uses the timed commitment
scheme described above. A drawback of this protocol is that
the deposits need to be relatively large, especially if the
protocol is executed among larger groups of players. More
precisely, to achieve security the deposit of each player