PBFT算法

概要

条件

• PBFT容忍无效或者恶意节点数：f
• 为保障整个系统可以正常运转，需要有正常节点：2f+1
• 系统的总节点数为：3f + 1

也就是说，PBFT算法可以容忍小于1/3个无效或者恶意节点

前提

节点0为主节点，节点1-3为从节点（其中节点3为拜占庭节点），C为客户端

前提（request），客户端（C）向主节点（0）发起请求，主节点 0 收到客户端请求，会向其它节点发送 pre-prepare 消息，其它节点就收到了pre-prepare 消息，就开始了这个核心三阶段共识过程了

角色

客户端（client）
主节点（primary）
副本节点（replica）

客户端

REQUEST

⚪ 客户端（发送消息）

向主节点发送请求，要求执行操作o

[!参数]

• o：operation，请求的具体操作
• t:：timestamp，请求时客户端追加的时间戳
• c：client，客户端标识
• ：是对消息c的签名
• REQUEST: 包含消息内容m，以及消息摘要d(m)

🔴主节点（接收条件）

校验客户端请求消息签名是否正确，非法请求则丢弃，正确则进入三段式提交

REPLY

⚪客户端

客户端等待· f+1 个节点返回相同的响应

参数

• v：view，视图号
• t：timestamp，请求时间戳
• c：client，客户端标识
• i：节点i的编号
• r：节点i的回复
• ：节点i对消息的签名

完成条件（f+1） 客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识！否则的话，客户端需要判断是否重新发送请求给主节点

---

三段式共识协议

预准备阶段 pre-prepare

🔴主节点（广播消息）

为请求分配序号n，生成一条 消息

[!参数]

• v：view，视图号
• n：序号（n必须未被分配给其它请求，且比最近一次的请求的序号大）
• d：为m的消息摘要
• ：主节点对消息的签名
• m：消息内容

• 记录到本地消息日志中
• 发送给所有副本节点

🔵副本节点（接收条件）

进行以下验证：

• 主节点PRE-PREPARE消息签名是否正确
• 同一v下并且编号也是n的PRE-PREPARE信息
• d与m的摘要是否一致
• n是否在区间[h, H]内，非法请求丢弃

验证不通过，丢弃消息；验证通过，接收消息，记录到本地消息日志中，并进入下一阶段

---

准备阶段 prepare

🔵副本节点（广播消息）

每个副本节点生成 （i是当前副本节点编号）

• 记录在本地，表明自己已经接收了主节点的提议
• 向其他节点包括主节点发送

🔴🔵主节点&副本节点（接收条件）

进行以下验证：

• 副本节点PREPARE消息签名 是否正确
• 当前副本节点是否已经收到了同一视图v下的n
• n是否在区间[h, H]内
• d是否和当前已收到PRE-PPREPARE中的d相同

验证不通过，丢弃消息；验证通过，则接收消息

完成条件（2f）

1.将消息写入消息日志中（本地消息日志中记录摘要为d的请求m，记录了主节点对请求m进行排序的pre-prepare消息） 2.从2f个不同副本节点收到（与pre-prepare消息一致的）prepare消息（2f个prepare+1个pre-prepare）

则进入commit阶段

形式化证明描述

定义prepared(m,v,n,i)，如果某节点i验证通过了以下数据：

• a. m本身
• b. 关于m的 消息
• c. 2f条其它节点（不包含自己）发送过来的、与 消息相匹配的消息（匹配的定义是，它们的 v、n以及d是完全一样的）

则称prepared(m,v,n,i)的值为true，否则为false

