DN404 - Finding next NFT Mint tokenIds

DN404 is a new hybrid ERC20 and ERC721 standard that aims to combine tokens and NFTs and adding more liquidity and fractionalization to NFTs. In this post, we will query storage slots of DN404 contract to determine which NFTs will be minted and ordering of NFTs when buying tokens.


One of the most asked questions in Xtremeverse community around DN404 was how to determine which NFT will they get when user buys tokens from Uniswap.

Quick explanation of DN404 - If a user holds 1 complete token, then only they will also have 1 NFT, if they hold 0.99 token, then they wouldn’t have the NFT, similarly, 1.6 tokens equivalent to 1 NFT.

So let’s say totalSupply of NFTs is 3000, and we have equivalent 3000 * 10e18 number of tokens.

If a user is airdropped 1 NFT (and equivalent 1 token), and then they decide to sell half of their token, then their NFT will be burned but they will still have 0.5 token. Now let’s say after some time, this user again decides to buy 0.5 token back, then they might not get the same NFT as they burned originally and that NFT might have been minted to someone else already.

Now, we need to determine which token id will a user get when a new NFT is to be minted

This post mainly targets the DN404 configuration where tokenIds are recycled in minting/burning and useExistsLookup is set to true but process can be tweaked to follow any configuration.

Our goal is to find next NFT minting order using Javascript and ethers.js to provide this info to the user.

Relevant code in DN404 where mint is done is as below

    DN404Storage storage $ = _getDN404Storage();

    t.nextTokenId = _wrapNFTId($.nextTokenId, maxId);
    // Mint loop.
    do {
        uint256 id;
        if (burnedPoolHead != t.burnedPoolTail) {
            id = _get($.burnedPool, burnedPoolHead++);
        } else {
            id = t.nextTokenId;
            while (_get(oo, _ownershipIndex(id)) != 0) {
                id = _useExistsLookup()
                    ? _wrapNFTId(_findFirstUnset($.exists, id + 1, maxId + 1), maxId)
                    : _wrapNFTId(id + 1, maxId);
            }
            t.nextTokenId = _wrapNFTId(id + 1, maxId);
        }
        if (_useExistsLookup()) _set($.exists, id, true);
        _set(toOwned, toIndex, uint32(id));
        _setOwnerAliasAndOwnedIndex(oo, id, t.toAlias, uint32(toIndex++));
        _packedLogsAppend(packedLogs, id);
        _afterNFTTransfer(address(0), to, id);
    } while (toIndex != t.toEnd);

    $.nextTokenId = uint32(t.nextTokenId);

Here, while (toIndex != t.toEnd) loops for the number of NFTs to be minted, nextTokenId is a pointer to where we should start looking for new NFTs to be minted.

If useExistsLookup is true and ids will be recycled, then logic for next mint will be

- get current $.nextTokenId
- iterate from nextTokenId until maxTokenId and find the first tokenId that doesnt exist (doesnt exist == burned)
- set $.nextTokenId as firstUnsetId + 1
- keep looping for the number of NFTs to be minted

Finding Next NFT Mint IDs in Javascript

First, we need to find out the storage slots of the data we are interested in.

evm.storage also provides a pretty decent view of the storage layout for a contract but it’s not able to decode Bitmaps used for efficient gas management

We primarily need two data values

DN404 storage layout

/// @dev Struct containing the base token contract storage.
struct DN404Storage {
    // Current number of address aliases assigned.
    uint32 numAliases;
    // Next NFT ID to assign for a mint.
    uint32 nextTokenId;
    // The head of the burned pool.
    uint32 burnedPoolHead;
    // The tail of the burned pool.
    uint32 burnedPoolTail;
    // Total number of NFTs in existence.
    uint32 totalNFTSupply;
    // Total supply of tokens.
    uint96 totalSupply;
    // Address of the NFT mirror contract.
    address mirrorERC721;
    // Mapping of a user alias number to their address.
    mapping(uint32 => address) aliasToAddress;
    // Mapping of user operator approvals for NFTs.
    AddressPairToUint256RefMap operatorApprovals;
    // Mapping of NFT approvals to approved operators.
    mapping(uint256 => address) nftApprovals;
    // Bitmap of whether an non-zero NFT approval may exist.
    Bitmap mayHaveNFTApproval;
    // Bitmap of whether a NFT ID exists. Ignored if `_useExistsLookup()` returns false.
    Bitmap exists;
    // Mapping of user allowances for ERC20 spenders.
    AddressPairToUint256RefMap allowance;
    // Mapping of NFT IDs owned by an address.
    mapping(address => Uint32Map) owned;
    // The pool of burned NFT IDs.
    Uint32Map burnedPool;
    // Even indices: owner aliases. Odd indices: owned indices.
    Uint32Map oo;
    // Mapping of user account AddressData.
    mapping(address => AddressData) addressData;
}

