【白皮书第一章】ICP 2021 互联网计算机共识白皮书,中文版

NBC News:Cardano是市场上最重要的PoS加密货币

美国广播电视网NBC的新闻部门NBC News在一份关于加密货币能耗的名为“加密货币走向绿色:‘PoS证明’能否为能源问题提供解决方案?”的报告中称,Cardano是“目前市场上最重要的PoS加密货币”。(Crypto Globe)

互联网计算机共识

扬·卡梅尼奇、马努·德里弗斯、蒂莫·汉克、伊冯娜-安妮·皮诺莱、维克多·舒普、多米尼克·威廉姆斯

Dfinity 基金会

2021-05-13

概览

我们提出了互联网计算机共识(ICC)系列协议,用于原子广播(又称共识),它是互联网计算机拜占庭容错复制状态机的基础。ICC协议是基于领导者的协议,假定部分同步,并与区块链完全整合。领导者在每一轮中都会有概率性的变化。这些协议非常简单和稳健:在任何一轮领导者腐败的情况下(这种情况本身发生的概率小于1/3),每个ICC协议将有效地允许另一方接管该轮的领导者,很少有麻烦,以便及时地将协议推进到下一轮。与许多其他协议不同的是,没有复杂的子协议(如PBFT中的 “视图变化”)或未指定的子协议(如HotStuff的 “起搏器”)。此外,与许多其他协议(如PBFT和HotStuff)不同,向所有各方可靠地传播区块的任务是协议的一个组成部分,而不是留给其他一些未指定的子协议。ICC协议享有的另一个属性(就像PBFT和HotStuff一样,也不同于其他协议,如Tendermint)是乐观的响应性,这意味着当领导者是诚实的,协议将以实际网络延迟的速度进行,而不是网络延迟的某个上限。我们提出了三个不同的协议(以及每个协议的各种小变化)。其中一个协议(ICC1)被设计成与点对点的八卦子层集成,它减少了在领导者处为传播大区块而产生的瓶颈,这是所有基于领导者的协议,如PBFT和HotStuff,必须解决的问题,但通常没有。我们的协议ICC2通过用一个低通信量的可靠广播子协议(可能是独立的利益)代替八卦子层来解决同样的问题。

1.介绍

拜占庭容错(BFT)是指计算系统能够忍受其部分组件的任意(即拜占庭)故障,而整体上仍能正常运行。实现BFT的一种方法是通过状态机复制[Sch90]:系统的逻辑被复制到许多机器上,每个机器都保持状态,并通过执行一系列命令来更新其状态。为了确保非故障机器最终处于相同的状态,它们必须各自确定地执行相同的命令序列。这可以通过使用原子广播协议来实现。

在一个原子广播协议中,我们有n个当事方,其中一些是诚实的(并遵循协议),一些是腐败的(并可能表现出摇摆不定的行为)。

粗略地说,这样的原子广播协议允许诚实的一方以一致的方式安排命令序列,因此,每个诚实的一方都以相同的顺序安排相同的命令。

每方都会收到各种命令作为输入–这些输入是随着时间的推移逐渐收到的,而不是一次性的。可能需要一个命令满足某种类型的有效性条件,这可以由每一方在本地环境进行验证。这些细节是特定的应用,将不再进一步讨论。

每个输出方一个有序的命令序列–这些输出是增量产生的,而不是一次性的。

任何安全原子广播协议的一个关键安全属性是安全,这意味着每一方输出相同的命令序列。请注意,在任何给定的时间点,一方可能比另一方在协议中走得更远,所以这个条件意味着在任何时间点,如果一方输出了一个序列s,另一方输出了一个序列sJ,那么s必须是sJ的前缀,反之亦然。

