共识协议 PBFT 协议的理解

PBFT 是一种分布式节点间的状态复制协议,在总节点数为n的情况下,它能容错不超过 $\lfloor \frac {n-1}{3} \rfloor$ 的拜占庭节点,使得大多数的状态复制机(replica)保持一致的状态。保持分布式节点之间的系统状态的一致性,只需要做到如下两点即可:

系统中节点就 client 的 request 分配一个唯一的编号,并且对于系统中任意两个非故障节点,同一个 request 对应相同并且唯一的编号.
系统中的节点有序的执行 request ,保证任意两个非故障节点的系统状态一致.

PBFT 协议通过完成上述两个要求从而实现了系统的一致性.在介绍PBFT协议的具体内容前,应该首先明确该协议的系统模型.

一、系统模型

网络是异步的分布式网络,网络中节点之间会出现信息发送失败, 延迟,重复发送,甚至无序的情况.
系统中可能有一个强力的恶意节点联合其他节点,故意导致发送信息出现延迟或者故意延迟正确的节点发送的信息,但是恶意节点不能无限延迟.
恶意节点无法伪造诚实节点的签名,而恶意节点之间可能串通,可以相互伪造签名.
恶意节点无法通过一条消息的摘要计算出消息体.
恶意节点无法针对一个消息m,找到另外一个对应的消息m’使得它们的摘要相同.(摘要是对消息求hash).
系统中总结点数为n的时候, PBFT协议最多容忍 $\lfloor \frac{n-1}{3}\rfloor$ 的拜占庭节点.

二、系统角色

Replica, 状态复制机,所有的 replica 都会执行 PBFT 协议并保持系统状态一致性.
Primary, 在 PBFT 协议中,每个 primary 都有一个任期,称之为 view, 在一个 view 中,只有一个 replica 会被称为 primary,可以理解为leader.
Backup,除了primary 以外的 replica 都称之为backup.
client, 向 primary 发送 request 请求服务的客户端.

三、PBFT协议简述

PBFT 协议以状态机复制的形式展示,将服务建立为在分布式环境下跨机器之间进行数据复制的状态机模型. 每一个状态复制机都会维护一个当前的服务状态,PBFT 协议可以保证所有非拜占庭节点的系统状态全部相同, 而这些状态复制机执行客户的请求后转入下一个状态,并将执行结果反馈给 client.

在PBFT协议中,主要有三个身份,client,primary 和 backup。replica 中有一个主节点,称之为primary, 其他 replica 称之为backup. client向 primary 发出操作请求, primary 把 client 的请求发送给所有 backup , primary和其他backup通过按照PBFT协议对操作进行响应,然后将执行结果返回给client.

PBFT论文中默认client在收到前一个 request 的执行结果之前不会发送下一个 request .每一个primary在其任期内对应一个view, 下一任primary上任时,view自动加1. 一个view中只有一个primary.

整个协议的整体流程如下:

client向 primary发送一个 request .
primary向其他备份节点广播 request .
所有节点执行 request 并且向client返回执行结果
client 从f+1个不同的节点处得到相同的执行结果,则认为执行结果可靠并且接受这个结果.

PBFT 细节

再次强调的是，在该协议中,假定拜占庭节点的数目最多为 $f$ 个, 而全体节点的数目为 $n = 3f+1$ .

1. client 发出 request

client 向 primary 发出一个 request , request 的具体形式如下:

$<REQUEST, o,t,c>_{\sigma i}$

$o$ 表示 operation,即具体执行的操作, t 表示 timestamp, 之所以需要加上时间戳, 是在一个client在发出多次相同operation的时候, primary 用 timestamp 区分这些命令, c 表示 client 编号, $\sigma i$ 表示 client $i$ 将这些信息进行签名,以证实自身合法的身份.

注意: 如果 client 将 request 发送给了 backup 节点,那么该节点会将 client 的 request 转发给 primary.

2. pre-prepare 阶段

