哈希树（hash tree；Merkle tree），在密码学及计算机科学中是一种树形数据结构，用于校验数据完整性和有效性，并且被广泛的应用于区块链网络中。

Merkle Tree

哈希树（hash tree；Merkle tree），在密码学及计算机科学中是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式 —— wikipedia

1920px-Hash_Tree.svg.png
图来源维基百科[3]

上面就是一个Merkle Tree的例子，叶子节点为数据块的hash值，每两个叶子节点拼接后的hash值作为其父节点的值，自底向上迭代后生成一个根节点，也形成一个完整的二叉树（满树）。

这种数据结构可以用来验证数据是否被篡改过。

1.1 检验数据的有效性

通常的下载场景中，例如我们想从 pypy 网站上下载一个软件 ,通常下载界面会提供一个校验和，这里是使用 sha256 hash算法,如下图所示：

那么当我们官方网站上或者从其他地方下载后，就可以利用同样的算法对文件进行hash计算，查看结果是否和网站给出的校验和一致，如果一致则说明文件未被篡改（哈希碰撞的概率很小忽略不计），否则被修改过。

1.2 Merkle Tree 校验文件

既然通过简单的hash运算就可以判断文件的有效性，那么为什么还需要树的结构呢？

因为在有些场景下，我们下载文件的时候通常是下载多个文件，或者一个文件的多个部分，而这些数据可能分散在不同的服务器上。也就意味着如果要比对文件的有效性，也就得从官方获得所有文件或者数据块的校验和，并且需要对文件进行一一匹配，这显然是很繁琐的。Merkel Tree 的作用就是将hash列表转换成树的形式，入上面描述所示，这样做了之后，对于多个文件，我们依然只使用一个hash，即根节点hash值。当用户下载完文件后，同样生成一个Merkle Tree，对比根节点即可。

1.3 Merkle Tree 在比特币中的应用

1.3.1 验证交易存在

比特币网络中，所有的交易信息都被存放在区块中，而所有的区块信息非常大
（从比特币网络信息可以看出，目前已经达到682532长度，大约427GB大小），保存这些完整信息的称为全节点，而普通用户往往不需要保存这些全局信息，可以通过向全节点查询信息即可，称为轻节点。

而比特币网络是一个P2P网络，那么就可能存在恶意节点，如何保证轻节点查询的信息是准确的呢？首先我们可以从某个信任的节点上获取区块的头部摘要，这部分摘要包含了区块中由交易组成的Merkel Tree 根节点hash。当我们需要从其他全节点查询具体的交易时，全节点会返回交易数据，同时给出证明，包含该交易到根节点所在路径上的节点的哈希值。当用户拿到该笔交易后，通过计算即可得到根节点hash，与自己所得到的根节点hash比对即可。

图来源《Master Bitcoin》[2]

例如我们需要得到 $H_k$ 这笔交易，全节点必须给出 $H_{IJ}$, $H_{MNOP}$,$H_{ABCDEFGH}$, 即途中蓝色节点，用户拿到证明后，就可以依次计算得到图中虚线节点所在位置的hash，从而得到根节点hash，对比即可。

也就是说在比特币网络中Merkle Tree 可以作为验证交易数据是否是可信的数据结构，这种方式的查找效率是$O(logn)$，这样即兼顾安全，又能保证效率。

1.3.2 验证交易不存在

上面提到了Merkle Tree 可以用于验证交易的存在性，那么节点是否可以证明某笔交易不存在某个区块中呢？
这个问题的提出可以参考 https://github.com/JoinMarket-Org/joinmarket/issues/693，这里按下不表。

他提出了一种 Sorted Merkle Tree，就是将叶子节点按照某种顺序进行排列，利用证明存在性的原理，证明某几个节点存在，而这几个节点的区间满足刚好包含不存在的节点的取值，从而说明节点的不存在性。

原文没有给出证明，我在这儿简单说明下：由于验证节点的范围是包含不存在节点的，假设该节点本身存在在树中，那么返回的路径中也必定包含该节点的信息，也就是说验证节点之间就一定不相邻了，那么想要伪造必须碰撞hash，来使得和真实根节点保持一致，显然这是很难做到的。

具体参考下面的例子：

         R
      /       \
    N_5        N_6
   / \         /   \
 N_1  N_2     N_3   N_4
 / \   / \    / \  /  \
0   2 3   4   6  7 8   9

如果想要证明1不存在，那么返回0和2的存在性证明，因为 $0<1<2$，在例如证明5不存在，是不是返回${3,4}$ 和 $6,7$这几个节点的存在性证明即可呢？答案是不可以，因为如果返回这两个区间，客户在验证的时候会把$N2$和$N4$当作相邻的节点，来计算上层hash，显然和真实的情况不符，从而得到错误的根节点hash，验证失败。

参考：

[1]. 《Sorted Merkle Tree as Solution to Issue #693》. Gist. 见于 2021年5月8日. https://gist.github.com/chris-belcher/eb9abe417d74a7b5f20aabe6bff10de0

[2]. GitHub. 《Bitcoinbook/Bitcoinbook》. 见于 2021年5月8日. https://github.com/bitcoinbook/bitcoinbook.

[3].《Merkle Tree》. 收入 Wikipedia, 2021年5月6日. https://en.wikipedia.org/w/index.php?title=Merkle_tree&oldid=1021824892.

Merkle-Tree在比特币中的应用

Contents