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?
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
N before hashing. Otherwise, another user could simply submit an identical hash, then wait for
N to be revealed, then submit that.
N XOR N equals 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
N has 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.
Note that with linagee's suggestion, you're not just trusting random.org, you're also trusting Oraclize. Oraclize publish a TLS notary proof to show that the data they're giving you really came from random.org, but that's not enough for this case: We need to know that this was the only data they got from random.org. Otherwise they could keep trying and throwing away random numbers from random.org until they got one which won their bet, and you would have no way of detecting this.
You could use https://api.random.org/json-rpc/1/ which gives you a random source of data through JSON and Oraclize which allows you to make use of the feed inside an Ethereum contract and optionally have it strongly authenticated as having come from random.org. (Along with existing methods of using the hash of the block, timestamp, and such.)
You would be "trusting" random.org to feed you random data. You might mitigate the risk by using multiple sources of randomness.
Since different contracts are securing different amounts of value, at the opposite end of the spectrum to RANDAO is the simple BLOCKHASH.
If BLOCKHASH may suit your purpose, it's highly recommended to review the question (below is only a snippet):
As a general rule, BLOCKHASH can only be safely used for a random number if the total amount of value resting on the quality of that randomness is lower than what a miner earns by mining a single block.
The short answer is you can't. RANDAO works, but it's slow, and if your game is popular, there will be a strong incentive for people to game applying the last number.
I suggest using an oracle to provide randomness. (as mentioned in Tjaden Hess' Notes and Alternatives 2c.) The two major benefits are you can strongly assert that your number is independent of any other wager, which is vital to pricing the risk of using that number. Secondly, there is effectively no limit on entropy throughput. If there is a marketplace of oracles, then you can leverage the irrevocable history of the blockchain to model the likelihood that a given oracle is colluding with players or not. Of course, the players, the house, and the oracle all provide their own entropy. Other features such as whitelisting, blacklisting, bonds asserting non-collusion, etc etc can be added as desired.
It seems to me the various suggestions presented here all have in common a model in which a smart contract is acting as the server in what is essentially a regular ol' single-server/multi-client architecture, and much of the concern is that a miner will game the system - which is sorta the problem that has always existed when there is a single trusted server.
Why not just turn the thing on its side and simply not involve the contract at all in the random number generation process?
A lottery-like game might work this way:
Each gambler submits a transaction to the lottery contract containing the fee, a desired "picked" number and an encrypted random seed value. If the same gambler wants to pick another number only the fee and pick are required - the seed is per-gambler, not per bet.
After betting closes, the gambler sends another transaction - this time containing nothing but the key to decrypt his seed.
After everyone has provided decryption keys (or a sufficient amount of time elapses) each gambler fetches all of the keys and encrypted seeds and computes the "real" random number - probably just a modulo-sum of the decrytped seeds. If it is one of the gambler's picks, a transaction is sent to the contract that causes the contract to verify that the gambler provided a seed, verify that the winning number supplied in the transaction is in fact correct and was picked by the gambler, and then award the winnings.
Lots of hand-waving and left-out details here, but I believe the basic idea is sound.
Lets think that you are using a block hash to decide a lottery winner and miner A participates to that lottery and buys one ticket. Then he mines many valid blocks and throws them away, if they are not suited to his ticket.
In practice, every valid block that a miner throws away costs him 5 ethers. If your lottery's odds are so, that miner A has to eg create 1 000 000 valid blocks till he finds a proper block for him to win, he wil throw away 5 000 000 ethers.
If your lottery's main win is 1 000 000 ethers it makes no sense for a miner to throw away 5 000 000 eth to win 1 000 000.
I have an idea that builds on Tjaden's protocol that I outline here:
It solves the problem of having to put up a large security deposit in lotteries. Would appreciate some feedback.
Marco from Oraclize here. You could use the Oraclize Random Data Source, which leverages a Ledger Trusted Execution Environment.
The Random Data Source is significantly safer than using Random.org with TLSNotary and using the blockhash to determine a random number, and it less difficulty and expensive than others commit-reveal schemes.
Another way to generate random numbers could be to distribute various sources of randomness into the platform to seed the winning ticket. For instance we could use the cents of the closing prices of every stock traded in the main stock exchanges in the world. It would be nearly impossible to make all the stock exchanges work together to tamper the lotto.
The closing prices are shown by various services including Yahoo, Google, Bloomberg, etc. so they can work as a kind-of a public ledger to verify the prices are correct.
Also since so many direct traders, algorithms, company traders, etc. are involved changing those prices, it would be nearly impossible to predict what the very last traded price will be or wait for the very last second to be the last person to trade a stock.
Try the following algorithm to prevent cheating.
The idea is to use hash of a block but the block number is not known for miners/participants and organizers to prevent cheating.
- On start organizer defines a random uint64 - key number to be used in the winner random number calculation. The uint number is big enough and known to organizer only on start.
- Organizer fixes the key number by providing hash of sum - the number plus current block hash (as a salt). The key hash is stored in the Lottery contract and available for all the participants. Then key hash is used to prevent organizers cheating and fixes the key number.
- Participants buy tickets and the Lottery contract stores all the participant addresses. The addresses are used on winner calculation as well.
- When conditions are fulfilled (e.g. all the tickets are sold or necessary amount of blocks are generated or just after some time) organizer starts winner calculations.
- Organizer provides the stored key number and confirms the number is exactly the same by calculating the key hash (entered on init).
- The key number is added to the sum of addresses and we got mod 255 of the sum to detect number of block which hash is used to detect winner. Key number + address1 + address2 ... + addressN % 255 = number of winner block (the block hash is used to get winner number)
To person who want to guess winning number it is not possible to get the number - in the contract we have just hash of the number. The number is rather big uint64 (or could be even bigger) to prevent "unhashing" the number. For organizers the number is fixed and is futile because all the tickets owners addresses must be known to calculate the winner.
Opinions? Any holes in the logic?
I created a separate question but it could be answered here as well.
You need to use a third party to generate randomness.
Contract accounts only perform an operation when instructed to do so by an Externally Owned Account. So it is not possible for a Contract account to be performing native operations like random number generation or API calls – it can do these things only if prompted by an Externally Owned Account. This is because Ethereum requires nodes to be able to agree on the outcome of computation, which requires a guarantee of strictly deterministic execution.
I don't know the best secure method, but please see bellow a list of Vulnerable implementations (so finally do not use):
- PRNGs using block variables as a source of entropy
- PRNGs based on a blockhash of some past block
- PRNGs based on a blockhash of a past block combined with a seed deemed private
- PRNGs prone to front-running
You may take a look on Predicting Random Numbers in Ethereum Smart Contracts, which explain all security issues relative to different kinds of pseudo-random number generator (PRNG) implemented in (a lot of existing) Smart Contract.
How about this flow:
1) Each user generates a string "I am a part of the lottery and my number is 8272143" (Secretly) where 8272143 is the self chosen number.
2) Each user encrypts its own string with a self chosen password (secret)
3) Each user publishes the encrypted string, so now everyone can see all the encrypted strings
4) When it is decided to not allow any more participants, all users publish their self chosen passwords and all strings are decrypted. Users who do not publish their passwords are excluded from winning.
5) Everyone can confirm, that each player speaks the truth about their password, as the first part of the string must be "I am a part of the lottery and my number is " so there is no way to fake another number at this point.
6) All the strings are now concatenated, and a hash is generated. This hash is the final random number! In case of a lottery, you could pick the number closest to the hash, but this is just a case specific detail.
This way, there will be no waiting for blocks to complete. Only brute forcing decryption of the strings will allow for an advantage. This will be avoided by using strong enough encryption.
(I am a total rookie in this field, so bare with me if this is just nonsense.)
I realise, that if 2 clients work together, the last client can choose to wait publishing his password and to be excluded in case his friend will win this way. A solution can be, that all users have an amount of ETH on the line which they will have to pay of they do not publish their password. All in all, this solution is not very sexy, I admit.
Why not just use the official lottery figures from the television? For instance, the German Lotto Zahlen. Then you build in a voting mechanism where the players can vote on the winning numbers after the lottery numbers have been drawn and published on television. To incentivize also losers to vote, you could offer players to reimburse say 5% of their stake if they decide to vote and their vote turns out to find consensus among all players
Just a update to this question, but this time it use a technique call verifiable delay function (vdf). It was built based upon time lock puzzle invented by Ronald L Rivest et al. The core idea behind is that if you can't calculate the result in a set amount of time, then the result is pseudo random. So with that in mind, vdf is a function which take in an input and it take maybe 1 hour to compute (You can change the time in the setup phase of this function), then it output the result and a evidence that this result is indeed calculate using that input in no time.
So the idea is just like Perfectly Decentralized Lottery-Style Non-Malleable Commitment that was proposed in this question answer but we just need to add vdf into it in a step before
- The Ns are all XOR'd together to generate the resulting random number.
So our step is:
With that result we let it run through our vdf function (The time to calculate it must be longer than the submissions time to ensure that the last submit cannot calculate the final result).
Then You public the vdf function result to everybody, so that everybody can verify that the result is indeed calculate using the input
The reward is just the same as the answer propose.
But i just simplify to the core idea behind it, the beauty of this is in the math that implement it.
Verifiable delay function paper: https://eprint.iacr.org/2018/601.pdf
You can also check this paper which talk about 2 vdf: https://crypto.stanford.edu/~dabo/pubs/papers/VDFsurvey.pdf