#Solidity学习笔记-默克尔树 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。
我们可以利用网页或者Javascript库merkletreejs来生成Merkle Tree
。
操作流程:
1)生成Merkle Tree
2)Merkle Proof
验证
3)编写MerkleProof
库:有三个函数,verify()
函数——利用proof
数来验证leaf
是否属于根为root
的Merkle Tree
中,如果是,则返回true,
它调用了processProof()
函数;processProof()
函数——利用proof
和leaf
依次计算出Merkle Tree
的root
。它调用了_hashPair()
函数;_hashPair()
函数:用keccak256()
函数计算非根节点对应的两个子节点的哈希(排序后)。
4)编写MerkleTree
合约。
5)部署MerkleTree
合约。
6)验证测试。
总结:
在实际使用中,复杂的Merkle Tree
可以利用javascript
库merkletreejs
来生成和管理,链上只需要存储一个根值,非常节省gas
。很多项目方都选择利用Merkle Tree
来发放白名单。