Merkle树
在分布式系统、P2P应用中或者是区块链中,会经常使用一种数据结构Merkle tree(默克尔树),这里我们将详细讨论一下这个常用数据结构。
Merkle tree
Merkle树看起来非常像二叉树,其叶子节点上的值通常为数据块的哈希值,而非叶子节点上的值,所以有时候Merkle tree也表示为Hash tree,如下图所示:
在构造Merkle树时,首先要对数据块计算哈希值,通常,选用SHA-256等哈希算法。但如果仅仅防止数据不是蓄意的损坏或篡改,可以改用一些安全性低但效率高的校验和算法,如CRC。然后将数据块计算的哈希值两两配对(如果是奇数个数,最后一个自己与自己配对),计算上一层哈希,再重复这个步骤,一直到计算出根哈希值。
Merkle树大多用来进行完整性验证,比如分布式环境下,从多台主机获取数据,怎么验证获取的数据是否正确呢,只要验证Merkle树根哈希一致,即可。例如,下图中L3数据块发生错误(比如数据被修改了),错误会传导到计算hash(L3)
,接着传导到计算hash(Hash1-0+Hash1-1)
,最后传导到根哈希,导致根哈希的不一致,可以说,任何底层数据块的变化,最终都会传导到根哈希。另外如果根哈希不一致,也可以通过Merkle树快速定位到导致不一致的数据。
Merkle树还可以用来对数据进行快速比对,快速定位到不一致的数据。比如分布式存储中,一份数据会有多个副本,并且分布在不同的机器上。为了保持数据一致性,需要进行副本同步,而首要的就是比对当前副本是否一致,如一致,则无需同步,如不一致,还需找出不一致的地方,然后进行同步。很明显,如果采用直接传输数据进行比对,非常低效,一般采用对数据进行哈希,传输哈希值进行对比的方法。为此,可以对每台机器需要比对的数据构造Merkle树,如果根哈希一致,则数据相同,如果根哈希不一致,则通过Merkle树快速检索到不一致的数据。下面举例说明快速检索的过程,如上图蓝色标注所示。假设两台机器中L3数据块不一致,我们对比根哈希,发现根哈希不一致,即,数据不一致,此时需要找出是那一块不一致,分别对比Hash0
和Hash1
,发现是Hash1
不一致,接着向下发现是Hash1-0
不一致,这样就定位到是L3数据块不一致。定位过程的算法复杂度为O(log(n))
。
还有一种数据结构,在一定程度上可以看做是Merkle树的子树,但又不完全一样,这个数据结构是Hash list(为了避免中文哈希列表与哈希表的误解,这里使用英文名称),我们下面看一下这个Hash list。
Hash list
在点对点网络中数据传输的时候,为了提高效率往往会同时从多个机器下载数据的不同部分,即,不是从一台机器下载整个数据,而是将完整数据分成不同的部分,分别同时从不同的机器获取完整数据的不同组成部分。这样分块传输不但可以同时从多台机器下载数据,另一个好处是如果这一小块数据传输过程中损坏了,只要重新下载这一小数据块就可以了,不用重新下载整个数据。
但这种分布式环境下,很多机器应该认为是不稳定或者不可信的,如何校验整个数据的完整性及每一小数据块的完整性呢?
为了校验每一个数据块,我们需要对每个数据块做哈希,形成一个哈希列表,这样进行下载前,我们先要获取一个哈希列表,下载后,我们就能够通过哈希列表,来验证每一个数据块。哪怎么保证这个哈希列表是正确的呢,或者说怎么校验完整数据呢?只要每一个数据块哈希是正确的,最终获取的完整数据就一定是正确的,所以,我们需要对哈希列表进行哈希得到根哈希,将此根哈希放到一个可信源中,在下载数据前,先从可信数据源哪里获取到数据的跟哈希,然后从任意机器获取哈希列表,再下载数据块。这样,数据完整性可以通过根哈希来保证。
Merkle tree 对比 Hash list
两种数据结构都有验证数据完整性的功能,都可以通过根哈希保证整体数据完整性。所不同的是,在数据庞大,数据块非常多的情况下,当根哈希检测到数据不一致时,Merkle tree可以快速的定位到导致不一致的数据块,复杂度为O(log(n))
,而Hash list只能遍历庞大的哈希列表定位到导致不一致的数据块,复杂度为O(n)
,很显然,此时Merkle tree的效率要高很多。
参考文档:Hash list
关注微信公众号,与我一起学习分布式、数据结构、区块链!
最新文章
- hello,world!
- delphi locate多字段查询
- (转)oracle中用户删除不了,ORA-01940提示 “无法删除当前已连接用户”
- swift学习笔记之-属性
- 如何启动一个已经创建的docker 容器,并进入SHELL 对其操作
- CSS - 如何实现强制不换行、自动换行、强制换行 以及 chrom默认焦点 IE下 Input 默认出现叉
- MVC3/4 自定义HtmlHelper截断文本内容(截取)
- datatables配置及数据传输
- IE8 placeholder兼容+Password兼容
- Android Studio 2.1.x 关联SDK API Source
- and then set HOMEBREW_GITHUB_API_TOKEN.
- android studio的lib和jniLibs
- spring init
- 全方位解读";CPU load average";
- phpstorm php $post数据为空的原因
- flask教程
- MySQL之数据导入导出
- Golang入门教程(十三)延迟函数defer详解
- 【Java基本功】聊聊抽象类和接口的区别
- yasm开源汇编器分析
热门文章
- OAuth 2.0 的四种方式
- 使用多个tomcat如何修改端口号
- coercing to Unicode: need string or buffer, geoprocessing value object found
- Python自学笔记(九)
- [Java]两个将秒数转化为日时分秒形式的函数
- Locust - A modern load testing framework https://locust.io/
- OpenGL ES: (3) EGL、EGL绘图的基本步骤、EGLSurface、ANativeWindow
- ElementUI】日期选择器时间选择范围限制,只能选今天之前的时间,或者是只能选今天之后的时间。今天是否可以选。限制结束日期不能大于开始日期
- 28 Flutter 轮播图 flutter_swiper
- win10下安装Kafka