任何安全原子广播协议的另一个关键属性是有效性。我们可以考虑不同的有效性概念。在一个概念中,要求每个诚实方的输出队列以 “合理的速度”(相对于网络的速度)随时间增长。这种有效性的概念是相当弱的,因为它没有排除某些当事方的输入命令被无限期地忽略的可能性。在另一个更强的有效性概念中,要求如果 “足够多 “的各方在某个时间点收到某个特定的命令作为输入,那么该命令将在 “不会太晚 “出现在所有诚实的各方的输出队列。当然,如果不精确地定义 “足够多 “和 “不太晚”,即使这个定义也是不完整的。

互联网计算机共识(ICC)协议族。在本文中,我们提出一系列原子广播协议,它对应于互联网计算机中使用的原子广播协议[DFI20]。初步估计,互联网计算机是一个相互沟通的复制状态机的动态集合:在一个复制状态机上的原子广播的指令要么来自收到的其他复制状态机的信息,要么来自外部客户。我们实际上提出了三个具体的协议,ICC0、ICC1和ICC2。ICC0协议是互联网计算机中实际使用的协议的一个简化版本,但更容易展示和分析,它是本文大部分内容的重点。协议ICC1最接近互联网计算机中使用的协议版本,只比ICC0稍微多一点。协议ICC2略微超出了ICC1,并使用了目前互联网计算机中没有使用的技术。我们强调,ICC协议是完全指定的(它们不依赖于未指定的、非标准的组件),极其简单(相当详细的描述很容易放在一个页面上),而且很健壮(面对拜占庭攻击时,性能会优雅地降低)。

在设计和分析任何原子广播的协议时,关于腐败方的性质和数量以及网络的可靠性的某些假设是关键。在本文中,我们将假设最多有t < n/3的各方是腐败的,可能会有任意的行为,并且完全由对手协调。当然,这包括简单地 “崩溃 “的各方。然而,我们确实假设对手在协议执行的开始阶段就静态地选择要破坏的各方。

关于网络,通常有几个不同的假设:在一个极端,我们可以假设网络是同步的,这意味着所有从诚实方发送到诚实方的信息都在已知的时间界限∆bnd内到达。在另一个极端,我们可以假设网络是异步的,这意味着信息可以被任意地延迟。

在这两个极端之间,可以做出各种部分同步的假设[DLS88]。对于我们这里的分析,我们需要的部分同步假设的类型是,网络每隔一段时间在相对较短的时间内是同步的。

无论我们假设的是异步网络还是部分同步网络,我们都将假设从一个诚实的一方发送到另一方的每个消息都会被传递。

像一些原子广播协议一样,ICC协议中的每一个都是基于区块链的。随着协议的发展,一棵区块树被生长出来,从一个特殊的 “创世区块 “开始,它是该树的根。树上的每个非创世区块都包含(除其他外)一个有效载荷,由一连串的命令组成,以及该区块在树上的父方的哈希值。诚实的各方对这棵树有一个一致的看法:虽然每一方对这棵树可能有不同的、部分的看法,但所有各方对同一棵树都有一个看法。此外,随着协议的进展,这棵树上总是有一条承诺块的路径。同样,诚实的各方对这一路径有一致的看法:虽然每一方对这一路径可能有不同的、部分的看法,但所有各方对同一路径都有看法。沿着这个路径的块的有效载荷中的命令是每一方输出的命令。

协议以轮次进行。在协议的第k轮,一个或多个深度为k的块被添加到树上。也就是说,在第k轮中加入的区块总是与根的距离正好为k。在每一轮中,一个随机信标被用来生成n个当事方的随机排列,以便给每个当事方分配一个等级。等级最低的一方是该轮的领导者。当领导者是诚实的,并且网络是同步的,领导者将提出一个区块,这个区块将被添加到树上。如果领导者不诚实或网络是异步的,其他一些等级较高的一方也可能提出区块,并将其区块添加到树上。在任何情况下,协议的逻辑都给予领导者提议的区块最高的优先权。

我们表明:

