RNG on Ethereum blockchain

Obtaining a reliable source of randomness on Ethereum is no easy task. The best pattern we chose to ultimately implement on CryptoKitties is known as commit-reveal. See original GeneScience contract here for an example

The main constraints we conformed to are:

1. Get an arbitrary amount of random numbers per block
2. Run cheaply
3. Be unpredictable and not manipulable

At the time a kitty gets pregnant we know from which block it will be able to be born, let's call the block height DDB. Therefore we save DDB to the kitty struct at time of pregnancy.
Then after DDB is achieved, a birther will call the give birth function, which is roughly: R = uint256(block.blockhash(DDB-1)) [1].

For Cryptokitties purposes, other elements go into this hash as well, BUT it's important that any elements that go into that hashing are unable to be changed.

Then R can be bitsliced to make power of 2 numbers that make random slices of it [2]. If more random numbers are necessary, it's possible to continually re-hash R and obtain equaly strong random numbers.

[1] Can only get the last 256 block hashes, otherwise it will return 0, which sucks. Cryptokitties implement 2 fallbacks: first an economic measure, anyone is able to give birth to kitties and get an Ether reward for that. The second one is to check if R==0, and (loosely speaking) add 256 until we get a R != 0.

[2] May use a bit slicing function and keep an index of how many bits have been used so far as a variable that you increment.

Analysis

In addition to good quality of number generation, several concerns play when harvesting random numbers from blockchains, so let's address the main points.

Predictability

Since the block hash in the future is unknown, it's unpredictable at the time of commit.

User manipulation

No user should be able to seed or tamper with the RNG input. As we discussed in item [1] above, counter measures must be in place to prevent "re-rolls".

Miner manipulation

Miners are a powerful force in every aspect that comes into play when creating a block, because well, they create the blocks. Block hashes happen to be the hardest element to meddle with due to how PoW functions, miners are lucky to mine a block and get it's reward, by essentially finding a fitting hash, and if a miner is to keep on re-hashing the block until it's satisfied with the hashing result, it will end up failing to be the winner for that block height, as other miners will propose a block before them.

Given the current state of Ethereum, the described RNG method seems safe, as long as the possible reward from the RNG result is not big enough to have miners altering their mining behaviour. Such value is estimated at 0.25ETH.

With Casper PoS changes in 2020, RNG methods that rely on blockhash entropy might become more easily exploitable.

Low cost

This technique gas cost is pretty low. The most costly element requires the cost of 1 update in an existing storage word, and that would happen anyways as kitties get pregnant. Hashing and bit manipulation operations are not expensive.

Links of interest:

1. Presentation at Ethdenver 2019 about random-number generation
2. Cryptokitties blog post on GeneScience
3. @Razor talk on the topic
4. Consensys Smart contract recommendations
5. A multi input based random generation

Contributing

PR > new issue. Welcome pull requests that:

1. Improve the quality of the information
2. Adds an example in solidity #8
3. Adds links of interest

Acknowledgement

While the final mechanism implemented in Cryptokitties was developed and implemented by @dete and @flockonus, @Arachnid had a major contribution to the mechanism. Also thanks to constructive criticism by @MicahZoltu and @Raz0r, among others.