比特币的区块头有多少个字节 9.7默克尔树

9.7默克尔树

区块链中的每个区块都包含区块中产生的所有交易，并用默克尔树表示。

Merkle树是一种哈希二叉树，是一种用于快速汇总和验证大规模数据完整性的数据结构。 此二叉树包含加密哈希值。 计算机科学中经常使用术语“树”来描述分支数据结构比特币的区块头有多少个字节，但树通常颠倒显示，“根”在图的顶部，“叶”在图的底部，如下所示您将在后续章节中看到相应的示例。

在比特币网络中，默克尔树用于汇总一个区块中的所有交易，同时生成整个交易集的数字指纹，为验证区块中是否存在某笔交易提供了一种高效的方式。 生成一棵完整的 Merkle 树需要递归地对一对节点进行哈希运算，并将新生成的哈希节点插入到 Merkle 树中，直到只剩下一个哈希节点，即 Merkle 树的根节点。 SHA256算法在比特币的Merkle树中使用了两次，所以它的密码哈希算法也被称为double-SHA256。

当N个数据元素被加密后插入到Merkle树中，你最多可以通过计算2*log~2~(N)次来检查任何一个数据元素是否在树中，这使得数据结构非常高效。

Merkle 树是自下而上构建的。 在下面的示例中，我们从构成 Merkle 树的叶子的四个事务 A、B、C 和 D 开始比特币的区块头有多少个字节，如图 9-2 所示。

图 9-2 统计 Merkle 树中的节点

所有的交易都不是存储在Merkle树中，而是对数据进行哈希处理，然后将哈希值存储在对应的叶子节点中。 这些叶子节点是H~A~、H~B~、H~C~和H~D~：

HA = SHA256(SHA256(交易A))

将相邻的两个叶子节点的哈希值拼接在一起进行哈希运算，然后将这一对叶子节点汇总为一个父节点。 比如创建父节点H~AB~，子节点A和子节点B的两个32字节的哈希值会被拼接成一个64字节的字符串。 然后对该字符串进行两次哈希处理以生成父节点的哈希值：

HAB = SHA256(SHA256(H~A~ + H~B~))

继续类似的操作，直到只剩下顶部的一个节点，即 Merkle 根。 生成的 32 字节哈希值存储在区块头中，汇总了四笔交易的所有数据。 图 9-2 显示了如何根据节点对的哈希值计算 Merkle 树的根。

因为 Merkle 树是二叉树，所以它需要偶数个叶节点。 如果只需要汇总奇数笔交易，则复制最后一笔交易，组成偶数个叶子节点。 这种叶子节点数为偶数的树也称为平衡树。 如图9-3所示，节点C被复制。

图9-3 复制一个数据元素可以实现偶数个数据元素

从四笔交易构建默克尔树的方法同样适用于从任意数量的交易构建默克尔树。 在比特币中，一个区块中有成百上千笔交易是很常见的，这些交易都会以相同的方式加起来，结果只有 32 字节的数据作为 Merkle 根。 在图 9-4 中，您会看到一棵由 16 个事务组成的树。 请注意，虽然图中的根节点看起来比所有叶节点都大，但它们实际上都是 32 字节的相同大小。 无论区块中是一笔交易还是十万笔交易，Merkle root 总是会将所有交易汇总到 32 字节中。

图 9-4 Merkle 树总结了很多数据元素

为了证明区块中存在特定交易，节点只需要计算log~2~(N)个32字节的哈希值，就可以形成从特定交易到区块根的认证路径或Merkle路径树。 随着交易数量的急剧增加，这样的计算极其重要，因为相对于交易数量的增长，以2为底的交易数量的对数增长会慢很多。 这使得比特币节点可以高效地生成 10 或 12 个哈希值（320~384 字节）的路径，以在一个巨大的字节大小的区块中从数千笔交易中证明交易的真实性。 存在。

在图 9-5 中，节点可以通过生成一条长度仅为 4 个 32 字节哈希值（共 128 字节）的 Merkle 路径来证明区块中存在交易 K。 该路径有 4 个哈希值（在图 9-5 中以蓝色标记）H~L~、H~IJ~、H~MNOP~ 和 H~ABCDEFGH~。 这4个哈希值生成的认证路径，再通过计算其他四对哈希值H~KL~、H~IJKL~、H~IJKLMNOP~和Merkle树根（图中虚线标示）图），任意节点均证明H~K~（图中绿色标注）包含在Merkle根中。

图9-5用于证明包含数据元素的merkle路径

示例 7-1 中的代码借用了 libbitcoin 库中的一些辅助程序来演示从叶节点哈希到根创建整个 Merkle 树的过程。

示例 9-1 构建 Merkle 树

代码/merkle.cpp[]

示例 9-2 显示了编译和运行上述代码的结果

\ # 编译merkle.cpp代码

$ g++ -o merkle merkle.cpp

$(pkg-config --cflags --libs libbitcoin)

\ # 运行 merkle 可执行文件

$ ./默克尔

当前的 merkle 哈希列表：

32650049a0418e4380db0af81788635d8b65424d397170b8499cdc28c4d27006

30861db96905c8dc8b99398ca1cd5bd5b84ac3264a4e1b3e65afa1bcee7540c4

当前的 merkle 哈希列表：

d47780c084bad3830bcdaf6eace035e4c6cbf646d103795d22104fb105014ba3

结果：d47780c084bad3830bcdaf6eace035e4c6cbf646d103795d22104fb105014ba3

随着交易规模的增大，Merkle 树的效率变得极其明显。 表 9-3 显示了需要转换为 Merkle 路径以证明区块中交易存在的数据量。

从表中可以看出，当区块大小从16笔交易（4KB）急剧增加到65535笔交易（16MB）时，证明交易存在的默克尔路径长度增长极其缓慢，仅从128字节增加到512字节. 使用 Merkle 树，节点可以只下载块头（80 字节/块），然后通过从全节点回溯一条小的 Merkle 路径来验证交易的存在，而无需存储或传输大块。 区块链中的大部分内容可能有几千兆字节的大小。 这种不需要维护完整区块链的节点也称为简单支付验证（SPV）节点。 它不需要下载整个区块来通过 Merkle 路径验证交易的存在。