拜占庭容错（区块链系统支持拜占庭容错）

拜占庭问题

拜占庭帝国即中世纪的土耳其，拥有巨大的财富，周围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个比特币，而拜占庭将军问题的奖励机制可以是瓜分拜占庭获得的利益。

在这个分布式网络里：

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

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

尽管有消息不一致的，只要超过半数同意进攻，少数服从多数，共识达成（只要大多数是好人，那么就可以实现共识）。

区块链上的共识机制主要解决 由谁来构造区块 ，以及 如何维护区块链统一 的问题。

拜占庭容错问题需要解决的也同样是 谁来发起信息 ，如何 实现信息的统一同步 的问题。

注：区块链学习新人，若有不正确的地方，望指出

共识算法4 (BFT)

拜占庭将军问题（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作为共识核心）。

拜占庭容错和PBFT共识算法

实用的拜占庭容错算法

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

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

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

背景如下：

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？

单从上面的说明可能无法理解这个问题的复杂性，我们来简单分析一下：

先看在没有叛徒情况下，假如一个将军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

部分论文翻译

版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。