拜占庭容错系统的设计已经有几十年的历史，最近区块链解决方案的蓬勃发展也不断推动了这方面的研究。尽管大量文献对如何提高一致性系统的可靠性、健壮性和可恢复性进行了讨论和研究，但对于具有最终确认块的状态机复制机制，能够用于解决大规模行业案例的相关研究却很少。本文不仅可以作为教材，也可以作为在区块链生态学中使用拜占庭容错代理通信的科学参考。

委托拜占庭容错：技术细节、挑战与展望

本小节是社区黄皮书[1]的一部分：社区驱动的NEO区块链技术规范。

对于部分同步和完全异步的拜占庭容错系统(郝等2018；段、赖特尔、张2018；Miller et al. 2016)有很多相关的研究文献；然而，很少有研究能够真正应用于不同类型的分散应用智能合同(SC)场景。值得注意的是，与涉及状态机复制的智能合约事务的持久性要求(Schneider 1990)相比，更新存储状态的应用程序将带来不同的挑战。此外，要考虑的第二个重要事实与更新的账簿信息的确定性有关。最终用户、商家和交易所都想清楚地知道他们的交易是否已经被处理或者是否可能被退回。与以往文献中的大多数研究不同，新区块链提出了一种共识机制，最终确认第一层网络上的一个区块(达洪飞，张正文，2015)。除了在实际案例中众所周知的优势之外，这一特点也带来了一些额外的限制、漏洞和挑战。

[1]参见社区黄皮书

本技术资料的目的是强调从经典实用的拜占庭容错机制(pBFT)到目前NEO区块链核心库采用的委托拜占庭容错机制(dBFT)所做的关键修改(参见Github上的NEO项目)。此外，本文还描述了一种新的数学模型，该模型可以通过离散模型来验证特定的共识行为，离散模型可以对实际情况下的共识行为进行建模。在强调当前近地天体共识机制积极方面的同时，本文也旨在指出可能存在的缺陷以及未来的研究和发展方向。后者可以通过将NEO的需求及其新颖的理念与文献中的一些著名研究相结合来实现。

本文件的其余部分组织如下。第1.1节简要介绍了经典PBFT机制的背景。第1.2节描述了对文献进行的一些关键修改，以实现NEO dBFT机制。1.3节详细介绍了NEO dBFT机制的最新讨论，并提供了相关的伪代码和流程图。最后，1.9节提出了一种新的基于线性整数规划的数学规划模型，对最佳攻击者进行建模，并在最坏的情况下对网络进行测试，以验证其局限性。

1.1实用BFT的背景

Miguel Castro和Barbara Liskov(见图1)在他们的论文《实用拜占庭容错》(Castro和Liskov 1999)中首次提出了实用BFT的概念。

图1:2010年图灵奖得主芭芭拉利斯科夫。维基百科CC BY-SA 3.0

给n=3f 1一个状态机的副本。状态机由一个主节点和一个备份节点组成。给出的算法可以保证网络的活泼性和安全性，假设拜占庭[1]存在故障或者节点数不超过f

[1]拜占庭指任意行为，由Leslie Lamport等人在他们的论文《拜占庭将军的问题》中提出。

？安全性可以保证所有进程都以原子操作的方式进行，即在所有节点上执行或者整体回滚。由于流程的确定性(已在所有节点上执行)，这种可能性是存在的。一般来说，近地天体网络和区块链协议也存在这种可能性。

？活度保证网络不会停止(除非拜占庭节点数超过F)。通过使用一种称为“改变视图”的机制，允许在可能出现拜占庭时将备份节点切换到主节点。 通过使用超时机制和增加每个视图中的延迟时间，PBFT机制可以防止恶意网络延迟的攻击，恶意网络延迟不能无限运行。在当前公式中，假设当前视图号为N，将生成块的周期时间T向左移动N位得到的结果就是超时发生的时间，例如：

生成块的周期为15秒：15 ^ 1为30s(视图号为1)；5 12是60s13是120s14是240。

生成块的周期为1秒：1 1为2s；1是4s；1是8s；1是16s。

基于PBFT机制的网络假设“可能无法传递消息、延迟消息、复制消息或无序传递消息”。同时使用公钥加密对副本进行认证，对于NEO的dBFT算法也是如此。由于算法不依靠同步来保证其安全性，所以必须依靠同步来保证其生动性。对于拜占庭协议(布拉查和图伊格1985)，3f 1节点的设置具有最好的灵活性，其中恶意节点数不超过f .

