2

Lets say you have 50 tickets to a raffle. You choose to return 4 random bytes from the ledger proof RNG(https://github.com/oraclize/ethereum-examples/blob/master/solidity/random-datasource/randomExample.sol). The bytes generated can return a number up to 2^(8*4) = 4294967296.

You have 50 tickets -- so the RN’s 4294967251–4294967296 represent a slightly higher chance of winning for ticket holders 1–46 versus a slightly less chance for tickets 47–50. The disparity of fairness is tiny… but non-zero.

Do you know any good solutions to this problem?

1.Discarding the numbers 4294967251–4294967296 has cost value when paying Oraclize.

edit: So to clarify I am completely convinced by the tinyness of the disparity between tickets in this case and when using the full 32 bytes. However, I neglected to mention I feel the need to accommodate a 'laymens perspective' (There is lottery for who gets to go to Mars, and my ticket has miniscule chance less than my neigbours ticket of getting to go -- I am a laymen and don't really understand statistics, bias, etc... all I understand is that my neighbour gets one more chance in 10 googleplexes than me to go). So it seems like rejection sampling is the only way. But it means I have to code for making multiple calls vs adapting the random bytes somehow.

Improve this question
4
  • 1
    I think you should probably just discard those numbers or ignore the bias. Those numbers occur roughly once in every 100,000,000 trials, so the amount of bias seems fairly insignificant, as does the cost of generating a new random number.
    – user19510
    Jan 22, 2019 at 2:38
  • Yeah, I agree it is tiny. But that would be of little consolation to a person participating in this raffle. If your life or your money depends on a raffle you want it to be fair.
    – Duncan Brain
    Jan 22, 2019 at 17:10
  • 1
    So just pay everyone when that event occurs. Assuming there's a house, increase the house advantage by a millionth of a percent or so to cover it (and increase profits too). But if you don't want to do that, take my second suggestion: just choose another random number.
    – user19510
    Jan 22, 2019 at 17:21
  • Yeah, no house. So far it is looking like the rejection sampling is the only way to keep it fair.
    – Duncan Brain
    Jan 22, 2019 at 17:25

2 Answers 2

Reset to default
3

So your solution of discarding the numbers is known as rejection sampling and is indeed the way to solve your issue for your given inputs. As you've also noticed, there is a cost associated with this due to the nature of Oraclize.

If you prefer not to have that extra cost, then your only other option is to remove this biasing affect of the modulo operation by changing the range you restrict your numbers to to a power of 2.

So by selling either 32 tickets, or 64, you won't have to perform rejection sampling and you won't have any bias after taking the modulus.

Improve this answer
2
  • Yeah, it seems like it would be a useful upgrade to the Oraclize service if possible. Also, thank you for the technical term for it! I was hoping a technique exists that I could cast the range over the ticket numbers somehow though. Something analogous to 0-85899345.92 is ticket 1, 85899345.92-171798691.84 is ticket 2 etc.
    – Duncan Brain
    Jan 22, 2019 at 17:15
  • Accepted this answer as best, seems like the only answer that --barring a change in the Oraclize ledger proof options -- will fit my (edited) description.
    – Duncan Brain
    Jan 22, 2019 at 23:17
0

The best way to bring down this bias, to hopefully negligible levels, is to use full 256 bits of randomness in any such cases, and the bias approaches 0. The lower the randomness range, the lower this bias.

Here is a google sheets spreadsheet to help visualize the biases for a random range of 10; from 4 bits to 50 bits of randomness: https://docs.google.com/spreadsheets/d/1sbMeI-CgRdc95VKAXO-KgBmmxCoRVO14KY4UdBla3Bk/edit?usp=sharing

4 bits of randomness will result in a bias of the first 6 numbers being twice as likely to occur, or a 100% bias, obviously very bad. At 32 bits, this bias drops to ~0.0000002328306%.

A formula to find the bias you can use is 1 / ((2 ** random bits) / range)

Here is the equivalent formula plugged into WA achieving the approx result for 32 bits stated:

WA 32 bit formula link

Here it is for 256 bits of randomness for a range of 10:

WA 256 bit formula link

Its bias is 8.6e-75 % , that's a lot of zeroes, and I would say it's fair to consider the bias affecting anything within our lifetimes as being extremely negligible.

If any math is incorrect, please let me know, as it was practically just formulated on whims, but appears correct to me and meets what I expected.

EDIT: After looking more into the equation, the above provides a decent approximation, especially with higher numbers, but the correct equation is

1 / floor[ x / y ]

where x is the highest randomness provided, and y is the max desired range from 0...y

Improve this answer
4
  • So Oraclize only has options in bytes, so the minimum bits is 8, and multiples of 8... for anyone else looking at it. So I get that the bias is small for my values, but perception is everything, so rejection sampling or some alternative(know any?) would be best to manage that perception. I don't know much about bias though, where did you get your bias equation? Are you maybe overestimating, and is this better?.. 1 / ((2 ** random bits) / rangeRemainder) where rangeRemainder = (2 ** random bits) % range.
    – Duncan Brain
    Jan 22, 2019 at 20:17
  • Solidity has bitwise shift operators, so you can convert the bytes into equivalent bit sizes you need. The formulas should be looked at as approximations for biases that could result for said range + random bits. Again, they will probably not give exact amounts, but at the very least should showcase that the numbers get so large at some point, that they are unlikely to affect anything for the foreseeable existence of humanity. And the takeaway is to use 256 bits to modul against, if you are working with a set that would require rejection sampling.
    – DenisM
    Jan 22, 2019 at 20:24
  • Yeah, I get the stats but it seems like rejection sampling is the only way to tackle a perception that the average person would understand. Also the Ledger-proof from Oraclize mentioned in this question only accepts a uint value for N bytes between 1 and 32 under a require(,). So it seems to me a requirement of using their contract 'ethereum-api'. So I don't think the bitwise shift will help unless you want to code your own ledger-proof machine and api...right? or truncate the returned bytes, seems inefficient for spending gas. I'm new and learning though and just trying to clarify for noobs.
    – Duncan Brain
    Jan 22, 2019 at 21:03
  • 1
    Just adding this: The bias can be calculated for a random number picked from a range 0 - X and moduloed by x as ( X mod x ) / X (with this being the maximum it can possibly deviate from a normal distribution byi...)
    – gskapka
    Jan 23, 2019 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.