学习
实践
活动
专区
工具
TVP
写文章

元宵节,用汤圆带你理解默克尔树

今天是正月十五,元宵佳节。肖恩祝大家元宵节快乐,新的一年越来越好。为了未来更好,前进的脚步不能停止,今天继续跟着肖恩学点区块链知识。在之前关于

比特币工作流程

一文中,提及到了区块头的组成,简单讲到了其组成数据之一的默克尔树根。今天肖恩就来讲解下默克尔树。

默克尔树是什么

默克尔树,英文名Merkle树。是一种包含加密哈希值的二叉树(“树”是计算机领域的一个专有术语,是一种具有分支的数据结构)。与现实中的树不一样的是,二叉树是倒置显示的,“根”在上部,“叶子”下部。

如图1所示,就是一个默克尔树的结构。

HABCD:默克尔树根。

HAB和HCD:中间节点。

HA、HB、HC、HD:叶子节点。

DA、DB、DC、DD:存储着交易数据。

其中,HA、HB、HC、HD就是由DA、DB、DC、DD进行哈希计算而来的。并且,每个节点都为32个字节。

图1

默克尔树的构建过程

默克尔树是自底向上构建的,主要的构建步骤如下:

1. 交易数据进行用SHA256算法进行两次计算(又称Double-SHA256)生成32个字节的哈希值,即生成叶子节点。

如HA=SHA256(SHA256(DA))

2. 相连的叶子节点串联起来,形成一个64字节的字符串,再用Double-SHA256计算生成32个字节的哈希值,即生成中间节点。

如:HAB=SHA256(SHA256(HA+HB))

3. 重复步骤二,不断生成中间节点。

4. 最终哈希计算生成默克尔树根,如图1中的HABCD。

当然,相互串联的节点要求其始终是偶数的,若出现奇数的情况,则会复制自身一份,自身与自身串联,然后进行Double-SHA256计算。如图2,HC只有一个节点,那么就自身复制一个HC',HC与HC'进行Double-SHA256计算获得HCC',再继续进行默克尔树的构建工作。

图2

默克尔树有什么用?

默克尔树的用途涉及到简单支付验证(SPV)。顾名思义,简单支付验证(SPV)就是节点可以快速且简单地验证交易。

具体说来,区块链一直处于不断增长的阶段,会不断有新的区块产生,整个区块链账本的数据会越来越大,存储全部数据对节点的要求很高。SPV就不需节点把区块链中全部内容下载下来,仅需要存储部分足以验证交易的数据即可。这就是默克尔树根,根据默克尔树路径去哈希计算,将最终获得的“树根”与区块头中的默克尔树根对比,一次来验证相对应的交易是否存在。

此前在讲解隔离见证时,肖恩就有提到部分老节点因没有进行升级,就没办法验证交易的签名等信息。但老节点还是有其验证方式的,就是借助区块头中默克尔树根,验证默克尔路径进行哈希计算验证。

如何通过默克尔树验证交易

如图3,我们要验证L交易是否存在,我们只需要知道HK、HIJ、HMNOP、HABCDEFGH的值即可验证。具体验证过程如下:

1. 将L交易数据进行Double-SHA256计算获得HL'

2.HL'与HK进行Double-SHA256计算获得HKL'

3.HKL'与HIJ进行Double-SHA256计算获得HIJKL'

4.HIJKL'与HMNOP'进行Double-SHA256计算获得HIJKL'MNOP

5.HIJKL'MNOP与HABCDEFGH进行Double-SHA256计算获得HABCDEFGHIJKL'MNOP

6.HABCDEFGHIJKL'MNOP与HABCDEFGHIJKLMNOP是否一样,若一样,这说明L交易是存在的。

图3

理解了这个验证过程,可能你会觉得这个验证过程也没体现出简单性。这是因为肖恩举的例子中涉及到的交易数量比较低,当存在很多笔交易的时候,就会觉得这个验证过程简单了。

这个交易验证过程具有对数规律:

若有2笔交易,需要进行1(Log22)次Double-SHA256计算;

若有4笔交易,需要进行2(Log24)次Double-SHA256计算;

若有8笔交易,需要进行3(Log28)次Double-SHA256计算;

...

若有N笔交易,需要进行Log2N次Double-SHA256计算。

若Log2N的值不为整数,则舍弃小数位,整数位加一,如227

我们来看看y=Log2N的函数图像,随着N的不断增加,Log2N虽然也递增,但其增长趋缓。即当交易中的数量越来越多的时候,我们验证交易所需进行哈希计算次数越少。如若存在65535笔交易,我们需要验证的计算32(31265535

这就如同肖恩在元宵节自制汤圆,人越多,需要自制的汤圆就越多。但都需要准备材料,5个人需要买材料,10个人也需要买材料,5个人一次性买完,10个人也是一次性买完,汤圆包多了,动作也快了。总体上来说,自制10个人份量的汤圆比5个人份量的汤圆更能体现自制汤圆这项工作的效率。默克尔树用于简单支付验证也是这个道理,随着区块中交易越多,其验证交易的简单性与效率就更能被体现出来。

最后,祝大家元宵节快乐,吃个汤圆,团团圆圆。

关注肖恩说链,读懂区块链,抢占财富先机。

-End-

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190219G0WDSN00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券