区块链课程13共识层：PBFT共识算法

1、PBFT算法Cuiting Shi, OneThing Tech LTD.Thursday, December 6, 2018 TOC o 1-5 h z HYPERLINK l bookmark13 o Current Document 背景-1 HYPERLINK l bookmark16 o Current Document PBFT算法模型3 HYPERLINK l bookmark22 o Current Document 2.1基本概念3三阶段协议-4 HYPERLINK l bookmark38 o Current Document pre-prepare 阶段6 HYPERLI

2、NK l bookmark46 o Current Document prepare 阶段-7 HYPERLINK l bookmark53 o Current Document commit 阶段8算法优化9 HYPERLINK l bookmark62 o Current Document 4.1检查点协议9 HYPERLINK l bookmark69 o Current Document 4.2视图变更协议11 HYPERLINK l bookmark72 o Current Document 4.2.1维持计时器11 HYPERLINK l bookmark75 o Current

3、Document 4.2.2请求视图变更12 HYPERLINK l bookmark80 o Current Document 4.2.3切换到新视图13 HYPERLINK l bookmark85 o Current Document PBFT算法应用15 HYPERLINK l bookmark88 o Current Document 参考161.背景通常情况下，分布式系统由很多节点组成，系统的可靠性要求系统必须具备应付异常节点发 送过来的不一致消息的能力。分布式的这个场景最早由Lamport，Shostak和Pease于 1982年形象地描述为拜占庭将军问题(1Leslie Lam

4、port 1982)，即多个拜占庭将军各自率 领了小分队驻扎在敌方城市之外，他们需要对是否进攻敌军达成统一的作战计划，但是这些 将军之间存在反叛者，他们可能会篡改、延迟或者丢弃其他将军的命令，迷惑其他可信将 军。拜占庭将军问题就是要找到一个算法来保证可信将军之间能够达成一致的作战计划。Lamport他们证明了对于拜占庭将军问题，系统中如果存在f个不可信节点，那么只有总节 点数不少于3f + 1才存在一个算法解决该问题。下面我们来简单地证明这个问题解的不可能 性，假设系统中总共有3个节点，Commander是提议者，记为C，Lieutenant 1和 Lieutenant 2是验证节点，记为LT

5、1和LT2。这三个节点中存在一作恶节点，下面我们 证明在存在一个作恶节点的情况下，无论是提议者还是验证节点，系统均无法达成统一的共 识。如图1-1所示，假设C是作恶节点，另外两个节点是可信节点。C向节点LT1和LT2发送 了相互矛盾的命令一进攻和撤退，那么LT1在接收到C发送过来的进攻命令和LT2转发过 来的命令撤退，那么它就无法确定是要进攻还是撤退。Commander图1-1提议者是作恶节点C said retreatretreatLieutenant2如图1-2所示，假设LT2是作恶节点，节点C和LT1是可信节点，C要求LT1和LT2进 攻，但是LT2在转发C的命令给LT1的时候作假，告诉

6、LT1它接收到C发过来的命令是撤 退，那么LT1在就无法判断到底是要进攻还是撤退。图1-2 Lieutenant 2是作恶节点从上述论证中我们可以直观地觉察到3个节点的情况下，即使只有一个作恶节点，也无法达 成共识。但如果系统中多一个可信节点LT3，则LT1可以收到可信节点Commander发出 的和LT3转发的进攻命令，即使LT2节点发出撤退命令，LT1也可以正确选择跟大多数节 点一致的进攻命令，这样系统能达成共识。我们可以将这个结论进行推广，即对于存在f个 作恶节点的分布式系统，当节点总数不超过3f的时候，是不存在一个可以达成共识的解的， 严格的数学证明大家可以参考Lamport另夕卜一篇

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

