实现数字货币双花攻击的多种方法

1. 工作量证明和双花攻击

2008年，中本聪提出了一种完全通过点对点技术实现的电子现金系统，它使得在线支付能够直接由一方发起并支付给另外一方，中间不需要通过任何的金融机构。虽然数字签名部分解决了这个问题，但是如果仍然需要第三方的支持才能防止双重支付的话，那么这种系统也就失去了存在的价值。比特币的工作量证明机制(PoW)的本质，就是要使现金系统在点对点的环境下运行，并防止双花攻击。

工作量证明机制的原理如下：网络中每一个区块都包含当前网络中的交易和上一个区块的区块头哈希。新区块产生，其区块头哈希必须满足工作量证明条件（需要进行大量的哈希计算）。整个网络将满足工作量证明的哈希链连接起来，从而形成区块链。除非攻击者重新完成全部的工作量证明，否则形成的交易记录将不可更改。最长的区块链不仅将作为被观察到的交易序列的证明，而且被看做是来自算力最大的群体的共识。只要整个网络中大多数算力都没有打算合作起来对全网进行攻击，那么诚实的节点将会生成最长的、超过攻击者的链条，从而实现对双花攻击的抵抗。

双花攻击实际上是一个结果。如果一个攻击者A将同一个比特币同时支付给B和C两个用户，并且B和C两个用户都认可了这笔交易。那么我们说A将该比特币花了两次，A实现了一次双花攻击。针对工作量证明机制的双花攻击中，51%攻击是被讨论的最多的一种攻击形式。但针对工作量证明机制的双花攻击实际上有多种形式，包括芬妮攻击、竞争攻击、Vector76攻击等。这些攻击实际上也得到了充分的关注和讨论，本文中不做赘述。实际上，实用的数字货币双花攻击还有很多种其他形式。下文中，我们将通过多个我们发现的多个安全漏洞，讨论多种数字货币双花攻击的多种原因，并提出一种高效减的缓措施。

2. 双花攻击的新分类

智能合约平台，本质上是要在全网共享一个账本。这可以看成是一个分布式状态机复制问题。当前的账本状态，我们可以认为是State_n。当一个新交易Tx_{n+1}产生的时候，Tx_{n+1}将对State_n产生一个作用。从而使State_n状态过渡到State_{n+1}状态。

这个过程我们可以 用公式表示：

State_n × Tx_{n+1}èState_{n+1}

智能合约平台共识机制，本质上是将所有的交易【Tx_1 Tx_2 ……. Tx_n】按顺序作用到初始State_0上，使全网始终保持相同的状态。区块链中的每一个区块，实际上将交易序列【Tx_1 Tx_2 ……. Tx_n】按顺序拆分成不同的区块 Block1{Tx_1,Tx_2},Block2{Tx_3,Tx_4}并按顺序链接起来。在全网状态机复制的过程中，如果一旦因为某些原因产生了全网状态不一致，则我们可以认为全网产生了一个分叉。分叉被攻击者利用，可进一步实现双花攻击。

本文中，我们将我们发现的这些双花攻击漏洞 分成3类：

1. 验证不严格造成的双花攻击。

2. 状态机State_n × Tx_{n+1}èState_{n+1}不一致执行造成的双花攻击。

3. 共识机制造成的双花攻击。

验证不严格造成的双花攻击，主要原因在于具体实现逻辑校验问题。比特币的漏洞CVE-2018-17144实际上就是这样一个漏洞。

状态机不一致执行造成的双花攻击，主要是由于智能合约虚拟机因为各种原因导致直接结果不一致，从而在整个网络中创造分叉，造成双花攻击。

共识机制漏洞可能产生整个网络的分叉，从而进一步造成双花攻击。人们常说的51%攻击，实际上就是PoW共识机制的分叉漏洞。

3、验证不严格造成的双花攻击

验证不严格造成的双花攻击，主要原因在于具体实现逻辑校验问题。这里我们介绍两个关于区块与交易绑定时校验不严格，从而产生双花攻击的漏洞。

在区块链项目中，一笔交易Tx_1被打包的某个区块Block_1中的方式如下：首先计算交易Tx_1的哈希值Hash_1，然后用Hash_1与其他交易的哈希值Hash_2…Hash_n组合构成Merkle Hash Tree。计算出哈希树的根节点root，然后将root打包到Block_1中。这样即形成一笔交易与区块的绑定。一般来讲，除非攻击者能够攻破哈希函数的抗碰撞性，否则无法打破一笔交易与区块的绑定。如果攻击者能够打包交易与区块的绑定，则攻击者能通过造成全网的分叉从而实现双花攻击。

