From editor:

Gas optimization suggestions are important components of the smart contract auditing process of Secure3. Through the analysis of ERC721A improved implementation, this article discusses the gas optimization of NFT batch mint.

About the author:

Comcat earned his B.S. Computer Science from Zhejiang University. He is now in charge of smart contract design and implementation of a famous web3 technology company.

The Disadvantages of OpenZeppelin Implementation

Developers usually use EIP721 template from OpenZeppelin to implement a typical NFT, shown below:

In which, safeMint is the mint API function from OpenZeppelin, see below:

From the implementation above, the complexity of a regular NFT minting process is O(n), where minting N NFTs requires looping single minting process for N times. The core part is to keep two global variables, the mapping of NFT ownership of each user balance, and the mapping between tokenIdand owners. Both minting and transferring processes need to update these two global variables. For instance, in the minting process, each minting requires two SSTORE, and thus minting N NFTs needs 2N of SSTORE.

One Possible Improvement of ERC721A

The major disadvantage of OpenZeppelin template is that it does not provide API for minting NFTs in batches, so that the complexity goes up to O(N). Thus the implementation in ERC721A provides a batch-minting API to reduce its complexity to O(1).

The easiest improvement is to revise _mintfunction directly, so that the batch-minting variablequantity is also considered, and the global variables balance and owners will be updated accordingly. Instead of minting individual NFTs in the OpenZeppelin standard, this revision needs to maintain a global incremental variable toeknId. And, in addition, according to EIP721 standard, a Transfer event must be emitted whenever the ownership of NFT has changed. Thus the Transferevent is also emitted in the for loop as well

Analysis on the Revision

The implementation of new _mint function is indeed ofO(1) complexity. One easy-to-make misunderstanding is that although it has a for loop inside of _mint function, that loop only executes emit events. From the perspective of OPCODE, there are only LOG4 and ADD, instead of very gas-consuming SSTORE; in addition, tokenId++ is about a local rather than global variable increment, such that the corresponding OPCODE is ADD instead of SSTORE.

In fact, as shown below, this revision only updates the ownership of tokenId at the first index of the batch, and the following tokenId’s ownerships is unchanged asaddress(0). For instance, after Alice mints five NFTs，system only updates _owners[2]=alice at tokenId=2; to reduce the usage of SSTORE, the _owners of the rest of tokenId=3, 4, 5, 6 are still address(0). And when the next user starts minting, it will start from tokenId=7.

Some Q&A’s

Q1: as not every single tokenId records corresponding owners, who are the owners of those tokenId’s with owners[tokenId]=address(0)?

A: In OpenZeppelin standard, every tokenId has its corresponding owner address in owners[tokenId]. If it is address(0), it means that such tokenId has not yet been minted, such that _exists[tokenId]=false. But, for ERC721A, there are two possibilities when the owners of a tokenId is address(0):

1. That token has not yet been minted
2. That token belongs to some specific owner, but not the first one in that batch.

Q2: Then how do we implement the ownerOf function?

A: The tokenId from same batch mint will be monotonic increasing series of integers: 0, 1, 2, 3... There is one simple algorithm to derive the owner of a specific tokenId. Decrement from the tokenId until the first index that is not address(0), and that address value stored will be the owner of tokenId .

Q3: How does it exclude those not minted tokenId?

A: we can compare tokenId to currIndex. The token is not minted if tokenId >= currIndex.

Q4: If Alice mints a batch of NFTs, transfer one of which to Bob, then the tokenId of Alice’s batch is discontinuous now. How should we design the transfer algorithm to accommodate this?

A: Let’s say Alice owns NFT NO.2, 3, 4, 5 and 6, and transfer NO.3 to Bob. Then the system should be updated as following:

• Update the owner of NFT NO.3 to Bob (tokenId=3)
• Update the owner of NFT NO.4 to Alice from address(0)(tokenId=4)

Note that the transfer process here is not batch operation, but operation on individual NFT. The complexity is still O(N) for batch operation.

And its implementation is shown below:

Q5: How do we implement thetokenOfOwnerByIndex enumeration function?

A: In OpenZeppelin standard, its implementation is based on a global mapping: mapping(address=>mapping(uint256=>uint256)) private _ownedTokens;

But in ERC721A, it does NOT store a corresponding owner for each tokenId, hence we cannot obtain a list of tokenId for a specific owner.

Again, given that all tokenId’s in ERC721A are monotonically increasing sequence of integers, one solution is proposed below:

• Looping all tokenId
• Find all tokenId’s from this owner
• Sort the founded tokenId by time stamps; if they have the same time stamps, then sort thetokenId based on its value.

According to EIP721 standard, there is no specific requirement of sorting; so any sorting criteria work. The detailed implementation is shown below:

Some Open Questions

From the analysis above, we can tell that there are both breakthroughs and limitations of ERC721A comparing to EIP721. We welcome feedbacks, comments and communications through some open questions below:

1. ERC721A requires tokenId increase monotonically from 0. Let’s say if tokenId’s are some discontinuous integers, such as timestamp, that algorithm would not work.
2. Thus the use of startTimestamp is unclear to me:

About Secure3

Secure 3 aims to secure Web3 by empowering a transparent, collaborative and verifiable security ecosystem. We aim to provide trustworthy security auditing for projects, competitive incentive model for auditors, and verifiable auditing track record for Web3 community.