Merkle树和 Merkle证明

数据完整性是通信协议需要考虑的基本问题之一。 数据存储于硬盘中、将在网络中传输,应时时刻刻保证数据的完整性。区块链程序更是如此。

如果一组数据量不大的话,例如我们有 \(a_1\)\(a_2\)\(a_3\) 三个数据要传输, 发送方可以用串联数据片段并执行哈希,得到一个校验值 h,如下所示。

\(h = {hash}(a_1 + a_2 + a_3)\)

在收到数据后,接收方进行相同形式的串联,并按同样的哈希函数计算,比较哈希值是否一致就可知数据是否完整。

\(h' = {hash}(a_1 + a_2 + a_3)\)

但这个思路存在一定的效率问题。

在于当数据量比较大时候,例如有 \(a_1\)\(a_2\)\(a_3\)\(a_{100}\) 的数据片段的时候, 我们往往分批传输这些小块,每次只要有一小部分数据损坏,整个数据校验和便无法对应上, 我们也不知道过程中哪个小块错误了,导致我们重传整组数据,这是非常耗时的。 如果能将数据进一步细分成小组,对小组做校验和,再将小组与小组组合成大组做校验和,将能方便地解决上述问题。

Merkle树是一个在密码学中常使用的树形结构,适用于解决数据完整性问题。 它的结构功能异常简单,通常我们用二叉树的形式来表示一棵 Merkle树, 它存在的作用是数据分组并保证数据在存储中的完整性。 例如一棵包含了数字 1 到 8 的 Merkle二叉树,如图 4-4 所示。

../_images/Picture30.png

一棵包含了数字1到8的Merkle二叉树

在图中的 Merkle树里,我们一共持有8个基础数据, 18 ,它们两两分组形成最初的小组。

例如数据 1 与数据 2 ,它们分在一组中,并计算它们串联后的哈希值 \(H_{1}={hash}(1,2)\)

同理将数据 3 与数据 4 串联的串联哈希值计算为 \(H_2\),依次类推,形成第二层的树中节点。

之后再将第二层的树中节点\(H_1\)~ \(H_4\)两两分组。例如 (\(H_1\)\(H_2\)串联计算第三层的哈希值\(H_5\))。

逐层聚合反复递归,执行哈希计算。直到的仅剩下一个哈希值节点:根节点哈希值 Root ,该过程完毕。

如果碰上基础数据集不是偶数个元素(例如仅有7个数据),则复制一个元素,让它与自己的双胞胎做哈希运算。

由此我们可以推论:Merkle树的树叶都是数据、树中的节点都是哈希值。

那么,Merkle树如何提升了校验效率呢?

Merkle树的精妙在于它将一个庞大的数据集分散成组。

在网络传输的过程中,仅需逐步传送各个小组,并执行组合校验,再逐步传送,直到拼接完成整个数据集。 过程中若有任何数据传送出差错,仅需重传那个小分组。 如果数据集中的一个值在传输中被损毁,会影响该数据所在的整个分支、子树、到根节点的哈希值,方便我们快速定位出错点。 如图 4-5 所示,我们修改数据4为44后,相应路径直到根节点哈希都会产生变化。

../_images/Picture31.png

修改数据4为数据44后,相应的路径直到根节点哈希都发生了变化

Merkle树的应用场景在哪里呢?

Merkle树最实用的两个场景,其一是当比较两份大数据时,可以从根节点上就直接判断出两份数据是否相同(哪怕一个子数据不同,根节点的哈希值都不同)。

其二是可以做 “Merkle证明”,即在整棵树尚未 完整下载 的情况下,仅通过下载的部分数据来进行完整性校验,快速判断某数据小组是否在其应处的位置,举例如图 4-6 所示。

../_images/Picture32.png

Merkle证明数据64有效存在于该棵树中

在这里我们有一组份数据包含了8个元素,依次是 [5,27,18,64,30,2,43,48] ,当我们在传输过程中收到了数据 64 ,我们如何才能在其他数据尚未送达之前,证明以下两点?:

  • 数据 64 的确存在于这组组数据中。
  • 数据 64 存在的位置是第4格(第四顺位)。

按照 Merkle证明 ,我们仅需知晓4个哈希值即可作出证明。

  • 数字 64 的相邻数字 18 的哈希值 (图中为 1FXq)
  • 相邻分组 [5, 27] 的联合哈希值 (图中为 ec20)
  • 相邻分支的哈希值 (图中为 8f74)
  • 根节点哈希值 (图中为 6c0a)

证明推导过程如下:

我们计算得出 64 的哈希值为 9Dog,将结果与哈希值 1FXq 串联,计算得出联合哈希值 781a

重复上述过程,将 781aec20 串联,计算得出联合哈希值 5c71

重复上述过程,将 5c718f74 串联,计算出根哈希值 6c0a

若根哈希值与我们从数据发送方传来的值 6c0a 对比,相等,则证明完毕。

在整个校验过程中,我们并没有下载任何其他的数据,仅通过哈希值就能鉴别数据 64 的位置以及是否存在,是一种极其高效的方式,且可以横向扩展到任意大数量的数据集。