拜占庭容错的基本概念及实现方法解析

在过去的一个月里，我们一直致力于我们的视图更改协议。这是任何区块链的核心部分，我们可以从中判断协议是经过许可的还是无许可的，以及它是如何实现去中心化。

代码在这里：harmony/consensus。

我们在6月28日在4个分片上推出了Day ONE主网，共有600个节点。在过去的830，000个区块中，它一直运行顺畅。

在我们之前的测试中，我们观察到由于网络状况不佳而在某些分片中发生了视图更改（即领导者更改）。我们还通过杀死领导者节点以及其他类型的攻击来手动触发视图更改。攻击发生后视图发生了变化，网络按预期继续运行 - 耶！！

在下文中，我们将首先解释拜占庭容错的基本概念，然后我们会介绍如何做出改进使得能够在实践中处理大量节点，最后介绍一下整体的代码结构和一些实现细节。

什么是拜占庭容错？

一个分布式系统是由多个节点组成，其中每个节点都是独立的服务器。它们通过网络发送消息并根据它们遵循的协议执行某些任务来相互通信。

这个过程中会出现很多类型的错误的类型，但它们基本上可以分为两大类。第一种错误是节点崩溃、网络故障、丢包等，这种错误类型的节点是没有恶意的，属于非拜占庭错误。

第二种类型是节点可能是恶意的。它们可以任意行动，不遵守协议规则。例如，验证器可以延迟或拒绝中继网络中的消息、领导者可以提出无效块、或者节点可以向不同的对等体发送不同的消息。在最坏的情况下，恶意节点可能会相互协作。这些被称为拜占庭错误。

考虑到这两种错误，我们希望系统始终能够保持两个属性：一致性（consistency）和活性（liveness）。

在区块链术语中，一致性意味着诚实的节点必须为任何给定的块数/高度提交相同的块；活性意味着链高度必须保持增长而不会停滞。

一个被许可的网络中只会出现第一类错误（非拜占庭），这比较容易解决。例如，我们可以选择一个性能很强的节点作为领导者，所有其他节点将只听取领导者广播的内容并信任领导者建议的任何块。在这种情况下，我们只需要注意第一类错误，特别是当错误发生在领导者身上时。

对于去中心化的网络，我们不能信任任何节点，因为第二种错误可能发生在任何节点中。这样我们只能基于一个基本假设，即恶意节点无法伪造其他节点的签名。密码学理论证明伪造签名的难度非常高，以至于今天的计算机在任何的实际时间长度内都无法破解。当量子计算机准备就绪时，情况可能会改变。但那时，我们将使用量子抗性加密算法。

拜占庭容错协议是一种即使系统中存在恶意节点也能保证分布式系统的一致性和活性的协议。所有这些协议都有一个基本假设，即恶意节点的数量小于某个阈值。这很容易理解，如果有超过50％的恶意节点，那么网络完全由恶意节点控制。

比特币的工作量证明（PoW）要求不到50％的节点（在计算能力意义上）是恶意的。然而，自私挖矿（selfish mining）将基本假设降低到25％。当只有少于在总计算能力小于25％的节点（是恶意的，PoW系统才是安全的。

在传统的分布式系统中有着对拜占庭容错协议深入的研究。事实证明，在Lamport的经典论文中，恶意节点应少于网络的33％。后来，著名的实用拜占庭容错（PBFT）论文让这种系统变得可实用化。

但是，依然还有两个问题。首先，这样的系统是经过许可的，不允许任意节点加入和离开。其次，它不能扩展到超过数百个节点。第一个问题源于女巫攻击（Sybil Attack），恶意用户可以轻松创建许多假身份并接管大部分网络。不过，这个问题首先在中本村的比特币白皮书中被解决了，主要是从经济效应的角度考量。在工作量证明（PoW）之后，有许多新的设计，例如股权证明（PoS），权威证明（PoA）等。我们不计算节点的数量，而是计算投票权的数量。在PoS中，节点的投票能力与其放样量（staking）成比例。第二个问题可以通过使用BLS签名方案的聚合签名解决，这在FBFT部分中有解释。

实用拜占庭容错

像Raft和Paxos这样的协议主要用于处理第一类系统错误。实用拜占庭容错算法（PBFT）是现实世界里首批能够同时处理第一类和第二类错误的拜占庭容错协议之一。

我们将始终假设有N个节点最多有f个恶意节点，其中N = 3f+1。PBFT中有两种模式，即普通共识（简称正常）模式和视图更改模式。正常模式看起来像这样（在区块链中，可以忽略客户端请求和回复）：

