拜占庭容错（拜占庭容错问题）

拜占庭将军效果（Byzantine Generals Problem），由Leslie Lamport、Robert Shostak和Marshall Pease，在其同名论文中提出（1982年）。拜占庭将军问题往常主要指散布式对等网络节点间的通讯容错问题。在散布式网络中，不同的计节点经过交流音讯达成共识。但有时分，系统中的成员节点可以出错而发送过失的音讯，用于传递音讯的通讯网络也可以招致音讯维护，也能够具有恶意节点或被黑客突破的节点故意发送过失的消息，从而招致系统无法达成共识大约达成过失的共识。（参考： BFT Wikipedia ）

拜占庭将军问题提出后，有很多的算法被提出用于处置这个问题。这类算法统称拜占庭容错算法（BFT: Byzantine Fault Tolerance）。BFT从上世纪80年代末尾被研讨，目前曾经是一个被研讨得比拟透彻的实践，精细完成都曾经有现成的算法。

BFT算法中最典型的是PBFT（Practical BFT）。PBFT是由Miguel Castro和Barbara Liskov于1999年提出。PBFT算法处置了之前拜占庭容错算法效率不高的问题，将算法冗杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统运用中变得可行。PBFT在保证平安性和可用性的前提下，提供了 (n-1)/3 的容错性。（细节请参考： PBFT ）

PBFT之后，很多进一步提升功用或鲁棒性的BFT算法先后被提出，例如Zyzzyva、ABsTRACTs、Aardvark、RBFT等等。近几年，由于区块链的热度，有数针对区块链运用场景优化过的BFT算法也不时出现进去。固然目前PBFT已经不能说是最好的，或最适宜区块链的BFT算法。但是PBFT已经足够好了，而且在实际使用中已经十分干练。

在BFT共识机制中，网络中节点的数量和身份必需是延迟肯定好的。BFT共识机制无法做到PoW共识机制中完成的任何人都可以随时参与挖矿。另外，BFT算法无法使用到少量的节点，业内普遍以为100个节点是BFT算法的下限。所以BFT算法无法直接用于私有链，BFT算法适宜的场景是私有链和联盟链。业内默默无闻的联盟链Hyperledger fabric v0.6采用的是PBFT，v1.0又推出PBFT的改良版本SBFT。这里再特地提一句，在可信环境下共识算法一般使用激进的散布式一致算法PAXOS大约RAFT。

私有链使用BFT的一个例外是NEO，NEO使用了DBFT（delegated BFT）共识机制。DBFT共识机制下投票选出7个共识节点。这些代理节点是经过静态选出的，并完整由项目方布置。这也是NEO被外界质疑过于中心化的缘由。（参考： 早期公有链明星项目-NEO ）

BFT算法和公有链适宜的区分点在于基于BFT的PoS共识算法（BFT based PoS）。基于BFT的PoS共识算法要点有：一，网络节点经过锁定虚拟资产央求成为区块链系统的考证者（或矿工）。系统考证者的数量是静态变化的。二，系统从以后考证者中随机选择一团体作为区块提案人。三，系统考证者对区块提案中止投票表决，投票能够要中止多轮才干达成共识。每团体的投票比重与锁定的虚拟资产成比例。

基于BFT的PoS的典型例子是tendermint（Cosmos采用了tendermint作为共识中心）。

拜占庭帝国即中世纪的土耳其，具有庞大的财富，周围10个邻邦垂诞已久，但拜占庭高墙屹立，铜墙铁壁，没有一个独自的邻邦能够胜利入侵。任何单个邻邦入侵的都会失利，同时也有能够自身被其他9个邻邦入侵。拜占庭帝国进攻才干如此之强，至少要有十个邻邦中的一半上述文章内容同时进攻，才有能够突破。

但是，假定其中的一个或许几个邻邦自身允许好一同进攻，但实践进程出现背叛，那么入侵者可能都会被消灭。

于是每一方都注意行事，不敢随意置信邻国。这就是拜占庭将军问题。

在拜占庭问题中，最主要的point就是： 一切将军如何达成一致攻击拜占庭的共识 ，这当中，可能出现的状况举例如下：

用一个模型注释一下：

假定只需3团体，A、B、C，三人中假定其中一个是叛徒。当A收回进攻命令时，B假设是叛徒，他可能通知C，他收到的是“撤离”的命令。这时C收到一个“进攻”，一个“撤离“，于是C被消息迷惘，而无所适从。

