一、实用拜占庭容错算法(PBFT)

    拜占庭帝国即东罗马帝国，拥有巨大的财富，并对邻邦垂诞已久，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题【在分布式系统中指的是消息不仅可以被丢失、延迟、重放，还可以被伪造】。

     PBFT(Practical Byzantine Fault Tolerance)算法由Miguel Castro和Barbara Liskov在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

     PBFT是一种状态机副本复制算法，一般包括三种协议:一致性协议(agreement)、检查点协议(checkpoint)和视图更换协议(view change)。该算法要满足以下两个性质：  

    安全性(safety)：safety means nothing bad happens.                            活性(liveness)：liveness means that something good eventually happens.

    在一个拜占庭系统里面，要容忍f个拜占庭节点错误，则replica数量至少为3f+1，这是满足安全性的前提。因为网络延迟或宕机，系统存在f个节点不回复响应（f个节点包括拜占庭节点和非拜占庭节点，最坏情况f个节点全是非拜占庭节点），剩下2f+1个响应中可能有f个拜占庭节点，从而得到n-2f>f，即响应中非拜占庭节点数目大于拜占庭节点数目（f+1>f）。

    算法不依赖同步提供安全性，则必须依赖同步提供活性，否则违背FLP定理(在异步通信场景，即使只有一个进程失败了，没有任何算法能保证非失败进程能够达到一致性)。在拜占庭节点不超过f，并且delay(t)有界的情况下就能保证系统活性，delay(t)表示从消息发送到接受的时间间隔。

    在一个view里面，会从replicas中选择一个primary，其余的replicas则叫backups。如果主节点行为发生异常，则进行view change换主。                  

    游戏从client向primary发送请求开始。状态机操作，时戳。                                                                    游戏从client至少收到f+1个replicas的响应结束。视图编号，时戳，客户端身份， replica编号，请求结果。【why f+1？因为在2f+1个committed中有f个拜占庭节点表面上同意请求，实际上根本不会回复请求】

3.1重彩大戏------三阶段协议

Pre-prepare:

     Primary为客户端请求分配一个序列号n，向所有backups发现预准备消息。视图编号，消息的摘要。

Prepare:

    若满足以下条件，backups接受预准备消息：                                   1.客户端请求和预准备消息具有正确签名。                                     2.当前视图编号是v。                                                      3.backups从未在当前视图v接收过序列号为n但摘要不同的预准备请求。              4.h<n<H。【防止一个拜占庭节点选择一个大的序号来消耗序号空间】

    如果上述条件满足，backups接收预准备消息，进入prepare阶段，向其他节点广播准备消息，并将预准备和准备消息写入日志。

commit:

    如果backups收到2f【包括自己】个与预准备消息一致的准备消息，请求消息和预准备消息具有相同的视图v和序列号n，并且已将相关消息写入日志，则进入commit阶段，向其他节点广播一条确认消息。如果各节点收到2f+1条相同的commits消息，则向客户端发送一条reply消息。

3.2垃圾回收

    PBFT是一种状态机副本复制算法，replicas会将执行过消息记录在本地日志中，为了节省内存，需要一种机制来清理日志。何时来清理？在每次操作完后执行是不明智的，因为比较耗资源。可以定期清理，比如每100次清理一次。我们将请求后执行的状态称为检查点checkpoint；带证明的检查点称为stable certificate，当节点收到2f+1个checkpoint消息时，可证明稳定检查点是正确的。稳定检查点之前的日志消息均可删除。            

   当清理检查点时replica i向其他replicas广播一条检查点协议，是最近一次正确执行请求序号，是其当前状态摘要。如果每一个replica收到2f+1个具有相同序号和摘要的检查点消息，这时每一个replica可以清理序列号小于等于n的日志信息。

    检查点协议也用来更新水平线。低水平线等于最近稳定检查点的序号，高水平线，为日志大小。

