Random UChile seeks to enhance computational services which are inherently random so any external observer can verify that the underlying algorithm was correctly executed, and no manipulation of the randomness used to produce the final outcome has occurred. Our approach can be used with a wide range of services from choosing which person pays a bill at the restaurant, up to which officials will be financially scrutinized by a government auditing agency.
Random UChile is a project developed by a team of researchers at the Laboratorio de Seguridad Computacional y Criptografía Aplicada (CLCERT), at the Faculty of Physical and Mathematical Sciences of the University of Chile.
The main service provided by Random UChile is the Randomness Beacon. The beacon generates “fresh” randomness every minute in the form of a 512-bit long random value (or “pulse”). All other services that Random UChile provides are related to the use of the random values generated by the Randomness Beacon.
The 512 bits randomness value is generated by an algorithm (detailed below) which provides a mathematical proof that no entity, not even Random UChile, can effectively manipulate or predict the random output before than 60 seconds in advance.
Every minute, we execute the same generation algorithm, which consists of the following phases:
Collection of External Entropy: during the first 30 seconds, a large collection of data is gathered from several sources, all of which are inherently random in nature. More precisely, for any of our sources, it is difficult to predict the exact data stream or output that the source will emit when sampled in that period. A classic mathematical metric the unpredictability of such sources is called entropy: the more difficult, the more entropy the source is said to have. All sources currently in used by Random UChile (which are detailed in the next section) must fulfill some requirements in order to qualify as a good entropy source: (1) the source must produce consistent data, meaning that it must output the same information to any observer accessing the source at the same time in any part of the world, (2) the source must belong to a trustworthy organization that one would not have any reason to suspect is corrupted and may be motivated to alter or bias the information produced by the source, (3) the source must be related to some phenomenon that is likely to produce some minimal amount of entropy on each output (or sample), (4) the source must deliver highly dynamic information, that is, the source must be able to produce mildly-correlated outputs often enough, and finally, (5) the source must be available most of the time.
Use of Local Entropy: after collecting data from the external sources, it is necessary to generate entropy locally. For that, we use our own TRNG (True Random Number Generator), a piece of hardware that produces random bits by relying on a quantum process on an electrical circuit. At every minute, the TRNG generates a 512 bit value. The TRNG value is stored and not used on the current computation but in the next minute’s computation. In consequence, at each computation, the value generated in the previous minute is used. To ensure a correct (and transparent) use of the value generated in the previous minute, the algorithm uses a cryptographic tool called a commitment which not only hides a value (the randomness generated at the previous minute), but also binds the beacon (or forces the beacon to commit to) such value, effectively forcing the beacon to use exactly that value in the next iteration. Any deviation from this usage is detected by an external entity.
Cryptographic functions and Publication: in the last phase of the algorithm, the external entropy, the local entropy, and some additional information of the system are linked together into a single value. This value is signed by Random UChile (using a digital signature algorithm). After that, the signature is concatenated once again with all the information previously linked together, and the result passed through an slow hash function, which ensures that any computation of the final value (the digest of the hash function) must involve a certain minimum wall-clock time, regardless of the computational power of the entity doing the computation. Finally, after this minimum time, the system outputs 512 bit-length random value as a result, as the random value generated by the Beacon in the current minute. Then, at the beginning of the next minute the process starts once again.
Currently, the slow hash function, used by our system is
sloth, proposed by Arjen Lenstra and Benjamin Wesolowski and described in this paper. Our implementation is based on github repository. We expect to substitute this algorithm for a newer Verifiable Delay Function soon.
Currently the Beacon relies on the following four entropy sources:
In Chile, many government organizations must execute public processes which are randomized in nature. One notable class are those processes where citizens are selected in order to receive benefits or be subject to penalties. By law, any selection of this type must be done without any discrimination, be positive or negative.
Yet, there is a fundamental problem that government organizations must solve to comply with the law: given the nature of random selection, it seems impossible to prove that a given person that was chosen was the result of a truly random process and not ‘handpicked’ by the organization. Random UChile provides a solution for this apparent impossibility, by providing an service that takes care of the randomness generation in a way that provides independence and verifiability to the organization. Random UChile takes charge of the randomized part of the process, while the organization runs the process using Random UChile’s random coins, making the output a direct result of both the randomness generated by Random UChile. The organization then can prove it did not have any interference in the outcome. In parallel, Random UChile provides mathematical guarantees that no person, in particular no one working for Random UChile, and not even the same people using Random UChile’s beacon, can interfere with or have prior knowledge of the concrete random value that is computed. With this, the random processes carried out by the public organization is trusted to generate a final outcome for which any observer can be sure that there was no manipulation of any sort.
Random UChile is currently working with several public organizations in order to incorporate verifiable randomness in some of their public processes. To explore some of the projects currently in development visit the project section.
The utility of Random UChile’s service goes beyond processes carried out by public organizations who strive for transparency. It is also useful for simpler and more mundane processes that involve randomness and trust. For example, choosing a random number inside a range, publicly choosing several random numbers inside a range (say, in a lottery), shuffling the order of a public list, choosing the winner of a draw performed in a social network, or even choosing a different random movie every day, just to name a few. Indeed, some of them are already available in our applications section.
The key and unique factor in Random UChile’s service relies on providing verifiability. Any person can verify that the process was carried out correctly and fairly, that is to say, that the outcome was not tamper or manipulated in any way. To achieve this, Random UChile allows (and actually encourages) participant organizations to follow our guidelines to create a verifiable execution. Most of the time, this means publishing not only the result of the process, but some public data so any interested external entity can recreate and then validate the result.
The National Institute of Standards and Technologies (NIST) also owns a Randomness Beacon that you can access here. The NIST service works under a fully-compatible API with that of Random UChile, meaning that both services are interoperable. Any service using Random UChile’s beacon will transparently work with the NIST’s beacon.
Random UChile is being supported by the National Institute of Standards and Technologies (NIST) ITL MSE Award #60NANB16D304 and #60NANB18D215 from the U.S. Department of Commerce.