转载请注明出处：www.huamo.online
字节杭州 求贤若渴：
实用拜占庭容错算法PBFT
拜占庭将军问题
拜占庭将军问题见于Leslie Lamport等人1982年的论文《The Byzantine Generals Problem》。是一个关于协议的问题。
想象一个敌方城市被拜占庭军队团团围住，围城部队分为几个部分驻扎在城外，每个部分仅由自己的将军指挥。将军们只能通过信使和其它将军进行通信。在观察了敌情之后，他们必须制定一个一致行动的计划。结果表明：仅使用口头消息的情况下，该问题当且仅当超过2/3的将军忠诚时可解；而若使用不可伪造的书面消息时，对于任意数量的将军和可能出现的叛徒，该问题都是可解的。
然而，其中有一些将军可能是叛徒，他们会试图阻止忠诚的将军们达成共识。所以拜占庭将军们必须有一个算法能够保证：
A. 所有忠诚的将军能够统一行动计划：算法告诉什么，忠诚将军就会做什么，但是叛徒则会为所欲为。算法要能够在这种情况下依然保证忠诚的将军们达成一致决定。
B. 一小部分数量的叛徒不能导致忠诚的将军们采纳了一个坏的计划：这个标准很难形式化的描述，因为首先要定义出什么叫做坏计划，我们不准备这么做。而是回顾下将军们如何达成一致。每个将军观察敌情，然后向其它将军交流观察结果。设v[i]是第i个将军发出的消息。每一个将军都使用某种神奇的方法，将v[1], ..., v[n]数据联合在一起并制定出一个单一的行动计划，其中n代表将军们的编号。当所有将军都使用同样的方法来制定计划时，就表明条件A达成，而条件B则需要保证采用的是一个鲁棒的方法。
举个例子，假如行动计划就是进攻或者撤退二选一，
v[i]就是第i个将军认为哪个选项更好，最终决定就是看哪一项投票更多就选那一项。那么只有当忠诚将军们在两个选项上投票持平，少数反叛者才能影响结果。在这种情况下哪一个选项都不能称之为坏计划（因为忠诚将军们原本对这两个计划就平分秋色）。
实用拜占庭容错算法
0. 概述
论文介绍了一种新的拜占庭容错算法。之前的拜占庭算法，要么假定环境是同步系统，要么就是太慢不适用于实际场景。而这种新的算法是实用的：适用于异步环境，并结合了几个重要优化，可以将以前算法的响应时间提高一个数量级以上。文中还将该算法运用于NFS服务来测量其性能，结果表明仅比标准的NFS服务慢3%。
1. 介绍
现如今的软件世界，拜占庭容错算法的重要性日益提高。本文介绍一种可容忍拜占庭错误的，实用的，状态机复制算法。该算法可以在最多 $\lfloor \frac{n-1}{3} \rfloor$ 个副本同时出错的情况下依然提供可用性和安全性（n是副本总数量，也可以认为是节点总数量）。这也就意味着用户最终能收到他们请求的，线性正确的回复（从RAFT那篇文章里可知，副本状态机的副本都是线性编号的）。该算法在异步环境下依然能够有效执行。所以不容易受到denail-of-service attack这种攻击的影响。
denail-of-service attack：拒绝服务攻击
该算法仅用1个消息往返就执行了只读操作，以及2个消息往返执行了读写操作。并且在常用操作中使用了一种有效的，基于消息验证码（MAC）的验证模式。而仅在出现拜占庭错误时才会使用耗时耗性能的公钥密码学技术。
为了评估算法性能，他们实现了一个复制算法库，并用到了一个实际系统中：一个支持NFS协议的，拜占庭容错的，分布式文件系统。基准测试结果表明：只比普通的NFS服务慢3%。
论文做出了如下贡献：
第一个提出了在异步环境下，拜占庭容错的，状态机复制协议。
描述了一堆重要的优化以便算法能在真实系统中有效执行。
描述了一个拜占庭容错的分布式文件系统的实现。
提供了该算法性能的量化实验结果。
2. 系统模型
我们设想一个异步的分布式系统，其中的节点都是通过网络连接在一起。这个网络可能会传递消息失败，传递消息延时，重复传递消息，或者不按顺序传递消息。
并且使用拜占庭故障模型，即故障节点可以任意行事，只受这一条限制：节点故障都是相互独立的。例如每个故障节点都使用不同的服务实现版本。
我们使用密码学技术来防止欺骗，重放，以及检测损坏的消息。我们的消息包含公钥签名，消息验证码（MAC），以及使用抗碰撞哈希函数生成的消息摘要。我们将节点i对消息m的签名记为 $$\langle m \rangle_{\sigma_{i}}$$，而消息m的摘要记为D(m)。我们遵循常用的做法：即对消息的摘要进行签名，然后将其追加到消息明文后面。而不是对整个消息进行签名。（这种方式需要确保签名能够被解析出来）。所有的节点（或称复制体）都知道其他人的公钥以验证签名。
除此之外，就是我们假想攻击者很强大，延迟通信，甚至控制拜占庭故障节点。但是它也有一些合理的限制，比如无法无限期延迟网络通讯，无法计算攻破密码学技术。
3. 服务属性
该算法可以用于实现任意的，拥有状态机和一些操作的，确定的，复制服务。操作不仅限于对状态局部的简单读或写，还可以执行基于状态和参数的任意确定的计算。客户端发起请求，调用操作并阻塞等待一个回复。复制服务由n个复制体实现。只要遵循第4节描述的算法并且攻击者无法伪造签名，那么这个服务就不会出现故障。
只要不超过$\lfloor \frac{n-1}{3} \rfloor$个复制体出现故障，该算法就能通知保证安全和可用性。安全指的是复制服务满足线性化：它表现的就像一个中心化实现，每次只执行一个原子操作。安全性要求故障复制体的数量受到限制，因为故障节点会出现任意行为，比如它可以破坏本地状态。
安全性不需要管有多少故障客户端来使用这个服务（即使它们串通了故障节点，也不影响服务的安全性）：故障客户端的所有操作和正常客户端的操作都一视同仁。比如：一个操作被设计为在状态里保存几个不变量，那么故障节点是无法破坏这些不变量的。
单有安全性是不足以抵御故障节点的，比如在一个文件系统里，故障客户端可以向共享文件写入大量垃圾数据。所以，我们通过访问控制来限制故障节点的危害：验证客户端，如果没有权限调用某一操作，则拒绝客户端的请求。另外，服务也可以提供修改一个客户端的访问权限的操作。由于算法对所有客户端，一视同仁的保证了危险操作的影响程度，这就提供了一个强有力的机制来抵御故障客户端的攻击。
算法不依赖同步来提供安全性，因此，它就必须依赖同步来提供可用性(liveness)。否则，就不可能在一个异步系统中实现共识（证明见参考资料3）。如果最多只有$\lfloor \frac{n-1}{3} \rfloor$个复制体出现故障，并且dealy(t)不会关于t无限增长下去。那么该算法就可以保证可用性。这里的delay(t)指的是在t时刻消息第一次发送出去，一直到收到对方回复这一段时间（假设发送者收不到回复就会一直重发）。这是一种相当弱的同步假设，更符合真实系统中的网络情况。即使很弱，但也依然帮我们避开了资料3中的不可能命题。
该算法对数量的弹性适用是很棒的：在一个异步系统中，当有f个复制体出现故障时，如果还想保持安全性和可用性，那么系统的总节点数量n最少应为3f+1。需要这么多节点的原因是：剩下的n-f个节点通信还需要继续处理，因为f个节点可能已经出现故障并且没有响应。然而，也有可能存在有f个节点没有响应，但是它们并没有出现故障这种情况，同时，在响应的节点中，有f个节点虽然响应了，但是它们却出现了故障。所以，除了f个故障节点之外，剩余的节点也要有足够的响应数量来维护多数原则才能使整个系统属性得以保障，亦即：n - 2f > f，因此，n > 3f。
备注：这一段非常精髓简要的解释了为什么是
3f+1的原因，就是前提是已经有f个节点叛变了，那么我如何保障系统还能正常，正常的根本就是诚实节点占大多数，但是剩余的n-f个节点不一定都是诚实节点，最坏情况下，减掉的那f个节点其实都是诚实节点，只是它们没有响应而已，所以叛变节点都在n - f里面，所以我们需要保证剩余节点里面，诚实节点占大多数，于是就有：n - f - f > f，即n - 2f > f，得出：n > 3f
该算法并没有解决隐私容错的问题：叛变节点有可能会泄露信息给攻击者。这不是本算法目前关注的重点，作者在文中表示计划在未来调研这方面的技术。可能会用秘密共享方案或者设置获取隐私的门槛等。
4. 算法
该算法是状态机复制的一种形式：服务建模在一个分布式系统中，一个状态机要在不同的节点之间进行复制。每个状态机副本都维护了服务状态，以及实现了服务操作。我们将副本集合记为R，并用整数来编号每个副本：{0, ..., |R|-1}。为了简单，我们假定|R| = 3f + 1。其中f表示集合中故障副本的最大数量。虽然总数量|R|也可以大于3f+1，但是多余的那些副本只会降低系统的性能（因为有更多更大的消息要被传输），并不会提高系统的健壮性。
副本通过一系列称为view（视图）的配置进行移动。在一个view中有一个副本是主副本（primary），其它的都称为备用副本(backups)。视图是被连续编号的。一个视图中的主副本是p号副本，其中p = v mod |R|，其中v是视图编号。当主节点出现故障时，就会执行view change（视图改变）
算法大致运行过程如下：
一个客户端向主节点发送请求去调用一个服务操作。
主节点向备用节点广播这个请求。
各个节点都会执行这个请求，并向客户端发送一个回复。
客户端从不同节点收到了
f + 1回复，且这些回复都是相同的结果，那么这就是该操作的执行结果。
就像所有的状态机副本技术那样，该算法对副本也有两个强制要求：1. 他们必须是确定的（给定一个状态，给定一组参数，给定一个操作，那么必须能够输出同样的结果）；2. 他们必须从同一个状态开始演变。有了这2个规定，算法就能通过保证 所有非故障副本执行请求的总顺序上达成一致，即使执行失败，但总顺序依然是一致的 这一原则来确保安全性。
4.1 客户端
一个客户端c通过向主节点发送一个消息 $$\langle REQUEST, o, t, c \rangle_{\sigma_{c}}$$ 来请求执行状态机操作o。时间戳t用来在语义上确保请求只执行一次。对于客户端c的请求，时间戳是全部有序的，即后续的请求总是比之前的请求时间戳大。例如时间戳可以被设计为客户端的本地时间。
节点发送给客户端的每个消息都包含了当前的视图编号，方便客户端追踪视图，从而确定当前的主节点。客户端通过点对点消息向它自认为的主节点发送请求。而主节点则使用下文中描述的协议向所有备用节点广播请求。
每个节点都向客户端直接发送回复。回复遵守的格式为 $$\langle REPLY, v, t, c, i, r \rangle_{\sigma_{i}}$$ 其中v是当前视图编号，t是对应请求的时间戳，i是节点编号，r则是请求操作的执行结果。
客户端等待f + 1个有合法签名的不同节点的回执，并且它们都有相同的t和r，这样才最终接受结果r，并确信这个结果是合法的，因为整个系统最多会有f个节点出现故障。
如果客户端没有及时收到回复，它会将请求广播给所有节点。如果请求已经被处理了，节点则简单的重发回复；节点缓存了它发给每个客户端的最后一条回复。否则（即请求没有被处理），如果节点不是主节点，它将会把请求转发给主节点。如果主节点没有把请求广播给组内其它人，它最终会被足够多的节点质疑为出现故障，而出现view change。
在论文中，作者假定的是客户端等待一个请求执行完成，再发送下一个请求。而算法可以允许客户端异步发送请求，同时保留对它们的排序约束。
4.2 普通情况操作
每个节点的状态都包含了服务状态，消息日志则包含了节点收到的消息，还有一个整数记录了该节点所处的当前视图。后文还会讲述如何截短日志。
当主节点p收到了一条客户端请求m，它就会启动一个三阶段协议向其它节点来原子得广播请求。一般来说主节点会在收到请求后立马启动协议，除非协议正在进行的消息数目已经超过了给定的最大值。这种情况下，它会先缓存该请求。缓存的请求稍后会作为一组多播出去，以降低高负载下的消息流量和CPU开销。这种优化类似于事务性系统中的组提交。
三阶段协议为pre-prepare，prepare，和commit。pre-prepare和prepare阶段是用来全局排序在一个相同view中发出的请求，即使提出排序请求的主节点出现了故障也是如此。prepare和commit阶段是用来确保提交的请求在视图之间也是全局有序的。
在pre-prepare阶段，主节点向请求派发一个序列编号n，并多播一个pre-prepare消息，连带请求m，发送给所有备用节点，并将该消息追加到节点日志中。这个pre-prepare消息具有如下格式 $$\langle \langle PRE-PREPARE, v, n, d \rangle_{\sigma_{p}}, m \rangle$$ ，其中v代表这个pp消息发出时的view编号，m是客户端发出的请求消息（不是请求本身），d是m的消息摘要。
请求并没有包含在pre-prepare消息中，以使它们体积更小。这一点很重要因为pp消息，在发生view change时，可用来证明请求在视图v中被指定了序列号n。此外，它对协议进行了解耦，将协议中的对请求全局排序，和向各节点传输请求分离开来；这就允许我们对小消息通信运用一种传输优化手段，而对大请求的大消息通信采用另一种传输优化手段。
一个备用节点只接受满足如下条件的pre-prepare消息：
请求的签名，和
pp消息都是正确的，并且d是请求消息m的摘要。该节点在视图
v中。节点还没有接受过一个视图
v，序列号n，而摘要不一样的pp消息。pp消息中的序列号介于低水印h，和高水印H之间。
最后一个条件是为了防止一个故障主节点选用一个超大值来耗尽序列号空间。后文会讨论h和H的更新。
如果备用节点i接受了消息 $$\langle \langle PRE-PREPARE, v, n, d \rangle_{\sigma_{p}}, m \rangle$$ ，它会通过做以下事情进入prepare阶段：向所有其它节点多播 $$\langle PREPARE, v, n, d, i\rangle_{\sigma_{i}}$$ 消息，并将这2个消息都存入日志中。否则，不做任何事。
一个节点（包括主节点）接受prepare消息，并存入自己的日志中，只要
该消息的签名正确。
消息中的
view编号等于自身当前所处的view。并且序列号介于
h和H之间。
我们定义谓词prepared(m, v, n, i)为true，当且仅当节点i已经将如下几项存入到日志中：
请求
m。m在视图v中具有序列号n的pre-prepare消息。并且由
2f个不同节点发来的匹配该pre-prepare消息的prepare消息。节点判断是否匹配的标准是：它俩是否具有相同的view，相同的序列号，相同的摘要。
算法的pre-prepare阶段和prepare阶段保证了正常节点都认同一个视图内的请求顺序。更确切的说，它们保证了如下不变式：
如果prepared(m, v, n, i)为true，那么对于任意的正常节点j（包括i = j），以及任意的其它请求m'（D(m') != D(m)）来说，都有prepared(m', v, n, j)为false。
这个命题之所以是真的，是因为prepared(m, v, n, i)和|R|=3f+1暗含了至少有f + 1个正常节点为数据(m, v, n)发出了pre-prepare或prepare消息，数据(m, v, n)意思是一个在视图v内携带序列号n的请求m。因此，要想让prepared(m', v, n, j)为true，那么这些正常节点中至少要有1个节点需要发出2条冲突的prepare消息（或者它是视图v的主节点，则是pre-prepare消息），但这和它是正常节点的假设是冲突的。当然了，这里假设的是对于不同的请求m和m'，它们的哈希摘要也是不同的：D(m) != D(m')
这一段很精彩，用反证法证明了对于同样的视图，同样的序列号，只会存在一个请求是合法的，这就保证了同一视图内请求都是全部有序的：因为已知系统内至少有
f+1个正常节点，假设最坏情况有f个故障节点，那么剩余的节点还有f个待定节点，但是要想让m'谓词为真，需要f+1个节点背书，即使所有的待定节点为其背书，那也还少1个节点，所以只能从f+1个正常节点取出1个为其背书，但是f+1个正常节点已经为m谓词背书了，所以凑不够数，因此m'不可能为真。
当prepared(m, v, n, i)为true时，节点i向其它节点多播一条格式为 $$\langle COMMIT, v, n, D(m), i \rangle_{\sigma_{i}}$$ 的commit消息，以此开启commit阶段。节点接受commit消息并将它们插入到日志中的前提是：
消息被正确的签名。
消息的
view编号等于节点当前所处的view。序列号介于
h和H之间。
我们定义committed和committed-local这两个新谓词如下：
committed(m, v, n)为true，当且仅当对于f+1个无故障节点的集合中的所有的节点i，都有prepared(m, v, n, i)为true。committed-local(m, v, n, i)为true，当且仅当prepared(m, v, n, i)为true，且节点i收到了2f+1个（很可能包含它自己的）不同节点发来的匹配pre-prepare消息的commit消息。匹配标准是：相同的view，相同的序列号，和相同的摘要。
commit阶段保证了如下不变式：
对于一些正常节点i，如果committed-local(m, v, n, i)为true，那么committed(m, v, n)为true。
将在后文介绍该不变式和view-change协议，该协议确保了正常节点会认同已经本地提交的请求序列号，即使它们在每个节点上，是在不同view中本地提交的。此外，该协议还保证了任何一个在1个正常节点上本地提交的请求，最终都会在f+1甚至更多的正常节点上本地提交成功。
当committed-local(m, v, n, i)为true后，每个节点i都会执行客户端请求的操作，并且操作的状态也反映了之前更小序列号的请求顺序执行完的结果。这就确保了所有的正常节点按照要求遵循同样的顺序执行请求以提供安全性。当操作执行完成之后，节点直接向客户端返回结果。节点会记住最后一次回复对应的请求时间戳t，如果收到了一个新请求时间戳小于t，则会丢弃该请求以保证一次性语义。
该算法不依赖有序消息传输，因此会有可能一个节点不按顺序commit请求。这没有什么影响，因为commit请求并不是真正去执行操作，而是把pre-prepare，prepare，commit消息记录在日志中，直到对应的请求可以被执行了，才会去真正执行请求。
下图图示了在正常情况下，主节点正常的前提下，算法的操作流程。节点0是主节点，节点3是故障节点，C则是客户端。
4.3 垃圾回收
本节讨论的是忽略日志中某些信息的机制。为了保证安全性，节点必须将消息保存在日志中，直到它们知晓了相关的请求已经至少被f+1个正常节点执行，并且在view-change时它能够向其它节点提供这样的证明。此外，如果有些节点丢失了一些消息，这些消息恰好又被所有正常节点丢弃了，那么它就需要通过传输全部或者部分服务状态来同步到最新。因此节点还需要证明状态正确的证明。
在每次操作完成后生成这些证明是极为昂贵的。所以，替代方案是周期性的生成证明，比如当一个请求的序列号可以整除一些常量（比如100）时生成证明。我们将此时的服务状态称为checkpoints（检查点），并称带有证明的检查点为stable checkpoint（稳定检查点）。
一个节点会维护服务状态的几份逻辑拷贝：最近稳定检查点，0或多个不稳定的检查点，还有一个目前的服务状态。copy-on-write技术可以用来减少额外存储的开销。这种优化会在6.3节讨论。
检查点正确性的证明按照如下规则生成。当一个节点i产生一份检查点时，它会向其它节点多播一个格式为 $$\langle CHECKPOINT, n, d, i \rangle_{\sigma_{i}}$$ 的checkpoint消息，其中n是反映在服务状态上最近一个已经执行操作了的请求序列号，d是服务状态的摘要。每个节点收集checkpoint消息存入到日志中，直到收集到相同序列号n，相同摘要d，来自不同节点（很可能包含自己的），数量为2f+1个这样的消息。那么这2f+1个消息就是该检查点的正确性证明。
一个带有证明的检查点就变为了稳定检查点，节点就会丢弃掉日志中所有序列号小于等于n的pre-prepare，prepare，commit消息。它还会丢弃掉所有更早的检查点以及checkpoint消息。
checkpoint协议是用来更新低水印h和高水印H的值的，这两个值限制了消息是否会被节点接受。其中低水印h等于最近一次稳定的检查点的序列号。高水印H = h + k，其中k是足够大的数，以便节点不需要停在那儿等待一个检查点变成稳定状态。例如，检查点被设为每100个请求检查一次，那么k有可能就等于200。
4.4 View Changes
当主节点出现故障时，view-change协议允许系统能够自我演进，以此提供了可用性。view change通过超时机制触发，避免了执行请求时备用节点的无限等待。如果一个备用节点收到了一个合法的但还没有执行的请求，此时它就会waiting执行请求。当节点收到一个请求并且计时器没有在运行时，它就会启动一个计时器。当它不再需要waiting执行请求时，它就会停止计时器。而如果这个时候，它又要waiting执行其它的请求时，就会重启计时器。
一个请求处理完，此时计时器还在运行，应该要停止计时器，但恰好又有新的请求被接受，此时因为计时器还在运行，不符合启动计时器的条件，所以节点需要重启计时器，即重置。
如果备用节点i的计时器在视图v中到期了，这个备用节点就会开启一个view change将系统移至视图v + 1。它会停止接受消息（除了checkpoint，view-change，'new-view消息，这些它还接受），并且多播一个 $$\langle VIEW-CHANGE, v+1, n, C, P, i \rangle_{\sigma_{i}}$$ 的view-change消息给所有节点。这里的n是节点i知晓的最近一个稳定检查点s的序列号，C是一个集合，包含了2f+1个合法的checkpoint消息证明了s的正确性，P也是一个集合，包含了一系列的，在节点i上已经prepared，并且序列号高于n的请求m的 $P_{m}$ 。 $P_{m}$ 也是一个集合，包含了一个合法的pre-prepare消息（不含对应的客户端消息），以及2f个匹配的，合法的prepare消息，这些prepare消息由不同的备用节点签名，它们都具有相同的view，相同的序列号，还有相同的请求m的摘要。
当视图v+1的主节点从其他节点收到了2f个合法的，提议改变到视图v+1的view-change消息时，它会多播一个 $$\langle NEW-VIEW, v+1, V, Q\rangle_{\sigma_{p}}$$ 的new-view消息给所有其它节点，其中V是一个集合，包含了主节点自己收到的，合法的view-change消息，以及它自己发出的（或者要发出的）view-change消息，还有Q也是一个集合，包含了一系列的pre-prepare消息（不包含夹带的客户端请求）。Q经由如下规则计算。
主节点先确定最低序列号，和最高序列号。最低序列号来自于
V中最小的最近稳定检查点min-s，最高序列号来自于V中prepare消息中最大的最近稳定检查点max-s。主节点对于每一个序列号
n介于min-s和max-s之间的请求，都用视图v+1创建一个新的pre-prepare消息。这分2种情况：(1)对于V中的一些view-change消息，至少有一个在P集合中。或者(2)没有这样的集合。对于第一种情况，主节点创建出一个新的pre-prepare消息：$$\langle PRE-PREPARE, v+1, n, d \rangle_{\sigma_{p}}$$，其中d是V中具有最高视图编号的序列号为n的pre-prepare消息中的请求摘要。对于第2种情况，主节点会创建出另一种新的pre-prepare消息：$$\langle PRE-PREPARE, v+1, n, d^{null} \rangle_{\sigma_{p}}$$ ，其中 $$d^{null}$$ 指的是一个特殊的null请求的摘要。这种null请求可以像正常请求那样穿梭在协议中，但是它申请执行的操作就是没有操作。
接下来，主节点会将Q中的消息记录到自己的日志中。如果min-s比它自己知晓的最近稳定检查点序列号还要大，主节点还会将序列号为min-s的检查点的稳定性证明插入到日志中，并忽略掉4.3节讨论的日志中信息。然后它进入视图v+1：此时它可以接受视图v+1的消息了。
一个备用节点接受视图v+1的new-view消息，需要满足如下3个条件：
签名正确
它包含的
view-change消息对于视图v+1合法集合
Q正确
节点判断集合Q的正确性，是通过执行一系列计算，计算规则类似于主节点创造Q的算法。然后它将这个新信息存入到日志中，然后向所有其它节点，对Q中的每个消息多播一个prepare消息，并将这些prepare消息加入到日志中，并且进入视图v+1。
随后，协议会像4.2节描述的那样进行处理。节点对于min-s和max-s之间的消息重做相同操作，但会避免重复执行请求（依据本地存储信息，关于对每个客户端发出的最后一次反馈来判断）。
参考资料
M. Fischer, N. Lynch, and M. Paterson. Impossibility of
Distributed Consensus With One Faulty Process. Journal of the
ACM, 32(2), 1985.
转载请注明出处：www.huamo.online