DOI: 10.1145/2896386

Secure Multiparty Computations
on Bitcoin

By Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, and Łukasz Mazurek

Abstract

Is it possible to design an online protocol for playing a lottery, in a completely decentralized way, that is, without relying on a trusted third party? Or can one construct a fully decentralized protocol for selling secret information, so that neither the seller nor the buyer can cheat in it? Until recently, it seemed that every online protocol that has financial consequences for the participants needs to rely on some sort of a trusted server that ensures that the money is transferred between them. In this work, we propose to use Bitcoin (a digital currency, introduced in 2008) to design such fully decentralized protocols that are secure even if no trusted third party is available. As an instantiation of this idea, we construct protocols for secure multiparty lotteries using the Bitcoin currency, without relying on a trusted authority. Our protocols guarantee fairness for the honest parties no matter how the loser behaves. For example, if one party interrupts the protocol, then her money is transferred to the honest participants. Our protocols are practical (to demonstrate it, we performed their transactions in the actual Bitcoin system) and in principle could be used in real life as a replacement for the online gambling sites.

1. INTRODUCTION

One of the most attractive features of the Internet is its decentralization: the TCP/IP protocol itself, and several other protocols running on top of it do not rely on a single server, and often can be executed between parties that do not need to trust each other, or even do not need to know each other’s true identity. Examples of such protocols include: the SMTP and the HTTP protocols, the peer-to-peer content distributions platforms, messaging systems, and many others. A natural question to ask is how far can the “ decentralization” of the digital world go? In other words, what are the real-life applications which one can implement on the Internet without the need of a trusted third party? Until recently, one notable example of a task that seemed to always require some sort of a “trusted server” was the online financial transactions (that had to rely on a bank or a credit card company). This situation changed radically in 2009 when the first fully decentralized digital currency, called Bitcoin, was deployed by Nakamoto. 17, a The huge success of Bitcoin (its current market capitalization is around $5 billion) is due precisely to its distributed nature and the lack of a central authority that controls Bitcoin transactions. We describe Bitcoin in more detail in Section 2.

The fact that Bitcoin money transfers can be done without a trusted server raises another intriguing question, namely, can we “decentralize” the financial system even further, that is, can we implement some more advanced financial instruments in a distributed manner? The Bitcoin specification partly answers this question, by providing the so-called “nonstandard transactions.” We describe this feature in more detail in Section 2, but for a moment, let us only say that Bitcoin allows the parties to specify more complex conditions about when the money can be spent. This, in turn, permits them to create the so-called “Bitcoin contracts,” which are forms of agreements whose execution is later enforced by the Bitcoin system itself (without the need of a trusted third party). Examples of such contracts include rapidly adjusted micropayments, assurance contracts, and dispute mediation (see https://en.bitcoin.it/wiki/Contracts for more on this).

Probably, one of the most advanced types of multiparty protocols that can be performed digitally are the cryptographic “secure multiparty computation (MPC)” protocols, originating from the seminal works of Yao20 and Goldreich et al. 14 Informally, such protocols allow a group of mutually distrusting parties to compute a joint function f on their private inputs. For example, for two parties, Alice and Bob, Alice has an input x, Bob has an input y, and they both want to learn f (x, y), but without Alice learning y or Bob learning x. In this paper, we initiate the study of using Bitcoin to perform MPC protocols.

The coin-tossing protocol. A very simple example of such
a protocol is the coin-tossing problem, 6 executed between two
parties, Alice and Bob, who want to jointly compute a bit b
that is equally likely to be 0 or 1. In other words, they want to
compute a randomized function frnd : {⊥} × {⊥} → {0, 1} that
takes no inputs and outputs as a uniformly random bit. This
protocol can be implemented using an idea similar to the rock-
paper-scissors game: Alice sends a bit bA to Bob, and simultane-
ously Bob sends a bit bB to Alice. The output b is computed
A longer version of this paper appeared on the IEEE
Symposium on Security and Privacy 2014. An extended
version of it is also available on the Cryptology Eprint
Archive eprint.iacr.org/2013/784. This work was sup-
ported by the WELCOME/2010-4/2 grant founded within
the framework of the EU Innovative Economy (National
Cohesion Strategy) Operational Programme. Łukasz
Mazurek is a recipient of the Google Europe Fellowship
in Security, and this research is supported in part by this

Google Fellowship. a This name is widely believed to be a pseudonym.