Cryptographic Beacons (a.k.a. Randomness Beacons)

A cryptographic beacon (also known as a randomness beacon) is a service that provides a public source of randomness. The beacon continuously emits new random data (a beacon record) at a regular rate. If everybody agrees that there's no way to predict the next output from the beacon, it can be relied on as a provider of fair random values.

The random values emitted by the beacon can trivially be used for e.g. any public lottery, but cryptographers have also proposed many other interesting applications that require random values that cannot be predicted prior to being generated, but are made public after generation - these applications include contract signing, voting protocols, and zero-knowledge proofs. 

Cryptographic beacons should satisfy a few security properties, i.e. beacons must be: 
  • unpredictable: any adversary’s ability to predict any information about a beacon record prior to it being published is negligible.
  • unbiased: a beacon record is statistically close to a uniformly random string.
  • universally sampleable: after a beacon record is published, any party has unrestricted access to it.
  • universally verifiable: the source of randomness, that a beacon record is sampled from, can be verified to be unknown to any party prior to the time the beacon record is published.
Please note that the fact that a beacon is unpredictable also implies that it cannot be manipulated (as that would make it possible to predict its outcome with a non-negligible accuracy).

Unfortunately, no perfect way of implementing such a beacon has been devised yet; and current providers of public randomness, like NIST and Random.org, are trusted third-parties with good reasons to avoid. Recent research suggests that Bitcoin can be used to construct a decentralized, blockchain-based beacon with no trusted parties.

The NIST Randomness Beacon

The US National Institute of Standards and Technology (NIST) is implementing a source of public randomness. If you trust NIST, Heisenberg's uncertainty principle and other laws of physics, then this beacon should be truly unpredictable and random.

The service (at https://beacon.nist.gov/home) uses two independent commercially available sources of randomness, each with an independent hardware entropy source and SP 800-90-approved components.

The Beacon is designed to provide unpredictability, autonomy, and consistency. Unpredictability means that users cannot algorithmically predict bits before they are made available by the source. Autonomy means that the source is resistant to attempts by outside parties to alter the distribution of the random bits. Consistency means that a set of users can access the source in such a way that they are confident they all receive the same random string

The Beacon broadcasts full-entropy bit-strings in blocks of 512 bits every 60 seconds. Each such value is time-stamped and signed, and includes the hash of the previous value to chain the sequence of values together. This prevents all, even the source, from retroactively changing an output packet without being detected. The beacon keeps all output packets and makes them available online.

NIST Beacon Architecture

Please refer to the official NIST Randomness Beacon page for a detailed description.


References
Bonneau, Joseph et al . (2015), "On Bitcoin as a public randomness source", Cryptology ePrint Archive, Report 2015/1015

Clark, Jeremy et al (2010), "On the Use of Financial Data as a Random Beacon", Cryptology ePrint Archive, Report 2010/361

Fischer, Michael J. et al. (2011), "A Public Randomness Service", Proceedings of the International Conference on Security and Cryptography (SECRYPT 2011), 434-438   

Narayanan, Arvind et al. (2016), Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction, Princeton University Press

Rabin, Michael O. (1983), "Transaction Protection by Beacons", Journal of Computer and System Sciences, 27 (2): 256-267