为了确保所有的非拜占庭节点保持一致的状态, primary 需要对 request 分配一个序号(sequence number),如果全体 replica 能够对每一个 request 的序号达成一致,那么就能达成整个系统服务状态的一致性.

2.1 Primary 收到 Request

收到一个 request 时，primary会检查 request 的合法性,首先检查客户端的签名是否正确, 如果不正确,则拒绝执行后续步骤;

如果正确,则给 request分配一个唯一的序列号n,然后向其他 backup 广播一条 $pre-prepare$ (预准备)消息,形式如下:

$\left < \left < PRE-PREPARE, v, n, d \right > _{\sigma p}, m \right >$

$v$ 是当前view序号, $n$ 是 primary 为 request 分配的序列号, d是 request 的摘要, m 代表 client的 request 信息, $\sigma_p$ 是 primary 的签名.

2.2 Backup 收到 pre-prepare消息

backup收到pre-prepare消息时,会验证如下消息:

request 的签名是否正确, 确保client的签名不是伪造的.
view的序列号与当前backup当前的view序列号相等.
backup确定当前 view下,序号n没有分配给另外一个不同的 request .
n应该在某个范围[h, H].

如果上述条件全部符合,则backup接受这个 $pre-prepare$ 消息, 并且进入 prepare 阶段.

3. prepare阶段

3.1 广播 Prepare 消息

对于 Prepare 阶段做一下解释，节点收到 pre-prepare 消息之后，相当于收到了一个来自 primary 的提议，但是节点不清楚其他节点是否收到了同样的 pre-prepare 信息，因为 primary 节点可能是恶意节点，它可能向其 backup 发送不同的 pre-prepare 信息。因此，每个节点向网络中其他节点广播 prepare 信息进行同步，其含义是告诉其他节点：本节点收到了来自 primary 的一条 pre-prepare 信息。

backup 在 prepare 阶段,向本地的log中插入 $pre-prepare$ 消息以及自身的 $prepare$ 消息 ,并向其他 backup(包括primary)广播一条prepare消息,prepare消息形式如下:

$\left < PREPARE, v, n, d,i\right >_{\sigma i}$

其中 $i$ 是 backup 的编号, $\sigma_i$ 表示节点 $i$ 的签名, backup(包括primary)收到来自其他节点的prepare消息时,会验证如下信息:

view 序号和节点自身的 view序号相同.
n在 [h,H] 范围内.
d 和 pre-prepare阶段消息的摘要相同。

如果上述验证通过,则将这条信息插入本地log.

如果一个节点收到 $2f+1$ (包括自身的)相同的 $prepare$ 消息,并且这些消息与之前收到的 $pre-prepare$ 消息的 $m, v, n$ 相同, 则认为 prepared(m, v, n, i) 为真,并将 prepared(m, v, n, i) 插入log, 然后进入commit 阶段.

3.2 pre-prepare 和 prepare 阶段的作用

$prepared(m, v, n, i)$ 的主要作用就是,确保在一个 view 中，一个 request 唯一的对应一个序列号 n。因为 $prepared(m, v, n, i)$ 为真的条件是,有 $2f+1$ 个节点广播信息验证了 $m, v, n$ 的一一对应关系.证明如下：

