Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文
区块链与Git内部数据结构都以树形数据对象表示——即以默克尔树(Merkle Tree)作为底层数据结构。+ q( X  _4 {7 n! r# y
默克尔树这种现代数据结构是由计算机科学家Ralph Merkle(他也是公钥加密算法共同设计者)在1979年提出(作为对比,Knuth的TAOCP三卷第一版写完是1973年),并以他的名字命名。$ F! {2 x4 W/ C* Y5 |! Z
* P6 S3 [* E5 Q& Y
这种数据结构的特点是:2 H$ s: b8 q( |0 s
大多数为二叉树,也可以多叉树,无论是几叉树,它都具有树结构的所有特点& N9 h5 X9 P1 |* |# b/ R  a6 |
叶子节点value是数据集合的单元数据或者单元数据Hash
% r! D, }% V3 k) L非叶子节点的value是根据它下面所有的叶子节点值,然后按照Hash算法计算而得出
9 [- o1 O6 O+ c( B  @2 L* o1 i: M3 v8 l
近年来,除了Bitcoin、Ethereum、IPFS,一大批计算机工程突破,都得益于这种数据结构进行完整性校验,例如文件系统ZFS、Btrfs,另一种分布式版本控制系统Mercurial,NoSQL数据库Apache Cassandra、Riak、Dynamo等。BT下载,也是通过默克尔树进行完整性校验。2 h# D4 ^, U. o, M  M2 ^$ E
要实现完整性校验,最简单的方法是对整个数据文件做Hash运算,把得到的Hash值公布在网上,下载数据后,再次运算Hash值,如果运算结果相等,就表示没有任何的损坏。
% p, Y) s0 M: C+ g2 ^0 |& t假如从稳定的服务器上下载,那么采用单个Hash来进行校验的形式是可以接受的。但在点对点网络中作数据传输时,会从同时从多个机器上下载,且线路充斥着不稳定,这时需要有更加巧妙的做法。
8 D7 f) f3 i. T$ M$ K3 g6 p实际中,都是把比较大的一个文件,切成小块。如果有一个小块数据在传输过程中损坏,只要重新下载这一个数据块就行。当然这就要求每个数据块都拥有自己的Hash值。
$ B: ^: O. C" w+ \2 T以我们熟悉的BT下载为例,下载真正的数据之前,会先下载一个Hash列表的。这时有一个问题出现——那么多的Hash,怎么保证它们本身都是正确地呢?6 c$ d1 ]7 j$ Y- e) \
答案是需要一个“根Hash”。把每个小块的Hash值拼到一起,然后对整个这个长长的字符串再做一次Hash运算,最终的结果就是Hash列表的根Hash。于是,如果我们能够保证从一个绝对可信的网站,或者从我们的朋友手里拿到一个正确的根Hash,就可以用它来校验Hash列表中的每一个Hash都是正确的,进而可以保证下载的每一个数据块的正确性了。
: M9 H4 }' W! h  x: R/ _这种设想挺好,但实际应用中,还有不足,这就是为什么要发默克尔树。
/ g2 o8 ]% L% S# ^在最底层,与Hash列表一样,数据被分成小块,有相应的Hash和其对应。但是往上走,并不是直接去运算根Hash,而是把相邻的两个Hash合并成一个字符串,然后运算这个字符串的Hash,这样每两个Hash就结婚生子,得到了一个“子Hash”。
# X, ~1 j  t9 v$ K+ V如果最底层的Hash总数是单数,那到最后必然出现一个单身Hash,这种情况就直接对它进行Hash运算,所以也能得到它的子Hash。于是往上推,依然是一样的方式,可以得到数目更少的新一级Hash,最终必然形成一棵倒挂的树,到了树根的这个位置,这一代就剩下一个根Hash了,称为默克尔根。
7 u- r. M, D) n6 _4 m6 A! I相对于Hash List,Merkle Tree 的明显的一个好处是可以单独拿出一个分支来(作为一个小树)对部分数据进行校验,这个很多使用场合就带来了Hash列表所不能比拟的方便和高效。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

卡扎菲偶遇拉登 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    38