深入探讨区块链底层系统漏洞：双生树漏洞

越是面对久经考验的安全机制，实现时越应谨慎小心，因为系统往往十分依赖它们。

经过十余年发展，区块链逐渐得到了世界的关注，引发了一波又一波的区块链热潮，有人视之为信仰，有人预言其为第四次工业革命的核心，它的发展牵动着无数人的注意，甚至正在影响着我们这个世界的未来。

区块链技术之所以能够引起如此大的轰动，是因为他能够构建出传递价值的信任机器，也就是能够在去中心化场景下实现数据可信。这其中构建“数据可信”大坝的基石之一的，就是Merkle Tree (MT)算法，它通过二叉哈希树实现对交易信息的保护并提供低成本验证能力，只要Merkle Tree Root(MTR)不变，便可确信区块中的交易信息没有被篡改。

然而在现实生活中，不同区块链系统中MT的算法实现间通常存在差异，如果系统开发时没有‘手下留意’，那其中不经意掺入的某些细节便可能彻底改变MT算法性质，最终使区块链“数据可信”的大坝决堤。

在长期的区块链源码安全审计实战经验中，长亭区块链安全团队曾发现数个由Merkle Tree算法问题引起的0day逻辑漏洞，于是合并命名为双生树漏洞（CNVD-2020-66571）。

双生树漏洞类型定义

双生树漏洞

MT构建算法存在实现问题，使得可在改变源数据的同时保持MTR不变，即可对原叶子节点对应的数据进行修改，使得新MT与原MT拥有同一个MTR，从而导致区块交易信息篡改、链系统分叉等危害的漏洞。

通俗来讲，这类问题属于Hash Collision，给定一组原始数据和它对应的Hash值，攻击者可以通过某种方式构造出其他具有相同Hash值的数据组，相当于使Hash对原数据的完整性校验失效。

那么为了解释出现这种Collision的原因和方法，我们先看看正常情况下Merkle Tree Root的计算方法（熟悉MT的朋友可跳过）。

Merkle Tree 与区块链

在密码学与计算机科学中，梅根树(Merkle Tree)是一种树型数据结构，具有树的结构特点。其每个叶子节点中存放原始数据的哈希值（通过密码学中哈希函数计算得到的一种信息摘要），非叶子节点中存放其所有直接子节点拼接后的哈希值。

具体情形如图1所示（方便起见，本文均采用二叉树形式）：

可以看到所有原始数据DATABLOCK的Hash都在最下层的叶子节点中，通过将每相邻2个子节点的值拼接计算哈希得到父节点的值，逐层计算上去，最终得到一个根节点Top Hash，这个就称为梅克尔树根(Merkle Tree Root, MTR)。

Merkle Tree Root具有能够快速校验信息的特点，如图2所示，倘若敌手修改任一叶子节点的内容，将DATABLOCK2篡改成FAULTDATA，那么Hash0-1、Hash0就会将这种改变逐层向上传递，最终使MTR发生变化。因此只需验证MTR与预期一致，便可确信所有原始数据都没有被篡改过。

另外，在实际应用中，数据量往往很大，而需要验证的数据块相较之下非常小，因此利用MT结构，只需知晓从关心的数据块到根节点路径上每层兄弟节点的值，并检查MTR是否与预期一致，便可完成验证，无需下载全部数据，这样就可以提高效率，起到快速验证的作用。

Merkle Tree被广泛应用于数据对比以及完整性校验中。在区块链技术中，Merkle Tree通常被用于验证各区块中的交易在传输过程中的完整性。区块链中接受到新区块的节点会在交易列表基础上重新计算MTR，如果发现重构MTR与区块头中的MTR不一致，我们就可以断定该区块交易信息出现了传输出错或被恶意篡改。

双生树漏洞成因及发现过程

了解了Merkle Tree原理后，来聊聊漏洞。

先看一个实现案例：

<code>if hashList[i] > hashList[i+1] : hashList[p] = sha3(hashList[i]+hashList[i+1]) else: hashList[p] = sha3(hashList[i+1]+hashList[i])</code>

这是MT构造算法中计算每层父节点时的伪码，外层为循环，用来建立Merkle Tree。

此案例中 Merkle Tree 的实现方式与常见写法有些微差异，有差异就要有分析。

翻译一下代码逻辑（假设tx_hash数量为2的幂）：

1. 建立一棵完全二叉树，叶子数量与 tx_hash 数量一致
2. 将 tx_hash，按顺序放至叶子节点中
3. 计算每层父节点值时，比较其两孩子的 value，始终按序列大者靠前小者靠后，将两孩子拼接并计算Hash，得到的 Hash 值为该父节点的 value。如此往复直到建立 Merkle Tree，算得根节点的 value

举例如图3所示：

看到这里，很容易察觉到这里强制排序的操作有些不对劲，虽然粗看下似乎并不影响快速校验功能，但我们还是按习惯记录下来。而在审计研判阶段随着讨论深入，漏洞本质终于浮出水面，最终我们构造出完整利用手法并成功复现了攻击。

