共识算法 PBFT
source link: https://arminli.com/pbft/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
共识算法 PBFT
July 18, 2018
共识算法是分布式系统中一个很重要的概念，多个节点协同工作，如何就某个请求达成一致是一个很复杂的事。PBFT 全称 Practical Byzantine-Fault-Tolerant，是 BFT（拜占庭容错）算法的一种。
在分布式系统中主要有两种故障类型：一是系统的延迟、宕机等非人为错误，称为非拜占庭错误，另一种是人为的作恶比如恶意攻击，这在区块链系统中讨论较多，称为拜占庭式错误，PBFT 属于后者。关于拜占庭容错的理论可以看下其他文章，这篇文章主要描述算法。
PBFT 的相关论文比较多，https://www.microsoft.com/en-us/research/publication/practical-byzantine-fault-tolerance-proactive-recovery/ 这篇比较容易理解，同时有很多开源的实现，https://github.com/gdanezis/pybft 比较完整，符号和 paper 中一致，就是没有注释，不是很容易完全看懂。
Overview
客户端发送请求给副本（去执行一些操作），BFT 保证所有正常的副本以相同的顺序执行相同的操作，如果客户端收到来自 f+1 个节点的相同的响应消息，则共识完成，执行请求；由于这 f+1 个中至少一个是正常的副本，因此可以保证结果是正确的，但是难处在于在一个分布式系统中，如何确保正常的副本以相同的顺序执行相同的请求。
PBFT 使用 primary-backup 和 quorum replication 技术去为请求排序。
primary-backup
在一个 view 中，有一个副本是主节点（primary），其他副本是备份节点（backups）。主节点接收客户端的请求并给它安排一个可用的序号（sequence number）,然后发给备份节点。主节点可能坏掉，比如为不同的请求安排了相同的序号、停止安排序号、序号不连续等等。备份节点会检查序号，并且设置了超时机制以防主节点挂掉。如果主节点挂掉后，view 会切换并且选择新的主节点。
quorum
quorum 有两个重要的属性：
- Intersection：任意两个 quorum 至少有一个公共的正确副本。
- Availability：总有一个没有出错副本的 quorum。
副本将信息写入 quorum 后得到 quorum certificate，这些证书是信息已经被可靠存储的证明。此外 weak certificates 代表至少 f+1 个不同的副本存储信息，这样能保证至少有一个正确的副本存储了信息。
副本的集合用 R 表示，{0,…,|R|-1}，|R|=3f+1，f 是最大故障节点数。
主节点为 p=v mod |R|，
其中 v 是视图号（view number），是连续增加的，这样保证主节点在{0,…,|R|-1}内。
定义集合 quorum 里至少有 2f+1 个副本。
客户端 c 通过广播 <REQUEST,o,t,c> 发送包括操作 o 的请求给副本，其中 t 是时间戳。
当请求最后达成共识后，副本会回复给客户端 <REPLY,v,t,c,i,r> 其中 v 是当前视图号，t 是对应请求的时间戳，i 是副本号， r 是请求操作的执行结果。
客户端收到来自 f+1 个不同副本（具有相同 t 和 r）的回复后（weak certificate），会接受结果 r。由于最多有 f 个副本是坏的，那么这就保证结果是有效的，称之为 reply certificate。
若客户端未在一定时间内收到 reply certificate，它会再次发送请求，如果请求已经被处理了，副本会再次发送回复，因此副本需要记住它对每一个客户端回复的上一个消息。如果主节点没有为请求安排合适的序号，它就会被其他节点怀疑坏掉，足够多时会造成主节点更换（view change）。
对于客户端数量带来的可扩展性，可以通过限制活跃客户端数量来解决。
我们使用三段协议去自动广播请求给副本：pre-prepare，prepare，commit。下图是没有故障节点时的算法总览：
pre-prepare
主节点 p （0 号副本）收到客户端请求 m (m=<REQUEST,o,t,c> )后，分配序号为 n，广播 pre-prepare 信息给备份节点，格式为 <PRE-PREPARE,v,n,D(m)>，其中 v 是视图号，D(m) 是 m 的 digest。
n 要在低水位 h 和高水位 H 之间，保证垃圾回收机制和防止出错的主节点随意选择序号。
如果其他备份节点已经收到了包含 v 和 n 但不同 digest 的 PRE-PREPARE，那么它就不会接受（not accept）。
prepare
备份节点进入 prepare 节点，向其他副本广播 <PREPARE,v,n,D(m),i>，同时会将 PRE-PREPARE 和 PREPARE 的信息写入日志。
每个副本收到 2f 个一致的 PREPARE 后会得到 prepared certificate，证明了这个 quorum 一致同意视图 v 内 m 的序号为 n。
commit
副本 i 广播 <COMMIT,v,n,i> 来宣布自己已经拥有了 prepared certificate，当副本收到 2f+1 个来自不同副本（包括自己）的 COMMIT 后（n, v 相同），获得 committed certificate。
每个副本按照客户端请求的顺序执行请求，然后回复客户端。
已经执行过的请求的相关日志应该被删除，但是其中包含的 prepared certificate 可能在后面被使用，所以应该什么时候删除呢？
每个副本在执行请求后可以广播全网说可以删掉 log 了，但是每个请求后都发成本比较高，因此设计 checkpoint period K，每 K 个请求广播一次，这个 checkpoint 称为 stable checkpoint。
副本 i 到达 checkpoints 时向其他副本广播 <CHECKPOINT,n,d,i>，其中 n 是上一请求序号，d 是 digest，其他副本收到 2f+1 （包括自身）个 CHECKPOINT 消息后，会删掉所有序号小于等于 n 的 log 和之前的 checkpoints。
但在实际的系统中，每个副本都不是同步的，所以高低水位限制了什么样的消息能够添加到 log 中。高水位 H=h+L，其中 L 是 log size，低水位 h 是上一个 stable checkpoint 的序号。高水位一般是 K 的倍数，而且比较小，比如 2 倍，因此如果有的副本执行的比较快的话，需要等一等其他副本，这个区间足够了。
view change 协议主要发生在主节点故障时，新的 view 如何保持上一 view 的状态，以及如何处理未完成的请求。
副本需要用两个集合 P 和 Q 记录之前 view 里的信息，系统正常时这两个集合是空的。
副本 i 的集合 P 存储了之前 view 中到达 prepared 状态的请求，数据结构为 <n,d,v> 意为副本 i 收集到 view v 中序号为 n，digest 为 d 的请求的 prepared certificate，并且副本 i 上的下一个 view 中就不能有相同序号的请求。
Q 存储了之前 view 中到达 pre-prepared 状态，<n,d,v> 意为 i 已经 pre-prepare 了一个请求并且在下一 view 中这个请求没有相同序号的 pre-prepare。
View-Change Messages
下图展示了从 v 切换到 v+1 时的 view change 协议。当备份节点 i 怀疑视图 v 下的主节点作恶之后，它会切换到 v+1 中并且广播 <VIEW-CHANGE,v+1,C,P,Q,i>，其中 h 是副本 i 的最新 stable checkpoint，C 是每个 checkpoint <序号, digest> 的集合，P 和 Q 上上一节描述的。
View-Change-Ack Messages
副本收集 VIEW-CHANGE 消息后发送 acknowledgments 以达成切换到 v+1 的共识，<VIEW-CHANGE-ACK,v+1,i,j,d> 其中 i 是发送者的标识，d 是 acknowledged VIEW-CHANGE message 的 digest，j 是发送 VIEW-CHANGE 消息的副本。
接下来是 New-View Message Construction 和 New-View Message Processing，属于比较细节的处理，这里不再介绍。
Recommend
-
122
DPOS区块链技术是近几年逐渐变得非常热门的技术，以比特币为首的密码货币其实已经被无数人所知晓，但是却很少有人会去研究它们的底层技术，也就是作为一个分布式网络比特币等加密货币是如何工作的。
-
113
谈谈共识算法 ...
-
117
DPOS共识算法——缺失的白皮书
-
81
区块链主流共识算法的浅析
-
151
1研究 工作量证明(Proof Of Work，简称POW)，简单理解就是一份证明，用来确认你做过一定量的工作。监测工作的整个过程通常是极为低效的，而通过对工作的结果进行认证来证明完成了相应的工作量，则是一种非常高效的方式。比如现实生活中的毕业证、驾驶证等等，也是...
-
77
-
69
0.前言 本文记录笔者学习和理解区块链共识算法Paxos的点滴，文章比较长，需要耐心来细细琢磨，笔者也是苦战了一个周末才对此有那么一点初步了解，有问题的地方请不吝斧正！ 1.初始是阅读本文后续内容的基础，概念性的东西叙述不多，干货干货干货在后面的代码实战。...
-
52
作者：黎跃春 孔壹学院创始人兼CEO 黎跃春：孔壹学院创始人兼CEO，国内区块...
-
10
pBFT为什么不要三个阶段，看完你就知道。 实用拜占庭容错算法，简称pBFT，是首个可以在实际应用场景中相对高效的...
-
5
Kid1999' Blog分布式一致性协议之Pbft算法发表于2021-10-26|更新于2021-10-26|区块链字数总计:2...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK