一种有意思的数据结构-默克树（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，第2次commit中内容是2，此时git本地库房中会别离有：内容为1的文件a，内容为2的文件a。

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

注：将工作区的文件改成本地库房的某个版别的文件是index区担任的，这儿就不细讲了。

常见使用 – 2 分布式数据存储的数据校验

咱们将成千上万个文件存在互联网上的恣意服务器，任何一个能上网的终端，都能够作为咱们的存储器，注：假定咱们为了确保功能，不通过中介服务器，直接p2p连接，并且不校验这些存储器的身份。那怎么确保咱们从这些不受信赖的存储器中下载的数据，是咱们存入时的姿态（没有被篡改）？

是否能够测验如下过程：

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

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

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

2.运用时判别这个文件内容是否有被这个默克树记载。

3.判别一切文件都被这个默克树记载。

结

能够看到默克树的底子在于hash的核算，是否真的能确保防篡改呢？，假如想进一步了解，能够看看密码学中有关于Collision resistance（抗碰撞性）和 Hiding（躲藏性）。 也能够看：BANote/1.密码学根底.md at master BAByte/BANote (github.com)