区块链底层系统漏洞类型之-双生树漏洞

微信又改版了，为了我们能一直相见

你的加星和在看对我们非常重要

点击“长亭安全课堂”——主页右上角——设为星标🌟

期待与你的每次见面～

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

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

鉴于大部分已知漏洞已修复完成，现公开该漏洞类型技术细节以及发现过程。

双生树漏洞类型定义

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

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

Merkle Tree 与区块链

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

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

图1. Merkle Tree结构

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

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

图2. Merkle Tree对数据的完整性校验

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

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

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

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

先看一个实现案例：

if hashList[i] > hashList[i+1] :
    hashList
 = sha3(hashList[i]+hashList[i+1])
else:
    hashList
 = sha3(hashList[i+1]+hashList[i])

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

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

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

1. 建立一棵完全二叉树，叶子数量与 tx_hash 数量一致

2. 将 tx_hash，按顺序放至叶子节点中

3. 计算每层父节点值时，比较其两孩子的 value，始终按序列大者靠前小者靠后，将两孩子拼接并计算Hash，得到的 Hash 值为该父节点的 value。如此往复直到建立 Merkle Tree，算得根节点的 value

举例如图3所示：

图3. 案例中MT逻辑说明

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

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

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

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

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

图4. 双生树构造举例

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

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

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

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

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

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

不长的后记