“无奈”的中本聪与默克尔树的“冗余”

本文由保利企业团队制作

指导

数字货币本质上是一串可以无限复制的特殊字符串。 如果一个矿工暂时控制了50%以上的算力，他向交易所发起转账，同时将同一种数字货币转账给自己。 因为手头有足够的算力，所以这两笔交易都写入了区块，成为了合法交易。 这是一次“双花攻击”。

比特币网络自诞生以来一直稳定运行，事实证明：在没有结算中心的点对点网络中，点对点交易同样可以拒绝双花攻击。 所有比特币交易记录都存储在区块链上。 2008年，中本聪在描述比特币原型的论文中提到，他使用了默克尔树（Merkle Tree，简称MT）数据结构对每个区块中的所有交易进行了简要记录，默克尔树可以用更少的字节。

Merkle树的结构是一颗满二叉树，所以交易数必须是2n。 中本聪通过引入“无效但必要”的冗余信息解决了这个问题，代价是这些冗余信息可能被攻击者用来进行双花攻击。

本文首先介绍了Merkle树的基本结构和节点生成规则，然后通过实例说明了如何为比特币交易构建Merkle树，最后解释了比特币如何利用UTXO的唯一编号来避免Merkle的威胁树可能导致的双花。

知识点1：

哈希函数是数学家或密码学家精心设计的数学运算规则。 它可以输入任意长度的数据，而输出结果（即哈希值）的长度不变，满足：

1）单向运算：只能计算输入得到输出，不能逆向计算得到输入；

2）避免碰撞：不可能找到具有相同散列值的两个不同输入。

哈希函数可以说是区块链的核心技术之一，另外一个就是非对称加密。 正是这两个特性，保证了比特币像黄金一样难以获取，只有经过大量计算才能得到正确的哈希值，使得哈希值比其他字符串更珍贵，从而获得价值属性。 这就是哈希函数在比特币挖矿中的应用，但不是本文的重点。

知识点2：

Merkle 树也称为哈希树，因为在这种树状数据结构中，每个节点的标签（或值）是一串哈希值。 按照从左到右的顺序，将所有子节点的哈希拼接成一个新的长字符串，并将结果作为哈希函数的输入，计算得到父节点的标签。

哈希树的概念是以 Ralph Merkle 的名字命名的，他于 1979 年 9 月 5 日提交了专利注册申请。当然，到中本聪使用 Merkle 树作为比特币底层数据结构时，专利保护期间已经结束。 否则，中本聪将不得不向默克尔先生支付专利许可费。 这样做，他的身份可能会暴露，整个区块链行业都需要支付巨额费用。

此外，比特币也没有凭空创造出什么新技术，而是巧妙地利用了现有的几种密码学工具，结合之后，就成为了区块链一样前所未见的系统。 这种创新需要极强的系统性思维，一个人往往很难有这样的思维深度和广度。 有人猜测中本聪其实并不是他背后的人中本聪设计的比特币规则是中本聪设计的比特币规则是，而可能是一群密码学专家。

Merkle树的基本结构

言归正传，Merkle树是一棵满二叉树，其结构如图所示。

每个叶子节点的标签为其记录内容的哈希值，将两个兄弟节点的标签拼接起来作为哈希函数的输入，计算得到父节点的哈希，以此类推直到下一个节点，即根节点，也称为 Merkle 根。

中本聪设计了一种区块结构，其中区块头中的一个字段是 Merkle 树的根。 Merkle树的根来自记录在区块中的每一笔交易，交易可以理解为一次转账，比如类似于“A将一定数量的比特币转账给B”的格式。 将一条固定格式的转账记录序列化后，可以作为输入tx，提交给哈希函数运算，得到的结果就是叶节点的标签L。

L = 哈希(tx)

可以将每两个叶节点的哈希值拼接起来作为输入，得到父节点的哈希值P。

P = Hash(L0+L1) // '+' 表示串联

一个区块中可以记录的交易内容的长度是有限的。 在中本聪的设计中，一个区块中所有交易的总长度被严格限制在不超过 1MB。 交易的时间长短随着交易的复杂程度而变化。 可以简单理解为交易越复杂，内容越长。 为了有效地使用区块并赚取更多的手续费，矿工总是希望将尽可能多的交易记录到区块中。

