Fair Random Number Generation for Trustless Peers

This is a obvious technique and merely an application of one way cryptographic functions.


Suppose players in a peer network wish to participate in a game of chance. The primary object is high quality random binary numbers. However in a network without server authority, no single peer can be trusted to create these random values.


The first solution that comes to mind is to have each peer submit a random number and to xor these values together to form the final random value.  This would be a valid procedure only if the data was guaranteed to be in flight along the wire.

Rf =   R1 ^ R2 ^ R3 ^ ...  Ri =  ⦻ Ri 

However the nature of modern networks prevents us from practically knowing if the data is really on the wire. This is due to to the unknown real symmetry of the underlying network latency. (network latency can always be artificially increased and made asymmetric)

What we need is a method of commitment to a chosen random value prior to revealing its value. Cryptographic functions can perform this task.

Method

First we gather salt for the hashes by requesting a client Nonce for each peer.
🖧 ⟲  N1 , N2 , N3 , N4 ... , Ni          sharing a single nonce value from each peer to each other peer 


Now each peer generates a random number Ri  and build a signature value via a cryptographic one way function 𝓕.

Si = 𝓕(  Ri ,   N1 , N2 , N3 , N4 ... , Ni )       signature hash is created with random R in combination with  all nonce values  

🖧 ⟲ Si                   share signature hash values from all peers to all peers

Once all signatures have been shared the original random values can now be shared and the final random value can be computed.

🖧 ⟲ Ri                                                          share original random R from each peer to each other peer
Rf =   R1 ^ R2 ^ R3 ^ ...  Ri =  ⦻ Ri         final random value is computed by xor-ing all peer R values

Committed values of Ri can now be verified against Si by all peers.

Discussion

• Suggestion for one way function 𝓕 is SHA3.  It is current computationally infeasible to find collisions and this makes it virtually impossible to determine R from S or to change R for a given S.
• Xor-ing a random from each peers ensures that if at most one peer actually uses a random value then the final value will contain appropriate entropy.

Example

Peers p1 and p2

N1 = 0x12345678

N2 = 0x9ABCDEF0

Ni  shared.

R1 = 0x11111111    generated by peer 1

R2 = 0x22222222  generated by peer 2

S1 = sha1( R1 , N1 , N2 ) = b4853b44cbb378db14608716c1dd415536b40cf5
S1 = sha1( R2 , N1 , N2 ) = f29c5b7cedf5bd8f5eaded280c3b2586a4071aa0
Si  shared.

Ri  shared.
Rf = 0x11111111 ^ 0x22222222  =    0x33333333
Si  can be verified.