Random Number Generators
Here’s an interesting fact many people don’t know about blockchains: they depend on the generation of random numbers for security. In fact, Bitcoin’s proof-of-work consensus, described in Satoshi Nakamoto’s original Bitcoin paper and subsequent proof-of-work algorithms, can be seen as very expensive random number generators.
The fact that consensus protocols are random number generators may be surprising, but public blockchains rely on a way to determine the next block producers. This election process should have three properties:
- Fairness: The process should be fair, in the sense that anyone can have a chance at creating a block, proportional to some effort invested.
- Incentive-based: Participants should gain an advantage from being chosen as the block producer and be incentivized to behave honestly.
- Non-determinism: The next block producer should not be known in advance.
Proof-of-work reaches consensus by competition. All participating nodes repeatedly change a field in a block and compute the hash values until someone finds a solution that matches a certain criterion (defined by the difficulty). As no one can predict these hash values without performing the computation, this process is essentially a random selection, weighted by computational power.
In proof-of-stake, the computational weight added to the random process is replaced by wealth, i.e. the number of coins staked. However, the actual block generation is still a weighted random selection. In Peercoin, for example, nodes still generate hashes, but the rate at which they can run computations is restricted by the coin age of their staked coins.
Choosing the next block generator can be handled differently in permissioned blockchains or delegated proof-of-stake models. The key properties that allow choosing block generators by other means in this type of system are that the participants are known and limited in number. A round robin solution is often used for choosing a block proposer. However, even in this setting, random selection is seen as a security and performance improvement.
The Difficulty of Generating Random Numbers
Generating randomness is difficult for computers in general, but even more so in a distributed system. First, it is difficult to generate global random numbers shared between all participants without putting one of the nodes into a privileged position. Second, it is hard to find the source of entropy necessary to seed random number generation algorithms. Many developers of gambling or game smart contracts have found this out the hard way, as predictability of random numbers is a common vulnerability in these contracts.
Generating real randomness in distributed systems is an active field of research, recently rejuvenated by the blockchain boom. Several novel consensus algorithms have come out of this research. Hyperledger Sawtooth’s proof of elapsed time relies on trusted computing solutions (Intel Software Guard Extensions (SGX)) as an outside source for random number generation. Dfinity uses a cryptographic technique called BLS signatures to generate randomness.
Whatever the best solution, it’s clear that randomness is the foundation for the blockchain security model, not just for block generation. Let’s not forget that cryptography, in general, relies heavily on random numbers at the lowest level. For example, it would not be possible to generate safe Bitcoin key pairs without random number generation.