干货 | Long Range Attack

Ajian   |     |   971 次阅读

远程攻击:适应性工作量证明的严峻问题

编者按:这是 Vitalik 在2014年5月发布的博文,提出了远程攻击(Long-Range Attacks)的概念。

我们目前的工作量证明设计是基于区块链的工作量证明,这是我们第二次尝试构建保证不会给 CPU 造成负担并且长期来看是抗专用硬件(ASIC)挖矿的算法(编者按:即在长期挖矿的情况下,使用 ASIC 不能明显提高优势)。我们第一次尝试的是 Dagger,试图通过有向无环图构建一个计算时 memory-hard、验证时 memory-easy 的算法(译者按:即计算时会占用大量内存、验证时不会),从而进一步发展 Scrypt 等 memory-hard 算法的概念(从根本上来说是每个节点都有多个父节点的树)。我们目前的策略要严密得多:让工作量证明执行来自区块链的随机合约。由于以太坊采用的是图灵完备的脚本语言,能够执行以太坊脚本的 ASIC 从定义上来说是用于通用计算的 ASIC,也就是 CPU——技术宅一点来说就是“这是 memory-hard 算法,因此你没法并行处理太多指令”。当然还有“那么能否(对ASIC)进行特定优化,使得速度大大提升?”等问题,不过这些都是假以时日可以解决的小瑕疵。我们的解决方案很巧妙,因为它兼具经济实惠的特点:如果有人真的创建了一个 ASIC,那会激励其他人寻找该 ASIC 无法进行的计算类型并用这类合约充斥且污染区块链。不过遗憾的是,这类方案通常面临一个更大的障碍,从某种程度上来说还是一个根本障碍:远程攻击。

远程攻击的运行流程基本如下。在传统的51%攻击中,我先将100枚比特币存入一个全新的账户,再用这100枚比特币购买某个即时交付的数字商品(如莱特币)。我等待卖家交付(比方说要等到6次确认之后),之后我立即从100枚比特币的转让交易达成前的一个区块开始构建一条新的区块链,并且重新提交一份将这些比特币转回我的账户的交易。之后,我为自己的分叉链使用了超出剩余网络提供给主链的算力来挖矿,最后我的分叉链超越并取代了主链。结果是我将比特币和莱特币双双收入囊中。在远程攻击中,我开始制造分叉的地方不再提前6个区块,而可以提前60000个区块,甚至可以从创世块开始。

在比特币中,这种分叉是无效的,因为你只是在徒增赶上主链所需的时间。然而,这对基于区块链的工作量证明来说是一个严峻的问题。因为如果你直接从创世块开始制造分叉,尽管你的挖矿过程一开始会很缓慢,但在链接几百个区块之后就能够用很容易挖出的合约将这条区块链填满,而别人要想挖掘这些合约却难比登天。关于这类合约,有一则简单的例子:

i = 0

while sha3(i) != 0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f:

i = i + 1

你清楚地知道该合约在与哈希值匹配之前将经历整整一百万轮计算,那么你就可以立刻准确地计算出该合约在这一过程中将经历几个步骤、消耗多少gas,最后又会变为什么状态,然而其他人别无选择,只能实实在在地运行代码。实际上,要构建一个不经过实际运行就能在一般情况下检测出这类投机取巧的合约的机制是不可能的(此处可经由数学证明,而非凭空臆断),这既是这类方案的一个重要特性,也是停机问题的必然结果。因此,远程攻击者可以用这类合约填补分叉链,“挖掘”这类合约,明明走了捷径,却让网络相信他做了大量工作。因此,不出几日,我们的攻击者的挖矿速度就会是主链的数十亿倍,其长度很快就超越了主链。

要注意的是,上述攻击没有对算法的实际运行方式作出假设;而只是假设了有效区块产生的条件取决于区块链本身, 而且每单位算力在区块链上可以产生的影响力程度具有广泛的可变性。一种解决方案是人为抑制这种可变性;这需要通过一个哈希树计算堆栈追踪合约算法来实现,这样一来就无捷径可走了,因为即使你知道计算会在一百万步之后终止并产生一个输出值,你依然需要亲自运行一百万步来计算出所有中间的哈希值。然而,虽然这解决了远程攻击问题,但也导致了主要计算并非通用计算,而是计算出许许多多SHA3哈希值——使得算法再度易于受到专用硬件的影响。

权益证明

还有一种远程攻击是纯权益证明算法。在纯权益证明中, 假设在创世块产生之时或之后不久,攻击者持有代币总量的1%。之后,攻击者开始制造自己的分叉链并开始挖矿。虽然,攻击者在当时只有1%的概率被选中生产区块,他们轻易就能产生100倍数量的区块,以此创造出一条更长的区块链。我原本认为这是个根本问题,但它实际是可以变通解决的。例如,一种解决方案是注意每个区块必须有对应的时间戳,而且用户要抵制那些时间戳远远早于他们自己时间戳的链。这样一来,远程攻击就必须合乎相同的时间长度,但是由于它涉及的代币单位少得多,其得分也会低得多。另一种解决方案至少需要代币总量的一定百分比(如30%)为每个区块或是每第N个区块背书,这样绝对能抵御少于该百分比的代币量的一切攻击。我们自己的权益证明算法 Slasher 很容易就能更新成上述任一解决方案。

因此从长期看来,纯权益证明或混合工作量/权益证明似乎都是区块链的发展方向。在采用混合工作量/权益证明的情况下,人们很容易就能找到一个方案,利用权益证明来解决上述通过基于区块链的工作量证明解决的问题。对于 Ethereum 1.0,我们可能会采用权益证明,可能会是一种混合型方案,可能还是那套老掉牙的 SHA3 算法。我们明白 ASIC 不会有所发展,因为 Ethereum 2.0 到来在即,ASIC 的生产商会认为此举无利可图。然而,还有一大挑战尚未解决:分布式模型。欲知我的看法如何,敬请期待该系列的下一篇文章。


原文链接: https://blog.ethereum.org/2014/05/15/long-range-attacks-the-serious-problem-with-adaptive-proof-of-work/
作者: Vitalik Buterin
翻译&校对: 闵敏 & Elisa

本文由作者授权 EthFans 翻译及再出版。


你可能还会喜欢:

干货 | 以太坊 Casper FFG Overview
Casper机制的历史起源—第二篇
科普 | 区块链是什么鬼?

 
0 人喜欢