干货

对链式结构型 PoS 系统的 “虚假权益” 攻击(已更新)

Ajian   |     |   4568 次阅读

编者注:本文为 Decentralized Systems Lab 发表的讨论使用最长链规则的 PoS 系统安全性的文章。按照某种划分方法,PoS 系统可以分为链式结构型(chain-based)和拜占庭容错型(BFT-Style);文章所阐述的漏洞是是链式结构型系统中出现的,因此跟 Cosmos 的 Tendermint 这样的拜占庭容错型 PoS 共识算法无关;Casper 不使用最长链规则,而是 Latest Message Driven Ghost,因此也跟这里讲的漏洞无关。

本文由伊利诺伊大学厄巴纳-香槟分校(@ UIUC)的分布式系统实验室(Decentralized Systems Lab)发布。由 Sanket Kanjalkar(sanket1729smk7@illinois.edu) ,%20Yunqi)、Yuqi Li、Yuguang Chen、 Joseph Kuo 组成的学生研究团队在 Andrew Miller (socrates1024) 导师的带领下发现了一些会造成资源耗竭的漏洞,特撰此文作公开披露。这些漏洞已经影响了超过 26 类 PoS 型加密货币。通过这些漏洞,一个攻击者只需使用少量权益就能摧毁任何运行相关软件的网络节点。在这次公开披露之前,我们从 2018 年 10 月开始有规划地通知受影响的加密货币开发团队。大部分团队(根据市值计算)已经部署了应对措施。

权益证明(PoS)类加密货币,特别是那些基于链上 PoSv3(第三版权益证明)的加密货币,它们与比特币很相似,都使用未花费的交易输出(UTXO)模型和最长链共识规则。主要的区别在于前者用代币的所有权证明替代了工作量证明(PoW)。PoS 的潜在优点包括能够降低对环境的影响以及增强对 51% 攻击的抵抗性。很多加密货币实际上是比特币代码库的分叉(至少是衍生物)并且加入了 PoS 的功能。但是,由于它们盲目复制了比特币的一些设计理念,留下了安全隐患,因此出现了一些在原先代码库中并不存在的新漏洞

我们将这些漏洞称为“虚假权益”攻击。从本质上讲,该攻击之所以有效是因为 PoSv3 的程序在签发珍贵资源(硬盘和内存)之前对网络数据验证不足。因此,一个攻击者只需使用很少的权益份额(在某些情况下甚至是零份额),就能用虚假数据填满某个节点的硬盘和内存,致使其崩溃。我们认为所有基于 UTXO 和最长链原则的权益证明模型都容易受到这类“虚假权益”攻击的影响。经过调查研究,我们已经发现了一批存在漏洞的加密货币,并在文末附上了列表。

接下来,我们将详细解释这些漏洞和攻击手法,因为它们会产生一些不易察觉的后果。虽然事后看来这些漏洞本身很简单,但是想要一劳永逸地解决它们还是很困难,而且现有的解决方案可能会导致分叉(后文会给出解释)。

背景

在深入了解这些漏洞的细节之前,我们将简要介绍一些关于链上 PoS 机制原理的背景知识。

权益证明挖矿

与 PoW 挖矿类似,PoS 挖矿也要将区块头的哈希值(hash)与难度目标进行比较。PoS 的目标是确保每个权益者挖出下一个区块的概率与他们质押的代币量成正比。为了达成这一目标,链式结构型 PoS 机制的哈希值不仅取决于区块头,还取决于权益所有者通过区块中一笔特殊的 “coinstake” 交易所质押的代币数量。本文会涉及一些关于 PoS 挖矿的具体细节,更详细的解释可以在 Earlz 的博客中找到。本文重点从 1)coinstake 交易和 2)coinstake 交易所花费的 UTXO 这两方面来阐述 PoS 机制。

工作量证明在节约区块验证资源方面起到的作用

众所周知,PoW 在比特币共识机制中扮演至关重要的作用,不过它还有一个不那么受重视的作用,就是控制对节点有限资源的访问,例如磁盘、带宽、内存和 CPU 。在免许可型公链网络中,一个节点是不能信任其它对等节点的。因此,为了防止资源耗竭型攻击,比特币节点要先检查区块的工作量证明,再决定是否花费更多硬盘或内存资源存储这个区块。但是,事实表明,检查权益证明比起验证工作量证明要复杂的多,对环境也更为敏感。因此,许多链式结构 PoS 机制在有效验证上投入的资源严重不足。

