Merkle树
什么是 Merkle 树?
Merkle 数是一种特殊的hash 树，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值, 非叶节点是其对应子节点串联字符串的hash.
在比特币里, 矿工把区块内所有交易（约1-2千笔）的哈希值一字排开，让他们两两牵手，每对交易哈希牵手后再算出新哈希。矿工验证、记录和整理交易的过程称为“打包”。 下面这棵树的顶点, 就是默克尔树根(Merkle Root)
Merkle 树解决什么问题?
Bitcoin发展到今天, 全节点的区块至少已经几百G, 让每个节点下载全部的区块并不是一个好主意. 因此有人提出了一个SPV的方案.
SPV= Simple Pay Verification. 是一种即使没有完整交易记录，也能便捷、安全地验证支付的方法。 不用下载全部区块（几百G），只需下载全部区块头（约40M），就能轻松验证所有支付.
Merkle的数据结构, 允许SPV节点能够方便的验证交易.
如何解决这个问题的?
SPV有两个前提:
- 每笔交易都有标准格式：输出地址、输入地址和交易金额等，所以交易一旦发生，该交易哈希值瞬间产生（假设为HK，图3绿框）。
- 如果交易被矿工打包过，拥有全部交易数据的节点（称为“全节点”：full node）必然有整棵默克尔树。
如果想要验证这个某笔交易是否存在, 验证步骤为:
- 用户A的钱包把某笔交易(假设为$H_k$), 提交给附近的全节点
- 全节点反馈A下载下图4个蓝块的哈希值。
- 第三步：A的钱包经过4步哈希计算：
- Hash($H_k$,$H_l$)
- Hash($H_ij$, $H_kl$)
- Hash($H_ijkl$,$H_mnop$)
- Hash($H_abcdefghijklmop$) 即：沿上图的虚线框路径，用户A的钱包最终得出哈希值$H_abcdefghijklmop$
- A钱包将
$H_abcdefghijklmop$与钱包里已经下载好的默克尔树根对比，若一致就能确认这笔交易存在
使用了以上方案后, 即使一个区块中交易再多，十来下就能搞定验证，假设区块里有2048个交易, 最多也只需要$lg(2048)=11$次
Merkle 树有什么缺点?
Merkle树是用空间换时间, 带来的代价是全节点需要存储更多的东西, 来记录Merkle的中间节点.
在Bitcoin的Merkle树比较简单, 只能做简单的验证功能. 以太坊扩展了Bitcoin的Merkle树, 允许做更多的功能. 譬如:
- 这笔交易被包含在特定的区块中了么？
- 告诉我这个地址在过去30天中，发出X类型事件的所有实例（例如，一个众筹合约完成了它的目标）
- 目前我的账户余额是多少？
- 这个账户是否存在？
- 假如在这个合约中运行这笔交易，它的输出会是什么？
