《迅雷链精品课》第十三课：PBFT 算法

 上一节课我们学习了PoW(Proof-of-Work，工作量证明)共识算法，了解其来源和优缺点，这节课我们将学习PBFT算法，了解PBFT算法如何通过三阶段协议保证了系统能够在包含作恶节点的情况下达成共识。



第十三课 PoW共识算法



1. 背景



通常情况下，分布式系统由很多节点组成，系统的可靠性要求系统必须具备应付异常节点发送过来的不一致消息的能力。分布式的这个场景最早由 Lamport，Shostak 和 Pease 于1982年形象地描述为拜占庭将军问题，即多个拜占庭将军各自率领了小分队驻扎在敌方城市之外，他们需要对是否进攻敌军达成统一的作战计划，但是这些将军之间存在反叛者，他们可能会篡改、延迟或者丢弃其他将军的命令，迷惑其他可信将军。拜占庭将军问题就是要找到一个算法来保证可信将军之间能够达成一致的作战计划。



Lamport他们证明了对于拜占庭将军问题，系统中如果存在f个不可信节点，那么只有总节点数不少于3f+1才存在一个算法解决该问题。下面我们来简单地证明这个问题解的不可能性，假设系统中总共有3个节点，Commander是提议者，记为C，Lieutenant 1 和Lieutenant 2 是验证节点，记为 LT1 和 LT2。这三个节点中存在一个作恶节点，下面我们证明在存在一个作恶节点的情况下，无论是提议者还是验证节点，系统均无法达成统一的共识。



如图1-1所示，假设 C 是作恶节点，另外两个节点是可信节点。C 向节点LT1和LT2发送了相互矛盾的命令— 进攻和撤退，那么LT1在接收到C发送过来的进攻命令和LT2转发过来的命令撤退，那么它就无法确定是要进攻还是撤退。



图1-1 提议者是作恶节点



如图1-2所示，假设 LT2 是作恶节点，节点 C 和 LT1 是可信节点，C要求LT1和LT2进攻，但是LT2在转发C的命令给LT1的时候作假，告诉LT1它接收到C发过来的命令是撤退，那么LT1在就无法判断到底是要进攻还是撤退。



图1-2 Lieutenant 2 是作恶节点



从上述论证中我们可以直观地觉察到3个节点的情况下，即使只有一个作恶节点，也无法达成共识。但如果系统中多一个可信节点LT3，则LT1可以收到可信节点Commander发出的和LT3转发的进攻命令，即使LT2节点发出撤退命令，LT1也可以正确选择跟大多数节点一致的进攻命令，这样系统能达成共识。我们可以将这个结论进行推广，即对于存在f个作恶节点的分布式系统，当节点总数不超过3f的时候，是不存在一个可以达成共识的解的。



学者们陆续提出了解决该问题的拜占庭容错算法BFT，不是只能用于同步系统，就是性能太差，难以在生产环境中广泛运用。为了解决BFT的实际运用问题，MIT计算机实验室的Castro和Liskov于1999年在OSDI会议上提出了能够在异步网络环境中工作的PBFT算法，在借鉴分布式系统的状态机复制和quorum的基础上设计了三阶段协议来解决一致性问题，同时引入了优化项，算法的复杂度由原来的指数级降低为多项式级别。下面我们会讲解PBFT算法的模型、算法流程、优化，其中算法流程即三阶段协议是PBFT算法的核心算法流程，是我们的重点讲解对象。



2. PBFT算法模型



PBFT算法本质上是一个状态机复制算法，能够用于实现带有状态和特定操作的任意确定性状态复制服务，它的目的是让所有的可信节点执行相同的序列。此外，PBFT算法使用安全的哈希函数对消息做摘要、使用公私钥对消息进行签名和验签、同时增加了消息验证码，保证了消息的完整性和不可篡改性。在作恶节点总数不超过系统节点总数的1/3的情况下，PBFT算法能够保证系统的安全性和活性。PBFT算法主要包含三类基本协议：



1. 三阶段协议：解决如何达成共识

2. 检查点协议：类似于操作系统的还原点，主要用于垃圾回收



2.1 基本概念



首先我们了解一下PBFT算法的基本概念：



1. 主节点primary：负责对请求进行排序，发起新的请求

2. 副节点backup：负责验证请求是否有效

3. 客户端client：负责提出请求，要求节点执行某个操作，通常跟主节点合二为一

4. 序列号sequence number：请求的编号

5. 视图view：一个主节点和多个备份节点形成一个视图

6. 检查点checkpoint：如果某个序列号对应的请求收到了超过的节点的确认，则称为一个检查点。



根据前面的讨论，我们知道PBFT算法是用于解决拜占庭将军问题的，所以系统要能够容忍f个作恶节点，则系统的总节点数不少3f+1个。假定系统中包含1个主节点和2f+1个副节点。



3. 三阶段协议



