双花攻击是大多数区块链系统中的主要安全问题之一，但除非对手具有强大的计算能力，否则很难成功发起攻击。在本文中介绍了一种新的攻击模型，该模型将双花攻击与Sybil攻击（女巫攻击）结合在一起。
0x01 Introduction
比特币是中本聪在2008年创建的第一个去中心化加密货币，它依赖于防篡改的公共分类账本，比特币的核心是区块链技术。区块链是一种分散的公共账本，包含加密、共识算法、点对点（P2P）等技术。由于区块链的隐私性和匿名性等安全特性，近年来许多研究人员致力于研究它。但是，区块链系统本身的安全性已成为重要问题。
双花是一种对区块链系统构成了巨大威胁的攻击。在开发通过互联网运行的加密货币时，这是一个主要的安全问题。在双花攻击中，攻击者可以设法多次使用相同的代币或令牌。比特币是第一个通过采用工作量证明（PoW）来成功解决双花问题的加密货币，工作量证明是矿工的节点通过挖矿竞争获得创建要添加到主链中的区块的能力。
通常，双花攻击的实现需要攻击者拥有大量计算能力。在本文中着重于通过结合比特币网络中的Sybil攻击，研究具有较低计算能力的攻击者如何增加双花攻击的可能性。研究表明，其他类型的攻击可以帮助增加成功的双花攻击的可能性。例如Bissias等指出日蚀攻击（Eclipse attack）可以提高双花攻击的效果[1,2]。Eyal的发现表明，合谋矿工还可以通过自私的采矿成功发动双花攻击[3]。 Gervais等认为网络等级攻击（network-level attack）和双花攻击的组合[4]。本文的攻击模型将双花与Sybil攻击结合在一起，以增加正确的块信息在区块链网络上的传播延迟。
0x02 Relevant Attacks and Related Work
A.双花攻击
双花攻击是对加密货币网络的潜在威胁。 例如在比特币中，攻击者创建了交易TXA，该交易从未花费的交易输出（UTXO）释放给商家。 TXA将被记录在主链中，诚实的矿工然后开始挖矿。在将TXA添加到主链中的新区块之前，攻击者会秘密挖掘自己的分支，该分支紧随当前最新的区块。然后，攻击者从同一UTXO创建另一个与TXA冲突的事务T XB，攻击者分支中包含的TXB将资金转移到攻击者的第二地址。一旦商家收到足够的针对TXA的冻结确认，便将货物发送给该攻击者。攻击者继续挖掘，一旦他使自己的链比主链长，攻击者便将自己的分支广播到网络。由于最长链规则，其他矿工最终同意了此攻击者的分支链，因此，将TXA替换为TXB。因此，攻击者同时获得商品和资金。
B.Sybil攻击
Sybil攻击以Sybil一书的主题命名，并在2002年由Microsoft研究的Brian Zill提出[5]。 一个敌对的对等方可以通过创建大量虚假身份来欺骗系统，从而破坏其信任和冗余机制，从而对区块链进行攻击。 2003年，Karlof和Wagner发现Sybil攻击是对作为分布式网络的无线传感器网络的潜在威胁[6]。从那以后Sybil攻击被许多研究人员证明是对P2P网络系统的巨大威胁。 Bissias等提出了一种名为Xim[7]的混合解决方案来防止这种攻击。 在[8]中，BitFury Group得出结论，在权益证明（POS）和工作量证明（PoW）区块链系统中Sybil攻击都可能成功。
C.长时延攻击（Long Delay Attack）
一些研究显示了区块传播延迟对比特币区块链系统的健壮性的影响。 Decker等证明信息传播延迟将导致区块链分叉[9]。在[10]中Kiayias等人发现了交易处理速度与区块链系统安全性之间的关系，并指出在整个网络传播时间较长的情况下，整个网络中拥有不到50％的计算能力的攻击者可能会对系统造成破坏。
在[11]中Garay等人提出了比特币骨干协议（Bitcoin backbone protocol），并在有界延迟模型中对该协议进行了分析。
D.先前工作的局限性
在[12]中Pass等人提到通过增加区块传播的延迟可以破坏区块链的一致性和链质量。但是他们没有详细说明如何实现较大的块传播延迟以及长时延攻击可带来多少双花攻击。
先前的研究在假设比特币网络完全同步的情况下研究了成功的双花攻击的可能性。实际上，比特币网络是异步的或部分同步的，并且块的传播具有延迟。在这种情况下，可能会发生由块传播延迟引起的区块链分叉。因此，在计算攻击成功的可能性时本文考虑了区块链分支。
许多论文讨论了如何计算成功的双花攻击的可能性。中本聪撰写的比特币白皮书首次提到了概率模型。他提出了有关概率模型的初步构想，后来被证明不太准确。 中本聪的错误是他认为挖掘每个块的时间间隔是固定的，因此，攻击者的随机过程在一定的时间段内创建了多个块，这是泊松分布。
Rosenfeld等其他研究人员并未将开采一个区块的时间视为平均时间，相反他推断挖掘块所花费的总时间为伽马分布，而攻击者的随机过程被证明为负二项式分布[13]。Grunspan类似地提出了一种特殊的证明过程，以证明攻击者挖掘的随机过程与负二项式分布是一致的[14]。但是先前工作的概率模型并不直接适合于本文提出的攻击，本文中使用的概率模型是根据Rosnefeld和Crunspan的概率模型进行修改的。
0x03 Information Dissemination in the Bitcoin Network
比特币采用gossip协议来传播交易和块信息，时间复杂度为O（log N）（N为节点总数）。由于gossip协议具有良好的容错性，某些比特币节点的崩溃或重启不会影响交易和区块信息的传播。因此，在一定的信息传播延迟范围内，比特币保证最终一致性，即所有节点最终将收敛到同一链。
比特币节点之间的通信方法基于gossip协议。接收到新块信息的每个节点都处于“infected”状态。他们首先检查新块的有效性，然后将inv消息发送到连接的邻居节点，以通知他们新块已准备就绪。接下来的getdata消息将由邻居节点发送。邻居节点请求inv消息发送方传播新的块信息。 inv消息发送方收到getdata消息后，他们将块信息发送到其邻居节点。这样一个完整的块请求和发送通信周期包含三个信息交换。在提出的攻击模型中，使用Sybil攻击来影响比特币节点之间的通信规则。关于通信规则的具体更改将在下一部分中介绍。
0x04 Proposed Double-Spending with a Sybil Attack
在本节中描述了用Sybil攻击进行双H花，将从攻击目标和攻击过程的角度解释这种攻击的工作方式。此外提出了假设的攻击模型。
A.攻击目标
毫无疑问，攻击者的最终目标是成功实现双花攻击。攻击者希望通过执行Sybil攻击来增加正确的块信息在比特币网络上的传播延迟。在假设的攻击环境中，比特币网络不是完全同步的。一旦新区块被挖掘并广播到整个网络，一些诚实节点将接收新区块信息并将最新区块添加到最长链（即主链）中。由于存在块传播延迟，因此剩余的诚实节点可能不会接收到新的块信息，因此会等待一段时间。假设块传播回合的上限时间为Δ，等待块信息的时间为d。如果d超过Δ，这些节点将开始新一轮的共识（即挖矿竞争），在这种情况下，将发生区块链分叉。攻击者的目标是最大程度地提高块传播延迟，以使其在每次块传播中都超过Δ。这样，不仅会减慢主链的增长，而且区块链分支也会造成诚实节点计算能力的浪费。因此与没有进行Sybil攻击的情况相比，攻击者的链长超过主链的可能性将大大增加，这为攻击者实现最终目标提供了许多优势。
B.攻击过程
首先，攻击者向比特币网络填充了多个虚假节点，这些虚假节点的虚假身份计算能力为零，称这些假节点为Sybil节点。利用这些带有假身份的Sybil节点，攻击者将发起双花攻击。攻击者向商家发起一个具有v值的交易TX0。然后，将TX0散布到其他节点。验证TX0之后，诚实节点将TX0放入其各自的内存池中，并争夺创建下一个块的权利。在将包括TX0的有效区块添加到主链之前，攻击者开始秘密创建一个由最新区块派生的私有链，并且他的链中的一个区块包含与TX0冲突的另一笔交易TX1，这笔交易向自己转移了一些资金。
之后，私有链与主链进行一次挖矿竞争。攻击者利用他的Sybil节点发起Sybil攻击，以延迟主链的增长率。请注意，这些Sybil节点仅影响区块链共识的传播速度，而不是参与区块挖掘。如上，时间复杂度为O(Δ)的算法1描述了一轮块传播期间Sybil攻击的过程。攻击中的块传播规则遵循第gossip协议。一旦Sybil节点接收到一个新开采的块，这些Sybil节点的每个假身份将向每个连接的诚实节点发送一条inv消息。接收inv消息的诚实节点将getdata消息发送到这些Sybil节点。这里的技巧是这些Sybil节点不会将新的块信息发送到这些诚实节点，因此，块传播的一部分是“frozen”。
同时，尚未收到阻止信息的诚实节点可以连续尝试将getdata消息发送给向其发送inv消息的节点。但是，由于每个Sybil节点拥有许多伪造的身份，诚实节点的大多数inv消息都来自这些伪造的身份，因此这些诚实节点仍可能不会接收到Δ中的新块信息。只要d超过Δ，这些诚实节点就必须停止等待并开始下一轮区块挖掘竞争。在另一方面，接收新块的节点将检查新块的有效性，然后将最长链延长一个。因此，在此区块高度上，持有不同区块链分类账的诚实节点（即区块链分叉）之间存在差异，这可能浪费诚实节点的计算能力。
尽管在Sybil节点的影响下区块链中会有一些分叉，但攻击者仍然旨在追赶最长的链。由于最长链的增长速度被延迟，因此攻击者可以积累延迟的优势，使其私有链比没有Sybil攻击的情况少回合，追上最长链，最后删除TX0，从而使TX1有效。
上图(a)-(c)描述了攻击过程中区块链的三种不同状态。仅描绘了主链和私有链，没有添加由Sybil攻击引起的其他分叉。第一种状态是，攻击者在将TX0发送给商家后开始在自己的分支上进行挖掘。第二种状态是商家等待TX0的z个块确认，而攻击者已经挖掘了k个块。当k小于z时，出现第三种状态。如果k大于z，则不存在第三种状态，攻击者在第二种状态下直接成功进行了所建议的攻击。在第三种状态下假设诚实的矿工在确定TX0之后开采了n个区块。 Sybil攻击会继续减慢主链中块的传播速度，直到攻击者伪造比主链长一倍的私有链为止。到那时，攻击者将在整个网络中广播自己的分支，并且由于私有链的长度较长，因此私有链很快将得到大多数矿工的共识。
C.攻击模型
对于Sybil攻击，假设攻击者部署了多个Sybil节点S，如上图所示。每个S（用红色表示）连接到两个诚实节点（用蓝色表示）。为了最大程度地增加块传播的延迟以使d超过Δ，每个S利用大量伪造的身份对连接的诚实节点进行欺诈，以确保将这些诚实节点的多个getdata消息发送给S，因此这些诚实节点无法及时从Δ中的其他诚实节点获取块信息。如图所示每个S通过其三个不同的身份与连接的诚实节点进行通信。请注意，每个Sybil节点的实际伪身份数量要大得多，并且不会影响以下部分的计算。
另一方面，由于S的计算能力为零，因此只有攻击者自己的节点才参与私有链的创建。假设攻击者的计算能力占网络总计算能力的q。因此，诚实的矿工在总计算能力中所占的比例为p=1-q。假设q<p并且每个诚实节点具有相同的计算能力，还假设攻击者节点和诚实节点的计算能力与其挖掘速度呈正相关。在攻击过程中，攻击者无法更改其计算能力或破坏PoW规则以加快其挖掘速度。相反，攻击者只是利用Sybil节点来影响块传播过程。下表表列出了此攻击模型的环境参数。
0x05 Conclution
在本文中，设计了一种新的组合攻击模型。通过引入Sybil攻击来影响比特币节点之间的通信协议（即gossip协议）来增加块传播延迟。研究了在Sybil攻击下成功进行双花攻击的可能性。研究取得了很好的结果，即只有比特币网络中32％的计算能力份额的攻击者可以成功地双花。成功攻击的可能性将在下一篇文章中给出，同时还有经济评估的结果。
Reference
[1] G. Bissias, B. N. Levine, A. P. Ozisik, and G. Andresen, “An analysis of attacks on blockchain consensus,” 2016, arXiv:1610.07985.
[2] E. Heilman, A. Kendler, A. Zohar, and S. Goldberg, “Eclipse attacks on bitcoin’s peer-to-peer network,” in Proc. USENIX Secur. Symp., 2015,pp. 129–144.
[3] I. Eyal and E. G. Sirer, “Majority is not enough: Bitcoin mining is vulnerable,”Commun. ACM, vol. 61, no. 7, pp. 95–102, 2018.
[4] A. Gervais, G. O. Karame, K. Wust, V. Glykantzis, H. Ritzdorf, and ¨S. Capkun, “On the security and performance of proof of work blockchains,” in Proc. ACM Special Interest Group Secur., Audit Control (SIGSAC) Conf. Comput. Commun.Secur., ACM, 2016, pp. 3–16.
[5] J. R. Douceur, “The sybil attack,” in Proc. Int. Workshop Peer-to-Peer Syst., Springer, 2002, pp. 251–260.
[6] C. Karlof and D. Wagner, “Secure routing in wireless sensor networks:Attacks and countermeasures,” in Proc. 1st IEEE Int. Workshop Sensor Netw. Protocols Appl., IEEE, 2003, pp. 113–127.
[7] G. Bissias, A. P. Ozisik, B. N. Levine, and M. Liberatore, “Sybil-resistant mixing for bitcoin,” in Proc. 13th Workshop Privacy Electron. Soc., ACM,2014, pp. 149–158.
[8] Proof of stake versus proof of work white paper, 2015. [Online]. Available:https://bitfury.com/content/downloads/pos-vs-pow-1.0.2.pdf
[9] C. Decker and R. Wattenhofer, “Information propagation in the bitcoin network,” in Proc. IEEE P2P, IEEE, 2013, pp. 1–10.
[10] A. Kiayias and G. Panagiotakos, “Speed-security tradeoffs in blockchain protocols,” IACR Cryptology ePrint Archive, vol. 2015, p. 1019, 2015.[Online].Available: https://eprint.iacr.org/2015/1019.pdf
[11] J. Garay, A. Kiayias, and N. Leonardos, “The bitcoin backbone protocol:Analysis and applications,” in Proc. Annu. Int. Conf. Theory Appl.Cryptographic Techn., Springer, 2015, pp. 281–310.
[12] R. Pass, L. Seeman, and A. Shelat, “Analysis of the blockchain protocol in asynchronous networks,” in Proc. Annu. Int. Conf. Theory Appl.Cryptographic Techn., Springer, 2017, pp. 643–673.
[13] M. Rosenfeld, “Analysis of hashrate-based double spending,” Preprint,2014, arXiv:1402.2009.
[14] C. Grunspan et al., “Double spend races,” J. Enterprising Culture (JEC),
vol. 21, no. 08, pp. 1–32, 2018.