大发快3_快3和值_大发快3和值 - 大发快3,快3和值,大发快3和值精选头条好文,分享实用生活小技巧,达人购物经验,包括科技、手机、数码、娱乐、美容、母婴、旅行、居家等内容,打造优质阅读体验。

[区块链] 密码学——Merkle 树

  • 时间:
  • 浏览:0

  在计算机领域,Merkle树大多用来进行完整版性验证解决。在解决完整版性验证的应用场景中,怪怪的是在分布式环境下进行我应该 的验证时,Merkle树会大大减少数据的传输量以及计算的多样化度。

  Merkle哈希树是一类基于哈希值的二叉树或多叉树,其叶子节点上的值通常为数据块的哈希值,而非叶子节点上的值是将该节点的所有子节点的组合结果的哈希值。

  如下图所示为一另另4个Merkle哈希树,节点A的值须要通过节点C、D上的值计算而得到。叶子节点C、D分别存储数据块001和002的哈希值,而非叶子节点A存储的是其子节点C、D的组合的哈希值,类似于于非叶子节点的哈希值被称作路径哈希值,而叶子节点的哈希值是实际数据的哈希值。

  当数据从A端传到B端时,为了检验数据的完整版性,只须要验证A、B端上所构造的Merkle树的根节点与非 一致即可。若一致,表示数据在传输过程中那末存在改变。若不一致,说明数据在传输过程中被修改。我应该 通过Merkle树很容易定位找到被篡改的节点。定位的时间多样化度为O(log(n))。

  比特币的轻量级节点所采用的SPV验证我应该 利用Merkle树一种生活生活优点。

  区块链中的Merkle树是二叉树,用于存储交易信息。每个交易两两配对,构成Merkle树的叶子节点,进而生成整个Merkle树。Merkle树使得用户还须要通过从区块头得到的Merkle树根和别的用户所提供的后面 哈希值列表去验证某个交易与非 所含在区块中。提供后面 哈希值的用户很多说需我应该 可信的,不可能 伪造区块头的代价很高,而后面 哈希值不可能 伪造得话会原因分析分析着验证失败。

  通常,加密的hash最好的办法像SHA-2和MD5用来做Hash。但不可能 仅仅解决数据都是蓄意的损坏或篡改,还须要改用全都安全性低但速率单位高的校验和算法,如CRC。

  Second Preimage Attack: Merkle tree的树根很多说表示树的速率单位,这不可能 会原因分析分析着second-preimage attack,即攻击者创建一另另4个具有相同Merkle树根的虚假文档。一另另4个简单的解决最好的办法在Certificate Transparency中定义:当计算叶节点的hash时,在hash数据前加0x00。当计算外部节点是,在前面加0x01。另外全都实现限制hash tree的根,通过在hash值前面加速率单位前缀。我应该 ,前缀每一步会减少,非要当到达叶子时前缀依然为正,提取的hash链才被定义为有效。

