加载中…
个人资料
区块链的作坊
区块链的作坊
  • 博客等级:
  • 博客积分:0
  • 博客访问:30,883
  • 关注人气:9
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Merkle树与二叉树

(2017-05-23 20:09:06)
标签:

merkle

二叉树

       在比特币等电子货币中,使用一种称为Merkle树的树形结构来记录所有的交易信息,这些交易信息相互关联,任何信息的改动都会被发现,从而有效防止信息篡改,同时采用这种树形结构,能够快速定位某一个信息。下面我们介绍其基本原理和作用。

1、简介

       默克尔树(Merkle tree,MT)是一种哈希二叉树,1979年由Ralph Merkle发明。在计算机科学中,二叉树是每个节点最多有两个子树的树结构,每个节点代表一条结构化数据。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现数据快速查询。二叉树如下图所示

二叉树 的图像结果

 

2、Merkle树结构

        由一个根节点(root)、一组中间节点和一组叶节点(leaf)组成。叶节点(leaf)包含存储数据或其哈希值,中间节点是它的两个孩子节点内容的哈希值,根节点也是由它的两个子节点内容的哈希值组成。所以Merkle树也称哈希树。

      哈希树的特点: 叶节点存储的是数据文件,而非叶节点存储的是其子节点的哈希值(Hash,通过SHA1、SHA256等哈希算法计算而来),这些非叶子节点的Hash被称作路径哈希值(可以据其确定某个叶节点到根节点的路径), 叶节点的Hash值是真实数据的Hash值。因为使用了树形结构, 其查询的时间复杂度为 O(logn),n是节点数量。

Merkle tree 的图像结果

       默克尔树的另一个特点是,底层数据的任何变动,都会传递到其父节点,一直到树根。

 

3、应用模式

       默克尔树的典型应用场景包括:

  • 快速比较大量数据:当两个默克尔树根相同时,则意味着所代表的数据必然相同(哈希算法决定的)。
  • 快速定位修改:例如上例中,如果 D1 中数据被修改,会影响到Hash0-0,Hash0 和 Root。因此,沿着 Root --> 0 --> 0-0,可以快速定位到发生改变的 D1;
  • 零知识证明:例如如何证明某个数据(D0……D3)中包括给定内容 D0,很简单,构造一个默克尔树,公布 N0,N1,N4,Root,D0 拥有者可以很容易检测 D0 存在,但不知道其它内容。

        相对于 Hash List,MT的明显的一个好处是可以单独拿出一个分支来(作为一个小树)对部分数据进行校验,这个很多使用场合就带来了哈希列表所不能比拟的方便和高效。正是源于这些优点,MT常用于分布式系统或分布式存储中。

4、在分布式存储系统中的应用原理

       为了保持数据一致,分布系统间数据需要同步,如果对机器上所有数据都进行比对的话,数据传输量就会很大,从而造成“网络拥挤”。为了解决这个问题,可以在每台机器上构造一棵Merkle Tree,这样,在两台机器间进行数据比对时,从Merkle Tree的根节点开始进行比对,如果根节点一样,则表示两个副本目前是一致的,不再需要任何处理;如果不一样,则沿着hash值不同的节点路径查询,很快就能定位到数据不一致的叶节点,只用把不一致的数据同步即可,这样大大节省了比对时间以及数据的传输量。

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有