search

ethereum / solidity

Solidity, the Smart Contract Programming Language
https://soliditylang.org
GNU General Public License v3.0
23.48k stars 5.8k forks source link

An on-chain Gaussian random number generator #11829

Closed simontianx closed 3 years ago

simontianx commented 3 years ago

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.

axic commented 3 years ago

I suggest you bring this up on either https://ethereum-magicians.org or https://ethresear.ch.

This issue tracker is not the appropriate place for this discussion, unless you are asking for a language feature.

simontianx commented 3 years ago

@axic Yes, this is actually the purpose of bringing this up. Looking for a clue where this should go. Thanks.

axic commented 3 years ago

Do you see any strong reason why this should be a language feature, when you have proven it can be implemented as a library?

simontianx commented 3 years ago

Do you see any strong reason why this should be a language feature, when you have proven it can be implemented as a library?

Actually this is already a language feature. It is just not made known to people. My initial thought was to briefly mention it in the language doc.

Talking about the library, do you have any specific recommendations? I have made a post on the OZ forum and see if this would go somewhere there.

axic commented 3 years ago

Under language feature we usually mean syntactical features supported by the compiler, which can not, are hard, or are very inefficient to express otherwise. It seems that your implementation can be perfectly expressed with current language constructs.

My initial thought was to briefly mention it in the language doc.

We do not talk about third party software too much in the documentation, but if you feel strongly this should be mentioned in the documentation, then please feel free to create a pull request changing the appropriate section (where randomness is discussed). On that pull request the team can chime in, but my expectation is that it won't be merged.

Talking about the library, do you have any specific recommendations? I have made a post on the OZ forum and see if this would go somewhere there.

Regarding libraries you can either champion your own library, or try to get the feature into another one. I think reaching out to OZ, as you did, is a good idea, but I can't predict what will happen there.

simontianx commented 3 years ago

Thanks @axic . I think it is a very important piece of knowledge that everyone should know about. It may inspire people to come up with new applications with Solidity in areas such as on-chain financial derivatives, games, and etc.