Ask HN: Can anyone suggest a decentralized way to agree on a random number?
In this scenario each peer might be connected to, say, 20 others with a "small world" network topology - where most (but not all) of a peer's connections are to nearby peers.
I know it can be done on a small scale if every peer selects a random number, and then broadcasts a cryptographic hash of that number to all other peers - thus "committing" to it. The peers would then broadcast their actual random numbers which can be verified against the hashes and then combined using xor to get the global random number.
With this algorithm no subset of peers could manipulate the result because even just one honest peer will randomize the global value, due to the xor step.
Unfortunately this won't work in my scenario because it won't scale beyond a relatively small network.
A possible solution I've considered is more easily explained if we first simplify the problem to the peer network collectively choosing a single random bit.
Each peer chooses their own random value, 0 or 1, and broadcasts it to its neighbors. Each peer then looks at whether the majority of neighbors have selected 1 or 0 and changes their bit to that value.
The process is then repeated iteratively until the entire network converges to 1 or 0, my hope is that this would occur in time proportional to log(n) where n is the network size - due to the network's small world topology.
This algorithm can then be extended to larger numbers involving multiple bits.
While a substantial subset of peers could influence the final result (making it less secure than the small-scale algorithm), my hope is that it would require considerable resources to do this, making it impractical.
I'm interested in whether anyone can recommend a better approach.
4 comments
[ 3.1 ms ] story [ 24.0 ms ] thread2. all random numbers are XOR'ed together.
The result is as random as the most random number provided. XOR can be done in any order and any combination and it produces the same result. Complexity is log(n) XOR operations. No need for everyone to be connected to each other
That's fairly similar to the first algorithm I described except without the initial hash commit step, but I think it shares the same problem which is that I don't see how it could scale up to tens of thousands of peers, with peers constantly leaving and joining the network.
If you want every node over some time period participating, you can't do faster than than log2(n) XOR operations.
(in above comment I said O(n) xor's, that's obviously wrong. You need only log(N) xor's)
In this example, if any of ‘everyone’ can see all the other n-bit random numbers before broadcasting their n-bit number, that party had complete control over the result of step 2.
One way to solve that is by appointing a party P to do step 2, have all parties communicate their number to P in private, and then have P do the XOR.
Problem with that is that you have to trust party P. Even if you require it to not only report the result of step 2, but also all the numbers generated in step 1, P can collude with one of them to generate any result those two parties want to generate, and all parties can claim they didn’t send P the number P says they sent him if they’re not happy with the result of step 2.
A better approach:
- each party picks a random encryption key
- each party encrypts their n-bit number with that key
- each party broadcasts the encrypted number to the world
- once a party knows that all parties have seen all encrypted numbers (how to know that is left as an exercise for the reader), it broadcasts its encryption key.
- eventually, all parties will have seen all encryption keys.
- once a party has all encryption keys, it can decrypt the encrypted n-bit numbers and XOR the results.
Even ignoring the exercise for the reader, the above likely has holes. I’m not an expert in this field.
https://en.wikipedia.org/wiki/Byzantine_fault probably is a better starting point for this kind of problem (but doesn’t give a solution to this specific problem)