下面我们介绍两个我们在NEO上发现的双花攻击漏洞：

3.1 NEO虚拟机GetInvocationScript双花攻击漏洞：

区块链项目中，一个交易一般是由未签名的部分（UnsignedTx，交易要执行的内容）和签名的部分（交易的witness）构成的。在如比特币之类的区块链项目中，交易的hash计算实际上是包含了该交易的签名部分的。而在如NEO、ONT等多种区块链平台中，交易的计算公式为hash=SHA256(UnsignedTx)。即交易的哈希是由未签名的部分计算的来的，与交易的witness无关。而NEO智能合约在执行的时候，能够通过Transaction_GetWitnesses方法，从一个交易中获得该交易的witnesses。其具体实现如下：

某个合约交易获得自己的witness之后，还能够通过Witness_GetVerificationScript方法获得该witness中的验证脚本。如果攻击者针对同一个未签名交易UnsignedTx1，可以构造两个不同的验证脚本。则可以造成该合约执行的不一致性。正常情况下，合约的VerificationScript是由合约的输入等信息决定的，攻击者无法构造不同的验证脚本并通过验证。但是我们发现在VerifyWitness方法中，当VerificationScript.length=0的时候，系统会调用EmitAppCall来执行目标脚本hash。

所以当VerificationScript=0，或者VerificationScript等于目标脚本的时候，均可满足witness验证条件。即攻击者可以对于同一个未签名的交易UnsignedTx_1，构造两个不同的VerificationScript。攻击者利用这个性质，可以对NEO智能合约上的所有代币资产进行双花攻击，其具体攻击场景如下：

步骤1： 攻击者构造智能合约交易Tx_1（未签名内容UnsignedTx_1,验证脚本为VerficationScript_1）。在UnsignedTx_1的合约执行中，合约判断自己的VerficationScript是否为VerficationScript_1。如果为VerficationScript_1，择发送代币给A用户。如果VerficationScript为空，则发送代币给B用户。

步骤2： Tx_1被打包到区块Block_1中。

步骤3:  攻击者收到Block_1后，将Tx_1替换成Tx_2(Tx_1具有与Tx_1相同的未签名内容UnsignedTx_1，但验证脚本为空)从而形成Block_2。攻击者将Block_1发送给A用户，将Block_2发送给B用户。

步骤4： 当A用户收到Block_1时，发现自己收到攻击者发送的代币。当B用户收到Block_2时，也会发现自己收到了攻击者发送的代币。双花攻击完成。

可见，该漏洞的利用门槛非常低，且可以对NEO智能合约上的所有代币资产进行双花攻击。危害非常严重。

3.2 NEO MerlkeTree绑定绕过造成交易双花攻击漏洞：

智能合约交易与区块的绑定，通常通过MerkleTree来完成。如果攻击者能绕过该绑定，则能实现对任意交易的双花。这里我们看看NEO的MerkleTree的实现如下：

在MerkleTreeNode函数中，NEO进行了MerkleTree叶节点到父节点的计算。但这里存在一个问题，当leaves.length为奇数n的时候。NEO的MerkleTree会将最后一个叶节点复制一次，加入到MerkleTree的计算中。也就是说当n为奇数时，以下两组交易的MerkleRoot值会相等：

【Tx_1 Tx_2 …… Tx_n】

【Tx_1 Tx_2 …… Tx_n Tx_{n+1}】其中 Tx_{n+1}= Tx_n

利用这个特性，攻击者可以实现对任意NEO资产的双花攻击。其具体攻击场景如下：

步骤1： 假设正常的一个合法Block_1，包含的交易列表为【Tx_1 Tx_2 … Tx_n】。攻击者收到Block_1后，将交易列表替换为【Tx_1 Tx_2 … Tx_n Tx_{n+1}】，形成 Block_2。然后将Block_2发布到网络中去。

步骤2： 一个普通节点收到Block_2后，会对Block_2的合法性进行校验。然而因为【Tx_1 Tx_2 … Tx_n Tx_{n+1}】与【Tx_1 Tx_2 … Tx_n】具有相同的MerkleRoot。所以Block_2能够通过区块合法性校验，从而进如区块持久化流程。NEO本地取消了普通节点对合法区块中交易的验证（信任几个共识节点）。则Tx_n交易可以被普通节点执行两次，双花攻击执行成功。

