SIGNA:PBFT 拜占庭协议安全性分析:不适合联盟链或公链_IGN

作者:王永革教授,著名华裔密码学家,北卡罗来纳大学夏洛特分校(UNC,Charlotte)计算机系终身教授,德国海德堡大学获得博士学位,Sperax首席科学家。共识协议的设计一直是一个很具有挑战性的课题。图灵奖获得者Lamport在1989年用古希腊帕克西岛(Paxos)上的一群业余立法议员制定法律的过程描述了他所设计的可用于分布式计算的Paxos共识协议。Lamport将他的文章投给了ACMTOCS。也许这个杂志的编辑没领会到该文章的重要性,所以一直没同意发表。直到Paxos共识协议被学术界广泛讨论并被工业界广泛应用,该杂志才在1998年发表了该文章:Lamport,Leslie."Thepart-timeparliament."ACMTransactionsonComputerSystems(TOCS)16.2(1998):133-169.Lamport自我调侃说这是他的所有文章中等待发表时间第二长的一篇文章。到目前为止,Paxos共识协议几乎被使用于所有的分布式系统。比如Google的Bigtable使用Chubbylockservice系统来保证各个节点数据的一致性。而Chubbylockservice就是基于Paxos协议的。此外,微软,IBM,亚马逊的云服务系统都用Paxos协议为其提供系统的一致性。粗略来讲,Paxos协议由一系列ROUND组成。ROUND由0开始直到共识达成。每个ROUND分以下四步:1.主节点生成一个序列号,向所有节点广播。希望大家参与该序列号的活动2.每个节点发给主节点以下信息:他所参与投过票的序列号和他投过的票3.主节点在收到第二步的大部分回复后,选取一个不会违反SAFETY的数值v。把这个值v广播给所有的节点4.每个节点在收到主节点第三步的值v后,投票给v并向所有节点广播他的投票由于Paxos协议比较难于实现,斯坦福的研究者在2014年提出了模块化的易于实现的Paxos协议,并将其命名为Raft协议。Paxos/Raft协议是在比较温和的威胁模型里工作的。换句话说,该协议只对异步网络里的非拜占庭错误具有鲁棒性。在非拜占庭威胁模型里,出错的节点只能犯被动性的错误而不能展开具有主动进攻性的攻击。具有n个节点的系统最多能容忍的非拜占庭错误节点数是/2。Paxos/Raft协议达到了这个最大的容错节点数。因为Paxos/Raft协议对拜占庭错误不具有鲁棒性,他们是无法在开放的网络系统里使用的。拜占庭错误是具有主动攻击性的错误,比如:说谎,伪造消息,合谋攻击,或者展开具有选择性的DoS攻击。我们在之前的文章中已经提到,去中心化的区块链系统是基于开放的网络系统的,所以我们必须使用拜占庭威胁模型。目前市场上的区块链里使用最多的拜占庭协议是图灵奖获得者BarbaraLiskov和她的学生Castro设计的实用拜占庭容错系统PBFT(practicalBFT)。PBFT被广泛使用于联盟链和很多公链。PBFT可以被看作是Paxos协议的拜占庭版本。其主要区别在于PBFT在Paxos协议中加入了一个验证步骤来防止拜占庭错误。在分析其安全性之前,我们先给出其协议的形式化描述。在PBFT协议中,我们假定有n=3t+1个节点P1,…,Pn。其中最多t个节点被攻击者所控制。PBFT要求所有的节点共同维护一个状态并采取一致的行动。PBFT协议是通过一系列的视图(view)来进行的。在每一个视图里,有一个节点被称为主节点(leader)。PBFT系统首先从视图(v=0)开始,然后通过视图更换协议进入视图v=1,v=2,…等等。只有在系统认为主节点不能正常工作时,才会启动视图更换协议进入下一个视图。我们假定所有的节点都知道每一个视图的主节点是谁。每当一个客户提交一个任务给当前视图的主节点后,PBFT协议将进行三个阶段的通信:序号分配,相互交互,和序号确认。序号分配阶段对每个任务分配一个序列号,相互交互和序号确认阶段对所有的任务提供一个全局的排序。假定我们现在在视图v,并且主节点是Pi。那么整个协议的过程如下:1.客户端发送任务请求m,激活主节点的服务操作。2.当主节点Pi接收任务请求m后,启动三阶段的协议:a.序号分配阶段:主节点选择一个唯一的序列号seq给任务请求m。主节点然后向所有的节点广播以下消息m,<PRE-PREPARE,v,seq,H(m)>,SIGNATURE其中H是一个哈希函数。一个节点Pj接受以上的消息,如果以下的条件都满足i.数字签名SIGNATURE有效ii.Pj尚未接受另一个含有相同v,seq的另一任务请求iii.序列号seq在合理的范围内b.相互交互阶段:如果节点Pj接受接受了主节点的广播消息,那么Pj进入相互交互阶段并对所有的节点广播以下消息<PREPARE,v,seq,H(m),Pj>,SIGNATUREc.序号确认阶段:对于节点Pj来说,一个数组<m,v,seq,Pj>是准备好了的当且仅当Pj收到了至少2t个有效的消息<PREPARE,v,seq,H(m),P>。当数组<m,v,seq,Pj>对Pj来说是准备好了后,Pj对所有的节点广播以下确认消息:<COMMIT,v,seq,H(m),Pj>,SIGNATURE当一个节点收到2t+1个确认消息后,该节点将执行任务请求m中所包含的任务,并将结果直接发送给客户。3.客户端等待来自不同节点的回复,若有t+1个回复相同,则该回复即为运算的结果。最近我们在如下文章中对PBFT的安全性进行了分析:YonggeWang.ByzantineFaultToleranceinPartiallyConnectedAsynchronousNetworks该文章的分析结论是PBFT共识协议在异步网络里是不安全的。我们在本文,简单的介绍我们设计的在异步网络里对PBFT协议的攻击办法。为了简化我们的描述,我们假定系统有n=3+1=4个节点P1,P2,P3,P4。其中节点P1被攻击者控制。另外我们假定视图v的主节点是P1。我们的攻击在视图v展开:1.在视图v的序号分配阶段,主节点P1把广播消息「m,<PRE-PREPARE,v,seq,H(m)>,SIGNATURE」发送给P1,P2,P3。但是不发给P4。2.在相互交互阶段,P1把广播消息「<PREPARE,v,seq,H(m),P1>,SIGNATURE」发送给P1,P2,P3。但是不发给P4。在相互交互阶段,节点P2,P3会把广播消息「<PREPARE,v,seq,H(m),P2>,SIGNATURE」和「<PREPARE,v,seq,H(m),P3>,SIGNATURE」发给所有的节点。当然了,如果可能,攻击者也许会发起DoS攻击,让节点P4不会接受到节点P2,P3的广播消息。到此时,数组<m,v,seq,Pj>对节点P1,P2,P3来说是准备好了。因为P4最多收到了两个相互交互消息,而我么最少需要2+1=3个消息来准备好一个数组,所以对P4来说,该数组并没有准备好。3.在序号确认阶段,P1把广播消息「<COMMIT,v,seq,H(m),P1>,SIGNATURE」发送给P1,P2。但是不发给P4。在序号确认阶段,节点P2,P3会把广播消息「<COMMIT,v,seq,H(m),P2>,SIGNATURE」和「<PREPARE,v,seq,H(m),P3>,SIGNATURE」发给所有的节点。当然了,如果可能,攻击者也许会发起DoS攻击,让节点P4不会接受到节点P2,P3的广播消息。到此时,节点P1,P2收到了3个对任务m的确认消息。节点P3和P4最多收到2个对任务m的确认消息。所以节点P2将执行任务请求m中所包含的任务,并将结果直接发送给客户。但是P1,P3,P4不会执行该任务。所以客户收不到足够的回复。在实行了以上的攻击后,节点P1将不再回复任何视图v的任何消息。所以系统将启动视图更换协议进入下一个视图v+1。在进入视图v+1后,诚实节点的P2,P3,P4的内部数据状态是不一样的。所以系统进入了不协调的状态。在PBFT协议中,为了解决有些节点可能会收不到某些消息,PBFT协议设计了CHECKPOINT状态更新过程。特别的,每执行100个任务后,每个节点Pj会广播其当前状态的消息给所有的节点:<CHECKPOINT,seq,H(state),Pj>,SIGNATURE如果一个节点Pi收到2t+1个如上的状态更新消息,并且其状态state的,那么节点Pi将用如上消息里的状态state替换自己的当前状态。在我们的如上攻击中,如果不诚实的节点P1不发布状态更新消息,那么P2发布的状态更新消息将不同于P3和P4发布的状态更新消息。因为我们至少需要2+1=3个相同的状态更新消息来更新一个节点的状态,P2的状态是没法更新到P3和P4的状态的。所以系统将一直处于不协调状态。在以后的视图里,不诚实的节点P1可以和诚实的节点P3,P4合作共同执行客户端的另一个任务请求。所以各个节点的状态将进入不可恢复的不协调状态。在我们的前一篇文章里,我们提到,在基于Internet的区块链技术中,DoS攻击是很容易展开的。由于Internet是一个异步网络,所以我们用以下模型来刻画其网络通信:存在一个GlobalStabilizationTime(GST),在GST之前,任何消息可能丢失,或被重新排序。在GST之后,网络变为同步网络。但是GST什么时候开始,没有人知道。所以说,我们以上的攻击在异步网络的GST之前是可以展开的。那么如果一个区块链系统使用PBFT作为其共识协议,我们以上的攻击结果是什么样的?一般来说,在发起如上攻击收,该区块链系统首先会出现分叉,然后将进入死机状态。特别的,加入在展开我们所描述的以上攻击之前,大家达成共识的区块链是:A→B→C→D。攻击者用以上的攻击方案,先让P2决定下一个区块是E。也就是说在P2的记录里,当前区块链是:A→B→C→D→E。但是P3,P4所记录的当前区块链仍然是A→B→C→D。然后攻击者P1让节点P3,P4决定下一个节点为F。这样在P3,P4的记录里,当前区块链是:A→B→C→D→F。因为区块E不同于区块F。区块链产生了分叉。由于下一个区块必须有当前区块链延伸出去。如果节点从现在开始不在参与任何活动,那么系统没发得到最小的投票数2+1=3。所以没有新的区块可以生成。综合起来,我们在本文的分析结论是:PBFT共识协议没法保证区块链系统的安全性和活性需求。所以我们建议,不论是联盟链或公链,都不应该用PBFT做为其共识协议。

郑重声明: 本文版权归原作者所有, 转载文章仅为传播更多信息之目的, 如作者信息标记有误, 请第一时间联系我们修改或删除, 多谢。

区块博客

[0:0ms0-3:513ms