在一个视图中（一个视图是类似一轮的概念），有3个步骤/阶段：预先准备（或宣布）、准备和提交。

1. 在预准备（宣布）阶段，领导者将向其他节点（称为验证者）广播宣布消息（announce message）（例如，包含最新交易的区块）。当验证者收到宣布消息时，它进入准备阶段。

2. 在准备阶段，在验证者接收到宣布消息之后，它将向每个节点广播准备消息（例如，在blockhash上的签名）。当验证者（包括领导者）收到足够的（即≥2f+1）准备消息时，它将进入提交阶段。

3. 在提交阶段，验证者（包括领导者）将发送提交消息（例如在| blockNum | blockHash |上的签名）当验证者收到足够的（≥2f+ 1）提交消息时。它可以安全地提交区块。这结束了一轮正常的共识过程。

请注意，一般PBFT和区块链PBFT之间存在一些差异。主要区别在于区块链在两个区块之间是“同步的”，即我们不能在提交h（区块号）之前继续提交区块h+1。在传统的PBFT中，我们可以在请求h之前提交客户请求h+1。PBFT将保证所有节点的一致性。

从这个意义上说，区块链使共识过程更简单。确切地说，PBFT中有一个被称为“检查点过程”的步骤。检查点（checkpoint）是一个证书，其中序列号（在区块链中，即是区块号）小于或等于检查点的区块都被视作已经最终确定，不可更改。在区块链中，每个已经确定的区块，都可以被视为检查点。

当验证者在共识超时（ΔT≥T0）之前，如果还没有提交新块，验证器将开始发送视图更改信息（v→v+1），每个验证者都会选择一样的新的领导者。如果视图更改无法在超时（ΔT≥T1）之前完成，则验证者将建议另一个新的视图更改（v+1→v+2，同时视图更改超时间隔增加到2*T1）。

视图更改模式有两个步骤/阶段：

1. 验证者通过向新领导者发送包含≥2f+ 1个准备消息的视图更改消息来启动视图更改。如果它并没有收到足够的准备消息，它只需发送空的视图更改消息，给新的领导者。

2. 新领导者收集足够的（≥2f+ 1）视图更改消息并广播接收到的所有视图更改消息（新视图消息）。然后新领导者切换到正常模式。验证在收到来自新领导者的新视图消息时切换到正常模式，同时停止视图更改计时器并启动共识计时器。如果验证程序在视图更改超时之前未收到新的视图消息，则会将viewID增加1并开始另一个新的视图更改。

视图更改可以确保网络的活性。在视图更改过程中，我们需要确保提交的区块在整个视图更改中也是一致的。简单来说，接收2f+1准备消息（prepare message）只能确保同一视图中的一致性。接收2f+1个提交消息（commit message）可确保不同视图之间的一致性。当节点收到2f+1提交消息时，它可以安全地将块提交到区块链中。PBFT协议确保即使在视图更改的情况下，任何诚实节点都提交相同的区块。

一致性和活性

PBFT的一个关键概念是法定人数。法定人数是具有至少2f+1个节点的任何子集。由于总共有3f+1个节点，因此任何两个法定人数将至少有f+1个节点相交。因为最多有f个恶意节点，故在两个法定人数的交集中将至少包含一个诚实节点。这就是我们需要法定人数来采取任何行动的原因。

一个视图中的一致性指的是：假设一个节点收到2f+1准备消息，这些2f+1个节点将形成一个法定人数。请注意，任何两个法定人数中将至少有一个共同的诚实节点，这意味着任何两个这样的法定人数在其准备消息中不能包含不同的区块哈希，否则共同的诚实节点允许两个相同高度的不同区块，这与它诚实的事实相矛盾。

不同视图的一致性指的是：假设一个节点收到2f+1提交消息，这些2f+1个节点形成一个法定人数，将其表示为Q1。当一个诚实的节点开始视图更改时，它会将准备好的消息（包含2f+1准备消息）发送给新的领导者。新领导者需要收集2f+1个视图更改消息（表示为法定人数Q2）才能发送新的试图消息。Q1和Q2再次包含至少一个诚实节点。此节点包含2f + 1个准备消息，因为它在发送其提交消息之前必须先收到了足够的准备消息。这确保了不同视图中的诚实节点将提交相同的区块。

活性 ：每个节点都有一个用于正常共识过程的计时器（具有T0超时）和用于视图更改过程的计时器（具有k*T1超时，其中k是在验证器可以切换回正常模式之前发生了多少视图更改）。当计时器超时时，节点将通过增加一个视图来启动视图更改。在连续的领导者未能发送正确的新视图消息的情况下，视图更改计时器的超时时段将增加，以避免频繁的视图更改并确保最终足够的诚实节点将与诚实的新领导者具有相同的viewID。

