一种有意思的数据结构-默克树(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)