PBFT论文阅读笔记

算法流程

一个副本有：当前状态，log（包含副本收到的所有消息），当前view

主节点收到请求的时候会立即处理（发pre-prepare）（除非正在处理的请求个数超过了上限，这个时候会把请求缓存，缓存的请求之后会以组为单位发送来减轻负担）

三阶段：pre-prepare, prepare, commit.

pre-prepare, prepare用来对同一个视图里面的请求进行完全排序，即使主视图是有问题的。

Pre-parepare阶段

预准备阶段给请求assigns一个n，做 <<pre-prepare, v, n, d>, m>发送给副本（副本logs接受后将收录，作为一个证明）。

副本接受pre-prepare的条件：

1. m（用户签名）和pre-prepare（主节点签名）上的签名正确，d确实是m的摘要。
2. 当前副本的视角确实是v
3. 之前在视角v没有收到过编号n的摘要d不同的pre-prepare
4. n在[h,H] ( 防止坏的主节点浪费序列号的空间)

Prepare阶段

如果副本i接受了pre-prepare，它进入准备阶段，广播<prepare, v, n, d, i> 给所有其他副本同时也把这个消息放到自己的log。

副本接受prepare的条件：

1. 签名正确
2. view-number和副本当前view number相同
3. n在区间[h, H]

注意：这里接受prepare，不需要节点本身接受过对应的pre-prepare。

定义节点i准备好了prepared<m, v, n , i>:

i的日志里面有:
1. 消息m
2. 有消息m对应的<pre-prepare,v,n,d>
3. 有2f条来自不同节点的与<pre-prepare,v,n,d> 匹配的prepare消息（检查v，n，d是否相同）

pre-prepare和prepare阶段保证了在同一个v下所有正常节点对执行顺序达成共识。

详细的：

当 prepared<m, v, n, i> 成功，则一定不存在 d(m’)!=d(m)使得对某个j， prepared<m’, v, n, j> 是成功的。

原因：

prepared<m, v, n, i> 成功，说明有至少f 1个正常节点发送了 prepare<v, n, d, i> ，那么剩余只有2f个节点会做不同的选择，无法使得 prepared<m’, v, n, j>成功。

Commit阶段

当节点i准备好了，即 prepared<m, v, n, i>. 它会发送 <Commit, v, n, d, i> 给其他节点。

节点接受commit消息的时候验证：

1. 签名正确
2. view和节点当前的view相同
3. n在区间[h,H]

验证完加入到log

定义commited:

committed(m, v, n) 为真当且仅当 ：prepared(m, v, n, i) 在至少f 1个正常节点为真

定义commited-local：

prepared(m, v, n, i )为真且收到了2f 1个不同节点的与m的pre-prepare 匹配的commits。

匹配：有相同的v, n, d

commited-local为真则commited一定为真（显然）。

这个不变性保证了本地的commits最终会在f 1或者更多个正常节点上commit。

每个副本i在满足一下两个条件（同时满足）的情况下执行m：

1. commited-local(m,v,n,i) 为真
2. i的状态反应出所有编号低于n的请求都被按顺序执行

这个过程并不依赖消息按顺序发送，因此一个副本在顺序外commit一个请求是可能的，这并不重要因为它保持pre-prepare, prepare和commit消息在log中直到对应的请求被执行。

垃圾回收

这一章讲丢弃log中的消息的机制。

安全起见，消息需要一直被存在副本的log里直到它知道它关心的请求已经被至少f 1个正常节点执行并且它可以在view change的时候向其他人证明这一点。此外，如果某个副本错过了被所有正常副本丢弃的消息，它需要通过转移全部或者部分状态来实现更新，因此副本同样需要证明它的状态是正确的（错过消息的节点依此来更新自己的状态）

每次执行一个操作之后就生成一个证明很浪费资源，因此它们周期性的生成（每隔K个，把当前这些请求生成的状态作为checkpoints）一个有proof的checkpoint称为stable checkpoint

一个副本维护若干个service state的逻辑拷贝：最后一个stable checkpoint，若干个不stable的checkpoint，当前状态。state写时拷贝来节省空间。

一个checkpoint的证明生成方式如下：

当一个副本i生成一个checkpoint，它广播一个<checkpoint, n, d, i>消息给其他副本，n是这个checkpoint最后被执行的请求，d是state的摘要。每个副本收集checkpoint消息到它们的log里面直到它有2f 1个不同节点对于编号n的摘要相同的消息。这2f 1个消息就是这个checkpoint正确的证明。

当一个checkpoint有了证明，它就成为了stable的，，副本会丢弃所有编号小于等于这个checkpoint的n的log。并且同样会丢弃更早的checkpoint和checkpoint消息。

