区块链Merkle树(默克尔树)

区块链利用Merkle树的数据结构存放所有叶子节点的值,并以此为基础生成一个统一的哈希值。Merkle树的叶子节点存储的是数据信息的哈希值,非叶子的节点存储的是对其下面所有叶子节点的组合进行哈希计算后得出的哈希值。

同样地,区块中任意一个数据的变更都会导致Merkle树结构发生变化,在交易信息验证比对的过程中,Merkle树结构能够大大减少数据的计算量,毕竟,我们只需验证Merkle树结构生成的统一哈希值就可以了。

区块链中的Merkle树结构

图2-23  区块链中的Merkle树结构

Merkle Tree,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵树。Merkle树的叶子是数据块(例如,文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash

Merkle Tree的特点

MT是一种树,大多数是二叉树,也可以多叉树,无论是几叉树,它都具有树结构的所有特点;

Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。

非叶子节点的value是根据它下面所有的叶子节点值,然后按照Hash算法计算而得出的。

通常,加密的hash方法像SHA-2和MD5用来做hash。但如果仅仅防止数据不是蓄意的损坏或篡改,可以改用一些安全性低但效率高的校验和算法,如CRC。

Second Preimage Attack: Merkle tree的树根并不表示树的深度,这可能会导致second-preimage attack,即攻击者创建一个具有相同Merkle树根的虚假文档。一个简单的解决方法在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: (橙色线)相邻两个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。

玖壹区块链声明

加微信:469649885区块链培训教程
还可免费获取区块链培训班试学名额

分享:

扫一扫在手机阅读、分享本文

区块链评论

玖壹区块链培训

玖壹区块链培训学院简称(玖壹学院http://www.91xiubbs.com/)提供区块链技术培训资料、区块链开发培训视频教程等下载,不过网上自学区块链技术课程必然存在一些缺陷:遇到问题易卡壳、学习周期漫长、无针对性等。区块链培训机构现场面对面的讲授区块链培训课程可以让您和团队在最短时间内掌握正确、系统、高效的区块链实战技术。