区块链100讲：Fabric的PBFT算法

内容来源：区块链兄弟

原文来源：zhj_fly的博客

《区块链100讲》专栏策划及内容编辑：HiBlock区块链社区Cynthia

如需转载，需申请并注明专栏及原文出处。

在公有链中用的最多的是pow算法和pos算法，这些算法都是参与者的利益直接相关，通过利益来制约节点诚实的工作，解决分布式系统中的拜占庭问题。拜占庭容错算法是一种状态机副本复制算法，通过节点间的多轮消息传递，网络内的所有诚实节点就可以达成一致的共识。

使用拜占庭容错算法不需要发行加密货币，但是只能用于私有链或者联盟链，需要对节点的加入进行权限控制；不能用于公有链，因为公有链中所有节点都可以随意加入退出，无法抵挡女巫攻击（sybil attack）。下面主要介绍Fabric的PBFT算法。

1

系统模型

该系统要达成的目的是：让所有正常的replicas节点执行相同的序列操作。

1、系统假设是异步分布式的，通过网络传播的消息可能丢失、延迟、重复或乱序，节点可能失效但节点失效是相互独立的。传递的消息都是通过签名的，恶意节点可以控制失效节点，但是不能够篡改正常节点的签名信息。

2、安全性：在R>=3f+1的前提下，系统能保持安全性和活性。R为总结点数，f为错误节点数。

3、角色分工：

replica（副本）所有参与的节点，总数为R

primary（主节点）：负责将来自client的请求排好序，然后发给所有的备份节点。

backup（备份节点）：接收并检查主节点的排序信息，如果主节点作恶可以进行换选。

其中主节点的选举方法是：p = v mod R ，其中v是系统的view编号，每次换选时发生view change，view编号+1。

4、quorums

quorums有两个重要的属性：

Intersection： 任意两个quorums至少有一个共同的并且正确的replica

Availability: 总是存在一个没有faulty replicas的quorum

如果一个replica把信息写给一个quorum，并让该quorum来存储信息，在收到每一个quorum中的成员的确认反馈后，那么我们可以认为该replica的信息已经被可靠的保存在了这个分布式系统中。这是强的约束，当然还有一个weak certificates：就是至少f+1个节点来共同存取信息，这样至少有一个正确的replica存到了这份信息。

2

算法流程

PBFT算法通过三阶段广播协议来使所有正常节点按相同的顺序执行请求，三阶段分别为pre-prepare、prepare和commit。执行流程如图所示。

prepare阶段和commit阶段用来确保那些已经达到commit状态的请求即使在发生view change后在新的view里依然保持原有的序列不变，比如一开始在view 0中，共有req 0， req 1， req2三个请求依次进入了commit阶段，假设没有坏节点，那么这四个replicas即将要依次执行者三条请求并返回给Client。但这时主节点问题导致view change的发生，view 0 变成 view 1，在新的view里，原本的req 0， req1， req2三条请求的序列被保留，作数。那些处于pre-prepare和prepare阶段的请求在view change发生后，在新的view里都将被遗弃，不作数。

pre-prepare阶段

主节点收到client发送的一条请求，给这条请求编号为n，然后想所有的备份节点发送pre-prepare消息，消息的格式为

, m>，其中v是视图view编号，m是请求的消息，d是请求消息的摘要。当满足一下条件时，备份节点会接受这条pre-prepare消息，进入prepare阶段。

1、请求和预准备消息的签名正确，并且d与m的摘要一致。

2、当前视图编号是v。

3、该备份节点从未在视图v中接受过序号为n但是摘要d不同的消息m。

4、预准备消息的序号n必须在水线（watermark）上下限h和H之间。

prepare阶段

备份节点i进入prepare阶段后，发送一条prepare消息给所有的副本节点，消息格式为

，同时接收其他节点发送的prepare消息。

所有副本节点在收到准备消息之后，对消息的签名是否正确，视图编号是否一致，以及消息序号是否满足水线限制这三个条件进行验证，如果都正确则接受。（这个阶段是防止主节点作恶）如果从2f个不同的副本收到的prepare消息与pre-prepare消息一致，即连同自己一共2f+1个确认，那么这个节点就处于prepared状态，同时拥有一个prepared certificate证书。然后进入commit阶段。

预准备阶段和准备阶段确保所有正常节点对同一个视图中的请求序号达成一致。

commit阶段

进入commit阶段的节点i会广播一条commit消息给其他所有节点，消息格式为,同时接收其他节点发送的commit消息，每个副本接受确认消息的条件是：

1）签名正确；

2）消息的视图编号与节点的当前视图编号一致；

3）消息的序号n满足水线条件，在h和H之间。

