攻击分析 — 从简易寄生链开始吧!

这篇文章需要对缠结有基本的认识,特别是几个核心的概念,包括:随机漫步、累积加权(以及他如何影响随机漫步)、参数α还有寄生链攻击。我们建议可以阅读IOTA白皮书,或者阅读一下关于α的Alon Gal的博客文章介绍文章。
双花的问题
IOTA跟第一代的分布式账本不同,IOTA是基于DAG(有向无环图directed acyclic graph)而不是区块链(blockchain)。这个创新的构架给了IOTA很多内存块链没有的好处,像是拥有非常强的扩容性、零矿工费。然而使用了新的方法管理分布式账本,也就必须要重新替一些基础的安全问题寻找解决方法。在这篇文章里面我们会讨论寄生链攻击。寄生链在IOTA的白皮书4.1章被提出,也是一个IOTA Foundation着重的研究题目。
寄生链式企图用下面的方法达到双花攻击:
攻击者偷偷的建了一个别人看不到的次缠结(sub-tangle)。我们会叫这个次缠结叫做「寄生链(parasite chain)」或者缩写成PC。在某一个时间点,这个攻击者已经发布出一个交易A到主缠结上,透过这个交易A跟商店买了东西。在买东西的这个时候,攻击者早已偷偷地放了一个跟交易A会有冲突的冲突交易(conflicting transaction),这个会起冲突的交易B,会把攻击者的钱从付款的帐号X移到另一个攻击者的帐号Y,而并非商店的帐号Z。也就透过这样完成了双花攻击。
因为这个在寄生链上的冲突交易一开始是被藏起来的,在商家接受了主缠结上的付款后,攻击者就会借着广播寄生链到公共网络上,去使原本付钱给商店的交易A无效。寄生链攻击是利用端点选择算法(tip selection algorithm)使大部分接下来新发出的交易都会认可(approve)寄生链上那笔双花的交易B。如果攻击成功的话,这个攻击会使之前正常的交易A变得无效,这样攻击者就等同从商店那边偷了商品,而且还对IOTA网络造成一些附带的伤害,所有认可正常的交易A的交易都会被认为是无效的交易。
为什么这个问题很难解决?
要以一个通用的方法分析寄生链是很难的,因为寄生链会以各形状、各种大小的方式出现。攻击者可以随自己的意去选择,有多少个在寄生链上的交易要去认可(approve)在主缠结上的交易,或者选择有哪些交易是攻击者想要自己寄生链上的交易去认可的,又或者是选一个对于寄生链最佳的落座位置去攻击整个主缠结。他可以是链,又或者是其他更有攻击效率的数据结构型态。上面提到的这些问题,提供攻击者很大的自由度去产生不同的类型的寄生链攻击。我们在这篇文章不会提到一个对于寄生链通用的分析,反之,我们会以简易寄生链(simple parasite chain)当作示例,我们简称这种寄生链叫做SPC。尽管简易寄生链十分的简单,但它还是拥有一些非常有趣而且惊人的性质。也因为它是最自然最基本的寄生链,所以我们就从这种寄生链开始讨论。
首先先让我们来定义简易寄生链:
一个简易寄生链上必须有一连串的交易,而这些交易必须
1. 认可接在简易寄生链,自己的前一笔交易。
2. 一个在主缠结上特别指定的交易,我们用r当作代号来代表这笔交易。

在简易寄生链上有一个交易是与主缠结上的交易有冲突的冲突交易。另外r的位置必须在双花交易的前面,如果没有在前面的话,整个寄生链会被认为是不合法的。下图就是我们根据上述条件所做出的图标。

这个简易寄生链上,红色的点是两个冲突交易。一个在主缠结上,一个在寄生链上。所有寄生链上的交易都直接认可交易r