假设A是叛徒。他通知B“进攻”，通知C“撤离”。当C通知B，他收到“撤离”命令时，B由于收到了司令“进攻”的命令，而无法与C坚持一致。

正由于上述缘由，在只需三个角色的系统中，只需有一个是叛徒，即叛徒数等于1/3，拜占庭问题便不可解。

能够看得出， 只需叛徒的数量大于或等于1/3，拜占庭问题不可解

从技术上了解， 拜占庭将军问题是散布式系统容错性问题 。加密货币树立在P2P网络之上，是典型的分布式系统，类比一下， 将军就是P2P网络中的节点，信使就是节点之间的通讯，进攻还是撤离的决议就是需求达成的共识 。 如果某台独立的节点计算机拓机、掉线或攻击网络搞破坏，整个系统就要中止运转，那这样的系统将十分软弱，所以容许局部节点出错或搞破坏而不影响整个系统运转是必要的 ， 这就需求算法实践上的支持，保证分布式系统在肯定量的过失节点具有的状况下，依然坚持一致性和可用性 。

而且，拜占庭将军与两军问题不同，前者假定信差没有问题，只是将军出现了叛变等问题；后者研讨信差的通讯问题。

终极处置计划到了——

如果 10个将军中的几个同时发起音讯，势必会形成系统的紊乱，形成各说各的攻击时间计划，举措难以一致 。

谁都能够发起进攻的消息，但由谁来收回呢？中本聪拙劣地在个系统参与了 发送信息的利息 ，即：

它参与的 利息就是”义务量“ —— 节点必需完成一个计算义务才干向各城邦传达消息 ，当然，谁第一个完成义务，谁才干传达消息。（这也是 任务量证明机制的意义：以检验结果的方式证明你过去所做过了几任务 ）

这种加密技术——非对称加密，完整可以处置现代难以处置的签名问题：

中本聪在想象比特币时，它采用了一种任务量证明机制叫哈希现金，在一个买卖块这要找到一个随机数，计算机只能用穷举法来找到这个随机数，可以说，能不能找到全靠运气，所以关于各个节点来说，这个世界上，只需随机才是真正的公允，完成随机的最好方法是使用数学，一切的将军在寻觅共识的进程，借助了自己都认可的数学逻辑。

当然了， 凭什么要权益停止计算任务，那么肯定要有一个鼓舞机制 ：比特币的奖励机制是每打包一个块，目前是奖励25个比特币，而拜占庭将军问题的奖励机制可以是瓜分拜占庭取得的利益。

在这个分布式网络里：

每个将军都有一份实时与其他将军同步的消息账本 。

账本里有每个将军的签名都是可以考证身份的。 如果有哪些消息不一致，可以知道消息不一致的是哪些将军 。

固然有消息不一致的，只需逾越半数赞同进攻，少数遵从少数，共识达成（只需大多数是坏人，那么就可以完成共识）。

区块链上的共识机制主要处理 由谁来结构区块 ，以及 如何维护区块链一致 的问题。

拜占庭容错问题需求解决的也十分是 谁来发动信息 ，如何 完成信息的一致同步 的问题。

注：区块链进修新人，若有不准确的中央，望指出

拜占庭帝国想要进攻一个弱小的冤家，为此派出了10支军队去突围这个冤家。这个朋友虽不比拜占庭帝国，但也足以抵御5支惯例拜占庭军队的同时攻击。基于一些缘由，这10支军队不能集合在一同单点突破，必需在兼并的突围外形下同时进攻。他们任一支军队独自进攻都毫无胜算，除非有至少6支军队同时攻击才能攻下敌国。他们聚集在敌国的周围，依托通讯兵相互通讯来商量进攻意向及进攻时间。搅扰这些将军的问题是，他们不肯定他们中能否有叛徒，叛徒可能私自变卦进攻意向或许进攻工夫。在这种外形下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程商量，从而赢取战役？这就是知名的拜占庭将军问题。

拜占庭将军问题中并不去思索通讯兵能否会被截获或无法传达信息等问题，即消息传递的信道绝无问题。Lamport已经证明了在消息可能丧失的不牢靠信道上试图经过消息传递的方式抵达一致性是不可能的。所以，在研讨拜占庭将军问题的时分，假定信道是没有问题的，然后去做一致性和容错性相关研究。

