Bob Bets With Alice For One Million, But They Don’t Trust Anyone To Toss The Coin
Living in a world without trust
Bob bets one million on the toss of a coin with Alice. “But, who will we get to toss the coin?”, says Bob. “Well. I don’t trust you!”, says Alice, and Bob says that he doesn’t trust her. And so they draw-up a list of people who could toss the coin, but cannot agree on anyone. So let’s look at a method that allows Bob and Alice to toss a coin, and then they both compute the result of the toss, and without any of them gaining an unfair advantage.
First Alice creates a random number (a), and Bob does the same (b). Next Alice calculates a hash of the value and computes A. Bob does the same and computes B. Next they exchange values. Once they acknowledge that they have received them, they then send each other their random values. The result of the coin toss will be the least significant bit of each of the values, EX-OR’ed together:
In this case Bob and Alice can’t change their values, as they have sent the hash of the values. Alice will prove the b value against the hash that Bob provided, and Bob will check the value of the a value against…