search

divergencetech / ethier

Golang and Solidity SDK to make Ethereum development ethier
MIT License
217 stars 23 forks source link

Rejection sampling introduces unreliable gas estimations #5

Open cxkoda opened 2 years ago

cxkoda commented 2 years ago

Rationale

The current implementation for drawing uniformly random numbers in a given range is based on rejection sampling, see https://github.com/divergencetech/ethier/blob/a0b71a96a51e5a9080e0f0bbbbfac11e8e95a2af/contracts/random/PRNG.sol#L153

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 commented 2 years ago

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 commented 2 years ago

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.