默克尔树与默克尔根详解
目录
什么是默克尔树?
默克尔树的工作原理是什么?
比特币中为何使用默克尔根?
总结
默克尔树与默克尔根详解
首页文章
默克尔树与默克尔根详解

默克尔树与默克尔根详解

高阶
发布时间 Jul 6, 2020更新时间 Feb 3, 2022
7m

目录


什么是默克尔树?

80年代初,著名的公钥密码学领域的计算机科学家拉尔夫·默克尔(Ralph Merkle)提出了默克尔树概念。
默克尔树结构能有效验证数据集的完整性,在需要参与者共享并独立验证信息的点对点网络中更能发挥效用。
哈希函数是默克尔树结构的核心。因此,我们建议大家先了解什么是哈希运算,然后再继续阅读本文。


默克尔树的工作原理是什么?

假设您想要下载一个大型文件。使用开源软件下载,通常需要检查下载文件的哈希值是否与开发人员公开的相匹配。如果匹配则说明两份文件一致。

如果哈希值不匹配,那就遇到麻烦了。要么您下载了伪装成软件的恶意文件,要么您就是下载不正确,最终结果都是文件不可用。如果下载不正确,您的心情肯定烦躁,毕竟等待文件下载已经耗费很长时间。现在重头来过,还得期望不再出现同样的问题。

您是否考虑过,有没有更简单的方法解决这个问题?这正是默克尔树的用武之地。默克尔树能将文件分解为多个数据块。例如,50GB的文件可以分解为100份,每份大小为0.5GB。随后,就能逐份下载。这就是种子文件的原理。
此时的文件源就是一个哈希值,称之为默克尔根。这个单一哈希值代表了组成文件的所有数据块。而且,默克尔根能让数据验证变得更加简单。
为了便于理解,我们举例说明。下面将一个8GB的文件分为八份,每个片段分别以AH命名。随后,每个片段代入哈希函数,得出八个不同的哈希值。


通过哈希函数,计算出八个片段的哈希值。


希望以上示例解释还算易懂。我们有了所有片段的哈希值,如果其中一个出错,是不是对比源文件就能找出问题呢?或许可以,但是这样效率仍然极低。如果文件有成千上万个片段,难道要对所有片段进行哈希运算,再细致对比结果吗?

不需要。我们只需组合一对哈希值,再进行合并哈希运算即可。也就是说,我们用hA + hBhC + hDhE + hF以及hG + hH进行哈希运算。结果会得出四个哈希值。随后我们进行下一轮合并哈希运算,直到获得两个哈希值。这两个哈希值再合并运算,最终得出主哈希值,也就是默克尔根(亦称为根哈希值)。


这个结构看起来像一棵倒置的树。底部一排叶子,相互结合产生节点,最后生成根。


现在我们就得到了代表下载文件的默克尔根。将根哈希值与源文件的值进行比较,如果匹配,皆大欢喜!一旦哈希值不同,则证明数据遭到了篡改。换言之,一个或多个片段生成了不同的哈希值。因此,再小的数据修改都会彻底改变默克尔根。

幸好,要检查出错的片段也很方便。假设出错的是hE。首先,我们先向他人要来生成默克尔根的两个哈希值(hABCDhEFGH)。我们的hABCD值应与他人的匹配,就能证明子树没有错误。如果hEFGH不匹配,我们就能从这里纠错。之后再询问他人的hEFhGH哈希值,并与自己的比较,如果hGH没问题,则说明hEF是罪魁祸首。最后,我们比较hEhF的哈希值,一旦发现错误源是hE,那就可以重新下载该数据块。

综上所述,默克尔树的功能就是把数据划分为多份,然后反复哈希运算,最终形成默克尔根,这样就能有效验证究竟是哪里出现了错误数据。下一节中,我们将介绍其他的有趣应用。



想要开启加密货币之旅吗?立即前往币安购买比特币吧!



比特币中为何使用默克尔根?

默克尔树的用例不算少,但本文着重讨论它在区块链中发挥的重要作用。比特币和众多加密货币都离不开默克尔树。默克尔树是每个区块的组成部分,通常位于区块头。通过区块中每笔交易的交易哈希值(TXID),我们就能获得树叶。 

在这种情况下,默克尔根有多种用途。我们来看看默克尔根在加密货币挖矿和交易验证中的应用。


挖矿

比特币区块由两部分组成。第一部分为区块头,大小固定,包含区块元数据。第二部分为区块体,大小可变,但通常比区块头要大得多,包含交易列表。
矿工需重复哈希运算数据,直至产出符合特定条件的结果,才能挖出有效区块。为了获得正确结果,他们需要进行数万亿次尝试。每次尝试时,矿工改变区块头的随机数,即Nonce值,以此生成不同的结果。然而,区块的其他部分保持不变,其中的数千笔交易,每次仍需哈希运算。

默克尔根则大大简化了这个流程。开始挖矿时,所有的交易列队打包并构建为默克尔树,生成的32位根哈希值放入区块头。随后,无需再对整个区块进行哈希运算,只要针对区块头运算即可。

这种方式能防止数据篡改,因此切实有效,能够让区块的所有交易以紧凑的形式进行高效汇总。有效区块头的交易列表无法修改,否则将改变默克尔根。区块发送至其他节点后,将从交易列表中计算根哈希值。如果与区块头中的数值不匹配,则可拒绝该区块。


验证

我们还能使用默克尔根另一个有意思的属性,这关系到轻量级客户端(没有保存完整区块链副本的节点)的应用。如果您是在资源有限的设备中运行节点,肯定不希望下载区块中的所有交易并对其进行哈希运算。相反,您只需索要默克尔证明,即由全节点提供的证明交易被计入到特定区块的证据。这个证明更为人熟知的名称是“简单支付验证”或SPV,由中本聪在比特币白皮书中进行了详细说明。


要想检查hD,只需验证红色的哈希值即可。


假设,我们希望获取关于TXID为hD的交易信息。如果hC已知,则可以计算出hCD。然后,通过hAB,就能计算出hABCD。最后,参照hEFGH,就能检查计算出来的默克尔根是否与区块头中的根哈希值一致。如果成功匹配,就证明交易被计入了区块,因为要想使用不同的数据生成相同的哈希值几乎不可能实现。

在上面的示例中,我们只进行三次哈希运算。没有默克尔证明的话,则需要七次。现在的区块包含数千笔交易,而默克尔证明为我们节省了大量的时间和算力。


总结

默克尔树已经证明了自己在计算机科学应用领域的重要作用,正如我们所见,它在区块链中也颇具价值。默克尔树让分布式系统中的信息验证变得更加方便,避免了网络中冗余数据的拥堵。

如果没有默克尔树和默克尔根,比特币和其他加密货币区块不会像如今这般紧凑。虽然轻量级客户端在隐私和安全性方面缺乏优势,但有了默克尔证明,用户就能以最低的费用来验证交易是否计入了区块。