ERC721: Allow for lower-gas-cost minting with sequential IDs (and no burning)

[KaiRo-at]

As discussed in #2160 (comment) and the following comments, the merging of contracts in #2160 took away the possibility of an optimization that we at Capacity used e.g. for Crypto stamp Edition 1 and want to be using again in future projects (we have one going right now where we need it).

In those projects, we previously could replace the ERC721Enumerable implementation with an ERC721EnumerableSimple variant (see Crypto stamp 1 code, starting at line 534), which could save us two SSTOREs (40k gas) per token on minting, which sums up to quite some money when minting 150k tokens like we did there.
Of course, this optimization does not work when token IDs can be random, but for those collectibles, we already had the requirements in place that:

• token IDs start with 0 and are strictly sequential
• and tokens cannot be burned

When those two requirements are in place (which can be not just for those collectibles which always have a physical "twin" but also in a number of other cases), we know that in tokenByIndex(), the index and tokenId are always the same - and that allows for removing the back-end to this function and that saves us that gas on minting.

In the OpenZeppelin 2.x structure, the main ERC721.sol implementation could still be reused with this approach by just replacing ERC721Enumerable - but in OpenZeppelin 3.0, with the merged ERC721.sol, this is not possible that easily.
It would be great if there was a way to do this still in the future.

[KaiRo-at]

A solution I did in our projects for the moment is to have a full copy of ERC721.sol with only the EnumerableMap library replaced, the changed library has those changes:

--- openzeppelin-contracts/utils/EnumerableMap.sol      1985-10-26 09:15:00.000000000 +0100
+++ contracts/EnumerableMapSimple.sol   2020-04-14 18:07:43.454981171 +0200
@@ -1,6 +1,6 @@
 pragma solidity ^0.6.0;
 