8、算法的核心算法流程，是我们的重点讲解对象。2. PBFT算法模型PBFT算法本质上是一个状态机复制算法，能够用于实现带有状态和特定操作的任意确定性 状态复制服务，它的目的是让所有的可信节点执行相同的序列。此外，PBFT算法使用安全 的哈希函数对消息做摘要、使用公私钥对消息进行签名和验签、同时增加了消息验证码，保 证了消息的完整性和不可篡改性。在作恶节点总数不超过系统节点总数的1的情况下，PBFT3算法能够保证系统的安全性和活性。PBFT算法主要包含三类基本协议：三阶段协议：解决如何达成共识检查点协议：类似于操作系统的还原点，主要用于垃圾回收视图变更协议：用于解决主节点失效下不工作的情况2.1基

9、本概念首先我们了解一下PBFT算法的基本概念：主节点primary :负责对请求进行排序，发起新的请求副节点backup :负责验证请求是否有效客户端client :负责提出请求，要求节点执行某个操作，通常跟主节点合二为一序列号sequence number :请求的编号视图view : 一个主节点和多个备份节点形成一个视图检查点checkpoint :如果某个序列号对应的请求收到了超过2的节点的确认，则称为一个检查点。3根据前面的讨论，我们知道PBFT算法是用于解决拜占庭将军问题的，所以系统要能够容忍 /个作恶节点，则系统的总节点数不少于3f + 1个。假定系统中包含1个主节点和2f + 1

10、个 副节点。三阶段协议三阶段协议是PBFT算法的核心流程，用于解决系统的一致性问题，保证所有可信节点在给 定状态和参数组的条件下，按照相同的顺序执行完请求后能够取得相同的状态。三阶段分别 为pre-prepare、prepare和commit阶段，具体的执行流程图如图3-1所示，下面是正 常的流程：客户端c在时间为t发送请求REQUEST, of t,叱给主节点，要求执行操作。Pre-prepare阶段：主节点0对请求分配序列号：完成排序后将请求广播给所有的 副节点prepare阶段：副节点i验证在接受到主节点的请求后，需要验证请求和序列号在当 前的视图中是否有效，将投票结果发给其他节点com

11、mit阶段：每个节点在收到超过2/个副节点的投票信息之后，如果请求、序列 号和视图均匹配，则生成一个提交信息发送给其他节点，表明接收了对应的请求。每个节点在收到超过f + 1个节点的提交信息后，将请求的发起时间仁请求的执行 结果厂和当前的视图号v发送给客户端c :REPLY, v, t, c,睥八。客户端在接受执行结果r之前，需要阻塞等待/ + 1个节点白的响应，要求各个副本节 点i对于客户端C的请求的响应中的签名气必须有效，同时这些响应中的各个结果 r以及请求的时间戳t需要相同。如果客户端超时没有收到响应，客户端会广播请求给系统中的所有节点。节点接收到重复的 请求的时候，如果已经处理过该请求

12、的话，那么会将响应再次发送给客户端。同时，副本会 记录下自己最近一次发送给客户端的响应消息。此外，如果节点不是主节点的话，需要把请 求转发给主节点。如果主节点不将请求广播给副节点，当有足够的副节点怀疑主节点是作恶 节点的时候，亦会引发视图变更，将主节点替换掉。图3-1 PBFT算法流程图pre-prepare 阶段主节点在收到客户端的请求后，会基于当前的视图u对请求分配编号n，将视图号贝请求 序列号九、请求摘要d、签名。封装成pre-prepare消息PRE - PREPARE, vm,d、，记录 到本地的消息日志中，然后将pre-prepare消息连同客户端原始请求m发送给其他的副节 点，同

13、时追加到自己的消息日志中。注意，pre-prepare消息中，是不包含客户端原本的请 求消息m的，而只是包含了该请求的摘要而已。pre-prepare阶段主要是用来对请求进行 绝对排序，将请求传输和请求排序进行解耦，同时还可以证明在视图变更协议中，主节点在 视点为u的时候把请求编号为n。. backup (PRE - PREPA RE, v,n, d舄，m)*I backupf I backup图 3-2 pre-prepare 阶段当副节点接受到主节点的pre-prepare消息的时候，在满足如下的条件的情况下会接受该 消息。当前的视图号也是u，即表明pre-prepare消息的发起者确实是

