9
$\begingroup$

I am developing a network where potentially many many nodes (billions, in principle?) should be able to agree on a random number. I would really prefer to avoid $O(N^2)$ procedures where everyone contributes with some randomness and then everything is shuffled together. So I am looking for a random beacon.

I would also prefer to avoid random beacons generated from $O(N^2)$ sources, like Bitcoin. So I wonder: is there a random beacon that is:

  • Unpredictable
  • Universally verifiable
  • Impossible to pilot (i.e., no organization, no matter how powerful, could alter its values or predict them)

I don't really care about its bitrate (if it produces just a few random bits per hour, so be it).

Here are some solutions I thought about (but they don't seem very feasible):

  • Solar flares: their occurrence is random, and they interfere with VLF communications. But their time is not so narrowly defined, and their occurrence is really rare, in then order of once a week. Also this requires everyone to have an antenna. And maybe an attacker might interfere itself with VLF transmitters.
  • Lightnings: they strike much more often, but their signal can be detected (also with VLF antennas) only maybe a few thousands kilometers from the lightning. So it wouldn't be global.
  • Earthquakes: detectable everywhere, but again, not such a precise time definition, and requires a very sophisticated instrumentation.
  • Random beacon satellite: we could send a cubesat in orbit to generate random numbers and broadcast them down to Earth. I could add proximity sensors or accelerometers so that any approach results in terminated communications to prevent tampering. This would also be great because I would only need a receiver station and then the numbers could be broadcasted via the Internet. But maybe a motivated enough organization could find a way to... I don't know, tamper with it so as alter its behavior? Even in space?
  • Same as above, but with an hidden verifier that knows the satellite seed and is able to check that the numbers are correct, and is always silent and undetectable. But then, how do I hide it? Without a human that can be tortured or whatever and disclose its position? Also this wouldn't protect the satellite from having its seed copied. And how would I go about maintenance for the hidden verifier?
  • One that might also work: VLF receivers tuned on encrypted shore-to-submarine transmissions of multiple nuclear powers. Transmissions can be received basically anywhere in the world, but being encrypted I guess they can be used as a more than decent source of randomness? Obviously a nuclear power could send gibberish to its submarines to make its beacon non-random, but if I use multiple sources then multiple nuclear powers should agree to at the same time jam their own communications with their nuclear submarines... while also letting every other nuclear power know about it, since they should coordinate! Quite unlikely. Might this work? But (sigh) it requires everyone to have a VLF antenna.

Here is where I stop. Any more sensible solution?

$\endgroup$
  • 4
    $\begingroup$ Using various global lottery results maybe a low effort way to implement something like this. They are widely published and easily available to check online from multiple sources. In many countries they are even heavily regulated to be both truly random and hard to influence. $\endgroup$ – Guut Boy Feb 21 '17 at 20:35
  • $\begingroup$ Maybe you can look into BLS signature scheme. Blockchain project called Dfinity is using it. Another project named Randao evaluated available random number generation models/options, and concluded that Dfinity's BLS mechanism is the best solution (they even go a step further and say it's ideal :)). Hope that can help you. $\endgroup$ – Mihailo Bjelic Jun 9 '18 at 20:22
2
$\begingroup$

There is no sensible solution to this. It is impossible, even if this was not a hypothetical question. It cannot be done for primarily two reasons:-

  1. You cannot have the nodes measure any analogue quantity. Analogue measurement noise will govern the accuracy of the reading. Coupled with the typical hash based randomness extractors, the avalanche effect will guarantee that every node will generate a different random number.

  2. So you're left with digital entropy acquisition. Lottery results are good but there's not a lot of them to get the few bits /hr (maybe just - you'd have to do the math). This was done for the Million Dollar elliptical curve. Much larger quantities of digital randomness can be obtained from international market information acquired via the appropriate APIs. This will gradually fail though. Spotty developers will change the access APIs every 18 months. The nodes will gradually lose access to the digital entropy. This gradual degradation of sources will affect the nodes no matter what sources they use. The API degradation issue would also affect the lottery technique. And. You can't update the nodes as that would put them under singular control breaking your initial premise.

The only kinda solution (breaking many requirements) is to use a distribution network sending out randomness like the NIST Randomness Beacon. But it would have to be under international /UN control and inspection and outside of US jurisdiction. It can't be NIST itself as that is a politically controlled arm of government (US Department of Commerce.) Or do the same for updating the nodes with new market access APIs. If the nodes were open hardware /open source based and not sealed, it would then be possible for hackers /scientists and journalists to verify their on going correct function. But that would then allow prediction of the random numbers as the entropy and algorithm would be known.

$\endgroup$
2
$\begingroup$

Thinking about this and considering Paul Uszak's very useful (albeit perhaps pessimistic) remarks, one idea to consider for this is to use measurements of randomly fluctuating natural phenomena of high public interest that are published regularly by multiple independent parties that have strong incentives to provide accurate measurements.

The key ideas to this choice are:

  • By using published figures we avoid the analog measurement problem that Paul mentions. All nodes observe the exact same values.
  • If the publishers have strong incentives to publish accurate values, that limits their latitude to manipulate the numbers. Maybe they can mess with less significant digits, but if they mess with the most significant ones they compromise their mission.
  • If the measurand itself fluctuates randomly, those most significant digits might provide useful entropy.
  • If many independent parties are measuring the same thing, the ability of a proper subset to influence the results is lessened.
  • If public interest is substantial and important enough, the data will be gathered and published for a long time and format changes would only be adopted slowly and conservatively.

One category of sources that I can think of is time and frequency standards data. For example:

All of these are critical to a number of navigational, scientific and engineering applications, as you can imagine.

$\endgroup$
  • $\begingroup$ randomly fluctuating natural phenomena of high public interest is just as good as market data. Absolutely. I'm not saying that it's unsuitable. The unsolvable problem is how to get that data into the nodes automatically? Published means on paper /radio /website. Unless a billion users are going to enter the Earth's angular velocity into their nodes to 12 decimal places every few hours, it has to be done automatically via an API. APIs change because developers drive change. Over months, the nodes will loose their access unless updated via a central authority. $\endgroup$ – Paul Uszak Feb 22 '17 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.