# Bitmap结构在ENSToken里的应用 **Published by:** [franx.eth](https://paragraph.com/@franx-2/) **Published on:** 2022-05-14 **URL:** https://paragraph.com/@franx-2/bitmap-enstoken ## Content 在ENSToken的合约里看到了Bitmaps的应用，在地址认领空投时用了Merkle树证明来check用户地址和认领数量，进而会对应一个Merkle的index，为了防止重复认领空投，合约里用了OpenZeppelin的Bitmaps库来做位图存储，地址认领成功后，就将对应的index在位图里存true，下次如果再来认领就会判断这个位图，如果为true时就返回错误，以此来防止重复认领空投。BitMaps.BitMap private claimed; /** * @dev Claims airdropped tokens. * @param amount The amount of the claim being made. * @param delegate The address the tokenholder wants to delegate their votes to. * @param merkleProof A merkle proof proving the claim is valid. */ function claimTokens(uint256 amount, address delegate, bytes32[] calldata merkleProof) external { bytes32 leaf = keccak256(abi.encodePacked(msg.sender, amount)); (bool valid, uint256 index) = MerkleProof.verify(merkleProof, merkleRoot, leaf); require(valid, "ENS: Valid proof required."); require(!isClaimed(index), "ENS: Tokens already claimed.");//认领过就revert claimed.set(index);//设置位图，表示当前index认领过空投 emit Claim(msg.sender, amount); _delegate(msg.sender, delegate); _transfer(address(this), msg.sender, amount); } 普通的做法可以用mapping(uint256=>bool) hasClaimed来实现此功能，认领过就hasClaimed[index]=true，这样做每个index都要进行一下写storage操作，消耗较多的gas。可以采用位图来优化存储，因为uint256有256位，每位对应一个bool值，最多可以存储256个index，显然不够，因此可以将index拆分成n个256，存储到多个槽位，就变成mapping(uint256=>uint256) _data结构来存储位图。struct BitMap { mapping(uint256 => uint256) _data; } function set(BitMap storage bitmap, uint256 index) internal { uint256 bucket = index >> 8;//右移8位，相当于除以256取整 uint256 mask = 1 << (index & 0xff); bitmap._data[bucket] |= mask; } 上面代码的index&0xff相当于index对256取模，计算出余数，然后用1左移对应的余数位，表示要在256位中的哪一位写上1，就表示true，然后对_data里对应槽位的数据做或运算，表示更新存储。除了第一次的bucket存储是写操作要消耗20000gas外，后面相同的bucket存储就是修改操作，消耗5000gas，显然比上面的那种方法节省gas。 例如：index=1000 index>>8=3，bucket=3 index&&0xff=232 1<<232，表示如下二进制整数再对bitmap._data[bucket]进行或运算，相当于将bitmap._data[bucket]值的第232位设置为1。 对应的get则相反，将bitmap._data[bucket]与mask做与运算，如果不为0，就表示这个位是1。function get(BitMap storage bitmap, uint256 index) internal view returns (bool) { uint256 bucket = index >> 8; uint256 mask = 1 << (index & 0xff); return bitmap._data[bucket] & mask != 0; } 位图结构对存储uint256=>bool的映射时可以节省gas cost，如果是address，可以uint256(uint160(addr))转为uint256后使用此结构。例如，记录某地址是否做过某事时就可以用Bitmaps。 ## Publication Information - [franx.eth](https://paragraph.com/@franx-2/): Publication homepage - [All Posts](https://paragraph.com/@franx-2/): More posts from this publication - [RSS Feed](https://api.paragraph.com/blogs/rss/@franx-2): Subscribe to updates