Random numbers are used in various scenes in people’s life, such as welfare lottery, license plate lottery, and public housing allocation, etc. With the development of the Internet, people rely more and more on centralized systems for the use of random numbers, but most of the generated random numbers in the centralized system are pseudo-random with the risk of cheating.
The emergence of blockchain makes the random number generation of greater fairness a possibility. The random number also plays a very important role in the blockchain itself. So what are the application scenarios of random numbers in the blockchain? How does the blockchain generate more reliable random numbers?
The application of random numbers in blockchain
Private Key
All the cryptocurrency holders know the importance of the private key, and whoever owns your private key owns your assets. The generation of private keys depends on random numbers, sothe unpredictability and anti-decryption of random numbers holds the key to the security of cryptocurrency.
The private key of Bitcoin is a 256-bit random number generated by SHA-256 with the value ranging from 0 to 2256-1. 2256 is approximately 1077, which is a very large number, and it’s almost impossible to brute force with the existing computing power.
Although no brute force, if the random number generator can be manipulated, the generated random number can be predictable, then your private key may be decrypted, and the security of the encrypted asset may not be guaranteed.
Quiz applications
In the quiz application, randomness of the results is realized by the use of random numbers to avoid human intervention and ensure the fairness of the results.
In a centralized environment, users participating in the quiz need to submit a quiz order to the system. The system collects the user's information according to the rules and then generates a quiz result. Throughout the process, the client has nothing to do with the calculation of the quiz results, which are essentially a string of random numbers generated by the system. When facing a great temptation for profit, the system may cheat to make benefits.
While in a decentralized environment, there is no unique center that allows all nodes to join the generation of random numbers, which can effectively guarantee the fairness of random numbers. However, in a decentralized environment, it’s much easier for hackers to attack random numbers and gain benefits. So far, the security of random numbers in blockchains is still a technical problem that needs to be broken through.
In August 2018, Fomo3D, which had been popular for a while, was accused by hackers of exploiting its random number vulnerability to gain huge profits in the game. Following Fomo3D, a number of popular dAPPs on EOS, especially quiz games such as EOS.WIN, EOSDice, etc., have also been hacked due to defects in random number generation.
POS consensus mechanism
Blockchain is a decentralized ledge technology. In a decentralized environment, it is critical to select bookkeepers randomly to achieve correct bookkeeping. Because only under random conditions can the fair distribution of the bookkeeping rights and rationally distribution of the mining incentives be guaranteed.
The consensus mechanism of POW is to calculate a highly difficult hash value through computing-power competition to randomly determine bookkeepers. While POS uses random numbers to randomly elect a node for bookkeeping.
Most POS protocols select a group of miners and verifiers based on the number of tokens of the holder to jointly complete the verification of the transactions on chain and generate new blocks. In order to randomly select miners and verifiers to ensure fair distribution of rewards, the algorithm must incorporate some fair and unbiased random number sources. Therefore, random number generation is a key technology for various POS consensus mechanisms.
True random number and pseudo random number
Random numbers can be divided into two types: true random numbers and pseudo random numbers. True random number sequence are completely unpredictable and only exist in the real physical world, such as radioactive decay, electronic equipment noise, cosmic ray triggering time, etc. We can collect these data to obtain true random number sequence. Pseudo-random numbers are obtained by using the random number algorithm to calculate the true random number sequence (usually called the random number seed). As long as the random number seed is obtained, the same pseudo-random number sequence can be output.
In summary, true random numbers exist only in the real physical world, and most of the random numbers in computers are pseudo-random numbers. To ensure the security of pseudo-random numbers, a valid random number seed and a secure random number generator is essential.
How to generate random numbers in blockchains
The blockchain is a decentralized system. Theoretically, the generated random number is fairer than that in the centralized system. However, in the decentralized system, it is more vulnerable to hacking if there is a huge amount of interest.So a variety of random number generation mechanisms come to birth to ensure the security of random numbers in the blockchain.
VRF
VRF (verifiable random function) is a verifiable random number generation method. Currently it is mainly used in blockchain projects based on POS consensus algorithm, including Algorand and Cardano.
In Algorand and Cardano, VRF is the key to generate random numbers. The VRF can output a random number with any input. A non-interactive zero-knowledge proof process is specially designed in VRF, which can be used to verify the correctness of random numbers, and to identify which node generates the random number.
VRF mainly includes four links:
- Generate a public-private key pair
- Generate random number output
- Calculate zero knowledge proof
- Verify random number output
The node generating the random number takes its private key as part of the input and then outputs the random number and zero-knowledge proof locally. Other nodes can use the public key, input, and output of this node to verify the authenticity of the random number and the identity of the generator.
Once the random number is obtained, it is ready to use the number to pick the nodes that is able to propose blocks. The easiest way is to set a consensus threshold M in the whole network. If the random number R generated by a node is greater than M, the system will allow it to participate in the next block-generating task. However, there is no way to prevent witch attacks in this scheme, so most VRF lottery schemes now allocate votes based on equity, and then design a lottery algorithm to complete the follow-up consensus process.
Randao
Randao is based on blockchain technology and provides the service of random number generation that is open source, decentralized, socialized and verifiably fair. Randao not only has the characteristics of uncontrollability and unpredictability which it inherits from the common random number generator, but also it is more accessible and provably fair. Randao helps individuals to observe their impact on the generation process of random numbers through providing each stakeholder participation channel. The transparent, irreversible generation process ensures the fairness of the random numbers.
Randao mainly adopts Commit Reveal and BLS. The Commit Reveal Program has the disadvantage of low production in random number generation. In the case of the Ethereum, it takes at least 10 block time from receiving the production request to the output of a random number and at current block time it takes more than 3 minutes. In addition, participants need to send transactions and submit data several times, thus resulting in a relatively high cost of use. However, the advantage lies in its zero threshold, as anyone can participate in the generation process at any time, which also helps to avoid collusion and to prove its fairness.
The BLS signature scheme is a good complement to the Commit Reveal Program because the generation process is organized off-chain, with a fast response, usually requiring only one block time to generate a random number; the consumer initiates a request for random number generation, the producer writes the random number in the next block, which means it only needs to send two transactions to complete the generation and call of the random number. The production and usage costs are low, suitable for high frequency, and a less harsh demand to be conspiracy-resistance.
Threshold Signature Scheme
Dfinity is a public chain project with the goal of becoming an "Internet computer" that enables software and services to run in its public cloud. In Dfinity, the random number is the core of the normal operation of the whole consensus mechanism. The threshold signature scheme used in combination with the VRF and BLS signature mechanism is an effective way to generate random numbers.
The threshold signature scheme mainly consists of three parts: input, output, and threshold scheme. The input is a group of private keys of the member, and the output is a random number. The threshold scheme guarantees that as long as the number of inputs from the member exceeds the set value, a certain random number can be obtained; otherwise no one can predict the random number of the output. VRF is used in the process of random number output, and BLS signature scheme is used in the threshold scheme.
The threshold signature scheme combines VRF and BLS. The VRF makes the generated random number verifiable and the BLS signature scheme ensures the signature result unpredictable and realizes the uncontrollability of the random numbered being difficult to collude. Therefore, it is a good mechanism for random number generation.
NULSRNG
NULSRNG is a mechanism for random number seed generation specially designed for dApps based on POC algorithm by NULS, a global open source and community-driven project.
The implementation of NULSRNG is a two-stage random seed submission generation mechanism based on POC consensus. That is, each node generates a random seed at the same time as the block is generated, encrypts the random seed to include the generated cipher text in the block header, and at the same time, obtains the 256-bit random seed plaintext generated last time generating blocks. With the plaintext and cipher text in the block header, the random number seed generated by the node can be verified to ensure that it cannot be tampered with.
NULSRNG is implemented based on the underlying consensus, with the participation of all the consensus nodes, which increases the difficulty of node collusion. The two-stage submission of seed cipher text and plaintext makes seed verifiable and non-tamperable.
dApps developed based on NULS can obtain random seeds by using the underlying interface directly, and then use its own random algorithm to generate the required random number sequence, which can not only improve the security of random numbers, but also be flexible and convenient in use.
Conclusion
1. In the blockchain, there are various application scenarios of random numbers. With the continuous development and improvement of blockchain technology, applications of random numbers in blockchains will continue to increase;
2. In the field of blockchain, there are already many different random number generation mechanisms, each of which has its own characteristics;
3. Aware of the importance of random numbers, more and more technical teams and project parties are beginning to study better random number generation mechanisms, and more perfect
blockchain random number generation mechanisms will be produced in the future.
About the author:
Ken Huang
A well-known blockchain expert, chief scientist of NUChain, American DistributedApps CEO, member of Blockchain Experts Committee of Chinese Institute of Electronics and NULS technical advisor.
DoubleXiang
Java software engineer, cryptotech-writer and NULS Core Team member. He focuses on blockchain technology research and blockchain solutions.
References
《Randao: Verifiable Random Number Generation》；
《Verifiable Random Functions》Silvio Micali， Michael Rabiny， Salil Vadhanz；
《DFINITY Technology Overview Series Consensus System》Timo Hanke, Mahnush Movahedi ， Dominic Williams。
