默克尔树
默克尔树是区块链技术的一个基本概念。它们是一种特殊的二进制树,用于编码大块的信息。默克尔树的酷之处在于,它们是一种自下而上的 "建立",并允许你验证某些值是否存在于树中,而无需在树的每个元素上循环。这可能非常有用,我们会看到。
什么是梅克尔树?
Merkle 树是一种哈希树,其中每个叶子节点都标有数据块的加密哈希值,而每个非叶子节点都标有其子节点标签的加密哈希值。大多数哈希树的实现是二进制的(每个节点有两个子节点),但它们也可以有更多的子节点。
一个典型的 Merkle 树看起来是这样的。
让我解释一下这是怎么回事。树的所有叶子节点,即没有任何进一步子节点的节点,包括你想编码的数据的哈希值。注意,你想在树上编码的值总是只是叶子节点的一部分。因为它是一棵二叉树,每个非叶子节点有两个子节点。当你从叶子节点向上移动时,父节点会有叶子节点的组合哈希值,以此类推。
当你继续这样做时,最终你会在单一的顶级节点上结束,被称为 Merkle 树根,这将会起到非常重要的作用。
简单的例子
假设我们有 4 个交易。所有这些交易都是在同一个区块中执行的,其中包括 "交易 A"、B、C 和 D。这些交易中的每一个都将得到哈希值。让我们把这些哈希值分别称为 "哈希 A"、B、C 和 D。
以下将是这些交易的 Merkle 树的结果。
使用 Merkle Root 验证有效性
当这些交易被卷进一个区块时,区块头将包含 Merkle Root,哈希 ABCD。所有矿工都有一份迄今为止所有交易的副本,因此也有所有交易的哈希值。任何矿工都可以按需重建 Merkle 树,这意味着每个矿工都可以为同一组交易独立得出相同的 Merkle 根。
这使得任何矿工都可以验证一个欺诈性交易。假设有人试图引入一个虚假交易,而不是交易 D,我们称之为交易 E。交易 E 的哈希值是 Hash E。C 和 E 的哈希值是 Hash CE,它与 Hash CD 不同。当哈希 AB 和 CE 被哈希在一起时,你得到哈希 ABCE。由于哈希 ABCE 与哈希 ABCD 不同,我们可以得出结论,交易 E 是欺诈性的。
矿工可以在自己的区块中重新计算 Merkle Root,并试图将该版本发布到区块链上,但由于其他每个矿工都有不同的 Merkle Root,欺诈性的矿工很容易被拒绝。
哈希函数
我们之前在谈论 IPFS 的时候已经介绍了哈希函数,但只是回顾一下:为了将交易 A 哈希成哈希 A,使用了一个单向的加密哈希函数。一旦散列,哈希 A 不能变成交易 A;散列是不可逆的。
每个区块链使用不同的哈希函数,但它们都有相同的共同属性。