Communications of the ACM

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))