Meebits mint随机算法

先上代码

function randomIndex() internal returns (uint) {
        uint totalSize = TOKEN_LIMIT - numTokens;
        uint index = uint(keccak256(abi.encodePacked(nonce, msg.sender, block.difficulty, block.timestamp))) % totalSize;
        uint value = 0;
        if (indices[index] != 0) {
            value = indices[index];
        } else {
            value = index;
        }

        // Move last value to selected position
        if (indices[totalSize - 1] == 0) {
            // Array position not initialized, so use position
            indices[index] = totalSize - 1;
        } else {
            // Array position holds a value so use that
            indices[index] = indices[totalSize - 1];
        }
        nonce++;
        // Don't allow a zero index, start counting at 1
        return value.add(1);
    }

在mint时随机指定tokenId，可以实现一定程度的随机分配图片，Meebits只用了一个数组且是O(1)的时间复杂度就实现了随机分配tokenId。

总体思想是，keccak256哈希后对剩余可mint数量totalSize进行取模，得到index值，再到indices里取值。如果indices里的值为0表示这个index没用过，就可以直接用index当做tokenId，然后将最末尾的tokenId(也就是totalSize-1)赋值给indices[index]槽位（如果最末尾的tokenId被分配过，就取indices[totalSize-1]的值赋值给indices[index]槽位），表示如果下次取模后的值又是index，那么就取这时候的最后一个tokenId分配给用户，以此来保证不会重复分配tokenId；如果indices里的值不为0，则说明此index被使用过，那么就要用indices[index]槽位存储的值来做tokenId。

ZombieClub的随机tokenId也应用了此类似的算法，只不过他是在chainLink预言机回调时再去分配tokenId。

function fulfillRandomWords(uint256 requestId, uint256[] memory randomWords) internal override {
        uint256 tokenId = chainlinkTokenId[requestId];
        if (tokenInternalInfo[tokenId].requested && tokenInternalInfo[tokenId].revealId == 0) {
            uint256 randomIndex = randomWords[0] % (totalMysteryBoxes - revealedTokens) + revealedTokens;
            uint256 revealId = _tokenIdMap(randomIndex);
            uint256 currentId = _tokenIdMap(revealedTokens);

            tokenIdMap[randomIndex] = currentId;
            tokenInternalInfo[tokenId].revealId = uint64(revealId);
            revealedTokens ++;

            emit RevealReceived(tokenId, revealId);
        }
    }