ICC WhitePaper 中文版
ICC白皮书中文版
摘要
- 互联网计算机共识（ICC）是互联网计算机的基石，它巩固了互联网计算机的拜占庭容错复制状态机。
- ICC采用leader选举机制，并假设网络是部分同步的。任何一轮leader舞弊（概率小于1/3），ICC就会将leader权交给其他参与方。
- ICC没有复杂的子协议（如PBFT中的“view change”）或未详细说明的子协议（如HotStuff中的“pacemaker”），将区块可靠的分发给各方是该协议不可或缺的一部分。
- ICC协议具有积极响应的特性：当leader是诚实的，协议将会以实际网络延迟进行，而不是网络延迟的上界。
- ICC分为三种存在细微差别的协议：ICC0是目前互联网计算机实际使用的简化版本，更易于呈现和分析；ICC1被设计为与点对点gossip子层集成，从而减少了传播大块的瓶颈；ICC2使用低通信(low-communication)可靠广播子协议代替gossip子层来解决同样的问题。
1.介绍
- 拜占庭容错机制（BFT）是指计算系统能够容忍某些组件故障但整个系统仍然能够正常工作的能力。
- 实现BFT的一种方式是通过状态机复制：将系统逻辑复制到大量机器上，并通过执行一系列的命令来维护或更新状态。为了确保没有故障的机器最终处于相同状态，他们都必须确定性地执行相同的命令序列。这通过使用原子广播（atomic broadcast）来实现。
- 在原子广播协议中，各参与方会随着时间接收各种命令，并输出一个有序的命令序列。
- 安全性是共识协议的关键属性。这意味着对于一组相同顺序的输入操作，每个参与方都输出相同顺序的命令。（如果某个参与方输出命令序列s，另一个参与方在这之后输出序列s’，那么s必须是s’的前置序列）
- 活跃度（liveness）是另一个关键属性。有几种不同的活跃度概念，一种是要求每个诚实方的输出队列以“合理的速度”（相对于网络速度）增长，这个概念相对薄弱，因为它不排除某些方可能无限期地忽略其输入命令。另一种更健壮的概念是，如果“足够多”的参与方在某个时间点收到特定命令作为输入，“不久之后”该命令将会出现在所有诚实方的输出队列中。
**ICC系列协议。**本文提出了一系列原子广播协议，它们对应于互联网计算机中使用的原子广播协议。大致上来讲，互联网计算机是相互通信的复制状态机的动态集合：在一个复制状态机进行原子广播的命令要么来自其他复制状态机，要么来自外部客户端。
实际上有三种微小变化的协议：ICC0,ICC1,ICC2。ICC0是互联网计算机实际使用协议的简化版本，更容易分析和呈现，也是本文的主要重点。ICC1与互联网计算机中使用的协议版本最为接近，仅比ICC0稍微复杂一点。ICC2比ICC1略胜一筹，它使用了互联网计算机目前没有使用的技术。ICC协议是详细说明的(不依赖于不明确的、非标准的组件)、非常简单和健壮的(在面对拜占庭式攻击时性能会优雅地下降)。
在设计和分析任何原子广播协议时，关于舞弊方的性质和数量以及网络可靠性的某些假设是至关重要的。本文中假设至多有n/3方参与舞弊，它们可能行为随意并受对手操控，并假设在协议执行的一开始就确定对手选择贿赂哪些参与方。
关于网络，通常会有如下不同的假设：
- 一种极端是假设网络是同步的，这意味着所有的消息都会在一个已知的时间范围∆bnd内从一个诚实方发送至另一个诚实方。
- 另一种极端是假设网络是异步的，这意味着消息可以被任意的拖延
在这两种极端之间可以做出各种的部分同步假设。对于这里的分析，我们需要的部分同步假设类型是网络在相对较短的时间间隔内是同步的。无论网络是异步或者部分同步的，我们都会假设从一个诚实参与方发送至另一个诚实参与方的每条消息最终都会交付。
和许多原子广播协议一样，每个ICC协议都是基于区块链的。随着协议的进展，从作为树根的特殊“创世块”开始生成一颗块树。树中每一个非创世块都包含一个有效负载（payload），由一系列命令和父区块的哈希组成。诚实参与方对这棵树有一致的看法：虽然每一个参与方可能看到这棵树的不同部分，但所有的参与方看到的都是同一颗树。除此之外，这棵树上总有一条提交块的路径。同样的，诚实参与方对这条路径有一致的看法：虽然每一个参与方只能看到局部或不同的部分，但是所有的参与方看的是同一条路径。沿着这条路径的块中有效负载包含的命令是各方要输出的命令。
协议按照轮次进行。协议的第k轮，一个或多个k深度的块会被加到树上。也就是说，在第k轮加进来的块到根的距离总是k。在每一轮，随机信标（random beacon）产生n个参与方的排名，排名最低的（rank0）是这一轮的领导者(leader)。如果这个leader是诚实的并且网络是同步的，那么leader会产生一个块并添加到树上。如果leader不诚实或者网络异步，那么其他高排名的参与方可能同样会产生块并添加到树上。总之，协议的逻辑是赋予leader提出的块最高优先权。
分析表明：
- 在这种部分同步假设下，每个ICC协议都提供了活跃度（liveness）。粗略地讲，只要网络保持同步一小段时间，无论各方当时处于哪一轮，只要leader是诚实的，该轮次就只有leader的区块会被添加到区块树上。所有从根到这个块的路径上的块都会被提交。
- ICC的每个协议都提供了安全性，即使是在异步环境中。
在ICC协议的最基础版本中，部分同步假设中的通信时延界限（∆bnd）是协议规范中的显式参数。与许多此类协议一样，ICC协议易于修改，以便自适应调整到未知的通信时延界限。
我们还分析了每个ICC协议的消息复杂度（message complexity）。消息复杂度定义为在任何一轮中所有诚实方发送的消息总数—因此广播消息的一方对消息复杂度贡献了n。在最坏的情况下，消息复杂度是O(n3)。但在同步网络的任何一轮中，消息复杂度预期是O(n2)—实际上，它最有可能是O(n2)，这一概率是根据该轮的随机信标（random beacon）获取的。
当然，消息复杂度本身并不能说明通信复杂度的全部情况：消息的大小和通信模式也很重要。在ICC0和ICC1协议中，任一轮在最坏的情况下每个诚实参与方广播O(n)条消息，其中每条消息可能是一个签名、一个签名份额（signature share，用于阈值或者多重签名方案）或者一个块。签名或者签名份额通常非常小（几十字节），而块可能会很大（一个块的有效负载通常几MB）。如果网络在这一轮是同步的，每个诚实的参与方最有可能广播O(1)条这样的消息(无论大小)。此外，所有诚实方广播不同块的总数通常是O(1) --也就是说，诚实参与方通常都广播相同的块(或少数不同块中的一个)。此属性与互联网计算机对这些广播的实现很好地交互，这是使用点对点的gossip子层完成的，ICC1协议被明确设计为与p2p 的gossip子层协作。
协议ICC2与ICC1的结构非常相似，但它使用基于纠删码（erasure codes）的子协议来有效分发大块，而不是基于p2p的gossip子层。假设块大小为S，S = Ω(n log n λ)，其中签名（和哈希）的长度为O(λ)，在ICC2的每轮中每个参与方传输的比特总数最有可能是O(S)（假设网络在本轮是同步的）。
本文还分析了ICC协议的相互吞吐量（reciprocal throughput）和延迟（latency）。当leader是诚实的，且网络延迟在δ ≤ ∆bnd范围内的系统稳定状态下，协议ICC0和ICC1每2δ个时间完成一轮。也就是说，相互吞吐量为2δ。这些协议的延迟，即从一个leader提出一个块到所有参与方提交（commit）这个块所经过的时间为3δ。而对于协议ICC2，交互吞吐量是3δ，延迟是4δ。在部分同步假设下，界限δ可能比网络延迟界限∆bnd小很多。尤其，ICC协议具有积极响应（optimistic responsiveness）的特性，这意味着协议将在leader诚实的那些回合以网络允许的速度运行。对于任意轮次，当leader不诚实或δ > ∆bnd，该轮大概率会在O(∆bnd +δ)时间内完成。
1.1相关工作
原子广播问题是所谓共识问题的特例。面临任意失败达成共识被称为拜占庭将军问题。[PSL80]中给出了同步通信模型中的第一个解决方案。
在异步通信模型下，没有特定协议可以解决共识问题。尽管如此，这个问题可以用概率性协议（probabilistic protocols）处理。第一个这样的协议由[Ben83]提出，它表明在异步环境中，恢复界限（resilience bound）设为t<n/3是最优的。使用密码学可以实现更有效的协议，如[CKS05, CKP01]。
尽管最近在异步环境中取得了进展，但在部分同步环境下可以使用更高效的共识协议。部分同步环境下的目标是在不做任何同步假设的情况下保证安全性，并且仅依赖于网络同步的时间段来保证活跃度。在此环境中，第一个真正实用的协议是众所周知的PBFT协议，它是用于原子广播和状态机复制的协议。
PBFT按照轮次进行处理。在每一轮中，指定leader通过向各方广播命令来提出一批命令，然后通过两个多对多通信（all-to-all communication）步骤来实际提交批处理。一般情况下，leader将连续多轮担任该角色，但是如果有足够多的参与方认为协议没有取得进展，他们将触发一个视图更改（view-change）操作，这将会安排一位新leader，并清理旧leader留下的烂摊子。
尽管PBFT对该领域产生了深远的影响，但仍有改进的空间。
- 视图更改子协议是一个相对复杂和昂贵的过程。
- Leader负责将批量命令分发给所有参与方，这就产生了两个问题：
- 首先，如果批量命令数量非常大，从通信复杂度角度看，leader会成为瓶颈。
- 其次，舞弊leader可以不向所有参与方发送批次。实际上，一个舞弊的leader（在其他舞弊方的帮助下）可以轻易的将协议推进任意轮次，使一部分诚实方落后，失去与那些轮次相对应的批量命令。这些落后方如何赶上的细节并未详细说明，只是说可以从另一方那里获得丢失的批量命令。这当然是正确的，但这个想法很难实现，攻击者可以通过让舞弊方向诚实方请求缺失的批量命令，从而轻易地增加通信复杂度—如此的话，不仅仅只有leader广播批次，最终可能O(n)个诚实方在每一轮都会向O(n)个舞弊方发送一批命令。
- 每轮最后两步的多对多通信模式也可能导致较高的通信复杂度。但是当命令数量远大于n时——批次的传播仍然是通信复杂度的主导因素。
通信复杂度一般定义为所有诚实方传输的比特总数。像PBFT这样基于轮次的协议，通信复杂度通常是按照轮次来计算的。
通过消除多对多通信步骤来减少PBFT的通信复杂度方面已经做了很多工作，但在Mir-BFT（区块链的高通量BFT）中这么做是不合适的：在提高吞吐量和延迟方面重要的不是通信复杂度，而是通信瓶颈。也就是说，相关的度量不是各方传输的bit总数，而是任意方传输bit的最大数。当然，这种经验性的研究结果受实际网络影响较大。正如Mir-BFT文章中提到的，是大批量的传播导致了leader的通信瓶颈，而不是只涉及了比较小对象的多对多通信步骤。
最近也有关于消除PBFT的复杂视图更改子协议的讨论，如HotStuff [AMN+20]和Tendermint [BKM18]等。和PBFT一样这两个协议都是基于leader机制的，但他们不依赖复杂和昂贵的视图更改子协议，而是每回合轮换一名新的leader。此外，这两个都是基于区块链的协议（虽然PBFT可以用在区块链中，但并不是必须的）。
HotStuff取消了PBFT的多对多通信步骤。HotStuff提高了PBFT的吞吐量，将交互吞吐量从3δ降到2δ（δ为网络延迟）。类似PBFT，HotStuff是积极响应的（当leader是诚实时，会以网络允许最大速度运行），但是HotStuff的延迟（leader出块到提交块的时间）从3δ上升到了6δ。与PBFT一样，HotStuff依赖leader来传播块，但对于PBFT来说，这可能成为通信瓶颈，并且没有明确的机制保证leader舞弊时块可以可靠的传播。此外，虽然HotStuff没有依靠“视图更改（view change）”子协议，他仍然依靠“起搏器（pacemaker）”子协议。尽管起搏器子协议任务没有视图更改子协议那么繁重，但它仍然不容忽视。LibraBFT (也叫DiemBFT)实现了起搏器子协议，但重新引入了HotStuff想要消除的多对多通信模式。最近，起搏器协议被提出可以具有更好的通信复杂度[NBMS19, NK20, BCG20]。注意，这些提议都没有解决如何可靠并有效地传播块或批量命令，只处理了从一轮移动到下一轮时各方的同步。
Tendermint依赖点对点gossip子层（p2p gossip sub-layer）来通信。不同于PBFT和HotStuff这样的协议，Tendermint的一个优势是协议中包含了如何可靠地传播由leader提议的块。此外，一个设计良好的gossip子层可以明显减少leader的通信瓶颈—当然，这是以增加相互吞吐量和延迟为代价的，因为通过gossip子层传播消息需要在底层物理网络进行几次跳转。不同于HotStuff，Tendermint不依赖任何不明确的组件（如HotStuff中的起搏器）。Tendermint的一个劣势是，与PBFT和HotStuff不同，它不是积极响应的。这可能是个问题，因为为了保证活跃度，一般需要选择一个网络延迟上限∆bnd，这个上限可能明显大于实际网络延迟δ，而在Tendermint中，即便leader是诚实的，每一轮都需要时间O(∆bnd)。
Mir-BFT是PBFT的一种有趣变体，其中同时运行多个PBFT实例。这么做是为了缓解普通PBFT中在leader处观察到的瓶颈。因为MirPBFT依赖PBFT，它也使用了同样复杂和昂贵的视图更改子协议—但是，正如MirPBFT中指出的，除了PBFT之外的其他协议也可以在其框架中使用。让多方同时提出批处理存在新的挑战，其中之一是防止命令重复，这可能会抵消吞吐量的任何改进。Mir-BFT中给出了此问题的解决方案。
Algorand是一个有多种目标的基于pos共识的系统，但其核心是原子广播协议。类似Tendermint，它基于gossip子层，将块的传播构建到协议中，并且不是积极响应的。不同于之前提到的所有协议，它依赖于一个(非常弱的)同步假设来保证安全性。与ICC协议一样，Algorand也使用类似于随机信标的东西来对各参与方排名，但如何使用这些排名的基本逻辑是完全不同的。
现在将重点介绍ICC系列协议的主要特性，以及它们与上面讨论的一些协议之间的关系。
- ICC协议非常简单，且完全独立。没有复杂的子协议(如PBFT中的视图更改)，也没有不明确的子协议(如HotStuff中的起搏器，PBFT和HotStuff中可靠的批量命令或块传播)。
- 正如刚才提到的，ICC协议明确地处理块传播问题。和Tendermint和Algorand一样，ICC1集成了一个点对点的gossip子层。这种gossip子层可以降低leader的通信瓶颈。
ICC2依靠一个子协议替代gossip子层来进行可靠广播，该子协议使用纠删码来降低整体通信复杂度和leader的通信瓶颈。这种可靠的广播协议在《分布式计算》中引入，之前在《2016年ACM SIGSAC计算机与通信安全会议论文集》的原子广播中使用过。我们提出了一种新的基于纠删码的可靠广播子协议，它具有比《分布式计算》中更低的延迟，并且在与ICC2的集成中开发了更强的特性。
- 类似PBFT和HotStuff而与Tendermint和Algorand不同的是，所有ICC的协议都是积极响应的。ICC0和ICC1实现了2δ交互吞吐量和3δ延迟（当leader诚实且网络同步）。ICC2分别增长到了3δ和4δ。
- 类似PBFT而与HotStuff不同的是，ICC协议利用签名和签名份额来实现多对多传输。ICC协议适用于区块非常大的环境，因此多对多传播的通信复杂度通常不是瓶颈。相反，通信瓶颈是块本身的传播，ICC1使用gossip子层来缓解，协议ICC2使用纠删码可靠广播子协议来缓解。
- 不同于上述讨论的所有协议，ICC协议每轮至少有一个块会被添加到区块树上，并且其中一个最终会成为区块链的一部分。这确保了整体吞吐量保持稳定，即使在异步期间或者leader舞弊的轮次。也就是说，在leader舞弊的轮次中，leader提出的区块可能不如诚实leader提议的区块有用。例如在极端情况下，舞弊leader可以一直提议空区块，但如果一个leader在这方面一直表现不佳，互联网计算机提供了重新配置参与者集合的机制，通过该机制可以删除这样的leader。
**健壮的共识。**注意到，ICC协议的设计还确保了当实际发生拜占庭错误时，性能会优雅的下降。就像[CWA+09]中提出的，最近很多关于共识的工作都着重于在“乐观情况下（即没有失败）”改进性能，由此产生的协议是危险脆弱的，在发生故障时实际上可能不可用。例如，[CWA+09]表明，在某些类型(相当简单)拜占庭行为下，PBFT实现的吞吐量降至零。该论文提倡健壮的共识，这会牺牲部分最优条件下的峰值性能，以确保当某些参与方舞弊(但仍然假设网络是同步的)时的合理性能。 ICC协议是健壮的：在任何leader舞弊的轮次(这本身发生的概率小于1/3)，每个ICC协议将有效地让另一方接任leader，及时地推进协议到下一轮。在这种情况下唯一的性能下降是，该轮次将极有可能在O(∆bnd)时间内完成，而不能够在O(δ)时间内完成（δ是实际的网络延迟；∆bnd是基于部分同步假设时的网络延迟上限；∆bnd>=δ）。
**ICC协议初版。**这里提到的协议与[HMW18]或[AMNR18]中大不相同，这两个（1）只保证了同步环境下的安全性（2）不是积极响应的（3）具有潜在、无限的通信复杂度。
1.2本文剩余部分大纲
第2节将回顾协议所需的密码原语（cryptographic primitives）。第3节中介绍ICC0协议。第四节对协议ICC0进行了详细的分析。第5节介绍了ICC0的几种变体。协议ICC1和ICC2两个主要变体将在第5.2和5.3节中详细讨论。
2.密码学原语
2.1抗碰撞散列函数（collision resistant hash function）
ICC协议使用散列函数H，它是抗碰撞的，两个不同的输入几乎不可能有相同的散列值，即不可能出现input x≠x',but Hx=H(x')
2.2数字签名（digital signatures）
ICC协议使用了一种数字签名方案，该方案在标准意义上是安全的，不可能在自适应选择消息攻击中创造存在性伪造（existential forgery）。
2.3阈值签名（threshold signatures）
A(t,h,n)-阈值签名方案（threshold signature scheme）：n个参与方分别使用一对公/私钥、所有参与方的公钥和一个全局公钥进行初始化。该方案涉及到以下原语。
- 签名算法（signing algorithm）：给定一方的私钥和一条消息m，在m上产生该方的签名份额。
- 签名份额验证算法（signature share verification algorithm）：给定一方的公钥，一条消息m和签名份额ss，确定ss是否是给定公钥下消息m的有效签名。
正确生成的签名份额必须始终有效。
- 签名份额聚合算法（signature share combining algorithm）：将消息m上来自h个不同参与方的有效签名份额聚合成m的签名。
- 签名验证算法（signature verification algorithm）：给定一个全局公钥、一个签名σ和一条消息m，验证σ是不是m上的有效签名。
要求如果聚合算法聚合了来自h个不同方的有效签名份额，那么这个结果（极大概率）是m上的有效签名。
如果强劲的对手无法在下面的博弈中取胜，则可以认为这个方案是安全的。
- 首先对手选择t个舞弊方，剩余的n-t个参与方是诚实的。
- 然后挑战者（challenger）生成所有的密钥信息，给了对手所有的公钥，以及舞弊方的私钥。
- 对手进行一系列的签名查询。在每次查询中，对手指定一条消息和一名诚实方。挑战者在指定消息上回复属于该方的签名份额。
- 在博弈结束时，对手输出一条消息m和一个签名σ。
- 如果σ是m的有效签名，则对手赢了。但对手获得的签名份额来自少于h-t个诚实参与方。
这类的阈值签名可以通过以下几种方式来实现。
- 一种方法是简单地使用普通签名方案来生成签名份额，聚合算法只是输出一组签名份额。
- 第二种方法是使用多重签名，比如BLS多签，其中签名份额是一个普通的BLS签名，根据单个公钥的集合和h个签名者的描述符，这些签名份额可以组合成一个新的 BLS 签名。
- 第三种是使用普通签名方案（如BLS），但是在参与方之间共享密钥（通过Shamir私密共享[Sha79]）。
这些方法各有利弊：
- 与(iii)不同，(i)和(ii)方法的优点是不需要任何受信任的初始化（trusted setup）或分布式密钥生成协议。
- 与(iii)不同的是，方法(i)和(ii)中的签名标识了签名者(这可以是缺点，也可以是优点)。
- 类型 (iii) 的签名是唯一的（如果底层非阈值方案的签名是唯一的，这是 BLS 签名的情况）。 类型 (i) 和 (ii) 的签名不是唯一的。
- (iii) 中的签名通常（例如 BLS）比 (i) 或 (ii) 中的签名更简洁。
- 最后，当h > t+1时，方法(iii) 的安全性可能取决于某些更强但合理的安全性假设。
为了确保我们原子广播协议的安全性，我们同时使用了方法 (ii) 和 (iii)。
使用方法 ii（h = n – t） 进行验证：当一方希望验证指定消息时，它会在消息上广播签名份额。假设该方案是安全的，则消息上存在一个有效签名需要至少 n - 2t 个诚实方对消息进行认证。
使用方法 (iii) 来构建随机信标。为此，我们需要唯一签名（BLS提供）。随机信标是一系列值 R0, R1, R2 . . .值 R0是固定的初始值，各方都知道。对于 k = 1, 2, . . . ，值 Rk是 Rk-1 上的阈值签名。当一方拥有 Rk-1并想要生成 Rk时，它将在消息Rk-1上广播其签名份额。如果有 t + 1 个诚实方做同样的事情，他们每个人便都可以生成值 Rk。但是如果阈值签名方案是安全的，则必须至少有一个诚实方贡献了签名才能生成 Rk 值。实际上，Rk的哈希将与随机字符串无法区分（如果将哈希函数建模为“随机预言机(random oracle)”）。
3. ICC0协议
本节将详细介绍用于原子广播的ICC0协议。
3.1预备知识
在本文中，我们使用符号[k]表示集合{0,..., k−1}。
假设有n个参与方P1,...,Pn ，其中舞弊方最多有 t 个，对手（adversary）在协议开始执行时确定舞弊方（静态舞弊模型）， 并假设拜占庭将军问题中，舞弊方可能会行为随意并受对手操控。 但有时也会考虑较弱的舞弊形式，例如崩溃失败（crash failures），舞弊方失去响应。 我们还会考虑一种中间形式的舞弊称为一致性故障（consistent failures），它是某些协议特有的，通常意味着舞弊方存在不太明显的错误行为（参见第 4.7 节）。
协议中的唯一通信类型是广播，即其中一方向所有各方发送相同的消息（这适用于协议 ICC0 和 ICC1，但不适用于 ICC2）。 这个广播是不安全的：如果发送方舞弊，则无法保证诚实的各方会收到相同的消息或任何消息； 如果发送者是诚实的，那么所有诚实的各方最终都会收到消息。 我们通常假设消息传递的精确调度是由对手决定的。
每一方都有一个消息池，其中包含从所有各方（包括自己）接收到的所有消息。协议中描述到永远不会从消息池中删除任何消息。虽然协议需要优化来丢弃不再重要的消息，但不在这里讨论这些细节。此外和PBFT相似的是，复制状态机的实际实现通常会包含某种检查和垃圾回收机制，这里也不讨论这些细节。尽管互联网计算机的实现使用了“gossip网络”在各方之间传输消息，但除了上面已经提到的那些，我们不会对底层网络做任何假设。
每一方都将使用一些密钥以及所有方的公钥进行初始化。对于某些密码学原语，各方的密钥必须与另外一方相互关联，由受信任方或安全的分布式密钥生成协议设置。
用于数字签名的一些加密密钥可以用于验证消息，从而不需要其他消息认证机制。
3.2组件
协议使用：
- 抗碰撞散列函数H
- 签名方案Sauth，其中每个诚实方都有一个密钥，并配备所有方的公钥；
- (t, n − t, n)-阈值签名方案的实例 Snotary，其中每个诚实方都有一个密钥，并配备该实例的所有公钥信息；
- (t, n − t, n)-阈值签名方案的实例Sfinal，其中每个诚实方都有一个密钥，并配备该实例的所有公钥信息；
- (t, t + 1, n)-阈值签名方案的实例Sbeacon，其中每个诚实方都有一个密钥，并配备该实例的所有公钥信息； 这用于实现第 2 节所述的随机信标； 因此，该方案需要提供唯一的签名。
3.3协议的高级说明
该协议按轮次进行。 在每一轮中，每一方都可以提出一个块并添加到块树上。 这里的块树是有向根树 ， 除了根节点，树中的每个节点都是一个区块，区块由以下部分组成：
- 一个取整的数（也是树中块的深度），
- 出块方的索引，
- 块树中父区块的哈希值（使用抗碰撞散列函数 H），
- 块的有效负载。
根节点本身是一个特殊区块，表示根。
块有效负载中的内容依赖于具体应用程序。在原子广播中，就像第一节中提到的，有效负载由一条或多条输入到出块方的命令组成。此外，在构造块的有效负载时，一方总是在块树中拓展特定路径，并且可以分析该路径上已经存在的块中的有效载荷（以避免命令重复）。这是状态机复制的一个重要特性。
一方必须使用数字签名 Sauth来签署区块，才能提议一个区块。要将提议的块添加到块树，该块必须由 n - t 方使用阈值签名方案 Snotary进行公证，然后经过公证的区块可以由 n - t 方使用阈值签名方案 Sfinal最终确定。
协议中还使用了随机信标，通过使用阈值签名方案 Sbeacon实现，以便在每一轮中显示随机信标的下一个值。在给定轮次中随机信标的值决定了各方的排序 π，它分配了一个唯一的排名 0, …, n − 1 给每一方。在密码学假设下，每一轮中的排序 π 实际上是一个随机排序，与前几轮中使用的排序无关，也与舞弊方的选择无关（假设对手静态地舞弊各方）。
排名为0的参与方是该轮次的leader。虽然协议优先考虑由该轮的leader出块，但其他方也可以出块。如果本轮leader舞弊或暂时网络掉线，那么其他方提出的区块将被公证并可能最终确定。
在某些密码学假设和没有任何同步假设的情况中，这保证了每一轮中的 深度k ≥ 1：
下面介绍本协议的三个重要性质：
P1：至少一个深度为 k 的经过公证的块将被添加到块树中
P2：如果一个深度为 k 且经过公证的块被最终确定，则没有其他深度 为k的经过公证的区块
此外，
P3：如果在任何诚实方第一次进入第 k 轮时，网络存在短时间的同步，并且第 k 轮的领导者是诚实的，那么第 k 轮领导者提出的区块将被最终确定 。
性质 P1 确保协议不会死锁，因为树在每一轮中都会增长。
性质 P2 的使用如下： 假设某方看到一个最终确定的深度 为k的 块 B，并设 p 为块树中从根到 B 的路径。（相同或不同的）某方看到一个最终确定的深度为k'的块B'，其中k'≥k，并设p'为块树中从根到 B'的路径 。 那么性质P2 意味着路径 p 必须是路径 p' 的前置序列：如果不是，那么在深度 k 处将有两个不同的公证块，与性质 P2 相矛盾。
在原子广播中，上述论点表明，当一方看到最终确定的块 B 时，它可以安全地将从根到 B 的路径上的块的有效负载中的命令按该顺序追加到其输出队列中。
性质 P3 保证了部分同步假设下的一个重要概念——活跃度（liveness）。事实上，如果至少 n - t 方收到了第 k 轮输入的命令，那么至少 n - 2t > n/3 个诚实方将收到该命令作为输入，并且有超过1/3的概率 ，第 k 轮的领导者可以确保该命令在其提议的区块中。如果第 k 轮同步假设成立，则每个诚实方将在第 k 轮输出此命令（只要所有相关消息都已送达）^1
此外，由于性质 P1，即使网络在多个轮次中保持异步，只要它在很短的时间内变为同步，那么同步区间内所有轮次的有效负载中的命令将被所有诚实方输出。因此，即使网络只是间歇性同步，系统也会保持恒定的吞吐量。但就中间轮次的区块均由舞弊方提议的情况而言，这些轮次中的命令可能没有多大用处。
3.4区块
现在我们给出更多关于区块的细节。首先有一个特殊的轮次为0的根区块。
当k≥1，第k轮的区块B是这种形式的元组
block,k,α,phash,payload# AUTONUM
其中，α代表出块方Pα的索引，phash是散列函数H的输出，payload是特定应用程序的内容。
根据 Q消息池中的其他数据，我们将诚实方Q 的消息池中的区块分类为真实的（authentic）、有效的（valid）、经过公证的（notarized）和最终确定的（finalized）（对于 Q）。根节点始终存在于 Q 的消息池中，并且始终被认为是真实的、有效的、经过公证的和最终确定的（对于 Q）
设k≥1，并设B为Q的消息池中形如（1）的第k轮区块B。
- B是真实的（对于Q），如果 Q 的池中存在 B 的验证器（authenticator）
B的验证器为元组(authenticator,k,α,HB,σ)，其中σ是Pα方在(authenticator,k,α,H(B))上的有效Sauth签名
- B是有效的（对于Q），如果他是真实的（对于Q），并且phash=H(Bp)，其中Bp是Q消息池中经过公证的（对于Q）第k-1轮次的块。Bp被称作B的父区块并称B拓展了Bp
注意，根据 H 的抗碰撞特性，可以假设 B 的父区块是唯一的。
另外，可能需要满足具体应用程序的特性才能将 B 视为有效。
- B是经过公证的（对于Q），如果B 有效并且在 Q 的消息池中存在 B 的公证书。
B的公证书为元组(notarization,k,α,HB,σ)，其中σ是(notarization,k,α,H(B))上的有效Snotary签名。B的公证份额为元组(notarization-share,k,α,HB,ns,β)，其中ns是Pβ方在(notarization,k,α,H(B))上有效的Snotary签名份额。
- B是最终确定的（对于Q），如果它是有效的（对于 Q）并且在 Q 的消息池中存在 B 的最终确定。
B的最终确定为元组(finalization,k,α,HB,σ)，其中σ是(finalization,k,α,H(B))上的有效Sfinal签名。B的最终确定份额为元组(finalization-share,k,α,HB,fs,β)，其中fs是Pβ方在(finalization,k,α,H(B))上有效的Sfinal签名份额。
在下文中，根节点充当自己的验证器、公证书和最终确定。
注意，如果一方在其消息池中有一个有效的第 k 轮区块 B，那么就会有区块 root = B0, B1,..., Bk = B 形成的区块链，这意味着对于 i=0 , …,k-1，以及 B1,..., Bk的验证器和 B1,..., Bk-1 的公证书来说，Bi 是 Bi+1的父区块。
3.5协议细节
该协议由两个并行的子协议组成：树构建子协议和最终确定子协议。
Pα的树构建子协议如图 1 所示。树构建子协议使用两个延迟函数：
- ∆prop : [n] → R≥0：用于根据出块者的排名，推迟提议一个区块。 它应该是一个非递减函数。
- ∆ntry : [n] → R≥0：用于根据出块者的排名，推迟在块上生成公证份额。 它应该是一个非递减函数。
我们对协议的介绍和分析将根据这些延迟函数进行。对于活跃度，唯一的要求是2δ + ∆prop(0) ≤ ∆ntry（1），其中δ是这一轮中网络延迟的界限。但是，为了更好地控制协议的通信复杂度，推荐这些函数的实现如下:
Δpropr≔2Δbndr;
Δntryr≔2Δbndr+ϵ#2
由上述公式推导可知，网络延迟界限δ ≤ Δbnd 的那些轮次，上述活跃度要求将会被满足。 参数 ε 是一个“调节器(governor)”——它可以设置为零，但将其设置为非零值可以防止协议运行“过快”。
需要注意的是，协议执行的唯一通信类型是广播，即一方向所有各方发送相同的消息。 此外，这种广播是不安全的：当一方收到来自舞弊方的消息时，它不确定其他方能不能收到相同的消息。
在此协议描述中，一方等待其消息池包含满足某一条件的消息。 正如已经讨论过的，这个消息池包含从任何一方接收到的所有消息的集合（包括它自己广播的消息），并且永远不会从消息池中删除任何消息（尽管适当优化的协议版本会这样做）。
图 1：ICC0:树构建子协议
在树构建子协议的每一轮中，首先Pα方将开始等待 t+1 份用于计算该轮随机信标的阈值签名。 之后，它将计算第 k 轮的随机信标，并立即广播其在第 k + 1 轮的随机信标的份额。这是一种用于最大程度减少延迟的“流水线（pipelining）”逻辑——因此， 在任何诚实的一方完成第 k 轮之前，对手可能已经知道第 k + 1 轮的随机信标，但这不是问题（至少，假设静态舞弊）。
正如已经讨论过的，第 k 轮的随机信标确定了各方的排序π，它分配了一个唯一的排名 0,…, n − 1 给每一方。排名为 0 的一方是第 k 轮的leader。对于第 k 轮的区块 B，将 rankπ(B) 定义为提议B区块方的排名。
在第k轮中，Pα方将维护了一个已经广播公证书份额的区块集合N，以及一个取消排名资格的区块集合D。如果某一排名被取消资格，则意味着该排名的一方被发现在本轮提出两个不同的区块。
只要Pα方在其消息池中找到一个经过公证的第k轮区块B，或者找到一些有效但未经公证的第k轮区块B的n-t个公证书份额的全集，则该轮将结束。在后一种情况下，Pα方会将公证书份额合并为 B 的公证书。无论哪种情况，它都会广播B的公证书。 此外，如果 Pα 方本身没有广播除 B 之外任何区块的公证份额，它将广播 B 的一个最终确定份额。
当轮次开始（更准确地说，从它执行图 1 中的步骤 t0 ← clock() 时）已经过去了 ∆prop(rme)单位时间时，Pα 方将提出自己的区块。这种延迟对于安全性或活跃度不是必需的，而是为了防止所有诚实的各方用他们自己的提议对网络造成洪泛攻击。特别是，当leader是诚实的，会选择适当的延迟函数，并且网络同步时，除了leader没有任何一方会广播自己的区块。在提出自己的区块时，Pα 必须首先在其消息池中选择一个 Bp 中经过公证的第k − 1轮的区块来拓展。总会有这样的块，因为上一轮只有在有这样的块（或 k = 1 且 Bp = root）时才结束。也可能会有不止一个这样的公证块，在这种情况下，选择哪一个都没有关系。接下来，Pα 必须计算有效负载。在图 1 中，这是通过调用函数 getPayload(Bp) 完成的，函数细节取决于具体应用程序，但请注意，它可能取决于 Bp 和以 Bp 结尾的整个区块链（例如，为了避免命令重复）。最后，在构建了要提议的区块 B 之后，Pα方广播 B、B 的验证器以及 B 的父节点 Bp 的公证书。
最后，Pα方将在其消息池中回传（echo）一个有效的排名为r的第 k 轮区块 B，前提是 (i) 它尚未广播 B 的公证份额；(ii) 它没有取消排名 r 的资格；(iii)自该轮开始已经过去至少 ∆ntry(t)的单位时间，并且 (iv) 池中没有“更好”的区块。 这里，“更好”的区块是指一个有效的第 k 轮区块，其排名小于 r 但尚未被取消资格。 如果这些条件成立，Pα 方将执行以下操作：
- 它“回传（echo）”区块 B，这意味着它广播 B、B 的验证器和 B 的父节点的公证书；
- 此外，它会广播 B 的公证书份额，除非它已经广播了排名同为 r 的不同区块的公证书份额，在这种情况下，它会取消排名 r 的资格。
请注意，即使 Pα已经广播了相同排名的另一个区块的公证书份额，它也会回传B。 这是为了确保所有其他诚实方也有机会取消排名 r 的资格。 但是，注意Pα最多只回传任何给定排名中的 2 个块。
图 2:参与方Pα的最终确定子协议
Pα方的最终确定子协议如图 2 所示。Pα方追踪它看到的最终确定块的最新轮次kmax。每当它看到（i）其消息池中最终确定的第 k 轮区块 B；（ii）其消息池中某些有效但未最终确定的第 k 轮区块 B 的 n-t 个最终确定份额的全集，其中 k > kmax，它的处理如下。在情况 (ii) 中，它将最终确定份额合并为B上的最终确定，并且在情况 (i) 或 (ii) 中，它将会广播B的最终确定。此外，它将按顺序输出区块链中以B结尾的最新k−kmax轮次区块的有效负载。
我们正式的执行模型是，当执行“wait for”语句时，执行（如有必要）将会暂停，直到消息到达或出现使“wait for”中的条件之一被满足的情况。当这种情况发生时，将执行相应的子句（如果满足多个条件，则任意选择一个）。我们将假设该方消息池在执行此子句时未被修改。
4. 协议ICC0详解
4.1初步结果
引理1（终止）。在每一轮中，每个诚实方将执行主循环O(n)次。
*证明：*当主循环中“wait for”语句中的条件（a）被触发时，循环终止。 条件 (b) 最多执行一次。 条件（c）最多可以触发 2n 次， 每次触发时我们要么
- 将一个与N中已经存在的区块不同的块添加至排名N。最多可能发生 n 次
- 或者向集合D添加一个新排名，它也是发生最多n 次（假设最多有t 个舞弊方和安全签名，因为每个这样的排名都属于一个舞弊方，那么最多发生t次）。
引理 1 给出了每轮消息复杂度的最坏情况界限为O(n3)。 之后我们将在部分同步假设下，证明每轮预期消息复杂度界限为O(n2)。
**引理2（公证书数量的界限）**假设最多有 t < n/3 个舞弊方、签名安全且哈希函数抗碰撞。 在每一轮中，对于每一方，经过公证的参与方至多可以提出一个区块。 特别是，在任何一轮中，系统中最多出现 n 个经过公证的区块。
证明：在每一轮中，一个诚实方为任意给定排名的至多一个区块生成公证书份额。 由于公证书的阈值为 n − t 且 t < n/3，因此引理遵循标准Quorum交集参数。
**引理3（无处不在的区块链）**假设最多 t < n/3 个舞弊方、签名安全且哈希函数抗碰撞。 假设在某个时间点，诚实方 P 广播了第 k 轮的一个区块 B，其区块链为root = B0, B1,... , Bk = B. 那么有：
- 块B1,... , Bk，以及块B1,... , Bk的验证器和B1,... , Bk-1的公证书已经被诚实方广播。
- 特别地，当 (i) 中的所有区块、验证器和公证书都已交付给任意诚实方 Q 时，B 为Q 的有效区块。
证明：每当诚实方广播一个区块 B = Bk时，它也会广播Bk的验证器和 Bk-1 的公证书。 此外，由于该方具有 Bk-1 的公证书，因此某些诚实方必须已经广播了 Bk-1的相应公证份额，因此必定已经广播了区块 Bk-1。 (i) 根据归纳法； (ii) 根据定义法。
4.2主要结论
现在我们开始证明主要结论，对应于第3.3节中讨论的属性P1、P2和P3。下面的引理对应于属性P1。
**引理4（无死锁）**假设至多 t < n/3 个舞弊方、签名安全且哈希函数抗碰撞。 在每一轮中，如果诚实方在该轮之前广播的所有消息都已传递给所有诚实方，并且所有公证和提案延迟时间都已到期，那么所有诚实方将会结束本轮，生成一个经过公证的区块。
证明：假设定理是错误的。然后有一些有限的执行使系统处于这样一种状态，在某一轮中，诚实方在该轮中广播的所有消息都已传递给所有诚实方，并且所有延迟都已到期，但是某个诚实方没有用经过公证的区块结束本轮。下面讨论第一个这样的轮次。
我们知道每个诚实方实际上都进入了这一轮。而且，由于所有诚实方都完成了上一轮，他们都广播了本轮随机信标的份额，因此所有诚实方都收到了足够多的份额来重构本轮的随机信标。因此，所有诚实方不仅进入了这一轮，还进入了这一轮的主循环。
我们也知道，没有诚实方完成了本轮，生成经过公证的区块。否则如果某个诚实方完成了本轮，它会广播公证书，所有诚实的一方都会利用公证书结束这一轮。
我们根据排名来命名各方，Pr为排名为 r 的参与方。对于任意诚实方 Pr，如果 Pr消息池中恰好有 Ps为这一轮提议的一个有效区块，则称排名 s 对 P(r) 有利，否则称排名s 对 Pr 不利。如果有任何对Pr有利的排名，则定义s*(r)为其中最小的，否则定义 s*(r):= n。
声明1。令Pr为诚实方。对于每个 s < s*(r)，要么
• Pr消息池中没有 Ps为此轮提议的有效区块，或
• Pr消息池中拥有 Ps为这一轮提议的多个有效区块，Pr广播了两个这样的区块，并且 Pr取消了排名 s的资格。
证明：通过对 s 的归纳，从协议的逻辑中可以清晰地看出这一点。回想一下，假设 Pr还没有完成这一轮。对于每个 s <s*(r)，如果 Pr消息池中有多个由P(s)提议的有效块，那么（通过归纳）对于任何排名 t < s，Pr要么消息池中没有 Pt提出的区块，要么取消了排名 t 的资格，因此 Pr会广播Ps提出的两个区块，从而取消排名 s 的资格。
声明 2. 令 h 是排名最低的诚实方的名次。那么 s*(h)≤ h。
证明：想证明 s*(h)< h 或 s*(h)= h，或者等价地，s*(h)≥ h 意味着s*(h)= h。所以假设 s*(h)≥ h。然后根据协议的逻辑和声明 1 ，假设Ph 还没有完成这一轮，Ph可能已经提出并广播了自己的块，这意味着排名 h 对Ph 有利，即 s*(h)= h。
声明 3. 另 Pr为诚实方，并假设 s := s*(r)< n。那么Pr消息池中有一个由Ps提议的唯一有效区块，Pr广播该块以及一个相应的公证书份额。
证明：这是根据声明 1、协议的逻辑以及假设Pr尚未完成这一轮得出的。
声明 4. 对于任意两个诚实方 Pr和 Pr'，有s*(r)= s*(r')。
证明：另 s := s*(r)和 s' := s*(r')。假设，s < s'。根据声明 3，Pr在其池中具有由 Ps提议的唯一有效块 B，并且Pr广播了块 B。因此（根据引理 3），B 也是Pr'池中的一个有效块。由于 s < s'，可以发现排名 s 对 Pr'不利，因此，根据定义，Pr'消息池中必须有另一个由 Ps提议的有效块 B'。此外，根据声明1，Pr'将广播 Ps提出的两个有效块，并且（根据引理 3）这两个都将作为Pr池中的有效块出现。这与排名s 对 Pr有利的假设相矛盾。
令s*是所有诚实方Pr中 s*(r)的一个值，正如前面声明所保证的那样。根据声明2，s∗ ≤ h。
声明 5. 有一个排名为 s*的区块 B*，使得对于每个诚实方 P，B*在 P 的消息池中显示为有效块，并且 B*的至少 n-t 个公证份额也在 P 的消息池中。
证明：根据声明 3，每个诚实方 Pr在其池中都有一个排名为 s*的唯一有效区块B*(r)，并且广播了B*(r)以及相应的公证份额。此外（根据引理 3），每个 B*(r)在每个诚实方的消息池中都表现为一个有效块。因此，对于所有诚实方Pr和Pr'有B*(r)= B*(r')。设 B*为 B*(r) 中的一个值，那么每个诚实方至少收到了 n − t 个 B*的公证份额。
最后，根据声明 5，可以发现每个诚实方都将完成协议。存在矛盾。
以下引理对应于第 3.3 节中讨论的属性 P2。
引理 5（安全性）。假设最多 t < n/3 个舞弊方、签名安全且哈希函数抗碰撞。在每一轮中，如果某个区块被最终确定，则该轮中的其他区块不能被公证。
证明：假设 f ≤ t < n/3 方是舞弊的。如果一个区块 B 被最终确定，那么至少有 n − t − f 个诚实方为 B 发布了最终确定份额，这意味着这些诚实方没有为除 B 之外的任何块发布公证份额。 如果另一个块被公证，这将需要 n − t − f 个来自一组不相交的诚实方的公证份额，这是不可能的，因为 f ≤ t < n/3。
如第 3.3 节所述，此性质意味着协议满足安全性。
接下来讨论活跃度。为此，我们正式陈述我们的部分同步假设：
定义 1. 假设在时间 T，所有诚实方都已启动。如果诚实方在时间 T 之前发送的所有消息在时间 T + δ 之前到达目的地，则认为通信网络在时间 T 是 δ- 同步的。
以下引理对应于第 3.3 节中讨论的属性 P3。
引理 6（假设部分同步下的活跃度）。假设：
(i) 最多有 t < n/3 个舞弊方，签名是安全的，哈希函数是抗碰撞的；
(ii) k > 1，第一个诚实方 P在时间 T进入第 k 轮，并且所有诚实方都在时间 T 被启动；
(iii) 第 k 轮的leader Q 是诚实的；
*(iv) 通信网络在时间 T 和 T + δ +*Δprop(0) 是 δ- 同步的；
(v) 2δ + Δprop(0)≤Δntry(1)。
那么当所有来自诚实方的第 k 轮消息都传递给所有诚实方时，每个诚实方将在其消息池中拥有 Q 的第 k 轮提议块作为最终确定的块。
证明：在时间 T，P 已经在第 1,...,k − 1 轮广播了区块的公证书。这意味着至少有 n − 2t > t 个诚实方已经广播了所有这些区块，因此也广播了第 1 ，...，k轮的随机信标份额。
因此，在时间 T + δ 之前，根据同步假设和引理 3，对于 i = 1,...,k − 1，Q 消息池中有一个经过公证的第 i 轮区块，并且对于 i = 1，... ,k, Q 消息池中拥有超过 t 个第 i 轮随机信标的份额。
因此，Q 将在时间 T + δ 之前进入第 k 轮的主循环，并在时间 T + δ + Δprop(0) （这里假设相对于网络延迟计算时间忽略不计）之前广播其自己的第 k 轮提议块 B。同样，根据同步假设和引理 3，B 在时间 T + 2δ + Δprop(0) ≤ T + Δntry(1)之前将作为有效块出现在每个诚实方的消息池中。这意味着每个诚实方都会为 B 并且只为 B广播公证书份额。
每当来自诚实方的所有第 k 轮消息都传递给所有诚实方时，每个诚实方都将广播 B 的最终确定份额，因此每个诚实方消息池中将会存在 B 作为最终确定的区块。
注意，当 δ ≤Δbnd时，引理 6 的条件 (v)将被公式(2) 中定义的延迟函数满足。
4.3预期消息复杂度和延迟
在给定的第 k 轮中，我们定义诚实方领导者为该轮中排名最低的诚实方，并定义Necho(k)为该轮次中被任意诚实参与方“回传”的任意块的最高排名。 注意，任意诚实方广播的区块数量为 O(Necho(k))。 以下引理定义在部分同步假设下，Necho(k)≤ h，其中 h是轮次k中诚实leader的排名。 这意味着第 k 轮的消息复杂度为Ο((h+1)n2)。 稍后，我们将使用这个结果来证明每轮的预期消息复杂度为Ο(n2)——事实上大概率为Ο(n2)
**引理 7（部分同步下的消息复杂度）**假设：
(i) 最多有 t < n/3 个舞弊方，签名是安全的，哈希函数是抗碰撞的；
(ii) k > 1，第一个诚实方 P在时间 T进入第 k ，并且所有诚实方在时间 T都被启动
(iii) 第 k 轮诚实方的领导者 Q 的排名为 h；
*(iv) 通信网络在时间 T 和 T + δ +*Δprop(h)是 δ- 同步的；
(v) 2δ + Δprop(h) ≤ Δntry(h+1)。
则有 Necho(k)≤ h。
证明：与引理 6 中的推理相同，Q 将进入第 k 轮并在时间 T + δ +* Δprop(h)之前广播自己的第 k 轮提议的区块 B。同样，根据同步假设和引理 3，B 在时间T+2δ+Δproph≤T+Δntry(h+1)之前作为有效块出现在每个诚实方的消息池中。这意味着对于每个诚实参与方都不会为排名大于h的参与方“回传”区块。
注意，当 δ ≤ Δbnd时，引理 7 的条件 (v) 将始终被 (2) 中定义的延迟函数满足。
我们接下来会根据一轮诚实方领导者的排名证明该轮延迟的界限。假设网络在某个时间间隔内是 δ- 同步的，则该结果被证明。然而，与引理 6 和 7 不同，没有假设δ 、延迟函数 Δprop和 Δntry之间存在关系。
引理8（延迟）。假设：
- 最多有 t < n/3 个舞弊方，签名是安全的，哈希函数是抗碰撞的；
- 在时间 T，所有诚实方都已启动，k 是任何诚实方进入的最高轮次；
- 第 k 轮诚实方的领导者 Q 的排名为 h；
- 通信网络在如下时间间隔内始终是 δ-同步的
[T, T+Δ0h,δ+2hδ]
其中
Δ0h,δ≔max2δ+Δproph, δ+Δntryh#3
那么所有诚实方完成第k轮的时间为时间T+(4)，
Δ0h,δ+2h+1δ#4
证明。与引理 6 中的推理相同，所有诚实方都将进入第 k 轮并在时间 T + δ 之前到达第 k 轮的主循环。此外，Q 将在时间 T + δ +Δproph之前广播自己第 k 轮提议的区块 B。同样，根据同步假设和引理 3，B 在时间 T +2δ+Δproph之前作为有效块出现在每个诚实方消息池中。因此，每个诚实方都会在时间 T +Δ0h,δ之前广播 B 的公证书份额，这将导致所有参与方在时间 T +Δ0h,δ+δ 完成该轮，*除非某个诚实方已经在时间 T +*Δ0h,δ 之前收到并“回传”了一个排名较低的块。
所以假设从现在开始到时间 T + Δ0h,δ，某个诚实方收到并“回传”了一个的排名小于h的区块。
对于 i = 0,...,2h，我们将考虑时间点 T +Δ0h,δ+ iδ。在每个时间点，我们将为每个小于h的排名设置一个状态，包括“未使用”、“已使用”或“已损坏”。每个排名初始状态均为未使用。在每个时间点 T + Δ0h,δ+ iδ，我们将改变最多一个排名 r 的状态，以便满足以下条件：
- 排名r 可能从未使用变为已使用，如果发生这种情况则意味着，在时间 T+Δ0h,δ+iδ 之前，某个诚实方至少收到并回应了一个 排名r的区块，在时间 T +Δ0h,δ+(i+1)δ之前，所有诚实方消息池中将会有一个排名为 r 的区块。
- 排名 r 可能会从已使用变为已损坏，如果发生这种情况则意味着，在时间 T + Δ0h,δ+iδ 之前，诚实参与方至少收到并回传了两个不同的排名为r的区块，并且在时间 T + Δ0h,δ+ (i + 1)δ之前 ，每个诚实参与方消息池将中拥有两个不同的排名为r的区块。
此外，如果没有排名改变状态，那么所有诚实方将在时间 T + Δ0h,δ + (i + 1)δ 之前完成该轮。由于状态变化不超过 2 小时，因此各方将在时间 T + Δ0h,δ+ (2h + 1)δ 之前完成该轮次。
假设在时间点 T+Δ0h,δ，某个诚实方收到并回传了一个排名小于h的块。选择排名最小的块并将其状态从未使用更改为已使用。
反过来，依次考虑i = 1,...,2h的时间点 T +Δ0h,δ+iδ。令 r 为时间 T + Δ0h,δ + (i − 1)δ 时状态为已使用的排名，如果没有则设 r := h。
现在，假设在时间 T +Δ0h,δ+iδ之前，某个诚实方已经收到并回传了一个排名小于 r 的状态为未使用的块；这种情况下，我们选择排名最小的这样的块并将其状态更改为已使用。
否则，在时间 T +Δ0h,δ+ iδ之前，所有诚实方都取消了任何小于 r 的已损坏排名的资格，并且已经收到并回传了至少一个排名为r 的区块。
- 如果每一方广播了同一区块的公证书份额，则所有诚实方将在时间 T + Δ0h,δ + (i + 1)δ 之内完成该轮。
- 否则至少公证了两个不同的排名为r的区块，我们将 r 的状态更改为已损坏。
请注意，引理 8 中的延迟界限 (4) 为第k轮从第一个诚实方开始到最后一个诚实方完成之间的时间。 如果出现最终确定，它不考虑额外的实际最终确定一个块的通信延迟。 这需要在界限 (4) 中添加一个 δ 项，从而可以更恰当地被视为控制协议的吞吐量——块被公证的速率，这与协议输出有效负载的摊销率（amortized rate）成正比（考虑到有效负荷可能包含许多命令 ）。
如果有攻击将会导致延迟基本上等于引理8中的上限。
4.3.1概率分析
设 h 是第 k 轮中诚实领导者的排名，可将其视为一个随机变量。 引理 7 和 8 中消息复杂度和延迟的结果依赖于 h 的值。 假设对手静态地舞弊参与方（即在协议执行开始时确定舞弊方），或者至少在第 k 轮的随机信标向对手透露之前，这种情况下，对手对舞弊参与方的选择和第 k 轮的排名函数是独立的。 假设 t < n/3，那么对于 i = 1,...,t，
Prh≥i= tn ∙t-1n-1 ∙∙∙∙t-i-1n-i-1 <13i #5
当然，对于i>t，有Prh≥i=0。尤其，根据尾和公式（tail sum formula），h的期望值为
Eh= i≥1Pr[h≥i]≤i≥113i= 12
因此，假设网络在第 k 轮中保持 δ- 同步，有 E[Necho(k)] ≤ 1，则该轮的预期消息复杂度为 O(n2)。然而，（5）是更重要的因素。
现在考虑引理8假设下的预期延迟，假设延迟函数Δntry和Δprop如（2）中定义，这种情况下，有
Δ0h,δ=2Δbndh+ δ+ max(ϵ,δ)
因此延迟（4）的界限为
2(Δbnd+δ)h+ 2δ+ max(ϵ,δ)
因为Eh=1/2，预期延迟最多为
Δbnd+3δ+ max(ϵ,δ)
4.4 间断同步下的活跃度（liveness under interval synchrony）
如上所述，如果网络在第一个诚实方进入该轮开始较短的时间间隔内是 δ- 同步的，则引理 6 保证了给定轮次的活跃度。 最好能够说，只要网络在足够长的时间间隔内保持δ- 同步，则无论协议到达任何轮次，活跃度都将保持不变。 我们可以通过将 引理8 的延迟与引理6 结合来获得如下结果：
**引理9（假设间断同步下的活跃度）**假设：
(i) 最多有 t < n/3 个舞弊方，签名是安全的，哈希函数是抗碰撞的；
(ii) 在时间 T，所有诚实方都已启动，k 是任意诚实方进入的最高轮次；
(iii) 第 k 轮的诚实leader排名为 h；
(iv) 通信网络在整个时间间隔内始终是 δ- 同步的
[T, T + Δ0(h, δ) + (2h + 2)δ + Δprop(0)]，
其中 Δ0(h, δ)定义如（3）；
(v) 第 k+1 轮的leader是诚实的；
(vi) 2δ +Δprop(0) ≤ Δntry(1)。
那么当所有来自诚实方的 (k + 1) 轮消息都传递给所有诚实方时，每个诚实方消息池中将拥有第 k + 1 轮领导者提出的区块作为最终确定区块。
如果我们进一步延长同步的时间间隔，我们可以保证大概率该间隔内的某一轮将最终确定由诚实领导者提出的一个区块。
4.5提议复杂度
在给定的第 k 轮中，我们将Nprop(k)定义为在第 k 轮中提出自身区块的任意诚实方的最高排名。 Nprop(k)的大小决定了在第 k 轮网络中流通的不同区块的数量（至少是诚实方提出的那些）。 正如第 1 节中简要讨论的那样，边界 Nprop(k)将有助于控制整体通信复杂度，尤其是当使用p2p gossip子层实现底层广播时。
在本节中，我们研究在哪些假设下边界 Nprop(k)仍然保持良好。
**引理10（在部分同步下的提议复杂度）**假设：
- 最多有 t < n/3 个舞弊方，签名是安全的，哈希函数是抗碰撞的；
- k > 1，第一个诚实方在时间 T进入第 k 轮，所有诚实方到时间 T为止都已启动；
- 第 k 轮的诚实方领导者 Q 的排名为 h；
- 通信网络在整个时间间隔中始终是 δ- 同步的，
[T,T +Δ0(h,δ)+2hδ]
其中Δ0(h,δ)定义为（3）；
- l≥1 是这样的
Δ0h,δ+2h+1δ≤ Δproph+l#6
那么Nprop(k) <h+l
这个引理很容易从引理8的延迟中得到，假设延迟函数如（2）中定义，且δ≤Δbnd和ϵ≤Δbnd，所以
Δ0h,δ≤2(h+1) Δbnd
因此，如果网络在轮次k中始终保持δ同步，那么
Nprop(k) <2h+1
4.6崩溃故障分析
在只有崩溃故障的常见情况下，我们重新审视上面的一些分析。在这种设置中，如果诚实方领导者的排名为h，那么排名0，…，h-1的各方都崩溃了。
**引理11（假设部分同步和崩溃故障下活跃度和消息复杂度）**假设：
- 最多有 t < n/3 个舞弊方，签名是安全的，哈希函数是抗碰撞的；
- k > 1，第一个诚实方在时间 T进入第 k 轮，并且所有诚实方在时间 T 之前都已启动；
- 第 k 轮的诚实方领导者 Q 的等级为 h；
- 通信网络在时间 T 和 T + δ + ∆prop(h) 是 δ - 同步的；
- 2δ + ∆prop(h) ≤ ∆ntry(h + 1)。
那么
- 当来自诚实方的所有第 k 轮消息都已交付给所有诚实方时，每个诚实方消息池中将拥有 Q 的第 k 轮提议区块并作为最终区块，并且
- Necho(k)≤ h，事实上，任意诚实方回传的唯一区块是 Q 提议的区块。
请注意，当 δ ≤ Δbnd时，引理 11 的条件 (v) 将被 (2) 中定义的延迟函数满足。
**引理12（假设崩溃故障下的延迟）**假设：
- 最多有 t < n/3 个舞弊方，签名是安全的，哈希函数是抗碰撞的；
- 在时间 T，所有诚实方都已启动，k 是任意诚实方进入的最高编号的回合；
- 第 k 轮的诚实方领导者 Q 的排名为 h；
- 通信网络在以下整个时间间隔中始终是 δ- 同步的，
[T,T +Δ0(h,δ)] 其中Δ0(h,δ)如（3）中定义
那么所有诚实参与方完成第k轮的时间为T+（7）
Δ0h,δ+δ#7
**引理13（假设部分同步和崩溃故障下的提议复杂度）**假设：
- 最多有 t < n/3 个舞弊方，签名是安全的，哈希函数是抗碰撞的；
- k > 1，第一个诚实方在时间T进入第 k 轮，并且所有诚实方在时间 T 之前都已启动；
- 第 k 轮的诚实方领导者Q 的排名为 h；
- 通信网络在以下整个时间间隔内始终是 δ- 同步的
[T,T +Δ0(h,δ)]
其中Δ0(h,δ)如（3）中定义
- l≥1 是这样的
Δ0h,δ+δ≤ Δproph+l#8
那么Nprop(k) <h+l
我们来检查引理13中的结果，假设延迟函数如（2）中定义，并且δ≤Δbnd和ϵ≤Δbnd，那么
Δ0h,δ≤2(h+1) Δbnd
因此，如果网络在轮次k中始终保持δ-同步，那么
Nprop(k) <h+1
特别是，在第 k 轮中最多有两个区块在网络中流通，即一个排名为 h 的区块，以及（可能）一个排名为 h + 1 的区块。
4.7一致性故障分析
考虑到参与方可能舞弊但行为一致的情况，这意味着他们不会发送可能取消他们资格的不一致的提案。正如第 5.1 节中讨论的细节，这在一种参与方被永久取消资格的变种协议中尤为重要。这种变种协议中，至多 t 轮任意方都能被取消资格。
一个结论是引理 8中的延迟是可以改善的。尤其是延迟界限 (4) 可以减少到
∆0h, δ+ h + 1δ, #9
其中∆0h, δ如（3）中定义。
另一个结论是提案复杂度可以改进。 具体来说，引理10中的公式（6）可以用稍微弱的条件代替
∆0h, δ+ h + 1δ ≤ ∆proph + l#10
4.8本地延迟函数
目前为止，为简单起见，我们假设了所有诚实方在每一轮中都使用相同的延迟函数∆prop 和 ∆ntry。这并不完全现实，原因至少有两个。
首先，诚实方的时钟可能以略微不同的速率运行（时钟漂移）。可以通过使各方具有不同的延迟函数来解决。
其次，如果网络延迟随时间变化，诚实方希望根据系统的感知性能动态调整他们的延迟函数来应对此变化。
例如，如果某方看到太多轮次没有最终确定，或者看到几个轮次消息复杂度过高超出预期，则可能会增加其 ∆ntry延迟函数。在 ∆ntry增加后，一方会尝试在之后的轮次中减少它。对于（2）中定义的延迟函数，可以通过简单地调整用于定义函数∆ntry的 ∆bnd的值来对 ∆ntry进行这些调整（不必改变用于定义函数∆prop的 ∆bnd的值）。在另一种场景中，如果协议相对于系统中的其他元素运行过快，某方会增加 (2) 中的附加项ϵ以使协议慢下来。在任何情况下，各方都是在本地做出这些决定，从而他们最终会得到不同的延迟函数。
因此，我们引入了本地延迟函数。具体来说，假设轮次k中参与方Q使用延迟函数Δprop(k,Q)和Δntry(k,Q)。假设对于每个k和Q，函数Δprop(k,Q)和Δntry(k,Q)是非递减的。
对于每个k，我们定义
Δprop(k) :=minΔpropk,Q :Q honest, Δprop(k) :=max{Δpropk,Q :Q honest}
相似地
Δntry(k) :=minΔntryk,Q :Q honest, Δntry(k) :=max{Δntryk,Q :Q honest}
对于每个k，每个函数
Δprop(k)，Δprop(k)，Δntry(k)，Δntry(k)
都是非递减的。
重新审视依赖于这些延迟函数的每个主要结果。 显而易见，为了保持活跃度和消息复杂度，虽然各方可以本地增加他们的 ∆ntry函数，但不应该本地调整 ∆prop函数，这是很重要的。 但如果只是为了适当地考虑时钟偏移，仍然可以在本地调整 ∆prop。
**活跃度 引理6**仍然是正确的，只是条件（v）被（11）替代
2δ+Δpropk0≤ Δntryk1#11
相似地，崩溃故障情况下，活跃度结果（a部分）仍然是正确的，随着引理11中条件（v）被（12）代替。
2δ+Δpropkh≤ Δntrykh+1#12
在保持活跃度方面，对函数 ∆prop 进行任何本地调整是没有收益的，实际上，本地增加∆prop的值只会使得（11）和（12）不太可能被满足。 因此，从现在开始假设没有对函数∆prop进行本地调整——实际上，没有理由使用除 0 以外的 ∆prop(0) 值，因此假设 Δpropk0=0。
现在，如果有几轮没有最终确定，并且每个参与方 Q 自发式地增加Δntry(k,Q)至足以补偿大于预期的网络延迟，那么最终确定将在第 k 轮恢复。 此外，就活跃度而言，如果Δntry(k)过大没有惩罚，此情况下 (11) 和 (12) 仍然成立。 也就是说，如果对∆ntry所做的本地调整彼此不同步，只要它们都足够大，就不会受到惩罚。
消息复杂度 引理7仍然成立，随着条件（v）被（13）替换，
2δ+Δpropkh≤ Δntrykh+1#13
因此，用于活跃度的相同解释也适用于消息复杂度。 在保持消息复杂度方面，对函数 ∆prop 进行任何本地调整没有收益，所以继续假设没有进行此类调整。 此外，如果各方 Q 在本地增加∆ntry到足以补偿大于预期的网络延迟，那么消息复杂度应该在第 k 轮再次恢复到界限内。 此外，就消息复杂度而言，如果对函数∆ntry所做的本地调整彼此不同步，只要它们都足够大，就不会受到惩罚。
延迟 引理8仍然成立，随着∆0h, δ被（14）替代
Δ0kh,δ :=max2δ+ Δpropkh, δ+Δntrykh#14
很明显如果Δntrykh太大，我们会受到惩罚。 但是我们强调无论是哪个 Δntryk，协议仍然会响应。例如假设 Δpropk0和Δntryk0 （接近）为零并假设第 k 轮领导者是诚实的，协议会以网络速度运行。
然而，在间断同步假设下，引理 9 的活跃度产生了相同的惩罚——同步下保持的时间间隔的长度随着 Δntrykh的增加而增加。
**提案复杂度 引理10**仍然成立，随着∆0h, δ被（14）中定义的Δ0kh,δ所代替，不等式（6）被（15）代替
Δ0kh,δ+2h+1δ≤Δpropkh+l#15
正如前面已经提到的，为了维持活跃度和消息复杂度，我们不应该在本地调整∆prop函数。所以假设对于所有的k和Q，Δprop(k,Q)=Δprop，条件（15）变成
maxδ+∆proph,Δntrykh+2h+2δ≤∆proph+l#16
然而，这揭示了保持消息复杂度和提案复杂度目标之间的紧张关系。 如果网络出乎意料地慢，并且 Δntrykh出乎意料地大，则条件（16）无法满足任何合理小的 l。
注意，即使我们只考虑一致性故障或崩溃故障，也会存在同样的问题。 在崩溃故障情况下，引理13中的条件 (16) 变为
maxδ+∆proph,Δntrykh+2δ≤∆proph+l#17
这也不可能满足任意合理小的l。
一种可能缓解该问题的方法是定义超线性增长的延迟函数，而不是像 (2) 中的线性增长——这将使(17) 更可能满足更小的 l值。
5. # 变种协议
在本节中，我们考虑一些协议的变种及其影响。
5.1永久取消不一致方资格
正如之前提到的，如果一方检测到另一方在一轮中提出了两个不同的区块，则前者可以取消后者的资格。 但是，取消资格不会延续到后续轮次。
图表 3：永久取消资格逻辑架构
协议可以修改为，如果一方在某一轮中取消了另一方的资格，那么它广播一条称为“不一致声明”的特殊消息，来证明一方在同一轮中验证通过了两个块，而不是（像向当前协议中）广播导致取消资格的第二个区块。
回想一下第3.4节，我们为第k轮区块
B=(block, k,α,phash,payload)
定义了一个验证器作为元组(authenticator,k,α,HB,σ)，其中σ是参与方Pσ在（authenticator,k,α,HB）上的有效Sauth签名。
第k轮中来自Pα的不一致验证器为一对元组
authenticator,k,α,hash1,σ1, (authenticator,k,α,hash2,σ2)
其中对于i=1,2，σi是参与方Pσ在authenticator,k,α,hashi上的有效Sauth签名，并且hash1≠hash2。
对于第k轮针对Pσ的不一致证明为如下形式的元组
(inconsistent,k,α,hash1,σ1,hash2,σ2)
对于i=1,2，σi是参与方Pσ在authenticator,k,α,hashi上的有效Sauth签名，并且hash1≠hash2。假设Sauth签名是安全的，则无法构建针对诚实方的不一致证明。注意有了这种验证器的新语法，可以在不知道块本身的情况下验证这种不一致证明。
树构建子协议修改如下。首先，每一方Pα维护已经被永久取消资格方的集合Dp，而不是维护每轮被初始化为∅的取消资格方的集合 D。在协议的最开始，集合Dp被初始化为 ∅。
其次，图1主循环中“wait for”条件（c）的逻辑被修改为如图3所示。
这里，ranks(Dp)表示集合Dp中当前轮次各方排名的集合。此外，如果 Pβ是本轮中排名为 r 的一方，那么排名为 r 行为不一致的证据要么是
- 当前轮次一对来自 Pβ的不一致验证器，或是
- 当前轮次或任意之前的一轮针对 Pβ 的不一致证明；
在情况 (ii) 中，Pα广播它所拥有的针对 Pβ的不一致证明，而在情况 (i) 中，Pα构造并广播针对 Pβ的全新的源自不一致验证器的不一致证明。
对于该变种，我们上面证明的所有引理都保持不变，因为没有明显的负面影响。该变种中，经过最多t 轮任意方都可能被取消资格，因此就长期的系统性能而言，实际上只有所有参与方行为一致的协议性能才是更重要的。我们已经在第 4.7 节中讨论了如何在该情况下改善延迟和提案复杂性。
5.1.1暂时取消资格的另一种实现
即使不希望永久取消参与方资格，使用不一致证明和身份验证器的这种可选语法也更实用，因为它不需要为了说服其他方有一方行为不一致而要广播整个第二个块。实际上，通过简单地将上面排名为r 行为不一致证据的定义更改为如下两点，从而使得暂时取消资格的原始协议效率更高：
- 当前轮次一对来自 Pβ的不一致验证器，或
- 当前轮次针对 Pβ的不一致证明
5.2协议ICC1：收紧提议条件
在介绍称之为 ICC1 的变种协议时，我们将会假设已经纳入了第 5.1 节中介绍的“永久取消资格”，但它也能够通过使用“暂时取消资格”以及（如下讨论的）一些细小改动来实现。
回顾一下从一轮开始（实际上，从获得当前轮次随机信标开始）经过了Δprop(rme)时间单位后，Pα将会提出自己的区块。在该变种中，我们将收紧Pα方提出其区块的条件，以便如果其消息池中有明显“更好”的区块，它将“阻止”这么做。在这里，“更好”的区块是指等级低于 Pα且未被取消资格的区块。
但是请注意，如果参与方因为在其池中看到“更好”的区块而“阻止”提出其自己的提议，则不能保证任何其他诚实方可以很快看到这个“更好”的区块。因此，比起简单地“阻止”，参与方将回传这个“更好”的区块。准确地说，在轮次结束之前，它将回传最低等级为 r 的“更好”的区块，但前提是自轮次开始已经过去了Δprop(r)时间单位。
该变种的目的是当底层通信层为p2p gossip层时（正如互联网计算中的实现）能够最小化带宽使用率。在这种情况下，真正想要最小化的是通过网络流通的不同块的总数（这可能非常大），而不是像传统定义的那样最小化消息复杂度（或通信复杂度）。此外，该变种针对崩溃故障和一致性故障进行了优化（如果协议永久取消不一致方资格这是最重要的，无论是使用这里的机制，还是使用协议栈中一些其他更高层的机制）。该协议变种最类似于当前为互联网计算机设计的协议。我们将在下面简要讨论此变种协议与p2p gossip层之间的更多联系（参见第 5.2.1 节）。
该变种的细节如图 4 所示。请注意，为了简化协议的逻辑，在本节还假设对于所有r∈n有Δprop(r)≤Δntry(r)。在带有本地延迟函数的情况下（如第 4.8 节），该不等式只需要在本地保证（即对于每个 k 和 Q，Δprop(k,Q)(r) ≤ Δntry(k,Q)(r)）。这里，Dp是永久取消资格方的集合，ranks(Dp)是这些方排名的集合，由当前轮次的随机信标确定。 “不一致行为的证据”和“不一致证明”的概念细节可以在第 5.1 节中找到。注意，如果我们希望实施暂时取消资格而不是永久取消资格，可以通过简单地（a）在每轮开始时将Dp重置为∅，和（b）如第 5.1.1 节中定义“不一致行为的证据”和“不一致证明”的概念。
图表 4:ICC1：参与方Pα树构建子协议
5.2.1 p2p gossip子层的更多细节
我们这里不涉及太多细节，只是简单地介绍该变种协议和底层p2p gossip层之间的关系，互联网计算机中也是这样实现的。
有时Gossip通信在描述中满足以下属性：
• 如果任意诚实方发送一条消息，那么最终（或是及时地，在部分同步假设下），每个诚实方都会收到该消息。
• 如果任意诚实的方收到一条“有趣的”消息，那么最终（或是及时地，在部分同步假设下），每个诚实方都会收到该消息。
显然，要使这种类型的通信完全保持在界限内，用于构成“有趣”消息的标准必须相当严格。 其实，如果所有消息都是“有趣的”，那么通信复杂度会可能变得无限大。
本节的变种协议中，在p2p gossip层方面，参与方认为一个块“有趣”，如果这是一个经过公证的区块，或是一个待广播的未经公证的区块，则该方很乐意将该块告诉其他参与方。因此，每轮通过goosip层流通的“有趣”块的数量将是有限的，正如将在下面讨论的，在部分同步假设下，该数量将非常小（至少对于崩溃故障和一致性故障是这样）。除了区块，还有其他类型的消息，例如公证份额、公证书等。总的来说，这些类型的消息与特定的区块相关联，如果区块本身有趣，那么这些消息也会被认为是“有趣的”。
除了提议和公证区块的各方之外，网络还包含额外的“中继（relay）”节点以帮助传播“有趣”的消息。这样的中继节点本质上运行协议时似乎它们的排名为♾——特别是，它们从不提出自己的区块，也从不生成任何公证书、最终确定或随机信标份额。但是，这些参与方通过使用与普通参与方相同的规则来选择“回传”区块。此外，“中继”节点也可能正在运行它们自己的复制状态机的副本。
对于大消息，如果参与方有一条它认为“有趣”的消息，参与方会向网络中直接对等参与方发送“广告（advert）”。广告”是对实际消息的简洁描述。例如，对于一个块，这样的“广告”可能包含有关该块除了通常非常大的有效负载之外的所有信息。如果对等方看到“广告”并认为相关消息“有趣”（例如，一个会回传自己的块），那么对等方将自己请求消息。发出请求的对等方还可以根据哪些消息看起来更“有趣”（给定轮次中，排名更低的块通常更“有趣”），对此类请求进行优先级排序。这种试探法通常会产生良好的带宽利用率，同时在合理假设下仍然保持活跃度（当然，安全性永远不会受到威胁）。
5.2.2分析
回顾之前定义的：
- Nprop(k)是轮次k中提交自己的块并且排名最高的诚实参与方，并且
- Necho(k)是被任意方回传并且排名最高的区块
定义
Nmax(k)≔max(Npropk,Necho(k))
在任何情况下，这是第k轮被任意诚实方广播的排名最高的区块。
接下来探讨ICC1更为严格的区块提议条件的影响。引理1-6（包括安全度和活跃度）仍然成立。同样地，就崩溃故障时的活跃度而言（不包括消息复杂度），引理11中的（a）部分结论成立。注意如第4.8节所述，活跃度的那些结论在本地延迟函数情况下仍然成立。正如本节中探讨的，如果每一 方在本地充分增加函数Δntry（但并不调整本地Δprop），就会符合活跃度。此外，本地延迟函数Δntry是否同步并不重要----重要的是它们每个都足够大。
如上所述，就带宽利用率而言，我们主要感兴趣的是限制在崩溃故障和一致性故障情况中通过网络流通的的不同区块的数量。所以在这种情况下，这等同于限制Nmax(k)的值。
在崩溃和一致性故障情况下限制Nmax(k)。在崩溃故障或是一致性故障情况中，如果h是轮次k中诚实领导者的排名，并且网络在该轮中是δ-同步的，那么将有Nmax(k)<h+l，倘若
2δ+Δproph≤Δproph+l#18
简要证明：如果第一个诚实方在时间 T 进入该轮，则排名为 h 的参与方Q 将在时间 T + δ 进入，并在时间T+δ+Δproph之前广播自己的或排名更低的提议。这将在时间T+2δ+Δproph之前到达所有诚实方。由于没有取消资格，该协议将阻止所有诚实方广播任何排名高于 h 的提议。
如果我们像 (2) 中那样线性地定义延迟函数，并且 δ≤Δbnd，则该条件将在l≔1时成立。在崩溃故障情况下，这意味着将只有一个块在循环中，而在一致性故障情况下，最多有 h+1 个区块在循环中。
如果(2) 中的网络延迟界限 Δbnd太小，那么我们将需要选择更大的 l值以满足（18），因此 Nmax(k)可能会更大，这可以通过超线性而不是线性增长的延迟函数来缓解。但是要注意，由于 Δprop 出现在不等式 (18) 的两边，像 4.8 节中的那样在本地调整延迟函数对于缓解这种情况帮助不大。
和我们的原始协议来比较Nmax(k)的界限，对于此协议，为了确保Nmax(k)<h+l，我们需要在一致性故障情况中有
2δ+Δproph≤Δntryh+l，并且
max2δ+Δproph,δ+Δntryh+h+1δ≤Δproph+l#19
在崩溃故障情况中
2δ+Δproph≤Δntryh+l，并且
max2δ+Δproph,δ+Δntryh+δ≤Δproph+l#20
可以看到条件（18）弱于条件（19）和（20）。 此外，如果我们本地调整延迟函数 Δntry，则条件（19）和（20）会变得更加难以满足。 因此，就界限 Nmax(k)而言，在一致性故障和崩溃故障情况中，这种变体更优秀。
拜占庭错误情况下限制Nmax(k)**。**在这种情况中，虽然Nmax(k)数量控制着变种协议的消息复杂度，但不再控制网络中流通的不同块的数量（因为现在可能有给定排名的几个块）。在这种情况中，如果h是轮次k中诚实领导者的排名，并且网络在该轮中是δ-同步的，那么有Nmax(k)<h+l，倘若
max2δ+Δproph,δ+Δntryh-1+2hδ≤Δproph+l#21
*简要证明：*如果第一个诚实方在时间 T 进入该轮，则排名为 h 的参与方 Q 将在时间 T + δ 之前进入，并在时间 T + δ + Δprop(h) 之前广播自己的或排名更低的提议。
有两种情况需要考虑。 在第一种情况下，Q 在时间 T + δ + Δprop(h)之前广播自己的提议，其论证如上所述。
在第二种情况下，Q 广播一个较低排名的提议，并阻止广播其自身的提议。这里讨论的是在时间
T+max(2δ+Δproph,δ+Δntryh-1)+2hδΔ0'≔
之前，所有诚实参与方要么完成了该轮次，要么已经接受了Q的提议，这将会阻止所有参与方广播任何排名高于h的提议。
现在，在时间 T + Δ0'之前，所有诚实方都收到了来自 Q 的排名较低的提案，并准备对其发布公证份额。 我们在引理 8 的证明中进行了状态改变的论证，其中每个排名 0,...,h − 1 被分配状态为未使用、使用或损坏。 然而，在时间 T + Δ0' 开始状态改变的论证之前，我们可能已经将Q广播的第一个提议的排名初始化状态为已使用，而不是未使用。 根据引理 8 中使用的相同推理，在最多 2h − 1 次状态改变之后，到时间 T + Δ0'+ (2h - 1)δ，要么
(a) 所有诚实方都在同一个区块上发布了公证份额，或
(b) Q 将广播自己的提议。
所以在时间 T+Δ0'+2hδ 之前，所有诚实参与方要么完成了该轮次，要么已经接受了Q的提议.
和我们的原始协议来比较Nmax(k)的界限，对于此协议，为了确保Nmax(k)<h+l，我们需要
2δ+Δproph≤Δntryh+l，并且
max2δ+Δproph,δ+Δntryh+2h+1δ≤Δproph+l#22
条件 (22) 蕴含着条件 (21)。 因此，就界限Nmax(k)而言，在拜占庭情况中，该变种也很优秀。 但要注意如果是在本地调整函数 Δntry，原始协议和此变种都将难以在拜占庭错误情况下限制Nmax(k)。
延迟。在崩溃、一致性和拜占庭错误情况中，所有关于延迟的结论都保持不变。
*简要证明：*对于崩溃故障，无任何改变。
对于拜占庭故障，讨论如下。如果第一个诚实方在时间 T 之前进入该轮，则排名为 h 的参与方 Q 将在时间 T + δ 之前进入，并在时间 T + δ + Δprop(h) 之前广播自己的提议或是排名更低的提议。
有两种情况需要考虑。 在第一种情况下，Q 在时间 T + δ + Δprop(h)之前广播自己的提议，其论证如对原始协议的分析所示。
正如上面关于Nmax(k)的讨论，在时间
T+max(2δ+Δproph,δ+Δntryh-1)+sδΔ0'≔
之前，其中s≤2h-1,参与方Q要么已经广播了自己的提议，要么所有诚实参与方广播了关于相同块的一个公证份额，并且我们将会有s+1次状态改变。所以在时间
T+max(s+1δ+Δ0',δ+Δntryh)
之前，所有诚实参与方要么完成了该轮，要么准备公证Q的提议。在后一种情况中，他们都会公证Q的提议，除非有多次状态改变，其中可能至多有2h-(s+1)次改变。所以在时间
T+maxs+1δ+Δ0',δ+Δntryh+(2h-(s+1))δ
之前，所有参与方将会公证Q的提议，并且所有参与方都会在时间
T+maxs+1δ+Δ0',T+δ+Δntryh+(2h-s)δ
之前完成本轮，可以验证其最大为延迟限制（4）
对于一致性故障，论证如下。如果第一个诚实方在时间 T 进入该轮，则排名为 h 的参与方 Q 将在时间 T + δ 之前进入，并在时间 T + δ + Δprop(h) 之前广播自己的或排名更低的提议。
有两种情况需要考虑。 在第一种情况下，Q 在时间 T + δ + Δprop(h)之前广播自己的提议，其论证如对原始协议的分析所示。
使用与上面相似的论证，并且使用参与方均一致的事实，在时间
T+max(2δ+Δproph,δ+Δntryh-1)+(h-1)δΔ0'≔
之前，所有参与方都会广播同一个块上的公证份额。所以所有参与方都是在时间T加上
T+Δ0'+hδ
之前完成本轮，可以验证其小于延迟界限（9）.
5.3协议ICC2：减少通信瓶颈
在第5.2节的ICC1协议中，大部分协议，尤其是主循环中“wait for”的条件 (b) 中的逻辑，可以被视为并行大量简单的广播子协议，但随着交错的开始时间——如果自该轮次开始已经过去了Δpropr单位时间，那么排名为rme的一方只愿意参与排名r<rme机器的广播子协议。
然而，所使用的底层广播子协议本身并不能保证一致性，这就是为什么原子广播协议本身需要有额外的逻辑来取消不一致方的资格。此外，底层广播子协议在通信复杂度方面并不是最优的——至少在我们简单计算所有诚实方发送比特数的这种对通信复杂度的传统度量中是这样。如果块的大小为 S，那么忽略签名和签名份额增加的通信复杂度（可能比大块小几个数量级），通信复杂度为O(n2S)。
在本节中，我们将概述如何用可靠的广播协议替代底层广播子协议，从而不必取消不一致方资格。此外，当假设 S = Ω(nlognλ)，并且签名和哈希长度为 O(λ)，则我们使用的特定可靠广播协议的通信复杂度仅为 O(nS)。
这种方法的一个缺点是每轮最佳情况的延迟会增加一些——但只会增加一个网络延迟 δ，另一个缺点是协议的计算复杂度稍高一些。
5.3.1可靠广播
在可靠广播协议中，我们有参与方 P1, . . . , Pn，其中 t < n/3方可能是舞弊的，并且我们假设是一个异步的通信网络。在每个轮次k中，每一方Pα发起协议向所有方可靠地广播单个消息 m：我们称 Pα在第 k 轮中用消息 m 从 Pα 发起可靠广播。在每个轮次k中，对于α≠β，每方 Pβ会发起协议以可靠地接收来自 Pα的一些消息，在第 k 轮中：我们称Pβ在第 k 轮中从Pα发起可靠广播。在每个轮次k中，从Pα发起可靠广播的每一方 Pβ（可能有 α = β）稍后可能会输出单个消息 m：我们称Pβ在第 k 轮中可靠地接收来自Pα的消息m。
这种协议的如下关键属性在每个轮次k都应该成立：
**有效性：**如果诚实方 Pα在第 k 轮用消息 m 从Pα发起可靠广播，那么每个诚实方最终在第 k 轮中都能可靠地接收来自Pα 的消息m。
一致性：如果两个诚实方在第 k 轮中分别可靠地收到来自Pα的消息 m 和 m'，则 m= m'。
完整性：如果一个诚实方在第 k 轮可靠地收到来自诚实方Pα的消息 m，则Pα先前在第 k 轮消息m上发起了来自Pα的可靠广播。
总体性：如果诚实方在第 k 轮可靠地接收到来自 Pα的消息，那么最终每个诚实方都会这么做。
对于有效性和总体性，“最终”是指当所有诚实方都已在第 k 轮中为了来自Pα的可靠广播启动了协议（作为广播者或接收者），并且与该可靠广播实例相关的所有诚实方生成的消息都已被交付。
5.3.2使用纠删码来降低通信复杂度的可靠广播
我们草拟了一个基于纠删码的可靠广播协议，它是《分布式计算》中协议的变体。虽然《分布式计算》中的协议可以看作是从 Bracha 的广播协议 [异步拜占庭协议] 中派生出来的，但我们这里提出的协议可以看作是从 [ANRX21] 的图 1 中提出的更简单的协议派生而来的，它具有比《分布式计算》中更低的延迟。我们的协议还有一个对于原子广播协议至关重要的额外属性----强总体性（strong totality）。原则上，可以在我们的原子广播协议中使用任何满足这一额外属性的可靠广播协议。
我们希望可靠广播的消息是区块，因此我们将自己限制在这种情况中。
我们需要一个 (n, n - 2t) 纠删码。该纠删码可将大小为 S 的区块 B 分解为 n 个片段，每个片段的大小 ≈ S/(n - 2t)，任意 n - 2t 个片段都可用来重构区块 B 。在 t < n/3 的假设下，我们有 S/(n - 2t) < 3S/n，因此所有 n 个片段加在一起的大小最多 ≈ 3S。
我们还需要一个 Merkle 树。知道区块 B 的参与方可以获取 B 的所有 n 个片段，并以这 n 个片段作为叶子构建 Merkle 树，并仅发布 Merkle 树的根。通过在 Merkle 树中沿相应路径发布片段和节点（及其兄弟），上述参与方能够经过验证发布 B 的一个片段。我们称这些节点为有效路径（validating path）。
最后，我们需要一个 (t, n - t, n) 阈值签名方案的实例 Srbc。
当Pα在轮次k可靠地广播了它自己提议的块B ，它首先计算
- hash⟵HB
- B的片段F1,...,Fn
- 使用F1,...,Fn作为叶子的Merkle 树
然后创建B的验证器，此时的验证器和第3.4节中参数不同：它是一个元组(authenticator,k,α,hash,σ)，其中hash是经计算的Merkle 树的根，σ是Pα方在(authenticator,k,α,hash)上的有效Sauth签名。更一般的说法是：
贯穿整个原子广播协议，我们将使用相应的Merkle树的根，而不是使用块的哈希作为块的“句柄（handle）”；这不仅适用于验证器，也适用于公证和最终确认，以及在一个区块内正确地标识其父区块。
Pα还要为每个参与方Pβ创建一个可验证片段，格式如下：
(rbc-fragment,k,α,hash,β,path,Fβ)
其中，path是Merkle 树中叶子Fβ的有效路径，最后，Pα方
- 给每一方Pβ发送相应的片段
- 给所有参与方广播B的验证器和B父节点的公证书
- 可靠地接收B
我们现在来考虑轮次k中Pβ从Pα发起可靠广播的逻辑，其中包括α = β的情况。
- 如果当Pβ接收两个有效验证器
(authenticator,k,α,hash,σ)
并且一个有效的相应的可验证的片段
(rbc-fragment,k,α,hash,β,path,Fβ)
Pβ将会广播这样的可验证片段至所有参与方，以及一个rbc-校验份额，格式如下：
(rbc-validation-share,k,α,hash,rvs,β)
其中rvs是Pβ方在
(rbc-validation,k,α,hash)
上的有效Srbc签名份额。下文中，Pα在轮次k中的rbc-检验格式如下：
(rbc-validation,k,α,hash,σ)
其中σ为
(rbc-validation,k,α,hash)
上的有效Srbc签名。参与方Pβ只会这么做一次(如果它在第k轮中看到来自Pα的第二个验证器，将忽略它)，并且如果它已经执行了第2步，它也不会这么做。
- 如果当Pβ收到
- n - 2t个与某些验证器相对应的可验证片段
(authenticator,k,α,hash,σ)，
不必是其步骤1中接收到的相同验证器，并且
- 要么n-t个有效的相对应的rbc-校验份额，要么是有效的相对应的rbc-校验
参与方Pβ将
- 重建相应的块B
- 计算所有B的片段并验证hash是否正确
- 验证B是否是有效块（为此，需要等到其收到B父区块的公证书）
如果上述验证通过，Pβ将会重建rbc-校验（如果必要）并且广播
- 这个rbc-校验
- B的验证器和B父区块的公证书（如果(α≠β)）
最后，Pβ将会可靠的接收B（如果(α≠β)）。
初步观察。 如果签名方案是安全的，哈希函数是抗碰撞的，并且 t < n/3，则可以验证可靠广播的所有基本属性都会得到满足。 有效性和完整性直接来自假设和构造。 对于一致性，假设某个诚实参与方Pβ在第 k 轮中可靠地从舞弊方Pα接收到块 B。 因为Pβ有 rbc-校验，这意味着至少有 n-2t 个诚实方广播相应的片段和 rbc-校验份额。 由于 t < n/3，并且诚实方仅在第 k 轮中为 Pα发布了一个 rbc-校验份额，因此在第 k 轮中永远不会出现任何对 Pα其他验证器的 rbc-校验。 这意味着一致性，也意味着总体性，因为至少有 n - 2t 方已经广播了相应的片段，并且 Pβ方已经广播了其他参与方完成协议所需的所有剩余数据。
事实上，在原子广播协议中，我们开拓了一个更为重要的属性，称之为
强总体性：
如果 n − 2t 个诚实方在第 k 轮可靠地从 Pα方收到了块 B，则已经广播了足够的数据来使任意诚实方重建块 B。
对于上述协议，如果 n − 2t 个诚实方在第 k 轮中可靠地收到了来自 Pα方的块 B，那么除了Pα之外的某个诚实方在步骤 2 中也可靠地收到了 B，并且根据上述论证，所有需要的数据都已经被广播。
在原子广播协议中，只有当一方可靠地接收到该块时，它才会广播该块上的公证份额。因此，如果任何诚实方消息池中有一个经过公证的区块 B，那么只要当前传输中的所有消息都被送达，所有诚实方就能够将B恢复为经过公证的区块（以及恢复以 B 结尾的区块链中B的所有祖先)
假设网络是δ-同步的。
如果到时间 T，所有诚实方都从一个诚实方发起了可靠的广播实例，那么在时间 T+2δ 之前，所有诚实方都将可靠地收到该消息。
此外，如果到时间 T ，所有诚实方都从舞弊方发起了一个可靠的广播实例，并且某个诚实方 Q 可靠地收到了来自该方的消息，那么在时间 T + δ 之前，所有诚实方都将可靠地接收到该消息。
在通信复杂度方面，每一方在每个可靠广播实例中最多广播一个可验证的片段。n 个这样的片段大小最多 ≈ 3S，因此n2个这样的片段（所有诚实方发送的片段总数）的大小最多 ≈ 3Sn。重要的是，不仅整体通信复杂度是有界的，而且它在所有诚实方中分布得很好——特别是，发送方贡献的通信复杂度只有其他方的两倍左右。
5.3.3一种使用可靠广播的不同的原子广播协议
我们现在介绍第5.2节中呈现方案的一个变种，称为协议ICC2，使用上述可靠广播协议作为子协议。细节如图5所示。
图表 5：ICC2：树构建子协议
此外，我们再详细说明一些额外的细节
- 在每一轮开始时，集合I和 R 被初始化为 ∅。
- 当Pα方从排名为r方（作为接收方或发送方）发起一个可靠广播实例时，排名r被可靠广播协议添加到集合I中。
- 当Pα方可靠地在第k轮从某一方接收到一个区块，区块B被可靠广播协议添加到集合R中。尤其是，当Pα方提议自己的区块B，那么块B会被立即添加到集合R中。
- 即使Pα方未能可靠地收到相应的区块 B或是在相应轮次中从相应方发起了一个可靠广播实例，Pα方仍有可能收到一个公证书（或最终确定）或是公证书（或最终确定）份额的全集。在这里，我们利用了上面提到的强总体性。事实上，这样的公证书（或最终确定）或是公证书（或最终确定）份额的全集意味着至少有 n-2t 个诚实方可靠地收到了该块，因此Pα方最终可以重建相应的块 B（以及以B结尾的区块链中B的所有祖先）。
更具体地说，在图 5 “wait for”的条件（a）中，即使Pα方没有可靠地接收到块 B 或启动相应的可靠广播实例，如果有必要，Pα方将根据它收到的有效可验证片段重建公证块 B。类似的探讨适用于图 2 中的最终块。
- 原则上，一旦 Pα方在给定轮次 k 中从Pβ方发起了一个可靠的广播实例，它将一直执行到完成，无论之后是否可靠地接收到等级更低的块。然而，一旦Pα方完成了这一轮，它就不需要为该轮完成任何未结束的可靠广播实例。这是由强总体性证明的。
5.3.4分析
假设网络是 δ-同步的，第一个诚实方Pα在时间 T 进入该轮。那么在时间 T + δ 之前，所有诚实方将进入该轮，包括排名为 h 的诚实方领导者 Q。这是由可靠广播协议的强总体性证明的：如果 P 以经过公证的区块 B 结束上一轮，则所有其他诚实方也将区块 B 视为经过公证的区块所需的所有数据在时间 T 已经在传播中。因此，在时间 T + δ + Δprop(h) 之前，所有诚实方都准备好从 Q 和所有排名更低的参与方发起广播。
声明。在时间 T + 3δ + Δprop(h)之前，所有诚实方都可靠地收到了某个排名为 r ≤ h 的区块 B。
- 一方面，假设到时间T + δ + Δprop(h)，没有诚实方可靠地收到任何排名 < h 的块。这意味着到时，所有诚实方都会从 Q 发起可靠的广播，包括 Q 本身，并且在不到 2δ 个时间单位之后，所有诚实方都将可靠地收到 Q 的提议。
- 另一方面，假设到时间T + δ + Δprop(h)，某个诚实方已经可靠地收到了任何排名 < h 的块。设 B 是此时任何诚实方可靠收到的排名最低的区块，则所有诚实方将在少于 δ 个时间单位后可靠地收到B。
这个声明允许我们保证活跃度，倘若h=0（即，leader是诚实的）并且
3δ + Δprop0≤Δntry1#23
在崩溃故障情况中，活跃度受到保证，倘若
3δ + Δproph≤Δntryh+1#24
如果选择线性的延迟函数，如 (2)，但斜率为3Δbnd，并且网络保持Δbnd-同步，那么将满足不等式 (23) 和 (24)。重要的是，正如在第 4.8 节所示，如果 Δbnd太小，各方可以自适应地调整Δntry函数以进行补偿，从而即使在这种情况下也能保持活跃度。
我们也可以使用这个声明来限制协议的通信复杂度。设Nmax(k)为任意诚实方在第 k 轮中发起广播的最高排名，则我们有Nmax(k)<h+l，倘若
3δ + Δproph≤Δproph+l#25
如果选择线性的延迟函数，如 (2)，但斜率为3Δbnd，并且网络保持Δbnd-同步，我们限制Nmax(k)≤h，并且Eh=O(1)（如4.3.1节）。不像活跃度，如果Δbnd太小，我们无法轻易地自适应调整延迟函数来进行补偿。
至于延迟，对应于（4）的界限变为
max3δ+Δproph,δ+Δntryh+h+1δ#26
5.4限制区块提议者的集合
可以将提议区块的参与方集合限制为排名0, . . . , t。 对于此改变（以及与上面给出的任意变种相结合），我们已经证明的所有引理都保持不变，只是引理 2 中每轮经过公证的区块数量的界限从 n 下降至 t + 1。
2