Lottery Smart Contract: Can we generate random numbers in Solidity?
Imagine we are building a decentralized Lottery. What challanges does it have? Ever thought about is that even possible? In this article we are going to explore the possibile approaches for building a Smart Contract for decentralized lottery.
History of Lottery.
The earliest mention of lottery games is in China, during Han dynasty, a game called keno, which you can still find in many Casinos in Asia. The idea of the lottery is simple. The organizer is collecting the money from players, and a randomly selected subset of players, called winners, are getting rewarded, while others are loosing their money. The organizer usually is distributing one part of all collected money, which is putting him on always profiting position. French King Francis I used lottery to get money to state budget and help state budget. Countries like Thailand or Russia, are allowing only state issued lotteries, while other countries like Goergia you can register lottery company within minutes.
What is Lottery?
Well, everybody knows what is lottery. At least if you are reading this articles, you know what is lottery. I am asking to question, to go further and define the task we will solve in this article.
Design a Smart Contract, which accept a single number from users, after getting payed for 0.1 eth, add a pool of users. At some point stop allowing submissions of new user, then select a random number, distribute half of collected funds between users, who have submitted the selected number.
Why It is difficult?
Here are two challanges we will face in order to develop Smart Contract for a lottery.
- How we will generate random number? In Solidity, the code should be deterministic, as it will run on multiple nodes. Things like clock time are not available for generating random number.
- How does Smart Contract know the time for selecting the winner? Again things like clock time are not available in Ethereum Virtual Machine, as the code will be ran on multiple nodes, on different time.
The second challange can be solved using Ethereum Alarm. The blocknumber can be an alternative in a clock time, as it is always increasing by 1. As I want to focus on the first challage, in our smart contract We will make a public function which will trigger the winner(s) selection process. This can be triggered either by owner of smart contract, or by Ethereum alarm, or in any other way.
Generating (Pseudo)Random number in Solidity
We need a random number generator, which will generate the same number on multiple nodes, running multiple times. This is nonsense for anyone who knows what means random number. Then how we can accomplish that task? We need a random number generated once, and use that on different nodes. Well Solidity code will ran the code on multiple nodes, multiple times, but there is one running process which makes it unique among all the runs of the code. Yes it is the time when the code will be ran by miner, who will confirm the transaction. Let’s take a look to the block variable , which is assigned by miner to every confirmed smart contract. If we will look to block.timestamp constant, it is assigned by miner, no player have control on it. After it will be generated and assigned, it will be the same for all other nodes which will ran the Solidity code. block.difficulty also has some properties of randomness. Basically those two variables are completely out of control of the players, thus they can be used as a source for random number. They are generated only once by miner, and on all other nodes it will have the same value, thus random number will be generated on multiple nodes will be the same.
Sounds legit enough right? let’s look the Solidity code snippet for a lottery, everything should be self explaining. Note that in this code I have ignored gas limits, as this code is for demonstration of random number generation only.
Let’s explain the random() function. It depends on block.difficulty and block.timestamp, it is being hashed and encoded as a number. After encoding 256 bit hash to 256 bit integer, we are taking reminder by dividing 251, to get an integer in a range from [0, 250]. In our case 251 is prime number, whic is good. You are free to use any hash function Solidity is providing. But Why Hashing? All you need is just an operation which will convert given constants into fixed length bits. Hashing is not important here, as it is only incapsulating initial values, which is not giving us anything, as initial values they are available for any blockchain explorer.
But wait? can we trust miners?
The answer is NO!
More good solution?
A question was asked on stackoverflow about how lottery can be implemented in Solidity. A user Tjaden Hess has suggested wonderfull solution. Am implementation bellow is heavily based on his algorithm. We have simplified a little bit, also modified as our definition of the task was slightly different.
The paradigm is simple. As a source of randomness, there can be used adresses of players, or their numbers, as their distributions are completely random. We need also to hide those values for other players, in order to prevent attacks. We can not hide adresses of players, as they are recorded in the blockchain. So we need relay only on numbers submitted by our players. We may need from them to submit their hashes instead of numbers.
Let’s describe algorithm of the lottery smart contract bellow
- The organizer is starting to accept submissions
- User is generating their number, which they want to submit
- User is hashing it’s number alongside with their address
- User submits that hash only, instead of number
- At some point, ether by block number, or by the organizer, or when sufficient players are here, the contract is stopping to accept new submissions.
- Contract is opening new round of submissions. Now users who have previously submitted a hash, are required to submit the original number. Only users who have submitted before a hash can submit original value. Note that two rounds were created, in order to hide user’s numbers from other users, as we don’t want them to know the source of randomness.
- When the user is submitting original number, the contract is verifying it by adding it to the address of sender, hashing and comparing with previously
- Contract is stopping to accept new submissions.
- As we have list of original numbers, we can use them to generate final number. One possible solution is to XOR all numbers. You are free to do some creativity here.
- The half of the funds collected by the users are being split between users who have submitted number.
Bellow is an implementation of such lottery.
This idea of collecting hashes, then numbers, then generating pseudorandom number based on them, are used and implemented in Randao, think like a DAO for generating random number. I strongly encourage to go further to their documents.
Thank you for reading, if you enjoyed the material follow me on medium, and look to my other articles. Thanks!