PBFT正确性的保证主要分为前期准备、准备和确认三个阶段。

？在预准备阶段，主节点会发送一个序列号K，同时发送消息M和签名摘要d，如果签名正确，K为有蓑衣网小编2022效区间，备份节点I没有收到相同K值和相同视图下的预准备信息，那么我将进入预准备阶段。

？进入预准备阶段后，备份节点会在全网广播一条准备消息(包括对主节点的广播)，对于同一个视图，当匹配本地准备阶段的节点收到的准备消息数量不少于2f时，表明该节点已经处于准备阶段。因此，对于给定的视图，非故障复制节点已就请求的整体顺序达成一致。一旦2f 1非故障节点准备就绪，网络就可以进入确认阶段。

？每个确认阶段中的复制节点广播确认消息，并且一旦节点I接收到2f 1确认消息，它指示该节点处于本地提交-本地阶段。最终，即使视图被改变，具有本地确认节点的系统也将完成确认。

PBFT机制认为客户端直接与主节点交互并广播消息，同时接收来自2f 1节点的独立响应，以便前进(执行下一步操作)。近地天体区块链也有类似的情况，信息通过对等网络传播，但在近地天体区块链网络中，共识节点的位置是未知的(以防止直接延迟攻击和拒绝服务)。在PBFT中，客户端在不同的时间戳上提交原子的和独立的操作，这些操作被独立地处理和发布。然而，新区块链是不同的。共识节点必须将事务分组为批，每个组称为一个块。由于不同的分组方法(即不同的事务组合)，在相同的块高度上可能有成千上万个有效块。因此，为了确保区块的最终确定性(即对于给定的区块高度，只有一个区块)，我们必须考虑“客户”(区块提议者)也失败的情况，而PBFT没有考虑到这一点。

[1]这一点在《单失效节点的分布式系统无法达成共识》一文中已经得到了证明。

[1]NEOdBFT 2.0也包含三个阶段，命名略有变化：准备请求、准备响应和确认[1]一种可以避免因失败而耗尽序列号空间的特殊技术

1.2 NEODdBFT临界修改

