ERC721A 算法分析与设计

  • 时间:
  • 浏览:234
  • 来源:区块链技术网

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-04-17

十大虚拟币排行,比特币上榜,第三关注度极高

十大虚拟币排行,比特币上榜,第三关注度极高 十大虚拟货币,指非真实的货币,主要用于互联网金融投资,它代表着一种价值,但需要广大网友注意的是,币圈投资有风险,入圈需谨慎,不要盲目跟风,那么你知道的虚拟货币都有哪些呢?学姐为大家整理了2022年十大虚拟货币排名一览,感兴趣的一起来看看吧。

2022-04-17

2022区块链赚钱方向 2022年区块链行业研究报告

2022区块链赚钱方向 2022年区块链行业研究报告 1.NFT市场综述 1.1.什么是NFT:虚拟资产或实物资产的数字所有权证书

2022-04-17

币圈大佬23岁赚1个亿,钱不知道怎么花

币圈大佬23岁赚1个亿,钱不知道怎么花 币圈一直充斥着各路神仙的传奇。但提到矿池,就不得不提矿池始祖七彩神仙鱼毛世行了,也是我们口中的神鱼大佬。神鱼是现在是全球最大的综合性矿池鱼池f2pool联合创始人,资深矿工,目前鱼池f2pool是全球最大的以太坊矿池。

2022-04-17

2022年可能大涨的币种,2022小币种必崛起

2022年可能大涨的币种,2022小币种必崛起 因为比较忙而错过春晚,这几天时不时关注下新闻,春节联欢晚会上麻花团队沈腾在小品《还不还》中多次提及“元宇宙里的DogeKing”,而在沈腾元宇宙的春晚小品结束后,同名DogeKing加密货币短线暴涨542倍。

2022-04-17