可见，该漏洞的利用门槛非常低，且可以对NEO上的所有资产进行双花攻击。危害非常严重。

4、虚拟机不一致性执行

智能合约平台共识机制，本质上是将所有的交易【Tx_1 Tx_2 ……. Tx_n】按顺序作用到初始State_0上，使全网始终保持相同的状态。在状态机复制过程中，我们要求State_n × Tx_{n+1}èState_{n+1}是决定性的。State_n × Tx_{n+1}èState_{n+1}实质上就是智能合约虚拟机对Tx_{n+1}的执行过程，如果智能合约虚拟机中存在设计或者实现漏洞，导致虚拟机不一致性执行（对相同的输入State_n 和Tx_{n+1}，输出State_{n+1}不一致）。则攻击者可以利用该问题在网络中产生分叉和并进行双花攻击。下面我们介绍多个EOS和NEO上我们发现的虚拟机不一致执行漏洞和其产生原因。

4.1 EOS虚拟机内存破坏RCE漏洞:

此前，文章《EOS Node Remote Code Execution Vulnerability --- EOS WASM Contract Function Table Array Out of Bound》。 url: http://blogs.360.cn/post/eos-node-remote-code-execution-vulnerability.html。在该文中，我们发现了一个EOS WASM虚拟机的一个内存越界写漏洞，针对该漏洞我们编写的利用程序可以成功利用该漏洞使EOS虚拟机执行任意指令，从而完全控制EOS所有出块和验证节点。

究其本质而言，是在State_n × Tx_{n+1}èState_{n+1}过程中。攻击者能让EOS虚拟机完全脱离原本执行路径，执行任意指令，自然可以完成双花攻击。其攻击流程如下：

步骤1： 攻击者构造能够实现RCE的恶意智能合约，并将该合约发布到EOS网络中。

步骤2： EOS超级节点解析到该合约后，触发漏洞，执行攻击者自定义的任意指令。

步骤3： 攻击者实现双花攻击。

该漏洞的危害非常严重，且是第一次智能合约平台受到远程代码执行攻击事件。读者可以阅读该文章了解相关细节，在此不再赘述。

4.2 EOS虚拟机内存未初始化造成双花攻击：

《EOS Node Remote Code Execution Vulnerability --- EOS WASM Contract Function Table Array Out of Bound》的利用程序的过程中，还利用了EOS中当时的一个未公开的内存未初始化漏洞。在内存破坏攻击中，内存未初始化漏洞通常能够造成信息泄露、类型混淆等进一步问题，从而辅助我们绕过如ASLR之类的现代二进制程序的缓解措施，进一步实现攻击。然而在智能合约虚拟机中，内存未初始化漏洞有更直接的利用方式，可以直接造成双花攻击。以下为我们在EOS RCE中利用的一个内存未初始化漏洞的细节，其可以被用来直接实现EOS智能合约代币资产双花攻击。

当WASM虚拟机通过grow_memory伪代码来申请内存新的内存。在EOS WASM grow_memory最初的实现中，未对申请到的内存进行清零操作。该块内存的空间实际上是随机的（依赖于合约执行机器的内存状态）。则攻击者可以构造恶意合约，实现对EOS上任意合约资产的双花攻击。其攻击流程如下：

步骤1：  攻击者构造恶意智能合约。合约中通过grow_memory获得一块新的内存地址。

步骤2： 合约中读取该地址中的某个bit内容。【此时该bit可能为0，也可能为1，依赖于合约执行机器的状态】。

步骤3： 合约判断该bit的内容，如果为1。则发送代币给A用户，如果为0，则发送代币给B用户。从而实现双花攻击。

4.3 EOS虚拟机内存越界读造成双花攻击:

在传统的内存破坏中，内存越界读漏洞主要将会导致信息泄露，从而辅助我们绕过如ASLR之类的现代二进制程序的缓解措施，进一步与其他漏洞一起实现攻击。然而在智能合约虚拟机中，内存越界读漏洞有更直接的利用方式，可以直接造成双花攻击。下面为一个我们发现的EOS内存越界读漏洞，我们可以利用该漏洞实现双花攻击。

当EOS WASM将一个offset转换内WASM内存地址时，其边界检查过程如下：