快速拜占庭容错

作为对PBFT的改进，Harmony的共识协议在通信复杂性方面是线性可扩展的，因此我们将其称为快速拜占庭容错（FBFT）。在FBFT中，领导者不是要求所有验证者广播他们的投票，而是运行多签名的签名过程以在O（1）大小的多签名中收集验证者的投票，然后广而播之。因此，和接收O（N）签名不同，每个验证器仅接收一个多签名，从而将通信复杂度从O（N²） 减小到O（N）。通过对视图更改消息的一些修改，视图改变复杂度也可以减少到O（N）。

BLS签名方案

在这里，我们对Boneh-Lynn-Shacham（BLS）签名方案进行了非常简短的数学介绍，这是FBFT和PBFT之间的主要区别。BLS签名方案基于椭圆曲线配对。令E（Fp）为有限域Fp上的椭圆曲线，其中p为大质数。我们在此曲线上选择一个基本参考点g。私有BLS密钥是从Fp采样的随机数α，公钥是α⋅g，是椭圆曲线E上的一个点。给定一个消息m，签名计算为σ=α⋅H（m），这也是E上一个点，其中H是哈希到E的函数。在两条椭圆曲线E1和E2上的双线性映射e满足一下情况：

e（α⋅g1，g2）=e（g1，α⋅g2），g1∈E1，g2∈E2

e（g0+g1，g2）=e（g0，g2）+e（g1，g2），g0，g1∈E1，g2∈E2

e（g1，g2+g3）=e（g1，g2）+e（g1，g3），g1∈E1，g2，g3∈E2

现在我们可以看到如何通过聚合公钥来验证k个签名。

e（g1，σ1+⋯+σk）=e（g1，α1⋅H（m）+⋯+αk⋅H（m））

=e（α1⋅g1+⋯+αk⋅g1，H（m））

请注意，聚合签名就是一个普通签名，也就是椭圆曲线上的一个点，聚合公钥就是一个普通公钥，也是椭圆曲线上的一个点。这将2f + 1签名简化为仅1个聚合签名，这对于减少共识协议中的网络流量至关重要。

正常模式

在传统的PBFT中，节点在每轮共识中发送或接收的总消息大小是O（N²）。这是因为在准备和提交阶段，每个节点需要收集2f+1=O（N）个签名并将它们广播到网络中的每个节点（即O（N）个节点）。通过使用BLS签名方案，我们将2f+1个签名聚合成一个签名，这样，准备和提交阶段的消息大小为O（1），从而将总大小从O（N²）减少到O（1）回合。为了从BLS方案中受益，每个验证器将仅向领导者发送准备和提交消息，并且领导者负责收集足够的》=2f+1个签名并将它们聚合成一个聚合签名，之后领导者分别在准备/提交阶段发送准备好/已提交的消息。从领导者的角度来看，这三个阶段是同步的，但从验证者的角度来看，他们仍然可以不按顺序接收消息，例如：验证者可以在宣布消息之前接收准备好的消息，但是在这种情况下，其准备签名将不会在准备好的消息中包含。

正常模式分为三个阶段：

1. 在宣布阶段，领导者将向验证者广播宣布消息（例如提议块）。当验证器收到宣布消息时，它进入准备阶段

2. 在准备阶段，验证器向领导者发送准备消息（例如，在blockhash上签名）。当领导者收到足够多的（即≥2f+1）准备消息时，它会聚合从验证者收到的准备消息上的签名，并发出准备好的消息，其中包含聚合的准备签名。然后领导者进入提交阶段。验证器在收到来自领导者的准备好的消息时进入提交阶段。

3. 在提交阶段，验证器向leader发送提交消息（例如|blockNum|blockHash|上的签名）。当领导者收到足够的（即≥2f+ 1）提交消息时，它会聚合从验证器接收的提交消息的签名，并发出提交消息，其中包含聚合的提交签名。然后领导者完成一个视图/回合。验证器在收到已提交的消息后完成一个视图/回合。当领导者或验证者完成一轮时，它将重新启动共识计时器。

在步骤3，也就是提交阶段，验证者在blockNum和blockHash上发送带有签名的提交消息。这可用于新加入网络的节点确认它是否和当前网络同步，同时不至于被恶意领导者欺骗。在状态同步模式部分中解释了共识过程如何与状态同步进行交互。