Merkle tree操作:

  1.创建Merckle Tree

  加入最底层有9个数据块。

  step1:(红色线)对数据块做hash运算,Node0i = hash(Data0i), i=1,2,…,9

  step2: (橙色线)相邻另另4个hash块串联,我应该 做hash运算,Node1((i+1)/2) = hash(Node0i+Node0(i+1)), i=1,3,5,7;对于i=9, Node1((i+1)/2) = hash(Node0i)

  step3: (黄色线)重复step2

  step4:(绿色线)重复step2

  step5:(暗蓝色线)重复step2,生成Merkle Tree Root

  易得,创建Merkle Tree是O(n)多样化度(这里指O(n)次hash运算),n是数据块的大小。得到Merkle Tree的树高是log(n)+1。

  2.检索数据块 

  为了更好理解,亲戚亲戚亲戚朋友假设有A和B两台机器,A须要与B相同目录下有8个文件,文件分别是f1 f2 f3 ....f8。一种生活生活前一天亲戚亲戚亲戚朋友就还须要通过Merkle Tree来进行快速比较。假设亲戚亲戚亲戚朋友在文件创建的前一天每个机器都构建了一另另4个Merkle Tree。具体如下图:

  从上图可得知,叶子节点node7的value = hash(f1),是f1文件的HASH;而其父亲节点node3的value = hash(v7, v8),也我应该 其子节点node7 node8的值得HASH。我应该 我应该 表示一另另4个层级运算关系。root节点的value其实是所有叶子节点的value的唯一价值形式。

  只要A上的文件5与B上的不一样。亲戚亲戚亲戚朋友咋整 通过另另4个机器的merkle treee信息找到不相同的文件? 一种生活生活比较检索过程如下:

  Step1. 首先比较v0与非 相同,不可能 不同,检索其孩子node1和node2.

  Step2. v1 相同,v2不同。检索node2的孩子node5 node6;

  Step3. v5不同,v6相同,检索比较node5的孩子node 11 和node 12

  Step4. v11不同,v12相同。node 11为叶子节点,获取其目录信息。

  Step5. 检索比较完毕。

  以上过程的理论多样化度是Log(N)。 

  3. 更新,插入和删除

  其实网上有全都全都关于Merkle Tree的资料,但大次要那末涉及Merkle Tree的更新、插入和删除操作,讨论Merkle Tree的检索和遍历的比较多。显然,一种生活生活树价值形式的操作肯定不仅包括查找,也包括更新、插入和删除的啊。我应该 查到风之舞555的总结的文章,少有感悟,下面引用风之舞555对该次要讲述:

  对于Merkle Tree数据块的更新操作其实是很简单的,更新完数据块,我应该 接着更新其到树根路径上的Hash值就还须要了,我应该 很多改变Merkle Tree的价值形式。我应该 ,插入和删除操作肯定会改变Merkle Tree的价值形式,如下图,一种生活生活插入操作是我应该 的:

  插入数据块0后(考虑数据块的位置),Merkle Tree的价值形式是我应该 的:

  而有的同学在考虑一种生活生活插入的算法,满足下面条件: 

  • re-hashing操作的次数控制在log(n)以内
  • 数据块的校验在log(n)+1以内
  • 除非原始树的n是偶数,插入数据后的树那末孤儿,我应该 不可能 有孤儿,那末孤儿是最后一另另4个数据块
  • 数据块的顺序保持一致
  • 插入后的Merkle Tree保持平衡

  我应该 后面 的插入结果就会变成我应该 :

  全都全都,Merkle Tree的插入和删除操作其实是一另另4个工程上的问题图片报告 ,不同问题图片报告 会有不同的插入最好的办法。不可能 要确保树是平衡的不可能 是树高是log(n)的,还须要用任何的标准的平衡二叉树的模式,如AVL树,红黑树,伸展树,2-3树等。那先 平衡二叉树的更新模式还须要在O(lgn)时间内完成插入操作,然还须要保证树高是O(lgn)的。那末很容易还须要看出更新所有的Merkle Hash还须要在O((lgn)2)时间内完成(对于每个节点如要更新从它到树根O(lgn)个节点,而为了满足树高的要求须要更新O(lgn)个节点)。不可能 仔细分析得话,更新所有的hash实际上还须要在O(lgn)时间内完成,不可能 要改变的所有节点都是相关联的,即亲戚亲戚亲戚朋友要都是都是从某个叶节点到树根的一根绳子 绳子 路径上,不可能 一种生活生活清况 相近。

  实际上Merkle Tree的价值形式(与非 平衡,树高限制几次)在大多数应用中很多说重要,我应该 保持数据块的顺序也在大多数应用中我应该 须要。我应该 ,还须要根据具体应用的清况 ,设计买车人的插入和删除操作。一另另4个通用的Merkle Tree插入删除操作是那末意义的。


拓展知识:

  Hash List 与 Merkle tree 有那先 异同?

       娓娓道来~~~~~~~

  网络传输数据的前一天,A收到B的传过来的文件,须要确认收到的文件有那末损坏。要怎样解决?

  :一种生活生活生活最好的办法是B在传文件前一天先把文件的hash结果给A,A收到文件再计算一次哈希我应该 和收到的哈希比较就知道文件与非 损坏。

  我应该 当文件很大的前一天,往往须要把文件拆分全都全都的数据块个人所有传输,一种生活生活前一天就须要知道每个数据块的哈希值。咋整 办呢?

  :一种生活生活清况 ,还须要在下载数据前一天先下载一份哈希列表(hash list),一种生活生活列表每一项对应一另另4个数据块的哈希值。对一种生活生活hash list拼接后还须要计算一另另4个根hash。实际应用中,亲戚亲戚亲戚朋友只要确保从一另另4个可信的渠道获取正确的根hash,就还须要确保下载正确的文件。

  我应该 基于hash list的方案我应该 一另另4个问题图片报告 : 数据块全都全都的前一天,往往遍历所有数据块的Hash List代价比较大。

  有没一种生活生活生活最好的办法还须要通过次要Hash就能校验整个文件的完整版性呢?

  :答案是肯定的!Merkle Tree 就能做到!

  Merkle Tree和Hash List的主要区别是,还须要直接下载并立即验证Merkle Tree的一另另4个分支。不可能 还须要将文件切分成小的数据块,我应该 不可能 有一块数据损坏,仅仅重新下载一种生活生活数据块就行了。不可能 文件非常大,那末Merkle tree和Hash list都很大,我应该 Merkle tree还须要一次下载一另另4个分支,我应该 立即验证一种生活生活分支,不可能 分支验证通过,就还须要下载数据了。而Hash list非要下载整个hash list很多 验证。


【时间仓促,如有错误,欢迎指正! ||   欢迎留下您的评语!  亲戚亲戚亲戚朋友一块儿探讨、学习区块链!】

【转载请注明出处!http://www.cnblogs.com/X-knight/


REFERENCE

1.Merkle Tree 学习 http://www.cnblogs.com/fengzhiwu/p/5524324.html

2. Merkle Tree 增删数据http://crypto.stackexchange.com/questions/22669/merkle-hash-tree-updates

3.Merkle Tree、Hash List https://blog.csdn.net/pony_maggie/article/details/74538902