共识算法 BFT PBFT

BFT (Byzantine Fault Tolerance)称为拜占庭容错。拜占庭容错技术是一类分布式计算领域的 容错技术。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意攻 击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行 为，并满足所要解决的问题的规范要求。

拜占庭将军问题

拜占庭容错技术来源于拜占庭将军问题。拜占庭将军问题是LeslieLamport (2013年的图灵讲得 住）用来为描述分布式系统一致性问题（Distributed Consensus)在论文中抽象出来一个著名的例子。 拜占庭帝国想要进攻一个强大的敌人，为此派出了 10支军队去包围这个敌人。这个敌人虽不比拜 占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时 攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻 下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这 些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在 这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而蠃取战斗？

拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信 道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式 达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，已经假定了信道是没有问题 的.

我们将拜占庭将军问题简化成了，所有忠诚的将军都能够让别的将军接收到自己的真实意图，并 最终一致行动；而形式化的要求就是，" 一致性"与"正确性"。

  • 一致性：每个忠诚的将军必须收到相同的命令值Vi (Vi是第i个将军的命令）
  • 正确性：如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的Vi相同。

Lamport对拜占庭将军的问题的研究表明，当n > 3m时，即叛徒的个数m小于将军总数的n的 1/3时，通过口头同步通信（假设通信是可靠的），可以构造同时满足" 一致性"和"正确性"的解 决方法，即将军们可以达成一致的命令。

拜占庭容错系统

区块链网络的记账共识和拜占庭将军的问题是相似的。参与共识记账的每一个节点相当于将军， 节点之间的消息传递相当于信使，某些节点可能由于各种原因而产生错误的信息传递给其他节 点。通常这些发生故障的节点被称为拜占庭节点，而正常的节点即为非拜占庭节点。 假设分布式系统拥有n台节点，并假设整个系统拜占庭节点不超过m台（n^ 3m+ 1)，拜占庭容 错系统需要满足如下两个条件：

  • 所有非拜占庭节点使用相同的输入信息，产生同样的结果。在区块链系统中，可以理解为， 随机数相同、区块算法相同、原账本相同的时候，计算结果相同。
  • 如果输入的信息正确，那么所有非拜占庭节点必须接收这个消息，并计算相应的结果。在区 块链系统中，可以理解为，非拜占庭节点需要对客户的请求进行计算并生成区块。 另外，拜占庭容错系统需要达成如下两个指标：
  • 安全性：任何已经完成的请求都不会被更改，它可以在以后请求看到。在区块链系统中，可 以理解为，已经生成的账本不可篡改，并且可以被节点随时查看。
  • 活性：可以接受并且执行非拜占庭客户端的请求，不会被任何因素影响而导致非拜占庭客户 端的请求不能执行。在区块链系统中，可以理解为，系统需要持续生成区块，为用户记账， 这主要靠挖矿的激励机制来保证。

在分析拜占庭问题的时候，假设信道是可信的。拓展开来，在拜占庭容错系统，普遍采用的假设 条件包括：

  • 拜占庭节点的行为可以是任意的，拜占庭节点之间可以共谋；
  • 节点之间的错误是不相关的；
  • 节点之间通过异步网络连接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设 消息在有限的时间里能传达到目的地；
  • 节点之间传递的信息，第三方可以嗅探到，但是不能篡改、伪造信息的内容和破坏信息的完 整性。

实用拜占庭容错系统

原始的拜占庭容错系统由于需要展示理论上的可行性而缺乏实用性。另外，算法的复杂度也是随节点的增加而呈指数级增加。实用拜占庭容错系统（Practical Byzantine Fault Tolerance,PBFT)降低了拜占庭协议的运行复杂度，从指数级别降低到多项式级别，使拜占庭协议在分布 式系统中应用成为可能。

什么是实用拜占庭容错系统

实用拜占庭容错系统是一类"状态机"拜占庭系统（这里的状态机可以理解为"系统状态"，以区块 链记账为例，系统每新增一个区块，账本就更新到一个新的状态。前面讲过，拜占庭容错系统是 一个强一致性协议，每次记账后系统都会达成新的状态。），要求系统所有节点共同维护一个状 态，所有节点采取的行动一致。 实用拜占庭容错系统需要运行三类基本协议：

  • 一致性协议：解决如何达成共识
  • 检查点协议：类似于操作系统的还原点
  • 视图更换协议：系统的每个服务器节点在同样的配置信息下工作，该配置信息被称为"视 图"。配置信息由主节点确定，主节点更换，视图也随之变化。

我们主要关注支持系统日常运行的一致性协议。

PBFT的一致性协议

—致性协议至少包含请求（request)、序号分配（pre-prepare)、响应（reply)三个阶段。根 据协议设计的不同，可能包含相互交互(prepare)、序号确认(commit)等阶段。 PBFT系统通常假设故障节点个数为m个，而整个服务节点数为3m+1个。

在这里插入图片描述

上图显示了_个简化的PBFT的协议通信模式，其中C为客户端，N0~N3为服务节点，NO为主节 点，N3为故障节点。协议的节本过程如下：

  • Request:客户端发送请求，激活主节点的服务操作
  • 当主节点接收请求后，启动三阶段的协议以向各从节点广播请求
    • Pre-Prepare:主节点给请求赋值一个序列号n，广播序号分配消息和请求消息，并构造 PRE-PREPARE消息给各从节点
    • Prepare:从节点接收PRE-PREPARE消息，并向其他服务节点广播PREPARE消息
    • Commit:各节点对视图内的请求和次序进行验证后，广播COMMIT消息，执行收到的 客户端的请求并给客户端以响应
  • Reply:客户端等待来自不同节点的响应，若有m+1个响应相同，则该响应即为运算的结果

    PBFT演示

    在n^3m + 1的情況下一致性是可能解決的，其中，n为总节点数，m为恶意节点总数。我们模 拟一下PBFT:

