Has random number generation in blockchain been solved?

Question

I've compared the 2 versions of the Ethereum wiki page about the hard problems of cryptoeconomics:

• https://github.com/ethereum/wiki/wiki/HPOC_2015
• https://github.com/ethereum/wiki/wiki/Problems

and found that the version from 2015 has a section titled Random Number Generation:

The open-ended challenge is to come up with a mechanism inside of a cryptoeconomic context which provides random numbers as output with maximally relaxed security assumptions and maximal robustness and resilience to attackers - ideally, a mechanism with the same properties as proof of work but without (or with only a negligible fraction of) its cost.

It also mentions the "N-of-N commit-reveal, as exemplified in Tomlion's RANDAO protocol" and its limitations.

This section is missing in the latest revision of the document. Does it mean that random number generation has been solved?

Answer 1

Yes, it has been solved by Chainlink VRF.

Getting a random number in a determanistic system is difficult, so we need to look outside the blockchain to get the random number. The question then, would be "is this number truly random?"

The Chainlink VRF has on-chain contracts that check to see if numbers are truly randomized, and can be easily generated.

pragma solidity 0.6.6;

import "@chainlink/contracts/src/v0.6/VRFConsumerBase.sol";

contract RandomNumberConsumer is VRFConsumerBase {
    
    bytes32 internal keyHash;
    uint256 internal fee;
    
    uint256 public randomResult;
    
    /**
     * Constructor inherits VRFConsumerBase
     * 
     * Network: Kovan
     * Chainlink VRF Coordinator address: 0xdD3782915140c8f3b190B5D67eAc6dc5760C46E9
     * LINK token address:                0xa36085F69e2889c224210F603D836748e7dC0088
     * Key Hash: 0x6c3699283bda56ad74f6b855546325b68d482e983852a7a82979cc4807b641f4
     */
    constructor() 
        VRFConsumerBase(
            0xdD3782915140c8f3b190B5D67eAc6dc5760C46E9, // VRF Coordinator
            0xa36085F69e2889c224210F603D836748e7dC0088  // LINK Token
        ) public
    {
        keyHash = 0x6c3699283bda56ad74f6b855546325b68d482e983852a7a82979cc4807b641f4;
        fee = 0.1 * 10 ** 18; // 0.1 LINK
    }
    
    /** 
     * Requests randomness from a user-provided seed
     */
    function getRandomNumber(uint256 userProvidedSeed) public returns (bytes32 requestId) {
        require(LINK.balanceOf(address(this)) >= fee, "Not enough LINK - fill contract with faucet");
        return requestRandomness(keyHash, fee, userProvidedSeed);
    }

    /**
     * Callback function used by VRF Coordinator
     */
    function fulfillRandomness(bytes32 requestId, uint256 randomness) internal override {
        randomResult = randomness;
    }
}

Answer 2

Here's a very good article on Random Number Generators (PRNG) in Ethereum Smart Contracts.

There are several implementations of pseudo PRNG that use elements like block.blockhash(block.number) like the one done by axiomzen:

function random(uint64 upper) public returns (uint64 randomNumber) {
  _seed = uint64(sha3(sha3(block.blockhash(block.number), _seed), now));
  return _seed % upper;
}

But these solutions are prone to predictability if given enough effort by an attacker. Here's an example of a Ethereum Roulette using this method, and how some one beat the house.

Currently the best approach is to use an external Oracle such as oraclize.

Answer 3

I suggest "majority vote Oracle" solves the issue. Here is an implementation in a Solidity smart contract, using one-cpu-one-vote to allocate votes.

contract RandomNumberOracle {
    
    uint constant period;

    function t() public view returns (uint) { return (block.number / period) * period; }

    uint nonce;

    mapping (uint => bytes32[]) blockhashes;

    mapping (uint => mapping (uint => uint)) points;

    mapping (uint => uint[]) leaderboard;
    mapping (uint => mapping (uint => uint)) leaderboardIndex;
    mapping (uint => mapping (uint => uint)) upperBound;
    mapping (uint => mapping (uint => uint)) lowerBound;

    function getRandomNumber() public view returns (uint) { return uint(blockhashes[t()-period*2][leaderboard[t()-period][0]]); }

    function vote(uint _id) public {
        require(msg.sender == block.coinbase && nonce != block.number);
        nonce = block.number;
        blockhashes[t()].push(blockhash(block.number - 1));

        if(blockhashes[t()-period].length == 0) return;

        require(_id < blockhashes[t()-period].length);

        if(points[t()][_id] == 0) {
            leaderboardIndex[t()][_id] = leaderboard[t()].length;
            if(upperBound[t()][1] == 0) upperBound[t()][1] = leaderboard[t()].length; 
            leaderboard[t()].push(_id);
        }
        else {
            uint index = leaderboardIndex[t()][_id];
            uint nextBucket = upperBound[t()][points[t()][_id]];
            if(nextBucket != index) (leaderboard[t()][nextBucket], leaderboard[t()][index]) = (leaderboard[t()][index], leaderboard[t()][nextBucket]);
            if(lowerBound[t()][points[t()][_id]] == nextBucket) { 
                lowerBound[t()][points[t()][_id]] = 0; 
                upperBound[t()][points[t()][_id]] = 0; 
            }
            else upperBound[t()][points[t()][_id]]--;

            if(upperBound[t()][points[t()][_id]+1] == 0) upperBound[t()][points[t()][_id]+1] = nextBucket;
            lowerBound[t()][points[t()][_id]+1] = nextBucket;
        }
        points[t()][_id]++;
    }
}