观察Merkle树的结构可以发现，它始终是一棵满二叉树，也就是说叶子节点的个数始终是2n。 当要记录的交易数小于2n，或等于2n时，所有交易的总长度超过1MB的限制。 此时，一个区块中可以记录的交易数不可能恰好等于一棵满二叉树的叶子数。 当出现这种情况时，如何计算默克尔树的根呢？

中本聪如何为比特币交易构建 Merkle 树？

让我们用一个简单的例子来说明这个问题。

假设一个区块中一共记录了5笔交易，那么初始叶子节点只有5个。 每2个叶子节点生成一个父节点，但是在生成父节点的过程中，最后一个叶子节点没有兄弟节点，所以需要构造另一个节点与之匹配。 中本聪的方法是：直接重复节点本身作为其兄弟节点，然后按照前述方法获取父节点。 这个重复节点就是原始交易记录中没有的，但存在于 Merkle 树中的冗余信息。

这时Merkle树结构中出现了三个父节点，然后根据这三个节点继续构建父节点。 同样的问题又出现了，这一层只有3个节点，最后一个节点必须重复自己才能满足兄弟节点成对出现的要求，所以出现了新的冗余信息。 最后再上一层出现两个父节点，继续合并得到最后一个唯一节点，即根节点。

在交易数为5的情况下，由此构建的默克尔树结构如下图所示。

比特币如何避免

Merkle 树可能造成双花威胁？

中本聪的这种做法可能会让读者感到困惑：由于最后一个叶子节点会重复，从其父节点来看，它有两个哈希值相同的叶子节点。 根据哈希函数的防碰撞特性，可以判断出两个叶子节点所代表的内容完全相同。 也就是说，假设可以将一条相同的交易记录加入到区块中，Merkle树根的计算值保持不变。 这种做法不会导致双花攻击的问题吗？

比特币网络如何防止不诚实的节点故意在同一个区块中记录相同的两笔交易？ 这种混淆需要借助比特币交易的基本单位 UTXO 来解释。

在比特币网络中，没有“账户”这个概念，也没有“余额”这样的衍生概念。 因此，无法像传统银行系统那样通过查看账户余额来判断用户是否拥有可以继续消费的资产。 所有的比特币都以 UTXO（Unspend Transaction Output）的形式存在。 交易消耗已有的UTXO（称为输入，Input）并产生新的UTXO（称为输出，Output），被消耗的UTXO不再有效率。

每个 UTXO 都有一个锁定脚本（ScriptPubKey）来保护 UTXO 不被除其所有者之外的其他人使用。 目前，任何人都无法解锁不属于他们的 UTXO。 UTXO 可花费的前提是其锁定脚本被正确解锁。 通常，UTXO 的锁定脚本会指定所有者的公钥信息。 当UTXO被花费时，只有私钥与公钥匹配生成的数字签名，即解锁脚本（ScriptSig）才能成功解锁。 UTXO。

在比特币的设计中，交易ID和交易中UTXO的输出序列号作为UTXO的唯一标识，所有可用的UTXO都存储在一个称为UTXO集的数据集合中。

这意味着可以将每一个未被消费的 UTXO 存储在数据库中并向全网公开，并从数据库中销毁和删除已消费的 UTXO。 那么当攻击者故意构造第二笔交易并尝试再次花费同一个UTXO时，他会发现在数据库中找不到相同ID的UTXO。 这相当于有人花掉了他手中的真实实物货币后，就不能再使用了。

由于每笔UTXO都有唯一的标识，节点很容易判断一个区块中每笔交易消耗的UTXO是否相同：如果有两笔交易的输入是UTXO且ID相同，则可以判断第二笔交易无效，此区块无法被诚实节点验证。

因此，虽然Merkle树在理论上存在交易数不等于2n时哈希值重复的问题，但在实践中，已经不可能再伪造真实区块中内容相同的交易，而避免了双花问题。 .

接下来要看什么

当得到根节点后，区块头就可以用它来表示区块中包含的所有交易记录。 一个很直观的问题是，为什么默克尔树的根可以代表所有的交易，如何证明呢？ 笔者将在下一篇文章中讲解，如何验证一笔交易是否确实包含在某棵Merkle树下？ 为什么默克尔树是一种高效的数据结构？

注：以上图片来自Onchain

参考：

[1]比特币原论文Bitcoin: A Peer-to-Peer Electronic Cash System

[2] Merkle树原始专利文件