Merkle树的逻辑和证明

什么是Merkle树

定义

Merkle Tree，也叫默克尔树或哈希树，是区块链的底层加密技术，被比特币和以太坊区块链广泛采用。Merkle Tree是一种自下而上构建的加密树，每个叶子是对应数据的哈希，而每个非叶子为它的2个子节点的哈希。

如何生成Merkle树的数据

在solidity中我们通过keccak256算法计算hash值:

keccak256(abi.encodePacked(toHashValue)

e.g.:
hash前
0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2

hash后
0x999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb

在对叶子节点的值进行hash运算之后，再把相邻的节点再进行hash运算，直到只剩下一个根节点。
假设存在两个相邻的节点A和B,那么在进行hash运算的时候到地址是hash(A+B)呢？还是hash(B+A)呢？其实这是由A和B的大小决定的，在openzeppelin对应的merkle代码中我们可以找到这么一段代码:

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

总结来说就是把相对小的数值放到前面去这么来排序计算hash值。这个地方在自己动手实际运算的时候可能会有些许困惑。
在实际的项目中一般只需要把计算的最后结果的根hash值存储到合约中，如果大量的地址都需要存到合约中的话会消耗大量的gas费。经过merkle树计算之后，大大的减少了需要存储的数据。
通过一段foundry的setUp演示下如何计算和存储root hash值:

bytes32 public root;
bytes32[] public leafs;
bytes32[] public l2;

function setUp() public {
    address[] memory addrss = new address[](4);
    addrss[0] = 0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2;
    addrss[1] = 0x2d886570A0dA04885bfD6eb48eD8b8ff01A0eb7e;
    addrss[2] = 0xed857ac80A9cc7ca07a1C213e79683A1883df07B;
    addrss[3] = 0x690B9A9E9aa1C9dB991C7721a92d351Db4FaC990;

    //通过地址列表计算叶子节点的hash值
    leafs.push(keccak256(abi.encodePacked(addrss[0])));
    leafs.push(keccak256(abi.encodePacked(addrss[1])));
    leafs.push(keccak256(abi.encodePacked(addrss[2])));
    leafs.push(keccak256(abi.encodePacked(addrss[3])));

    //计算第二层的hash值
    l2.push(keccak256(abi.encodePacked(leafs[0], leafs[1])));
    l2.push(keccak256(abi.encodePacked(leafs[2], leafs[3])));

    //计算根的hash值
    root = keccak256(abi.encodePacked(l2[1], l2[0]));
}

为了演示方便我们值写了4个地址，实际项目中可能地址数量非常大。

如何来验证Merkle树

在合约中存储到root hash值之后我们如何去验证由客户端发过来的地址是否是有效地址或者说在白名单中的地址呢？
首先我们需要将地址进行hash运算，作为第三个参数，然后将地址相邻的hash值作为proof传到验证函数中。
proof列表对应下面图片中的红色标记区域

测试的验证方法:

function testVerify() public {
    address proofAddress = 0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2;

    bytes32[] memory proof = new bytes32[](2);
    proof[0] = leafs[1];
    proof[1] = l2[1];

    assert(
        MerkleProof.verify(
            proof,
            root,
            keccak256(abi.encodePacked(proofAddress))
        )
    );
}

完整的foundry测试代码:https://gist.github.com/coffiasd/96022abd7f9a8a2189bda14bf9e755dc

在实际项目中的应用场景

• 发放空投
• NFT的白名单

在合约审计中的常见漏洞

function parentHash(bytes32 a, bytes32 b) public pure returns (bytes32) {
        if (a < b) {
            return keccak256(abi.encode(a, b));
        } else {
            return keccak256(abi.encode(b, a));
        }
    }

abi.encode(address, uint)将会输出64字节。由于abi.encode(bytes32, bytes32)也是64字节，因此在叶子节点和父节点之间可能会发生哈希碰撞。

Follow我的推进行交流学习:https://twitter.com/coffiasse
TG:@coffiasd