为了理解资源耗竭型漏洞产生的原因,我们必须详细说明一下区块在被验证之前是如何存储的。一个节点不仅要追踪当前时刻最长的链,还要追踪一整棵分叉链树(因为任何一条分叉链都有可能成为最长链,在这种情况下,节点需要 “重组” 才能切换到新的最长链上)。举例来说,不当升级、双花攻击(例如:遭受 51% 攻击的 ETC ),或者临时网络分区都有可能引发这种情况。

验证这些非主链上的区块是非常困难的。要完全验证某个区块,你需要上一个区块中未花费的代币(UTXOs)集合。比特币保存的是最长链顶端区块时候的 UTXO 集合,但是不会保存之前区块时候的 UTXO 集合状态(尽管在此前任何一个区块上都有可能形成分叉)。在完全验证分叉链上的区块主要有两种方法:

  1. 将当前视图(UTXO 集合)“回滚” 到分叉起始点之前;
  2. 存储之前每一区块时候的 UTXO 状态。

(校对注:(在 UTXO 模型的区块链中)将一条链上的所有区块所包含的交易都处理完之后就会形成一个 UTXO 的集合,这个集合就是该链的最新状态。因此,哪怕在同一条链上, #100 区块时候的状态(UTXO 集合)与 #101 区块时候的状态也是不同的。上文的意思是,虽然每一个区块上都有可能形成分叉,但比特币软件不会把每一个区块时候的状态都专门保存一个副本,而是只保存最新的 UTXO 集合;若是每一个区块时候的状态都要专门保存,这会变成很大一笔存储开销。)

比特币的代码库不支持第二个方法,即使它支持,这也会增加额外的存储成本(比特币的节点性能依赖于大幅裁减不必要的数据)。比特币代码库目前正是采用第一种方法来处理重组的。然而,经常回滚的代价也是很昂贵的,因此,回滚和完全验证不会在一有分叉的时候就发生,而是等到分叉链上的工作量证明真的超过当前主链的时候才会进行。因此,当一个对等节点第一次接收到一个非最长链上的区块或区块头时,我们将跳过完全验证并将这个区块保存在本地存储区。

在将这个区块存储进磁盘之前,比特币代码库会基于 PoW 机制执行一些初步验证(不过会忽略区块内的交易)。初步验证仅针对之前的区块头以及当前的区块头,因此节点验证起来非常快。而且这是一个非常有效的防御手段,因为生成一个有效的工作量证明来通过这个初步验证成本很高。例如,虽然有可能欺骗一个比特币节点将一个非法区块存储在硬盘内,但是以这种方式发起资源耗竭型攻击是一个非常不经济的行为。

PoS 机制中也存在类似的初步验证过程,就是对 coinstake 交易进行验证,将它与上一个区块的 kernel 值一起进行哈希运算,看最后得到的哈希值是否超过难度目标。计算 coinstake 交易的哈希值很容易,难的是验证 coinstake 交易中输入的 UTXO 是否合法并且未被花费;但是要检查一笔 UTXO 是否没有被花费,你就需要该笔交易发生前一个区块时候的 UTXO 集合状态;如我们上文所说,节点往往是没有专门存储这样一个状态的。因为完全验证 coinstake 交易是非常困难的,大多数链上 PoS 机制提供的是一个经验式或者近似式的验证方法作为替代。事实证明这些替代性的验证方法通常并不充分并且存在漏洞。

漏洞 1 :“我简直不敢相信还有非权益持有者可以攻击的漏洞”

我们第一次研究这个漏洞的时候,发现 Qtum、Particl、Navcoin、HTMLcoin 和 Emercoin 这五种密码学货币都存在这个漏洞,即,在将区块提交至内存或硬盘之前,无法对 coinstake 交易进行验证。这五种加密货币的共同之处是它们都采用了比特币的 “区块头优先” 规则,将区块分成两类独立的信息——区块体和区块头——进行传播。只有当节点确认了某个区块的区块头通过了 PoW 验证、并且该区块跟在最长链(或更长链)之后,才会请求区块体的信息。由于 coinstake 交易仅存在于区块体而非区块头中,节点无法做到只验证区块头,于是直接将区块头存储在了内部数据结构(mapBlockIndex)里。因此,任何网络攻击者,即使不持有任何权益,也可以恶意填满一个节点的内存。

此种攻击的还有另一个形式,可以针对相同的代码库实施,不过它采用的方式略微不同,而且攻击目标也从节点的内存资源转向了硬盘资源。可以说,针对节点硬盘的攻击危害更大:如果节点因内存被填满而崩溃,只需简单重启即可恢复。但是,如果硬盘被填满了,则需要手动干预才能恢复(例如,运行一个外部脚本来清除硬盘中的过时区块)。

如果接收的不是区块头而是区块体,需要执行初步验证也会不同。理想情况下,因为 coinstake 交易就包含在区块体中,节点软件应该先对其进行验证,再将区块体提交至硬盘。但是,如上所述,如果这个区块是在一条分叉链上,节点要访问 coinstake 交易所花费的 UTXO 会难得多。也许是出于这个原因,这些代码库并没有验证 coinstake 交易。

对于存在上述任意一个漏洞的加密货币来说,即使是不持有任何权益的人也能对它们发动攻击。针对内存的资源耗竭型攻击微不足道,从技术的角度来看,我们更需要堤防的是针对硬盘的资源耗竭型攻击(尽管二者都是不需要持有任何权益就能发动的攻击)。如果你想了解更多详细信息,可以阅读一篇发表在 2019 年金融密码学学术会议上的简短论文

漏洞 2 以及权益重用攻击

通过跟踪这些代码库的历史版本,我们注意到漏洞 1 最初是在将比特币的 “区块头优先” 功能合并到 PoSv3 代码库时引入的。更早期版本的密码学货币(例如:peercoin)并不存在漏洞 1 ,因为在将区块存储到硬盘之前要先经过两项初步验证:

  1. 验证将要花费的输出是否存在于主链中;
  2. 验证 PoS 区块的 kernel 哈希值是否达到难度目标。

第一项验证是通过查找交易数据库(TxDB)来完成的。该数据库保存了当前主链上的所有交易。换句话说,初步验证确实有一定的效果,但是它相比完全验证仍然不够完整和严谨。如果你一直跟随着这篇文章的思路,你可能会立刻发现两个问题:

问题 A :第一项验证只能确保这个币是存在的,但是不能确保它对应的 UTXO 没有被花费过。由此引发了我们接下来要讨论的漏洞。

问题 B :即使我们验证的是一条分叉链上的区块,也会基于主链的 TxDB 来验证这个区块内的 coinstake 交易。

基于问题 A ,我们找到了一种能够骗过这些验证的方法,那就是使用一种更微妙的攻击手段,我们称之为 “权益重用攻击”。为了绕过第一项验证,我们会使用一个已花费输出冒充未花费输出骗过节点。通常,为了绕过第二项验证,我们需要挖出一个达到难度目标的有效区块,这种操作需要投入一大笔权益。但是,事实证明,我们可以通过滥用不完全验证来产生任意数量的 表观权益 (apparent stake)。我们将这种技术称为 “权益放大” 。

权益放大

要想使用少量权益达到攻击的目的,攻击者必须放大自己的表观权益量。表观权益指的是所有备用权益输出的总量,包括已花费的权益。假设一个攻击者一开始拥有 k 数额的 UTXO ,他可以发起多笔发送给自己的交易(造成自己所持权益量增加的假象),如下图所示。原本应该只有 UTXO*(n+1)* 能算作权益,但是根据上文的验证 2 ,从 1n+1 的 UTXO 都可以算入权益量之中,从而将表观权益量增加到了 n*k 。由于攻击者可以一直通过这种方式增加表观权益量,也就增加了他挖到 PoS 块的几率。“权益放大的步骤” 参见图左。

-权益放大和已权益重用攻击-

假设攻击者拥有的权益只占整个系统的 0.01% ,他只需要通过交易将这些权益反复发送给自己,5000 次后就可以获得 50% 的表观权益算力来挖取区块。攻击者累积得到大量表观权益之后,就可以使用这些 表观权益输出 从过去的某个时间点开始重新挖 PoS 区块。最终,如图右所示,被攻击节点的硬盘会被无效区块填满。举个例子,攻击者可以从交易所购买一些代币,通过上文提到的自交易放大自己的表观权益,然后将代币重新在交易所卖掉,之后就可以随时进行攻击。对于攻击者来说,攻击成本仅仅是交易手续费。

协同漏洞披露

我们首先针对密码学货币 Particl 和 Qtum 调查了关于漏洞 1 的情况 <1>。为了了解这个漏洞的危害程度,我们从 coinmarketcap.com(截至 2018 年 8 月 9 日)网站上筛选出了一些知名的 PoS 密码学货币,根据市值降序列了一张表。我们只研究了那些从比特币(或是从比特币中衍生出来的密码学货币)的 C++ 代码库中分叉出来的密码学货币。我们总共审查了 26 种密码学货币,其中只有 5 种(Qtum、Navcoin、HTMLcoin、Emercoin 以及 Particl)存在漏洞 1 ,剩余 21 种似乎不受该攻击的影响。为了确认漏洞 1 的危害程度,我们对那 5 种密码学货币进行了攻击。我们利用了比特币现有的测试组件,特别是支持模拟时间戳和快捷建块的 regtest 测试 ,以及一个(基于比特币测试框架)用 Python 编写的测试节点,该节点可以随着攻击者的攻击行为进行扩展。作为漏洞披露的一部分,我们使用 Docker 容器引擎将这些测试、它们的依赖包和特定 commit 的哈希值打包成了一个可再现工具包,以便分享给相关密码学货币的开发团队。

我们又进一步深挖了其余密码学货币能够抵御漏洞 1 攻击的原因,发现了同样严重且更为普遍的漏洞 2 (只需要少量权益)。在准备披露这两个漏洞的过程中,我们考虑到有些密码学货币流动性不强,开发团队的活跃度又较低,向他们披露这些漏洞可能会适得其反(其中一种风险是,如果存在漏洞的事情被泄露,在相关开发团队部署解决方案之前可能会造成用户的损失)。最终,我们(从市值在前 200 名的密码学货币中)选出了最可能受到攻击以及团队应对积极性最强(在 2018 年提交过一些 commit )的 15 种密码学货币,并与它们的开发团队进行了交流。

其中一个比较复杂的因素是,大多数团队的代码库都没有使用 regtest 测试模式,因此我们很难向他们演示攻击方式或是为针对每个密码学货币提供一个可再现工具包。因此,我们只能通过一个 C++ 版本的 stratisX 代码库进行演示 <7>。基于代码库的相似性,我们将存在漏洞的事告知了上述 15 支开发团队。其中有 5 支团队确认了漏洞的存在, 3 支团队还在调查中, 3 支团队认为漏洞的影响不大(并指出一些程序上的改动可以抵御其影响),还有 4 支团队尚未回复。对于那 4 支未回复的团队,我们通过他们网站上提供的渠道进行了联系 <5> <6>。我们在 这里 提供了两个漏洞的 Github 可再现工具包,这里 是我们关于漏洞 1 的一篇小论文。我们还将漏洞保存在了 CVE 上,将于近日公布。

解决措施

我们看到一些团队针对这些漏洞采取了一定的解决措施。一些密码学货币团队采取的措施是监测这类攻击并断开与攻击节点的连接 <2>。简单来说,节点会监测其他节点的异常行为(例如,发送大量区块头到分叉链上)。这种方案的问题在于很难将真的攻击行为与诚实节点的合法重组区分开来——存在误禁诚实节点的风险。截止到目前的情况来看,我们认为这类解决措施是合理的,但还是需要进一步调查。

另一些密码学货币团队采取的措施是增加一个部分验证机制,每积累一定数量的区块就会触发这个机制,使触发点以前的区块链不再接受分叉区块 <3>。如果节点接收到的分叉区块过于久远(即比最新的触发点要更为久远),节点是不会认可的,只会将它丢弃。例如,BCH (比特币现金)的 ABC 代码库就使用了这种方法,设置了深度为 10 个区块的滚动检查点。这种方法的缺点在于会造成 “链分裂” 的可能性。“链分裂”指的是诚实节点分散在主链的不同分叉链上。例如,在一个网络不佳的环境下,节点之间长时间不同步,产生了有冲突的检查点。即使节点重新上线,也无法对这条链达成共识。我们注意到,即使不采用这种方案,链分裂的问题也是存在的。再说回上文的问题 B ,由于 coinstake 交易是基于当前主链上的交易输出进行验证的,如果一个节点突然发现自己处在一条分叉链上,可能无法切换到真正的主链上。

链分裂的风险同样为恶意矿工创造了新的攻击手段。攻击者可以秘密挖取一条长链,并将它广播至部分节点,从而造成链分裂的情况。处于 IBD(初始块同步)状态的节点或者是长时间离线后重新同步的节点特别容易受到这样的攻击。这类攻击能够和 eclipse 攻击结合,将诚实节点引入由攻击者控制的分叉链中。

所有这些解决措施都能有效抵御虚假权益攻击,但是依旧无法代替完全验证。包括 Qtum 在内的一些密码学货币计划在未来的版本中对非主链区块实行完全验证。

我们建议所有这些存在漏洞的密码学货币的用户将自己的节点软件进行升级,打上最新的补丁,未升级的节点有可能遭受攻击,RAM 或者磁盘资源消耗过大,最终造成程序崩溃。

最终感想

虽然 “虚假权益” 攻击本质上很简单,但是突显了设计上的难点:将一些适用于工作量证明的思路挪用到权益证明中会引发安全性问题。鉴于在 PoSv3 密码学货币的代码与 Bitcoin Core 高度重合,我们认为应该更加重视代码检查。在调查这些漏洞的时候,我们在不同的项目代码库 <4>(或是一些被注释掉的代码)发现了一些解决措施和有针对性的防御措施。我们认为,这表明当前 PoS 项目的开发者们已经意识到了自己在设计过程中对于权衡关系和需求上考虑不足。难点在于,一方面,我们想要尽快抵御无效区块攻击,但是另一方面,我们不希望因此发生链分裂或是延迟的情况。在未来的研究中,我们依旧要思考如何找到一个系统化的解决方案。

尽管我们已经看到了至少两个代码库受到影响(例如,在 BTC 中的 CVE 2018–17144),但是据我们所知,这次协同安全漏洞披露涉及的密码学货币数量之多(20+),绝对是史无前例的。考虑到这些密码学货币的设计思路和代码库重合度较高,我们预计在未来会发现更多这样的漏洞。我们还发现这些代码库几乎没有统一的安全性处理。比如,大多数团队都没有专设安全联络人。类似我们这种协同漏洞披露是一种最佳做法,同时也对整个生态有益。


注 1:本漏洞背后的观念起于 2018 年夏天,当时 Andrew Miller 还在跟 Unit-E 开发者一起工作。感谢 Matteo Sumberaz 和 Gil Danziger 充满教益的探讨,以及 DTR Foundation 提供的奖金。

注 2:Emercoin 实现的一种启发式节点发现方法 https://github.com/emercoin/emercoin/commit/ec32762b99cc68fb9abb2909dda96bc7a13bd819

注 3:Qtum 中的滚动检查点 https://github.com/qtumproject/qtum/commit/8d208d0bee8449c1e4a3904ff3fc97ed26156648

注 4:一个 PoS 中的 ad-hoc 检查案例:https://github.com/peercoin/peercoin/blob/ebb4003ce8367501020181f7e734d52c4b1ab5ea/src/main.cpp#L2564

注 5:我们通过电子邮件以及 "发送备忘录" 功能联系上了一些团队

注 6:我们从 11 月开始多次通过网页上的联系功能联系 PIVX 团队。直到哦们写作本文期间才发现,PIVX 团队也启动了一个 hackerone 项目。而且我们也发现,直到今天,PIVX 网页上的 bug 悬赏页都没有列出这个 hackerone 项目。

注 7:注 7:StratisX 已经从有漏洞的 C++ 代码库迁移到了 C# 实现。


原文链接: https://medium.com/@dsl_uiuc/fake-stake-attacks-on-chain-based-proof-of-stake-cryptocurrencies-b8b05723f806
作者: Decentralized Systems Lab
翻译&校对: TrumanW, Whisker & 闵敏


你可能还会喜欢:

干货 | 探究以太坊 2.0 的分叉选择规则
引介 | 以太坊区块链的轻客户端入门
观点 | 组成比特币的三驾马车

 
0 人喜欢