n = 4, m = 0：

节点 得到数据 最终结果
A 1111 1
B 1111 1
C 1111 1
D 1111 1

n = 4, m = 1：

节点 得到数据 最终结果
A 1110 1
B 1101 1
C 1011 1
D 0111 1

n = 4, m = 2：

节点 得到数据 最终结果
A 1100 NA
B 1001 NA
C 0011 NA
D 0110 NA

由此可以看出，实用拜占庭容错系统能够容纳将近1/3的拜占庭节点。

实用拜占庭容错系统在很多场景都有应用，在区块链应用中，一般适合于对强一致性有要求的私 有链和联盟链场景。例如，在旧M主导的区块链超级账本项目中，实用拜占庭容错系统是一个可 选的共识协议。

其他的拜占庭算法

dBFT (delegated BFT)授权拜占庭容错算法

小蚁采用的dBFT机制，是由权益来选出记账人，然后记账人之间通过拜占庭容错算法来达成共 识，此算法在PBFT基础上进行了以下改进：

  • 将C/S架构的请求响应模式，改进为适合P2P网络的对等节点模式；
  • 将静态的共识参与节点改进为可动态进入、退出的动态共识参与节点；
  • 为共识参与节点的产生设计了一套基于持有权益比例的投票机制，通过投票决定共识参与节 点（记账节点）；
  • 在区块链中引入数字证书，解决了投票中对记账节点真实身份的认证问题。

dBFT的优点是：专业化的记账人，可以容忍任何类型的错误，记账由多人协同完成，每一个区 块都有最终性，不会分叉，算法的可靠性有严格的数学证明。dBFT机制最核心的一点，就是最 大限度地确保系统的最终性，使区块链能够适用于真正的金融应用场景。

BFT-DPoS

E〇S为了改进传统的 DPoS 算法，我们可以借鉴 PBFT (Practical Byzantine Fault Tolerance,拜占庭容错算法）的机制。在传统DPoS共识机制中，我们让每个见证人在出块时向全网广播这 个区块，但即使其他见证人收到了目前的新区块，也无法对新区块进行确认，需要等待轮到自己 出块时，才能通过生产区块来确认之前的区块。

在新的机制下，每个见证人出块时依然全网广播，其他见证人收到新区块后，立即对此区块进行验证，并将验证签名完成的区块立即返回出块见证人，不需等待其他见证人自己出块时再确认。 从当前的出块见证人看来，他生产了一个区块，并全网广播，然后陆续收到了其他见证人对此区 块的确认，在收到2/3见证人确认的瞬间，区块（包括其中的交易）就不可逆了。交易确认时间 大大缩短，从45秒缩短至3秒左右（主要为等待生产区块的时间）。这种机制可以称为初级版的BFT-DPoS共识机制。

为了挖掘EOS系统的性能，Daniel Larimer在以上基础上又进行了修改。首先，他将出块速度由 3秒缩短至0.5秒，理论上这样可以极大提升系统性能，但帯来了网络延迟问题：0.5秒的确认 时间会导致下一个出块者还没有收到上一个出块者的区块，就该生产下一个区块了，那么下一个 出块者会忽略上一个区块，导致区块链分叉（相同区块高度有两个区块）。比如：中国见证人后 面可能就是美国见证人，中美网络延迟有时高达300ms，很有可能到时美国见证人没有收到中国 见证人的区块时，就该出块了，那么中国见证人的区块就会被略过。

为解决这个问题，Daniel Larimer将原先的随机出块顺序改为由见证人商议后确定的出块顺序， 这样网络连接延迟较低的见证人之间就可以相邻出块。比如：日本的见证人后面是中国的见证 人，再后面是俄罗斯的见证人，再后面是英国的见证人，再后面是美国的见证人。这样可以大大 降低见证人之间的网络延迟。使得0.5秒的出块速度有了理论上的可能。

为了保证万无一失，不让任何一个见证人因为网络延迟的意外而被跳过，Daniel Larimer让每个见证人连续生产6个区块，也就是每个见证人还是负责3秒的区块生产，但是由最初的只生产1 个变成生产6个。最恶劣的情况下，6个区块中，最后一个或两个有可能因为网络延迟或其他意 外被下一个见证人略过，但6个区块中的前几个会有足够的时间传递给下一个见证人。

再来讨论BFT-DPoS的交易确认时间问题：每个区块生产后立即进行全网广播，区块生产者一边 等待0.5秒生产下一个区块，同时会接收其他见证人对于上一个区块的确认结果。新区块的生产 和旧区块确认的接收同时进行。大部分的情况下，交易会在1秒之内确认（不可逆）。这其中包 括了 0.5秒的区块生产，和要求其他见证人确认的时间。

EOS系统规定，一旦区块达到不可逆状态（2/3见证人确认），就无法在此之前进行分叉，保证 了交易的永久可信。另外，即使多数见证人想分叉区块链，也只能以相同的速度（0.5秒）与主 链竞争，就算主链只剩下一个见证人，分叉链也永远不会追上主链，保证了系统的稳定。