两个将军要经过信使来达成进攻还是撤离的商定，但信使可能迷路或被敌军阻拦(消息丧失或假造)，如何达成一致?

依据FLP不可能原理，两将军问题无通用解。

BFT(Byzantine Fault Tolerance), 即拜占庭容错是拜占庭将军问题在梦想世界的模型化，由于硬件过失，网络问题以及恶意攻击等缘由，分布式计算系统的计算机和网络可能会出现不可预料的行为。拜占庭容错技术被想象用来处理梦想具有的十分行为，并满意所要解决的问题的规范央求。

一般，发生缺陷的节点被称为拜占庭节点，一般的节点为非拜占庭节点。

拜占庭容错系统是一台具有n个节点的系统，整个系统关于每个央求，满意一下条件：

拜占庭系统普遍采用的假定条件包括：

拜占庭将军问题是一个诙谐的困境，最终发生了拜占庭容错系统，这些系统正在各种场景中取得普遍使用。除区块链行业外，拜占庭容错系统的一些使用案例也包括航空，航天和核电行业。

在数字货币范围中，具有高效的网络通讯以及优秀的共识机制关于任何区块链生态系统都至关主要。维护这些系统需求继续的勤劳，现有的共识算法尚未能抑制一些限制（例如可扩展性）。固然如此，工作量证明和权益证明作为拜占庭容错系统来说都是有效的方法，其潜在的应用会激起更多的创新。

适用的拜占庭容错算法

BFT 是区块链共识算法中，需要解决的一个核心问题。比特币的POW，eos的dpos，以及共识算法pos，这些公链算法，解决的是共识节点众多情况下的bft问题。

拜占庭将军问题。也称为拜占庭容错。

用来描画分布式系一致致性问题。

背景如下：

拜占庭帝国想要进攻一个弱小的朋友，为此派出了10支军队去解围这个朋友。这个敌人虽不比拜占庭帝国，但也足以抵御5支惯例拜占庭军队的同时攻击。这10支军队在兼并的解围形状下同时攻击。他们任一支军队独自进攻都毫无胜算，除非有至少6支军队（一半上述文章内容）同时攻击才能攻下敌国。他们聚集在敌国的四周，依托通讯兵骑马相互通信来磋商进攻意向及进攻时间。搅扰这些将军的问题是，他们不肯定他们中能否有叛徒，叛徒可能私自变卦进攻意向或者进攻时间。在这种形状下，拜占庭将军们才能保证有多于6支军队在同一时间一eos同发动进攻，从而赢取战役？

单从下面的说明可能无法了解这个问题的冗杂性，我们来冗杂剖析一下：

先看在没有叛徒情况下，假设一个将军A提一个进攻建议（如：明日下午1点进攻，你甘愿参与吗？）由通信兵通信区分告诉其他的将军，如果幸运中的幸运，他收到了其他6位将军上述文章内容的赞同，发起进攻。如果倒运，其他的将军也在此时收回不同的进攻建议（如：明日下午2点、3点进攻，你甘愿参与吗？），由于时间上的差异，不同的将军收到（并认可）的进攻建议可能是不一样的，这是可能出现A建议有3个支持者，B建议有4个支撑者，C建议有2个支撑者等等。

再加一点繁杂性，在有叛徒情况下，一个叛徒会向不同的将军发出不同的进攻提议（告诉A明日下午1点进攻， 告诉B明日下午2点进攻等等），一个叛徒也会可能赞同多个进攻提议（即赞同下午1点进攻又赞同下午2点进攻）。

叛徒发送前后不一致的进攻提议，被称为“拜占庭过失”，而能够处理拜占庭过失的这种容错性称为「Byzantine fault tolerance」，简称为BFT。

使用密码学算法保证节点之间的消息传送是不可窜改的， 通过下面的算法我们可以保证A将军收到B将军发来的消息确实是B将军自己的真实央求 。

我们采用的是哈希函数（散列算法）SHA256 -- 从数据（byte）值中创立无独有偶的hash值，并紧缩成摘要，将数据格式活动下去。通过这个摘要与团体私钥生成Digital Signature 和团体公钥Public-key certificate，接收方考证签名和摘要，如果是通过验证，即证明摘要方式没有经过窜改。

pbft容忍有效或者恶意节点数量 e 。为了保证整个系统可以普通运作，需要有2f+1个一般节点，系统的总结点数为 ：3f+1。即pbft算法容忍小于1/3的恶意或者有效节点。 缘由见节点作恶的极端情况

