Rejection sampling introduces unreliable gas estimations

[cxkoda]

Rationale

The current implementation for drawing uniformly random numbers in a given range is based on rejection sampling, see

ethier/contracts/random/PRNG.sol

Line 153 in a0b71a9

for (result = n; result >= n; result = read(src, bits)) {}

The associated gas costs are therefore not fixed but might vary from call to call depending on the required iterations. This makes gas cost estimations unreliable because the state of the random source might change until a given transaction is included in a block. In the worst case, this could lead to failing transactions.

Potential solution

Change to a random number sampling scheme with constant gas cost.
I did not do any proper research on potential algorithms yet, but one that comes to mind would be modulus sampling result = BigUniformRand % n - trading exact uniformity (introducing mod biases) for a constant gas cost.

[ARR4N]

Thanks for picking up on this! It's subtle but important.

IIRC it's possible to use arithmetic coding as an ideal solution to not "waste" bits through rejection. That said, I'm recalling from many years ago and also couldn't tell you much more than that so it may be horrendously inefficient. Let's look into it before we decide on a fix. https://en.wikipedia.org/wiki/Arithmetic_coding

[ARR4N]

https://web.archive.org/web/20140513134705/http://www.cs.toronto.edu/~mackay/itprnn/ps/105.124.pdf describes the process. I'll start reading up on it but my gut's telling me it will be too gas intensive.