14、主节点客户端请求m的摘要确实是pre-prepare消息中带的摘要d，pre-prepare消息的签名 是有效的。在当前视图u中，序列号正还没有被用过，即该节点没有接受过编号同样为n、但是请求 不是m的pre-prepare消息。序列号正不能过小、也不能过大，即nehtH，这个是为了防止一个主节点作恶，选择 一个过大的序列号来恶意消耗完序列号空间。prepare 阶段每个副节点在上一个阶段验证主节点的pre-prepare消息有效之后，会进入到prepare阶段，生成一个prepare消息PREPARE, v,几d,私记录到本地，表明自己已经接受了主节点 的提议，同意在视图u中把序列号九分配给

15、了客户端请求m，保证自己在这个视图中不会再将序列号分配给其他的客户端请求，然后把prepare消息发送给其他节点。. r primary蜘叩5.5史瓜j叩I backup图3-3准备阶段对于各个节点发送过来的prepare消息PREPARE, v,几d,凯，包括主节点在内的所有节点接受该消息的条件是：prepare消息的签名气正确当前节点的视图号是/在视图号u中，客户端请求的编号不能过大过小，即neh,H算法的pre-prepare和prepare阶段保证了系统中可信节点在视图v中对于请求m的绝 对排序取得了共识。commit 阶段当各个节点做好准备之后，即本地消息日志中记录了摘要为d的请求m

16、、记录了主节点对请 求血进行排序的pre-prepare消息，同时接收到了超过2f个其他节点发过来的有效的 prepare消息，各个节点会进入下一个阶段，即commit阶段。各个节点会生成一个视图 为贝请求序列号为九、请求摘要为D(m)、签名为气的commit消息 COMMIT,v,n,D(rn)，mi追加到本地消息日志文件中，同时广播给系统内的其他节点。图3-4提交阶段对于各个节点发送过来的commit消息，接受该消息的条件是：COMMIT消息的签名是正确的当前节点的视图号是v对于客户端请求m的编号n e h, H上一个阶段请求的摘要也是D(rn)，对这个请求的编号也是n提交阶段保证了可信节

17、点就本地提交的客户端请求的序列号取得了共识，即便这些客户端请 求在每个节点是在不同的视图号中提交的，保证了所有的可信节点按照给定的顺序执行了所 有的客户端请求，从而实现了安全性。当节点收到超过/ + 1个不同节点发送过来的 commit消息之后，会执行客户端请求m中所要求的服务操作，同时将执行结果发送给客户 端，这个保证了在可信节点中提交的任意一个客户端请求，最终都会在另夕卜f + 1个节点中 被提交到本地的。算法优化4.1检查点协议PBFT通过三阶段协议来对请求达成共识，但是各个阶段产生的消息如果不进行垃圾回收的 话，系统的存储资源将会不堪重负。为此，PBFT算法设计了检查点协议来丢弃本地的

18、消息 日志文件中的旧消息。垃圾回收的设计需要考虑何时该删除消息，同时保证某个消息在可信 节点中都被删除之后，某个节点在缺失这些消息的情况下在同步到最新的状态后能够证明这 个状态是正确的。根据前面的三阶段协议，我们可以知道客户端收到某个请求的执行结果的时候，表明该请求 已经被至少/ + 1个节点提交过了，这个时候就可以删除该消息了。对于第二个问题，检查 点协议是通过提供额外的证据，checkpoint消息来证明这个状态是正确的。但是如果每次 执行完一个客户端请求之后都生成上述要求的证据，那么这个操作将是非常昂贵的。实际 上，PBFT的检查点协议是周期性地生成这些证明，比如当请求的序列号整除周期T

19、的时 候。图4-1检查点协议如图4-1所示，检查点协议的的工作流程如下所示：当周期T到达的时候，各个节点会生成一个内容为最近一次执行的请求的摘要义请求编号为九、签名为气的checkpoint消息(CHECKPOINT, n, d, i)，追加到本地日志记录 中，然后广播给系统内的其他节点。气各个节点接受到checkpoint消息后，验证有效后会追加到本地的日志消息中。当各个节点在其消息日志中收集到了 2/ + 1个不同节点发送过来的有效的且状态相同的 checkpoint消息的时候，那么表明这是一个稳定的检查点stablecheckpoint，即2f + 1 个节点他们最后一次执行的请求都是一