三阶段协议是PBFT算法的核心流程，用于解决系统的一致性问题，保证所有可信节点在给定状态和参数组的条件下，按照相同的顺序执行完请求后能够取得相同的状态。三阶段分别为pre-prepare、prepare和commit阶段，具体的执行流程图如图3-1所示，下面是正常的流程：



1. 客户端c在时间为t发送请求给主节点，要求执行操作o;

2. Pre-prepare阶段：主节点0对请求分配序列号，完成排序后将请求广播给所有的副节点;

3. prepare阶段：副节点i验证在接受到主节点的请求后，需要验证请求和序列号在当前的视图中是否有效，将投票结果发给其他节点;

4. commit阶段：每个节点在收到超过2f个副节点的投票信息之后，如果请求、序列号和视图均匹配，则生成一个提交信息发送给其他节点，表明接收了对应的请求;

5. 每个节点在收到超过f+1个节点的提交信息后，将请求的发起时间t、请求的执行结果r和当前的视图号v发送给客户端 c;

6. 客户端在接受执行结果r之前，需要阻塞等待f+1个节点的响应，要求各个副本节点i对于客户端c的请求的响应中的签名必须有效，同时这些响应中的各个结果r以及请求的时间戳t需要相同。



如果客户端超时没有收到响应，客户端会广播请求给系统中的所有节点。节点接收到重复的请求的时候，如果已经处理过该请求的话，那么会将响应再次发送给客户端。同时，副本会记录下自己最近一次发送给客户端的响应消息。此外，如果节点不是主节点的话，需要把请求转发给主节点。如果主节点不将请求广播给副节点，当有足够的副节点怀疑主节点是作恶节点的时候， 亦会引发视图变更，将主节点替换掉。



图3-1 PBFT算法流程图



3.1 pre-prepare阶段



主节点在收到客户端的请求后，会基于当前的视图v对请求分配编号n，将视图号v、请求序列号n、请求摘要d、签名封装成pre-prepare消息，记录到本地的消息日志中，然后将pre-prepare消息连同客户端原始请求m发送给其他的副节点，同时追加到自己的消息日志中。注意，pre-prepare消息中，是不包含客户端原本的请求消息m的，而只是包含了该请求的摘要而已。pre-prepare阶段主要是用来对请求进行绝对排序，将请求传输和请求排序进行解耦，同时还可以证明在视图变更协议中，主节点在视点为v的时候把请求编号为n。

图3-2 pre-prepare 阶段



当副节点接受到主节点的pre-prepare消息的时候，在满足如下的条件的情况下会接受该消息。



3.2 prepare阶段



每个副节点在上一个阶段验证主节点的pre-prepare消息有效之后，会进入到 prepare 阶段，生成一个prepare消息记录到本地，表明自己已经接受了主节点的提议，同意在视图v中把序列号n分配给了客户端请求，保证自己在这个视图中不会再将序列号分配给其他的客户端请求，然后把prepare消息发送给其他节点。

图3-3 准备阶段



对于各个节点发送过来的prepare消息，包括主节点在内的所有节点接受该消息的条件是：



算法的 pre-prepare 和 prepare 阶段保证了系统中可信节点在视图v中对于请求m的绝对排序取得了共识。



3.3 commit 阶段



当各个节点做好准备之后，即本地消息日志中记录了摘要为d的请求m、记录了主节点对请求m进行排序的pre-prepare消息，同时接收到了超过2f个其他节点发过来的有效的prepare消息，各个节点会进入下一个阶段，即commit阶段。各个节点会生成一个视图为v、请求序列号为n、请求摘要为D(m)的commit消息追加到本地消息日志文件中，同时广播给系统内的其他节点。

图3-4 提交阶段



对于各个节点发送过来的commit消息，接受该消息的条件是

提交阶段保证了可信节点就本地提交的客户端请求的序列号取得了共识，即便这些客户端请求在每个节点是在不同的视图号中提交的，保证了所有的可信节点按照给定的顺序执行了所有的客户端请求，从而实现了安全性。当节点收到超过f+1个不同节点发送过来的commit消息之后，会执行客户端请求m中所要求的服务操作，同时将执行结果发送给客户端，这个保证了在可信节点中提交的任意一个客户端请求，最终都会在另外f+1个节点中被提交到本地的。



4. 算法优化



4.1 检查点协议



PBFT通过三阶段协议来对请求达成共识，但是各个阶段产生的消息如果不进行垃圾回收的话，系统的存储资源将会不堪重负。为此，PBFT算法设计了检查点协议来丢弃本地的消息日志文件中的旧消息。垃圾回收的设计需要考虑何时该删除消息，同时保证某个消息在可信节点中都被删除之后，某个节点在缺失这些消息的情况下在同步到最新的状态后能够证明这个状态是正确的。



