科普 | 区块链核心算法之拜占庭容错算法

 在上两篇文章中有介绍到拜占庭将军问题，于战争时，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军，因为唯有达成一致的行动才能获致胜利。将军中若存在叛徒，叛徒可以采取行动以欺骗某些将军进行进攻行动，或致使他们无法做出决定，缺乏一致行动的结果则将注定战事的失利。

什么是拜占庭容错

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

安全的共识算法

拜占庭容错（BFT）就是为了解决即使出现一定数量的叛徒，整个作战计划也依然可以达成一致。我们需要一种安全的共识，并且不会给我们的地球施加巨大的能源成本。这种方法就是基于拜占庭容错（BFT）的权益证明（POS）。我们称之为BFT-PoS。 

BFT是针对状态机副本复制为主的分布式系统执行环境开发的算法，旨在 让系统中大部分的诚实节点来覆盖恶意节点或无效节点的行为。BFT算法的节 点数量是固定的，节点身份提前确定，无法动态添加或删除，只能适用于节点数 目固定的联盟链或私有链场景中。

标准的容错共识算法（如Raft和Paxos）假设当一个节点出现故障时，它只是停止工作而不回复消息。谷歌，Facebook和一些现有的数据库产品已经在他们的防火墙内使用了这一系列的共识算法，使机器有故障产生时也能确保服务仍然可用。 

但这些算法不适用于公有区块链，因为公有区块链中没有防火墙。任何拥有算力（PoW）或代币（PoS）的人都可以参与，甚至可以试图破坏网络。为了达成共识，我们需要拜占庭的容错能力。在拜占庭故障中，故障节点能以完全任意的方式运行。节点甚至可以串通来尝试作恶，并最大限度地发挥其破坏力。

因此，本质上，BFT共识算法的目的是在不信任网络（如万维网）中的节点间建立信任。但是只在同步环境中（所有的消息总是及时到达）演示了算法的理论可行性。但在现实世界中，你不能真正地相信互联网能及时交付任何东西。

虽然该理论可能难以解释或理解，但适当的BFT算法提供的最终结果很容易掌握。 与PoW区块链不同，BFT-PoS块链根本不分叉。对于双花攻击，除非1/3或更多的验证者协调进行此类攻击。而且，当1/3或更多的验证者确实导致双重花费攻击时，我们可以计算确定哪些验证者需要对攻击负责，进而可以摧毁它们的权益代币并将其从网络中剔除，就好像矿工联合起来控制整个链一样。

虽然PoW在比特币方面表现很好，但代价昂贵，速度慢，环境不友好。现在最好的选择是BFT-PoS。它是一种持久、节能的解决方案，在异步环境中运行良好。

实用拜占庭容错算法PBFT

实用拜占庭容错算法PBFT（Practical Byzantine Fault Tolerance）是针对状态机副本复制为主的分布式系统执行环境开发的算法，旨在让系统中大部分的诚实节点来覆盖恶意节点或无效节点的行为。PBFT算法的节点数量是固定的，一个节点代表一票，以少数服从多数的方式实现了拜占庭的容错演算。至多容错量以不超过全部节点数的1/3，意即如果有超过2/3的正常节点，整个系统就便可正常运作(R ≥ 3F + 1; R：节点总数，F：有问题节点总数)。节点身份提前确定，无法动态添加或删除，只能适用于节点数目固定的联盟链或私有链场景中。

PBFT算法的运作步骤为：

(1)取一个副本作为主节点，其他的副本作为备份；

(2)用户端向主节点发送使用服务操作的请求；

(3)主节点通过广播将请求发送给其他副本；

(4)所有副本执行请求并将结果发回用户端；

(5) 用户端需要等待F+1个不同副本节点发回相同的结果，作为整个操作的最终结果。

PBFT算法存在的问题:

计算效率依赖于参与协议的节点数量，不适用于节点数量过大的区块链

1.系统，扩展性差。

2.系统节点是固定的，无法应对公有链的开放环境，只适用于联盟链或私

3.有链环境。

4.PBFT算法要求总节点数n>=3f+1(其中，f代表作恶节点数)。系统的失效节点数量不得超过全网节点的1/3，容错率相对较低。

代理拜占庭容错算法DBFT

考虑到BFT算法存在的扩容性问题，NEO采用了一种代理拜占庭容错算法— —DBFT(Delegated Byzantine Fault Tolerant)。它与EOS的DPOS共识机制一样，由权益持有者投票选举产生代理记账人，由代理人验证和生成区块，以此 大幅度降低共识过程中的节点数量，解决了BFT算法固有的扩容性问题。

DBFT的算法中，参与记账的是超级节点，普通节点可以看到共识过程，并同步账本信息，但不参与记账。总共n个超级节点分为一个议长和 n-1 个议员，议长会轮流当选。每次记账时，先有议长发起区块提案(拟记账的区块内容)，一旦有至少(2n+1)/3个记账节点(议长加议员)同意了这个提案，那么这个 提案就成为最终发布的区块，并且该区块是不可逆的，所有里面的交易都是百分之百确认的，区块不会分叉。

DBFT的优点一方面是效率高，NEO每15~20秒生成一个区块，交易吞吐量可达到约1000TPS，通过适当优化，性能可达10000TPS;另一方面是其良好的最终性，区块不会分叉，以此来验证参与者的身份，保护网络安全，使区块链能够适用于对交易确认实时性要求高的真实金融场景。

DBFT的缺点也不容忽视，一方面体现在较低的容错率，当有1/3或以上超级节点为恶意节点或宕机后，系统将无法提供服务;另一方面体现在超级节点数量过少，中心化程度高。

类比到区块链系统中，其实是一样的。区块链中的共识节点（挖矿）相当于其中的将军，记账节点可能会发生故障或者被恶意控制而发送错误的消息，通常这些发生故障的节点被称为拜占庭节点，而正常的节点即为非拜占庭节点。

（本文内容由WF曲速未来独家编译，转载请注明出处。）

（本文仅代表作者观点，不代表链得得官方立场）