ERC721A 算法分析与设计

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。

该最简单想法的问题：

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
2. =currIndex，则说明该 tokenId 还没有被 mint 出来。

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 方法
2. 对于 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 标准，其顺序并不作相应的要求。故可以不使用上面的排序方式。只要保证有序就行。
2. 具体的遍历过程应该如下：从 tokenId=0 开始遍历，拿到当前 tokenId 的 owner，记录为 curr。如果下一个 tokenId 的 owner 是 address(0)，则 curr 保持不变；如果下一个 tokenId 的 owner 不是 address(0),则 curr 相应的更新。如果 curr==alice，则判断 tokensIdsIndex==index，如果不等，则 tokensIdsIndex++.如果相等，则直接返回 tokenId。

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，该算法其实就会失效。

没看懂的部分：

1. 为什么需要一个 timestamp？
2. struct TokenOwnership {        address addr;        uint64 startTimestamp;    }

这个 startTimestamp 有什么用？

猜你喜欢

比特币提现会被银行查吗？

比特币提现会被银行查吗？ 首先，根据《中华人民共和国反洗钱法》、《金融机构大额交易和可疑交易报告管理办法》、《金融机构报告涉嫌恐怖融资的可疑交易管理办法》等法律法规的相关规定，银行会对大额资金的流动做监控，主要是审查来源是否合法，是否涉嫌洗钱。

2022-05-21

比特币暴跌50%！30岁老公玩比特币输了好多钱

比特币暴跌50%！30岁老公玩比特币输了好多钱 过去的一周里，作为一个游曳在币圈边缘的键盘侠，见识了币圈度日如年的跌宕后，仍可以笑看潮起潮落。

2022-05-21

UST爆雷之后，USDT也要爆雷了？

这几天的行情，证明了良心哥的推测非常准确。 首先是5月10日分析luna背后是被人开了黑枪，并且持续看空luna。 次日消息实锤，luna再次跌了个99%。 昨天分析说，luna的死亡螺旋会带崩大盘。

2022-05-21

Luna币7天蒸发2000亿，但更怕的是熊市即将到来！

心哥昨天虽然不知道这里边的细节，但依然非常确定的告诉大家，这是一场狙击战，找的就是这个空档，打出来的子弹是要人命的。 另外排队枪毙这个场景，估计今天很多人也领教了。

2022-05-21

一天蒸发400亿人民币，Luna是如何被狙击的？

你们也都知道良心哥炒币是个渣渣，但良心哥的判断大体还是准确的。 可能这就是从业时间久了的盘感吧。 有人说luna的暴跌，ust抛锚，都他吗赖孙宇晨。 从5月5号孙宇晨宣布进军算法稳定币之后，大盘就崩了

2022-05-21

上一篇

ens简介：ENS源码分析

下一篇

最详细的解释EVM的函数选择原理