Is it possible to use one verifiably random uint to uniformly generate a randomised distribution?

Question

Assume I have a selection of token IDs, for instance:

uint256[] public tokenIds = [1,2,3,4,5];

Now, incorporate a random number generated by Chainlink, let's say:

uint256 public randomNumber = 98346139420554933047845823368198375528330957585398133092102047626198817698038;

At the moment, the approach I am taking is basically to take this large random number and:

uint256 public randomOffset = randomNumber % tokenIds.length;

This gives me a random offset, so if for example, randomOffset ends up being 1, then if a person wants to claim their token, for claiming token 1, they would instead get token 2, claiming token 5, they would instead get token 1 (wraps around).

So this gives me some ability to enable randomised claims of tokens, however, here is the problem:

The offset means that if someone can claim 5 tokens, they will all be sequential (sure, they will be offset by a random amount, but they would still get 5 consecutive token IDs).

I was wondering, is there a way for me to use the random number to have a uniform distribution of randomness?

So for example there isn't this consecutive number issue, instead each token ID will actually correspond to a more random distribution, where for example:

token ID 1 -> 2
token ID 2 -> 4
token ID 3 -> 5
token ID 4 -> 3
token ID 5 -> 1

This video at this timestamp basically shows exactly what I am trying to do in my use case:

https://youtu.be/YEBfamv-_do?t=307

Does anyone know how I could achieve this? Or would it need to be a situation where I have a prime number and a "primitive root" of that prime number as the video shows? Is there a totally different method I could use? I'm not good with mathematics so I apologise if I am being silly.

Answer 1

You should use a hash function on your ids combined with the random number.

tokenIds are randomly distributed (can repeat):

for (uint256 i = 0; i < tokenIds.length; i++) {
    tokenIds[i] = uint256(keccak256(
       abi.encode(randomNumber, i)
    )) % tokenIds.length;
}

tokenIds are randomly shuffled (can't repeat), this naive shuffling isn't very good

for (uint256 i = 0; i < tokenIds.length; i++) {
    uint j = uint256(keccak256(
       abi.encode(randomNumber, i)
    )) % tokenIds.length;
    (tokenIds[j], tokenIds[i]) = (tokenIds[i], tokenIds[j]);
}

tokenIds are randomly shuffled using EnumerableSet

// initialize some sequential ids
uint256 allTokenCount = 100;
EnumerableSet.UintSet storage tokenIds;
for (uint256 i = 0; i < allTokenCount; i++) {
    tokenIds.add(i);
}
// shuffle into a new array (it can be smaller than allTokenCount)
uint256[] memory result = new uint256[](allTokenCount);
for (uint256 i = 0; i < result.length; i++) {
    uint256 j = uint256(keccak256(abi.encode(randomNumber, i))) % tokenIds.length();
    uint256 tokenId = tokenIds.at(j);
    result[i] = tokenId;
    tokenIds.remove(tokenId);
}
return tokenIds.values()

• The last one you gives better distribution (since it pops ids into a new array)
• And you can use it in chunks (set will get smaller each time)
• But it's more complicated and memory-expensive

I use EnumerableSet.UintSet from https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/structs/EnumerableSet.sol

see https://docs.chain.link/docs/chainlink-vrf-best-practices/#getting-multiple-random-numbers and https://stackoverflow.com/questions/18806210/generating-non-repeating-random-numbers-in-js