0

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.

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

4
  • Hmm, I'm not sure this does what I am aiming for. Here is another framing of my question which may make more sense: math.stackexchange.com/questions/4303436/…
    – Jay
    Nov 11 '21 at 22:47
  • From the question you linked I see that you want shuffling, not a random distribution. Edited my answer to have 2 versions
    – dk1a
    Nov 11 '21 at 23:26
  • Thanks @dk1a, my only concern here is that the for loop would cause gas issues with a large number of token IDs, so I'm trying to find out if there is a way to do it without having to shuffle the whole array at once, but rather for each token claimer to do a fragment of the computation required to get their relevant IDs.
    – Jay
    Nov 11 '21 at 23:49
  • Added another shuffling method, you could maybe also use a linked list instead of a set there
    – dk1a
    Nov 12 '21 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.