A novel on-chain Gaussian random number generator

Abstract

Currently, randomness, be it on-chain or off-chain, is only uniform. Gaussian randomness is made available by simply counting 1’s in the binary representation of a hashed value calculated by the keccak256 hashing algorithm. It is simple, costs little gas, and can open up many possibilities in gaming and DeFi.

Motivation

DApps may desire to generate some numbers more frequently than the others, but currently, the randomness produced by keccak256 hashing algorithm is uniform in the domain [0, 2**256-1]. That is limiting what is possible with Solidity and blockchains. This on-chain Gaussian RNG can satisfy such needs.

Specification

The algorithm relies on the count of 1’s in the binary representation of a hashed value produced by the keccak256 hashing algorithm. By Lyapunov Central Limit Theorem, this count after proper transformations, has a Gaussian distribution. The theoretical basis, condition and proofs as well as Solidity implementation and practical issues can be found here.

Backwards Compatibility

This is a brand new algorithm and there is no backwards compatibility issue. Actually, it is already with Solidity. It was just never brought to light.

1 Like

You could also apply the quantile function of a probability distribution to the uniformly distributed value in order to get a variable with the specified distribution.

Inverse CDF is a common tool in generating random numbers, however, it would be challenging to express it and apply it on-chain cheaply.

I see. Do you have gas estimates? It could be interesting to compare the gas usage of this method to other methods such as the Ziggurat algorithm. I have a feeling that the Ziggurat could perhaps be more efficient, especially if many samples are computed, since each sample could consume just a small part of the hashed value, so you would need fewer hashings.

Feel free to run the smart contract in the repo.

Many algorithms that are working in the traditional setup do not necessarily work in Solidity or on a blockchain. I do not think Ziggurat algorithm or alike can be implemented in Solidity at this point, when floating numbers are not even supported yet.

The algorithm I am proposing does not run with floating numbers or sophisticated mathematical calculations, instead simple counting is sufficient to generate Gaussian randomness.

Given the limitations imposed by Solidity and blockchain, this is a non-trivial step forward.

I don’t think floating point calculations are actually needed for the Ziggurat if you use the same scaling trick as in your algorithm.

I agree that your solution is simple, but I’m not quite convinced that it is more gas efficient than the Ziggurat, although I might be wrong. One drawback of Ziggurat is the need for a lookup table, which could perhaps outweigh the gas savings on computations.

The advantage of using an algorithm like Ziggurat however, is that it could be used for more distributions, while it is harder to see how your algorithm generalises. If the Ziggurat turned out to also be more gas efficient, it would be a win win.

I’m not trying to nullify your work, just trying to give some constructive feedback and possible alternatives.

Unfortunately, the Gaussian pdf is not available to do any rejection sampling including Ziggurat in the first place. It would be great if someone can make it available on-chain, and that can definitely open up new possibilities.

When tens of token standards are designed for very specific needs, the idea of finding any generalization seems unrealistic if not impossible at all.

Yeah, I see. You would need to find a way to approximate the pdf using integer arithmetic, which would be tricky, but perhaps not impossible. The devil lies in the details.

Talking about generalization, this method can do well in generating RNGs for a few discrete distributions such as Bernoulli, Binomial, Negative Binomial, Poisson with a small parameter, and Geometric distributions. Continuous distributions are not possible to be generated with this methodology. Gaussian distribution, however, happens to be a special case since it can be approximated by discrete distributions.