How ERC721 Enumerable Works

An Enumerable ERC721 is an ERC721 with added functionality that enables a smart contract to list all the NFTs an address owns. This article describes how ERC721Enumerable functions and how we can integrate it into an existing ERC721 project. We’ll use Open Zeppelin’s popular implementation of ERC721Enumerable for our explanation.

Prerequisites

Since ERC721Enumerable is an extension of ERC721 , this article assumes that the reader has read our ERC721 article or has knowledge about the ERC721 standard.

Swap and Pop

Removing an item from an list in Solidity is typically done by copying the last element to the destination of the item that will be removed, then popping the array (deleting the last element). It’s too expensive gas-wise to shift all the elements to the left. The operation to delete from a list is shown in the animation below, which removes the item at index 1 (number 5):

Why ERC721Enumerable?

To understand why we need an extension like ERC721Enumerable, let’s consider an example scenario. If we had to find all the NFTs a wallet owns from a particular ERC721 contract, how would we do it with the functionality available within ERC721?

We would have to call the balanceOf() function with the token owner’s address, which would give us the number of NFTs owned by that address. Then, we would loop over all the tokenIDs in the ERC721 contract and call the ownerOf() function for each of these tokenIDs.

Let’s assume that the total supply of NFTs is 1000 and an address owns two NFTs, the first and the last. That is, it owns the tokenIDs #1 and #1000.

