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.
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.11;
import './libraries/SlothVDF.sol';
contract RandomVDFv1 {
// large prime
uint256 public prime = 432211379112113246928842014508850435796007;
// adjust for block finality
uint256 public iterations = 1000;
// increment nonce to increase entropy
uint256 private nonce;
// address -> vdf seed
mapping(address => uint256) public seeds;
function createSeed() external payable {
// commit funds/tokens/etc here
// create a pseudo random seed as the input
seeds[msg.sender] = uint256(keccak256(abi.encodePacked(msg.sender, nonce++, block.timestamp, blockhash(block.number - 1))));
}
function prove(uint256 proof) external {
// see if the proof is valid for the seed associated with the address
require(SlothVDF.verify(proof, seeds[msg.sender], prime, iterations), 'Invalid proof');
// use the proof as a provable random number
uint256 _random = proof;
}
}
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.
import { ethers, deployments } from 'hardhat';
import { RandomVDFv1 } from '../sdk/types';
import sloth from './slothVDF';
async function main() {
// We get the signer
const [signer] = await ethers.getSigners();
// get the contracts
const deploy = await deployments.get('RandomVDFv1');
const token = (await ethers.getContractAt('RandomVDFv1', deploy.address, signer)) as RandomVDFv1;
// the prime and iterations from the contract
const prime = BigInt((await token.prime()).toString());
const iterations = BigInt((await token.iterations()).toNumber());
console.log('prime', prime.toString());
console.log('iterations', iterations.toString());
// create a new seed
const tx = await token.createSeed();
await tx.wait();
// get the seed
const seed = BigInt((await token.seeds(signer.address)).toString());
console.log('seed', seed.toString());
// compute the proof
const start = Date.now();
const proof = sloth.computeBeacon(seed, prime, iterations);
console.log('compute time', Date.now() - start, 'ms', 'vdf proof', proof);
// this could be a mint function, etc
const proofTx = await token.prove(proof);
await proofTx.wait();
}
main().catch((error) => {
console.error(error);
process.exit(1);
});
Sloth Verifiable Delay
This off-chain implementation of Sloth VDF in Typescript will let us compute the proof on the client.
const bexmod = (base: bigint, exponent: bigint, modulus: bigint) => {
let result = 1n;
for (; exponent > 0n; exponent >>= 1n) {
if (exponent & 1n) {
result = (result * base) % modulus;
}
base = (base * base) % modulus;
}
return result;
};
const sloth = {
compute(seed: bigint, prime: bigint, iterations: bigint) {
const exponent = (prime + 1n) >> 2n;
let beacon = seed % prime;
for (let i = 0n; i < iterations; ++i) {
beacon = bexmod(beacon, exponent, prime);
}
return beacon;
},
verify(beacon: bigint, seed: bigint, prime: bigint, iterations: bigint) {
for (let i = 0n; i < iterations; ++i) {
beacon = (beacon * beacon) % prime;
}
seed %= prime;
if (seed == beacon) return true;
if (prime - seed === beacon) return true;
return false;
},
};
export default sloth;
Next we need to be able to verify the Sloth VDF proof on chain which is easy using the following library.
// SPDX-License-Identifier: MIT
// https://eprint.iacr.org/2015/366.pdf
pragma solidity ^0.8.11;
library SlothVDF {
/// @dev pow(base, exponent, modulus)
/// @param base base
/// @param exponent exponent
/// @param modulus modulus
function bexmod(
uint256 base,
uint256 exponent,
uint256 modulus
) internal pure returns (uint256) {
uint256 _result = 1;
uint256 _base = base;
for (; exponent > 0; exponent >>= 1) {
if (exponent & 1 == 1) {
_result = mulmod(_result, _base, modulus);
}
_base = mulmod(_base, _base, modulus);
}
return _result;
}
/// @dev compute sloth starting from seed, over prime, for iterations
/// @param _seed seed
/// @param _prime prime
/// @param _iterations number of iterations
/// @return sloth result
function compute(
uint256 _seed,
uint256 _prime,
uint256 _iterations
) internal pure returns (uint256) {
uint256 _exponent = (_prime + 1) >> 2;
_seed %= _prime;
for (uint256 i; i < _iterations; ++i) {
_seed = bexmod(_seed, _exponent, _prime);
}
return _seed;
}
/// @dev verify sloth result proof, starting from seed, over prime, for iterations
/// @param _proof result
/// @param _seed seed
/// @param _prime prime
/// @param _iterations number of iterations
/// @return true if y is a quadratic residue modulo p
function verify(
uint256 _proof,
uint256 _seed,
uint256 _prime,
uint256 _iterations
) internal pure returns (bool) {
for (uint256 i; i < _iterations; ++i) {
_proof = mulmod(_proof, _proof, _prime);
}
_seed %= _prime;
if (_seed == _proof) return true;
if (_prime - _seed == _proof) return true;
return false;
}
}
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.
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.11;
library Randomness {
// memory struct for rand
struct RNG {
uint256 seed;
uint256 nonce;
}
/// @dev get a random number
function getRandom(RNG storage _rng) external returns (uint256 randomness, uint256 random) {
return _getRandom(_rng, 0, 2**256 - 1, _rng.seed);
}
/// @dev get a random number
function getRandom(RNG storage _rng, uint256 _randomness) external returns (uint256 randomness, uint256 random) {
return _getRandom(_rng, _randomness, 2**256 - 1, _rng.seed);
}
/// @dev get a random number passing in a custom seed
function getRandom(
RNG storage _rng,
uint256 _randomness,
uint256 _seed
) external returns (uint256 randomness, uint256 random) {
return _getRandom(_rng, _randomness, 2**256 - 1, _seed);
}
/// @dev get a random number in range (0, _max)
function getRandomRange(
RNG storage _rng,
uint256 _max
) external returns (uint256 randomness, uint256 random) {
return _getRandom(_rng, 0, _max, _rng.seed);
}
/// @dev get a random number in range (0, _max)
function getRandomRange(
RNG storage _rng,
uint256 _randomness,
uint256 _max
) external returns (uint256 randomness, uint256 random) {
return _getRandom(_rng, _randomness, _max, _rng.seed);
}
/// @dev get a random number in range (0, _max) passing in a custom seed
function getRandomRange(
RNG storage _rng,
uint256 _randomness,
uint256 _max,
uint256 _seed
) external returns (uint256 randomness, uint256 random) {
return _getRandom(_rng, _randomness, _max, _seed);
}
/// @dev fullfill a random number request for the given inputs, incrementing the nonce, and returning the random number
function _getRandom(
RNG storage _rng,
uint256 _randomness,
uint256 _max,
uint256 _seed
) internal returns (uint256 randomness, uint256 random) {
// if the randomness is zero, we need to fill it
if (_randomness <= 0) {
// increment the nonce in case we roll over
_randomness = uint256(
keccak256(
abi.encodePacked(_seed, _rng.nonce++, block.timestamp, msg.sender, blockhash(block.number - 1))
)
);
}
// mod to the requested range
random = _randomness % _max;
// shift bits to the right to get a new random number
randomness = _randomness >>= 4;
}
}
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.
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.11;
import './libraries/Randomness.sol';
import './libraries/SlothVDF.sol';
contract RandomVDFv2 {
using Randomness for Randomness.RNG;
Randomness.RNG private _rng;
// large prime
uint256 public prime = 432211379112113246928842014508850435796007;
// adjust for block finality
uint256 public iterations = 1000;
// increment nonce to increase entropy
uint256 private nonce;
// address -> vdf seed
mapping(address => uint256) public seeds;
// commit funds/tokens/etc here
function createSeed() external payable {
// create a pseudo random seed as the input
seeds[msg.sender] = Randomness.RNG(0, nonce++).getRandom();
}
function prove(uint256 proof) external {
// see if the proof is valid for the seed associated with the address
require(SlothVDF.verify(proof, seeds[msg.sender], prime, iterations), 'Invalid proof');
uint256 _randomness;
uint256 _random;
(_randomness, _random) = _rng.getRandom(_randomness, proof);
(_randomness, _random) = _rng.getRandom(_randomness, proof);
(_randomness, _random) = _rng.getRandom(_randomness, proof);
}
}