checkpoints协议限制了[h,H]编号范围。h是最后一个stable checkpoint的n，H = h k, k要足够大避免副本执行过程中需要等待下线上升。k一般是K的倍数，可以取2K

视角切换（View change）

发起视角切换

一个副本被称为 “在等待一个请求” ：它收到了一个合法的请求但是还没有执行它。

一个副本会在收到请求的时候启动计时器（相当于每个请求都有个等待时间，执行完它的上一个请求-执行它 之间的时间有限制）。

如果某副本i的计时器在视角v下超时，它会发起view change让整个系统的view变成v 1. 这个时候它会停止接收信息（除了checkpoint，view-change，new-view），然后广播 $<view\_change,v1,n,C,P,i>$. 这里n是i所知的最后一个checkpoint的n，$C$是 2f 1 验证过的checkpoint 消息 提供的状态s正确的证明，$P$中是若干个 编号在n之后的对于i来说prepared了的请求m的信息 P m P_m Pm 。而 P m P_m Pm 包含了合法的pre-prepare消息和2f个匹配的，经过验证的在同一个(v, n, d)下的prepare消息。

进行视角切换

主节点行为

当v 1视角下的主节点p收到2f个经过验证的请求切换到view (v 1) 的 view-change信息，它会广播一个 $<new-view,v1,V,O>$消息给所有其他节点。$V$ 是这所有2f个viewchange信息 主节点自身的viewchange信息（一共2f 1个，都有签名）。$O$是一个pre-prepare消息集合（<pre-prepare, v, n, d>由p签名）。$O$的生成方式如下：

1. 主节点定义序列号 min_s 是V中最新的stable <checkpoint,n,d,i>中最小的那个n , max_s是prepared中最大的的那个n（[min_s到max_s]对应 [最新的存档点 -> 最新的prepared的请求]）
2. 主节点为编号在 [min_s, max_s] 的每个n创建一个新的在视角v 1下的pre-prepare消息。这里会有两种情况：
	i)在V中存在某个view-change消息，它的P中有编号为n的prepare消息
	ii)不存在上述view-change消息
	在情况(i)中，主节点创建一个<pre-prepare,v 1,n,d>消息，其中d是V中view最大的节点的编号为n的请求摘要
	在情况(ii)中，创建一个<pre-prepare, v 1, n, d_null>，d_null是对特殊请求null的摘要，一个null请求像其他请求一样通过协议但是不做任何事情

之后主节点把O中的这些消息放到log中。如果min_s比它最后一版stable checkpoint的编号还大，主节点会把min_s的证明加入log并更新checkpoint为min_s。然后它的view切换为v 1（在此时它只接收视角为v 1的消息）

副本节点行为

副本收到一个new-view消息，当这个new-view信息验证通过，副本接受它。验证通过需要满足：

1. 签名验证通过
2. 它包含的2f 1个切换到v 1的view-change消息合法
3. 集合O是正确的。验证O的方式是用与主节点相同的方式生成O，看是否和主节点生成的O相同。

然后它把O中这些消息放到log中（和主节点做的一样），对O中的每个pre-prepare生成一个prepare并广播给所有其他的副本，把这些prepare加入到自己的log，并进入视角v 1。

此后，协议正常处理。副本重做在[s_min, s_max]之间的请求并且避免重新执行客户端请求（通过使用它们存储的“最后一次回应给客户端的请求”信息来避免）。

一个副本可能丢失一些请求m或者checkpoint（没有发送new-view请求），它可以从其他副本获取信息。例如，i可以通过new-view中的V来确认某个状态s确实是得到了证明的，并从对应的副本获取状态。可以通过对状态分区，并标记最后一次修改它的请求的序列号来避免发送全部状态。

思考

问：为什么2阶段 (pre-prepare, prepare收到2f 1就直接执行) 不行

答：会在view-change的时候出问题。收到2f 1个prepare的正常节点个数可能并没有f 1个，甚至只有一个。此时它执行了 (n,m) ，其他没有执行。此时发生view-change，主节点重新发送[min_s到max_s]的消息（此时max_s是最后一次个收到的pre-prepare对应的序列号），但是max_s可能比n小，因为此时执行了(n,m)的可能很少。那么这个时候就会导致正常节点执行的不一致。

而在commit执行的时候，因为执行的时候一定收到了2f 1个commit，所以一定有f 1个正常节点的这个请求至少处于prepared阶段，那么在收集view-changed的时候，一定会收集到这个执行了的请求的prepare（鸽巢原理），max_s一定会包含这个请求的序列号。 这也就保证了请求执行最终顺序一致。

这篇好文章是转载于：学新通技术网