笔记作者: enzey
原文作者: Charlie Hou; Mingxun Zhou;
原文标题: SquirRL: Automating Attack Analysis on Blockchain Incentive Mechanisms with Deep Reinforcement Learning
发表会议: NDSS 2021
原文地址: https://arxiv.org/pdf/1912.01798.pdf
激励机制是无许可区块链的核心,它可以激励参与者参与以保证共识协议的安全,然而设计激励机制是非常困难的。即使是在传统背景下具有强大理论安全保障的系统,用户也要么是拜占庭式要么是诚实的,缺少对理性用户的分析。而理性用户会利用激励去偏离诚实行为,因此,大多数今天的公链使用激励机制的安全性缺乏深入分析且未经测试。
本文提出了SquirRL,它使用深度强化学习去识别区块链激励机制下的攻击策略,使用较短步骤,方法在BitCoin协议上复现了其著名的理论结果。另外,在更复杂的场景下,即当矿工的挖矿算力随时间改变的场景,SquirRL也比目前其他论文更好的识别攻击策略。最后,SquirRL发现针对比特币的传统自私挖矿攻击在多个攻击者场景下是无效的。这些结果阐明了为什么迄今为止在网络里还未发现的自私挖掘可能是一种糟糕的攻击策略。
区块链在过去的数十年内以去中心化信任的特性存储和处理数据的能力让人兴奋。区块链计算模型需要参与者消耗资源(存储资源,计算资源,电力资源)去确保其他用户数据的正确性。这些代价是巨大的,因此大多数公链依赖于激励机制去刺激用户参与区块链共识协议。公共区块链里激励机制是非常重要的。用户通常会被奖励因为参与维护彼此的数据。一个例子就是Bitcoin的共识协议,它需要参与者(矿工)建立连续的数据去看,每个区块都需要完成巨大的计算代价后才能形成。为了激励用户,在自己挖的区块获得网络的认可后,Bitcoin矿工会收到奖励。矿工也会因为打包到区块的交易收到交易费。这样做是为了防止矿工的区块没有被认可的情况下自己白白消耗了资源而没有获得奖励。这样的整个奖励机制极大地增加了BitCoin的参与用户数目。无许可区块链系统里一般都有自己的一套激励机制,虽然大多数模仿Bitcoin,但是因为共识协议的不同,其激励机制还是有所差异。
激励机制很容易受到攻击者博弈的影响,self mining是一个针对Bitcoin激励机制的著名攻击手段,它允许一个矿工通过不完全遵循共识协议来获得超过它在正常情况下获得的区块奖励。目前,对区块链激励机制的攻击通常是通过漫长的建模和理论分析过程发现的,在这个领域里获得一个大家都能接受的结果是很困难的。由于许多加密货币缺乏基本分析,所以绝大多数区块链激励机制根本没有被分析过。因此,目前存在于加密货币中的大量资金可能容易受到未知攻击。
在本文里,我们提出了名为SquirRL的方法,它可被区块链开发者用作测试激励机制漏洞。但是它不提供理论上的保证:他不能发现攻击并不代表诚实行为是主导的策略。我们在实际中发现,方法在识别对手策略上是有效的,这只能证明激励机制是不安全的。我们的贡献有三点:
目前,发现区块链激励机制攻击仍然是手动且极其耗时的。针对这些系统的博弈分析是很困难的,因为博弈是重复的,有多个参与方且状态空间巨大。事实上,现有的很多分析都集中在只有一两个不诚实挖矿的agent的场景上。
我们想让协议设计者使用我们的框架去研究攻击模型和实验的自然过渡以解决激励机制的关键安全和激励一致性问题,如下表所示。
解决上表里问题的一个首选方法是Markov Decision Processes(MDPs),MDP solvers通常被用于在一个已知但随机的环境里学习最大化一个agent的奖励的策略。在前人的工作里,针对Bitcoin协议的双agent场景,MDP solvers已经被有效地利用去计算最优的对抗策略。
MDPs由四元组组成,其中代表有效的状态集合,代表一个agent可以采取的动作集合,代表概率转移矩阵,代表奖励矩阵。MDPs依赖于马尔可夫假设,即状态间的概率分布只依赖于先前状态以及每个时间步长采取的行动。此外,MDPs需要知道状态转移矩阵。基于这样的假设,MDP的目标在于找到一个最优的策略去最大化长期奖励。但是由于下列两个原因,MDP solvers无法解决我们的问题。
强化学习是一类在某个环境里让agent学习到最大化自己累计收益的机器学习算法。深度强化学习是一种使用神经网络学习策略的强化学习,通常不需要明确指定系统的动态性。深度强化学习可以很好地解决具有两类特征的问题,其一是规则被很好地定义,其二是状态空间极大。在区块链中,参与者添加到账本中的每一个区块通常都会获得奖励,这让参与者能够事先评估自己的奖励,通过提供更快地反馈,更容易训练出自动系统去学习出有效的策略。因此深度强化学习适合解决我们的问题。
下图展示了SquirRL框架图,这个框架包括针对激励机制的一个发现和分析对抗策略的三个管道。首先,协议设计者建立环境,模拟激励机制的执行,协议设计者在环境中实例化将状态表示,以及agent可能采取的动作空间。第二步,协议设计者将选择攻击者模型。第三步,协议设计者将根据环境和攻击者模型去选择RL算法,协议设计者将奖励函数和超参数和RL算法关联起来。
本文重点研究POW系统下的self-mining攻击。我们的技术还可以推广到非POW系统,以及其他类型的攻击。在本文里还研究了block withholding攻击。
我们将区块生成作为一个连续时间过程,每个时间间隔内都会生成一个区块。一个控制着网络哈希算力的参与者会以的概率挖掘出第i个区块。我们建模诚实节点遵守最长链协议,即每次诚实节点生成一个区块的时候,会选择把区块加入到最长有效链上。如果出现有多个链长度相同的情况(比如攻击者产生一个区块去使得某一条链和最长链长度相同),那么假设诚实节点以的概率将自己的区块加入到攻击者的最长链上,以的概率加入到诚实节点的最长链上。
我们考虑一个或多个攻击者在有限计算资源下最大化区块奖励,忽略交易费用。定义和分别作为攻击者和诚实矿工在时刻使用攻击策略后的奖励。我们通过汇总区块奖励去计算矿工的奖励,从而避免分析不受控制的外力,如硬币价格或电力成本。现实中,矿工往往会去优化absolute reward rate,即,而以前的工作认为矿工会优化relative rewards,这定义为自己的奖励和网络里总奖励的占比。本文认为,这两个指标在合适的时间段内是可以互换的,给出了Proposition IV.1,并在附录里给出了证明。此外这里还有两点需要注意,其一是我们的系统必须在所有的agent都承认这个区块以后才会给出区块奖励。其二是在一些协议的实验里,我们考虑了一些额外的参数去更具体地描述了实际环境。
本文定义了矿工可以采取4个基本的动作:
环境状态空间都来自于引文50,我们研究的所有协议都类似Bitcoin协议。定义三元组标记着攻击者在时刻下的状态,标记着攻击者在自己分支下拥有的区块数目,是最长公链的长度,是forking特征。状态代表着前一个时刻的状态是,而·代表任意值。我们定义为分支的上限长度,在实验里设置为20。 意味着前一个状态是,在这个情况下无法执行match动作。当的时候,意味着攻击者处于分支竞争条件。
在实验的动作序列设计里,给出两条性质:1.同步动作选择:我们假设在看到诚实agent(如果它存在的话)的行动之后,agent的所有动作都被同步记录下来。2.adopt的延迟执行:一旦动作被记录,就以相同顺序使用他们,选择总是在最后应用adopt动作。
每个agent的类型由它的哈希算力决定,每个agent的类型还包括两个参数,即和
在单agent场景下使用Deep Dueling Q-Networks(DDQN),在多agent场景下使用PProximal Policy Optimization(PPO)。
使用OpenAI Gym去构建我们的环境并执行RL算法。环境代表了区块链共识机制和块奖励结构的组合,我们所实现的环境为用户提供了一个模板,可以方便地实例化他们自己的区块链协议。我们不断改变参数如哈希算力,agent种类。本文架构支持了多个RL算法如DQN PPO A2C和policy gradient。不同的agent可以初始化不同的RL算法,本文最后发现DDQN和PPO的效果最好。
单个agent场景下,只有一个攻击者,而剩下的agent都是诚实的。使用这样的设置去研究Bitcoin,Ethereum和GHOST平台。本部分的实验比较了几个基础挖矿策略:
在每次实验里,针对一个给定的参数设置,为每个区块链协议进行100次实验,每次实验在主链上涉及10000次状态转移以及至少5000个区块。我们计算每次实验的相对奖励,取平均值。
这部分的实验是为了复现引文50的两个重要发现:
图3描述了实验结果,首先当哈希算力小于0.25(即百分之25)的时候,不会进行自私挖掘。当大于0.25的时候,我们发现SquirRL在真正最优策略的1%偏差范围内获得了相对奖励。
GHOST的状态空间比Bitcoin更大,在实验里,假设奖励只给在最长链上的区块。对GHOST的建模和Bitcoin有两个区别。
本部分的实验在量化MDP solvers和RL的区别上是很有用的,MDP solvers的空间复杂度是,而RL不依赖于状态转移表。RL是两层全连接的神经网络,整个网络大约0.4MB内存。故在状态空间巨大的情况下,SquirRL也能学习到很好的策略。
以太坊的激励机制和Bitcoin相似,但是添加了针对叔区块的奖励。如果一个区块不是主链区块而是一个主链区块的子区块,这样的区块称之为叔区块。每个区块最多包含两个叔区块。本文拓展了状态空间表示叔区块信息,增加了引用叔区块后的额外奖励规则,在状态更新里增加叔区块的更新条件,实验结果如图5所示,SquirRL获得的相对回报与其他关于以太坊中自私挖矿攻击的文献进行比较,SquirRL显然更优。
在上三个实验里,写出一个描绘系统动态性的MDP是可能的,但是在实际的场景下,MDP可能会随着事件或者未知原因改变。
这一部分里我么们探索攻击者的哈希算力随着事件改变的情况,我们不知道随机过程的分布情况,如果进行估计,将连续随机过程加入到MDP会极大的增加状态空间。
而SquirRL在不知道潜在的随机过程的情况下,通过在训练期间使用哈希算力的当前值来处理这种不确定性。我们发现它可以很好的预测哈希算力的波动。假设了hash power<51%以防止51%攻击的发生,如图8所示,随着方差的增加,SquirRL逐渐优于OSM策略。
单agent的场景往往并不符合现实,区块链作为多方参与的平台,应该考虑多agent的场景。而由于多agent的场景很难进行理论分析,且MDP因为巨大的状态空间也不适合解决多agent的问题,而本文提出的强化学习就比较适合。这部分里,我们研究了Bitcoin协议中多agent竞争的场景,还研究了self-mining和block withholding attack。每次训练迭代由28000次区块创建事件组成,共有7个workers进行40次决策,每个worker在每个决策过程里运行100个区块生成事件。训练完成后,取过去10次训练迭代中获得的平均相对报酬。
首先探究在单agent场景下BITCOIN的OSM是否优于SquirRL训练得到的策略。考虑这样一种场景,ABC三个agent,A使用诚实策略,B使用OSM策略,C使用SquirRL。图9显示B与C在哈希算力小于0.5的情况,可以看到OSM不再是最优的,RL获得了比OSM更大的奖励。两个agent的博弈在的时候对两者都是有利的。图10展示了OSM和RL策略的区别,RL比OSM更加能适应环境,这是由于RL可以更多的采取match去识别OSM无法识别的场景。
只有两个agent都adapt的时候,才会有竞争。图11显示当B和C都使用SquirRL,且哈希算力小于0.5的场景。图11里,我们将总报酬较大的agent的相对报酬与总报酬较小的agent的平均报酬进行平均,并将两者的合计报酬绘制出来。图11展示了当小于0.4的时候,两个agent都比诚实挖矿获利多,当大于0.4的时候,联合奖励优于诚实挖矿,当大于0.42的时候,两者单个运行都比诚实挖矿获利大。
图12里给出了两个哈希算力为0.4时的agent在训练过程中的表现,出人意料的是并没有观测到最终收敛于纳什均衡。这表明在two-strategic-agent场景下可能不存在纳什均衡。
引文41分析了k个agent,这些agent只能使用两类策略(honest mining+semi-selfish mining)。引文41发现只要agent有足够的哈希算力,当所有agent选择semi-selfish mining,则存在纳什均衡。
但是本文的实验有着不太相同的结论,我们发现,有两个agent时,他们的相对奖励如果要超过hash power,则他们的hash power必须在,如果小于这个阈值,SquirRL将为所有agent产出诚实的策略,在的情况,没有多余的结合自私奖励。我们分析结论不同的原因是两者的策略空间不同。我们把SquirRL可以使用的策略限定为引文41的策略,下表给出了结果。可以发现,两个agent都采用OSM的时候,这个博弈的纳什均衡出现了。本文还探究了为什么随着agent的增加诚实行为也增加。图16显示了在的最后一次训练迭代中,当分叉状态为relevant时,agent对应的策略。
目前为止我们假设竞争agent没有其他agent的本地链信息,但是这个假设并不完善。采矿池已经被普遍应用,参与者将他们的采矿资源集中起来,并按比例分配报酬。采矿池通常对新参与者开放,他们彼此竞争以获得区块奖励。于是出现spy mining。
在实验里,对Bitcoin协议增加先验知识,即si是agent i无spy知识观测到的状态,增加spy mining state,即。和图11类似,图13里只是添加了spy mining信息,我们观测到agent的在结合哈希算力下奖励低于non-spy-mining情况。因为给矿工提供spy信息并不会增加他们从诚实方那里窃取相对奖励的能力,这里在图13当的时得以体现。拥有更小奖励的agent实际上会获得比自己的哈希算力更低的奖励。图15给出了三个具有完全spy信息的miners,可以发现自私矿工的总回报不会超过他们的哈希算力。
在区块保留攻击里,一个采矿池将矿工渗透到对手池中,以减少他们的收入并获得竞争优势。攻击池将挖掘资源部署到目标池中,提交部分解决方案,即工作证明,获得奖励。如果攻击池在目标池中挖了一个方块,它将保留它。因此,由于其哈希算力的下降,目标池会损失块奖励和收入。
我们发现SquirRL可以自动学习到和均衡预测到相同奖励下的策略。使用PPO对模型进行训练,因为它适用于多agent场景,并且支持连续的动作空间。在的学习率进行次决策后,策略和奖励都收敛于引文13发现的纳什均衡,具体数据如下表所示。
强化学习在测试区块链协议激励机制上具有良好前景,本文提出了SquirRL,一个基于深度强化学习的自动识别区块链激励机制漏洞的框架。我们显示了SquirRL可以接近对区块链机制攻击理论分析的结果,也可以拓展到使用传统技术如MDP solvers无法考虑的地方。
方法缺点在于,实验结果显示了协议是安全,但这并不能说明协议是安全的。由于超参数设置的原因,从协议测试的角度来看,RL agent没有发现漏洞的事实可能是安全协议糟糕的超参数造成的。我们将SquirRL看作一个工具,当理论分析不现实的情况下,让协议设计者对协议进行安全性分析。
在未来,可以对agent的不同攻击行为和意图进行模拟。比如,agent之间合作的影响是未知的。我们的多agent实验只做了竞争agent,假设如果两个agent联合,且是完全联合,等价于竞争的agent变少了,这样的情况需要在未来被考虑。因为现实下agent可能是合作的。