Merkle Tree
本文还是对《区块链：原理、设计与应用》的一个基础技术的总结和摘录。
默克尔树的特点
默克尔树是多层散列表（Hash List），目的是做多层摘要，把对多个 item 的校验，转化为对一个 item 的校验。
默克尔树可以是二叉树，也可以是多叉树。
叶子节点是 item 的 value 和 value 的散列值。中间每一层的值，都是它们子女散列值的和的散列值-多叉树的结果就是多个散列值加法的结果的再散列，孤儿的计算结果就是在孤儿散列值上进行再散列。
默克尔树的用途
快速比较大量数据
两组数据的排序后构建默克尔树，只要比较两个树的root 就可以确定两组数据是否一样。
快速 diff
如果默克尔树是二叉树，则只要从 root 开始做二分的 diff，就能快速定位到不一致的叶子节点。这在 p2p 传输文件数据的场景里非常有用。实际上 rsync 的 diff 算法就是一个一层的 Hash List ，
零（部分知识）知识证明
所谓的零知识证明，就是不告诉 verifier 验证一个论断真伪的全部信息。只提供部分信息，就可以让 verifier 相信某个事情是真的。
在默克尔树中，我们可以剪去部分枝节，只向 verifier 提供某一个叶子节点通往 root 所需要的 node，然后 verifier 就能断定一个特定的叶子 node 是否在此默克尔树中。也就是说，verifier 要求公允的验算可以让它自己来，我们只提供部分信息。在我看来，这不能算是零知识证明，只能算是部分知识证明。
默克尔树在比特币中的用途
在比特币中，每个区块里都存有所有交易的完整信息。这些完整信息又可以组成默克尔树的叶子节点，进而组成默克尔树。而每个区块中80bytes的区块头中，都含有五个数据：
- 上一个区块的散列值
- 时间戳
- 挖矿难度值
- 工作量证明随机数(nounce)
- 包含该区块交易的默克尔树的 root
轻节点可以只下载这个头，就能做到 SPV（Simplified Payment Verification）。具体过程如下：
验证某个交易是否真实存在时，理论上，用户可以通过以下方式进行验证：
- 从网络上获取并保存最长链的所有block header至本地；
- 计算该交易的hash值tx_hash；
- 定位到包含该tx_hash所在的区块，验证block header是否包含在已知的最长链中；
- 从区块中获取构建merkle tree所需的hash值；
- 根据这些hash值计算merkle_root_hash；
- 若计算结果与block header中的merkle_root_hash相等，则交易真实存在。
- 根据该block header所处的位置，确定该交易已经得到多少个确认。
优点：极大地节省存储空间。减轻终端用户的负担。无论未来的交易量有多大，block header的大小始终不变，只有80字节。按照每小时6个的出块速度，每年产出52560个区块。当只保存block header时，每年新增的存储需求约为4兆字节，100年后累计的存储需求仅为400兆，即使用户使用的是最低端的设备，正常情况下也完全能够负载。
默克尔树在以太坊中的应用
以太坊中实际上有三种默克尔树：
- transaction tree
- reciept tree
- state tree
这三种 tree 可以构建一个很强大的客户，允许轻客户端轻松地进行并核实以下类型的查询答案：
- 这笔交易被包含在特定的区块中了么？
- 告诉我这个地址在过去30天中，发出X类型事件的所有实例（例如，一个众筹合约完成了它的目标）
- 目前我的账户余额是多少？
- 这个账户是否存在？
- 假如在这个合约中运行这笔交易，它的输出会是什么？
第一种是由交易树（transaction tree）来处理的；第三和第四种则是由状态树（state tree）负责处理，第二种则由收据树（receipt tree）处理。计算前四个查询任务是相当简单的。服务器简单地找到对象，获取Merkle分支，并通过分支来回复轻客户端。
第五种查询任务同样也是由状态树处理，但它的计算方式会比较复杂。这里，我们需要构建一个Merkle状态转变证明（Merkle state transition proof）。从本质上来讲，这样的证明也就是在说“如果你在根S的状态树上运行交易T，其结果状态树将是根为S’，log为L，输出为O” （“输出”作为存在于以太坊的一种概念，因为每一笔交易都是一个函数调用；它在理论上并不是必要的）。