如何估算攻击成功的时间点
我们会专注于下面这个数字:任意一个随机漫步者移动到简易寄生链末端交易(final transaction)的机率。如果大部分新进交易(incoming transactions)的随机漫步都会走到寄生链末端的话,这代表攻击者的攻击是十分有可能成功的。并且代表,在冲突发生的时候,在IOTA网络上的诚实结点(honest users)是偏好寄生链而并非主缠结(main tangle)。
我们(IOTA Foundation)用于估算这种攻击成功机率的方法就是使用模拟,在这模拟中我们会使用大量的随机漫步,并去计算到达简易寄生链的随机漫步者的数量。在我们把模拟结果呈现给各位看之前,我们必须强调一点,我们这边模拟出来走到寄生链的机率,跟攻击成功的机率并不一样。一个攻击若是能够成功,代表大部分新进的交易(incoming transactions)都必须认可(approve)简易寄生链上的交易,因此寄生链会变成主导的次缠结(sub-tangle)。
如果一个攻击造成任意的随机漫步最后会停在简易寄生链上的机率是10%,这个攻击成功的机率还是十分微小,只会造成10%合法但是接(attach)到简易寄生链上的交易变成孤儿交易(be orpahned),但是这不代表这10%交易的前会被偷走,只是代表他们接到不该接的地方,需要重新接上去(re-attach),不然交易不能被认可(approve)。寄生链攻击除非让新进的交易能够有超过50%的机率都接到寄生链上,不然寄生链攻击其实不会真的有威胁性。
结果
现在我们要来给大家看看,若是一个攻击者有非常大的哈希算力(hasing power)的情况下,我们模拟出来的数据。我们看到任意一个随机漫步者会跑到简易寄生链上的机率是一个α的函数。

任意一个随机漫步者会跑到简易寄生链上的机率是一个α的函数。若是在主缠结上有800个交易,并且在简易寄生链上有200个交易,代表说攻击者有全网的20%的哈希算力。

上图的数据中展示出这笔数据有区域最大值(local maximun)。这个结果让人有点稍稍的惊讶到,因为α越大会让新的交易更容易接到累积加权值较大的缠结上,可想而知累积加权值最大的缠结就是主缠结。就因为上述我们对于α的了解,我们原本预估我们会得到一个单调递减的机率函数。然而这个简单的图后来发现只是整个事情全貌的一角罢了。
这个机率分布告诉我们,在这边至少有两方竞争的势力。为了讨论这两方势力,让我们来明确指定在什么条件被符合后,随机漫步才会停在寄生链上。
条件一:随机漫步者必须通过交易r。
条件二:随机漫步者必须通过交易r,才能到达到寄生链上。
无庸置疑的,α越大会让条件二的机率下降,但是α越大会让条件一的机率上升。
这是因为寄生链的累积加权值会吸引随机漫步走到寄生链上。寄生链的吸引力随着α越大,也变得越大。在简易寄生链攻击的情境下,寄生链只有接在交易r上,因此造成,一方面如果累积加权值越大,随机漫步会越想要待在下图深灰色的区域;同时,随机漫步也必须往缠结的末端走。因为交易r是深灰色区域的末端,所以随机漫步者倾向于通过交易r。

简易寄生链的图标。深灰色的区域是被交易r参考到(直接认可或是间接认可过)的交易,并且这部分的交易都透过寄生链得到额外的累积加权值。

让我们回过头来继续讨论条件二状况下的机率。我们可以透过解析计算的方式(analytical calculation)去估算这种状况下的机率,下图是用一些示例参数的解析解所作图出来的结果。

条件二发生的机率以α为自变数所做出的图,总共有400个交易在主缠结上,100个交易在寄生链上。

上图是可视化以α为自变数的安全等级(随机漫步走到寄生链上的机率)函数。我们必须重申一次,这张图不是攻击成功的机率,只是条件二发生的机率。但不可置否的,这张图也是一个重要的安全指标。我们也可以对这个函数进行逆运算,这样就可以把安全等级当作自变数,输入需求的安全等级就可以得到这种状况下所需的α大小。
在下面这张热度图(heat map)是描述在不同的主缠结和寄生链大小下,为了达到安全等级p = 0.1的话,所需的α大小。

在p = 0.1的机率会让随机漫步走到简易寄生链上,对不同大小的简易寄生链和主缠结作出来的图。这张图在主缠结上交易数量多于寄生链上交易数量时才会正确。

总结

在本文中,我们探讨了简易寄生链攻击和一些和他相关的有趣特性。最重要的是,我们发现有一个能够抵抗这类攻击的α理想值,并且这是一个蛮有意义的结果(non-trivial result)。虽然简易寄生链可能不是一个达成双花最有效率的方法,但是它是一个很重要的基础。我们可以透过这个方法去找出α安全的底线,并且可以与之后更复杂的问题作模拟。在之后IOTA Foundation会释出一份关于缠结的安全报告,在这份报告中我们会提供更多模拟数据、公式、并且讨论我们使用的方法。