ERC721A 算法分析与设计

本文作者：bixia1994[1]

参考链接：

1. Openzeppelin 的 EIP721 实现[2]
2. Azuki 的 EIP721A 实现[3]

OpenZepplin 实现的缺点

在一个典型的 NFT 中，通常会利用 OZ 的 EIP721 模板来做如下实现：

function mintNFT(uint256 numberOfNfts) public payable {
    //检查totalsupply不能超过
    require(totalSupply() < MAX_NFT_SUPPLY);
    require(numberOfNfts.add(totalSupply()) < MAX_NFT_SUPPLY);
    //检查numberOfNFT在(0,20]
    require(numberOfNfts > 0 && numberOfNfts <=20);
    //检查价格*numberOfNFT==msg.value
    require(numberOfNfts.mul(getNFTPrice()) == msg.value);
    //执行for循环，每个循环里都触发mint一次，写入一个全局变量
    for (uint i = 0; i < numberOfNfts; i++) {
     uint index = totalSupply();
     _safeMint(msg.sender, index);
    }
}

其中，_safeMint 是 OZ 中提供的 mint API 函数，其具体调用如下：

function _safeMint(
        address to,
        uint256 tokenId,
        bytes memory _data
    ) internal virtual {
        _mint(to, tokenId);
        require(
            _checkOnERC721Received(address(0), to, tokenId, _data),
            "ERC721: transfer to non ERC721Receiver implementer"
        );
    }
function _mint(address to, uint256 tokenId) internal virtual {
        require(to != address(0), "ERC721: mint to the zero address");
        require(!_exists(tokenId), "ERC721: token already minted");

        _beforeTokenTransfer(address(0), to, tokenId);

        _balances[to] += 1;
        _owners[tokenId] = to;

        emit Transfer(address(0), to, tokenId);

        _afterTokenTransfer(address(0), to, tokenId);
    }

从上述的实现过程中可以看到，对于普通的 NFT mint 过程，其算法复杂度是 O(N),即用户需要 mint N 个 NFT，则需要循环调用 N 次单独的 mint 方法。

其最核心的部分在于：OZ 的实现中，在 mint 方法内部，维护了两个全局的 mapping。

分别是用于记录用户拥有的 NFT 数量的 balance 和记录 tokenID 到用户映射的 owners。不管是 mint 还是 transfer，其内部都需要去更新这两个全局变量。单就 mint 来讲，mint 1 个 NFT 就需要进行至少 2 次 SSTORE。而 mint N 个 NFT 则需要进行至少 2N 次 SSTORE。

ERC721A 的改进

从 Openzeppelin 的实现缺点来看，其主要缺点在于没有提供批量 Mint 的 API，使得用户批量 Mint 时，其算法复杂度达到 O(N).故 ERC721A 提出了一种批量 Mint 的 API，使得其算法复杂度降为 O(1).

最简单的想法：

最简单的想法莫过于直接修改_mint 函数，将批量 mint 的数量也作为参数传入，然后在_mint 函数里面修改 balance 和 owners 两个全局变量。由于是批量 mint，与 OZ 的单独 mint 方式不同的是，其需要在 mint 函数内部维护一个全局递增的 tokenID。另一个需要注意的事情是：根据 EIP721 规范，当任何 NFT 的 ownership 发生变化时，都需要发出一个 Transfer 事件。故这里也需要通过 For 循环的方式来批量发出 Transfer 事件。

function _mint(address to, uint256 quantity) internal virtual {
...//checks
        uint256 tokenId = _currIndex;
        _balances[to] += quantity;
        _owners[tokenId] = to;
···//emit Event
        for (uint256 i = 0; i < quantity; i++) {
           emit Transfer(address(0),to,tokenId);
           tokenId++;
        }
   //update index
        _currIndex = tokenId;
}

对该简单想法的分析：

