a protocol for selling secret information for Bitcoins. Imagine
Alice and Bob know a description of a set X containing some
valuable information. For example, X can contain some sensitive data that is hard to find (say: personal data signed by a
secret key of some public authority). Alice knows some subset
A of X and Bob knows a subset B of X. Their goal is to sell to
each other the elements of A ∪ B in such a way that they will
pay to each other only for the elements they did not know in
advance. In other words, Alice will pay to Bob (|B\ A| − |A\ B|)
B (if this value is negative, then Bob will pay to Alice its negation). Without the MPC techniques, it is not clear how to do
it: whenever Alice reveals to Bob some element a ∈ A, Bob can
always claim that he already knew a. Moreover, even if MPC
techniques are used, Alice has no way to force Bob to pay her
the money (and vice-versa). Our tools (developed in the subsequent papers mentioned in Section 1. 2) solve this problem:
we can design a protocol that transfers exactly the right sum
of Bitcoins, and moreover, this happens if and only if both
parties really learned the output of the computation!
The above example can be generalized in several different ways. For example, the output can go only to one party
(say: Alice), and the condition for the information that
Alice is willing to pay for can be much more complicated.
For example, Alice can be an intelligence agency that has a
special secret function g that specifies what is the value of a
given information (for some set of inputs g can even output
0). Then Bob can try to “sell” his information x to Alice setting some minimal value υ that it is worth according to him.
The protocol would compute g (x) and check if g (x) ≥ υ —if
yes, then Alice would learn x and pay υ to Bob, and otherwise
Alice would learn nothing (and Bob would earn 0).
Finally, let us remark that our protocols can potentially be
used for malicious purposes. For example, consider ransom-ware that encrypts the hard disk of the victim’s machine and
promises to provide a decryption key only if the victim pays a
ransom. Currently, such malicious programs have no way to
prove that they will really send the right key if the ransom is
payed. With our techniques, one can make delivery of this key
secure (in the sense that the payment happens only if the key
really decrypts the disk). Another potential risk is attacks on
online voting schemes: it is well-known that if these schemes
are not receipt-free, then the adversary can buy votes. Our
techniques can make such attacks easier, as they eliminate
the need of the vote seller to trust the vote buyer.
2. A SHORT DESCRIPTION OF BITCOIN
Bitcoin17 works as a peer-to-peer network in which the par-
ticipants jointly emulate a central server that controls the cor-
rectness of the transactions. In this sense, it is similar to the
concept of the MPC protocols. Recall that, as described above,
a fundamental problem with the traditional MPCs is that they
cannot provide fairness if there is no honest majority among
the participants, which is particularly difficult to guaran-
tee in the peer-to-peer networks where the sybil attacks are
possible. The Bitcoin system overcomes this problem in
the following way: the honest majority is defined in terms
of the “majority of computing power.” In other words, in
order to break the system, the adversary needs to control
machines whose total computing power is comparable with
needs to be N (N − 1) times the size of the bet, where N is
the number of players. For the two-party case, this simply
means that the deposit is twice the size of the bet.
The only cost that the participants need to pay in our protocols is Bitcoin transaction fees. Most Bitcoin transactions
are currently free. However, the participants of our protocols need to make a small number of nonstandard transactions (the so-called “strange transactions,” see Section 2),
for which there is usually some small fee (currently around
0.0001 B ≈ $0.04).b To keep the exposition simple, we present our results assuming that the fees are zero. For the sake
of simplicity, we also assume that the bets in the lotteries
are equal to 1 B. It should be straightforward to see how to
generalize our protocols to other values of the bets.
Our constructions are based on the coin-tossing protocol explained above. We managed to adapt this protocol to
our model, without the need to modify the current Bitcoin
system. We do not use any generic methods like MPC or
zero-knowledge compilers, and hence our protocols are
very efficient. The only cryptographic primitives that we use
are commitment schemes, implemented using hash functions (which are standard Bitcoin primitives). Our protocols rely strongly on the advanced features of the Bitcoin (in
particular, the so-called “transaction scripts,” and “
time-locks”). Because of the lack of space, we only sketch the formal security definitions. We executed our transactions on
the real Bitcoin. We provide a description of these transactions and a reference to them in the Bitcoin block chain.c
1. 2. Independent and subsequent work
Usage of Bitcoin to create a secure and fair two-player lottery
has been independently proposed by Back and Bentov.
provide a detailed comparison between their protocol and
ours in the extended version of this paper.
In the subsequent work,
1, 2 we show how to extend the ideas
from this paper to construct a fair two-party protocol for any
functionality, in such a way that the execution of this protocol has “financial consequences.” More precisely, in the
1 we show how to solve this problem under
the assumption that the Bitcoin transactions are nonmalleable (see Andrychowicz et al.
1, 2 for more on this notion),
and in Andrychowicz et al.,
2 we show how to modify the protocol from Andrychowicz et al.
1 to obtain a protocol that is
secure in the current version of Bitcoin. Some alternative
ideas for obtaining fairness in the multiparty protocols were
developed independently by Bentov and Kumaresan.
1. 3. Applications and future work
Although, as argued in the extended version of this paper, it
may actually make economic sense to use our protocols in
practice, we view gambling mostly as a motivating example for
introducing a concept that can be called “MPCs on Bitcoin,”
and which will hopefully have other applications. One example of a task that can be implemented using our techniques is
b We use “B”; for the Bitcoin currency symbol.
c For example the main transaction (Compute) of the three-party lottery is
available here: blockchain.info/tx/540d816bd57300209754dd36ffcec1d669-