Ensuring a fair distribution of an NFT set?

Question

Suppose I have 1000 NFT's I would like to distribute. The user can see what any NFT looks like in advance, but they don't know what they'll be getting until they actually buy it. In other words, there will be a random number generated from Chainlink VRF that determines what they get. This ensures a fair distribution, so the rare NFT's can't be bought by early users.

The project that I see comes closest to this is Hashmasks, but they also had the quality that the user didn't even know what any of the artwork would look like in advance. For the purposes of my project, I don't need this property.

The main issue I see with Hashmasks is that there is no tokenURI function. They upload everything on IPFS, so it seems the only way to have a tokenURI would be to know the hashes of every NFT in advance and store them in the contract, and then append it to the IPFS url prefix, but this would be incredibly expensive.

I was wondering if there was a way I could still retain the property of having the tokenURI whilst also ensuring a random distribution.

For the random distribution part, I was thinking of getting a random number, r, from chainlink VRF, and then doing:

i = rand % maxSupply

Then I check ownerOf(i), if it's taken, then i+=1, if not taken, then assign. I was wondering, does the mere checking of ownerOf(i) take gas fees? This loop, in the worst case scenario, would take maxSupply - 1 iterations to assign a NFT; how bad could the gas fees look like?

Answer 1

Given two integers a and b which are coprime, then (a x + b) modulo n will visit all integers from 0 to n - 1 exactly once.

You can use this to "randomly" assign NFTs by choosing a fixed large prime a and populating b from VRF. Given sufficiently large a, a and b are very likely to be coprime.

You can then simply iterate through [0, x) assigning the nth NFT.

Here's a toy example written in Python to demonstrate it working:

a = 97        # Random prime
b = 12345678  # VRF
n = 10        # Total NFTs

for x in range(0, n):
    nft = ((a * x) + b) % n
    print(f"Mint {x} will be NFT {nft}")

Output:

Mint 0 will be NFT 8
Mint 1 will be NFT 5
Mint 2 will be NFT 2
Mint 3 will be NFT 9
Mint 4 will be NFT 6
Mint 5 will be NFT 3
Mint 6 will be NFT 0
Mint 7 will be NFT 7
Mint 8 will be NFT 4
Mint 9 will be NFT 1