Hey everyone, EtherPot is a smart contract on the Ethereum Blockchain. That means that no one can steal the funds or cheat to win. The lottery is provably fair.
100% of finds (except for transaction costs that go to miners) get returned to the users who play.
I have some questions about the legality: Since the miners mine this contract (or include it in the blockchain, or whatever it is for Ether), does that make them violate the UIGEA [1] or other gambling laws? And since the OP lives in NY, does creating & posting this violate, for example, "promotion of gambling"-laws? [2]
You have no idea how hard this would be to do with a normal blockchain OP. In fact, I have spent literal months just thinking of ways to hack Bitcoin to do more complex smart contracts when its already possible with a few patches and extra OP codes.
It helps to stop thinking about blockchains and smart contracts. Ethereum is a global public computer where programs have their own storage space that can't be modified by anything other than the program itself. You can remove the trusted middleman from pretty much any system that used to require one. That is a significant fraction of the economy. It's a significant fraction of our society.
In one paragraph you've given me a better understanding of Ethereum than several blog posts and even the Ethereum website itself. Good job and thank you.
As I'm sure you know, Bitcoin's scripting language, as originally designed, is deliberately not Turing complete[1]. That's one of Ethereum's key points of difference with Bitcoin.
It's a very difficult challenge to keep control of resource use in any such decentralized system, and even more of a challenge when scripts can loop. It's going to be interesting to see if Ethereum can eventually work without frequent human intervention to modify the code. Even Bitcoin didn't quite get to that state yet.
This is really cool, but I think there might be issues with this:
1) The "random" selection of a winner seems to come from the modulo of the hash of a determinidtically selected block in the blockchain. How difficult would it be for someone to rig the lottery by simply waiting until the right moment and adding a block to the chain with a hash that would make them the winner?
2) Aside from the above, the "random" winning ticket index is not uniformly distributed unless the number of tickets is a power of 2, so there will be a significant bias in ticket selection.
Are these real shortcomings or am I misunderstanding something?
1. By failing to submit a block, a miner loses the block reward of mining that block (5 ether). The lottery is set up in subpots of 5 ether each, and each subpot is decided by a seperate blockhash. The miners could cheat, but their economic incentive is to be honest.
2. Not sure if I understand this. Can you expand on it a little more?
Ah, gotcha. I'll try to explain and correct my claimed in #2. So the winning ticket index is chosen as H % n (read: H mod n) where H is a uniformly distributed number between 0 and 2^256 obtained from the hash of some block (I'm just picking 256, I don't know what hashing algorithm is being used, but I'm assuming the digest's length is a power of 2), and n is the number of tickets that were bought. This computation does not produce a uniform distribution unless |H| is a multiple of n.
Here's an example {0..7} % 3 takes on the values 0,1,2,0,1,2,0,1. Notice that 0 and 1 appear 3 times but 2 only appears twice. So even if you chose x from a uniform distribution of the numbers 0-7, x % 3 would have a 3/8 chance of being 0 or 1, but only a 2/8 chance of being 2. This bias disappears only when the order of the set that's being randomly sampled is a multiple of the modulus. I hope that made sense.
So even assuming that the block hash is randomly distributed, you're still introducing a bias with the modulus. I think this might be fixable by simply multiplying the number of tickets everyone has by 2.
Edit: Strike that last part. If the number of tickets is not a power of 2, and the digest of the hash is a uniformly selected number from a set with a magnitude that is a power of 2, then there must be a bias in the winning ticket selection as it's performed in this code.
Thanks for the detailed explanation, I never thought about this.
If my understanding is correct, the overall level of bias is extremely small ~(total#oftickets/2^256) but its definitely something to consider. The only way I see around it is to toss out a block if its hash is in a certain range, that way there are the same number of hashes for each ticket.
I think the bias is much greater than that. The number of "extra chances" that are created from random H and the number of tickets n is 2^256 mod n. So if there are 6 tickets in the lotto, 2^256 % 6 = 4 tickets will have an extra chance to being selected as the winner. If I'm one of the unlucky ones, my odds of winning just went from 1/6 to 1/10. That's a 6.7% bias. The lucky ones' chances, on the other hand, went from 1/6 to 2/10 = 1/5 which is a 3..3% bias. The bias that a single ticken can get when there are n tickets is (2/(n+(2^256 mod n))) - (1/n) (except for when 2^256 mod n = 0. Then the bias is 0). The bias goes down as n increases, but I still personally wouldn't put my money in the pot.
The solution I've seen done (at least in the Rust rand crate) is exactly what you say: throw out every hash >= 2^256 - (2^256 mod n). This ensures that the order of your sampling set is a multiple of n. I'm not sure how you could go about that in Ethereum but it may still be possible.
My apologies. Yes that's correct. My mistake was reducing the set of choices to n + (|H| mod n). Your worst-case estimate of a total bias of n/|H| seems to be correct. I guess the question now becomes whether that bias is acceptable for the purpose of the lottery (I would say probably yes). Thanks for sticking with this thread :)
The entropy comes from the mined hash. Could a cartel of miners all decide to not submit hashes where they don't win? Wouldn't that make this technically exploitable?
Each block they do not submit costs them the block reward (5 ether). The jackpot is split into subpots of 5 ether for this reason. Each subpot is decided on by a single blockhash. The incentive of the miners is to play honestly.
Very cool idea! I just finished the Orielly book called "Blockchains" and it is exciting to see these applications now that I have a better understanding of Smart Contracts, etc.
Hm. The first transaction sent was in block 141,525, and the site says 6,800 blocks per round... but block 148,325 has passed without payout, so I guess I skimmed and missed something :/
27 comments
[ 2.7 ms ] story [ 66.6 ms ] thread100% of finds (except for transaction costs that go to miners) get returned to the users who play.
[1] https://en.wikipedia.org/wiki/Unlawful_Internet_Gambling_Enf...
[2] http://ypdcrime.com/penal.law/article225.htm
I must check out Ethereum when I get chance.
It's a very difficult challenge to keep control of resource use in any such decentralized system, and even more of a challenge when scripts can loop. It's going to be interesting to see if Ethereum can eventually work without frequent human intervention to modify the code. Even Bitcoin didn't quite get to that state yet.
[1]https://en.bitcoin.it/wiki/Script
1) The "random" selection of a winner seems to come from the modulo of the hash of a determinidtically selected block in the blockchain. How difficult would it be for someone to rig the lottery by simply waiting until the right moment and adding a block to the chain with a hash that would make them the winner?
2) Aside from the above, the "random" winning ticket index is not uniformly distributed unless the number of tickets is a power of 2, so there will be a significant bias in ticket selection.
Are these real shortcomings or am I misunderstanding something?
2. Not sure if I understand this. Can you expand on it a little more?
Here's an example {0..7} % 3 takes on the values 0,1,2,0,1,2,0,1. Notice that 0 and 1 appear 3 times but 2 only appears twice. So even if you chose x from a uniform distribution of the numbers 0-7, x % 3 would have a 3/8 chance of being 0 or 1, but only a 2/8 chance of being 2. This bias disappears only when the order of the set that's being randomly sampled is a multiple of the modulus. I hope that made sense.
So even assuming that the block hash is randomly distributed, you're still introducing a bias with the modulus. I think this might be fixable by simply multiplying the number of tickets everyone has by 2.
Edit: Strike that last part. If the number of tickets is not a power of 2, and the digest of the hash is a uniformly selected number from a set with a magnitude that is a power of 2, then there must be a bias in the winning ticket selection as it's performed in this code.
If my understanding is correct, the overall level of bias is extremely small ~(total#oftickets/2^256) but its definitely something to consider. The only way I see around it is to toss out a block if its hash is in a certain range, that way there are the same number of hashes for each ticket.
The solution I've seen done (at least in the Rust rand crate) is exactly what you say: throw out every hash >= 2^256 - (2^256 mod n). This ensures that the order of your sampling set is a multiple of n. I'm not sure how you could go about that in Ethereum but it may still be possible.
Imagine a lottery where instead of 2^256 there are only 100 possible outcomes and there are 3 players.
The odds are 34/100, 33/100, and 33/100 respectively. The bias is around 1/33.
But if I plug that scenario into your equation, I get:
2/(4+100%3) - (1/3) which is 2/5-1/3 which is 1/15.
Each block they do not submit costs them the block reward (5 ether). The jackpot is split into subpots of 5 ether for this reason. Each subpot is decided on by a single blockhash. The incentive of the miners is to play honestly.
https://etherchain.org/account/0x539f2912831125c9b86451420bc...