APRIL 2016 | VOL. 59 | NO. 4 | COMMUNICATIONS OF THE ACM 83
executes the CS protocol acting as the committer, and Alice
being the receiver, and the corresponding variables are sB and
hB. Once both commitment phases are executed successfully
(recall that this includes receiving by each party the signed
PayDeposit transaction), the parties proceed to the next steps,
which are exactly as before: first, each of them broadcasts an
input transaction. Once these transactions are confirmed,
they create the Compute transaction in the same way as before,
and once it appears on the block chain, they open the commitments. The only difference is that, since they used the CS commitment scheme, they can now “punish” the other party if she
did not open her commitment by the time t and claim their deposit. On the other hand, each honest party is always guaranteed to get her deposit back, hence she does not risk anything
by investing this money at the beginning of the protocol. The
graph of transactions in this protocol is presented in Figure 2.
We also need to comment about the choice of the parameters: t: the time when deposit become available to the receiver
and d: the value of the deposit. Our protocol consists of four
“rounds” of transactions—in each round, parties wait for the
confirmation of all the transactions from this round before
proceeding to the next round. Thus, the correct execution of
the protocol always terminates within time 4 ⋅ Tmax, where Tmax
is the maximal time needed for a transaction to be confirmed.
Because of that we can safely set t to be the start time of the
protocol plus 5 ⋅ Tmax.
The parameter d should be chosen in such a way that it
will fully compensate to each party the fact that the other
player aborted. That means that for a two-player lottery, each
player should make a deposit equal to two stakes. This way if
one party aborts the protocol, then the other party may lose
her stake worth 1 B, but she gets a deposit of value 2 B, so as a
result of the protocol executions she earns 1 B, what is never
worse for her than executing the protocol to the very end.
The complete description of this protocol can be found in
the extended version of this paper, where we also show how to
generalize it to N parties. In our multiparty solution, the total
amount of money invested in the deposit by each player has
to be equal to N (N − 1) B. In real-life this would be ok probably
for small groups N = 2, 3, but not for the larger ones.
Acknowledgments
We would like to thank Iddo Bentov and Ranjit Kumaresan
for fruitful discussions and for pointing out an error in a
The output script of Compute is tricky. To make it evalu-
ate to true on body, one needs to provide as “witnesses” the
signature of a party P and strings xA, xB, where xA and xB are
the preimages of hA and hB (with respect to H). The collision-
resistance of H implies that xA and xB have to be equal to sA
and sB (resp.). Hence, it can be satisfied only if the winner
choosing function f evaluates to P on input (sA, sB ). Since only
party P knows her private key, only she can later provide a
signature that would make the output script evaluate to true.
Before Compute appears on the block chain, each party
P can “change her mind” and redeem her input transaction,
which would make the transaction Compute invalid. As we
said before, it is ok for us if one party interrupts the coin-tossing procedure as long as she had to decide about doing
it before she learned that she lost. Hence, Alice and Bob
wait until the transaction Compute becomes confirmed
before they proceed to the step in which the winner is
determined. This final step is simple: Alice and Bob just
broadcast sA and sB, respectively. Now: if f (sA, sB) = A, then
Alice can redeem the transaction Compute in a transaction
ClaimMoneyA constructed as:
ClaimMoneyA
in-script: strings sA and sB and A’s signature
out-script: can be spent only by A
On the other hand, Bob cannot redeem Compute, as the
condition f (sA, sB) = B evaluates to false. Symmetrically:
if f (sA, sB) = B, then only Bob can redeem Compute by an analogous transaction ClaimMoneyB.
This protocol is obviously correct. It may also look secure,
as it is essentially identical to Blum’s protocol described
before (with a hash function used as the commitment
scheme). Unfortunately, it suffers from the following problem: there is no way to guarantee that the parties always
reveal sA and sB. In particular: one party, say, Bob, can refuse
to send sB after he learned that he lost (i.e., that f (sA, sB) = A).
As his money is already “gone” (his input transaction has
already been redeemed in transaction Compute), he cannot
gain anything, but he might do it just because of sheer nastiness. Unfortunately, in a purely peer-to-peer environment,
with no concept of a “reputation,” such behavior can happen,
and there is no way to punish it. This is exactly why we need to
use the Bitcoin-based commitment scheme from Section 3.
The secure version of the scheme. The general idea behind
the SecureLottery protocol is that each party first commits
to her inputs, using the Bitcoin-based timed commitment
scheme, instead of the standard commitment scheme. Recall
that the CS protocol can be opened by sending a value s, and
this opening is verified by checking that s has required length
(either 128 or 129) and hashes to a value h sent by the committer in the commitment phase. So, Alice executes the CS protocol acting as the committer and Bob as a receiver. Let sA and hA
be the variables s and h created this way. Symmetrically, Bob
Compute
in-script1: A’s signature in-script2: B’s signature
out-script: can be spent using: ( 1) strings xA and xB of length
128 or 129 s.t. H(xA) = hA, H(xB) = hB and ( 2) X’s
signature where X is the winner (i.e., X = f(xA, xB))
ClaimMoneyA
in-script:
strings sA and sB
and A’s signature
in-script:
strings sA and sB
and B’s signature
out-script: can be
spent only by A
ClaimMoneyB
out-script: can be
spent only by B
1B 1B
2B
2B 2B
2B
Figure 2. The SecureLottery protocol.