To find the 2 tokenIDs owned by the address (token #1 and token #1000, we would have to loop over all the NFTs in a contract and query ownerOf() on that ID (from 1 to 1000), which is computationally expensive. Furthermore, we don’t always know all the tokenIDs in the contract, so we might not be able to do this.

In the upcoming sections, we’ll learn how ERC721Enumerable solves this problem.

Naïve Solution To Tracking Token Ownership

The naïve solution to tracking each token owned by an address is to store a mapping from the address to a list of owned NFTs.

mapping(address owner => uint256[] ownedIDs) public ownedTokens;

However, this solution is inefficient and incomplete for the following reasons:

1. If the user owns a lot of tokens, a smart contract reading their array might run out of gas storing the very long array in memory.

2. There are more gas-efficient ways to store a list of data (discussed later).

3. If we want to remove a particular token from the user’s list of tokens, we need to scan the entire list to find it. If the array is very long, we might run out of gas.

To solve issues 1 and 2 ERC721 Enumerable uses an array instead of a mapping (see the next section) and to solve the 3rd issue, an additional data structure is needed, which maps the a tokenID to the index it is in.

Using a mapping as an array

Mappings can be used in a manner similar to that of an array, where the keys are the index and values are the value stored at that index in the array.

If we replace the array in our example above with a mapping, the indexes of the array become the key, and the tokenIDs become the values.

In Solidity, mappings are more gas efficient than arrays. The length of an array is implicitly checked whenever the array is indexed (i.e., for index i, it checks if i < array.length). This check increases the gas cost of using an array. Using a mapping as an array, we skip this check, and thus save gas.

However, unlike arrays, mappings don’t have a built-in length property, which we could use to track the total number of NFTs in a contract. Therefore, mappings are not always a good substitute for arrays.

In the next section, we’ll delve into each data structure from ERC721Enumerable individually.

ERC721Enumerable: The Data Structures

ERC721 Enumerable tracks two things:

1. all the tokenIDs in existence.
2. all the tokenIDs an address owns.

To accomplish 1, it uses the data structures _allTokens and _allTokensIndex.

To accomplish 2, it uses the data structures _ownedTokens and _ownedTokensIndex

For the sake of simplicity, we’ll use the same set of tokenIDs for every example and explanation i.e. 2, 5, 9, 7, and 1.

_allTokens array:

The _allTokens array allows us to sequentially iterate over all NFTs in a contract. The _allTokens private array holds every existing tokenID (irrespective of its ownership status).

Initially, the order of tokenIDs in _allTokens depends on when they were minted. In the above diagram, tokenID #2 is at index #0 since it was minted before the other tokenIDs. This order can change upon burning of tokenIDs.

_allTokensIndex mapping:

The _allTokensIndex mapping, given a tokenID, returns the index of that tokenID in the _allTokens array.

Instead of looping over _allTokens to find the index for a tokenID, we can use the tokenID itself to find its index in _allTokens using the _allTokensIndex mapping.

Being able to quickly find the tokenID enables the burn function to remove the tokenID efficiently.

The diagram above illustrates a mapping of tokenIDs to their corresponding index values. The tokenID #2 maps to the 0th index since it was the first token minted in the contract. This mapping pattern continues for every token that gets minted.

_ownedTokens mapping:

The _ownedTokens mapping is used to track the tokenIDs owned by an address. It has a nested mapping (i.e., owner -> index -> tokenID). It maps each owner address to an index, which is within range of the token balance of the address. Each index maps to a tokenID owned by that address.

In the above diagram, the address ‘0xAli3c3’ owns 3 NFTs, and thus has a mapping for 3 tokenIDs. The other address (0xb0b) owns a single token, and thus has a mapping for a single tokenID. At the index of #2, the nested mapping for the ‘0xAli3c3’ address maps to the tokenID #1.

_ownedTokensIndex mapping:

Just like how _allTokensIndex is the mirror image of _allTokens, _ownedTokenIndex is the mirror image of _ownedTokens.

_ownedTokensIndex is a mapping from tokenIDs to the index of that token in _ownedTokens, for that user. Consider the diagram below:

If we plug tokenID 2 or 9 into _ownedTokensIndex, we get 0 back for both, because it is the “first owned token” for both Alice and Bob.

Also just like _allTokensIndex, the purpose of this data structure is to find a specific tokenID in _ownedTokens so we can efficiently remove it (such as when the user transfer or burns token).

Since these data structures are private, they cannot be directly interacted with. In the next section, we’ll understand the functions that read and manipulate these data structure.

ERC721Enumerable: Functions

According to the ERC721 documentation, the ERC721Enumerable has three public functions:

totalSupply()

This function is used to retrieve the total number of NFTs that exist in a contract. It returns the length of the _allTokens array.

tokenByIndex()

tokenByIndex is a simple wrapper around the _allTokens array, which takes an index as input and returns the tokenID stored at that index in the _allTokens array.

tokenOfOwnerByIndex()

This function is a wrapper around the _ownedTokens mapping with some input validation.

In the above example of the _ownedTokens mapping, the address ‘0xAli3c3‘ owns 3 tokenIDs. If the function gets called with this address and an index of 2, the tokenID #1 gets returned.

Adding/Removing tokenIDs From Enumeration

Apart from these functions, OpenZeppelin’s ERC721Enumerable implementation features 4 additional private functions, which are used by the _update function to ensure the data structures in ERC721Enumerable reflect the current token ownership.

We won’t be going into the details for all of these functions, as they’re not part of the ERC721 specification. However, let’s take a look at one of them:

removeTokenFromOwnerEnumeration()

This function is used when a tokenID needs to be deleted from an address’ enumeration data structures. If an owner sells or burns their NFT, the tokenID for that NFT needs to be dissociated from the owner’s address, this is where _removeTokenFromOwnerEnumeration comes into play.

The Deletion Process

Before the deletion takes place, the function uses the _ownedTokensIndex mapping to check if the tokenId is at the last index in the owner’s owned tokenIDs. If it is not at the last index, it is swapped with the tokenID at the last index.

This is necessary because if the tokenID were to be deleted directly, a gap would be left in the owner’s token-indexes which would cause the balanceOf() function to return incorrect results when called with the owner’s address.

After this swap, the function deletes the tokenID (which is now the last tokenID) from _ownedTokensIndex and _ownedTokens, effectively removing the token from enumeration.

The rest of such functions in the extension are:

_addTokenToOwnerEnumeration: adds a tokenID to _ownedTokens and _ownedTokensIndex, whenever a tokenID is minted or transferred to a non-zero address.

It uses the balanceOf() function to determine the index that can be assigned to the newly minted tokenID.

balanceOf() will return 3 for an address that owns 3 tokenIDs. This means that index #3 can be assigned to a newly minted tokenID (since indexing starts from 0).

_addTokenToAllTokensEnumeration: adds a tokenID to the data structures tracking all the NFTs whenever a tokenID is minted, eg., _allTokensIndex

_removeTokenFromAllTokensEnumeration: used when a tokenID is burned to keep the data structures updated.

__removeTokenFromAllTokensEnumeration_ follows a deletion process that is similar to __removeTokenFromOwnerEnumeration_.

Putting The Pieces Together: The _updateFunction

The four private functions that we briefly learned about in the previous section are used by the _update function to mint, burn, or transfer NFTs.

It is invoked whenever the ownership of a tokenID changes. There are two pairs of conditional statements in the function. Let’s understand what they’re doing:

Conditional Statements #1: Checking The Sender Address

The first pair checks if the tokenID is being minted or transferred. It handles the removal of a tokenID from the previous owner’s data structures. Assigning an owner to the tokenID is handled in the next conditional statement.

Case 1: Token is minted

If it is being minted, it calls _addTokenToAllTokensEnumeration, which adds the tokenID to _allTokens and _allTokensIndex.

Case 2: Token is transferred

If it is being transferred, _removeTokenFromOwnerEnumeration is called, which removes the tokenID from _ownedTokens and _ownedTokensIndex of the previousOwner address that the function takes as an input.

Conditional Statements #2: Checking The Receiver Address

The first condition isn’t concerned with the address that the tokenID is being transferred to. It is the second conditional statement that checks whether the tokenID is being burned or transferred to a non-zero address.

Case 1: Token is burned

If it is being burned, the _removeTokenFromAllTokensEnumeration function is called, which removes the tokenID from _allTokens and _allTokensIndex.

Case 2: Token is transferred

If it is being transferred to a non-zero address, _addTokenToOwnerEnumeration is called, which adds the tokenID to _ownedTokens and _ownedTokensIndex of the to address.

Adding ERC721Enumerable To Your Project

In this section, we’ll learn how to add OpenZeppelin’s ERC721Enumerable extension to our ERC721 contract in 2 steps.

1. Import ERC721Enumerable

At the top of your ERC721 file, add in the following line of code with the rest of your imports:

import "@openzeppelin/contracts/token/ERC721/extensions/ERC721Enumerable.sol";

After that, define the contract in the following manner:

contract YourTokenName is ERC721, ERC721Enumerable{

}

2. Overriding Functions

The inclusion of ERC721Enumerable requires some functions from ERC721 to be overridden. These functions are:

1. _update

function _update(
    address to,
    uint256 tokenId,
    address auth
) internal override(ERC721, ERC721Enumerable) returns (address) {
    return super._update(to, tokenId, auth);
}

2. _increaseBalance

function _increaseBalance(address account, uint128 value)
    internal
    override(ERC721, ERC721Enumerable)
{
    super._increaseBalance(account, value);
}

3. supportsInterface

function supportsInterface(bytes4 interfaceId)
    public
    view
    override(ERC721, ERC721Enumerable)
    returns (bool)
{
    return super.supportsInterface(interfaceId);
}

Note: Other extensions of ERC721 that implement a custom balanceOf() function (eg. ERC721Consecutive), cannot be used along with the ERC721Enumerable extension since they tamper with its functionality.

Enumeration At A Cost: Caveats Of The ERC721Enumerable Extension

For every transfer, the data structures in ERC721Enumerable have to be updated. This makes the contract gas-heavy, adding a considerable amount of gas costs. For projects that must list tokenIDs on-chain however, this is a necessary expense.

Authorship

This article was written by Poneta, a research intern at RareSkills.

Learn More With RareSkills

Check out our Solidity Bootcamp to learn advanced Solidity concepts.

Originally Published March 27, 2024