数据结构默克树 Merkle tree

一种有意思的数据结构-默克树（Merkle tree）

默克树（Merkle tree）又叫hash树。程序员可以说自己不知道默克树，但是不能保证自己一定没有用过，因为git存储我们每一个版本代码和提交记录关系的数据结构就是默克树。

其在区块链技术中起着十分重要的作用，本文会介绍这种数据结构，并举例两个常见的应用场景（可能不够严谨）。

长什么样子？

下图是一个简单的默克树，可以看到除最底层的数据外，其他节点都是左右两个子节点的hash值组成。（注：红线代表左右顺序）

Hash链表

链表的定义就是当前节点指向下一个节点，传统链表是使用地址作为指向，但是区块链中的链表和默克树一样，使用上一个节点的hash值作为指向，如图：

防篡改

这两种数据结构天生就具备防篡改的特性，我们看他们在区块链中的形态：

假设我们更改了左边虚框内那一批已经存在的交易数据，例如data1，那区块1的默克树root值就一定会改变，区块1的hash值也一定会变，这种变化会产生新的链，当发现这条新链在区块1后的所有区块值与各个节点原本记录的值不一致，就会认为有人修改了链上的旧数据。

而且我们使用的是hash值作为指向，只要大家手上的最后一个值没问题，在回溯时必然无法回溯到被篡改的数据，甚至回溯对比后还可以知道哪里发生了篡改。

既然无法指向我们篡改的数据，那我们把后面的所有区块以及其数据也篡改了行不行？可以的，但是区块有无数个，而且并不是简单的遍历修改本地数据就ok了，还需要所有节点的共识，你能黑光所有的节点，让他们都直接放弃手中的数据，认可你这新的链吗？

所以在对账时，就很容易知道账目是否正确，由于是直接比较hash值，使用默克树去判断内容是否被篡改是很快的！

我们看看默克树在分布式记账的应用中是如何大展身手的！！

判断某个交易是否被记录（是否存在）

你怎么保证你手中的数据和链上一致？怎么证明你的数据在链上呢？

例子：你在银行存了50万，银行怎么证明它给你存了50万呢？

1.我们首先要向信任节点获取蓝色框和黄色框的值。

2.这里假设我们判断data1数据，算出我们要判断的数据的记为A，A与B进行hash,得到C

3.将C与D进行hash，得到E

4.判断E是否等于 F，等于说明存在。

常见应用 - 1 git

我们切换commit时，git是怎么实现不同commit文件数量和文件内容的切换的？

git会记录所有版本的文件，例如文件a在第一个commit中内容是1，第二次commit中内容是2，此时git本地仓库中会分别有：内容为1的文件a，内容为2的文件a。

git中每一个commit就相当于一个区块，这个区块有对应的默克树，而默克树中的hash值又指向了对应的文件，所以切换一个commit其实就相当于将当前区块切换，如下图：

注：将工作区的文件改成本地仓库的某个版本的文件是index区负责的，这里就不细讲了。

常见应用 - 2 分布式数据存储的数据校验

我们将成千上万个文件存在互联网上的任意服务器，任何一个能上网的终端，都可以作为我们的存储器，注：假设我们为了保证性能，不通过中介服务器，直接p2p连接，并且不校验这些存储器的身份。那如何保证我们从这些不受信任的存储器中下载的数据，是我们存入时的样子（没有被篡改）？

是否可以尝试如下步骤：

0.这些任意的服务器都要拥有其存储文件的默克树。

1.终端下载这个服务器中存储的默克树，向值得信任的服务器取得这个默克树对应区块的值，计算并判断默克树顶部的hash值是否等于区块记录的值，等于说明这个服务器记录的默克树没有问题。

下面两步任选一个都能确认文件没被篡改。

2.使用时判断这个文件内容是否有被这个默克树记录。

3.判断所有文件都被这个默克树记录。

小结

可以看到默克树的根本在于hash的计算，是否真的能保证防篡改呢？，如果想进一步了解，可以看看密码学中有关于Collision resistance（抗碰撞性）和 Hiding（隐藏性）。

也可以看：密码学基础.md