Generating randomness

Posting here in response to Discord questionbecause this is a topic I suspect we’ll keep coming back to. The Discord question from GemCollector: " Is there any way to generate randomness on chain atm?"

The following is from a discord thread (Discord) a few weeks back:

Blockquote

apt-get-420 05/29/2022

Is there any way to produce pseudorandom numbers on Move?

Magnum6 05/29/2022

@Qwertey6 (Jake) wrote a clever random generator at the hackathon. I think that’s in a repo somewhere. I’ll find it in a bit.

Qwertey6 (Jake) 05/29/2022

there’s a BST module that turns any “MoveValue” (ie vector, int, struct, anything) into a Vector<u8>. There’s another module (Hash iirc?) that exposes a SHA function, which takes an input Vector<u8> and returns a Vector<u8> which is the SHA of the input. Since SHA is a cryptographic hash function, there’s a uniform distribution in the u8 values returned (ie the number 34 occurs 1/256 of the time, as does 1,2,3, …)

[4:09 PM]

Based on your requirements, you can implement increasingly “uncontrollable” random generators. The implementation @Magnum6 mentioned uses (essentially) a Counter-type struct that lives on each user’s account, and any time you need a random number, you can increment the counter, stick the value in a vector, and SHA it. If more “uncontrollability” is desired, you can increment the counter, stick it in a vector along with the current timestamp (which, for the user, is harder to control/predict).

Qwertey6 (Jake) 05/29/2022

I made a new version I call a k-way tug-of-war, where there is a SINGLETON random number generator, which holds a buffer of vec, and when a user requests a random number, a number (or more, if eg u64 output is desired) is fetched from the buffer. If the buffer is empty, then a new SHA is calculated from “counter++” and the current timestamp. This way, if you have an agent that’s trying to figure out what the random number WILL be ahead of time, this makes it extremely hard for them to “control” the output (ie get the specific number they want), as they do not know: 1. the exact timestamp of execution (but they can control it to a small degree by spamming requests), and 2. they don’t know the value of the counter (it’s private and lives on another account), and 3. they don’t know how many numbers are remaining in the buffer, and finally: 4. (why it’s a k-way tug-of-war) they don’t know how many other users will try to request a random number at the same time. In fact, the more malicious actors are using this system, the safer it is!! For k actors, each one will be trying to “pull the rope” (get a specific number), which will interfere with each other k-1 actors pulling the rope at the same time.

I made a new version I call a k-way tug-of-war, where there is a SINGLETON random number generator, which holds a buffer of vec, and when a user requests a random number, a number (or more, if eg u64 output is desired) is fetched from the buffer. If the buffer is empty, then a new SHA is calculated from “counter++” and the current timestamp. This way, if you have an agent that’s trying to figure out what the random number WILL be ahead of time, this makes it extremely hard for them to “control” the output (ie get the specific number they want), as they do not know: 1. the exact timestamp of execution (but they can control it to a small degree by spamming requests), and 2. they don’t know the value of the counter (it’s private and lives on another account), and 3. they don’t know how many numbers are remaining in the buffer, and finally: 4. (why it’s a k-way tug-of-war) they don’t know how many other users will try to request a random number at the same time. In fact, the more malicious actors are using this system, the safer it is!! For k actors, each one will be trying to “pull the rope” (get a specific number), which will interfere with each other k-1 actors pulling the rope at the same time.

Qwertey6 (Jake) 05/29/2022

I expect this last method to be the most expensive, as it’s not parallelizable whatsoever, where the version that stores a Counter on each user’s account is 100% parallelizable across users. A tradeoff must be made (at least in the approaches I’ve come up with) between “uncontrollability” and performance. This post was longer than I thought it would be lol

5 Likes

This is very useful information, thank you! I have also seen Oracle based solutions, like chainlink VRF: Introduction to Chainlink VRF | Chainlink Documentation

1 Like