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.