[Back] We can create a fair coin flip between Bob and Alice where there is no trusted third party:
A fair coin toss
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 the draw-up a list of people who could toss, the coin, and 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.
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 the exchange values. Once the 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 the hash that Alice sent. The following is a sample run:
===Bob random and hash===== Bob random= 369 Bob hash= ae2810e1e85383a19f8433a73bad300cecb7047023a47d5adcb607891417fae4:b0f1919bec594f7095d79b533682462b ===Alice random and hash===== Alice random= 835 Alice hash= 1c47f2ee558f83bcaadde316b35fc9b17d8e87fb1e55705689865ab4758e8083:b2c22fc9ac404387a30b44c1909a6bee Heads ====Checking the flips ==== Alice checks value with salt: True Bob checks value with salt: True ====10 random flips==== Tails Tails Heads Heads Tails Heads Tails Heads Tails Tails
An outline of the code is here:
import sys import uuid import hashlib import random def hash_password(password): salt = uuid.uuid4().hex return hashlib.sha256(salt.encode() + password.encode()).hexdigest() + ':' + salt def check_password(hashed_password, user_password): password, salt = hashed_password.split(':') return password == hashlib.sha256(salt.encode() + user_password.encode()).hexdigest() bob=random.randint(1, 1000) hash_bob = hash_password(str(bob)) alice=random.randint(1, 1000) hash_alice = hash_password(str(alice)) print '\n===Bob random and hash=====\n' print 'Bob random=',bob print 'Bob hash=',hash_bob print '\n===Alice random and hash=====\n' print 'Alice random=',alice print 'Alice hash=',hash_alice coin=(bob & 0x1) ^ (alice & 0x1) if (coin==0): print 'Heads ', else: print 'Tails ', print '\n====Checking the flips ====\n' print 'Alice checks value with salt: ',check_password(hash_bob,str(bob)) print 'Bob checks value with salt: ',check_password(hash_alice,str(alice)) print '\n====10 random flips====\n' for i in range(1,10): bob=random.randint(1, 1000) hash_bob = hash_password(str(bob)) alice=random.randint(1, 1000) hash_alice = hash_password(str(alice)) coin=(bob & 0x1) ^ (alice & 0x1) if (coin==0): print 'Heads ', else: print 'Tails ',
We increasingly live in a world where we do not trust anything, and so this method allows us to generate the result of a computation without requiring a trusted agent to perform the calculation. It is a world without the need for Trent. This is defined more formally as secure multi-party computation and can be used in secure elections to compute a result. It could also be used for a bidding system, where the winner of a bid could be revealed to those involved in the bid, but not to others.