3.3视图更改

    当主节点挂掉，或者在commit阶段有些节点收到2f+1个commit，有些没有收到2f+1个commit，导致状态不一致，这些状况都需要更改视图来提供系统活性和安全性。

    当请求超时，备份节点进入视图v+1，广播视图更改消息。稳定检查点序列号，是稳定检查点证明，是一个集合，包含对请求（请求的序列号大于）相关消息集合。包含2f+1个相同的准备消息。

     当视图v+1的主节点收到2f个相同个视图更改消息，向其他副本广播新视图消息，是2f+1个视图更改消息，的计算规则如下：     1.确定序列号和。其中等于中稳定检查点序列号,等于中最大prepare消息序列号。                                                  2.主节点为和之间的每一个序列号n分配pre-prepare消息。如果中包含n对应的组合，则对应的预准备消息为（也就是说序列号n对应的请求有2f+1个prepare消息，在新视图中依然提交这个请求）。如果中不包含n对应的组合，则提交null消息为，即不做任何处理。

    副本收到新视图消息后，广播一次prepare消息，进入v+1，视图更换完成。

二、拜占庭容错共识算法介绍

在区块链共识算法中，拜占庭容错（BFT）算法是一种独特且重要的解决方案，它源自拜占庭将军问题。这个问题的核心在于，如何在存在叛徒的情况下，确保忠诚节点能达成一致的决策，类似于分布式系统中的正常服务器和故障或恶意节点。BFT有三种主要版本，包括实用拜占庭容错（PBFT）、联邦拜占庭协议（FBA）和授权拜占庭容错（dBFT）。

PBFT是首个实际解决拜占庭问题的协议，具有高速和可扩展性，但主要适用于私有和许可网络，如Hyperledger Fabric和Ripple。PBFT通过预设的将军数量（如33%的容错率）保证高效运行，但其中心化的特性限制了它在公开网络的应用。Ripple的共识算法利用了PBFT，允许快速确认交易，但仅限于受信任的节点网络。

FBA，如在Stellar中采用的，强调的是吞吐量、低交易开销和网络扩展性，用户可以选择信任的验证者。与PBFT相比，FBA的去中心化程度更高，允许自由节点加入并投票，但可能牺牲部分性能。

dBFT在Neo中被应用，具有快速和可扩展性，通过代理投票支持大规模参与，但存在多个根链的风险。这种机制在交易速度和吞吐量上表现出色，但对记账节点的依赖度高，超过三分之一的记账节点故障可能导致服务中断或区块链分叉。

总结来说，BFT共识算法为分布式网络提供了在不确定性和安全性环境中达成共识的有效途径，但每个版本都有其适用场景和权衡。了解这些区别有助于选择最合适的共识机制来构建安全的区块链网络。

三、什么叫拜占庭失效

拜占庭失效

来自Wikipedia,免费的百科全书

在容错的分布式计算中，拜占庭失效可以是分布式系统中算法执行过程中的任意一个错误。这些错误被统称为“崩溃失效”和“发送与遗漏是实效”。当拜占庭失效发生时，系统可能会做出任何不可预料的反应。

这些任意的失效可以粗略地分成以下几类：

进行算法的另一步时失效，即崩溃失效；

无法正确执行算法的一个步骤；

执行了任意一个非算法指定的步骤

各个步骤由各进程执行，算法就是由这些进程执行的。一个错误的进程是在某个点出现了上述情况的进程。没有出现错误的进程是正确的进程。

参考Byzantine fault tolerance

拜占庭指拜占庭将军问题，这是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。

拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效，并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征，t表示算法可以应付的错误进程数。

很多经典算法问题只有在t<n/3是才有解，如拜占庭将军问题，其中n是系统中进程的总数。

参考文献

L. Lamport, R. Shostak, and M. Pease, The Byzantine Generals Problem, ACM Trans. Programming Languages and Systems, Vol. 4, No. 3, July 1982, pp. 382-401.

来源""