1. 是 O(1)还是 O(N)? 新的 mint 肯定是 O(1)的算法复杂度。容易引起误解的是里面仍然包含了一个 for 循环，但是该 for 循环里面只做了 emit 事件的操作。从 OPCODE 的角度来看，在 for 循环里面，其实只有 LOG4 和 ADD 两个 OPCODE，没有特别消耗 Gas 的 SSTORE。（tokenId++只是一个局部变量的++，而非全局变量的++，对应的 OPCODE 也只是 ADD 而没有 SSTORE）
2. 在上述的 mint 实现中，事实上只在用户 mint 的开头更新了一下对应的 tokenId 的归属，对于后续 tokenId 事实上没有去更新相应的 tokenId 归属，即仍然为 address(0). 如下图所示：alice 在 mint5 个之后，系统事实上只在 tokenId=2 的地方记录了其_owners[2]=alice, 其余的 tokenId 如 3，4，5，6,为节约 SSTORE 的次数，其_owners 仍然为 address(0)=alice, 其余的tokenId如3，4，5，6,为节约SSTORE的次数，其_owners仍然为address(0)![")当下一个用户 Bob 来批量 mint 时，其会从 7 直接开始 mint。

20220211151047.png

该最简单想法的问题：

1. 因为并不是每一个 tokenId 都记录了对应的 owner，那么对于 owners[tokenId]=address(0)的那部分 tokenId 其 owner 应该为谁？如果是 OZ 的实现，每一个 tokenId 都在 owners[tokenId]存在对应的 owner 地址，如果其为 address(0),说明该 tokenId 还没有被 mint 出来,即_exists[tokenId]=false。但是对于 ERC721A 算法，一个 tokenId 的 owners 为 address(0)存在两种可能的情况：1. 该 tokenId 确实还没有 mint 出来，不存在；2. 该 tokenId 属于某一个 owner，但不是该 owner 批量 mint 的第一个。即，应该如何实现 ownerOf 方法：观察 mint 得到的 tokenId，可以发现其均为连续，单调递增的整数序列，即:0,1,2,3... 单纯只考虑 mint 的情况，不考虑 transfer 的情况，可以得到一个简单的算法，即：将该 tokenId 依次递减，遇到的首个不为 address(0)的地址即为该 tokenId 的 Owner。该算法如何排除还没有 mint 出来的那部分 tokenId 呢？可以通过比较 tokenId 与当前的 currIndex，如果 tokenId<currIndex，则说明该 tokenId 的 owner 必然不为 address(0)，如果 tokenId>=currIndex，则说明该 tokenId 还没有被 mint 出来。

20220211151107.png

function _exists(uint256 tokenId) internal view returns (bool) {
   tokenId < _currentIndex;
}

function ownershipOf(uint256 tokenId) internal view returns (TokenOwnership memory) {
//check exists
   require(_exists(tokenId),"OwnerQueryForNonexistentToken");
//遍历 递减
   for (uint256 curr = tokenId;curr >= 0;curr--) {
      address owner = _owners[curr];
      if (owner != address(0)) {
         return owner;
      }
   }
   revert("Ownership Error");
}
function ownerOf(uint256 _tokenId) external view returns (address) {
  return ownershipOf(_tokenId).addr;
}

1. 如果用户 alice 在 mint 后在 transfer 给 bob，此时 alice 的 tokenId 区域就不连续了，此时应该如何来更新？即如何设计 transfer 方法 对于 alice，其拥有 2，3，4，5，6 这 5 个 NFT，当其把 3 转给 bob 时，系统的更新应该如下：首先把 tokenId=3 的 NFT 的 owner 更新 bob，然后在 tokenId=4 的 NFT 的 owner 应该由原来的 address(0)更新为 alice。这里的 transfer 不是批量操作，而是单个 NFT 的操作。对于多个 NFT 的批量 transfer，这种算法仍然需要 O(N).

具体实现逻辑如下：

function _transfer(address from,address to,uint256 tokenId) private {
   //check ownership
   TokenOwnership memory prevOwnership = ownershipOf(tokenId);
   require(from == prevOwnership.addr);
   //update from&to
   balance[from] -= 1;
   balance[to] += 1;
   _owners[tokenId] = to;
   uint256 nextTokenId = tokenId + 1;
   if (_owners[nextTokenId] == address(0) && _exists(nextTokenId)) {
      _owners[nextTokenId] = from;
   }
   emit Transfer(from,to,tokenId);
}

1. 第三个问题是如何实现 tokenOfOwnerByIndex 这一个枚举方法？在 OZ 中，其实现是基于一个全局的 mapping：mapping(address=>mapping(uint256=>uint256)) private _ownedTokens; 然而在 ERC721A 中，并没有给每一个 TokenId 都储存一个对应的 owner，自然也无法通过这种方式来获取到某个 owner 的 tokenid 列表。鉴于 ERC721A 解决的问题比较特殊，即所有的 tokenId 都是连续的整数。一个最简单的思路可以是：遍历整个 tokenId 序列，找到属于该 owner 的所有 tokenId，并按照时间戳的顺序来对所有的 tokenId 进行排序，对于同一个时间戳的，应该按照 tokenId 从小到大的顺序排序。根据 EIP721 标准，其顺序并不作相应的要求。故可以不使用上面的排序方式。只要保证有序就行。 具体的遍历过程应该如下：从 tokenId=0 开始遍历，拿到当前 tokenId 的 owner，记录为 curr。如果下一个 tokenId 的 owner 是 address(0)，则 curr 保持不变；如果下一个 tokenId 的 owner 不是 address(0),则 curr 相应的更新。如果 curr==alice，则判断 tokensIdsIndex==index，如果不等，则 tokensIdsIndex++.如果相等，则直接返回 tokenId。

20220211151200.png

function tokenOfOwnerByIndex(address owner, uint256 index) public view override returns (uint256) {
    //check index <= balance
    require(index <= balanceOf(owner),"OwnerIndexOutOfBounds");
    uint256 max = totalSupply();
    uint256 tokenIdsIndex;
    uint256 curr;
    for (uint256 i = 0; i < max; i++) {
       address alice = _ownes[i];
       if (owner != address(0)) {
          curr = alice;
       }
       if (curr == owner) {
          if (index == tokenIdsIndex) return i;
          tokenIdsIndex++;
       }
    }
    revert("error");

}

ERC721A 算法的局限性

从上面的分析可以看出，ERC721A 算法相较于 Openzeppelin 的 EIP721 实现有比较大的突破，但是也有自身的局限性。还有部分我暂未理解清楚：

局限性：

ERC721A 针对的 NFT 批量铸造过程，需要 tokenId 从 0 开始连续单调递增，如果 tokenId 是不连续的正整数，比如用 timestamp 来作为 tokenId，该算法其实就会失效。

没看懂的部分：

为什么需要一个 timestamp？

struct TokenOwnership {
        address addr;
        uint64 startTimestamp;
    }

这个 startTimestamp 有什么用？

参考资料

[1]

bixia1994: https://learnblockchain.cn/people/3295

[2]

Openzeppelin的EIP721实现: https://learnblockchain.cn/article/3041

[3]

Azuki的EIP721A实现: https://www.azuki.com/erc721a