Provable Randomness with VDF
A Verifiable Delay Function (VDF) is a linearly computed function that takes a relatively long time to calculate, however the resulting proof can be verified to be the result of this computation in a much shorter period of time. Since the computation can’t be sped up through parallelization or other tricks we can be sure that for a given seed the resulting value can’t be known ahead of time – thus making it a provable random number.
We can apply this to a blockchain to achieve provable randomness without an oracle by having the client compute the VDF. This process takes two transactions – the first to commit to the process and generate a seed for the VDF input, and the second to submit the calculated proof. If the length of time to calculate the VDF proof exceeds the block finality for the chain you are using, then the result of the second transaction can’t be known when the seed is generated and can thus be used as a provable random number. For more secure applications you can use multiple threads to calculate multiple VDF proofs concurrently, or for less strict requirements you can bitshift the value to get “new” random numbers.
Provable Random Numbers
The good stuff first – provable random numbers without an oracle. The user first makes a request to createSeed() typically with a commitment such as payment. This seed value along with the large prime and number of iterations are used to calculate the VDF proof – the larger the prime and the higher the iterations, the longer the proof takes to calculate and can be adjusted as needed. As long as the number of iterations takes longer to compute than the block finality we know it’s random since it’s not possible to know the result before it’s too late to change it. A blockchain like Fantom is ideal for this application with block times of ~1 second and finality after one block – validators cannot reorder blocks once the are minted.
This proof is then passed in to the prove() function. It uses the previously created seed – which now can’t be changed – and other inputs to verify the proof. If it passes, the value can be used as a random number, or can be passed into another function (as below) to create multiple random numbers by shifting the bits on each request for a random(ish) number.
Smart Contract
You can find large primes for your needs using https://bigprimes.org/, potentially even rotating them. Note that the code below is an example and should not be used directly without modifying for your needs.
[remote_content url='https://gist.githubusercontent.com/doublesharp/af6ee5cadb65222c062f8531d2c116a1/raw/RandomVDFv1.sol' decode_atts="true" htmlentities="true"]
Hardhat Example
This code is an example Hardhat script for calling the RandomVDFv1 contract. It shows the delay to calculate a proof and attempts to submit it. In a real implementation this could be an NFT mint, etc.
[remote_content url='https://gist.githubusercontent.com/doublesharp/af6ee5cadb65222c062f8531d2c116a1/raw/computeVDF.ts' decode_atts="true" htmlentities="true"]
Sloth Verifiable Delay
This off-chain implementation of Sloth VDF in Typescript will let us compute the proof on the client.
[remote_content url='https://gist.githubusercontent.com/doublesharp/af6ee5cadb65222c062f8531d2c116a1/raw/slothVDF.ts' decode_atts="true" htmlentities="true"]
Next we need to be able to verify the Sloth VDF proof on chain which is easy using the following library.
[remote_content url='https://gist.githubusercontent.com/doublesharp/af6ee5cadb65222c062f8531d2c116a1/raw/SlothVDF.sol' decode_atts="true" htmlentities="true"]
Randomness Library
Instead of using the proof directly as a single random number we can use it as the input to a random number generator for multiple provable random numbers. If we want to save a bit more gas instead of calling for a new number every time we can just shift the bits of the random number to the right and refill it when it empties. This pattern is more efficient if implemented directly your contract, but this library can be reused if you can support the relaxed security.
[remote_content url='https://gist.githubusercontent.com/doublesharp/af6ee5cadb65222c062f8531d2c116a1/raw/Randomness.sol' decode_atts="true" htmlentities="true"]
This example uses the Randomness library to generate multiple random numbers from a single proof in an efficient way. Note that this is a less secure application, though still valid for many use cases.
[remote_content url='https://gist.githubusercontent.com/doublesharp/af6ee5cadb65222c062f8531d2c116a1/raw/RandomVDFv2.sol' decode_atts="true" htmlentities="true"]
