Merkle

最简单的实现：单向递增的完全二叉树

众所周知，完全二叉树可以由一个二进制串存储

典型的一个应用场景是以太坊的 Deposit 合约。

添加节点

假设最开始只有一个节点

添加下一个节点

添加更多节点....

继续添加，n个叶子节点

验证节点

正常情况下，对于 $n$ 个 validator，我们要进行 $O(n)$ 次的运算，但是通过 Merkle Tree，我们只需要验证 $O(\log n)$ 次。

例如，在 $n$ 个节点中要验证第 $i$ 个节点，我们需要验证的路径如下：

增量完全二叉树的数据结构

在合约实现中，为了高效处理动态增加的叶子节点，通常使用增量 Merkle 树 (Incremental Merkle Tree)。

核心状态变量

• branch[32]: 数组存储了每一层当前最右侧子树的哈希值。
• deposit_count: 当前已插入的叶子节点总数。
• tree_depth: 树的最大高度（以太坊 Deposit 合约固定为 32，既总共可以支持 $2^{32}$ 个 Validator，约 42亿个）。

节点存储逻辑

当新插入第 $i$ 个节点时，我们不需要重新计算整棵树。利用 branch 数组，只需要将新哈希与 branch 中受影响的层级进行合并更新。由于是完全二叉树，第 $h$ 层的节点只有在满足特定的频率（$2^h$）时才会被更新。

叶子数为 $4$ -> 100

叶子数为 $5$ -> 101

叶子数为 $6$ -> 110

查询：叶子为 $7$ -> 111，查询 $i=6$

Solidity

• 插入

// SPDX-License-Identifier: MIT
pragma solidity 0.6.11;

contract DepositContract {
    uint constant TREE_DEPTH = 32;
    bytes32[TREE_DEPTH] branch;
    uint256 deposit_count;
    bytes32[TREE_DEPTH] zero_hashes;

    construcor() public{
        // ....
    }

    function deposit(bytes32 node) public payable {
        // ... 校验逻辑 ...
        
        deposit_count += 1;
        uint size = deposit_count;
        for (uint height = 0; height < TREE_DEPTH; height++) {
            // 如果当前位是 1，说明找到了当前高度的空位（左侧已填满）
            if ((size & 1) == 1) {
                branch[height] = node;
                return; // 插入完成，直接返回
            }
            // 否则，将当前节点与之前存储在 branch 中的左侧节点合并，继续向上传递
            node = sha256(abi.encodePacked(branch[height], node));
            size /= 2;
        }
        assert(false); 
    }

    /**
     * @dev 获取根哈希。
     */
    function get_deposit_root() public view returns (bytes32) {
        bytes32 node;
        uint size = deposit_count;
        for (uint height = 0; height < TREE_DEPTH; height++) {
            if ((size & 1) == 1)
                node = sha256(abi.encodePacked(branch[height], node));
            else
                node = sha256(abi.encodePacked(node, zero_hashes[height]));
            size /= 2;
        }
        // Root 包含了对 deposit_count 的混淆，增强安全性
        return sha256(abi.encodePacked(node, to_little_endian_64(uint64(deposit_count)), bytes24(0)));
    }
}

• 在 n 个叶子节点中 查询第 i 个

/**
 * @dev 验证 Merkle Proof
 * @param leaf 目标叶子节点哈希
 * @param proof 对应的兄弟节点哈希数组 (Path)
 * @param index 节点的索引 (0 到 2^32 - 1)
 * @param root 当前合约记录的树根
 */
function verify(
    bytes32 leaf,
    bytes32[] calldata proof,
    uint256 index,
    bytes32 root
) public pure returns (bool) {
    bytes32 computedHash = leaf;

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

        if (index % 2 == 0) {
            // index 是左孩子，proofElement 是右兄弟
            computedHash = sha256(abi.encodePacked(computedHash, proofElement));
        } else {
            // index 是右孩子，proofElement 是左兄弟
            computedHash = sha256(abi.encodePacked(proofElement, computedHash));
        }

        index = index / 2;
    }

    return computedHash == root;
}