根据前面的三阶段协议，我们可以知道客户端收到某个请求的执行结果的时候，表明该请求已经被至少f+1个节点提交过了，这个时候就可以删除该消息了。对于第二个问题，检查点协议是通过提供额外的证据，checkpoint 消息来证明这个状态是正确的。但是如果每次执行完一个客户端请求之后都生成上述要求的证据，那么这个操作将是非常昂贵的。实际上，PBFT的检查点协议是周期性地生成这些证明，比如当请求的序列号整除周期T的时候。



图4-1 检查点协议



如图4-1 所示，检查点协议的的工作流程如下所示：





检查点协议除了用于垃圾回收外，还用于更新请求序列号的有效范围，序列号的最低值h设为最近一次检查点里面的请求序列号，序列号的最高值设为H=h+k，其中需要设置得大一点，比checkpoint的周期要大，不然节点收到序列号较大的请求之后需要阻塞等待到下一个检查点才能处理。比如说，如果检查周期是100个请求，那么k可以设置成200。



4.2 视图变更协议



前面我们提到过，一些拜占庭算法不能解决主节点出故障的问题。PBFT算法是通过视图变更协议来允许系统在主节点出故障的情况下仍能够正常运转，从而保证了系统的活性。视图变更协议实际上是通过超时机制触发的，通过超时机制，我们可以避免主节点不工作的情况下，副节点无限期地等待客户端请求被执行。假定系统当前状态如图4-2所示，视图号为v。



图4-2 视图变更 — 初始视图v



下面我们来具体阐述一下视图变更协议的具体工作流程。



4.2.1 维持计时器



副节点会针对视图v维持一个计时器。当在收到主节点发送过来的一个有效的请求而且没有执行的时候，如果是针对当前视图的计时器还没有启动的话，那么节点会启动一个新的计时器。如果节点还在执行其他请求的话，那么节点会重置该请求的计时器。如果节点不再等待执行该请求的时候，会停止视图v的计时器。



4.2.2 请求视图变更



如图4-3所示，当副节点的视图v的计时器如果超时了，就会生成一个view-change 消息，记录到本地日志文件中，同时广播给其他节点，要求替换掉主节点，变更到下一个视图v+1。注意，在视图变更期间，除了 checkpoint、view-change 和 newview 消息之外，备份节点i是不会接受其他消息的。



图4-3 视图变更 — 计时器超时，发起视图变更





各个节点收到view-change 消息后，会检验该消息是否有效，如果有效的话，会追加到本地的日志文件中。



4.2.3 切换到新视图



如图4-4所示，当新视图v+1对应的新的主节点接收到2f个节点的发送过来的有效的view-change消息之后，会向其他节点发送一个带上自己签名的new-view消息，提议系统内所有节点切换到下一个视图v+1，同时接受自己成为新的主节点。这个 new-view 消息的另外一个作用是找到所有节点的共同的稳定检查点，同时针对那些携带了尚未提交执行的请求的 prepare 消息重新生成相应的 pre-prepare 消息，这个主要是在切换到新视图之后，新的主节点需要重新对这些未处理的请求分配序列号，然后对这些请求再次执行一遍三阶段协议。





副节点在收到要求将视点变更为v+1的new-vew消息之后，在确认消息有效之后，会接受该new-view消息，记录到本地消息文件中，同时将视点更换到新的视点v+1。此外，副节点还会new-view中携带的由新的主节点重新生成的pre-prepare消息都追加记录到本地的消息日志中，并按照检查点协议进行垃圾回收，删除比较老的消息。然后，对于new-vew消息中集合携带的所有由新主节点生成的新的pre-prepare消息，备份节点都会生成相应的prepare消息，记录到本地日志文件中，转发给其他节点，即对这些未处理的请求在新的视图中重新执行一遍三阶段协议，保证视图切换过程中未处理的请求能够重新被处理。



5. PBFT算法应用



PBFT算法通过三阶段协议保证了系统能够在包含作恶节点的情况下达成共识，将算法复杂度由指数级别降低成了多项式级别，大大地降低了网络通信的开销，为拜占庭算法的在生产环境中的实际运用提供了可能。此外，PBFT算法通过检查点协议进行垃圾回收的同时保证了系统能够感知全局状态的一致性，而视图变更协议解决了主节点失效的问题，保证了系统的活性。实际上，相比于比特币等区块链系统使用的概率性的PoW算法，PBFT算法的确定性特性保证了系统具有应付作恶节点的能力同时不会分叉，非常适合于联盟链和私链的搭建，比如联盟链 fabric 中最初就提供了PBFT作为共识算法。虽然 PBFT 算法性能比原有的拜占庭算法提高了很多，但是PBFT算法的性能会随着节点个数的增加而急剧下降，所以通常会结合DPoS等算法来对节点的权限进行控制，比如 tendermint 共识算法，即区块链上的PBFT算法，就是使用DPoS来控制验证节点的数量的。