在这种部分同步的假设下,每一个ICC协议都提供了灵活性。粗略地讲,只要网络在短时间内保持同步,无论各方当时处于什么轮次,如果领导者是诚实的,只有领导者的区块会被添加到该轮次的区块树上,而从根到该区块的路径上的所有节点都会被承诺。即使是在异步设置中,每个ICC协议都提供了安全性。

在ICC协议的最基本版本中,部分同步假设中的通信延迟约束∆bnd是协议规范中的一个明确参数。就像许多这样的协议一样,ICC协议很容易被修改,以适应未知的通信延迟约束。然而,在此过程中必须注意一些问题,我们将详细讨论这一问题。

我们还分析了每个ICC协议的消息复杂性。消息复杂度被定义为所有诚实的一方在任何一个轮次中所发送的消息总数

因此,一方广播信息对信息复杂度的贡献是n。在最坏的情况下,消息复杂度是O(n3)。然而,我们表明,在网络是同步的任何一轮中,预期的消息复杂度是O(n2) – 事实上,它是O(n2),具有压倒性的概率。这里的概率是相对于该轮的随机信标而言的。

当然,消息复杂度本身并不能说明通信复杂度的全部情况:消息的大小很重要,通信模式也是如此。在ICC0和ICC1协议中,在任何一个轮次中,每个诚实的一方在最坏的情况下广播O(n)消息,其中每个消息是一个签名,一个签名份额(对于一个阈值或多签方案),或一个块。签名和签名共享通常非常小(几十个字节),而块可能非常大(一个块的有效载荷通常可能是几兆字节)。如果该轮网络是同步的,每个诚实的一方以压倒性的概率广播O(1)这样的信息(包括小的和大的)。此外,所有诚实的一方所广播的不同区块的总数通常是O(1)–也就是说,诚实的一方通常都广播相同的区块(或一小撮不同区块中的一个)。这一特性与互联网计算机对这些广播的实现有很好的互动,它是通过点对点的八卦子层完成的[DGH+87]。正如我们将讨论的那样,ICC1协议被明确设计为与这个点对点八卦子层很好地协调(尽管该协议的逻辑可以很容易地理解为与这个子层无关)。

ICC2协议的结构与ICC1协议非常相似;然而,它不是依靠点对点的八卦子层来有效地传播大区块,而是利用基于擦除码的子协议来进行传播。假设区块大小为S,S=Ω(n log n λ),其中签名(和哈希)的长度为O(λ),在ICC2的每一轮中,每一方传输的总比特数为O(S),概率极大(假设该轮中网络是同步的)。

我们还分析了ICC协议的对等的吞吐量和延迟。在系统的稳定状态下,领导者是诚实的,网络延迟由δ≤约束。

∆bnd,ICC0和ICC1协议将每2δ个单位的时间完成一个轮次。也就是说,对等的吞吐量是2δ。这些协议的延迟,即从领导者提出一个区块到所有各方承诺一个区块所经过的时间,是3δ。对于ICC2协议,互换的吞吐量是3δ,延迟是4δ。边界δ可能比部分同步假设(用于确保有效性)所依据的网络延迟边界∆bnd小很多。特别是,ICC协议享有被称为乐观响应性的特性[PS18],这意味着在领导者诚实的那些轮次中,协议将以网络允许的速度运行。对于一个任意的轮次,当领导者不诚实或δ>∆bnd时,该轮次将以压倒性的概率在O(∆bnd + δ)的时间内完成。

1.1 相关工作 原子广播问题是所谓的共识问题的一个特例。[LSP82]将面对任意故障时达成共识的问题表述为拜占庭将军问题。同步通信模型中的第一个解决方案由[PSL80]给出。

在异步通信模型中,表明没有确定性协议可以解决共识问题。尽管这个结果是否定的,但这个问题可以通过概率性协议来解决。第一个这样的协议是由[Ben83]给出的,他还表明,在异步设置中,弹性约束t < n/3是最佳的。如[CKS05, CKPS01]所示,使用密码学可以实现更有效的协议,最近在[MXC+16, DRZ18, GLT+20]中也有重大改进。

