4 ms·

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 subpo

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?

doomrobo 11y ago
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.
- aakilfernandes 11y ago
  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.
  - doomrobo 11y ago
    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.
    - aakilfernandes 11y ago
      I don't think your math is right there. You can check that by plugging in the values of a much simpler lottery. 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.
      - doomrobo 11y ago
        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 :)

doomrobo 11y ago

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.

aakilfernandes 11y ago
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.
- doomrobo 11y ago
  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.
  - aakilfernandes 11y ago
    I don't think your math is right there. You can check that by plugging in the values of a much simpler lottery. 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.
    - doomrobo 11y ago
      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 :)