-library EnumerableMap {
+library EnumerableMapSimple {
     // To implement this library for multiple types with as little code
     // repetition as possible, we write it in terms of a generic Map type with
     // bytes32 keys and values.
@@ -10,18 +10,9 @@
     // This means that we can only create new EnumerableMaps for types that fit
     // in bytes32.
 
-    struct MapEntry {
-        bytes32 _key;
-        bytes32 _value;
-    }
-
     struct Map {
         // Storage of map keys and values
-        MapEntry[] _entries;
-
-        // Position of the entry defined by a key in the `entries` array, plus 1
-        // because index 0 means a key is not in the map.
-        mapping (bytes32 => uint256) _indexes;
+        bytes32[] _entries;
     }
 
     /**
@@ -32,17 +23,14 @@
      * already present.
      */
     function _set(Map storage map, bytes32 key, bytes32 value) private returns (bool) {
-        // We read and store the key's index to prevent multiple reads from the same storage slot
-        uint256 keyIndex = map._indexes[key];
+        uint256 uintKey = uint256(key);
+        require(uintKey <= map._entries.length, "Cannot add entry that is not connected to existing IDs");
 
-        if (keyIndex == 0) { // Equivalent to !contains(map, key)
-            map._entries.push(MapEntry({ _key: key, _value: value }));
-            // The entry is stored at length-1, but we add 1 to all indexes
-            // and use 0 as a sentinel value
-            map._indexes[key] = map._entries.length;
+        if (uintKey == map._entries.length) { // add new entry
+            map._entries.push(value);
             return true;
         } else {
-            map._entries[keyIndex - 1]._value = value;
+            map._entries[uintKey] = value;
             return false;
         }
     }
@@ -52,45 +40,15 @@
      *
      * Returns true if the key was removed from the map, that is if it was present.
      */
-    function _remove(Map storage map, bytes32 key) private returns (bool) {
-        // We read and store the key's index to prevent multiple reads from the same storage slot
-        uint256 keyIndex = map._indexes[key];
-
-        if (keyIndex != 0) { // Equivalent to contains(map, key)
-            // To delete a key-value pair from the _entries array in O(1), we swap the entry to delete with the last one
-            // in the array, and then remove the last entry (sometimes called as 'swap and pop').
-            // This modifies the order of the array, as noted in {at}.
-
-            uint256 toDeleteIndex = keyIndex - 1;
-            uint256 lastIndex = map._entries.length - 1;
-
-            // When the entry to delete is the last one, the swap operation is unnecessary. However, since this occurs
-            // so rarely, we still do the swap anyway to avoid the gas cost of adding an 'if' statement.
-
-            MapEntry storage lastEntry = map._entries[lastIndex];
-
-            // Move the last entry to the index where the entry to delete is
-            map._entries[toDeleteIndex] = lastEntry;
-            // Update the index for the moved entry
-            map._indexes[lastEntry._key] = toDeleteIndex + 1; // All indexes are 1-based
-
-            // Delete the slot where the moved entry was stored
-            map._entries.pop();
-
-            // Delete the index for the deleted slot
-            delete map._indexes[key];
-
-            return true;
-        } else {
-            return false;
-        }
+    function _remove(Map storage /*map*/, bytes32 /*key*/) private pure returns (bool) {
+        revert("No removal supported");
     }
 
     /**
      * @dev Returns true if the key is in the map. O(1).
      */
     function _contains(Map storage map, bytes32 key) private view returns (bool) {
-        return map._indexes[key] != 0;
+        return uint256(key) < map._entries.length;
     }
 
     /**
@@ -112,9 +70,7 @@
     */
     function _at(Map storage map, uint256 index) private view returns (bytes32, bytes32) {
         require(map._entries.length > index, "EnumerableMap: index out of bounds");
-
-        MapEntry storage entry = map._entries[index];
-        return (entry._key, entry._value);
+        return (bytes32(index), map._entries[index]);
     }
 
     /**
@@ -132,9 +88,9 @@
      * @dev Same as {_get}, with a custom error message when `key` is not in the map.
      */
     function _get(Map storage map, bytes32 key, string memory errorMessage) private view returns (bytes32) {
-        uint256 keyIndex = map._indexes[key];
-        require(keyIndex != 0, errorMessage); // Equivalent to contains(map, key)
-        return map._entries[keyIndex - 1]._value; // All indexes are 1-based
+        uint256 uintKey = uint256(key);
+        require(map._entries.length > uintKey, errorMessage); // Equivalent to contains(map, key)
+        return map._entries[uintKey];
     }
 
     // UintToAddressMap
@@ -159,7 +115,7 @@
      *
      * Returns true if the key was removed from the map, that is if it was present.
      */
-    function remove(UintToAddressMap storage map, uint256 key) internal returns (bool) {
+    function remove(UintToAddressMap storage map, uint256 key) internal view returns (bool) {
         return _remove(map._inner, bytes32(key));
     }

With that, I can reclaim those 40k gas per token on minting and not touch the actual ERC721 implementation code, keeping custom changes confined to this library. Unfortunately, I still need a full copy of ERC721.sol as Solidity doesn't allow just overriding a used library.
But maybe we can find a better solution here that actually allows real reuse of the OpenZeppelin code.

[nventuro]

This is an interesting limitation of the Contracts library and Solidity in general. The behavior you want to change is encapsulated inside EnumerableMap (as can be seem by you fixing the issue by just modifying that library), but the notions of overriding library functions or inyecting dependencies don't exist in the language.

We saw something similar happen in an ERC777 contract, where a user wanted to store balances in a different data structure and had to end up with duplicated entries (both the original and their custom ones).

@chriseth I believe you mentioned during the Solidity Summit wanting to extend what can be done with internal functions in libraries (soon to be free functions) - have you considered mechanisms to replace or otherwise modifiy them as discussed here?

[frangio]

This could be achieve with templatized contracts. The template parameter would be the library used, and we'd have a default value but the user would be able to replace it.

Free functions would actually go against this idea.

[nventuro]

Free functions would actually go against this idea.

Because you'd need to have a concept of a group of internal functions? (what is now sort of achieved with library)

[chriseth]

I'm sorry, I have a hard time grasping the gist of this issue or the question by you, @nventuro.
I would be very much interested, though, in how templates can help and why free functions are a problem (or which aspect of free functions).

[frangio]

@chriseth Sorry for the delay in replying. This issue is a request for the ability to customize how one of our contracts works, but it's a kind of internal customization that we can't provide without more advanced language support. An example of a language construct that would help would be (bounded) templates to parameterize the data structure we use internally, so that users would be able to swap that out with an alternative that has added (or removed) features according to their needs.

Free functions wouldn't be a problem, but this pattern would not work with only free functions because the contract would need to be parameterized with the whole data structure + functions bundle.

[chriseth]

OK, I think I understand the problem better now. I fear that templates are not really the solution here. Templates, at least as we currently envision them, are pieces of code that can be applied to different datatypes, but the code will always look the same. I'm not sure if libraries would qualify for data types, though.

As far as I see, EnumerableMapSimple more or less exchanges the complete code of EnumerableMap. Why can't it be its own library?

[frangio]

@chriseth I see what you mean. I think my suggestion was based on languages that have custom datatypes with attached functions, and it's easy to mistake the struct+library combo as that, even though it isn't.

The language features required for what I mentioned are too far from current Solidity, so I think we can leave this on the side now until some time in the future. Thanks for taking the time to join the conversation!

On your last paragraph, the goal would not be changing EnumerableMap itself, but the internal data structure used by ERC721Enumerable which is by default EnumerableMap.

[frangio]

There has been quite a bit of interest in this feature in the past few months. The "ERC721A" implementation by Azuki makes same tradeoffs (that we consider unacceptable) with the purpose of enabling cheap batch minting.

We want to revisit this and see if there's a way to implement cheap batch minting with acceptable tradeoffs.

[rubo]

@frangio Could you please elaborate on what tradeoffs exactly you mean?

[frangio]

@rubo Functions like tokenOfOwnerByIndex use unbounded loops. Please see this thread: https://forum.openzeppelin.com/t/erc721enumerable-gas-optimization/22795

[frangio]

Fixed in #3311.

Currently in release candidate.

Note: Burning is available even for consecutive mints.

[xinbenlv]

FYI, compatibility issue of EIP-2309 with ERC-721 have been raised per this discussion and this discussion

[frangio]

There is no compatibility issue. Please open a new issue if you still believe otherwise.