您现在的位置是:网站首页> 编程资料编程资料
有意思的数据结构默克树 Merkle tree应用介绍_其它综合_
2023-05-27 143人已围观
简介 有意思的数据结构默克树 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
以上就是有意思的数据结构默克树 Merkle tree应用介绍的详细内容,更多关于数据结构默克树 Merkle tree的资料请关注其它相关文章!
点击排行
- TYSB手游公测版下载-TYSB官方唯一正版手游下载 _安卓网
- 青云传之琉璃梦手游下载-青云传之琉璃梦官方版下载 v5.7.0安卓版_安卓网
- 爆枪突击专用修改器下载-爆枪突击无限兑换码 v1.0.0.3辅助修改_安卓网
- 丛林动物宝宝发型沙龙游戏-丛林动物宝宝发型沙龙(休闲装扮)Baby Jungle Animal Hair Salon v1.0.10_安卓网
- 洗牌猫下载-洗牌猫(卡牌对战)Shuffle Cats v0.14.8_安卓网
- 终极奥特超人50周年版下载-终极奥特超人50周年版(奥特曼正版授权) v2.3_安卓网
- project h手机|project h安卓-project h手机版(虚拟空间女友)预约 v1.0_安卓网
- project h试玩版-project h手游试玩版预约 v1.0_安卓网