As we know, EVM storage slots work in 32 bytes data slots. So for gas efficiency, nextTokenId is packed in a struct with 6 other variables to occupy a single storage slot.

These 6 variables occupying a single storage slot are

// Current number of address aliases assigned.
uint32 numAliases;
// Next NFT ID to assign for a mint.
uint32 nextTokenId;
// The head of the burned pool.
uint32 burnedPoolHead;
// The tail of the burned pool.
uint32 burnedPoolTail;
// Total number of NFTs in existence.
uint32 totalNFTSupply;
// Total supply of tokens.
uint96 totalSupply;

As we can see, uint32, uint32, uint32, uint32, uint32 and uint96 (6 variables) when packed together results in full 32 bytes (256 bits) slot.

The slot address of this can be found using evm.storage

alt text

Slot address - 0x0000000000000000000000000000000000000000000000a20d6e21d0e5255308

We can also find the slot address by following the solidity storage layout guide

Now we can query the data at this address using ethersjs

let hexString = await provider.getStorage(XTREMEVERSE_ERC20_ADDRESS, '0x0000000000000000000000000000000000000000000000a20d6e21d0e5255308')
// hexString = 0x000000a2a15d09519be0000000000afe00000000000000000000015d000005be

After we have the data value, we can decode the packed data into individual 6 variables

let hexString = await provider.getStorage(XTREMEVERSE_ERC20_ADDRESS, '0x0000000000000000000000000000000000000000000000a20d6e21d0e5255308')
// hexString = 0x000000a2a15d09519be0000000000afe00000000000000000000015d000005be

hexString = hexString.slice(2);

// decode according to how variables are packed in the struct

// first 12 bytes in data hex are totalSupply (uint96 in our solidity struct)
// we take first 24 characters as 2 hex characters represent 1 byte and we are looking for 12 bytes total for totalSupply
const totalSupply = decodeUint('0x' + hexString.slice(0, 24));
// next 4 bytes for totalNFTSupply and so on..
const totalNFTSupply = decodeUint('0x' + hexString.slice(24, 32));
const burnedPoolTail = decodeUint('0x' + hexString.slice(32, 40));
const burnedPoolHead = decodeUint('0x' + hexString.slice(40, 48));
const nextTokenId = decodeUint('0x' + hexString.slice(48, 56));
const numAliases = decodeUint('0x' + hexString.slice(56, 64));

function decodeUint(hex) {
    const value = BigInt(hex);
    return value.toString();
}

From this storage slot data value, we are only interested in nextTokenId

Next, we need to find which tokenId exists starting from nextTokenId. E.g if nextTokenId is 250, but id #250 is already owned by someone, then this wouldnt be minted, we will keep moving forward until we find the first tokenId that does not exist.

Relevant code in DN404 is _findFirstUnset($.exists, id + 1, maxId + 1)

So we are looking for the first unset id starting from nextTokenId up until maxId

Now, we need to look at $.exists Bitmap in DN404

struct DN404Storage {
    ...
    // Next NFT ID to assign for a mint.
    uint32 nextTokenId;
    ...
    // Bitmap of whether a NFT ID exists. Ignored if `_useExistsLookup()` returns false.
    Bitmap exists;
    ...
}

Bitmap is then defined as

/// @dev A bitmap in storage.
struct Bitmap {
    uint256 spacer;
}

What is Bitmap?

$.exists is effectively a mapping of every tokenId to whether or not that tokenId exists. However using a simple mapping(uint256 => boolean) is not really efficient for storing just a boolean value at every tokenId.

From OpenZeppelin Bitmaps library documentation -

BitMaps pack 256 booleans across each bit of a single 256-bit slot of uint256 type. Hence booleans corresponding to 256 sequential indices would only consume a single slot, unlike the regular bool which would consume an entire slot for a single value.

So effectively, if lets say totalSupply is 3000, then we can store the exists bool for every tokenId in 3000/256 = 11 uint256 buckets.

From tokenId 1 to 256 -> first bucket of our Bitmap is used to store first 256 ids exists bits across 256 bits of first uint256

Similarly From tokenId 257 to 512 -> second bucket of our Bitmap is used to store next 256 ids exists bits.

Finding data in Bitmap

Now coming back to our next query requirement, it is to find what is the first tokenId that does not exists yet starting from nextTokenId.

For that, lets query all buckets of our Bitmap and save every tokenId -> exists mapping in JS

