过于超前的Merkle Tree，诞生30多年后才在区块链上大放异彩
新开一个系列，5分钟讲一个Web3的基本概念。东西虽然基础，讲得透彻却也不容易。
Day2: Merkle Tree
Merkle Tree，一般翻译为默克尔树，后面简称MT，这个1979年由密码学家Ralph Merkle提出的数据结构，一直潜伏在历史的尘埃里。直到30多年后随着区块链的发展才跟着声名鹊起。
不过圈外人很少有听过这个概念，谁能想到这样一个本来不起眼的数据结构，却构筑了区块链的信任基石。今天咱就来好好聊一聊这个过于超前的Merkle Tree。
Hash函数
正式开讲MT之前，需要先了解一个概念：Hash函数。这个函数需要具备如下性质：
- 防碰撞 collision resistance。也就是很难能够找到两个不同的值x和y，使得H(x)=H(y)。
- 计算过程不可逆。这两个性质结合起来可以做信息摘要，用于验证数据是否被篡改。
- 生成的值足够随机。
目前比较常用的Hash算法是SHA256（Secure Hash Algorithm 256bits），结果包含256个二进制bit，这个数比全宇宙所有的原子数量总和都大。
MT原理
MT本质上是一棵 哈希二叉树 hash binary tree，如图所示，分别计算L1、L2的Hash值得到Hash 0-0和Hash 0-1，再计算（Hash 0-0+Hash 0-1）的Hash值得到Hash 0……层层递归，最终会计算得到Top Hash。
Top Hash就是整棵MT的摘要。
MT有什么用
1. 可以极大节约数据存储成本
如果仅仅是为了做数据验证，只需存一个Top Hash即可。这有点类似我们下载软件包时验证Hash值那样，只要软件包的任意bit被篡改，其计算出的Hash值都不会相同。
2. 防止数据被篡改
如上所述。
3. 做为区块链数据存储的共识
区块链的共识机制，除了记账权共识（上一期说过），还有数据存储共识。否则每一个分布式节点上的内容不一致就乱套了。
实际上在BTC区块链中，MT存储的是交易数据，MT的每个叶子节点都存储一个 交易 transaction 信息，根节点叫Merkle Root，作为整棵树的摘要信息放进Block Header中，再加上随机数nonce和一些其他字段，就构成了区块的存储结构。
每个Block Header又可以计算出一个Hash值做为该Block的摘要和唯一编号，注意到每个区块其实存储了上一个区块的编号（preBlockHash），就这样一个链接一个形成了区块链。
这个结构有个神奇之处，只需知道最后一个区块的Hash值就可以校验整个区块链的正确性。
4. Merkle Tree和挖矿的关系
上一期聊了挖矿的共识机制：PoW，说到挖矿就是在不断进行Mining Puzzle的计算。
提示
参考：发明PoW的人真是个天才
实际上Mining Puzzle就是计算区块的Hash值，直到算出的Hash值小于某个难度系数，可以通过调整随机数nonce来影响Hash值，换句话说挖矿其实是在进行一种暴力破解。
Merkle Root是被包含在Block Header中的，因此挖矿必须先进行“交易打包”算出Merkle Root。关于如何交易打包，后续专门找一期再聊。
Merkle Tree的变种
在BTC系统中，MT使用的是二叉树的形式，不过在ETH中，由于设计的理念不同，导致数据结构也不一样。
ETH用的是叫做Modified MPT（Modified Merkle-Patricia-Trie）的变种，后续说到ETH时咱们再详聊。