如果prepared(m,v,n,i)为真，则prepared(m',v,n,j)必不成立，这就意味着至少f+1个正常节点在视图v的预准备或者准备阶段发送了序号为n的消息m

---

提交阶段 commit

🔴🔵主节点&副本节点（广播消息）

生成 commit消息 ，进行:

• 追加到本地消息日志中
• 广播给系统内其他节点

🔴🔵主节点&副本节点（接收条件）

校验

• 副本节点commit消息签名是否正确。
• 当前副本节点是否已经收到了同一视图v下的n。
• d与m的摘要是否一致。
• n是否在区间[h, H]内。

验证不通过，丢弃消息；验证通过，则接收消息，并将该消息插入本地消息日志中

完成条件（2f+1） 如果副本节点i收到了2f+1个验证通过的commit消息（包括自己），说明当前网络中的大部分节点已经达成共识，然后运行客户端请求，并向客户端返回执行结果reply

形式化描述

如果对于某个节点i，prepared(m,v,n,i)为true，则该节点将进入commit阶段，并广播消息

定义

如果某节点i满足以下条件：

• a. prepared(m,v,n,i)的值为true
• b. 2f条其它节点（不包含自己）发送过来的、与 消息相匹配的消息（匹配的定义是，它们的 v、n以及d是完全一样的）

则定义为true，否则为false

定义

• a. 任意f+1个正常副本节点集合中prepared(m,v,n,i)为true
• b. 为true

则定义为true，否则为false

对一些无故障节点来说，当为true，则为true

如果某节点i的为true，则执行该请求，并将结果返回客户端

---

垃圾回收

上述算法流程中，各个阶段产生消息记录，需要定期进行垃圾回收
如果在每一步操作后执行检查点操作，会非常消耗资源，所以通常在请求序号可以被某个常数K（比如K=100）整除的时候，才会周期性地进行

检查点协议流程

1. 各节点生成

参数

• d：最近一次执行请求的摘要
• n：请求编号
• ：签名

• 追加到本地日志记录中
• 广播给系统内其他节点

2. 各个节点接收checkpoint消息，验证有效后追加到本地日志消息中
3. 各个节点收集到来自其他节点发来的checkpoint消息，收到2f+1个（2f个其他节点的，1个自己的）有效且状态相同的checkpoint消息时，表明这是一个stable-checkpoint
4. 此时，节点会将本地消息日志中客户端请求序列号小于或等于n的消息（pre-prepare、prepare、commit消息）全部删除掉，同时也删除旧的checkpoint消息

通过检查点协议设置高低水位区间（序列号有效范围）

上面是一种理想情况，实际上当副本i向全网发出checkpoint共识后，其他节点可能没有执行完这K条请求，所以副本i不会立即得到响应，它还要继续自己的事情，那么这个checkpoint在它那里就不是stable的，通过设置高低水位区间[h, H]来解决：
最低值h设为最近一次检查点的编号
最高值H设为 H=h+L（一般设置L是K的倍数，例如2倍）

这样即使该副本处理速度很快，它处理的请求编号达到高水位H后也得停一停自己的脚步，直到它的stable checkpoint发生变化，它才能继续向前。

视图变更

每个副本节点会针对视图 v 维持一个计时器，当发现主节点超时异常情况（超时）

请求视图变更

副本节点

1. 拒绝接收和处理消息（除了checkpoint、view-change 和 new-view三种消息）
2. 生成消息

[!参数]

• n：最近一次的稳定检查点对应请求的序列号

• C：证明该检查点稳定性的 2f+1 个checkpoint消息的集合

• P：的集合，当前副本节点未处理完成的pre-prepare和prepare消息集合（m表示副本节点i中序号大于n的等待提交和执行的客户端请求）

每个包含：

• pre-prepare消息（不包含原始请求m）
• prepare消息（2f个由其他副本节点签名，且与pre-prepare消息匹配的）

• 记录到本地日志文件
• 广播给其他节点

请求替换掉主节点，变更到下一视图 v+1

说明

View所属的主节点是计算出的： primary = v % R，R是运行PBFT协议的节点数量。

3. 各个节点收到view-change 消息，进行检验，通过检验则追加到本地日志文件

切换新视图

新主节点

1. 当视图 v+1对应的新主节点接收到其他节点发过来的2f个有效的view-change 消息（不包括自己）
2. 向其他节点发送消息，提议系统内所有节点切换到下一个视图v+1，并接受自己作为新的主节点

参数

• v+1：要变更到的目标视图编号

• V： vew-change 消息集合，由视图 v 变更为视图 v+1 的有效 vew-change 消息的集合

• O：pre-prepare 消息集合，主节点重新发起的未经完成的PRE-PREPARE消息集合

O集合选取规则

• 选取V中最小的stable CheckPoint编号min-s，选取V中prepare消息的最大编号max-s
• 在min-s和max-s之间，如果存在P消息集合，则创建< PRE-PREPARE, v+1, n, d>, m>消息。否则创建一个空的PRE-PREPARE消息，即：< PRE-PREPARE, v+1, n, d(null)>, m(null)>, m(null)空消息，d(null)空消息摘要。

副本节点

• 接收 new-view消息，验证通过，将new-view消息写入本地消息日志
• 进入v+1视图，并开始处理集合O中所有pre-prepare 消息

问题

1. prepare和commit阶段为何都要2f+1个节点反馈确认?

只有当收到2f+1个相同的反馈确认，才能说明正常节点（f+1）都进行反馈了
如果只收到f+1个相同的反馈，有可能是f个恶意节点，1个正常节点，恶意节点的消息时不能作数的（给不同节点发送不同消息）
而如果收到2f+1个相同的反馈，说明f+1个正常节点都进行了返反馈（因为我们限制最多有f个恶意节点），这f个恶意节点无论发什么消息也不影响最终结果，即大多数正常节点达成一致了

另一举证

某副本收到f+1个相同的反馈确认，如果这f+1个反馈中包含faulty节点发过来的消息，是不能作数的，因为faulty节点是墙头草，给副本i发送的消息和副本j发送的消息不一致(类⽐一下一个汉奸跟游击队说⾃己是爱国的，跟⻤子说⾃己是忠⼼的)。必须要2f+1个相同的反馈确认才能保证f+1个non-faulty节点正常，这时候即便f个faulty节点给不同⼈发不同消息也没关系，f+1个non-faulty节点已经形成了统一战线，他们在⼈数上已经多于那些墙头草了，可以达成⼀致了。
(出自：https://zhuanlan.zhihu.com/p/53897982)

2. 客户端为何只需要f+1个相同反馈即可确认？

我们来看最坏情况：这f+1个反馈，来自于f个恶意节点，以及1个正常节点 。那么，仍然至少有一个reply是正常节点发出来的。而这个正常节点的反馈消息，说明在之前的prepare阶段已被f+1个正常节点所认同，所以可以保证该反馈也是大多数正常节点的意见

3. 为什么要三段式提交，两段式可不可以？

• 在主节点诚实的情况下，两阶段可以达成共识
• 在主节点恶意的情况下，两阶段不可以达成共识

Transclude of excalidraw-20220916100942

• 【共识系列.01】PBFT为什么需要三阶段_独倚高楼望月盼归人的博客-CSDN博客
• 【共识系列.01】PBFT为什么需要三阶段 - 知乎
• 为什么PBFT需要三阶段_weixin_44033321的博客-CSDN博客

pbft 的前提是诚实节点状态必须一致，才能继续。三阶段，其实惯用说法是两段提交，也就是节点投两次票。第一次投票结果，节点 i 收到 包括节点 j 的 2f+1个prepare消息后，节点 i 现在可以prepared了。那么节点 j 呢？可能只收到一部分消息，没有prepared。所以要确定2f+1都prepared了，就需要新一轮投票，也就是commit。这个时候能够无论节点i, 还是节点 j 都知道有2f+1个节点prepared了，共识达成。有点像 tcp 三次握手，保证我知道对方知道我的状态。

4. 为什么PBFT算法只能容忍(n-1)/3个作恶节点

总：n 恶：f 好：n-f

好节点数量为n-f，即只要收到n-f个消息就能做出决定。但是这n-f个消息中有可能有f个恶节点冒充的，则最恶劣情况下，正确消息为n-f-f ⇒ n-f-f>f ⇒ n>3f

⇒ 最少：n=3f+1 ⇒ 即：f=(n-1)/3

参考

• 区块链核心技术：拜占庭共识算法之PBFT
• 迅雷链精品课-第13课 PBFT共识算法
• 共识算法-PBFT
• 实用拜占庭容错算法（PBFT）
• 为什么PBFT需要3个阶段消息？ | 登链社区 | 区块链技术社区
• 深入浅出PBFT算法原理 - 简书
• 区块链核心技术：拜占庭共识算法之PBFT_拜占庭节点_啊拉丁的鱼的博客-CSDN博客
• 共识算法系列：PBFT算法关键点综述、优缺点总结 - 知乎
• 共识算法系列之一：raft和pbft算法 - 知乎

其他参考：