默克尔树与默克尔根

区块链是用于记录数据的去中心化账本，也是加密货币的技术基础。与人工记录的账本不同，区块链具有不可篡改性，也就是说，区块链上的任何记录都是不能被更改的最终结果。而在突出区块链独特性方面，绝对少不了默克尔树（Merkle Tree）和默克尔根（Merkle Root）。

作为区块链的组成部分，默克尔树有助于有效验证交易并维护链上存储信息的完整性。在去中心化网络中，人手一份网络数据的副本，比如比特币，因此有必要验证这些数据是否有效，以保证账本的一致性。下文将详细介绍默克尔树和默克尔根在区块链中的应用。

什么是默克尔树？

默克尔树是一种能高效地验证和维护数据集完整性的结构。它由多个交易哈希组成，以树状结构排列。哈希函数在区块链中被用于简单记录交易细节，但这些细节都是能保持一致性的。换句话说，哈希数列可以输入任何长度，但却能输出一个固定长度，这有助于有效地处理大量信息。

默克尔树由斯坦福大学教授拉尔夫·默克尔（Ralph Merkle）于1980年开发，并在《经认证的数字签名 》一文中提出。默克尔树大多被用于点对点网络（P2P）以帮助信息实现共享和独立验证。与此同时，加密货币也少不了它的身影，如比特币，用以验证交易的有效性。

区块链顾名思义是由链接在一起的区块组成的，而每个区块又能承载成千上万笔交易数据。因此，验证链上交易需要大量的空间和算力。但有了默克尔树后，交易可以被打包验证，而不一定非要每一笔交易单独验证。

在默克尔树中，交易按对分组，每对交易的哈希值被找到后会存储在父节点中。父节点也是按对分组的，它们的哈希值又被存储到上一层中，依次叠加，直到生成哈希树根。概括来说，默克尔树上有三种类型的节点。

1. 叶节点：一个区块中的每一笔交易都有其哈希值，这些哈希值就存储在叶节点上。
2. 非叶节点：非叶节点由不同叶节点的哈希值组成，可以看作是叶节点和根节点之间的中间节点。
3. 根节点：即默克尔根，只包含一个哈希值，但代表的是一个区块的所有交易，存储在区块头中。

因此，只需要验证区块头即可完成对该区块所有交易的验证。默克尔树采用二进制运算，这意味着，叶节点的数量需是偶数才能很确保搭建的准确性。但如果出现叶节点是奇数的情况，最后一个叶节点会被复制一遍，最终还是会变成偶数。

什么是默克尔根？

默克尔根是默克尔树上所有交易的哈希值。 当一个区块上的所有交易都成功配对并得出哈希值后，最终得到的值就是默克尔根。所以，更改任意数据都会导致默克尔根发生变化。 因此，一旦默克尔根生成，即可确保网络上没有任何数据被更改。

默克尔树的运作方式

默克尔树将大容量数据分解成更易处理的较小单元，同时整合一个区块中的所有交易数据，生成单一的数字指纹，使交易验证不仅变得更加简单，速度也得到了大幅提升。

默克尔树按对将节点进行组合并生成哈希值，最后得出默克尔根。与大自然的树不同，默克尔树的结构是自下而上的，下为叶，上为根。来自叶节点的不同交易被配对形成非叶节点，直到形成根节点。

举例来说，现在有一个包含8笔不同交易的区块，这8笔交易分别命名为T1, T2, T3, T4, T5, T6, T7和T8，每笔交易的哈希值分别为H1、H2、H3、H4、H5、H6、H7和H8。接着，将这些哈希值配对后，又得出新的哈希值，分别是H（12）、H（34）、H（56）和H（78）。然后，再次配对得到两个新的哈希值H（1234）和H（5678）。最后再次运算得到的就是默克尔根H（12345678）。具体可见下图。

需要注意的是，上图只是为了帮助理解默克尔树和默克尔根的概念，实际情况远远比这个例子要复杂得多。最后生成的默克尔根被存储在区块头中，并用于挖矿。例如，在比特币网络中，只要得出区块头的哈希值就可以，而不是处理这个区块包含的每一笔单独交易。默克尔根也易于发现初始数据的任何变化，确保了整个系统的不可篡改性。

默克尔树的优势

在区块链中运用默克尔树和默克尔根的显著优势包括：

高效验证

默克尔树提供了高效的交易验证方式，而不需要消耗大量算力。

节省内存

使用默克尔树验证交易不需要复制整个区块链的数据。因此，与其他数据结构相比，需要的内存更小。

快速交易

由于所有交易会按对分组并产生单一哈希值，所以信息的链上传输会变得更快。这也是加密货币传输速度非常快的主要原因之一。

防止篡改

默克尔树有助于检测交易是否被篡改。当一笔交易完成哈希运算并被存储在区块链上时，初始信息的变化也会导致哈希值的变化。所以，可以通过比较当前哈希值和存储在区块头的哈希值来检测信息是否被篡改。

默克尔树和默克尔根在区块链中的重要性

区块链由区块链接而成，一个区块可以容纳多达数千笔不同的交易。而在默克尔树顶端获得的默克尔根哈希值整合了该区块中包含的所有交易，使得交易验证过程变得高效，且任何改动都易于发现。

若不使用默克尔树，则网络上的每个节点都需要持有其账本的副本，而验证交易将需要比对节点的所有副本，这将耗费大量算力和内存空间。而有了默克尔树，这个复杂的过程可以省略，用最小的算力就能完成验证。

默克尔树和默克尔根在区块链中的应用

正因为默克尔树和默克尔根在区块链中的重要性，在比特币和其他加密货币网络中，它们被广泛应用于挖矿和验证。

挖矿

默克尔树是比特币网络的组成部分之一。为了验证交易和添加新区块，矿工需要对数据进行哈希运算，以产生符合特定条件的输出值，这个数值可能得尝试数万亿次才能得到，而矿工们则必须不停测试随机数字。

挖矿可以在默克尔根哈希值的帮助下变得更容易、更高效，只需要使用不同的交易搭建出正确的默克尔树，然后将根哈希值存储在区块头中。挖矿时再对区块头进行哈希运算即可，无需运算整个区块。

验证

如果在一个算力有限的设备上运行节点，可能无法下载一个区块中的所有交易并完成哈希运算。但引入默克尔证明后，即证明某特定交易存在于该区块中，则能减少要进行哈希运算的数量，因此，即使是算力有限的设备，也完全可以验证交易。

结论

默克尔树和默克尔根旨在强化链上数据的验证，有助于确保交易的有效性，而无需下载整个网络。它们是当今移动钱包的基石。用户可以在没有整个账本副本的情况下与区块链互动。