尽管最近在异步设置中取得了进展,但在部分同步设置中仍有更有效的共识协议。这种情况下的目标是在不做任何同步假设的情况下保证安全,并且只依靠网络同步期来保证有效性。第一个在部分同步环境下的共识协议是由[DLS88]给出的。在这种情况下,第一个真正实用的协议是著名的PBFT协议[CL99, CL02],它是一个用于原子广播和状态机复制的协议。

PBFT以轮次进行。在每一轮中,一个指定的领导者通过广播向所有各方提出一批命令。接下来是两个all-in-all的通信步骤,以实际承诺该批命令。在正常运行情况下,领导者将继续扮演其角色许多轮。然而,如果有足够多的缔约方认为协议没有取得及时的进展,他们将触发一个视图提案改变操作,这将选举一个新的领导者,并清理旧领导者留下的任何混乱提案。

尽管它对该领域产生了深远的影响,但PBFT在几个方面仍有一些改进的余地。

1.视图改变子协议是一个相对复杂和昂贵的程序。2.领导者负责向所有各方传播批文。这就产生了两个问题。(a) 首先,如果批次非常大,领导者就成为通信复杂性的瓶颈。(b) 其次,一个腐败的领导者可能无法将一个批次传播给所有各方。事实上,一个腐败的领导者(加上其他腐败方的帮助)可以很容易地推动协议前进任意数量的轮次,并留下一个落后的诚实方的子集,没有任何与这些轮次对应的批次。关于这些落后方如何追赶的细节并没有具体说明,只是说这样的一方可以从另一方获得任何丢失的批次。虽然这肯定是真的,但这个想法的天真实现使攻击者很容易进一步提高通信的复杂性,使许多腐败方要求从许多诚实方获得缺失的批次–所以不是只有领导者广播批次,而是最终会出现O(n)个诚实方在每一轮中都向O(n)个腐败方传送批次的情况。

3.每轮最后两步的all-in-all通信模式也会导致高通信复杂度。然而,如果批次相对于n来说非常大,就不必如此–在这种情况下,批次的传播仍然是通信复杂性的主导因素。

协议的通信复杂度传统上定义为所有诚实方传输的比特总数。在诸如 PBFT 之类的协议中,它以轮为单位构建,这通常以每轮为基础进行衡量。

很多工作都是通过消除所有对所有的通信步骤来降低PBFT的通信复杂性[RC05, GAG+19, AMN+20] 。然而,正如[SDV19]中的经验证明,这种努力可能是错误的:在提高吞吐量和延迟方面,重要的不是通信复杂性,而是通信瓶颈。也就是说,相关的衡量标准不是所有各方传输的比特总数,而是任何一方传输的最大比特数。这样的经验性发现当然对网络的特性很敏感。在[SDV19]中,网络是一个全球广域网,这是我们这项工作中最重要的设置。正如[SDV19]中所报告的那样,正是大批量的传播在领导者那里产生了通信瓶颈,而不是所有对所有的通信步骤,这只涉及较小的对象。事实上,[SDV19]认为,诸如[RC05, GAG+19, AMN+20]中的方法只会加剧领导者的瓶颈。

最近也有关于消除PBFT的复杂视图变化子协议的工作,例如HotStuff [AMN+20] 和Tendermint [BKM18]。与PBFT一样,这两个协议都是基于领导者的;但是,它们不依赖于复杂而昂贵的视图交换子协议,事实上,每一轮都可以轮换一个新的领导者。与PBFT不同,这两个协议都是基于区块链的协议(虽然PBFT可以在区块链的背景下使用,但它不需要)。