20、样的，而且都分配了序号队当一个检查点被证明是有效、稳定之后，那么节点会把本地消息日志中的消息中客户端 请求序列号小于或者等于打的消息(pre-prepare、prepare, commit消息)都删掉。 同时，它会删掉旧的检查点和checkpoint消息。检查点协议除了用于垃圾回收外，还用于更新请求序列号的有效范围，序列号的最低值h设 为最近一次检查点里面的请求序列号，序列号的最高值设为H = h + K,其中k需要设置得大 点，比checkpoint的周期要大，不然节点收到序列号较大的请求之后需要阻塞等待到下 个检查点才能处理。比如说，如果检查周期是100个请求，那么k可以设置成200。4.

21、2视图变更协议前面我们提到过，一些拜占庭算法不能解决主节点出故障的问题。PBFT算法是通过视图变 更协议来允许系统在主节点出故障的情况下仍能够正常运转，从而保证了系统的活性。视图 变更协议实际上是通过超时机制触发的，通过超时机制，我们可以避免主节点不工作的情况 下，副节点无限期地等待客户端请求被执行。假定系统当前状态如图4-2所示，视图号为兀图4-2视图变更初始视图v卜面我们来具体阐述一下视图变更协议的具体工作流程。4.2.1维持计时器副节点会针对视图能隹持一个计时器。当在收到主节点发送过来的一个有效的请求而且没有 执行的时候，如果是针对当前视图的计时器还没有启动的话，那么节点会启动一个新的计

22、时 器。如果节点还在执行其他请求的话，那么节点会重置该请求的计时器。如果节点不再等待 执行该请求的时候，会停止视图u的计时器。4.2.2请求视图变更如图4-3所示，当副节点的视图u的计时器如果超时了，就会生成一个view-change消 息，记录到本地日志文件中，同时广播给其他节点，要求替换掉主节点，变更到下一个视图 u + 1。注意，在视图变更期间，除了 checkpoint, view-change和newview消息之外， 备份节点i是不会接受其他消息的。图4-3视图变更计时器超时，发起视图变更view-change消息的具体内容为以W - CHANGE, v + 1,n, , P, i

23、)，其中最近一次的稳定 检查点对应的请求的序列号， 是证明该检查点稳定性的2/ + 1个 checkpoint消息的集 合，/是Pm的集合，其中血是副节点i中的序列号大于打的等待提交和执行的客户端请求m。每个九包含了如下的信息：不包含原始请求m的pre-prepare消息，不过不包含原始的客户端请求m ,2f个由其他副节点签名的跟pre-prepare消息匹配的、有效的prepare消息(匹配 有效指的是prepare消息中的签名有效，在视图u中分配给请求的序列号一致，客户 端请求摘要D(rn)相同)各个节点收到view-change消息后，会检验该消息是否有效，如果有效的话，会追加到本 地的

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

25、view消息的具体格式为NEW VIEW, v + 1,V, 0):V是主节点加本地日志中保留的所有要求由视图U变更为视图U + 1的有效vew- change消息的集合。0是一个没有携带客户端原始请求m的pre-prepare消息的集合，这些preprepare 消息中对应的请求都是在上一个视图u都是有效的，但是还没有处理完的。图4-4视图变更新的主节点发起新视图副节点在收到要求将视点变更为v + 1的new-vew消息之后，在确认消息有效之后，会接 受该new-view消息，记录到本地消息文件中，同时将视点更换到新的视点u + 1。此外， 副节点还会new-view中携带的由新的主节点重新生成的pre-prepare消息都追加记录到 本地的消息日志中，并按照检查点协议进行垃圾回收，删除比较老的消息。然后，对于 new-vew消息中集合。中携带的所有由新主节点生成的新的pre-prepare消息，备份节点 都会生成相应的prepare消息，记录到本地日志文件中，转发给其他节点，即对这些未处 理的请求在新的视图中重新执行一遍三阶段协议，保证视图切换过程中未处理的请求能够重 新被处理。5. PBFT