领导者选举

验证程序启动视图更改过程有两个原因。一个原因是当验证器检测到领导者在一个视图中提出两个不同的宣布消息时，它将立即开始视图更改。另一个原因是验证者在超时后没有任何进展。有两种超时：正常共识模式下的超时和视图更改模式下的超时。

在我们的区块链中，我们有了epoch的概念。每个epoch包含X个块（例如X = 1000）。在每个epoch的开始阶段，委员会成员都是由在信标链中为这个epoch下注的人决定的。委员会成员的顺序由该时期的VDF随机性唯一确定。在一个epoch中，委员会将始终保持不变。假设顺序列表是［v0，…，vn］，然后在epoch一开始，领导者是v0。如果发生视图更改，则下一个领导者是v1，依此类推。在这里，我们假设每个验证者具有相同的投票权。

视图更改模式

视图更改过程如下：

1. 当共识定时器超时，节点通过向新的领导者发送包括视图ID（viewID）和准备好（prepared message）的消息（包含≥2f+1个聚合签名）的视图更改消息来开始视图更改。如果它没有收到准备好的消息，那它就只是发送空的视图更改消息，只包括viewID上的签名但不包括准备好的消息。

2. 当新领导者收到足够的（≥2f+1）视图更改消息时，它会聚合viewID的签名，并从视图更改消息中选择一个准备好的消息。它广播新的视图消息，包括聚合签名以及选择出的准备消息。然后新领导者切换到正常共识模式。验证者在收到来自新领导者的新视图消息时切换到正常共识节点，同时停止视图更改计时器并启动共识计时器。如果验证程序在视图更改超时之前未收到新的视图消息，则会将viewID增加1并开始另一个新的视图更改。

第二步要求每个验证器在viewID上发送签名。目的是用于防备恶意领导者。确切地说，前一个领导者可以在准备阶段向不同的验证者发送不同的聚合签名。只要聚合签名有效，验证器就会接受它并在发生视图更改时提出它。在这种情况下，每个视图更改消息都包含不同的签名，新领导者不能进行签名聚合，所以新视图消息的大小为O（N），这是因为新的领导者必须证明接收到足够的有效视图更改消息。如果每个人都在viewID上签名，新的领导者很容易聚集签名，这样可以将新的试图消息的大小减少到O（1）。只有这样，我们才能在视图更改的情况下扩大网络中的节点数量。

状态同步模式

我们允许节点在区块链中自由加入和离开。当新节点加入共识时，它必须先进行状态同步，然后才能验证共识消息。此外，还存在节点在视图更改模式下卡住的情况。例如，当验证程序网络连接速度较慢时，可能无法在超时之前取得任何进展。在这种情况下，它将开始视图更改。但是，它无法从视图更改模式中退出，因为所有其他节点都在向前移动，视图更改会失败。在这种情况下，此节点需要执行状态同步才能赶上。

基本过程很简单。节点通过将其当前块高度和已提交消息中的最新块高度进行比较，如果检测出它不同步时，它将切换到状态同步模式并开始执行状态同步。完成状态同步后，它会切换到正常模式。

为了在状态同步完成后加入共识，节点需要知道谁是当前的领导者以及当前的viewID是什么。一种解决方案是盲目地接受来自共识消息的领导者和viewID。这种方法使恶意领导者有机会在共识消息中发送很大的viewID，强制使得每个验证者开始状态同步。更好的方法是仅在接收提交消息的时候接受领导者和viewID信息。在这种情况下，恶意领导者不能欺骗新节点。但它减缓了新节点加入共识的过程，因为在更新领导者和viewID之前，它无法验证宣布消息和准备好的消息。我们选择的方法是将领导者和viewID信息添加到区块头中。当节点完成状态同步时，它可以从最新的区块头中读取信息。如果在状态同步期间发生视图更改，那么来自最新块的信息已经过时。在这种情况下，新节点在收到提交的消息时通过更新领导者和viewID信息仍然可以得到最新的信息。

状态转换

下图是验证器的状态转换图。 领导者的状态转换相对比较简单在此省略。

有5种模式：3种正常模式（A：宣布 ，P：准备，C：提交），视图更改模式（VC）和状态同步模式（S， Syncing）。

模式之间的转换由不同的条件触发，例如接收特定类型的消息或满足某些条件，如超时。

条件列表：am（宣布消息announce message），pm（准备好的消息prepare message），cm（提交消息commit message），tc（尝试追赶成功 try catchup），to（超时 time out），nv（新视图消息new view），is（同步in sync），os（不同步out of sync）。