-
-
Save alexvandesande/259b4ffb581493ec0a1c to your computer and use it in GitHub Desktop.
| contract random { | |
| /* Generates a random number from 0 to 100 based on the last block hash */ | |
| function randomGen(uint seed) constant returns (uint randomNumber) { | |
| return(uint(sha3(block.blockhash(block.number-1), seed ))%100); | |
| } | |
| /* generates a number from 0 to 2^n based on the last n blocks */ | |
| function multiBlockRandomGen(uint seed, uint size) constant returns (uint randomNumber) { | |
| uint n = 0; | |
| for (uint i = 0; i < size; i++){ | |
| if (uint(sha3(block.blockhash(block.number-i-1), seed ))%2==0) | |
| n += 2**i; | |
| } | |
| return n; | |
| } | |
| } |
@aakilfernandes Yes, there is a big benefit as it spreads the influence of the final number with a long chain of miners.
@tjade273 actually that's not how the second function works
Suppose you want make a lottery where everyone tries to guess a number that will happen on the block X, based on input starting from block X - 32 . Tickets are only sold until block X - 33 and from that point on each miner will decide the fate of the lottery ticket.
There are four billion possible lottery tickets (2^32). The first block X-32 will define if it's an odd number or even number, by starting the lottery ticket at 0 or 1. The block after that will decide if they add a 2 or won't. The block after that defines if it gets added a 4 or won't and so on. After 32 blocks, each block is basically halving the possible outcomes.
Notice that each miner doesn't actually decide: if the number is added or not is random, all the miner gets to do is – if they are lucky enough to find a block at that time – they get the choice to discard one of the options and therefore forfeit their block rewards. In order for a lucky number to be picked one single entity must have the ability to mine 32 blocks in a row while discarding about half of them.
@alexvandesande Any way to reduce the influence of a miner per block to half a bit, instead of a full bit?
Say a miner buys half of all of the tickets, such that only the last block will determine whether or not they win. So, assuming we use 5 blocks, they buy numbers 00000 - 01111 (in binary). Then, they just need to make sure that they are the miner of the last block, and they are given a 3/4 chance of winning, and more if they can find another block before someone else does. This is the same result as if only one blockhash was used. That's an extreme case, but it illustrates how an attacker can perform the same attack on both systems.
Worse, For every block the miner mines, they get a choice, and thus better odds.
If an attacker buys one number out of 32 and mines 2 of the 5 blocks, they have a (1/2)^3 _(3/4)_2 = 9/128 = 7% chance, as opposed to a 1/2^5 = 3% chance for a fair player.
Alternatively, assuming only one blockhash is being used to choose from the same 32 numbers, and the miner is at worst capable of mining 2 blocks in a row before anyone else can publish theirs, the probability of the miner winning is 1-(31/32)^2 = 6%. Thus, not only is using multiple blocks not better, it can actually be worse.
In practice, the way the attack would be carried out is that the attacker would randomly choose numbers, and then choose to discard a blockhash if it would cause more than half of their numbers to be out of the running. Thus each block they mine gives them a better chance of winning.
The key point is that although a miner would need to mine 32 blocks in a row, and discard half of them in order to force the contract to give a particular number, they still have influence over the outcome, and the more choices you give them, the more influence they have.
@alexvandesande thats quite clever
@tjade273 thats a good point. My understanding is you would be able to price tickets so that such an attack is practically impossible (simply due to liquidity constraints of an attacker)
The problem is that even if the attacker only buys one ticket, he still gets a greater chance of winning. If the expected profit is more than 5 ETH, it makes sense for him to discard the block. Worse, if there are multiple lotteries at the same block height, the incentives are additive, so you have to be sure that no one else is using the same hash as you to run their lottery.
The liquidity argument doesn't really make sense to me. As long as you stand to win more than 5 Ether, you have an incentive to discard the block. Getting enough tickets to make your expected return go above 5 ETH might be expensive, but only if the chance of winning at all is very small, which will not be appealing to players.
I just started working on a lotttery contract, but with Bitcoin block hashes taken from BTCRelay, so that the cost of discarding a block is $4500 instead of $8. Then I allow a maximum of 1000 ETH to be paid out per block, and carry over excess earnings into future blocks.
True. I was following your 3/4 scenario but the same holds true for lower numbers as well.
I just started working on a lottery contract, but with Bitcoin block hashes taken from BTCRelay, so that the cost of discarding a block is $4500 instead of $8
Very cool. I didn't realize BTC relay had progressed that far yet.
It's fully functional on the testnet, just going through some code review before it's deployed on the mainnet.
@alexvandesande
Could we change n += 2**i; to n |= 2**i; for lower gas cost ?
+ is ADD
| is OR
it doesn't work.
Tried to run it in remix ide:
Error encoding arguments: TypeError: Cannot read property 'toArray' of undefined
Hey Guys!
I'm new to solidity, so please apologize my ignorance. I'm not sure if I get it, but If you need to provide a random "seed" as input, then this code is only a transformation of a random number?
Thanks
@felipe-cunha as you see in the Solidity documentation here, the seed is concatenated to the blockhash (which is another seed) for added complexity. No randomness was generated if I'm not wrong, only manipulation of a number which was not known until the block is mined.
Hey @alexvandesande, in randomGen() which part of the function ensures that a number between 0 and 100 is generated? Is it the %100?
In the case of the lottery, the seed provided to the function can be used to remove the interference from all the parties. Like this:
The seed is selected by the 'house' previous to the beginning of the lottery. The house encrypts it and provides a public key for it.
When the block at which the lottery plays is reached, the house uses the seed (known only to the house until that point) and the blockhash to calculate the random number. The house publishes the private key allowing the seed word to be decrypted so that everyone who wishes can verify the process.
In this approach:
The miners can influence the blockhash but not the seed.
The house knows the seed but not the blockhash
The ticket holders can verify the seed.
Other than that, the blockhash should work perfectly fine for random number generation in anything else.
Any objections to this?
No, only the last piece of input to the random number matters, since all of the previous blockhashes can be seen beforehand.