go-filecoin中的MerkleTree

发布时间:2020-02-07 14:57 浏览次数:次 作者:星际联盟 来源:http://www.ipfs-filecoin.cn

MerkleTree是这样的一种二叉或多叉树,其数据被保存在各叶子节点中,其它节点则保存子节点们的Hash值,整树由下往上,依次对子节点取Hash并存入到父节点中,最后就能使用Root节点中的Hash代表整棵树的数据。
MerkleTree在区块链等分布式系统中有着广泛应用。

MerkleTree

 

因为在MerkleTree中,每个父节点中保存的数据是对其所有子节点进行Hash运算得到的结果,而Root节点则相当于保存了整棵树的Hash值。所以如果树中任意一个节点的数据发生变化,必然会向上传递导致Root节点的数据发生变化。多数区块链都可以理解为一个透明的分布式账本,上面的数据只要产生,则不能发生改变,MerkleTree的特性正适合用于在区块链中验证区块中数据是否发生了改变,维护区块链的不可篡改性。

在分布式系统中的不同节点,可各自构建一个MerkleTree来保存自身的数据,通过与其它节点的MerkleTree进行比对,就能快速定位到数据不一致的节点,只需修改这些节点就可以以较小的代价维护系统内的数据一致性。

详说MerkleTree的特性

 

正如上一节所说,任意一个叶子节点的细微变动,都会导致根节点随之改变,可以用来判断保存的数据是否被篡改。

  • 只是可以检测数据是否发生了变动,我们有很多其它的方法。最简单的比如,直接对数据进行Hash运算,把得到的值与之前计算的值进行比较,不一样就说明数据必然被修改。但这样就会导致算法效率低下,因为这样会产生O(n)的复杂度,即保存的数据越多,要运行的Hash次数也越多。
    而在MerkleTree中,如果节点D1中数据被修改,父节点P1的值就会发生变化,P1的父结点G1也会改变,最后Root结点变动,沿着D0 - > N0 - > N4->Root这条路径即可快速定位到实际发生改变的数据块D9,算法复杂度为O(logn),效率会高很多。

    • 零知识证明指证明者能够在不向验证者提供任何有用的信息的情况下,使验证者相信某个论断是正确的。比如上图中若要证明某个数据(D0……D3)中包括给定内容 D0,构造一个MerkleTree,公布 N0,N1,N4,Root,D0拥有者就可以很容易检测 D0 的存在,但不需要知道其它内容。

      go-filecoin中区块是保存在MerkleDAG中,将MerkleDAG抽象为一种接口,定义如下

      DAGService

      DAGService提供了获取、添加、删除节点的功能。

       

      下图显示了一个保存区块的DAG:

      保存区块的DAG

上一篇:区块链——通往机器智能世界的钥匙!

下一篇:星际联盟受邀出席2019CAN 万物互链

相关推荐
渠道商首页渠道合作 微信客服1 微信客服2
X

截屏,微信识别二维码

微信号:463026449

(点击微信号复制,添加好友)

打开微信

微信号已复制,请打开微信添加咨询详情!
X

截屏,微信识别二维码

微信号:clj830911

(点击微信号复制,添加好友)

打开微信