Author: 0xEstarriol

Source code of ERC721Psi is available on github now. Commercial support is also available at ctor lab.

TL;DR

• We designed ERC721Psi, an ERC721 compliant implementation, ground up.
• Inspired by Azuki’s ERC721A, ERC721Psi also provides batch minting at a fixed gas cost. We further optimized the amount of the data written to the storage to achieve a lower minting cost.
• ERC721Psi solves the scaling issue of ERC721A in token transfer and on-chain metadata querying in a large batch through the use of bitmaps and the de Bruijn sequence.
• ERC721Psi provides the extension for batch minting tokens with tamper-proof on-chain randomness at the individual token level while maintaining a constant gas cost.
• With a batch of 10 tokens, ERC721Psi uses >90% less gas than OpenZepplin’s ERC721Enumerable and ~20% less gas than ERC721A in minting, and up to ~30% gas savings in first-time token transfer compared to ERC721A. In addition, ERC721Psi significantly reduces the cost of burning multiple tokens with close token IDs, which are ~70% and ~80% savings compared to ERC721A and ERC721Enumerable, respectively.

On the giant’s shoulders, we try to do more to pave a smoother road to the future metaverse.

The famous Non-Fungible-Token standard, ERC721, was established in 2018, opening a whole new era for the crypto world. Nowadays, many amazing NFT projects appear day after day, allowing celebrities to build their own fans’ kingdoms, artists to publish their artworks on-chain, and even communities to quickly gather people with the same interest from the globe. These activities undoubtedly will change the environments for art, entertainment, finance, and so many industries in the near future.

However, with more and more activities on Ethereum, gas fees have soared so much compared to before, especially at the launch of the NFT projects, making it harder and harder for people to join this wonderland.

But we also observe some great ideas on solving this problem in various ways. For example, the developers of Nuclear Nerds removed the redundant data, which is rarely used on chains, and implemented their own functions for NFT enumeration instead of relying on most of the project’s go-to implementation, OpenZepplin’s ERC721Enumerable. The Azuki team developed the ERC721A, which makes a considerable gas saving on batch minting NFTs by avoiding storing duplicate data on the ownership information.

Challenges on locating ownership / metadata with ERC721A

Azuki’s ERC721A provides a great concept of avoiding storing duplicate data and only storing the data at the storage slot of the first token in a batch during minting. For the rest of the tokens in the same batch, when the ownership of the token is being queried, the contract will look for the previous tokens one by one until it finds the head of the batch that stores the owner’s information.

For example, tokens #100 to #102 are minted from the same batch, but the information of the owner (Alice) is only stored with the first token, token #100. If we need the information of the owner of token #102, the contract will first check the storage slots of token #102. Since the owner’s information is not stored with #102, the smart contract will continue checking its previous token, which is token #101. It will continue this process until it finds the storage slots.

However, this searching-for-the-head process prevents ERC721A from being truly scalable and gas efficient for on-chain metadata querying and transactions.

Assume we mint 10 NFTs in a batch, and we’d like to transfer the 10th NFT in the batch (e.g. selling it on OpenSea or transferring it to a friend). By doing so, ERC721A needs to go through 10 address slots to find its owner to verify if the sender (we) owns the token. Loading data (SLOAD) from the storage is one of the most expensive operations. Moreover, its cost has been increased by ~2.6 times after the Berlin update.

Not only the ownership, but this issue also applies to querying on-chain metadata.
Introducing ERC721Psi

We designed ERC721Psi, an ERC721 compliant implementation, from scratch.

Our design is heavily inspired by Azuki’s ERC721A and can be used as a drop-in replacement. Like ERC721A, our design supports minting a batch of tokens with a constant gas cost, regardless of the number of tokens minted. The information of the owner’s address is only written to storage once for the whole batch.

To solve the issue of the expensive process of finding the head of a batch in ERC721A, we implement a bitmap for tracking the head of a batch. At each site of the bitmap, it can have two values, 1 and 0, and we use it to mark if the token is the head of a batch. A bitmap is a highly efficient data structure. In a single storage slot, it can track up to 256 NFTs at once!

Searching the head of a batch efficiently: de Bruijn sequence

The most naive method for finding the index of the first token of a batch is searching the bit map one bit by one bit until the head of the batch is found. Depending on the distance between the token we are interested in and the first token in the same batch, the searching process can still be costly.

