4 ms·

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

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

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 :)