之前在职期间审计项目时发现的漏洞，关于公链项目在审计底层merkle tree实现时产生的漏洞。对内容进行了一定的处理，不能介绍完整的攻击链。欢迎大佬们提提意见，看看思路如何。
长亭科技@区块链方向安全研究员 Sissel
前言
区块链项目态势汹涌，在经历了比特币、以太坊时代之后，大量拥有着不同特点与优势的公链项目如雨后春笋般层出不穷，吸引着人们的眼球。
这些项目既拥有区块链1.0、2.0时代中，数字货币交易、去中心化、支持智能合约的特征，也通过更加巧妙的共识机制、更复杂的技术和金融模型，来解决现有的种种问题，助区块链技术步入我们的生活。
在此期间，长亭科技区块链安全组也在关注着诸多公链项目，为这些公链项目的发展与上线保驾护航。在此前一项公链审计的项目过程中，我们发现了一个有意思的关于Merkle Tree底层实现漏洞。下面将分享发现该漏洞的前期技术积累，以及发现过程。
公链项目审计
回顾2018年，对于区块链安全从业人员而言，大部分人印象颇深的可能都是以太坊的诸多合约漏洞，EOS公链上层出不穷的合约问题。使用搜索引擎搜索，搜索和区块链相关的审计类文章，也大多为智能合约的check list、智能合约的审计分析等。针对公链审计类的技术分享并无很多。这里推荐大家一份长亭科技的《区块链安全生存指南》，其中介绍了当下区块链行业环境，以及近年来区块链业内的一些著名事件等。
审计区块链公链项目，与通常的软件代码审计略有不同。通常的代码审计，我们会考虑语言特性以及该语言的0day或1day漏洞，结合业务场景，分析代码的实现。区块链公链项目，其本身代码量较多，且无较为实用的审计工具。并且在项目背后，还有严谨的金融货币模型以及共识模型。依我理解，我们主要从以下方向入手：
- 语言特性及其已知漏洞
- 底层实现【密码学、序列化、大数运算等】
- 区块链基本元素的实现【区块、交易、链】
- 区块链行为的逻辑【生成一个区块、交易进入tx_pool等】
- 区块链的其他组件【p2p、rpc、钱包等】
- 共识算法合理性
- 金融模型合理性
- 历史公链漏洞
- 【待chief补充2333】
漏洞发现过程
我们在审计过程中发现的漏洞利用方式，源于该公链项目在实现Merkle Tree逻辑时，与常规实现方式有些许不同。在整理之前比特币区块链、以太坊区块链，出现过的漏洞时，发现了可能利用的漏洞点，经过确认发现可以影响不同节点间达成共识，进而造成分叉。
在发现问题后，长亭科技立刻汇报给公链项目方，公链开发者响应迅速，非常重视此次安全问题，即刻完成了修复。
什么是Merkle Tree
Merkle Tree，一般也称为Merkle Hash Tree。是数据结构中我们所了解的树，其各个节点均包含Hash值。Merkle Tree具有以下的特点。
- 它是一棵树，具有数据结构中，树结构的所有特点。【在讲解中我们默认其为二叉树】
- Merkle Tree的叶子节点中存放数据。非叶子节点的value，是由其左右两子节点，经过组合和Hash运算获得。
让我们举个例子来表示：
我们可以看到，只有叶子节点中存放了Data【Tx Hash】，而其上面每一个非叶子节点的value，都是他们孩子的value，经过组合和哈希运算得到的。
Merkle Tree被广泛应用于对比以及验证处理。在区块链技术中，Merkle Tree被用于验证各区块中的交易，在传输过程中是否被篡改，因为我们可以看到，倘若修改任一叶子节点的内容，这棵Merkle Tree的root节点的值【Merkle根】就会随之改变，可以通过判断Merkle根来得知，该区块中，有交易可能传输出错或被恶意篡改。
审计中发现的实现方式
核心代码【有修改】：1
2
3
4
5
6
7
8
9# 外层为循环，以建立Merkle Tree
if hashList[i+1] == None :
hashList[p] = sha3(hashList[i]+hashList[i])
else :
if hashList[i] > hashList[i+1] :
hashList[p] = sha3(hashList[i]+hashList[i+1])
else:
hashList[p] = sha3(hashList[i+1]+hashList[i])
在审计过程中，当考察到Merkle Tree底层实现方式时，发现其实现有一定违和感，具体如下：
- 先根据tx_hash数量，建立一棵完全二叉树
- 将tx_hash，按顺序放至叶子节点中
- 通过以下算法算得上层节点的Hash值：
- 对于某一非叶子节点，将其两孩子的value进行比较，序列大者靠前
- 将排好的两孩子，进行Hash运算，得到的Hash值为该节点的value
- 如此往复，建立Merkle Tree，算得根节点的value
举例说明：
初看此处时，觉得实现Merkle Tree的方式有些奇怪，进行了一次两孩子的value比较，但想到Merkle Tree的主要意义在于校验，防止篡改。实现方式略有不同可能影响不大，遂只做了记录。
Bitcoin漏洞 CVE-2012-2459
在整理曾经出现的公链漏洞时，发现了这样一个有名的比特币DoS漏洞。
通过了Merkle Root的根认证的区块，但其实并不合法。可能导致区块链分叉，或是进行双花攻击等，危害性较高，攻击方式较为简单，我们来分析该漏洞成因。
在旧版本的Bitcoin客户端中，其实现Merkle Tree的建立【计算该区块交易的Merkle根】的过程和通常的方式没有太大区别，当区块中交易个数为奇数时，会进行一个这样的操作：
在计算Merkle根时，若其叶子节点的个数为奇数个，则复制最后一笔交易的Hash值，参与建立Merkle Tree【并不是复制一笔交易出来，不能有重复的交易】。
看上去没有什么太大的问题，只是计算Merkle根时，对边界的处理。但CVE-2012-2459漏洞，利用的就是这一个特性。
区块A：
| tx_id | hash |
|---|---|
| 0 | 3d5c |
| 1 | e8aa |
| 2 | 7e7f |
攻击者首先选择,一个有奇数笔交易的区块，构造区块时，将最后一笔交易复制一份，加入该区块中。
区块B:
| tx_id | hash | 备注 |
|---|---|---|
| 0 | 3d5c | |
| 1 | e8aa | |
| 2 | 7e7f | |
| 3 | 7e7f | 重复的交易 |
区块A是一个正常的区块，区块B是拥有重复交易的区块。在共识过程中，会因为tx_3和tx_2一致，而造成出错并抛弃。但这两个区块根据上面的描述，对应的Merkle根是一致的。对应的区块头也是一致的。
攻击者可以构造同样的区块头，在传播广播区块时，广播不同交易列表的区块信息，造成不同节点面对这一区块不能达到共识，进而使区块链分叉，或是进行双花攻击等，危害极大。
漏洞利用方式
回到我们的审计过程中，类似上面的例子，思考在此项目中是否也会有类似的攻击手法。
我们发现，对于任意两笔相邻的交易，我们可以调换他们的位置，来使Merkle 根不变，更有甚者，我们可以交换任意一个节点下，两个孩子为根的树的位置，也不会改变Merkle 根的值。
经过对于其他部分对区块和交易的校验分析之后，我们发现可以通过构造两笔特定的交易，造成和上面比特币区块链类似的攻击效果。经过攻击链的设计和验证后，验证了此方法的可能性。此公链在运行过程中，有可能因此漏洞，被进行强制分叉或是双花攻击等。
总结
汇报该漏洞后，公链开发者十分重视这一问题，响应迅速，立刻修复了该实现问题。
在审计该项目的一些底层实现过程中，我们审计到这个较为经典的漏洞，并根据此漏洞，构造了一条完整的攻击链，达到了对公链强制分叉的影响。这也提醒了我们： 代码千万行，安全第一行。实现不规范，首席两行泪。 对于已证明安全的密码学方案或技术方案，若实现不规范，亦有可能成为漏洞，造成严重后果。
长亭科技区块链安全组，在区块链安全技术方面已有相当的积累，拥有多个区块链相关的CVE编号漏洞，曾进行过大量的公链审计、智能合约审计，提供许多企业级服务，并曾对优秀的公链社区提供了许多建设性意见。