A Review Of Random Number Generator (RNG) On Blockchain
Randomness is a criterion to evaluate the security level of a system. Traditional random number generation is centralized and lacks an easy cost effective way to verify the results or if there has been any tampering. Blockchain random number generators as known as decentralized random number generators, on the other hand, solve this problem by leveraging the blockchain technology to bring transparency, fairness, verifiability, and tamper-resistance into the process of generating numbers. Let’s take a look at existing RNG solutions to identify the challenges that need to be conquered.
It is well known that randomness is an essential building block of many aspects of life ranging from theory such as security, cryptography, or computer simulation to forms of gambling like lotteries. Obtaining a true randomness source is always significantly challenging and a lot of effort has been devoted to constructing a good Random Number Generator (RNG). Traditionally, RNGs can be classified into two types: Pseudo-Random Number Generators (PRNGs) and True Random Number Generators (TRNGs). PRNGs utilize mathematical algorithms, which are considered deterministic. These RNGs are based on algorithms implemented on finite-state machines to produce pseudo-random determinism sequences from initial values called seeds in mathematical processes. TRNGs, on the other hand, derive randomness from various physical phenomena such as thermal noise, radio noise and so on. It is widely agreed that these sources behave on an inherently unpredictable and non-deterministic manner.
Many applications today not only require randomness in the unpredictability manner but also require public randomness which cannot be manipulated or in control of any organization. Traditional RNGs cannot resolve this since they are centralized (this article explains in-depth the terms, centralization, and decentralization) and running solely on a local source and or under the control of a group of individuals or organizations. All this changed in 2009 with the invention of blockchain technology. Since then, the phrase “blockchain random number” has been getting more and more attention from computer scientists. As a result, many attempts have been made to construct a blockchain-based random number generator. We will briefly discuss some of these solutions in order to clarify the current state of blockchain-based random number generation:
In this approach, the hash of blocks or transactions is used as the source of randomness. As the hash is deterministic, everyone will get the same result. A block, once added to the blockchain, is likely to stay there forever, therefore, everyone can verify the correctness of the generated numbers.
Consider an example of a lottery service that adopts this method. The players first buy a ticket by placing their number before a specific time, say 7PM everyday. After 7PM, the buying ticket phase is closed, the protocol proceeds to the next phase which is to determine the winning numbers for a ticket. This ticket is calculated based on the hash of the first block accessible for everyone on the Bitcoin blockchain after 8PM. As we can see, at 7PM, no one can predict the hash of block at 8 PM which makes the service seemingly a sound one. However, this hash is subject to manipulation by the miners guarding the blockchain. When the reward of the lottery is small, the miners have little motivation to tamper with the block but as soon as this amount is larger than the block reward plus the transaction fees, there is a chance that miners will start influencing the block-hash to generate their desired numbers. Thus, for high-stake randomness-based applications, this method is not a secure one.
In this case, Bitcoin blockchain is used to produce random numbers. The timestamps and transactions in Bitcoin pack a sustainably high entropy source. Entropy measures the “chaos” of a randomness source. The more “chaotic” the source is (the higher the entropy is), the more difficult to predict the number generated. Additionally, the SHA256 hash function and the Proof-of-Work algorithm are used to determine the random function. We know that PoW is computationally intensive, and non-deterministic resulting in the unpredictability of the RNG’s outcomes. This approach retains the same problem as the previous one since it does not properly deal with the risk of Block Withholding Attacks, where (financially incentivized) miners intentionally discard blocks they do not favor. On a blockchain, miners help secure the blockchain by running the Proof-of-Work algorithm and probabilistically receive rewards in the form of bitcoins for doing so. As a result, any attack on the random beacon would form an attack on Bitcoin itself. Therefore, this approach can only be secure up to a specific bound of monetary costs. In lotteries, when the reward is large, one can bribe miners to ignore specific blocks, consequently compromising the randomness. Another issue is that normal parties (non-miners) cannot take part in the producing of these random numbers, which implies that fairness does not hold true for this solution.
By design, Oraclize is a data supplier which provides data for smart contracts and blockchain applications. Many real-world situations require fetching data from outside of the blockchain, but the nature of smart contracts does not help solve this problem. Oraclize comes as a rescue to make this scenario come true. As an intermediary, Oraclize collects data from external sources such as WolframAlpha, IPFS, etc and then delivers the data to the applications in need. Regarding random numbers, Oraclize fetches data from random.org into blockchains. The solution, as its core, is a centralized data service. It argues that through the so-called Authenticity Proofs, everyone can verify that the fetched numbers are genuine and untampered. Obviously, in this model, one has to trust not only Oraclize but also the data provider, i.e which is random.org in the randomness case. We have not concluded on the plausibility of this solution. However, relying on trusted parties contradicts the philosophy of the blockchain technology as a centralized service can be corrupted at any time. This makes Oraclize inefficient for applications that require high security and trustless between parties on the blockchain.
“Miners cannot be trusted” is the philosophy of designing RanDAO. In the first and second approaches, the random numbers are subject to being manipulated by miners on blockchains. RanDAO is an organization whose aim is to construct a verifiably fair RNG on blockchains. They have come up with 2 solutions: the Commit-Reveal Scheme and the BLS Scheme. Here, we briefly introduce the former, which has been deployed since 2017. It is a Verifiable Random Number Generator. RanDAO commit-reveal scheme (RanDAO for short) is an RNG running on the Ethereum blockchain that allows many parties to participate in generating random numbers. Anyone with an Ethereum address is able to take part in the generation process, hence, fairness is guaranteed. The core idea is to allow participants to give their contribution to form the final outcome. As in its nature, RanDAO attempts to solve the problem of verifiability and fairness, not the problem of randomness as a whole. The protocol goes through three phases as follows:
- Commit: Any participant i who wants to take part in the random number generation submits a commitment associated with the secret number si he wants to contribute.
- Reveal: After the Commit phase has finished, i.e. everyone has submitted their commitment, participants need to reveal the secret number si.
- Calculate: When everyone has revealed their number, the final random number will be calculated from a function f(s1,s2,…,sn) of all collected secret numbers.
The integrity of the generated numbers relies on the assumption that there is at least one honest party since the function f ensures that if one controls up to n-1 values of si, he still cannot manipulate the final outcome. However, the main problem of this protocol is that the last person to reveal the secret will is able to know the resulting random number beforehand and this person can refuse to reveal the secret value leading the protocol to termination without producing any outcome.
Random Beacon Protocols
The main focus of random beacon protocols is to generate publicly-verifiable, bias-resistant and unpredictable randomness in distributed environments. First proposed by Rabin, until now, random beacon protocols have employed many different techniques such as unique signatures, Proof-of-Delay or publicly-verifiable secret sharing (PVSS).
The last one appears to be the most popular one. In this technique, A party holding a secret in the publicly-verifiable secret sharing splits it into shares (verifiable by any third party) and distributes these shares to other parties. When everyone comes to an agreement to reveal the secret, shares are collected and once one is in possession of enough shares, he can reconstruct the secret. The number of shares enough to reconstruct the secret varies in different use cases (usually, this number is set to be half of the total number of shares). Therefore, most of the PVSS protocols require strong assumption on the number of honest parties, i.e. honest majority (more than half of the network is honest) to make sure that the secret is unpredictable whilst RanDAO only requires honest minority (at least one party is honest) to ensure the unpredictability. Another problem with this scheme is that the network communication complexity is high which prevents it from scaling out.
A lot of attempts have been made to design blockchain random number generators, however, existing solutions only deal with one or two aspects and fall short in other aspects. While some are too slow to generate a number, some do not satisfy the security requirements. Thus, to have an RNG that runs on a decentralized network and allows anyone to generate, and audit the random numbers while still ensuring its security is significantly challenging.
This is where GINAR comes in. GINAR answers the shortcomings by other blockchain based random number generators. GINAR random number generator is a multi-participatory RNG which allows many people to take part in the process of generating a random number. Each party/participant/person contributes a number and the final outcome will be calculated as the combination of all contributed numbers. In the subsequent articles, we will explain in greater detail how GINAR offers solutions to many of these problems.