深入理解PBFT算法——提交阶段的作用

文章目录

• 1. 前述
• 2. PBFT算法的QC性质
• 3. 提交阶段的作用
  • 3.1 前两个阶段
  • 3.2 假设只有两个阶段
  • 3.3 提交阶段的作用

1. 前述

PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错算法）是联盟链常用的一种共识算法。本文讨论PBFT提交阶段的作用，要求读者对PBFT的算法有一个大致了解，如果你是刚听过这个算法，知道算法的基本流程，看完本文可能会对PBFT有更深入的理解；如果你研读过PBFT原论文，那么本文也许可以作为阅读拓展。如果有不同理解或者认为文中表述有问题，欢迎讨论指正。

2. PBFT算法的QC性质

在讨论主题之前，我们需要先了解PBFT算法的QC性质，这是证明PBFT正确性的重要前提。

Q 和 C 分别表示 Quorum 和 Certificate。

• Quorum 意思为 仲裁数，法定人数。在PBFT中，当总节点数为3f+1时（用 f 表示拜占庭节点数量时，总节点数大于等于 3f+1 时拜占庭问题才有解，这个问题的证明不在本文的讨论范围），Quorum 表示数量不少于 2f+1 的节点集合。
• Quorum certificate 则表示来自一个Quorum的每个节点的某种消息组成的一个集合，称为证书，如准备证书和提交证书。

Quorum 有两个重要的性质：

1. 相交性: 任何两个 Quorum 至少有一个共同的正确节点。
2. 可得性: 总能找到一个没有错误节点的 Quorum 。

Intersection property: any two quorums have at least one correct replica in common. Availability property: there is always a quorum available with no faulty replicas.

这两个性质贯穿了PBFT的整个证明过程，特别是性质1。

第一个性质，我们可以用一个图直观地理解：

图1. Quorum 的相交性

我们在一个大小为3f+1的集合中，画两个2f+1子集，并且使得交集尽可能地小，可以看到，即使尽最大的努力减小交集，最小的交集还是f+1，即交集中至少有一个正确节点。

另外，当 f=1 时，3f+1=4，当 f=2 时，3f+1=7，那么当总节点数等于5或6时，Quorum 的数量该如何计算呢？我们记总节点数为N，且 3f+1≤N＜3(f+1)+1 ，则一个 Quorum 的数量不少于\lceil\frac{2N}{3}\rceil ，其中\lceil\rceil 表示向上取整，推导：

设 Quorum 的数量为x，为了满足性质1，两个 Quorum 的交集大小至少为 f+1，则有

由 3f+1≤N＜3(f+1)+1 ，即 \frac{N-1}{3}-1＜f≤\frac{N-1}{3} ，可得 f = \lfloor\frac{N-1}{3}\rfloor ，其中\lfloor\rfloor 表示向下取整，带入上式，并由\lfloor\frac{n}{m}\rfloor=\lceil\frac{n+1}{m}\rceil-1 1有：

因为x为整数，可对上式右侧向上取整，得：

转化为向下取整可以方便转化为编程语言（编程语言的整数除法一般为向下取整）。

N=3f+1时带入校验，同样满足上式。

3. 提交阶段的作用

3.1 前两个阶段

PBFT包含三个阶段：预准备阶段、准备阶段、提交阶段。

图2. PBFT算法大致流程

准备阶段收集2f+1个来自不同节点的序列号相同、请求相同的准备消息（可以含1个预准备消息），这一步确保了请求顺序在所有正确节点上达成一致。这利用了性质1，对于任意两个节点来说，如果他们分别收到了2f+1个来自不同节点的序列号相同的准备消息，那么一定有一个消息来自一个共同的正确节点，再加上正确节点不会对同一个请求发送两个序列号不同的消息（算法决定），所以他们收到的准备消息的序列号一定相同。

前两个阶段是用于同一个视图内保证请求的顺序一致，提交阶段是用于保证跨视图（主节点切换）的请求顺序一致。也就是说，如果没有视图切换，前两个阶段已经能够保证顺序一致。

3.2 假设只有两个阶段

为了看清提交阶段的作用，我们假设没有这个阶段，看是否能够保证算法的正确（安全性和活动性），或者说，我们能否设计出一个算法，可以将提交阶段去除。

我们考虑四个节点的情况，节点1为主节点、且为恶意节点，在一次共识周期中，主节点向节点3和4发送编号为n、请求为m的预准备消息，向节点2发送编号为n、请求为m’(与m不同)的预准备消息，假设在一定时间之后，节点3收集到了准备证书（2f个准备消息和1个预准备消息），并执行了该请求，对客户端进行了响应。

图3. 假设没有提交阶段

假设此时发生了主节点切换，新的主节点为节点2，我们知道，节点2并没有收集到请求m的准备证书，但由于此时节点3认为该请求已达成共识，并且已经执行了该请求，所以请求m必须被重放，以使得所有节点达成一致。为了重放请求m，节点2需要收集来自其他节点的准备证书，假设只有节点3收集到了准备证书，那么只有保证节点2能够收到来自节点3的准备证书，才能重放该请求。

我们尝试能否通过设计一定的算法来达到这样的目的：在视图切换的时候，所有节点向新的主节点发送已有的准备证书，主节点收集这些证书并对这些请求进行重放，那么主节点要在什么时候停止收集证书呢？假设是收到2f+1个节点的消息时，停止收集，那就可能错过节点3的准备证书；所以不难得出，必须收集所有节点的消息，才能停止，但这更是不可能的，因为拜占庭节点可以选择不发送消息。可见，设计出这样的算法是不太可能的。

3.3 提交阶段的作用

那么提交阶段是如何解决这个问题的呢？通过以上的讨论，我们可以看到，如果收集到准备证书就执行请求，此时由于可能没有足够的节点收集到了准备证书，所以后续无法保证在切换主节点之后，该请求能够被重放（被其他节点执行）。因此，每个节点应该在获知有足够的节点收集到准备证书之后，再执行请求，提交阶段就是做了这样的事情。

首先，提交阶段要求节点收集到2f+1个提交消息之后，才进入已提交状态，此时节点执行该请求并对客户端进行响应。这个要求保证了在执行请求的时候，已经有2f+1个节点收集到了准备证书，这对于后续请求的重放起了关键作用。

在主节点切换时，节点在广播的View-Change消息中包含了（所有未达到稳定检查点的）准备证书，新主节点发出的New-View消息之前，至少收集2f+1个节点的View-Change消息。假设请求m在主节点切换之前已经被提交了，也就是有2f+1个节点持有它的准备证书，由PBFT算法的QC性质1，这**2f+1**个节点与New-View消息中的**2f+1**个节点，一定有一个共同的正确节点，也就是被提交的请求一定会在新的视图中重放，这解决了跨视图的一致性问题。

综上所述，提交阶段是用于与View-Change配合，保证在上一视图中执行的请求，可以在新的视图中重放，并且编号n相同，即保证了跨视图请求顺序的一致性。

参考：

• Practical Byzantine Fault Tolerance
• Useful Properties of the Floor and Ceil Functions
• Floor and ceiling functions
• https://en.wikipedia.org/wiki/Floor_and_ceiling_functions ↩︎