在这里|ptr|的类型实际上是一个I32类型，它可以是一个负数。那么当： -sizeof(T) < ptr < 0的时候，ptr+sizeof(T)是一个很小的数可以通过该边界检查。在之后的寻址中，我们看到代码：

T &base = (T)(getMemoryBaseAddress(mem)+ptr);

|base|的地址将会超过WASM的内存基址，从而让智能合约实现内存越界读【读到的内存地址内容取决于虚拟机当前执行状态，可被认为使随机的】。

攻击者可以利用该漏洞实现双花攻击。其攻击过程如下：

步骤1：  攻击者构造恶意智能合约。合约中利用内存越界读漏洞，读取超越WASM内存基址的某个bit。此时该bit可能为0，也可能为1，依赖于合约执行机器的状态】

步骤2： 合约判断该bit的内容，如果为1。则发送代币给A用户，如果为0，则发送代币给B用户。从而实现双花攻击。

4.4 标准函数实现不一致造成双花攻击：

总结上面双花攻击两个例子的本质，实际上是EOS合约在执行过程中因为某些内存漏洞原因读取到了随机变量，从而打破了原本虚拟机执行的一致性，造成了双花攻击。事实上，合约执行的不一致性，不一定完全依赖于随机性。这里我们介绍一个因为各个平台（版本）对标准C函数实现不一致造成的双花攻击。

在 C语言 标准定义中，memcmp函数的返回时被要求为：小于0，等于0，或者大于0。然而各种不同的C版本实现中，具体返回的可能不一样（但依然符合C标准）。攻击者可以利用该标准实现的不一致性，造成运行在不同系统上的EOS 虚拟机执行结果不一致，进而实现双花攻击。其攻击流程如下：

步骤1： 攻击者构造恶意智能合约，在合约中调用memcmp函数，并获取返回值。

步骤2： 此时，不同的平台和版本实现Memcmp的返回值不一致（即使EOS虚拟机的二进制代码是相同的）。恶意合约判断Memcmp的返回值，决定转账给A或B。从而完成双花。

该漏洞的具体修复如下：

EOS强制将memcmp的返回值转换为0，-1或者1，从而抵抗这种不一致执行。

Memcmp这个问题，是同一种语言对相同标准实现的不一致性造成的。事实上，同一个区块链项目经常会有多个不同版本语言的实现。不同语言对相同标准的实现通常也会有偏差，比如一个我们发现的因标准定义实现不一致造成不一致执行是ECDSA函数。ECDSA签名标准中要求私钥x不为0。如 python 、JS中的多个密码学库中对该标准由严格执行，但是我们发现部分golang的ECDSA库允许私钥x=0进行签名和验证计算，恶意攻击者利用该问题可以对同一个区块链平台的不同版本实现（比如golang实现和python实现）构造不一致执行恶意合约，从而进一步完成双花攻击。

4.5版本实现不一致造成双花攻击：

同一个区块链项目经常会有多个不同版本编程语言的实现。不同编程语言的实现同样存在着各种这样的不一致执行的可能性。上面ECDSA是一个例子。大整数运算也是一个常见的例子。比如在曾经的NEO的C#版本实现和python版本实现中，大整数(BigInteger)除法运算可导致不同编程语言实现版本见的不一致执行现象，从而造成双花攻击。类似的现象在多个区块链项目中产生过。

4.6其他问题不一致性问题

系统时间、随机数、浮点数计算等因素也是可以造成虚拟机不一致执行的原因。但是在我们的审计中，并没有发现此类漏洞在大公链项目中出现。多数区块链项目在设计之初就会考虑到这些明显可能造成的问题。

但可能造成不一致执行的因素可能远远超过我们上面发现的这些问题。事实上，一些主观因素（取决于机器当前运行状态的因素，我们称之为主观因素）都可能造成虚拟机的不一致执行。举个例子，比如在4G内存，8G内存的机器在执行过程中产生内存溢出(OOM)的主观边界就不一样，攻击者利用OOM可能造成虚拟机的不一致执行。

5、共识机制造成的双花攻击

共识机制造成的双花攻击实际上是在业界中获得充分讨论的一个问题，然而各种公链方案在共识机制实现上仍然可能存在分叉问题，从而造成双花攻击。

5.1 ONT vBFT VRF随机数绕过漏洞