HotStuff消除了PBFT的all-in-all的通信步骤。另外,HotStuff(实际上是 “链式 “HotStuff,它是HotStuff的流水线版本)改善了PBFT的吞吐量,将互换的吞吐量从3δ减少到2δ,其中δ是网络延迟。像PBFT一样,HotStuff是乐观的响应(当领导者是诚实的,它运行的速度是网络允许的)。然而,请注意,HotStuff的延迟(从领导者提出一个区块到它被提交之间的时间)从3δ增加到6δ。和PBFT一样,HotStuff依靠领导者来传播区块(即批次),就像PBFT一样,这可能成为一个通信瓶颈,而且没有明确的机制来确保领导者腐败时区块的可靠传播。此外,虽然HotStuff不依赖于 “视图改变 “子协议,但它仍然依赖于一个叫做 “起搏器 “的子协议。虽然起搏器子协议的任务没有视图改变子协议那么繁重,但它仍然是绝对不简单的,而且在[AMN+20]中没有规定。LibraBFT(又名DiemBFT)[Lib20]实现了一个起搏器子协议,但该子协议重新引入了HotStuff打算消除的全对全通信模式。最近,有人提出了具有更好通信复杂性的起搏器协议[NBMS19, NK20, BCG20]。请注意,这些建议都没有处理可靠和有效的块或批的传播,只涉及各方从一轮移动到下一轮时的同步。

Tendermint依靠点对点的八卦子层进行通信。这样做的一个好处是,领导者提出的区块的可靠传播是内置于该协议中的。

与PBFT和HotStuff等协议不同。此外,一个精心设计的八卦子层可以大大减少领导者的通信瓶颈–当然,这可能是以增加对等的吞吐量和延迟为代价的,因为通过八卦子层传播一个消息可能需要通过底层物理网络进行几跳。此外,与HotStuff不同,Tendermint不依赖于任何未指定的组件(如HotStuff的 “起搏器”)。Tendermint的一个缺点是,与PBFT和HotStuff不同,它不是乐观的响应。这可能是一个问题,因为要保证有效性,通常必须选择一个网络延迟上界Δbnd,这个上界可能比实际的网络延迟δ大得多,而在Tendermint中,即使领导者是诚实的,每一轮也需要O(Δbnd)的时间。

MirBFT[SDV19]是PBFT的一个有趣的变体,其中许多PBFT的实例被并发运行。这样做的动机是为了缓解在普通PBFT中观察到的领导者的瓶颈问题。由于MirBFT依赖于PBFT,它也使用了同样复杂和昂贵的视图改变子协议–然而,正如[SDV19]中所指出的,除了PBFT之外,其他协议也可以在其框架中使用。让许多人同时提出批次,这带来了新的挑战,其中之一是要防止命令的重复,这可能会否定吞吐量的任何改善。[SDV19]中给出了这个问题的解决方案。

Algorand [GHM+17]是一个用于股权证明区块链共识的系统,有许多不同的目标,但其核心是一个原子广播的协议。像Tendermint一样,它是基于一个流言子层,区块的传播是建立在协议中的。也像Tendermint一样,它不是乐观的响应。与这里讨论的所有其他协议不同,它依靠一个(非常弱的)同步性假设来保证安全。与ICC协议一样,Algorand也使用类似于随机信标的东西对各方进行排名,但这些排名的基本逻辑是相当不同的。

我们现在强调ICC协议系列的主要特征,以及它们与上面讨论的一些协议的关系。ICC协议极其简单,而且完全自成一体。没有复杂的子协议(类似于PBFT中的view-change),也没有未指定的子协议(如HotStuff中的pacemaker,或可靠的批/块传播,如PBFT和HotStuff)。正如刚才提到的,ICC协议明确地处理了块传播问题。像Tendermint和Algorand一样,ICC1协议被设计成与点对点的八卦子层集成。如上所述,这种八卦子层可以减少领导者的通信瓶颈。

