区块链在中国（2）：PBFT算法

上一张我们从分布式系统的角度简单叙述了一下 IBM HyperLedger fabric 的一些基本概念、架构和协议信息。其中最为核心的部分就是共识算法（consensus plugin），fabric推荐并实现的就是PBFT这一经典算法。

BFT算法

Client会发送一系列请求给各个replicas节点来执行相应的操作，BFT算法保证所有正常的replicas节点执行相同序列的操作。因为所有的replicas节点都是deterministic，而且初始状态都相同，根据状态机原理（state machine replication），这些replicas会产生相同的结果状态。当Client收到f+1个replicas节点返回的结果时，如果这些结果都一样，因为BFT算法确保了最多有f个replicas出现问题，所以至少有一个replicas是正确的，那么Client收到的这些结果都是正确的。

但是state machine replication的难点在于确保正常replicas节点都以相同的序列执行同样的一些请求，尤其是如何来面对拜占庭故障。PBFT会融合primary-backup [Alsberg and Day 1976] 和 quorum replication
[Gifford 1979]两种技术来序列化请求。

primary-backup

这个机制下有一个叫view的概念，在一个view里，一个replica会是主节点（primary），其余的replicas都叫备份节点（backups）。主节点负责将来自Client的请求给排好序，然后按序发送给备份节点们。但是主节点可能会是faulty的：它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性，并能通过timeout机制检测到主节点是否已经宕掉。当出现这些异常情况时，这些备份节点就会触发view change协议来选举出新的主节点。

The algorithm ensures that request sequence numbers are dense, that is, no sequence numbers are skipped but when there are view changes some sequence numbers may be assigned to null requests whose execution is a no-op.

quorums

quorums有两个重要的属性：

• Intersection： 任意两个quorums至少有一个共同的并且正确的replica
• Availability: 总是存在一个没有faulty replicas的quorum

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

我们先来约定一些符合：

R是所有replicas的集合，每一个replica用一个整数来表示，依次为

{ 0, …, $\vert R$ - 1 }

简单起见，我们定义

$\vert R$ = 3f + 1
f 是最大可容忍的faulty节点

另外我们将一个view中的primary节点定义为replica p&#x