Is there some way to generate a non-predictable random number in a decentralised network?

Question

Is there a way to generate a random number with given restrictions:

• It will be used in a decentralised network with a big number of peers (no central authority to generate it)
• Its generation should not rely on any third-party service (for example, going to a specific website)
• Its generation is triggered by a semi-random data being sent through the network, and it should relate to the data
• The computer sending the data should not have an advantage in determining the random number (for example, computing some number that would have a really high chance of becoming the seeked number)

I was thinking of using a random number like that to counter a 51% attack against the Bitcoin network. The main problem there is that an attacker with a lot of computation power can compute a couple "blocks" in advance and only release them to counter "blocks" generated by legitimate users. I figured a way to counter that would be by requiring generation of some random number that couldn't be pre-computed in advance, but only when a block is sent through the network. Required use of that number would then invalidate blocks that are precomputed beforehand, preventing the attack.

So, is there a way to generate a random number like that described above?

Answer 1

A service that provides such numbers is called a random beacon.

Since everyone has to agree on what a beacon's value is and peers may not have a complete view of the network, it is very difficult to construct a universally verifiable value using only internal network data. Since data only becomes canonical when it is included in a block (a block that is accepted by everyone else), I'm not sure what else could be used.

If you relax the internal-only constraint and allow external beacons, you will hopefully be able to use NIST's beacon service. You can also construct values with financial data however this only works when markets are open.

Answer 2

The classic way to do this is to have all parties commit to individual random values by publishing a secure hash of a suitably random-nonce-padded number. Once the commitments have been distributed, the parties open the commitments by publishing the nonce and the number. The numbers are combined in some previously agreed suitable fashion such as adding them modulo some number or xoring them together. As long as your value was included then you are confident that the result is random. If the numbers used are large enough, the nonce is not required.

Answer 3

count the bits in some organic white noise -- like an overloaded diode -- in an interval. There was a start-up in the late nineties that successfully got investors to fund a random number generation rig involving pointing video cameras at lava lamps. Sounded as much like a joke at the time as it does now.