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

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

比特币工作流程

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

默克尔树是什么

默克尔树，英文名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-

▼