However, apart from significantly reducing the amount of data required from the storage, using bitmap allows us to provide additional speedup. The basic computation unit of the Ethereum virtual machine (EVM) is 256 bit, and it enables us to search 256 indexes at once instead of looping through every bit to find the set bit.

The first step of our method is shifting the bit that represents the token to the most right of the 256-bit bitmap. Finding the head of the batch is now equivalent to finding the least significant 1 bit (LS1B), the position of the most right 1 bit, in the bitmap.

Luckily, there is an algorithm that utilizes de Bruijn sequence to quickly find the LS1B. The beautiful mathematics behind the algorithm is beyond the scope of this article, but if you are interested in knowing more about it, definitely let us know. We might write another article discussing it!

The first step of the algorithm is to separate the LS1B, and this can be done with a simple bit trick:

The bitmap with the isolated LS1B is subsequently multiplied by a pre-calculated magic number and right-shifted by an amount that depends on the bitmap’s width. The resulting number will have a one-to-one relation to the index of LS1B, and therefore we can use a lookup table to find the index.

Keen readers should notice that the amount of computation required to find the index of LS1B here doesn’t depend on where the LS1B is.

In addition, the lookup table is stored within the contract, and loading it doesn’t require the expensive operation (SLOAD) to load data from the storage.

Though the existing implementations are designed for either a 32-bit or a 64-bit processor because the 256-bit version of the algorithm doesn’t match the architecture of the conventional CPUs, as a result, we have to compute the magic number and the lookup table ourselves.

Shown in the figure below, the gas consumption of our method is very satisfying, the cost doesn’t scale, and only cost ~300 gas, which is 0.00003 ETH under 100 gwei gas fee.

Batch minting with on-chain random metadata at the individual token level.

In Medieval DAO, we’d like to develop an ultimate framework for on-chain metaverse experience. Therefore, we designed an extension to make each token have its unique randomly generated attribute even in the same batch while maintaining a constant gas cost.

With the extension, when the tokens are minted, the NFT contract will make a request for randomness, and a randomness provider will later fulfill this randomness request. In our implementation, we use Chainlink’s VRF as our built-in provider.

Like how we deal with the ownership, the randomness will only be stored with the first token of a batch. We use a simple but effective method to generate random attributes for each token. Instead of having random numbers assigned to individual tokens, the random number (seed) for each token is derived through hashing the randomness associated with the batch and the offset of the token from the head of the batch.

tokenSeed = keccak256(abi.encode(batchSeed + offset) );

With this framework, each token will have a seed that the developer can use to generate various attributes, including the appearance or abilities. As for how we use the random seed to synthesize attributes with various properties, we will have another article talking about it. Stay tuned!

Benchmark

Batch Mint Optimization

ERC721Psi provides batch minting optimization inspired by ERC721A by Azuki. After our improvement, the gas used will be lower by more than 20% compared to ERC721A.

Token Transfer Optimization

ERC721Psi solves the scaling issue of ERC721A in the first-time token transfer in a large batch. The gas savings will be more significant as the batch gets larger.

Once the token is transferred, the token owner is registered to the Ethereum storage. Thus the gas consumption for the subsequent transfers will be considerably lower. However, ERC721psi still improves on the gas consumption here.

Burning Multiple Tokens

ERC721Psi also uses a bitmap to track the burned token. Our implementation significantly reduces the cost of burning multiple tokens with close token IDs. We believe this is a valid assumption since users can mint multiple tokens in a single transaction. In contrast, Azuki’s ERC721A stores this information and ownership information. This results in significant gas consumption, especially for burning the tokens of which the ownership information hasn’t been set (Tokens that are not the first one in a batch.).

Below we showed the comparison of burning multiple tokens in a single transaction, and we can observe that ERC721Psi provides a significant reduction in gas consumption.

Conclusion

• ERC721Psi improves the gas consumption on batch minting and solves the scaling problem of ERC721A by Azuki in first-time token transfer in a large batch.
• Although not implemented in our specific implementation. It is possible to stake extra bitmaps layers to track the batch head, and the scaling is highly efficient.
• For example, by adding one extra layer, we will need to load one extra storage slot, but the amount of tokens we can search at once is increased to 256 * 256 = 65536 at once.
• ERC721Psi also retains flexibility for burning function and on-chain randomized metadata, hoping the flexibility can help other NFT projects create more exciting features.