Random number generator

[ilblackdragon]

Provide a library that would allow to draw a random number based on the random seed in a secure manner.

FYI. AssemblyScript sdk has a set of functions for this.

Possible implementation:

 use rand::rngs::StdRng;
 use rand::SeedableRng;

pub fn random_u64() -> u64 

 { let mut rng: StdRng = SeedableRng::from_seed(env::random_seed()); rng.next_u64() } 

Also security consideration is to make sure that different transactions in the same blocks will not be generating the same numbers.

[MaksymZavershynskyi]

Also security consideration is to make sure that different transactions in the same blocks will not be generating the same numbers.

CC @willemneal since near-sdk-as would need to implement it too.

[willemneal]

Hmm yeah I didn't consider the security implications when I made one for AS. Perhaps we should add the hash of the of the name of the contract. Though maybe this should be done by VM logic since this will be an issue for any language that expects env::random_seed() to be random.

In the runtime it seems that the random seed is created like

random_seed: if apply_state.current_protocol_version < CORRECT_RANDOM_VALUE_PROTOCOL_VERSION
        {
            action_hash.as_ref().to_vec()
        } else {
            apply_state.random_seed.as_ref().to_vec()
        },

But I can't seem to find where the random_seed in apply_state is set.

[bowenwang1996]

random_seed comes from the block vrf output. You don't have to worry about it and can trust its randomness. It is a 32-byte value.

[willemneal]

Is it is the same for each transaction in the block?

[bowenwang1996]

@willemneal yes

[bowenwang1996]

Looks like rand crate supports wasm, but we need to understand the gas cost to see if it is feasible.

[ilblackdragon]

Random seed needs to be unique and ideally per transaction non predictable from previous transactions. Right now it will be the same for all tx, which is highly suboptimal. @willemneal your suggestion would still make it the same per tx that goes to the same contract. E.g. if it's lottery - all tx in one block will win lottery.

I suggest we set random seed in apply_state to hash([block.random_seed, transaction.hash].concat())

[ilblackdragon]

@bowenwang1996 Yep, I don't think using rand crate is the right approach. Using some common pseudo-random generation from seed is probably fine, if we have good seeds per transactions.

[MaksymZavershynskyi]

I suggest we set random seed in apply_state to hash([block.random_seed, transaction.hash].concat())

Ideally we want it to be random per action. Also, transaction hash is manipulatable. We could argue that it is not easy to abuse, but it would require some solid math argument that we might not want to be involved with, yet.

I suggest we use the storage to keep the state of the seed used by the previous contract call, e.g. here is the algorithm for generating the seed:

prev_seed <- read_from_storage_or_default('RNG_SEED')
curr_seed <- hash(prev_seed, env::random_seed())
storage_write(`RNG_SEED`, curr_seed)

@bowenwang1996 Yep, I don't think using rand crate is the right approach. Using some common pseudo-random generation from seed is probably fine, if we have good seeds per transactions.

If we don't use rand crate then we would need to generate byte sequences on our own. In this case I would agree that we don't need to use rand crate (even though it might compile to small byte code, because PCG and XorShift are designed to be small https://github.com/rust-random/small-rngs/blob/master/rand_xorshift/src/lib.rs#L56-L65). Because most of the dApp developers will call it only once or twice in a single contract call. So we should be generating batches of new random bytes using recursive hashing like this: next_batch = hash(prev_batch) where prev_batch is initialized with curr_seed then we expose interface that implements next_u32, next_u64, fill_bytes, try_fill_bytes similarly to https://docs.rs/rand/0.7.3/rand/trait.RngCore.html

@abacabadabacaba What is your opinion on generating random bytes like this inside the contract?

[evgenykuzyakov]

Even though the uniqueness per call will be addressed with the next protocol upgrade, we still need to provide a random_u64() call in near-sdk

[austinabell]

I can take this, I'm thinking of something like using ChaCha20 rng using the env randomness seed or just have it generic based on a seedable rng to allow the user to use any Rng they want using this seed.

Definitely opinionated how the API would look like, so I'll just think through something and PR it and iterate from there, but does anyone have ideas about how this API should/could look like?

Edit: I totally get the concern about the randomness being influenceable by the tx hash, is there anything I can progress forward wrt keeping the seed state and/or fulfilling these concerns?

Seems like the constraints are:

1. Introduce more entropy than just the VRF hash from the block
2. Transaction hash should not be used by default for the seed, as it's influenceable to some degree
3. Minimize hash costs for the rng generation, but keeping as much integrity of the randomness (this doesn't seem like an issue as the randomness generator can just be generic, but maybe a good default would be good for an easy UX)