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