在前面的小节中，我们强调了PBFT和dBFT的一些区别：[x终端用户和种子节点区块的最终确定性；

？在进程的不同阶段使用加密签名，以避免暴露当前块的节点确认；

？能够基于块头的信息共享生成块(通过独立的同步机制共享和存储事务)；蓑衣网小编2022

？通过在确认阶段之后禁止视图改变来避免重复暴露块签名；

？无论是在本地硬件还是在网络的P2P共识层，再生机制都可以恢复失效的节点。

1.3 dBFT详细描述

DBFT共识机制本质上是一个状态机，其状态转换依赖于循环模式(定义主节点/备份节点)以及网络消息。

1.3.1 dBFT状态

dBFT有以下几种状态：

？Initial:状态机

的初始状态？Primary:取决于块高和视图数

？Backup:如果不是主节点则为true，否则为false

？RequestSent:如果已经发送了块头请求，则为真，否则为假(在dBFT2.0中已删除，因为代码会跟踪所有准备好的签名，并将其合并到RequestSendorReceived)

？RequestReceived:如果收到了块头请求，则为真，否则为假(在dBFT2.0中已删除，因为代码会跟踪所有准备好的签名，并将其合并到RequestSentOrReceived)

？签名：如果签名已发送，则为真，否则为假(在dBFT 2.0中已删除，因为新的确认阶段将携带签名)

？RequestSentOrReceived:如果收到主节点的有效签名，则为true，否则为false(在dBFT2.0中引入)。

？响应：如果已经发送了块头确认，则为真(dBFT2.0:内部状态中引入，仅用于发块节点触发consensus OnTransaction事件)

？CommitSent:如果已经发送了块签名，则为true(该状态仅在dBFT2.0中引入，并取代了签名)

？BlockSent:如果块已经发送，则为true，否则为false

？ViewChanging:如果触发了视图改变机制，则为true，否则为false

？IsIecovery:如果接收到有效的恢复消息并正在处理，则为true(在dBFT2.0蓑衣网小编2022:内部状态中引入)

dBFT的第一个版本将这些状态显式地视为标志(ConsensusState的枚举值)。但是，dBFT 2.0可以隐式地处理这些信息，因为它跟踪签名的准备和状态恢复机制。

1.4流程图

图2显示了在每个共识节点上复制的状态机(术语copy/node/consensus node在本小节中可视为同义词)。对于区块链上给定的块高度h，状态机副本的执行过程从初始状态开始。t设置为标准闭塞时间(15秒)；v是当前视图号(从v=0开始)；Exp(j)被设置为2j；I是共识指数；r是共有节点的总数。这个状态机可以表示为一个时间自动机(Alur和Dill 1994)，其中C表示时间变量，操作(C条件)？表示时间转换(C:=0为复位时间)。虚线表示明确依赖于超时行为的状态转换，为了清楚起见，它们以不同的格式表示。同时，假设状态转换是按照每个状态出现的顺序进行的。例：

(C=5)？

A

(C=7)？

B

当时间C超过5s时，阻塞状态会切换到状态A，当时间C超过7s时，阻塞状态会切换到B，这个状态机可以更准确的描述dBFT 2.0的实现原理。

图2:给定块高的dBFT 2.0状态机

图2中，共识节点从初始状态开始，视图号的初始值为v=0。给定H和V，每轮共识会用下面的公式来检验当前节点I是否为主节点：(H v)modR=i(否则设置为复制节点)。如果当前节点是主节点，它将在t秒钟后进入SendPrepareRequest状态(选择一个事务并创建一个新的建议块),然后再次转换到RequestSentOrReceived状态。如果节点是复制节点，您需要等待OnPrepareRequest状态。时钟到期后，节点可以进入换景状态，这样可以保证主节点失效时网络的活动。但是，因为该节点已经确认了一个特定的块(因此它不会为该高度的任何其他块提供签名)，所以CommitSet状态可以保证视图不会发生变化。由于这会影响网络的活动，状态机提出了一个恢复过程(见图3)。EnoughPreparations、EnoughCommits和EnoughViewChanges取决于是否有足够的超过拜占庭级别M的有效响应(即不超过失败节点的最大数量F)。在2.0版之后，T表示节点收到的最后一个块的时间，而不是签署前一个块头时的时间戳。

1.5块确定性

共有水平中的块确定性由等式(1)中的条件确定，其定义了对于给定的块高度？和任何封闭周期t，将不会有两个不同的块。

简而言之，块确定性使客户不必验证状态机复制(SMR)的大多数节点一致性。在这个意义上，种子节点可以直接附加所有具有协议定义的真实签名的块(即M=2f 1)。如目前的NEO dBFT算法所描述的，所需的最小签名数是拜占庭一般问题(Lamport，Shostak和Pease 1982)中定义的2f 1，其f=1/3N是网络协议允许的最大拜占庭节点数。

1.6多块签名曝光

1.6.1 dBFT v1.0版本检测失败

2017年，近地天体区块链网络实际运行中出现了块哈希阻塞分叉。具体来说，这种现象是由主节点选择的块的以下两个属性引起的：

？不同的交易集；

？块随机数。

特别是在没有确认阶段的时候，NEODBFT版简单实现了pBFT算法。

但是，在极少数情况下，一个给定的节点可以接收到持久存储一个块所需的M个签名，然后突然与其他节点断开连接。此时，其他节点可以检测到缺少通信(以及它们之间的其他故障),并生成新的块。除了破坏块的确定性之外，这个问题可能终止共识节点和任何其他客户端的操作，这将持续大多数共识节点(CN)不同意的块。此外，在更罕见的情况下，当其他节点具有不同的块散列时，X个节点可以接收给定的块，其中$f 1类型的攻击。

就这点而言，自然而然会出现以下这种可能性：

?发送区块头的签名后锁定视图更换（NEOdBFT 2.0后实现了该功能）。这意味着那些被该区块所确认的节点不会对其他提议的区块进行签名。

另一方面，由于节点需要遵守相应的协议，再生策略似乎是必需的。我们将此定义为不知疲倦的矿工问题，定义如下：

该议长是一名地质工程师，正在寻找一个可以挖掘氪石的地方;

他提议了一个地理位置（待挖掘的地理坐标）;

团队（M）的大多数成员对该坐标达成了共识（带有他们的签名）并签署了合约同意开始挖掘;

挖掘的时间：他们会不停地挖掘，直到他们找到氪石（在发现氪石前不会去任何其他地方进行挖掘）。氪石是一种无限可分的晶体，因此，一旦有人挖掘到氪石，他就可共享以便所有人都能拥有一块氪石从而履行完他们的合约（3）;

如果有人死亡了，当有其他人加入时，他将看到先前签署的协议，并自动开始挖掘（再生策略）。其他小部分人也会遇到相同的问题，可以通过隐藏的信息来告知他们也应该进行挖掘。

该策略在最大故障节点数为f的限制下保证了dBFT算法的强度。此外，生存/再生策略也增强了系统的鲁棒性。

1.7再生

恢复/再生机制用于对给定的丢失部分历史数据的故障节点进行响应。此外，它还在本地进行了数据备份，从而可以在发生硬件故障时恢复节点。这种本地级别的安全性（可以看作是硬件故障安全性）是至关重要的，可减少有意设计的恶意攻击所带来的影响。

从这个意义上讲，如果节点发生故障后又恢复运行，它会自动将change_view设置为0，这意味着该节点已经恢复并希望通过其他节点恢复历史数据。因此，它可能接收一个有效负载，使其能够验证大多数节点的共识并返回开始实际操作，帮助它们对当前正在处理的区块进行签名。

根据这些要求，dBFT 2.0列举了一系列不同的情况，其中节点可以恢复其先前的状态，二者都是网络或自身已知的。因此，目前恢复场景包括：

?重播ChangeView消息;

?重播主节点的prepareRequest信息;

?重播PrepareResponse消息;

?重播Commit消息。

代码可以恢复以下情况：

?将节点恢复到更高级别的视图;

?将节点恢复到已发送准备请求，但还未收集到足够多的进入确认阶段所需的准备信息的视图;

?将节点恢复到已发送准备请求，同时已收集到足够多的准备信息从而可以进入确认阶段的视图，接下来可转换到CommitSent状态;

?将确认签名共享到已确认的节点（激活CommitSent标志）。

图3总结了由恢复机制引导的一些当前状态，这些状态目前由接收到视图更换请求的节点发送。恢复负载由接收到ChangeView请求的节点发送，且节点数不超过f。当前根据负载发送方和本地当前视图的编号进行选择。值得注意的是，OnStart事件会在编号为0的视图处触ChangeView事件，以便与其他节点进行通信，告知其初始活动及其可接收任何恢复负载的状态。这么做的原因是，可以让启动较晚的节点发现网络已经处于某些高级状态。

不同于reResponse状态，这里的内部状态IsRecovering是为了简化Recover消息可能带来的影响。从这个意义上说，在不失一般性的情况下，指向它的箭头可以直接与它指出的箭头相连。

图 3: 带有恢复机制的dBFT 2.0状态机

1.8可能的故障

1.8.1单纯的网络故障

可能场景：

?多达f个节点延迟消息;

?至多有f个节点会由于硬件故障或者软件问题而崩溃

1.8.2混合型恶意拜占庭故障

首先，拜占庭式攻击的设计应确保节点永远无法证明这是一次攻击。否则，NEO持有者将重新审视此类行为，并投票支持其他节点。此外，加入给定协作网络的节点拥有身份或权益。如果有人能够检测到这种恶意行为，那么，该节点将“自动”（通过当前的投票系统或可设计的自动机制）从网络中删除。

?至多有f个节点会延迟消息;

?至多有f个节点会发送不正确的信息（由于可以揭示恶意行为，所以这种情况不太可能发生）;

?至多有f个节点会尝试为策略场景保留正确的信息。

1.9针对BFT区块链协议的故障和攻击的MILP模型

我们提出了一个针对BFT区块链协议的故障和攻击的MILP模型，该模型针对dBFT的具体情况进行了设计，也适用于其他那些不太特殊的情况。

由于dBFT最近刚更新到2.0版本，所以当前的模型还没有完全完成。完成后，它将包括一些使用数学编程语言（AMPL）建模的基准测试结果，目前正在开发中，可参见:https://github.com/NeoResearch/milp_bft_failures_attacks。

1.9.1数学模型

参数：

变量：

目标函数：

攻击者可以控制f个副本，但其他M个副本必须遵循dBFT算法。攻击者可以为任意消息选择任意延迟时间（最大模拟时间为|T|）。如果它想要关闭整个网络，就不能再产生任何区块，并且目标函数值将为零（可能的最小值）。因此，攻击者将尝试以巧妙的方式来操纵延迟时间从而最大化所生成的区块数。如等式（2）所示，目标函数的值域为[0，|B|]。

限制：

1.9.2 示例

1.10 致谢dBFT 2.0背后的关键思想和开发主要由张铮文指导，而在Github上的开放式讨论中，也有很多来自社区成员的宝贵贡献，感谢大家花费宝贵的时间对BFT理念进行讨论并提出改进建议。我们也感谢为解决这些挑战性问题而不断尝试，并最终对算法进行实现的开发人员。为此，真诚地感谢那些为实现算法而做出贡献的人: jsolman、shargon、longfei、tog、edge等人。