在公有链中用的最多的是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里都将被遗弃，不作数。

假设replica 0为主节点，下面详细介绍三阶段：

• pre-prepare阶段

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

3

垃圾回收

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

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

这就是建立检查点checkpoint，当节点i执行完k条请求后，就生成一个checkpoint，并广播checkpoint消息：

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

内容来源：区块链兄弟

原文来源：zhj_fly的博客

原文链接：http://t.cn/RdHmOvo

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

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

以下是我们的社区介绍，欢迎各种合作、交流、学习：）