How can I securely generate a random number in my smart contract?
If I am writing a smart contract for some kind of (gambling) game, how can I generate a random number securely? What are the best practises and security trade-offs to be aware of?
This is a very interesting question that may have a lot of applications other than a gambling game. The best application I can think of is a truly random number based cryptocurrency mining scheme - simply give the reward to a random miner/user. A network with this scheme would attract new miners while it would need very little electricity to run in comparison to Bitcoin's proof of work which is nothing else but energy waste.
There are a few trade-offs and key points to keep in mind in this area.
Any decision that a user makes which affects the outcome gives that user an unfair advantage. Examples include:
- Using a blockhash, timestamp, or other miner-defined value. Keep in mind that the miner has a choice of whether to publish a block or not, so they could conceivably have one chance at the prize per block they mine.
- Any user-submitted random number. Even if the user pre-commits to a number, they have a choice in whether or not to reveal the number.
Everything that the contract sees, the public sees.
- This means that the number should not be generated until after entry into the lottery has been closed.
The EVM will not outrace a physical computer.
- Any number that the contract generates may be known before the end of that block. Leave time between the generation of the number and its use.
Now for the technique:
Perfectly Decentralized Lottery-Style Non-Malleable Commitment:
- The Casino sets aside a reward for a random number
- Each user generates their own secret random number
- Users create their commitment by hashing their
Nwith their address:
bytes32 hash = sha3(N,msg.sender)1
- note: steps 2 & 3 should be performed locally, in secret
- Users send their hash to the contract, along with ether greater than or equal in value to the value of the random number.2
Submissions continue for some number of blocks, or until sufficient participants have joined.
Once the submission round has ended, the reveal round begins.
Each user submits their random number
Nto the contract
The contract verifies that the
sha3(N,msg.sender)matches the original submission
- If the user does not submit a valid
Nin time, his deposit is forfeit.
- If the user does not submit a valid
Ns are all
XOR'd together to generate the resulting random number.
- This number is used to determine which of the participants receives the reward. (
N % numUsers)3
Notes and alternatives:
1. The users must concatenate their address to their
Nbefore hashing. Otherwise, another user could simply submit an identical hash, then wait for
Nto be revealed, then submit that.
N XOR Nequals 0, so this could be used to cancel out all submissions except the attacker's.
2. This is where the trade-offs come in. The last person to reveal their
Nhas a choice whether to reveal or to not reveal. This essentially gives them a double chance at winning. Enter enough times, and you get a new choice for each entry. Hint: Miners chose the order of transactions in a block. In order to discourage this, users must put up a large security deposit, equal to the value they would gain by manipulating the random number. This could be a problem for many users, especially for large jackpots, even with game-theoretic optimizations.
- A commonly used alternative is a semi-centralized system. This requires the "house" to submit the first hash and last reveal. If the house does not fulfill their duty, everyone's ether is returned. This has issues, such as the house choosing to flake if a jackpot payout is imminent. The idea is that the house's reputation is at stake.
- Note that this essentially centralizes the whole system. One simply needs to take down the house for the whole operation to be shut down. This risk can be reduced by hiring multiple trusted non-players to be the first/last commiters.
- Another trick is to use hired professional third parties to "mine" randomness for you, so that the players need not be bothered with the process.
3. A reward is necessary in order to foster competition among participants. It causes a classic tragedy-of-the-commons/prisoner's dilemma situation. Collusion between participants would allow them to win a large pot and split it among themselves, but if everyone knows what everyone else will submit, they know what they themselves should submit to win the reward. Thus, if the reward is larger than the value of the random number divided by the number of players, then everyone is incentivised to keep their own number a secret in order to have a better shot at the reward. Note that only one of the participants needs to submit a good random number, and the result will be unpredictable.
Thinking out loud here: what about using one (or several) oracle to get the SHA-256 of a particular Bitcoin block number (not found yet) as a seed. Would this work for Ethereum games where the payout is inferior to the reward of mining a BTC block? Because the cost of finding a BTC block is very high, deciding "not to publish" the block and forfeiting 12.5 BTC reward plus tx fees would not make sense it the payout of the Ethereum game is less than, say, 12.5 BTC.
This is actually a very interesting idea. You would need to wait for a few confirmations, but it would definitely increase the cost to manipulate the results. I think I'll make a contract to do this...
@TjadenHess Can we just construct the random number sequentially from future ETH block hashes bit-by-bit? The 1st bit of the random number is the rightmost bit of the future block #1 hash, the 2nd bit is the rightmost bit of the future block #2 hash etc until some future block #L. If we get more 1s than 0s in the end, then it is "Heads", otherwise it is "Tails". No single block can significantly influence the result (not even the last one). By increasing length L, you can make it progressively more expensive for any miner to cheat continuously.
@akhmed That's an interesting idea, but as L grows, any single miner's influence will *grow*, not decrease, since on average all of the honest miners are putting out 1s and 0s with equal probability, so every block the malicious miner makes shifts the total 1s vs 0s more unequal
The manipulation potential of this technique is worse than you describe here. Imagine a miner who has entered 100 addresses. He will have to pay 100 deposits, but for each of his entries he can choose whether to reveal so he can check every combination, giving him 2^100 chances to win...or at least, as many chances as his hardware can generate in a few seconds.
That's exactly what I described... "Enter enough times, and you get a new choice for each entry". I.e. you get 2 choices per entry so n entries allows 2^n choices
I think you can manipulate the result more efficiently than that: Create `m` entries `N0, ..., Nm` where `m` is the number of bits in each entry and `Ni` is `m-(i+1)` zeroes followed by a 1 followed by `i` more zeroes, e.g. `N3` = 0...01000. In the reveal stage you may now flip the `j` th least significant bit in the XOR'd combination of entries by revealing your corresponding entry `Nj`. Therefore you can change the XOR'd combination to whatever you like and in particular ensure that `N % numPlayers` is equal to one of your revealed entries.
Could you give an example for the step 4? What do you mean by: " along with ether greater than or equal in value to the value of the random number." ? If random number is 10, isn't it expensive to send 10 ether into the contract? and What is the smallest and largest value for N? @Tjaden Hess♦
This solution is memory wise inefficient. If each user buy 100 tickets they have to generate 100 different hashes (they need to make 100 transaction to send their hash to the contact) , where the hundreds of hashes also needed to be stored in the contract's storage. @Tjaden Hess♦
At step 8: `N`s and `BLOCKHASH` all together could also be `XOR`'d in order to generate another random number? @Tjaden Hess♦
@TjadenHess I may be missing something here. Why not just wait for the next block and use its hash as Random number?
I guess I miss something, but at step 8, why XORing, knowing that the last `N` can jeopardize the randomness of the output? (as you suggest in your first footnote, saying "`N XOR N`") I was thinking about concatenating all `N`, then hash the result. That way, no one can "cancel" the entropy, only merely fail to contribute to it (eg. with a remarkable value such as `0`). Oh, and thank you for your contributions to this question!
The exact function used to calculate the final result doesn't matter much, you could pairwise hash as well. The point is that the Ns are committed beforehand so there's no way of knowing what the contribution will be. It's sort of similar to the resoning behind a one-time pad; each bit has a 50/50 chance of being 1, so there's no way to pick your N to manipulate it.