pbft是一种形态机正本复制算法，一切正本在一个view轮换进程中操作，哪些是主节点（进攻的提议者的大将军们，轮番当）通过view中其他节点（其他将军）赋予的编号和节点数集合来肯定，即：主节点p=v mod |R| 。 v：view编号，|R|节点个数，p：主节点编号。 关于状态机复制算法、view change的意义（主要是防止主节点作恶），主节点详见论文。

基于拜占庭将军问题，PBFT算法一致性确实保次要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：

[图片上传失利...(image-e3329d-1562488133052)]

首先注释一下上面各个符号表达的意义：

上面区分上图，精细说一下PBFT的方法：

依据上述流程，在N ≥ 3F + 1的情况下一致性是可能解决， N为算计算机数，F为有问题的计算机总数 。

上面一切的校验流程略去抵消息方式、签名和身份的验证，即已经保证了节点之间消息传达是不可窜改的

上述算法中，比拟主要的一个点是view change，为了能恢复之前的恳求，每一个正本节点收到消息之后或者发送消息的时分都会记载消息到外地的log记载中。当实施恳求后，正本节点需要把之前该请求的记载消息消除掉。最复杂的做法是在reply消息后，在实施一次以后状态的共识同步，但是为了俭省资源，一般在多条请求K后实施一次状态同步。这个状态同步就是checkpoint消息。

为了俭省内存，系统需要一种将日志中的 无异议消息记载 删除的机制。为了保证系统的平安性，副本节点在删除本人的消息日志前，需要确保至少 f+1 个一般副本节点施行了消息对应的请求，并且可以在视图变卦时向其他副本节点证明。另外，如果一些副本节点错过局部消息，但是这些消息已经被一切一般副本节点删除了，这就需要通过 传输局部或者部分效力状态完成该副本节点的同步 。因此，副本节点非常需要证明状态的准确性。

在每一个操作施行后都生成这样的证明是非常消耗资源的。因此，证明进程只要在请求序号可以被某个常数（比如100）整除的时分才会周期性地停止。我们将这些请求施行后取得的状态称作 检查点（checkpoint） ，并且将具有证明的检查点称作 坚定检查点（stable checkpoint） 。

上述情况是梦想情况，实践受骗副本节点i向其他节点发出checkpoint消息之后，其他节点还没有完成K条请求的互相共识，所以不会立刻对i的请求作出照应。其他节点会依照本人的处理方法和次第，向前行进和共识。但是此时i发出的checkpoint没有构成stable，为了防止i太快，逾越本人太多，于是被便会设置一个高水位H=h+L，其中L就是我们指定允许的高度差，等于checkpoint周期处理数K的整数倍，可以设置为L=2K。当副本节点i处理请求逾越高水位H时，副本节点即使接遭到请求也会视为合法请求。等候stable checkpoint发生变化，再继续向前促进处理。

如果主节点作恶，它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻请求的序号不继续。备份节点（备份主节点）应当有职责来自动检查这些序号的合法性。如果主节点掉线或者作恶不广播客户端的请求，客户端设置超机遇制，超时的话，向一切副本节点广播请求消息。副本节点检测出主节点或者下线，发起view change流程。

我们在上面讲到，当网络中有F台有问题的计算机时，至少需要3F+1台计算机才能保证一致性问题的解决，我们在这里议论一下原因。

我们可以思索：由于有F个节点为缺陷或被攻击的节点，故我们只能从N-F个节点中进行区分。但是由于异步传输，故当收到N-F个消息后，并不能肯定前面能否有新的消息。（有可能是目前收到的N-F个节点的消息中具有被攻击的节点发来的消息，而好的节点的消息由于异步传输还没有被收到。）

我们思索最坏的情况，即剩下F个都是好的节点，收到的中有F个被攻击的节点，故我们需要使得收到的中好节点的数量 (N-F)-F 大于被攻击节点的数量 F ，于是有 N-2FF ，即 N3F ，所以N的最小整数为 N=3F+1 。

pbft是需要参与认证的节点进行的。所以一个残缺的共识算法包括DPOS+PBFT。其速度是可以抵达1500tps左右的。

参考文献：

Practical Byzantine Fault Tolerance

Miguel Castro and Barbara Liskov Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139 castro,liskov @lcs .mit.edu

部分论文翻译