$2f+1$ 个一致的 $prepared(m, v, n, i)$ 消息中，最多有 $f$ 个拜占庭节点的 prepared 消息, 至少有 $f+1$ 个诚实节点的 $prepared(m, v, n, i)$ 消息。
剩余的 $f$ 个诚实节点由于收到了错误的prepare 消息，它们互相广播 $prepared(m', v, n, i)$ 。由于存在 $f$ 个拜占庭节点，这些节点可能广播了 $f$ 个 $prepared(m, v, n, i)$ 消息，又作恶的广播了 $f$ 个 $prepared(m', v, n, i)$ 消息，此时也只能存在 $2f$ 个 $prepared(m', v, n, i)$ 消息，这不足以达成一致 (达成一致的要求是至少 $2f+1$ 个相同的prepared消息)。

综上所述， pre-prepare和prepare两个阶段保证了在同一个 view下,n 和 request 的一一对应关系. 这一步骤带来的好处是，即使发生了 view change，此时最多 f 个节点出错，那么剩余的 2f+1 个节点至少有一个节点保留有最新的 2f+1 个prepare信息。当新的 leader 产生时，最新的 2f+1 个 prepare 消息仍然会被执行，保证了系统的安全性。

4. commit阶段

4.1 广播 commit 消息

对 commit 消息再作下解释，进入 commit 阶段的前提是节点收到了 2f+1 个合法的prepare消息，然而在异步环境下，节点不知道其他节点是否也收到了 2f+1 个prepare 消息，所以，节点向其他节点广播一条 commit 消息，其目的是告诉其他节点：本节点已经收到了 2f+1 个prepare 消息。

backup 进入commit 阶段时, 向其他 backup (包括 primary) 广播一条 commit 消息,具体形式如下:

$\left < COMMIT, v, n, D(m), i \right >_{\sigma i}$

其他replica收到commit消息后,验证如下信息:

节点 $i$ 的签名正确.
view 的序号和本地 view 序号相同.
n在[h,H]范围内.

如果上述验证全部通过,节点将该commit信息插入本地log. 如果节点 $i$ 满足两个条件:

节点 $i$ 的 $prepare(m, n, v,i)$ 为真,即节点 $i$ 也进入commi阶段.
节点 $i$ 收到 $2f+1$ (包括自身)一致的 commit 信息, 并且它们与本地的 pre-prepare的 $m, v, n$ 全部相同.

则作出定义 $committed-local(m, n, v, i)$ 为真的判断。

4.2 执行 commit

$committed-local(m, n, v, i)$ 为真，表示系统中至少有 $2f+1$ 个节点认同对 request 分配的编号，这些达成共识的节点执行 request 后的系统状态是一致的. 执行完毕后所有节点会向 client 发送一个 $reply$ 消息. 其形式如下：

$<REPLY, v, t, c, i, r>_{\sigma i}$

其中 v 是当前的 view 编号，t 是 client 的 request 的时间戳，client可以根据时间戳判断是哪一个 request 的执行结果，因为client可能先后不同的时间发送同一个 request, i 是 replica 的编号， r 是执行结果.

4.3 client 验证结果

client如果只要收到 $f+1$ 个相同的执行结果（相同的 r，t）,则认为执行结果可信.

这里面对相同的执行结果的定义是，对应同一个 request，收到了 $f+1$ 个执行结果，这些执行结果具有相同的 r，同时它们也对应于同一个时间戳。这里并不要求同一个 view，具体详见 view change 阶段。

为什么是 $f+1$ 个相同的结果，client 就能确保结果可信呢？因为 $f+1$ 个节点中至少有一个诚实的节点，而一个诚实的节点能够执行一个 request，说明有其他 2f 个节点向其广播了 commit 信息，这 2f 个节点也必然进入了commit 阶段。这说明至少有 $2f+1$ 个节点对 request 的编号 $n$ 达成一致，这种情况下，一个诚实节点返回的执行结果一定可信。

5 Garbage Collect

每个节点都有一个日志系统记录当前系统的执行状态，但是需要定时的对系统做一个snap shot，这是为了确保其他节点从错误中恢复时，可以从中间某个状态再次启动，因此就有了 checkpoint。

Checkpoint 有两个作用:

checkpoint之前的所有 request 的内容都已经执行，因此可以删除之前的log,节省 replica 的存储.
replica 丢失状态时,可以向其他节点请求系统状态时，可以请求最近的checkpoint以快速恢复状态.

假设系统每执行了 $T$ 个request后进行一次checkpoint，于是replica 执行第n个request后,如果 $n\%T == 0$ , 则该节点向其他节点广播一条checkpoint 消息:

$<CHECKPOINT, n, d, i>_{\sigma i}$

其中 d 是执行完第 n 个 request 后的系统状态的摘要, $i$ 是节点编号.

如果收到 $2f+1$ 相互一致并且合法的 heckpoint 信息,则认为这些checkpoint代表的系统状态是合法并且一致的。

对于一个checkpoint，如果有其他 $2f$ 个与之相同的checkpoint 信息，则这个 checkpoint 可以称作是 stable checkpoint。节点可以删除 checkpoint 对应的序列号n的所有 pre-prepared, prepared 和 commit 消息。

当其他节点请求本地传输某个系统状态时, $2f+1$ 个 checkpoint 消息可以作为传输的系统状态合法的证明.

checkpoint协议用来对下一次序列号的范围进行设定,当某个 checkpoint 被证明合法后,对序列号范围可以调整为H = h+k, 其中h是上一次稳定检查点的序列号, 假如每100个请求后进行一次检查点验证, k 可以设置为200, 即H = 200.

6. View Change(视图切换)

view-change 消息是为了应对系统中primary发生故障后切换新的 primary 的机制.

6.1 backup广播 View Change消息

如果当前 view 的编号为 $v$ , 那么出现故障时，下一任 primary的编号为 $(v+1)\%n$ ，因此，PBFT 协议不存在 primary 出现故障后其他 backup 竞争 primary 的情况，这一点和 RAFT 协议有所不同。

每个 backup 收到一个 request 时,就会启动一个计时器,如果计时器超时之后,仍然没有执行该 request ,该backup认为 primary 出现了故障，那么它向其他 replica 发出一个view-change消息,格式如下:

$<VIEW-CHANGE, v+1, n, C, P, i>_{\sigma i}$

其中， $v+1$ 表示下一个视图的编号, n表示该节点已知的最近的一个stable checkpoint的编号, $C$ 是一个集合,其中包括 $2f+1$ 个有效的 checkpoint 信息以证明该 checkpoint是stable checkpoint. $P$ 也是一个集合,集合中的每一个元素是 $P_m$ , $P_m$ 本身又是一个集合, 每一个 $P_m$ 中包含序列号大于n的pre-prepare消息以及与之匹配的 $2f$ 个 prepared 消息.
从这里看到，一条 view-change 消息中包含的消息数量复杂度是 $O(n)$ 级别的，而 $n$ 节点，每个节点都广播一个 new-view 消息，广播消息的复杂度是 $O(n^2)$ 级别，所以，整个 view-change 的广播的消息数量，其复杂度是 $O(n^3)$ 级别

6.2 新primary广播new-view消息

当 v+1视图对应的 primary 从其他 replica 收到 $2f$ 个有效的 view-change 消息时,向其他所有节点广播new-view消息,具体格式如下:

$<NEW-VIEW, v+1, V, O>_{\sigma p}$

其中 $V$ 是一个集合, 包括 $2f+1$ (包含新的primary自身)个view-change消息, O是pre-prepare消息的集合。

O的计算方式如下:

primary 首先确定两个变量 $min-s$ 和 $max-s$ , $min-s$ 指的是 primary 收到的所有view-change消息中最新的stable checkpoint的对应的序号n, $max-s$ 指的是view-change消息中,集合 $P$ 中所有 $P_m$ 中pre-prepare消息编号的最大值.
primary 为编号为 $( min-s, max-s]$ 范围内的 request , 重新创建view序号为v+1的 pre-prepare 信息. 这里包含两种情况:
1. primary 收到的所有 view-change 消息中,至少有1个集合P不为空, 即存在某个编号 $n\in (min-s, max-s]$ 的pre-prepare消息.
2. 所有的view-change消息中的集合P全部为空.
第一种情况下, primary为 P 中所有 request 创建一个新的pre-prepare消息,格式为:

$\left < \left < PRE-PREPARE, v+1, n, d \right > _{\sigma p}, m \right >$

其中 d是该 request 的摘要, n 的范围为 $(min-s, max-s]$ ，这表明这些 request 虽然处于不同的 view，但是为其分配的编号仍然不变。

第二种情况下, primary创建一个null request 的pre-prepare消息,格式如下:

$\left < PRE-PREPARE, v+1, n, d^{null} \right > _{\sigma p}$

$d^{null}$ 是特定的的null request摘要, null request不执行任何操作.

随后，primary 将 $O$ 中的信息插入 log 之中。因为 $min-s$ 是最新的一个 checkpoint 的 request 的编号，如果 primary 发现 $min-s$ 大于 primary 本地最新的stable checkpoint的编号n,则primary也会将相应的 $min-s$ 对应的 checkpoint 的 proof 插入到 log之中, 然后丢弃 stable checkpoint 之前的所有信息。

6.3 backup 验证 new-view消息

当 backup 收到primary发送的new-view信息时, 检查如下信息:

primary签名是否正确.
new-view中包含的 view-change 消息是否合法。
根据new view信息中的集合V计算集合 $O$ , 检查计算得到的 $O$ 是否消息中的 $O$ 一致.

如果上述条件全部满足, backup选择最新的stable checkpoint, 删除stable checkpoint之前的所有log, 并根据执行集合O中的pre-prepare信息.执行步骤按照PBFT的协议进行,如果该节点已经执行过该 request ,则不再执行该 request，但是其他prepared、commit以及reply信息，都需要照常发送.

注意: backup如果没有最新的stable checkpoint的状态,应该首先向其他节点请求最新的stable checkpoint的系统服务状态,然后再执行 $(min-s, max-s]$ 范围内的 request ,否则会导致系统状态不一致.

7. PBFT协议讨论

7.1 为什么PBFT协议中节点总数 $N>3f$ , 为什么后两个阶段至少需要 $2f+1$ 的投票?

以下证明来自个人理解

设系统总节点数为 $N$ , 拜占庭节点数目为 $f$ ,于是剩余的诚实节点的数量为 $N-f$ ，假设系统中有 $Q$ 个节点就一个消息达成一致，那么就认为达成共识。共识协议需要保证安全性(Safeness) 和活性方面(Liveness)。

活性方面，即如果系统中 f 个拜占庭节点不参与投票，那么其他节点应该能够达成一致，于是: $Q<=N-f \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \bold \{1\}$$$ $2f + A + B < 2Q \rightarrow N + f < 2Q \quad (已知A+B = N-f)\quad\quad\quad \bold \{2\}$$ 根据 1 和 2 得到的两个不等式，得到：$

\rightarrow N+f<2N-2f

\rightarrow 3f < N \rightarrow 3f+1 \leq N \quad\quad\quad \bold\{3\}

将 3 的结果代入到 2 式中，得到 $2f < Q$ ，即 $Q$ 的取值至少为 $2f+1$ 。

下文来自 PBFT 论文证明

系统中 $f$ 个拜占庭节点可能不参与共识,此时协议应该保证剩余 $N-f$ 个 replica 达成共识，即 $Q<=N-f$ 。
$N-f$ 个节点中必须保证诚实节点数量超过拜占庭节点的数量（我不太理解作者为什么想当然这么说这句话，可能BFT问题中一个已知的定理）,即 $N-f-f = N-2f > f \rightarrow N>3f$ .
$3f+1 \leq N$ , 根据第 2 式可得 $2f+1 \leq Q$ .
当 $N = 3f+1$ 时，根据 $Q \leq N-f$ ,推导出 $Q \leq 2f+1$ ,即此时Q的取值只能为 $2f+1$ .
当 $N = 3f+k, (k>0)$ 时，Q 的取值范围为 $[2f+1, 2f+k]$ 。

7.2 PBFT的三个步骤中将commit步骤去掉可以吗?

现在撤销 $commit$ 步骤, 只有 $pre-prepare$ 阶段和 $prepare$ ,如果 $prepare(m,n,v,i)$ 为真,则直接执行 request 并且返回给client.

假设有部分诚实的节点数量为 $f$ ,成功的收到了 $2f+1$ 与本地pre-prepare匹配的 $prepare$ 消息, 它们执行了对应的request-m, 假设m对应的序号是 $n$ , view序号是 $v$ . 但是其他 $2f+1$ 个节点在接收 $prepare$ 消息过程中网络不好, 没能收到足够的 $2f+1$ 个匹配的 $prepare$ 消息, 所以它们不会执行这个m.(PBFT协议中假设网络中信息传输会出现丢失的情况). 然后这 $2f+1$ 个节点进行了 $view-change$ , 并且primary在这 $2f+1$ 个节点中产生, 这 $2f+1$ 个 $view-change$ 消息中没有request-m的对应的 $2f$ 个prepared消息,并且如果出现 $2f+1$ 个节点的 view-change消息集合中的 P为空,新的primary重新发布 $new-view$ 消息时,消息中的O只包含了一个null-request的pre-prepare消息:

$\left < PRE-PREPARE, v+1, n, d^{null} \right > _{\sigma p}$

此时执行了request-m的 $f$ 个节点验证 new-view后通过,它们本地的序号n对应request-m,但是new-view中的序号 $n$ 对应的是一个null request, 而不是request-m. 这就导致了这诚实的 $f$ 个节点和另外 $2f+1$ 个节点的系统状态已经出现了不一致.这不满足PBFT协议保证系统一致性的另外一个条件,所有系统中的非故障节点都必须对 request 的执行达成一致.

实际上,引入 $commit$ 步骤中, $committed-locally$ 为真才执行 request 这一条件, 就是保证至少有 $2f+1$ 个节点(其中至少 $f+1$ 个诚实的节点)的 $prepared(m,v,n)$ 为真, 这些节点一起执行 request .

view-change时,这 $2f+1$ 个执行了reqeust-m的节点中,至少有 $f+1$ 个节点参与其中,这个节点的参与,保证了request-m在view序号为 v+1的时候分配的编号仍然是 view序号为v时的序号,这就是为什么论文中说 $commit$ 步骤保证了不同 $view$ 中 request 的有序执行.

7.3 如果client在发出request之后在一定时间内没有收到足够多的响应怎么办?

client会将 request 广播给所有节点, 如果收到的节点已经处理了这条 request ,则会直接向client返回执行结果.如果该节点没有处理过这条 request ,则会将这条 request 转发给primary. 如果primary在一段时间内不广播该 request ,其他节点会怀疑primary作恶并且进行 $view-change$ 操作以更换primary.

7.4 为什么client收到 $f+1$ 个一致的结果就认为结果是正确的?

在PBFT协议中最多有 $f$ 个恶意的节点,当client收到 $f+1$ 个相同的执行结果时,说明其中至少包含一个诚实的节点的执行结果. 诚实的节点返回执行结果的前提就是, 分别在prepared和committed-local达成了一致,并且这个一致性是唯一的,这也能说明系统中诚实的节点达成了唯一的一致, 所以client可以相信执行结果.

7.5 backup 验证pre-prepare消息时为什么n的范围需要在[h, H]之间

为了防止恶意的primary选择一个超级大的序列号n耗尽序列号的空间.不过这个解释不太令人信服,我暂时也不太清楚.

7.6 PBFT协议中的log有什么作用?

log可以记录节点是否执行了某个 request .
另外如果发生 $view-change$ 时可能会从最新的stable checkpoint重新执行 request ,log记录了 request , 方便重新执行.
其他节点请求stable point时可以直接传输 $committed-local$ 消息方便该节点恢复.

参考文献

[1] M. Fischer, N. Lynch, and M. Paterson. Impossibility of Distributed Consensus With One Faulty Process. Journal of the ACM, 32(2), 1985

[2] G. Bracha and S. Toueg. Asynchronous Consensus and Broadcast Protocols. Journal of the ACM, 32(4), 1995
[3] Castro M, Liskov B. Practical Byzantine fault tolerance[J]. operating systems design and implementation, 1999: 173-186.

一、 系统模型

二、 系统角色