First, we need to find the storage slot addresses of each of these Bitmap buckets, then we will query data there and then we will find if tokenId exists at every single bit of uint256

Using Solidity storage layout guide, the slot address for 1st exists bucket is 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000000

we can also confirm by logging the slot directly in Solidity

function logExistsSlotAddress(uint256 index) public view {
    DN404Storage storage $ = _getDN404Storage();
    Bitmap storage exists = $.exists;
    bytes32 slot = _returnSlot(exists, index);
    console.logBytes32(slot);
}

function _returnSlot(Bitmap storage bitmap, uint256 index) pure internal returns (bytes32 slot) {
    assembly {
        slot := add(shl(96, bitmap.slot), shr(8, index))
    }
}

Similarly, the slot address for 2nd bucket will be 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000001

All 11 bucket slot addresses for 3000 totalSupply are

bucket 0 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000000
bucket 1 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000001
bucket 2 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000002
bucket 3 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000003
bucket 4 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000004
bucket 5 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000005
bucket 6 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000006
bucket 7 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000007
bucket 8 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000008
bucket 9 slot 0x0000000000000000000000a20d6e21d0e525530e000000000000000000000009
bucket 10 slot 0x0000000000000000000000a20d6e21d0e525530e00000000000000000000000a
bucket 11 slot 0x0000000000000000000000a20d6e21d0e525530e00000000000000000000000b

Now, we can fetch data at all of these slots

function getTokenIdBucketSlot(bucket) {
    let existsStructSlot = '0x0000000000000000000000a20d6e21d0e525530e000000000000000000000000'
    // bucket (int) 0,1,2 etc
    let bucketHex = bucket.toString(16)
    let end = existsStructSlot.length - bucketHex.length
    let bucketSlot = existsStructSlot.slice(0, end).concat(bucketHex)
    return bucketSlot
}

let bucketsCount = MAX_TOKEN_ID / 256
let batchCalls = []
for (let i = 0; i < bucketsCount; i++) {
    let bucketSlot = getTokenIdBucketSlot(i)
    batchCalls.push(provider.getStorage(XTREMEVERSE_ERC20_ADDRESS, bucketSlot))
}

const results = await Promise.all(batchCalls);
// results is array of slot data values of each exists bucket

exists data at each bucket comes out to be

0: "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
1: "0xfffffffffffffffffffefffffffffffff0207ffbffffffffffffffffffffffff"
2: "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
3: "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
4: "0xffffffffffff74ffffffffffffff3fffffffffffff3ffffffbbdfffff8efffff"
5: "0xfffffffffffffffffffffe9ff2ff197e4fffff90dfffffffda5c07fe33ffffff"
6: "0x61ffffeffffffaffbff05ffbe7f9ffbfbff8fffffffffff7fffffdefffbfffff"
7: "0xfffffffdffffffdffffffffffffefffffffe71ff7effd97ffdfffffffff61dff"
8: "0xefffaffffdffffdffffffff7ff3bfe9ff6b0eaffff5dfffeffffffffeeffffff"
9: "0xfffffffffffffffffffffffffffddfd6fffffffffffffffffffffdfffbffffff"
10: "0xfffbfffffffffff7fefbf9fe4fffefcafffffffffffdbffffff7ffd7ffffdfff"
11: "0x000000000000000001fffffdfffffffffffffffffdf79ef6fefbffffffffffff"

Bitmap data values to boolean

Now, when we have Bitmap values, we can get bool for each tokenId using (bucketValueHex >> BigInt(index)) & BigInt(1)

function getTokenIdExists(tokenId) {
    // which bucket this tokenId lies in
    let bucket = Math.floor(tokenId / 256)
    // which bit we need to check for this tokenId
    let bit = tokenId % 256
    // uint256 data value at this bucket (fetched above, different for different bucker)
    let bucketValueHex = '0xfffffffffffffffffffefffffffffffff0207ffbffffffffffffffffffffffff'
    let exists = (BigInt(bucketValueHex) >> BigInt(bit)) & BigInt(1)
    return exists === BigInt(1)
}

Using above, from a single uint256 data value, we can calculate 256 exists boolean for 256 tokenIds.

Now we have all the required data (nextTokenId and exists bool for every tokenId) to calculate order of next NFT mints

let nextNftMints = []
for (let i = parseInt(nextTokenId); i <= MAX_TOKEN_ID; i++) {
    if (!getTokenIdExists(i)) {
        nextNftMints.push(i)
    }
}

We can then also listen for new blocks and refresh the next mints order on every new block

alt text


Posted by Naman Dwivedi on 15 Mar 2024

Tags- DN404 ,Solidity