NFT – Mint Random Token ID

  • andrey-metelev-yscrM1AOEKI-unsplash (1)

The perceived value of many NFTs is based on that item’s rarity making it ideal to mint them fairly. Rarity snipers and bad actors on a team can scoop up rare items from a collection in an attempt to further profit on the secondary market. How can you both fairly distribute the tokens – both to the community and the project team?

One solution is to hide the metadata until after reveal and mint the token IDs out of order – either using a provable random number, a pseudo random number, as pseudo random number seeded with a provable random beacon, or other options depend on your security needs. For provable random numbers check out Provable Randomness with VDF.

How It Works

uint16[100] public ids;
uint16 private index;

function _pickRandomUniqueId(uint256 random) private returns (uint256 id) {
    uint256 len = ids.length - index++;
    require(len > 0, 'no ids left');
    uint256 randomIndex = random % len;
    id = ids[randomIndex] != 0 ? ids[randomIndex] : randomIndex;
    ids[randomIndex] = uint16(ids[len - 1] == 0 ? len - 1 : ids[len - 1]);
    ids[len - 1] = 0;
}

We can efficiently track which IDs have – and have not – been minted by starting with an empty and cheap to create array of empty values with a size that matches your total supply. The array size could suffice in lieu of tracking the index, but this is more gas efficient than pop()ing the array. For each round it will select a random index, bounded by the remaining supply – we will call this a “roll” as in “roll of the dice” except we will reduce the number of sides by one for each round.

Round 0

When we start the Data array will match the supply we want to create (five) and be empty (all zeroes), as well our Results, which are just empty (this represents the token ids that would be minted).

Index:    0  1  2  3  4  5
--------------------------
Data:    [0, 0, 0, 0, 0, 0] 
Results: []
Round 1: 3

For the first round, let’s say it’s a 3. We look at the third index, check to see if it is 0, and if is we return the index – this will make more sense in a moment. Next we look at the last position in the array given our remaining supply and if it is a 0 we move that index to the 3 position we rolled.

Index:    0  1  2 *3* 4  5
---------------------------
Data:    [0, 0, 0, 0, 0, 0] 
Results: []

<< before
after >>

Data:    [0, 0, 0, 5, 0] 
Results: [3]
Round 2: 3

In the previous step when we check an index for a value, if a value was set a that index we would use it rather than the index. To demonstrate this, let’s assume we rolled a 3 again. This time we look at this third position and it contains a 5, so we return that instead of a three. This is great, because we already selected a 3 and we want these to be unique. Again we look at the last position, and since it is not set we set the index 4 as the value of index 3.

Index:    0  1  2 *3* 4  5
---------------------------
Data:    [0, 0, 0, 5, 0] 
Results: [3]

<< before
after >>

Data:    [0, 0, 0, 4] 
Results: [3, 5]
Round 3: 2

Next, we roll a 2 again. We look at position 2, it’s not set, so we return a 2, again a number we haven’t selected previously. Next we check the last position which now as a 4 set, so it is moved into index 2 as we have yet to select it.

Index:    0  1 *2* 3  4  5
---------------------------
Data:    [0, 0, 0, 4] 
Results: [3, 5]

<< before
after >>

Data:    [0, 0, 4] 
Results: [3, 5, 2]
Round 4: 1

We roll a 1, and since the first index contains a 4 we move that to our results.

Index:    0 *1* 2  3  4  5
---------------------------
Data:    [0, 0, 4] 
Results: [3, 5, 2]

<< before
after >>

Data:    [0, 4] 
Results: [3, 5, 2, 1]
Round 5: 1

We roll a 1 again. This time we return the 4, but since there is nothing to move into its place, we move on.

Index:    0 *1* 2  3  4  5
---------------------------
Data:    [0, 4] 
Results: [3, 5, 2, 1]

<< before
after >>

Data:    [0] 
Results: [3, 5, 2, 1, 4]
Round 6: 0

Lastly, we get a 0, since that’s all that remains. It both contains a 0 and is in that position so we select a 0.

Index:   *0* 1  2  3  4  5
---------------------------
Data:    [0] 
Results: [3, 5, 2, 1, 4]

<< before
after >>

Data:    [] 
Results: [3, 5, 2, 1, 4, 0]

TLDR;

Each index of the array tracks an unminted ID. If the position isn’t set, that ID hasn’t been minted. If it is set, it’s because the last position was moved to it when the available indexes shrank and the last index wasn’t the one selected so we want to preserve it. If you want to start minting at 1, add 1.

Pseudo Random

Uses a pseudo random number to select from a unique set of token IDs.

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.11;

import '@openzeppelin/contracts/token/ERC721/ERC721.sol';

