区块链中的Markle树与二叉树

在比特币等虚拟货币中，通常使用Merkle树的树形结构来记录所有的交易信息，这些交易信息相互关联，任何信息的改动都会被发现。所谓Markle树，说的直白一点就是哈希值按一定规则组成的一颗树，不同于hash list的是，Markle树更方便校验而且是区域性校验。

1、简介

默克尔树（Merkle tree，MT）是一种哈希二叉树，1979年由Ralph Merkle发明。在计算机科学中，二叉树是每个节点最多有两个子树的树结构，每个节点代表一条结构化数据。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现数据快速查询。二叉树如下图所示

2、Merkle树结构

由一个根节点（root）、一组中间节点和一组叶节点（leaf）组成。叶节点（leaf）包含存储数据或其哈希值，中间节点是它的两个孩子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。所以Merkle树也称哈希树。

哈希树的特点: 叶节点存储的是数据文件，而非叶节点存储的是其子节点的哈希值（Hash，通过SHA1、SHA256等哈希算法计算而来），这些非叶子节点的Hash被称作路径哈希值（可以据其确定某个叶节点到根节点的路径）, 叶节点的Hash值是真实数据的Hash值。因为使用了树形结构, 其查询的时间复杂度为 O(logn)，n是节点数量。

默克尔树的另一个特点是，底层数据的任何变动，都会传递到其父节点，一直到树根。

3、应用模式

默克尔树的典型应用场景包括：

快速比较大量数据：当两个默克尔树根相同时，则意味着所代表的数据必然相同（哈希算法决定的）。

快速定位修改：例如上例中，如果 D1 中数据被修改，会影响到Hash0-0，Hash0 和 Root。因此，沿着 Root --> 0 --> 0-0，可以快速定位到发生改变的 D1；

零知识证明：例如如何证明某个数据（D0……D3）中包括给定内容 D0，很简单，构造一个默克尔树，公布 N0，N1，N4，Root，D0 拥有者可以很容易检测 D0 存在，但不知道其它内容。

4、Merkle树优势

默克尔树（Merkle Tree）算法的最大好处就是，每个交易都可以单独直接删除，只保留这个交易的Hash值即可。这样，对整个区块来说，并没有改变其密码学安全性和完整性，但数据量可以大大减小。（Hash值32个字节，而一笔交易一般要400多个字节）。如果一个区块中只有一个交易没有后续交易，那么删除其他所有交易，整个区块的数据量会大大减小。因此，在UTXO的记账模式中，使用默克尔树结构，通常就无需担心数据量一直增长导致数据过大的问题了。

同时，相对于 Hash List，默克尔树的明显优势是可以单独拿出一个分支来（作为一个小树）对部分数据进行校验，应用在许多场合就带来了哈希列表所不能比拟的方便和高效。正是源于这些优点，默克尔树也常用于分布式系统或分布式存储中。

5、在分布式存储系统中的应用原理

为了保持数据一致，分布系统间数据需要同步，如果对机器上所有数据都进行比对的话，数据传输量就会很大，从而造成“网络拥挤”。为了解决这个问题，可以在每台机器上构造一棵Merkle Tree，这样，在两台机器间进行数据比对时，从Merkle Tree的根节点开始进行比对，如果根节点一样，则表示两个副本目前是一致的，不再需要任何处理；如果不一样，则沿着hash值不同的节点路径查询，很快就能定位到数据不一致的叶节点，只用把不一致的数据同步即可，这样大大节省了比对时间以及数据的传输量。