On-chain Random Number Generation
Last updated
Last updated
On-chain random number generation is an interesting task, as it may demand a good deal of data storage, computational resource expenditure, or plainly a seed concealed from the rest of the network. Therefore, the problem can be solved either by aggregating a number of off-chain source, so that the practical randomness is ensured by the great volume of submissions, or producing a verifiably random number (e.g., leveraging the decisional Diffie-Hellman assumption) on-chain.
A natural idea for generating random numbers would be to poll a number of users, each of whom supplies an off-chain random number, and aggregating them with some sequentially applied function, be it bitwise XOR, a sum-hash composition, or something else. However, doing this would beget a vulnerability to manipulation: the last submitter (mind that the miner that includes a given block is fully capable of determining who the last submitter will be) can look at the other submissions and fully determine the output of the algorithm by choosing a suitable number, since for him the output of the algorithm can be understood as a partial function from the space of all possible combinations, restricted to a subset so that the previous combinations are all fixed. Some functions make this harder for the attacker to do (e.g. functions that mimic random oracles, which are the majority of hash functions), but this is a critical vulnerability, and banking on suitable ASICs not existing would be unwise, especially when a simple correction can be made to diminish the attacker's influence.
This simple correction consists in demanding that the submitters commit to their values before the computation of the result starts. A simple way to do this is to collect first the hashes of the chosen numbers, terminate the process after a certain time, and collect the numbers themselves. Then, since (practically) any modification to the number (real hash functions are not injective) will change the hash, the only option for the attacker is to either reveal his number or avoid doing so. This obviously diminishes his influence to a single bit. This is a "good enough" algorithm, and it is used by Ethereum's RANDAO. However, a further improvement can be made to it, and a different approach to generating randomness can also be selected.
VDF/VRF (standing for verifiable delay and verifiable random function respectively) leverage certain properties of certain cyclic groups to construct problems that have computationally demanding inverses. The verifiable delay functions use the fact that in e.g., groups of unknown order, one cannot raise to a power efficiently except by performing sequential multiplications, thereby putting a lower bound on the amount of computational steps one needs to take in order to compute such a function. Practical treatments of this endow this function also with a Schnorr-type proof and an algorithm that allows to compute the principal values required for such a proof with a sublinear complexity in the amount of required computational steps t. An example of such VDF is the one constructed by Weselowski. By using the VDF, one can introduce a steep computational requirement that needs to be met to predict the output of the algorithm, which theoretically prevents the attacker from doing so. However, VDFs are vulnerable to construction of ASICs, and so their implementation on Ethereum is postponed until that issue is resolved.
VRFs, like the Goldberg VRF employed by Chainlink for construction of their random numbers, use cyclic groups where the decisional Diffie-Hellman assumption (asserting that given g^a, g^b, g^ab will be computationally indistinguishable from an unrelated random group member) to construct effectively random numbers in the following way: the VRF generator possesses a secret key x, for which the public key g^x is known, as is the generator of the group. From the provided seed a new generator of the same group h is constructed. Since g, h lay in the same group, h = g^d for some number d. Then by the Diffie-Hellmann assumption, h^x is computationally indistinguishable from an unrelated random number, given g^x, h. The demanding group operations are performed off-chain, and the number and the Chaum-Pedersen proof (though the Chainlink documentation compares it to a Schnorr proof, it manifestly proves the possession of the discrete logarithm of two problems with different bases and the same exponent, which is the Chaum-Pedersen setting) are passed on-chain to be verified before the randomness consumer is provided with the number. Verification entails a small number of group operations which can be reduced to group multiplications only, and for group multiplications there exist tricks allowing the verification to be relatively cheap.
