OpenZeppelin
ERC721Consecutive Meets ERC721Enumerable: A Compatibility Proof-of-Concept
🧐 Motivation
ERC721Consecutive make batch minting possible but it is not IERC721Enumerable compatible. the following contract Is a proof of concept that shows with some minor changes to ERC721Consecutive and ERC721Enumerable. it can be merge to one contract. with following features:
- batch minting during constructor.
- single minting after deployment.
- single burning of a token.
- full IERC721Enumerable compatibility.
- all of the indexing functions are O(1)
📝 Details
the main idea is , how to find the indices of tokens that are not initialized by single minting (like in ERC721Enumerable), while the mappings are empty and they have default value uint 0.
as an example.
tokenByIndex(uint256 index)
since the tokens that are created from batch minting start from tokenId 0 to totalConsecutiveSupply() -1
and Index of tokens have not initialized we can consider TokenIndex the same as tokenId
and if new tokens were minted we initialize them _allIndexToTokenId and _allTokenIdToIndex
and if we burned a token we can initialize the index by a swap operation if it's necessary see _removeTokenFromAllTokensEnumeration(uint256 tokenId)
upon reading the index if _allIndexToTokenId and _allTokenIdToIndex have not initialized and the value inside the mapping was uint(0) it means the token was batch minted and the value is not initialized, so the tokenId is the same as index and the index is the same as tokenId
note:
note: to remove the ambiguity of value uint(0) with default value of mapping that is also uint(0) while populating the
_allIndexToTokenId and _allTokenIdToIndex we write the values + 1 and when we want to access the value if we -1
see tokenByIndex(uint256 index) and _indexByToken(uint256 tokenId) and _addTokenToAllTokensEnumeration(uint256 tokenId) and _removeTokenFromAllTokensEnumeration(uint256 tokenId)
//list of all tokenId available(some values are available virtauly to access use tokenByIndex(_index))
mapping(uint256 => uint256) private _allIndexToTokenId;
//mapping of tokenId to index in _allIndexToTokenId(some value are available virtual to access use _indexByToken(tokenId))
mapping(uint256 => uint256) private _allTokenIdToIndex;
/**
* @dev See {IERC721Enumerable-tokenByIndex}.
*/
/**
* @dev handling tokens index virtually
*/
function tokenByIndex(uint256 index)
public
view
virtual
override
returns (uint256)
{
require(
index < ERC721CE.totalSupply(),
"ERC721Enumerable: global index out of bounds"
);
uint256 virtualIndex = _allIndexToTokenId[index];
//if mapping is empty, index is the same as tokenId, since they are all sequential and start from 0
if (virtualIndex == 0) {
return index;
}
return virtualIndex - 1; //decrement one (-1) to get the value, overflow is impossible because the virtualIndex is not 0.
}
////provied the token Index in the list of all tokens that have been created.
function _indexByToken(uint256 tokenId) private view returns (uint256) {
uint256 virtualIndex = _allTokenIdToIndex[tokenId];
//if mapping is empty, tokenId is the same as index, since they are all sequential and start from 0
if (virtualIndex == 0) {
return tokenId;
}
return virtualIndex - 1; //decrement one (-1) to get the value,overflow is impossible becuase the virtualIndex is not 0.
}
/**
* @dev Private function to add a token to this extension's token tracking data structures.
* @param tokenId uint256 ID of the token to be added to the tokens list
* write values + 1 to avoid confusion to mapping default value of uint (uint(0))
*/
function _addTokenToAllTokensEnumeration(uint256 tokenId) private {
uint256 _index = totalSupply();
// + 1 to remove the ambiguity of value with default value(uint 0) in mapping of _allIndexToTokenId and _allTokenIdToIndex
_allIndexToTokenId[_index] = tokenId + 1;
_allTokenIdToIndex[tokenId] = _index + 1;
}
/**
* @dev Private function to remove a token from this extension's token tracking data structures.
* This has O(1) time complexity, but works with to new mapping _allIndexToTokenId, _allTokenIdToIndex
* functionality is more similar to _removeTokenFromOwnerEnumeration(address from, uint256 tokenId)
* @param tokenId uint256 ID of the token to be removed from the tokens list
*/
function _removeTokenFromAllTokensEnumeration(uint256 tokenId) private {
uint256 lastIndex = totalSupply() - 1;
// uint256 tokenIndex = tokenByIndex(tokenId);
uint256 tokenIndex = _indexByToken(tokenId);
if (lastIndex != tokenIndex) {
uint256 lastTokenId = tokenByIndex(lastIndex);
// + 1 to remove the ambiguity of value with default value(uint 0) in mapping of _allIndexToTokenId and _allTokenIdToIndex
_allIndexToTokenId[tokenIndex] = lastTokenId + 1;
_allTokenIdToIndex[lastTokenId] = tokenIndex + 1;
}
delete _allIndexToTokenId[lastIndex];
delete _allTokenIdToIndex[tokenId];
}
this implementation can be a stand alone extension ERC721ConsecutiveEnumerable.sol or it can be break down as a changes to ERC721Consecutive.sol and ERC721Enumerable to make them compatible with each other.
github - ERC721ConsecutiveEnumerable
Goerli testnet : 0xaF8fA6fC07Da285a94f37148218fFd170eE827ff
thank you for your time. sciNFTist.eth
In this comment I will explain how we can Index batch minted tokens by lazy indexing.
_ownedTokens mapping is the data structure responsible for indexing an arbitrary owner tokens, but since in the batch minting this mapping won't be initialize, we can consider all of their token indexes sequentially from their first tokenId that they batch minted. and upon the transfer of a token we populate _ownedTokens and _ownedTokensIndex with a swap operation if it is necessary see _removeTokenFromOwnerEnumeration(address from, uint256 tokenId).
if _ownedTokens[owner][index] was equal to 0 it means the token index is not initialized and we can access it virtually
with tokenId - _ownerStartTokenId[_owner]
note: to remove the ambiguity of value uint(0) with default value of mapping that is also uint(0) while populating the _ownedTokens and _ownedTokensIndex we write the values + 1 and when we want to access _ownedTokens and _ownedTokensIndex we - 1. see _addTokenToOwnerEnumeration(address to, uint256 tokenId) and _ownerTokenByIndex(address owner, uint256 index) and _ownerIndexByToken(uint256 tokenId)
// Mapping from owner to list of owned token IDs (some values are available virtualy to access use _ownerTokenByIndex(_owner,_index) )
mapping(address => mapping(uint256 => uint256)) private _ownedTokens;
// Mapping from token ID to index of the owner tokens list(some values are available virtualy to access use _ownerIndexByToken(_tokenId))
mapping(uint256 => uint256) private _ownedTokensIndex;
////-------starting tokenId for batch minters , populated by _mintConsecutive(address to, uint96 batchSize)
mapping(address => uint256) private _ownerStartTokenId;
/**
* @dev See {IERC721Enumerable-tokenOfOwnerByIndex}.
*/
function tokenOfOwnerByIndex(address owner, uint256 index)
public
view
virtual
override
returns (uint256)
{
require(
index < ERC721.balanceOf(owner),
"ERC721Enumerable: owner index out of bounds"
);
return _ownerTokenByIndex(owner, index); //see _ownerTokenByIndex(owner, index)
}
/**
*
*
* @dev See {ERC721-_beforeTokenTransfer}, Hook that is called before any token transfer. This includes minting
* and burning.
*
* hook modified for consecutive transfer while maintaning enumarability
*/
function _beforeTokenTransfer(
address from,
address to,
uint256 tokenId,
uint256 batchSize
) internal virtual override {
super._beforeTokenTransfer(from, to, tokenId, batchSize);
//enumeration operations does not triger during batch minting and instead will be handled virtualy.
if (batchSize > 1) {
require(
!Address.isContract(address(this)),
"batch minting is restricted to constructor"
);
} else {
if (from == address(0)) {
_addTokenToAllTokensEnumeration(tokenId);
} else if (from != to) {
_removeTokenFromOwnerEnumeration(from, tokenId);
}
if (to == address(0)) {
_removeTokenFromAllTokensEnumeration(tokenId);
} else if (to != from) {
_addTokenToOwnerEnumeration(to, tokenId);
}
}
}
/**
* @dev Private function to add a token to this extension's ownership-tracking data structures.
* @param to address representing the new owner of the given token ID
* @param tokenId uint256 ID of the token to be added to the tokens list of the given address
* write values + 1 to avoid confussion to mapping default value of uint (uint(0))
*/
function _addTokenToOwnerEnumeration(address to, uint256 tokenId) private {
uint256 length = ERC721.balanceOf(to);
// + 1 to remove the ambiguity of value with default value(uint 0) in mapping of _ownedTokens and _ownedTokensIndex
_ownedTokens[to][length] = tokenId + 1;
_ownedTokensIndex[tokenId] = length + 1;
}
/**
* @dev Private function to remove a token from this extension's ownership-tracking data structures. Note that
* while the token is not assigned a new owner, the `_ownedTokensIndex` mapping is _not_ updated: this allows for
* gas optimizations e.g. when performing a transfer operation (avoiding double writes).
* This has O(1) time complexity, but alters the order of the _ownedTokens array.
* @param from address representing the previous owner of the given token ID
* @param tokenId uint256 ID of the token to be removed from the tokens list of the given address
* write values + 1 to avoid confussion to mapping default value of uint (uint(0))
*/
function _removeTokenFromOwnerEnumeration(address from, uint256 tokenId)
private
{
// To prevent a gap in from's tokens array, we store the last token in the index of the token to delete, and
// then delete the last slot (swap and pop).
uint256 lastTokenIndex = ERC721.balanceOf(from) - 1;
// uint256 tokenIndex = _ownedTokensIndex[tokenId];
uint256 tokenIndex = _ownerIndexByToken(tokenId);
// When the token to delete is the last token, the swap operation is unnecessary
if (tokenIndex != lastTokenIndex) {
// uint256 lastTokenId = _ownedTokens[from][lastTokenIndex];
uint256 lastTokenId = _ownerTokenByIndex(from, lastTokenIndex); //[from][lastTokenIndex];
// + 1 to remove the ambiguity of value with default value(uint 0) in mapping of _ownedTokens and _ownedTokensIndex
_ownedTokens[from][tokenIndex] = lastTokenId + 1; // Move the last token to the slot of the to-delete token
_ownedTokensIndex[lastTokenId] = tokenIndex + 1; // Update the moved token's index
}
// This also deletes the contents at the last position of the array
delete _ownedTokensIndex[tokenId];
delete _ownedTokens[from][lastTokenIndex];
}
//like tokenOfOwnerByIndex but does NOT revert
/**
* @dev See {IERC721Enumerable-tokenOfOwnerByIndex}.
*/
function _ownerTokenByIndex(address owner, uint256 index)
private
view
returns (uint256)
{
uint256 virtual_tokenId = _ownedTokens[owner][index];
//if there is noting is stored in the mapping, consider tokenId sequentialy from _ownerStartTokenId[owner]
if (virtual_tokenId == 0) {
return index + _ownerStartTokenId[owner]; //new
} else {
return virtual_tokenId - 1; //decrement one (-1) to get the value,overflow is impossible becuase the virtual_tokenId is not 0.
}
}
//finding the index of a token in tokens list that owned by the owner
function _ownerIndexByToken(uint256 tokenId)
private
view
returns (uint256)
{
//if there is noting is stored in the mapping, consider index sequentialy from _ownerStartTokenId[_owner]
uint256 virtual_index = _ownedTokensIndex[tokenId];
if (virtual_index == 0) {
address _owner = _ownerOf(tokenId);
return tokenId - _ownerStartTokenId[_owner];
} else {
return virtual_index - 1; //decrement one (-1) to get the value,overflow is impossible becuase the virtual_Index is not 0.
}
}
In this comment I'm going to explain how we can calculate the totalSupply of the token.
_totalConsecutiveSupply() count how many tokens were batch minted, and this value won't change after batch minting is finished.
totalSupply() is equal to number of tokens that were batch minted + number of tokens that exist beyond batch minted range - number of the tokens that we burned inside the batch minting range.
-
_totalConsecutiveSupply(): number of tokens that are batch minted -
_mintCounter: number of tokens that exist beyond batch minted range -
_burnCounter: number of the tokens that we burned inside the batch minting range
_mintCounter and _burnCounter are updated via {_afterTokenTransfer} hook.
note:
{_afterTokenTransfer} won't trigger during batch minting. require(batchSize > 1, "for single Mint use _mint()"); see batch minting
// number of tokens minted beyond consecutiveSupply range
uint256 private _mintCounter;
// number of token burned inside consecutiveSupply range
uint256 private _burnCounter;
/**
* @dev See {IERC721Enumerable-totalSupply}.
*/
function totalSupply() public view virtual override returns (uint256) {
return _totalConsecutiveSupply() + _mintCounter - _burnCounter;
}
function _totalConsecutiveSupply() private view returns (uint96) {
(bool exists, uint96 latestId, ) = _sequentialOwnership
.latestCheckpoint();
return exists ? latestId + 1 : 0;
}
/**
* @dev See {ERC721-_afterTokenTransfer}. Burning of tokens that have been sequentially minted must be explicit.
*/
function _afterTokenTransfer(
address from,
address to,
uint256 firstTokenId,
uint256 batchSize
) internal virtual override {
if (to == address(0)) {
require(
batchSize == 1,
"ERC721Consecutive: batch burn not supported"
);
if (firstTokenId < _totalConsecutiveSupply()) {
_sequentialBurn.set(firstTokenId);
_burnCounter += 1;
} else {
_mintCounter -= 1;
}
}
if (from == address(0) && batchSize == 1) {
if (firstTokenId < _totalConsecutiveSupply()) {
_burnCounter -= 1;
_sequentialBurn.unset(firstTokenId);
} else {
_mintCounter += 1;
}
}
super._afterTokenTransfer(from, to, firstTokenId, batchSize);
}
Hi @shypink I'm really interested in your solution because I was working with old contact and found out that it is impossible to expose _consecutiveMint function to mint the next batch.
My case is to mint the first batch of 10k NFTs and then mint 10k more. With the not-enumerable contracts after minting the first batch and before minting the next batch, a token with id 15000 might be already taken, so this is impossible (or gas-heavy) to keep track of the sequence But with the enumerable, this is not the case, so I can do at least 2 mints Btw I don't understand why it uses the uint96 restriction, In the same way, it can use unit128 or uint256, it does not change the storage layout.
Hi @TrejGun , thank you for reading,
- If you want to batch mint outside of contract constructor you should be aware that if you made single mint between batch mints for example( in above scenario that you batch minted 10k in constructor, let say you minted tokenId
12345and then you batch minted 10k item again tokens 10000 ~ 19999, we have problem. because there are 20000 token in existence in the contract 0 ~ 19999 but your balance would be 20001 and the contract counted token 12345 twice) so if you are not very careful in the implementation of batch minting your contract won't be ERC721 compliant, this why OpenZeppelin ERC721Consecutive batch mint require to be called in constructor, and disable single mint in the constructor. this also true in the case of ERC721A developed by chirulab, but if you are careful in your implementation you can work around it. for instance you can disable single mint and force the contract to perform minting in sequential order. - for enumerability of you have to be careful if you want to enable one owner to batch mint twice, in my implementation of ERC721ConsecutiveEnumerable I forced the mint function to check for
require(balanceOf(owner) == 0)to guarantee each user only mint one batch so all of the tokens are in sequential order, if you want to batch mint twice to same owner in different times you have to provide an structure to store start TokenId for each batch and owner. - the uint96 restriction, it's because ERC721Consecutive.sol uses Checkpoints.sol for storing batch minted data as list checkpont160
struct Checkpoint160 {
uint96 _key;
uint160 _value;
}
since the Ethereum addresses are 20 bytes long they can be converted to uint160 and since EVM store data in chunks of 32bytes the efficient data structure is to use 20bytes for address and 12bytes for key, in this case TokenId and a 12 bytes uint is (12*8) uint96 , if we use uint256 it need 2 word of storage, Ethereum yellow paper
@shypink thanks for the detailed explanation
- that is what I tried to say
it also looks like I can't do consecutive mints twice in the constructor with the current implementation too
constructor() ERC721("X","Y") {
_mintConsecutive(_msgSender(), 5000);
_mintConsecutive(_msgSender(), 5000);
}
and this is impossible to prevent
- It looks like by providing a structure
struct MyStructure {
uint256 _startTokenId;
uint256 _batchSize;
address _owner;
}
I can get rid of the Checkpoint and the uint96 restriction too. but the downside would be algorithm complexity and the storage size
At this point looping through all tokens in the batch doesn't seem that bad to me
function function _mintConsecutive(address to, uint256 batchSize) internal virtual {
require(to != address(0), "ERC721: mint to the zero address");
// there should be some check to ensure currentTokenId + batchSize < uint256
// maybe even check batchSize < 5000
uint256 tokenId = _tokenIdTracker.current();
_beforeTokenTransfer(address(0), to, tokenId, batchSize);
unchecked {
_balances[to] += batchSize;
}
for (uint256 i = 0; i < batchSize; i++) {
tokenId = _tokenIdTracker.current();
_owners[tokenId] = to;
_tokenIdTracker.increment();
}
emit ConsecutiveTransfer(tokenId, tokenId + batchSize, address(0), to);
_afterTokenTransfer(address(0), to, tokenId, batchSize);
}
- thanks for pointing me out to Checkpoint implementation, maybe you can also explain to me why there is a cap of 5000 tokens per batch?
I'm glad that I could help,
- there is nothing that prevent you to use
{_mintConsecutive}twice, maybe data type isn't right if you are using ERC721Consecutive.sol since_mintConsecutive(address to, uint96 batchSize)need batchSizeuint96you can cast or safeCastuint256touint96if you should. - Checkpoint library provide a binary search that is more efficient. and remove the need to initialize the
_owner[tokenId]storage for all of the token, sequentially. and you populate the storage when they transferred. - 5000 batch size limitation is an artificial limitation posed by notable NFT marketplaces, and I think there should be better way like a daily limitation on token creation, but there is this limitation for now, maybe you could use my Implementation of ERC721ConsecuitveEnumerable and emit consecutiveTransfer event in batches of 5k at most.
////////-------------------------
/**
* @dev some minor changes to ERC721Consecutive
* @param receivers should be list of unique user(no duplicates)
* @param amounts amounts can be more than 5000 and emiting consecutiveTransfer() event will be handled in batches of 5000 at most. see _mintConsecutive()
* @param amounts can not be equal to 1, for single minting use _mint, this was forced to avoid trigering {_afterTokenTransfer} during batch minting.
*/
constructor(
string memory name_,
string memory symbol_,
address[] memory receivers,
uint96[] memory amounts
) ERC721(name_, symbol_) {
for (uint256 i = 0; i < receivers.length; ++i) {
uint96 a = _mintConsecutive(receivers[i], amounts[i]);
}
}
//see ERC721Consecutive.sol // omited for now and set to 5k
// function _maxBatchSize() internal view virtual returns (uint96) {
// return 5000;
// }
// private
function _mintConsecutive(address to, uint96 batchSize)
private
returns (uint96)
{
uint96 first = _totalConsecutiveSupply();
// minting a batch of size 0 is a no-op//require batchSize > 1
if (batchSize > 0) {
require(
!Address.isContract(address(this)),
"ERC721Consecutive: batch minting restricted to constructor"
);
require(
to != address(0),
"ERC721Consecutive: mint to the zero address"
);
// require(
// batchSize <= _maxBatchSize(),
// "ERC721Consecutive: batch too large"
// );
// for not trigerimg {_afterTokenTransfer} during batch minting
require(batchSize > 1, "for single Mint use _mint()");
require(
ERC721.balanceOf(to) == 0,
"each account can batch mint once"
);
// hook before
_beforeTokenTransfer(address(0), to, first, batchSize);
/*
*new
*/
_ownerStartTokenId[to] = first; //storing start token id of batch minting to batch minter address
// push an ownership checkpoint & emit event
uint96 last = first + batchSize - 1;
_sequentialOwnership.push(last, uint160(to));
//emit in bundle of 5k
while (first < last) {
if (last - first > 5000) {
emit ConsecutiveTransfer(
first,
first + 4999,
address(0),
to
);
first = first + 5000;
} else {
emit ConsecutiveTransfer(first, last, address(0), to);
first = first + 5000;
}
}
// emit ConsecutiveTransfer(first, last, address(0), to);
// hook after
_afterTokenTransfer(address(0), to, first, batchSize);
}
return first;
}
1 It has the same problem as your implementation, however, you check require(balanceOf(owner) == 0) and the current implementation does not
2 I will run both solutions and check gas usage with hardhat-gas-reporter, not sure how to check storage size tho
for updating _balances you can use {_beforeTokenTransfer} hook in ERC721 OpenZepplen v4.8.0 and for _owners you can override the _ownerOf(tokenId) see {ownerOf} but you should be careful in your implementation.
@scinftist Hey hey, still playing around with your PoC
I want to match the interface of the original ER721Enumerable and have such safeMint function or something similar
function safeMint(address to) public virtual onlyRole(MINTER_ROLE) {
_safeMint(to, _tokenIdTracker.current());
_tokenIdTracker.increment();
}
to get the actual counter I have to add the initial batch size but _totalConsecutiveSupply is private, so maybe you consider making it at least internal
_totalConsecutiveSupply() + _tokenIdTracker.current()
Hey @TrejGun sorry I didn't seen your comment sooner.
great point I made initial _totalConsecutiveSupply() internal. it comes handy in development.
but {_safeMint} is part of the OpenZeppelin ERC721.sol and this contract inherit ERC721.sol, so {_safeMint} is available to use.