solidity | 默克尔树

参考资料

• 默克尔树 Merkle Tree

Merkle Tree

Merkle Tree，也叫默克尔树或哈希树，是区块链的底层加密技术，被比特币和以太坊区块链广泛采用。

Merkle Tree 是一种自下而上构建的加密树，每个叶子是对应数据的哈希，而每个非叶子为它的 2 个子节点的哈希。

Merkle Tree 允许对大型数据结构的内容进行有效和安全的验证（ Merkle Proof）。

对于有 N 个叶子结点的 Merkle Tree ，在已知 root 根值的情况下，验证某个数据是否有效（属于 Merkle Tree 叶子结点）只需要log(N)个数据（也叫 proof ），非常高效。如果数据有误，或者给的 proof 错误，则无法还原出 root 根植。 下面的例子中，叶子 L1 的 Merkle proof 为 Hash 0-1 和 Hash 1：知道这两个值，就能验证 L1 的值是不是在 Merkle Tree 的叶子中。

为什么呢？ 因为通过叶子 L1 我们就可以算出 Hash 0-0，我们又知道了 Hash 0-1，那么Hash 0-0和Hash 0-1就可以联合算出Hash 0，然后我们又知道Hash 1，Hash 0和Hash 1就可以联合算出Top Hash，也就是 root 节点的 hash。

生成Merkle Tree

我们可以利用 网页 或者 Javascript库 merkletreejs 来生成 Merkle Tree

使用

pragma solidity ^0.8.0;

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


contract WTFApe {

    function test(
        bytes32[] calldata proof,
        bytes32 root,
        bytes32 leaf
    ) public pure returns (bool){
        return MerkleProof.verifyCalldata(proof, root, leaf);
    }
}

我们的参数如下

[
"0x5B38Da6a701c568545dCfcB03FcB875f56beddC4", 
"0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2",
"0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db",
"0x78731D3Ca6b7E34aC0F824c42a7cC18A495cabaB"
]

执行参数如下

• proof
  • [ "0x999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb", "0x4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c" ]
• root
  • 0xeeefd63003e0e702cb41cd0043015a6e26ddb38073cc6ffeb0ba3e808ba8c097
• leaf
  • 0x5931b4ed56ace4c46b68524cb5bcbf4195f1bbaacbe5228fbd090546c88dd229