区块链中merkle树是怎样验证的,它的具体运行机制是

首先要理解区块链里面经常使用的梅克尔树(Merkle tree)是什么?
如下图所示:Merkle树是一种二叉树的数据结构,最底层是叶子,内容是对应数据的哈希值,然后每两片相邻的叶子联合起来做一次哈希计算成为上层节点的内容,持续这样的计算就产生了一个最顶层的节点的哈希值。如果叶子层对应的原始数据是由偶数个组合而成,那么自然两两结合配对。如果原始数据点个数为奇数,那么从最左边开始两两结合之后还有一个孤节点数据,它和自身结合配对后计算哈希值。?
区块链中merkle树是怎样验证的,它的具体运行机制是

这种特殊结构在比特币区块链代码里面使用到了。如下图所示:比特币的区块头(Block Head)里面包含了一个梅克尔树根, 也就是所有块交易哈希值的关联树计算后得到的顶层哈希值。
区块链中merkle树是怎样验证的,它的具体运行机制是

那么,为啥需要这样的数据结构?这就需要从简化支付验证(SPV:Simplified Payment Verification)说起了,也就是说如何验证或确保一个数字货币的交易已经在对应区块链的一个区块中了?一种无脑的方式就是自己搭建一个节点下载和同步好区块链数据,然后通过节点程序查询交易对应的哈希值来判断是否交易已经存在这条已经同步好的数据区块中。这种方法至少有两个弊端:
数据下载量太大:下载通信量大同时本地存储空间大;验证计算量大:需要把所有交易哈希值都串起来再计算对应的哈希值去比较是否相同。中本聪(Nakamoto Satoshi)当初设计这个就是考虑到比特币这条链的数据增长(目前已经在300GB左右)导致普通节点或者终端无法承载所有数据而实现自身验证交易可靠性,因此非常需要一个简单易行而又可靠的方法可以让一个轻节点只需要下载少量数据即可完成交易真实性的验证,这就是梅克尔树数据结构和算法发挥巨大作用了:
SPV钱包节点无需下载区块链完整数据,而只需下载区块链的每块不包含交易的头部数据;在验证某一个交易真实性的时候,SPV钱包节点只需要把该交易哈希值向网络中连接的全节点(Full Node: 同步了全部区块链数据的节点)发起询问网络里面的全节点只需要回复最小量必要数据给SPV钱包,即可验证交易真实性;如果SPV钱包不信任提供交易验证数据的全节点,还可以同时发起多个全节点的询问,来确保交易验证的最大可靠性。如下图所示,假如一个区块包含了Ta,Tb,Tc,Td,Te,Tf,Tg,Th等8个交易,而SPV钱包发起了对交易Td真实性的查询。在梅克尔树里面可以快速计算得到各个层级的哈希值,直到梅克尔树根的哈希值。然而被询问的全节点,无需传输整个梅克尔树的节点数据,而只需要传回给SPV钱包四个哈希值:Td, Hc, Hab, Hefgh。也就是说减少了一半的数据量传输。聪明的你会很快发现,所需要传输的验证数据的个数等同于梅克尔树的高度(从底部哈希值开始计算):
区块链中merkle树是怎样验证的,它的具体运行机制是

但是如果这个块里面包含的交易个数量变得很大,比如说有1000个,那么需要传输的数据量只需要如下个数:
区块链中merkle树是怎样验证的,它的具体运行机制是

也就是少传输了近100倍的数据量!如果块的总交易量继续上升,这个验证数据传输量的相对压缩比例还可以继续增大!!
区块链中merkle树是怎样验证的,它的具体运行机制是


推荐阅读