关于默克尔树应用的研究论文

Merkle 树是一种组织和构造大量数据以使其更易于处理的方法。在加密货币和区块链的情况下，Merkle 树用于以对资源要求较低的方式构建交易数据。 当在 Merkle 树结构中进行加密货币交易时，它会被散列，然后被赋予一个等效的散列值。每笔交易在 Merkle 树中散列后，产生的散列值与另一个散列值配对，然后再次散列。例如，将散列值“AB”和“AC”组合起来创建“ABC”。 重复这个配对散列值的过程，直到产生最终的散列值。最终的哈希值，即默克尔根，提供了它包含的所有交易的摘要。然后将 Merkle 根摘要插入到块头中。 Merkle 树结构提供了一个区块中交易的易于访问的记录。因此，检查块中的数据是否已更改或篡改非常简单。这是真的，因为对 Merkle 树中的交易（或任何其他相关数据）的任何更改都会导致完全不同的对应 Merkle 根。 如果加密货币不使用 Merkle 树，则每个验证请求都将涉及通过网络发送的大量信息。在 Merkle 树中构建交易数据是一种更有效的资源利用。验证交易不需要账本的完整副本，因为可以在 Merkle 根中验证散列的交易数据，需要在节点间发送的信息少得多，因此分析整体数据完整性的计算能力也更少。 换句话说，Merkle 树结构使用户能够验证单个交易是否已包含在一个区块中，而无需经过下载整个区块链的过程。该技术是加密货币组织交易数据并像它们一样高效运行的重要工具。如果没有默克尔树，对资源的更大需求很可能会导致参与网络的节点更少。

merkle tree一种二叉树也是区块链中一种常见的数据结构，其特性就是树的根及中间节点主要是由其左右子树的Hash构成。Parent = H(0,1)，其以密码学保证其安全性，以相同顺序插入才能计算出最终一致的树根。 而mmr(Merkle Mountain Range)是Peter Todd提出的一种Merkle tree，长相类似一组连续的山峰组成，其被设计为节点插入后就不能被修改，支持动态插入。 对于普通Merkle树对于每个新加入节点都需要重新计算merkle root,如果节点数量很大的话这个计算量会非常巨大，而mmr支持动态加入新节点并计算root。由上图可以发现，以存储索引位置作为其坐标的二叉树，都有左子树与父节点的距离(offset)为 offset=2^Height ,兄弟节点之间的距离为 offset=2^Height - 1 ,这样就可以计算出任意节点的兄弟节点与父节点的坐标。 另外如果我们能够计算出任意节点的高度，我们就能计算出任意节点的父节点及兄弟节点的坐标了，将节点坐标从 1 开始并以 二进制 来表示。如图：现在我们可以顺序追加节点了，我们只需要判断下一个节点的高度，如果大于当前高度则需要合并左右子树，方法如下: 由图2可以知道，MMR可能会有多个 山峰 ，而MMR的root是由最右侧的山峰依次向左合并，直到最后形成root,这个操作也被称为山峰的 拱起 操作。图2中的 root=Hash(Hash(18,17),14) 。 MMR的root是由山峰的 拱起 得到,那么最左侧的山峰一定一个完全的二叉树,节点数量为 2^Height - 1 ，由此我们可以在固定节点数量下(Count)不断尝试左侧山峰的高度,找到 2^Height - 1 < Count 的最大的树，如下: 在计算出左侧山峰后，可以以此为坐标，依次计算出右侧的所有山峰，如下: 获取到所有山峰后，就可以对所有山峰，由左到右依次 拱起 ，最后得到MMR的root。如下: 构造叶子节点的 merkle proof，分三个步骤： 如下: proof的验证，以相同的顺序重新计算Merkle Root就可以，如下: MMR可以极大的减少merkle证明的数据量，可以大幅度的减轻存储和网络的负担，提升验证效率，目前Open timestamp 和 Grin 等项目及Fly client的论文中都使用了MMR的证明。