2.3.3　默克尔树

默克尔树（Merkle哈希树）属于二叉树的一种，而比特币的底层交易系统选择了默克尔树进行了实现。

1．什么是默克尔树？

由一个根节点、一组中间节点和一组叶子节点组成。根节点表示的是最终的那个节点，只有一个。叶子节点可以有很多，但是不能再扩散，也就是没有子节点。

如果把它想象成一棵树，由树根长出树干，树干上长出树枝，树枝长出叶子，但是，叶子上不会再长出叶子，如图2-7所示。

图2-7　默克尔树示意图

    Root：就是根节点，所有的子节点汇总到这里。
Hash：能将任意长度的二进制明文映射为较短的二进制串的算法，也叫“哈希算法”，如2.3.1
小节介绍的MD5、SHA等算法，经过哈希算法哈希后的结果，也称为哈希值。
Data0, Data1……Data3：代表的是具体的原始数据。
B0, B1……B3：是把原始数据进行哈希运算后得到的对应哈希值。

一个简单的默克尔树就是图2-7所显示的那样，由以下三个步骤来实现：

（1）把最底层的Data0, Data1……Data3这四条数据，每一条单独进行Hash，得出4个哈希值作为叶子节点。

（2）把相邻的两个叶子节点的哈希值拿出来再进行Hash，如B0的哈希值加上B1的哈希值，求和的结果Hash后得出B4。

（3）递归执行这样的Hash操作，直到最终Hash出一个根节点，就结束了。

默克尔树的运行原理，在图中展现是：B0 + B1 Hash得出B4，B2 + B3 Hash得出B5，B4 + B5 Hash得出Root根节点。由于每个节点上的内容都是哈希值，所以也叫“哈希树”。

2．默克尔树的三大特性

（1）任意一个叶子节点的细微变动都会导致Root节点发生翻天覆地的变化，这个可以用来判断两个加密后的数据是否完全一样。

（2）快速定位修改，如果Data1中数据被修改，会影响到B1、B4和Root，当发现根节点Root的哈希值发生变化，沿着Root→B4→B1，最多通过O（log n）时间即可快速定位到实际发生改变的数据块Data 1。

（3）零知识证明（详细内容参见本书第3章），它指的是证明者能够在不向验证者提供任何有用信息的情况下，使验证者相信某个论断是正确的。比如怎么证明某个人拥有Data0……Data3这些数据呢？创建一棵如图2-8所示的默克尔树，然后对外公布B1、B5、Root；这时Data0的拥有者通过Hash生成B0，然后根据公布的B1生成B4，再根据公布的B5生成Root，如果最后生成的Root哈希值能和公布的Root一样，则可以证明拥有这些数据，而且不需要公布Data1、Data2、Data3这些真实数据，具体实现方式如图2-8所示。

图2-8　零知识证明原理图

3．默克尔树在比特币中的应用

• 默克尔路径：表示从根节点到叶子节点所经过的节点组成的路径，图2-8中Root→ B4 → B1就是一条路径。
• 比特币中，默克尔树被用作归纳一个区块中打包的所有交易，同时生成整个交易集合的数字签名，且提供了一种校验区块是否存在某交易的高效途径，这就是默克尔路径。生成默克尔树需要递归地对各个子节点进行哈希运算，将新生成的哈希节点插入默克尔树中，直到只剩一个哈希节点，该节点就是默克尔树的根节点。
• 假设一个区块中有16笔交易，根据公式O（log n）可以算出16的对数是4，也就是要找到这个区块中的任意一笔交易，只需要4次就可以，它的默克尔路径会保存4个哈希值，我们来看一个统计（见表2-1），直观感受一下它搜索效率的提升。

表2-1　交易路径对照表

（注：一笔交易的大小，大概需要250 Byte左右的存储空间，路径数代表哈希值的数量，路径数是4表示这条路径存了4个哈希值，每个哈希值是32 Byte，区块大小=交易数* 250 Byte，路径大小=路径数* 32 Byte）

可以看出，当区块大小由16笔交易（4KB）增加至262 144笔交易（65MB）时，为证明交易存在的默克尔路径长度增长极其缓慢，仅仅从128字节到576字节。有了默克尔树，一个节点能够仅下载区块头（80字节／区块，里面包含上一区块头的哈希值、时间戳、挖矿难度值、工作量证明随机数，包含该区块交易的默克尔树的根哈希值），然后通过从一个满节点 ，回溯一条小的默克尔路径，就能认证一笔交易的存在，而不需要存储或者传输大量区块链中的大多数内容——这些内容可能有几个G的大小。这种不需要维护一条完整的区块链的节点，又被称作“简单支付验证（SPV）节点”，它不需要下载整个区块而仅仅通过默克尔路径去验证交易的存在。