How Do We Flip A Billion Coins in a Fair Way and Writing Your Name in Crypto?

So let’s say we have one billion people who are in a competition. We have a single toss of the coin, and if you match it, you continue. If…

How Do We Flip A Billion Coins in a Fair Way and Writing Your Name in Crypto?

So let’s say we have one billion people who are in a competition. We have a single toss of the coin, and if you match it, you continue. If not it does not match, then you are out of the competition. How many tosses will it take to get a winner (on average)?

It think it would only take … 30 rounds (I asked someone early and they said one trillion!).

So from one billion people, we would have 30 tosses of the coin, and we would (on average) have a winner. Do you agree with me?

Fast random numbers

So how are we going to build a computer that is going to create one billion random numbers quickly. Well, in 2016, Xoroshiro128+ came along, and has sub-nano-second times for each random number generated. We could thus generate one billion random numbers in less than a second. But how do we just to a bit flip? Well we just mask of the least significant bit.

So let’s take two seed values, and generate the first 10 random values and the first 50 tosses:

import sys
val1=54253124354024L
val2=5395042653908L

def bin2chr(data):
result = ''

while data:
char = data & 0xff
result += chr(char)
data >>= 8

return result

class Xoroshiro128Plus(object):
def __init__(self, seed):
self.seed = seed

@staticmethod
def rotl(x, k):
return ((x << k) & 0xffffffffffffffff) | (x >> 64 - k)

def next(self):
s0 = self.seed[0]
s1 = self.seed[1]
		result = (s0 + s1) & 0xffffffffffffffff

s1 ^= s0
		self.seed[0] = self.rotl(s0, 55) ^ s1 ^ ((s1 << 14) & 0xffffffffffffffff)
self.seed[1] = self.rotl(s1, 36)

return result
print "Seed 1:\t",val1
print "Seed 2:\t",val2
print
generator = Xoroshiro128Plus([val1, val2]) 
for i in range(4):
val=generator.next()
print hex(val),'\t',
print(repr(bin2chr(val)))

The run gives:

Seed 1:    54253124354024
Seed 2: 5395042653908
0 0x363febce56bcL         '\xbcV\xce\xeb?6'
1 0xb44a630c2a0b0f01L '\x01\x0f\x0b*\x0ccJ\xb4'
2 0x35b971bef18473e6L '\xe6s\x84\xf1\xbeq\xb95'
3 0x9497b673f320d89bL '\x9b\xd8 \xf3s\xb6\x97\x94'
4 0xd07401ef48e22e0L '\xe0"\x8e\xf4\x1e@\x07\r'
5 0xdcc0618d77a1ce2bL '+\xce\xa1w\x8da\xc0\xdc'
6 0xd719917970062c09L '\t,\x06py\x91\x19\xd7'
7 0xacd2ed2c5461b336L '6\xb3aT,\xed\xd2\xac'
8 0xc619e5ac2efae9e7L '\xe7\xe9\xfa.\xac\xe5\x19\xc6'
9 0x4bfbdf8610735319L '\x19Ss\x10\x86\xdf\xfbK'
Coin flip (60)
H T H T H T T H T T T T T H T T H H H H H T T H T H T T T H T T T H T T H H H T H T H T H T T T H T T T H T H T H H T H
Heads: 26
Tails:    34

We can see we have 26 heads and 34 tails, which isn’t 50/50, but it will start to tend to a 50/50 split once we have enough tosses. Sample run here:

In the following code we take the random numbers and then mask of the least significant bit and define it as a “Head” or a “Tail”:

import sys
val1=54253124354024L
val2=5395042653908L
if (len(sys.argv)>1):
val1=int(sys.argv[1])
if (len(sys.argv)>2):
val2=int(sys.argv[2])
def bin2chr(data):
result = ''

while data:
char = data & 0xff
result += chr(char)
data >>= 8

return result

class Xoroshiro128Plus(object):
def __init__(self, seed):
self.seed = seed

@staticmethod
def rotl(x, k):
return ((x << k) & 0xffffffffffffffff) | (x >> 64 - k)

def next(self):
s0 = self.seed[0]
s1 = self.seed[1]
		result = (s0 + s1) & 0xffffffffffffffff

s1 ^= s0
		self.seed[0] = self.rotl(s0, 55) ^ s1 ^ ((s1 << 14) & 0xffffffffffffffff)
self.seed[1] = self.rotl(s1, 36)

return result
print "Seed 1:\t",val1
print "Seed 2:\t",val2
print
generator = Xoroshiro128Plus([val1, val2]) 
for i in range(10):
val=generator.next()
print i,hex(val),'\t',
print(repr(bin2chr(val)))
print '\nCoin flip'
generator = Xoroshiro128Plus([val1, val2])
count=0
for i in range(50):
val=generator.next()
bit = val & 0x1
if (bit==0):
count = count+1
print "H",
else:
print "T",
print 
print 'Heads:\t',count
print 'Tails:\t',50-count

Writing your name in crypto

And while we are using Xoroshiro128+, let’s have a bit of fun. Did you known than you can actually hack the random number generator to show my name (Try):

Seed 1: 11000710321405755819
Seed 2: 15528335171484875594
0 0x702a1a51a1ec7cf5L ‘\xf5|\xec\xa1Q\x1a*p’
1 0x7562206c6c6962L ‘bill bu’
2 0x6d206e616e616863L ‘chanan m’

3 0x5d92516ca1be5e56L ‘V^\xbe\xa1lQ\x92]’
4 0x26028de6210a115aL ‘Z\x11\n!\xe6\x8d\x02&’
5 0x6e2e21263ba96777L ‘wg\xa9;&!.n’
6 0x14104cb7e79dc043L ‘C\xc0\x9d\xe7\xb7L\x10\x14’
7 0x6b137d1ba15b5528L ‘(U[\xa1\x1b}\x13k’
8 0xab954c20376230cdL ‘\xcd0b7 L\x95\xab’
9 0xe5cce6246f6c38eL ‘\x8e\xc3\xf6Fb\xce\\\x0e’
Coin flip (60)
T H T H H T T H T H H T H H H T H H T T H H T H H H H T H T H T T T T H H H T T H H H T H H H H H H H T H T T H H H H H
Heads: 38
Tails: 22

How did I do that? Can you work out how to write your own name?

Conclusions

A billion people … and 30 rounds … and we have a winner. True or false?

Can you write your name in crypto too?