contract RandomTokenIdv1 is ERC721  {

    uint16[100] public ids;
    uint16 private index;

    constructor() ERC721('RandomIdv1', 'RNDMv1') {}

    function mint(address[] calldata _to) external {
        for (uint256 i = 0; i < _to.length; i++) {
            uint256 _random = uint256(keccak256(abi.encodePacked(index++, msg.sender, block.timestamp, blockhash(block.number-1))));
            _safeMint(_to[i], _pickRandomUniqueId(random));
        }
    }

    function _pickRandomUniqueId(uint256 random) private returns (uint256 id) {
        uint256 len = ids.length - index++;
        require(len > 0, 'no ids left');
        uint256 randomIndex = random % len;
        id = ids[randomIndex] != 0 ? ids[randomIndex] : randomIndex;
        ids[randomIndex] = uint16(ids[len - 1] == 0 ? len - 1 : ids[len - 1]);
        ids[len - 1] = 0;
    }

}

Provable Random

Uses a provable random number and derivatives to select from a unique set of token IDs.

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.11;

import '@openzeppelin/contracts/token/ERC721/ERC721.sol';
import './libraries/Randomness.sol';
import './libraries/SlothVDF.sol';

contract RandomTokenIdv2 is ERC721  {

    using Randomness for Randomness.RNG;
    
    Randomness.RNG private _rng;

    mapping(address => uint256) public seeds;
    uint256 public prime = 432211379112113246928842014508850435796007;
    uint256 public iterations = 1000;

    uint16[100] public ids;
    uint16 private index;

    constructor() ERC721('RandomIdv2', 'RNDMv2') {}

    function createSeed() external payable {
        seeds[msg.sender] = _rng.getRandom();
    }

    function mint(address[] calldata _to, uint256 proof) external {
        require(SlothVDF.verify(proof, seeds[msg.sender], prime, iterations), 'Invalid proof');

        uint256 _randomness = proof;
        uint256 _random;
        for (uint256 i = 0; i < _to.length; i++) {
            (_randomness, _random) = _rng.getRandom(_randomness);
            _safeMint(_to[i], _pickRandomUniqueId(_random));
        }
    }

    function _pickRandomUniqueId(uint256 random) private returns (uint256 id) {
        uint256 len = ids.length - index++;
        require(len > 0, 'no ids left');
        uint256 randomIndex = random % len;
        id = ids[randomIndex] != 0 ? ids[randomIndex] : randomIndex;
        ids[randomIndex] = uint16(ids[len - 1] == 0 ? len - 1 : ids[len - 1]);
        ids[len - 1] = 0;
    }

}

Random Beacon

Uses a provable random number as a beacon which is used as the seed for a pseudo random number and derivatives to select from a unique set of token IDs.

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.11;
 
import '@openzeppelin/contracts/access/Ownable.sol';
import '@openzeppelin/contracts/token/ERC721/ERC721.sol';
import './libraries/Randomness.sol';
import './libraries/SlothVDF.sol';
 
contract RandomTokenIdv3 is ERC721, Ownable  {

    using Randomness for Randomness.RNG;
     
    Randomness.RNG private _rng;

    uint16[100] public ids;
    uint16 private index;
 
    uint256 public prime = 432211379112113246928842014508850435796007;
    uint256 public iterations = 1000;
    uint256 public seed;
    uint256 public beacon;
 
    constructor() ERC721('RandomTokenIdv3', 'RNDMv3') {}
 
    // create a set - use something interesting for the input.
    function createSeed() external onlyOwner {
        (uint256, uint256 _random) = _rng.getRandom();
        seed = _random;
    }
 
    // once calclated set the beacon
    function setBeacon(uint256 proof) external {
        require(SlothVDF.verify(proof, seeds[msg.sender], prime, iterations), 'Invalid proof');
        beacon = proof;
    }

    function mint(address[] calldata _to) external {
        require(beacon > 0, 'Beacon not set');
        uint256 _randomness = beacon;
        uint256 _random;
        for (uint256 i = 0; i < _to.length; i++) {
            (_randomness, _random) = _rng.getRandom(_randomness);
            _safeMint(_to[i], _pickRandomUniqueId(_random));
        }
    }
 
    function _pickRandomUniqueId(uint256 random) private returns (uint256 id) {
        uint256 len = ids.length - index++;
        require(len > 0, 'no ids left');
        uint256 randomIndex = random % len;
        id = ids[randomIndex] != 0 ? ids[randomIndex] : randomIndex;
        ids[randomIndex] = uint16(ids[len - 1] == 0 ? len - 1 : ids[len - 1]);
        ids[len - 1] = 0;
    }
 
}

You may also like...

1 Response

  1. Cedric says:

    Could these be done in one transaction and still be provable?

Leave a Reply

Your email address will not be published. Required fields are marked *