专栏首页维基链技术专区晓说区块链 | 梅克尔树保障了区块链数据不可篡改,它的机制是怎样的?
原创

晓说区块链 | 梅克尔树保障了区块链数据不可篡改,它的机制是怎样的?

梅克尔树(Merkle tree)是为了解决多重一次签名中的认证问题而产生的,由于梅克尔树结构具有一次签名大量认证的优点,在认证方面具有显著的优势。

如今,梅克尔树的树形结构已经被广泛应用到了信息安全的各个领域,比如证书撤销、区块链数据安全、群密钥协商等等。那它的运行机制究竟是怎么样的呢?

本期《晓说区块链》,陈晓东先生(维基链首席技术官)将围绕这个话题,为大家解读。

网友:经常看到区块链验证交易的内容中,涉及到merkle树相关的内容,请问区块链中merkle树是如何验证的呢?它的具体运行机制是怎么样的?

陈晓东:首先要理解区块链里面经常使用的梅克尔树(Merkle tree)是什么?

如下图所示:Merkle树是一种二叉树的数据结构,最底层是叶子,内容是对应数据的哈希值,然后每两片相邻的叶子联合起来做一次哈希计算成为上层节点的内容,持续这样的计算就产生了一个最顶层的节点的哈希值。如果叶子层对应的原始数据是由偶数个组合而成,那么自然两两结合配对。如果原始数据点个数为奇数,那么从最左边开始两两结合之后还有一个孤节点数据,它和自身结合配对后计算哈希值。

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

那么,为啥需要这样的数据结构?这就需要从简化支付验证(SPV:Simplified Payment Verification)说起了,也就是说如何验证或确保一个数字货币的交易已经在对应区块链的一个区块中了?一种无脑的方式就是自己搭建一个节点下载和同步好区块链数据,然后通过节点程序查询交易对应的哈希值来判断是否交易已经存在这条已经同步好的数据区块中。这种方法至少有两个弊端:

  1. 数据下载量太大:下载通信量大同时本地存储空间大;
  2. 验证计算量大:需要把所有交易哈希值都串起来再计算对应的哈希值去比较是否相同。

中本聪(Nakamoto Satoshi)当初设计这个就是考虑到比特币这条链的数据增长(目前已经在300GB左右)导致普通节点或者终端无法承载所有数据而实现自身验证交易可靠性,因此非常需要一个简单易行而又可靠的方法可以让一个轻节点只需要下载少量数据即可完成交易真实性的验证,这就是梅克尔树数据结构和算法发挥巨大作用了:

  1. SPV钱包节点无需下载区块链完整数据,而只需下载区块链的每块不包含交易的头部数据;
  2. 在验证某一个交易真实性的时候,SPV钱包节点只需要把该交易哈希值向网络中连接的全节点(Full Node: 同步了全部区块链数据的节点)发起询问;
  3. 网络里面的全节点只需要回复最小量必要数据给SPV钱包,即可验证交易真实性;
  4. 如果SPV钱包不信任提供交易验证数据的全节点,还可以同时发起多个全节点的询问,来确保交易验证的最大可靠性。

如下图所示,假如一个区块包含了Ta,Tb,Tc,Td,Te,Tf,Tg,Th等8个交易,而SPV钱包发起了对交易Td真实性的查询。在梅克尔树里面可以快速计算得到各个层级的哈希值,直到梅克尔树根的哈希值。然而被询问的全节点,无需传输整个梅克尔树的节点数据,而只需要传回给SPV钱包四个哈希值:Td, Hc, Hab, Hefgh。也就是说减少了一半的数据量传输。聪明的你会很快发现,所需要传输的验证数据的个数等同于梅克尔树的高度(从底部哈希值开始计算):

但是如果这个块里面包含的交易个数量变得很大,比如说有1000个,那么需要传输的数据量只需要如下个数:

也就是少传输了近100倍的数据量!如果块的总交易量继续上升,这个验证数据传输量的相对压缩比例还可以继续增大!!

具体证明如下:

然后SPV钱包把计算出来的Habcefgh哈希值和自己同步下载好的区块数据块头里面的梅克尔树哈希值比较相等就行了。如果没有找到相等的,说明交易不可信。可能数据还没有同步过来,也可能交易就根本没有发生,所以暂时还不能相信或者接受/确认这个交易。

最后笔者这里抛一个问题,这个梅克尔树的数据结构包括每个树节点里面的值是否需要物理存储下来作为区块链的一部分而存在,甚至在网络广播呢?答案是当然不需要了。第一是不需要,因为被询问的全节点可以根据自己全量的交易块里面快速计算出SPV钱包验证需要的相应数据,并且不需要存储梅克尔树的中间层的数据。第二是假如特意存储了这个梅克尔树的全部节点数据,那么存储的数据比只单纯纯粹交易数据或者交易哈希值数据多了不少,明显是有违初衷的,相比其节约的哈希值计算时间的收益是微乎其微的,可以说是得不偿失。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 晓说区块链 | 区块链经济的熊市局面该如何改变?

    区块链行业中能落地的应用需要具备哪些特点?区块链应该怎么样应用到具体的行业中?区块链经济的熊市局面,又该如何改变?

    维基链WICC
  • 积极尝试区块链治理方案报告

    2008年,一个自称中本聪的人在密码学讨论组上贴出了一份电子货币的新构想,比特币就此问世。

    维基链WICC
  • 维基链开发者社区问答Q&A

    Q2: 区块链在应用的时候是有固定流程的吗?比如从数据层到网络层,共识层,激励层,合约层,最后是应用层?

    维基链WICC
  • Python NLP 入门教程

    本文简要介绍Python自然语言处理(NLP),使用Python的NLTK库。NLTK是Python的自然语言处理工具包,在NLP领域中,最常使用的一个Pyth...

    小小科
  • Qt多语言翻译示例

    Qt君
  • Windows下编译Chrome V8

    步骤基本上可以完成按照官方的操作来处理,这里记录编译中遇到的问题(编译环境 xp sp3、vs2005、python 2.6、scons 2.0):

    meteoric
  • 18.3.26日报

    1,给window.scrollX设置值会导致堆栈溢出,看堆栈是反复进入js的访问器回调导致。但发现github上最新代码反而没问题。一开始以为是v8-5-7和...

    龙泉寺扫地僧
  • 从 HTTP 到 HTTPS 再到 HSTS 转

    HSTS(HTTP Strict Transport Security)国际互联网工程组织IETE正在推行一种新的Web安全协议

    wuweixiang
  • 生信流程大全-基于nextflow的nf-core

    题目:The nf-core framework for community-curated bioinformatics pipelines

    生信技能树
  • 对抗Deepfake:AI驱动的成像系统识别图像是否经过修改

    为了防范能够改变照片和视频的复杂方法,纽约大学Tandon工程学院的研究人员展示了一种实验技术,利用人工智能对从采集到传输的整个过程中的图像进行认证。

    AiTechYun

扫码关注云+社区

领取腾讯云代金券