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
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
- nextTokenId
- if a tokenId exists or not
DN404 storage layout
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
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
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
After we have the data value, we can decode the packed data into individual 6 variables
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
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
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)
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
We can then also listen for new blocks and refresh the next mints order on every new block
Posted by Naman Dwivedi
on 15 Mar 2024
Tags- DN404
,Solidity