Long range attack 是目前所有PoS共识机制都面临的一种分叉攻击方法。攻击者可以选择不去分叉现有的链，而实回到某个很久之前的链状态（攻击者在这个状态曾占有大量货币），造一跳更长的新链出来让网络误以为是主链，从而完成双花。目前业界针对Long range attack并没有根本的解决办法，只能保证在“Weak Subjectivity”不发生的情况下，防止分叉发生。

ONT的vBFT共识算法提出了一种依靠可验证随机函数（VRF）来防止恶意分叉扩展的方法。网络首先基于VRF在共识网络中依次选择出一轮共识的备选区块提案节点集，区块验证节点集和区块确认节点集，然后由选出的节点集完成共识。由于每个区块都是由VRF确定节点的优先级顺序的，对于恶意产生的分叉，攻击者很难持续维持自己的高优先级（如果攻击者没有控制绝大多数股权的话），因此恶意产生的分叉将很快消亡，从而使vBFT拥有快速的状态终局性。

然而我们发现vBFT中的VRF实现存在一个漏洞，导致私钥为0的用户的可对任意区块数据生成相同的vrfValue。具体的，vBFT中的vrf是对由波士顿大学提出的VRF标准草稿：https://hdl.handle.net/2144/29225 的一个实现。具体在该草案的5.1和5.2章节中，我们可以看到证明生成，和随机数计算的算法。如图：

漏洞在于x=0时候，此时从计算上 y仍然为一个合法的公钥，且能通过vBFT实现中ValidatePublicKey的校验。gamma为椭圆曲线上固定的点（无穷远点）。即对任意输入alpha，该vrf产生的值为固定一个值。完全没有随机性。该问题可导致攻击者利用固定vrf破坏共识算法随机性，从而长期控制节点选举。

5.2 NEO dBFT共识分叉

NEO的dBFT共识机制，本质上可以看成是一个POS+pBFT方案。在原版NEO代码中，我们发现NEO和ONT在实现其dBFT共识机制的时候存在分叉问题。恶意的共识节点可以产生一个分叉块，从而造成双花的发生。具体细节可以参考文章：《Analysis and Improvement of NEO’s dBFT Consensus Mechanism》http://blogs.360.cn/post/NEO_dBFT_en.html，在此我们不做赘述。

6. 一种针对虚拟机执行不一致双花问题的高效减缓措施

对于校验绕过之类的逻辑漏洞和共识机制问题产生的双花漏洞，还是需要深入到业务逻辑中具体问题具体分析。这里我们提出一种针对虚拟机执行不一致的减缓措施。

一种简单的解决虚拟机执行不一致造成的双花问题的方法是由出块者将运行完交易后的全局状态State_{n+1}进行哈希散列，然后将该散列打包到区块中。普通节点在收到区块后，将本地运行完交易后的状态State’_{n+1}的哈希散列与State_{n+1}的哈希散列进行对比。如果相等，则说明没有分叉产生。然而由于本地数据是先行增长的，所以每次对全局状态进行散列计算的开销极大。针对这个问题，以太坊使用了MekleTree的结构来提高性能，同时应对分叉回滚问题。但以太坊的方案并不适用于采用其他数据结构存储状态信息的区块链项目。这里我们提出一种新的解决方案，其工作流程如下：

1. 区块生产者在区块打包阶段，将该区块中所有的交易运行过程中的对数据库的写操作序列【write_db_1 write_db_2 …. write_db_n】记录下来，并计算该序列的哈希值write_db_hash。

2. 普通节点收到新的区块后，对区块进行校验。然后在虚拟机中执行交易。同时本地记录这些交易对数据库的写操作序列【write_db_1’ write_db_2’ …. write_db_n’】，然后计算write_db_hash’。判断其与write_db_hash是否相等。如果相等，则认为没有不一致执行发生。如果不等，则拒绝对该写操作序列进行commit。

本方法的核心思路在于，智能合约平台虚拟机执行不一致产生的原因在于：合约中各种功能函数和图灵完备性的支持中，可能引入多种不确定因素，从而造成执行不一致。各种各样复杂的小原因，可能导致这种不一致执行防不胜防。但是我们退一步看，双花攻击的本质是要对全局状态State_{n+1}进行修改，本质上就是一系列的简单写操作（简单的写操作往往并不会产生二义性）。要防止双花，只需要对所有的写操作序列进行匹配校验便可。本地对这些写操作进行匹配和记录的开销非常小，同时本地记录这些写操作序列，也方便应对分叉回滚等其他因素。