5
$\begingroup$

Alice and Bob want to play a coin flipping game. Alice wins if the coin flips head.

They choose to trust a independent third party that generates a random beacon (such as NIST). There is no communication only before the random beacon is generated. After it is generated, there may be communication.

Alice has a message known only to her. The result is the first bit of hash(message, beacon).

  1. Alice and Bob may not be able to communicate before the random beacon is generated.
  2. The result can't be changed when at least one person knows the result.

With (2) we avoid the situation where Alice reads the random beacon then changes the message to yield a different result that favors her.

One solution may be having the message hash timestamped by another third party (not the one of the random beacon) to a time before the random beacon is generated. Alice then can't change the message retroactively. I see two problems with this solution:

  • Alice may generate several messages and timestamp them before the random beacon is generated. Then, after the random beacon is generated, she can choose the message that yield the result that favors her.

  • How can we prove that the timestamp was generated before the random beacon?

Is there a crypto solution to this problem? Is this a common and studied problem in cryptography, please can you point me to some literature that describes and solves this problem?

$\endgroup$
  • 2
    $\begingroup$ Alice and Bob must have come to a prior agreement of some kind. What's wrong with: the outcome is the first bit radioed by the beacon after a certain time ? (With time as radioed by the beacon; if the beacon does not embed a time signal, we can use: the first bit after such UTC date and the beacon has radioed a series of $n$ consecutive zeroes, where $n$ makes it unlikely that there is disagreement). $\endgroup$ – fgrieu Oct 28 '15 at 7:34
  • 1
    $\begingroup$ Thanks @fgrieu. It is part of the problem that Alice's message influences the result somehow. That is, for two pair of Alices and Bobs using the same random beacon, the two results may not be the same. $\endgroup$ – Victor Oct 28 '15 at 14:10
  • 1
    $\begingroup$ So why does the coin flip have to depend on the beacon in the first place? If Alice and Bob can communicate when they decide who wins, they can just use normal secure coin flipping protocol. $\endgroup$ – otus Oct 28 '15 at 18:40
2
$\begingroup$

As fgrieu pointed out, Alice and Bob must have somehow come to some kind of agreement before the random beacon is generated. Would either of these techniques work for you?

use the random beacon directly

They could agree ahead of time that "Alice wins if the first random bit sent by the NIST Randomness Beacon on 2015-11-02 at 11:59 is a 0, and Bob wins if that bit is a 1."

Randomness beacons allow a person to prove that the random number (or any hash value calculated from it) was generated after some particular time.

use Alice's message with trusted timestamping

There are ways of doing trusted timestamping to prove that Alice knew a message before some particular time.

They could agree ahead of time that "After Alice commits to a single message by including that message in the Bitcoin blockchain as part of a transaction sending a tiny amount of bitcoin from Alice to Bob sometime during the day of 2015-11-01, and then later the NIST Randomness Beacon on 2015-11-02 at 11:59 generates some random data, Alice wins if the first bit of hash(message, beacon) is a 0, and otherwise Bob wins."

(If the message is long, it would be better to store only the hash of that message in the blockchain as a commitment to that message).

There is no direct communication from Alice to Bob or from Bob to Alice before the beacon transmission, although this particular system requires some two-way communication between Alice and the Bitcoin system before the beacon transmission.

Alice may generate several messages and timestamp them before the random beacon is generated. Then, after the random beacon is generated, she can choose the message that yield the result that favors her.

With this system, after the beacon transmission, Bob can fairly easily inspect the Bitcoin blockchain for that day and see if Alice tried to cheat by sending small amounts of bitcoins to him over several transactions that day, each transaction with the hash of a different message. (Bob could inspect that blockchain even before the beacon transmission, although you could argue that would count as a message from Alice to Bob before the beacon transmission).

How can we prove that the timestamp was generated before the random beacon?

That is a hard problem, but that is the problem that Bitcoin was designed to solve.

$\endgroup$
  • $\begingroup$ Thank you! One could also use the block hash as the random beacon. $\endgroup$ – Victor Oct 28 '15 at 19:56
  • 1
    $\begingroup$ @Victor: You are right. As often happens to all programmers, I have a first part of something that solves part of the problem, and then I add a second part that solves the rest of the problem; and later I realize that this second part can be used to solve the entire problem and I don't need the first part any more. $\endgroup$ – David Cary Oct 29 '15 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.