isoulove@isoulove·Apr 01

#Solidity学习笔记-默克尔树 Merkle Tree

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

Merkle Tree允许对大型数据结构的内容进行有效和安全的验证(Merkle Proof)。对于有N个叶子结点的Merkle Tree,在已知root根值的情况下,验证某个数据是否有效(属于Merkle Tree叶子结点)只需要log(N)个数据(也叫proof),非常高效。如果数据有误,或者给的proof错误,则无法还原出root根植。下面的例子中,叶子L1Merkle proofHash 0-1Hash 1:知道这两个值,就能验证L1的值是不是在Merkle Tree的叶子中。为什么呢? 因为通过叶子L1我们就可以算出Hash 0-0,我们又知道了Hash 0-1,那么Hash 0-0Hash 0-1就可以联合算出Hash 0,然后我们又知道Hash 1Hash 0Hash 1就可以联合算出Top Hash,也就是root节点的hash。

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

操作流程:
1)生成Merkle Tree
2)Merkle Proof验证
3)编写MerkleProof库:有三个函数,verify()函数——利用proof数来验证leaf是否属于根为rootMerkle Tree中,如果是,则返回true,它调用了processProof()函数;processProof()函数——利用proofleaf依次计算出Merkle Treeroot。它调用了_hashPair()函数;_hashPair()函数:用keccak256()函数计算非根节点对应的两个子节点的哈希(排序后)。
4)编写MerkleTree合约。
5)部署MerkleTree合约。
6)验证测试。

总结:
在实际使用中,复杂的Merkle Tree可以利用javascriptmerkletreejs来生成和管理,链上只需要存储一个根值,非常节省gas。很多项目方都选择利用Merkle Tree来发放白名单。

Post by @isoulove.lens