PBFT

摘要&＃xff1a;

PBFT是Practical Byzantine Fault Tolerance的缩写&＃xff0c;即&＃xff1a;实用拜占庭容错算法。该算法是Miguel Castro&＃xff08;卡斯特罗&＃xff09;和Barbara Liskov&＃xff08;利斯科夫&＃xff09;在1999年提出来的&＃xff0c;解决了原始拜占庭容错算法效率不高的问题&＃xff0c;算法的时间复杂度是O(n^2)&＃xff0c;使得在实际系统应用中可以解决拜占庭容错问题。该论文发表在1999年的操作系统设计与实现国际会议上&＃xff08;OSDI99&＃xff09;。其中Barbara Liskov就是提出了著名的里氏替换原则&＃xff08;LSP&＃xff09;的人&＃xff0c;2008年图灵奖得主。以下拜占庭容错问题简称BFT。

BFT是区块链共识算法中&＃xff0c;需要解决的一个核心问题&＃xff0c;以比特币和以太访为代表的POW&＃xff0c;EOS为代表的DPOS&＃xff0c;以及今后以太访逐渐替换的共识算法POS&＃xff0c;这些都是公链算法&＃xff0c;解决的是共识节点众多情况下的BFT。而PBFT是在联盟链共识节点较少的情况下BFT的一种解决方案。

网上已经有很多关于PBFT算法的描述&＃xff0c;但是写的都不是很明白&＃xff0c;本文以一种更为清晰易懂的方法&＃xff0c;彻底讲明白PBFT算法原理。下一篇文章将会结合fabric-0.6.0-preview 中的代码&＃xff0c;讲解超级账本项目是如何实现PBFT算法的。

本文假设读者已经理解什么是BFT问题。

PBFT算法流程&＃xff1a;

PBFT算法前提&＃xff0c;采用密码学算法保证节点之间的消息传送是不可篡改的。

PBFT容忍无效或者恶意节点数&＃xff1a;f&＃xff0c;为了保障整个系统可以正常运转&＃xff0c;需要有2f&＃43;1个正常节点&＃xff0c;系统的总节点数为&＃xff1a;|R| &＃61; 3f &＃43; 1。也就是说&＃xff0c;PBFT算法可以容忍小于1/3个无效或者恶意节点&＃xff0c;该部分的原理证明请参考PBFT论文&＃xff0c;下文有链接地址。

PBFT是一种状态机副本复制算法&＃xff0c;所有的副本在一个视图&＃xff08;view&＃xff09;轮换的过程中操作&＃xff0c;主节点通过视图编号以及节点数集合来确定&＃xff0c;即&＃xff1a;主节点 p &＃61; v mod |R|。v&＃xff1a;视图编号&＃xff0c;|R|节点个数&＃xff0c;p&＃xff1a;主节点编号。

PBFT算法主体实现流程图如下&＃xff1a;

以下详细说明&＃xff0c;每个主体流程内容&＃xff1a;

1. REQUEST&＃xff1a;

客户端c向主节点p发送请求。o: 请求的具体操作&＃xff0c;t: 请求时客户端追加的时间戳&＃xff0c;c&＃xff1a;客户端标识。REQUEST: 包含消息内容m&＃xff0c;以及消息摘要d(m)。客户端对请求进行签名。

2. PRE-PREPARE&＃xff1a;

主节点收到客户端的请求&＃xff0c;需要进行以下交验&＃xff1a;

a. 客户端请求消息签名是否正确。

非法请求丢弃。正确请求&＃xff0c;分配一个编号n&＃xff0c;编号n主要用于对客户端的请求进行排序。然后广播一条<, m>消息给其他副本节点。v&＃xff1a;视图编号&＃xff0c;d客户端消息摘要&＃xff0c;m消息内容。进行主节点签名。n是要在某一个范围区间内的[h, H]&＃xff0c;具体原因参见垃圾回收章节。

3. PREPARE&＃xff1a;

副本节点i收到主节点的PRE-PREPARE消息&＃xff0c;需要进行以下交验&＃xff1a;

a. 主节点PRE-PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了一条在同一v下并且编号也是n&＃xff0c;但是签名不同的PRE-PREPARE信息。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。正确请求&＃xff0c;副本节点i向其他节点包括主节点发送一条消息, v, n, d, m与上述PRE-PREPARE消息内容相同&＃xff0c;i是当前副本节点编号。进行副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中&＃xff0c;用于View Change过程中恢复未完成的请求操作。

4. COMMIT&＃xff1a;

主节点和副本节点收到PREPARE消息&＃xff0c;需要进行以下交验&＃xff1a;

a. 副本节点PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. n是否在区间[h, H]内。

d. d是否和当前已收到PRE-PPREPARE中的d相同

非法请求丢弃。如果副本节点i收到了2f&＃43;1个验证通过的PREPARE消息&＃xff0c;则向其他节点包括主节点发送一条消息&＃xff0c;v, n, d, i与上述PREPARE消息内容相同。进行副本节点i的签名。记录COMMIT消息到日志中&＃xff0c;用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的PREPARE消息到log中。

5. REPLY&＃xff1a;

主节点和副本节点收到COMMIT消息&＃xff0c;需要进行以下交验&＃xff1a;