ICC2协议没有使用八卦子层,而是依靠可靠的广播子协议,该协议使用擦除码来减少整体通信的复杂性和领导者的通信瓶颈。这种可靠的广播协议在[CT05]中被引入,之前在[MXC+16]中被用于原子广播的背景。我们提出了一个新的擦除编码的可靠广播子协议,比[CT05]中的协议具有更好的延迟,并且具有更强的特性,我们在与协议ICC2的集成中利用了这些特性。与PBFT和HotStuff一样,与Tendermint和Algorand不同,所有的ICC协议都是乐观响应的。协议ICC0和ICC1达到了2δ的对等吞吐量和3δ的延迟(当领导者是诚实的,网络是同步的)。对于协议ICC2,这些数字分别增加到3δ和4δ。与PBFT一样,但与HotStuff不同,ICC协议利用签名和签名共享的全对全传输。然而,ICC协议面向的是区块相当大的环境,因此全对全传输对通信复杂性的贡献通常不是瓶颈。相反,通信瓶颈是区块本身的传播,ICC1协议通过使用八卦子层来缓解,而ICC2协议通过使用擦除编码的可靠广播子协议来缓解。 与上面讨论的所有协议不同,对于ICC协议,在每一轮中,至少有一个区块被添加到区块树中,这些区块中的一个将最终成为承诺区块链的一部分。这确保了整体吞吐量保持相当稳定,即使在不同步的时期或领导者腐败的轮次中。也就是说,在有腐败领导者的轮次中,领导者提出的区块可能不像领导者诚实时那样有用;例如,在一个极端,腐败的领导者可能总是提出一个空区块。然而,如果一个领导者在这方面一直表现不佳,互联网计算机提供了重新配置协议参与者的机制(在此不作讨论),通过这些机制可以移除这样一个领导者。

健全的共识。我们注意到,ICC协议的简单设计也确保了它们在拜占庭故障实际发生时可以很优雅地退化。正如[CWA+09]中所指出的,最近关于共识的许多工作都集中在提高没有故障的 “乐观情况 “下的性能上,因此所产生的协议是非常脆弱的,当故障发生时可能变得几乎无法使用。例如,[CWA+09]表明,在某些类型的(相当简单的)拜占庭行为下,现有的PBFT实现的吞吐量下降到零。论文[CWA+09]主张采用稳健的共识,在最佳条件下的峰值性能被部分地牺牲掉,以确保在某些当事方实际腐败时的合理性能(但仍然假设网络是同步的)。在[CWA+09]的意义上,ICC协议确实是稳健的:在任何一轮领导者腐败的情况下(这种情况本身发生的概率小于1/3),每个ICC协议将有效地允许另一方接管该轮的领导者,而不需要太多麻烦,以便及时地将协议推进到下一轮。在这种情况下,唯一的性能下降是,不是在O(δ)时间内完成回合,其中δ是实际的网络延迟,而是在O(∆bnd)时间内完成回合(以压倒性的概率),其中∆bnd≥δ是部分同步假设(用于确保有效性)所基于的网络延迟约束。

ICC协议的初步版本。请注意,这里介绍的协议与[HMW18]或[AMNR18]中讨论的协议非常不同。特别是,与这里的协议不同,[HMW18, AMNR18]中的初步协议:(1)只保证了同步环境下的安全;(2)不是乐观的响应;并且具有潜在的无限制的通信复杂性;

1.2 论文余下部分大纲

在第2节中,我们回顾了我们的协议所需要的密码学原语。在第3节中,我们提出了ICC0协议。在第4节中,我们对ICC0协议做了详细的分析。第5节介绍了ICC0的几种变化。在第5.2和5.3节中,我们详细讨论了两个主要的变化,即ICC1和ICC2协议。

毛里求斯央行将在试点基础上引入数字货币

据金十市场消息,毛里求斯央行将在试点基础上引入数字货币。

Click to rate this post!
[Total: 0 Average: 0]

人已赞赏
Dfinity名家说小白百科每日优选

互联网计算机ICP的代币分配以及社区主导治理

2021-6-12 0:39:20

Dfinity名家说小白百科每日优选

DFINITY主网启动以来社区主导网络治理

2021-6-15 13:07:12

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
有新消息 消息中心
搜索