咱们前面讲过MTR的功能是保护交易信息，很多朋友都知道交易信息就是指每一条交易的数据，但除此之外，还有一类容易忽视的交易信息也受到MTR的保护。

咱们先看有名的BTC MTCopy漏洞CVE-2012-2459，在此漏洞中，当交易数量非2的幂次时，敌手可通过复制任意奇数层末节点构造碰撞，并利用BTC对此常规Error情况的不合理处理流程，造成网络分叉。在这个过程中，没有任何一条交易的数据被篡改，但依然构造出了同MTR不同区块的情况。

带着这个启发我们回到本例中，这里的MT算法也是很好的防止了交易数据的篡改，但由于构建算法中排序操作的存在，使得对某个信息的保护失效了。没错，就是交易顺序。

因此，事实上我们可以通过篡改交易顺序来构造双生树。

展开来讲，对于处在任意一对相邻的两兄弟节点交易，敌手可以随意交换他们的位置而保持MTR不变；更有甚者，攻击者可以交换MT任意非叶子节点下，以两个孩子为根的两颗树整体的位置，即直接交换两组交易的顺序，也依然不会改变MTR的值，于是这样理论上每个区块就能构造出许多 𝑂(2𝑛−1)个碰撞。举例如图4：

上图中虽然交易A、B和C、D分别交换了顺序，但因为他们客观的大小顺序不变，所以父节点E、F以及ROOT并不会因此而改变。

双生树漏洞利用方式及危害

[图片]

现在我们知道了这里存在漏洞，那么这个漏洞能造成危害吗？攻击者有没有可能利用这个漏洞对区块链系统造成实质伤害？

利用原理

The short answer is Yes. 简单来说，交易顺序的改变能够影响数据终态，所以自然可造成区块链数据性分叉，这是通用区块链系统可能出现的最坏状况。

下面通过举例说明的方式来提供一种可行的利用思路。

初始时敌手有3个账户(A, B, C)，余额分别为(5, 0, 0)，敌手签发两条正常交易：

• Tx1：A向B转账5
• Tx2：B向C转账5

两交易广播后，以先1后2的顺序被打包进了同一个合法区块中；

这两条交易执行完毕后(A, B, C)三账户的终态余额变为(0, 0, 5)。

但此时敌手可以利用双生树漏洞，调整区块中交易列表的顺序成为先Tx2后Tx1。Tx2执行时B账户余额尚为0，因此执行失败，而只有后面的Tx1执行成功。于是(A, B, C)账户终态余额会变为(0, 5, 0)，如下图：

对比两个执行顺序，可以看到顺序的调整的确改变了数据终态。

攻击流程

现在我们来捋顺一下敌手的攻击流程：

1. 发布上述两交易并持续监听新区块
2. 当观测到在某个区块中包含了这2条交易时，可按上述原理调整交易顺序，在不改变MTR的前提下交换两交易执行顺序，并将恶意区块继续广播到网络中。

如此一来，敌手便强迫网络形成了先接收原始区块的和先接收恶意区块的两类节点，他们以不同顺序执行完交易列表后，产生了对于账户余额状态的分歧。所以在这一步，敌手已经对区块链系统造成了实质性的分叉危害。

3. 从B或C账户发起转账交易
   • 敌手只需从B或C账户发起转账交易，即可以轻松完成悄无声息的双花攻击，细节不再赘述。

更危险的是，由于这种攻击并不影响共识，所以区块链系统依然可以正常运转，但也正因此，这些节点其实并没有能力观测到这种数据性分叉，就连攻击结束后大概率也浑然不知。随着双花或者分叉次数变多，网络将在一个较长时间段内被逐渐悄然分割成一个个小份，直到系统完全不可用。这种表现我们称之为静默分叉，静默分叉的特点是潜伏期长，破坏力强，且不可逆。

当然，上述过程中简化了一些技术细节，实际利用中由于receipt中status的存在，无法直接双花平台币，需要借助智能合约和一些构造技巧来完成攻击，但核心原理相同。

根据《国家区块链漏洞库漏洞定级细则》，静默分叉属于严重危害，无特殊利用门槛属于低难度，综合评定为高危漏洞。

不长的后记

检测及应对

双生树漏洞虽然危害严重，但只要及早发现并修复，即可最大程度避免损失。要检查是否受这类问题影响，需要对区块链系统代码中Merkle Tree Build部分逻辑进行分析，确保交易数据、交易顺序这两点信息都得到保障，无法构造MTR碰撞。

另一方面，需要培养开发团队的安全意识，加深对区块链技术中各项机制细节的理解，严格执行科学的代码发布流程，避免未经充分论证的修改。

尾声

双生树漏洞再一次提醒我们，在理解不深刻的情况下修改设计，或是实现不规范，即便是已证明安全的密码学等技术方案，亦有可能引入漏洞，造成严重后果。