a. 副本节点COMMIT消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。如果副本节点i收到了2f&＃43;1个验证通过的COMMIT消息&＃xff0c;说明当前网络中的大部分节点已经达成共识&＃xff0c;运行客户端的请求操作o&＃xff0c;并返回给客户端&＃xff0c;r&＃xff1a;是请求操作结果&＃xff0c;客户端如果收到f&＃43;1个相同的REPLY消息&＃xff0c;说明客户端发起的请求已经达成全网共识&＃xff0c;否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的COMMIT消息到log中。

垃圾回收&＃xff1a;

在上述算法流程中&＃xff0c;为了确保在View Change的过程中&＃xff0c;能够恢复先前的请求&＃xff0c;每一个副本节点都记录一些消息到本地的log中&＃xff0c;当执行请求后副本节点需要把之前该请求的记录消息清除掉。最简单的做法是在Reply消息后&＃xff0c;再执行一次当前状态的共识同步&＃xff0c;这样做的成本比较高&＃xff0c;因此可以在执行完多条请求K&＃xff08;例如&＃xff1a;100条&＃xff09;后执行一次状态同步。这个状态同步消息就是CheckPoint消息。

副本节点i发送给其他节点&＃xff0c;n是当前节点所保留的最后一个视图请求编号&＃xff0c;d是对当前状态的一个摘要&＃xff0c;该CheckPoint消息记录到log中。如果副本节点i收到了2f&＃43;1个验证过的CheckPoint消息&＃xff0c;则清除先前日志中的消息&＃xff0c;并以n作为当前一个stable checkpoint。

这是理想情况&＃xff0c;实际上当副本节点i向其他节点发出CheckPoint消息后&＃xff0c;其他节点还没有完成K条请求&＃xff0c;所以不会立即对i的请求作出响应&＃xff0c;它还会按照自己的节奏&＃xff0c;向前行进&＃xff0c;但此时发出的CheckPoint并未形成stable&＃xff0c;为了防止i的处理请求过快&＃xff0c;设置一个上文提到的高低水位区间[h, H]来解决这个问题。低水位h等于上一个stable checkpoint的编号&＃xff0c;高水位H &＃61; h &＃43; L&＃xff0c;其中L是我们指定的数值&＃xff0c;等于checkpoint周期处理请求数K的整数倍&＃xff0c;可以设置为L &＃61; 2K。当副本节点i处理请求超过高水位H时&＃xff0c;此时就会停止脚步&＃xff0c;等待stable checkpoint发生变化&＃xff0c;再继续前进。

View Change&＃xff1a;

如果主节点作恶&＃xff0c;它可能会给不同的请求编上相同的序号&＃xff0c;或者不去分配序号&＃xff0c;或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性。如果主节点掉线或者作恶不广播客户端的请求&＃xff0c;客户端设置超时机制&＃xff0c;超时的话&＃xff0c;向所有副本节点广播请求消息。副本节点检测出主节点作恶或者下线&＃xff0c;发起View Change协议。

副本节点向其他节点广播C, P, i>消息。n是最新的stable checkpoint的编号&＃xff0c;C是2f&＃43;1验证过的CheckPoint消息集合&＃xff0c;P是当前副本节点未完成的请求的PRE-PREPARE和PREPARE消息集合。

当主节点p &＃61; v &＃43; 1 mod |R|收到2f个有效的VIEW-CHANGE消息后&＃xff0c;向其他节点广播V, O>消息。V是有效的VIEW-CHANGE消息集合。O是主节点重新发起的未经完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的选取规则&＃xff1a;

1. 选取V中最小的stable checkpoint编号min-s&＃xff0c;选取V中prepare消息的最大编号max-s。

2. 在min-s和max-s之间&＃xff0c;如果存在P消息集合&＃xff0c;则创建<, m>消息。否则创建一个空的PRE-PREPARE消息&＃xff0c;即&＃xff1a;<, m(null)>, m(null)空消息&＃xff0c;d(null)空消息摘要。

副本节点收到主节点的NEW-VIEW消息&＃xff0c;验证有效性&＃xff0c;有效的话&＃xff0c;进入v&＃43;1状态&＃xff0c;并且开始O中的PRE-PREPARE消息处理流程。

总结&＃xff1a;

PBFT算法由于每个副本节点都需要和其他节点进行P2P的共识同步&＃xff0c;因此随着节点的增多&＃xff0c;性能会下降的很快&＃xff0c;但是在较少节点的情况下可以有不错的性能&＃xff0c;并且分叉的几率很低。PBFT主要用于联盟链&＃xff0c;但是如果能够结合类似DPOS这样的节点代表选举规则的话也可以应用于公联&＃xff0c;并且可以在一个不可信的网络里解决拜占庭容错问题&＃xff0c;TPS应该是远大于POW的。

参考&＃xff1a;

拜占庭容错(Byzantine Fault Tolerance) WIKI: BFT - Wikipedia

PBFT论文地址&＃xff1a;http://pmg.csail.mit.edu/papers/osdi99.pdf

作者&＃xff1a;ether029
链接&＃xff1a;https://www.jianshu.com/p/78e2b3d3af62