# BFT（拜占庭容错）共识算法 By [Untitled](https://paragraph.com/@0x5a9b15d66f74b219a6d92c093818840d96fe87da) · 2021-11-23 --- 一、BFT简介 1、拜占庭将军问题简介 拜占庭将军问题（Byzantine Generals Problem）是Leslie Lamport（2013年的图灵奖得主）用来为描述分布式系统一致性问题（Distributed Consensus）在论文中抽象出来一个著名的例子。 拜占庭将军问题简易的非正式描述如下： 拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时进攻。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。 拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，假定信道是没有问题的，然后去做一致性和容错性相关研究。 2、两将军问题 拜占庭问题前，就已经存在两将军问题(Two Generals Paradox):两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦(消息丢失或伪造)，如何达成一致? 根据FLP不可能原理，两将军问题无通用解。 3、BFT简介 BFT（Byzantine Fault Tolerance），即拜占庭容错，是分布式计算领域的容错技术，拜占庭容错来源于拜占庭将军问题。拜占庭将军问题是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理现实存在的异常行为，并满足所要解决的问题的规范要求。 区块链网络环境符合拜占庭将军问题模型，有运行正常的服务器（忠诚的拜占庭将军），有故障的服务器，还有破坏者的服务器（叛变的拜占庭将军）。共识算法的核心是在正常的节点间形成对网络状态的共识。 通常，发生故障的节点被称为拜占庭节点，而正常的节点为非拜占庭节点。 拜占庭容错系统是一个拥有n台节点的系统，整个系统对于每一个请求，满足以下条件： 　　A、所有非拜占庭节点使用相同的输入信息，产生同样的结果； 　　B、如果输入的信息正确，那么所有非拜占庭节点必须接收这个信息，并计算相应的结果。 拜占庭系统普遍采用的假设条件包括： 　　A、拜占庭节点的行为可以是任意的，拜占庭节点之间可以共谋； 　　B、节点之间的错误是不相关的； 　　C、节点之间通过异步网络连接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设消息在有限的时间里能传达到目的地； 　　D、服务器之间传递的信息，第三方可以嗅探到，但是不能篡改、伪造信息的内容和验证信息的完整性。 原始的拜占庭容错系统由于需要展示其理论上的可行性而缺乏实用性。另外，还需要额外的时钟同步机制支持，算法的复杂度也是随节点增加而指数级增加。 二、PBFT算法 1、PBFT算法简介 PBFT（Practical Byzantine Fault Tolerance），即实用拜占庭容错算法，由Miguel Castro和Barbara Liskov在1999年发表的论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出。PBFT算法可以工作在异步环境中，并且通过优化解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行，目前已得到广泛应用。PBFT算法可以在失效节点不超过总数1/3的情况下同时保证Safety和Liveness。 PBFT 算法采用密码学相关技术(RSA 签名算法、消息验证编码和摘要)确保消息传递过程无法被篡改和破坏。 2、PBFT算法原理 PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，通常假设故障节点数为f个，整个服务节点数为|R|=3f+1个，f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但额外的副本除了降低性能外不能提高可靠性。 所有的副本在一个被称为视图（View）的轮换过程中运作。在某个视图中，一个副本作为主节点（primary），其它的副本节点作为备份节点（backups）。视图是连续编号的整数。主节点由公式p = v mod |R|计算得到，v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图轮换过程。 PBFT算法实现流程如下： （1）REQUEST 客户端C向主节点p发送 1. 请求。 o:请求的具体操作 t:请求时客户端追加的时间戳 c：客户端标识。 REQUEST: 包含消息内容m，以及消息摘要d(m)。 客户端对请求进行签名。 （2）PRE-PREPARE 主节点收到客户端的请求，需要对客户端请求消息签名是否正确进行校验。 非法请求则丢弃。正确请求，分配一个编号n，编号n主要用于对客户端的请求进行排序。然后广播一条 <, m> 1. 消息给其它副本节点。 v：视图编号 d客户端消息摘要 m：消息内容 1. 进行主节点签名。 n是要在某一个范围区间内的\[h, H\]。 （3）PREPARE 副本节点i收到主节点的PRE-PREPARE消息，需要进行以下校验： A、主节点PRE-PREPARE消息签名是否正确。 B、当前副本节点是否已经收到了一条在同一v下并且编号也是n，但是签名不同的PRE-PREPARE信息。 C、d与m的摘要是否一致。 D、n是否在区间\[h, H\]内。 非法请求则丢弃。正确请求，副本节点i向其它节点包括主节点发送一条 1. 消息, v, n, d, m与上述PRE-PREPARE消息内容相同，i是当前副本节点编号。 1. 进行副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中，用于视图轮换过程中恢复未完成的请求操作。 PREPARE阶段如果发生视图轮换会导致丢弃PREPARE阶段的请求。 （4）COMMIT 主节点和副本节点收到PREPARE消息，需要进行以下校验： A、副本节点PREPARE消息签名是否正确。 B、当前副本节点是否已经收到了同一视图v下的n。 C、 n是否在区间\[h, H\]内。 D、d是否和当前已收到PRE-PPREPARE中的d相同 非法请求则丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息，表明网络中的大多数节点已经收到同意信息，则向其它节点包括主节点发送一条 1. 消息，v, n, d,  i与上述PREPARE消息内容相同。 1. 进行副本节点i的签名。记录COMMIT消息到日志中，用于视图轮换过程中恢复未完成的请求操作。记录其它副本节点发送的PREPARE消息到log中。 COMMIT阶段用来确保网络中大多数节点都已经收到足够多的信息来达成共识，如果COMMIT阶段发生视图轮换，会保存原来COMMIT阶段的请求，不会达不成共识，也不会丢失请求编号。 （5）REPLY 主节点和副本节点收到COMMIT消息，需要进行以下校验： A、副本节点COMMIT消息签名是否正确。 B、当前副本节点是否已经收到了同一视图v下的n。 C、d与m的摘要是否一致。 D、n是否在区间\[h, H\]内。 非法请求则丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息，说明当前网络中的大部分节点已经达成共识，运行客户端的请求操作o，并返回 1. 给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。记录其它副本节点发送的COMMIT消息到log中。 3、PBFT算法的垃圾回收 为了确保在视图轮换的过程中，能够恢复先前的请求，每一个副本节点都记录一些消息到本地的log中，当执行请求后副本节点需要把之前该请求的记录消息清除掉。最简单的做法是在Reply消息后，再执行一次当前状态的共识同步，但成本比较高，因此可以在执行完多条请求K（例如：100条）后执行一次状态同步。状态同步消息就是CheckPoint消息。 --- *Originally published on [Untitled](https://paragraph.com/@0x5a9b15d66f74b219a6d92c093818840d96fe87da/bft)*