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

  • 时间:
  • 浏览:2
  • 来源:大发快3_快3手机app下载_大发快3手机app下载

  在计算机领域,Merkle树大多用来进行完整性性验证避免。在避免完整性性验证的应用场景中,很糙是在分布式环境下进行没法 的验证时,Merkle树会大大减少数据的传输量以及计算的比较复杂度。

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

  如下图所示为另另三个小多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的树根从不表示树的深度1,这是因为会是因为second-preimage attack,即攻击者创建另另三个小多具有相同Merkle树根的虚假文档。另另三个小多简单的避免土依据在Certificate Transparency中定义:当计算叶节点的hash时,在hash数据前加0x00。当计算內部节点是,在前面加0x01。另外或多或少实现限制hash tree的根,通过在hash值前面加深度1前缀。如果,前缀每一步会减少,没法 当到达叶子时前缀依然为正,提取的hash链才被定义为有效。

Merkle tree操作:

  1.创建Merckle Tree

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

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

  step2: (橙色线)相邻另另三个小多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来进行快速比较。假设亲戚他们他们他们在文件创建的刚刚每个机器都构建了另另三个小多Merkle Tree。具体如下图:

  从上图可得知,叶子节点node7的value = hash(f1),是f1文件的HASH;而其父亲节点node3的value = hash(v7, v8),也如果 其子节点node7 node8的值得HASH。如果 没法 表示另另三个小多层级运算关系。root节点的value实在是所有叶子节点的value的唯一內部。

  如果A上的文件5与B上的不一样。亲戚他们他们他们为社 会么会通过另另三个小多机器的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是偶数,插入数据后的树没法 孤儿,如果是因为有孤儿,没法 孤儿是最后另另三个小多数据块
  • 数据块的顺序保持一致
  • 插入后的Merkle Tree保持平衡

  如果底下的插入结果就会变成没法 :

  如果,Merkle Tree的插入和删除操作实在是另另三个小多工程上的什么的问题,不同什么的问题会有不同的插入土依据。是因为要确保树是平衡的是因为是树高是log(n)的,都还后能 用任何的标准的平衡二叉树的模式,如AVL树,红黑树,伸展树,2-3树等。什么平衡二叉树的更新模式都还后能 在O(lgn)时间内完成插入操作,随完会保证树高是O(lgn)的。没法 很容易都还后能 看出更新所有的Merkle Hash都还后能 在O((lgn)2)时间内完成(对于每个节点如要更新从它到树根O(lgn)个节点,而为了满足树高的要求还后能 更新O(lgn)个节点)。是因为仔细分析搞笑的话,更新所有的hash实际上都还后能 在O(lgn)时间内完成,是因为要改变的所有节点一定会相关联的,即亲戚他们他们他们要一定会一定会从某个叶节点到树根的一根路径上,是因为你是什么 请况相近。

  实际上Merkle Tree的內部(与非 平衡,树高限制几个 )在大多数应用中从不重要,如果保持数据块的顺序也在大多数应用中如果 还后能 。如果,都还后能 根据具体应用的请况,设计当事人的插入和删除操作。另另三个小多通用的Merkle Tree插入删除操作是没法 意义的。


拓展知识:

  Hash List 与 Merkle tree 有什么异同?

       娓娓道来~~~~~~~

  网络传输数据的刚刚,A收到B的传过来的文件,还后能 确认收到的文件有没法 损坏。如何避免?

  :有一种生活生活土依据是B在传文件刚刚先把文件的hash结果给A,A收到文件再计算一次哈希如果和收到的哈希比较就知道文件与非 损坏。

  如果当文件很大的刚刚,往往还后能 把文件拆分如果的数据块所他们传输,你是什么 刚刚就还后能 知道每个数据块的哈希值。为社 会么会办呢?

  :你是什么 请况,都还后能 在下载数据刚刚先下载一份哈希列表(hash list),你是什么 列表每一项对应另另三个小多数据块的哈希值。对你是什么 hash list拼接后都还后能 计算另另三个小多根hash。实际应用中,亲戚他们他们他们如果确保从另另三个小多可信的渠道获取正确的根hash,就都还后能 确保下载正确的文件。

  如果基于hash list的方案没法 另另三个小多什么的问题: 数据块如果的刚刚,往往遍历所有数据块的Hash List代价比较大。

  有没法 一种生活生活土依据都还后能 通过次责Hash就能校验整个文件的完整性性呢?

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

  Merkle Tree和Hash List的主要区别是,都还后能 直接下载并立即验证Merkle Tree的另另三个小多分支。是因为都还后能 将文件切分成小的数据块,没法 是因为有一块数据损坏,仅仅重新下载你是什么 数据块就行了。是因为文件非常大,没法 Merkle tree和Hash list都很大,如果Merkle tree都还后能 一次下载另另三个小多分支,如果立即验证你是什么 分支,是因为分支验证通过,就都还后能 下载数据了。而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

猜你喜欢

谷歌DeepMind欲开发识别乳腺癌的AI技术:已获得3万名女性的乳房X线照片

据福布斯报道,DeepMind从日本东京慈恵会医科大学附属病院(JikeiUniversityHospital)获得了60 7年-2018年间约3万名一个女人患者的乳房x线照

2020-01-25

科学家称量子计算机速度存在理论上限

北京时间1月19日消息据国外媒体报道,过去200年间,标准计算机补救器的带宽不断提升。但近年来,这项技术的局限逐渐开始英文英文显露:芯片可能无法做得更小,元件也无法排得常抓,刚

2020-01-25

商务部:中美经贸高级别磋商双方牵头人通话讨论遗留问题

商务部今天举行例行新闻发布会,在回答中美经贸磋商大大问题时,商务部新闻发言人高峰介绍:4月3号到5号,刘鹤副总理与美国贸易代表莱特希泽、财政部长姆努钦在华盛顿一块儿主持第九轮中

2020-01-25

明清古堡建筑“西古堡”,古式宅院别具一格!

核心提示:西古堡,明清古堡建筑,居于河北省蔚县暖泉镇内,冀晋界东2公里。古堡集古城堡与古戏楼、寺院、宅院于一体。建于明嘉靖年间(1522一1566年),明末清初续建,是古蔚州“

2020-01-24

新武器提升利润 华为P10 Plus首次跨入5000元档

《新武器提升利润华为P10Plus首次跨入40000元档》文章可能性归档,不再展示相关内容,编辑建议你查看最新于此相关的内容:这支消防队如保“驾云”为民保平安?一座被大火吞噬的

2020-01-24