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:
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.
There are more gas-efficient ways to store a list of data (discussed later).
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:
- all the
tokenIDs
in existence. - 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:
- _update
function _update(
address to,
uint256 tokenId,
address auth
) internal override(ERC721, ERC721Enumerable) returns (address) {
return super._update(to, tokenId, auth);
}
- _increaseBalance
function _increaseBalance(address account, uint128 value)
internal
override(ERC721, ERC721Enumerable)
{
super._increaseBalance(account, value);
}
- 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,sa 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