如果满足以上条件，则接受消息。如果从不同的节点收到2f+1（包括自己）条commit消息且都正确，那么这个节点进入committed状态，并拥有一个committd certificate。然后向客户端返回请求。

其中watermark的作用是：

我们想象一种情况，主节点是坏的，它在给请求编号时故意选择了一个很大的编号，以至于超出了序号的范围，所以我们需要设置一个低水位（low water mark）h和高水位（high water mark）H，让主节点分配的编号在h和H之间，不能肆意分配。

三阶段到此结束，客户端等待f+1个相同的副本结果作为最后结果。

3

垃圾回收

节点在一次三阶段协议中收到的pre-prepre,prepare,commit等消息是非常多的,这小消息都要记录在本地的日志中，为了节省存储空间,可以把已经确认无误的消息给清除掉。只有当至少f+1个节点执行了请求的消息的时候，才能将相应的日志删除。

于是，当一个节点执行完某条请求后，可以广播一条消息，当全网有2f+1个节点都执行完这条请求后就可以删除它的日志了。但是每条消息都进行广播来确认是否删除是低效的，所以可以k条消息放一起确认，每当k条请求执行完后，就广播一条消息，当2f+1个节点都执行完这个请求后，就可以将这k条请求的日志删除了。

这就是建立检查点checkpoint，当节点i执行完k条请求后，就生成一个checkpoint，并广播checkpoint消息：，n是最近一个影响状态的请求序号，d是状态的摘要。当有2f+1个检查点消息时，就证明这个检查点是正确的，形成一个stable checkpoint。具有这个stable checkpoint的节点就可以将所有序号小于等于n的pre-prepare,prepare,commit消息，以及之前的检查点和检查点消息删除。

但是由于节点的执行速度不同，要使不同的节点的检查点维持在一个范围内，最快的几点与最慢的节点之间最多差L个检查点。这里又用到了水线watermark，用检查点协议来更新水线的高低值（h和H），这两个高低值限定了可以被接受的消息。水线的低值h与最近稳定检查点的序列号相同，而水线的高值H=h+L，L需要足够大才能使副本不至于为了等待稳定检查点而停顿。

4

视图变现

以下内容直接从这篇文章（https://blog.csdn.net/bluecloudmatrix/article/details/51898105?utm_source=tuicool&utm_medium=referral）中摘取过来，原文讲的很明白。

当主节点挂掉后就触发了view change协议。我们需要确保在新的view中如何来延续上一个view最终的状态，比如给这时来的新请求的编号，还有如何处理上一个view还没来得及完全处理好的请求。

Data Structures

所以我们需要记录上一个view里发生什么。

有两个集合P和Q，replica i 的P存着 i 在上一 view 中达到prepared状态的请求的一些信息，有了P，在新的view中，replica i就会明白接下来处于prepared状态的请求不能与上一个view中处于prepared状态的请求的编号相同。Q是记录在上一个view里到达pre-prepared状态的请求的一些信息。

View-Change Messages

我们来看一下Fig 2， 当备份节点 i 怀疑 view v中的主节点出问题（比如是坏节点）后，它会进入 view v+1，并广播一条VIEW-CHANGE信息给所有的replicas，其中包含该replica i最新的stable checkpoint的编号，还有 replica i上存的每一个checkpoint的编号和digest的集合，还有上面所说的该replica的P和Q两个集合。

View-Change-Ack Messages

replicas 会收集VIEW-CHANGE信息并发送ACK确认给 view v+1 中的主节点。

新的主节点收集了VIEW-CHANGE和VIEW-CHANGE-ACK（包含自己的信息），它会将VIEW-CHANGE存在一个集合S中。主节点需要选出一个checkpoint作为新view处理请求的起始状态。它会从checkpoint的集合中选出编号最大（假设编号为h）的checkpoint。接下来，主节点会从h开始依次选取h到h+L（L就是normal case阶段我们提到的设置值）之间的编号n对应的请求在新的view中进行pre-prepare，如果一条请求在上一个view中到达了committed状态，主节点就选取这个请求开始在新的view中进行三阶段。

之所以选取committed的请求，是因为上面我们提到增加COMMIT阶段为了across view来考虑的，处于committed状态的请求的编号在新的view中是有效的，可以继续使用。但是如果选取的请求在上一view中并没有被一个quorum给prepare，那它的编号n有可能是不被一个quorum给同意的，我们选择在新的view中作废这样的请求。

参考文章：

https://blog.csdn.net/bluecloudmatrix/article/details/51898105?utm_source=tuicool&utm_medium=referral#commentBox

https://www.jianshu.com/p/fb5edf031afd

--- 线上课程推荐 ---

--- 线下活动推荐 ---