拜占庭终结工具

Note:该篇文章翻译自 Byzantine Finality Gadgets,有歧义处请留言。

1 简介

我们思考了区块链协议的终结问题:什么时候一个区块永远不会被回滚。有许多这样的协议,如最初的区块链——比特币,都具有最终共识的性质——链上一个不断增长的共同前缀将被所有参与者永远认同。但它们通常只给出一个特定块的概率终结性——在给定关于网络和参与者的一些假设下,如果我们看到一个给定块之上有几个块,我们可以估计出它是最终块的概率。

​ 但是我们更想要的是可证明的终结性。比如说,一个被一组可追踪的权威结点签名的声明,这样的块是终结性的。这对于证明轻客户端发生了什么非常有用,它们没有完整的链或者没有积极地监听网络,并且可以与其他链通信,这可能是可伸缩性解决方案的一部分,其中没有任何人接收或存储系统中的所有数据。

​ 另一种流行的区块链共识机制涉及对每个区块达成拜占庭式的协议[1]。这立即给出了可证明的结论。然而,如果我们在拜占庭协议中有大量参与者,这将是缓慢的。我们将采取的方法类似于以太坊计划采取的Casper FFG[2],该方法整合了所有这些方法。为了得到可证明的终结性,我们将使用一个块产生机制,和一个给出最终共识的链选择规则,然后添加一个终结工具,一个终结块的协议,其中的块是已经被参与者同意通过的。

​ 我们提出了一个可以在部分同步网络模型中工作的终结工具,GRANDPA,它可以在多达1/3的拜占庭参与者的情况下工作,以及一个异步终结小工具,它可以应对1/5拜占庭参与者的情况。

​ 最近关于共识的研究提出了许多不同的区块生产机制,最终达成了共识。我们想要正式的保证,来支持终结小工具,可以很容易地应用到许多可能的块生产机制。因此,我们希望对块生产机制做出尽可能少的假设。

​ 这项工作的一个重要目标是将终结小工具问题正式化。我们想要正式的安全保证和终结小工具的活性。

1.1 正式化问题

我们想要形式化“终结小工具”的概念,它可以用来把一个概率终结性的最终共识协议修改成可证明的终结性。为了实现这一点,我们需要在拜占庭协议的定义中纳入这样一个概念,即我们有权使用一项如果不曾被影响,就能最终达成一致的协议。考虑一个多值拜占庭协议的典型定义:我们有一组参与者V,其中大多数遵守协议,但可能有一个常数部分是拜占庭式的,意思是他们的行为是任意的,例如提供虚假的或不一致的信息,或者在应该在线的时候随意离线。

定义 1.1. 多值拜占庭协议中有一组值S和一组投票人V,其中一个常数部分可能是拜占庭式的,对于该部分,每个投票者v∈V从一个初值$s_v$∈S开始,最终确定一个终值$f_v$∈S,使得

  • 协定所有诚实的选民都认为$f_v$值相同
  • 终止所有诚实的选民最终都会决定一个值
  • 有效性如果所有诚实的选民都有相同的初始值,那么他们都决定这个值

​ 我们可以修改这个定义,假设所有投票者都可以访问一个外部协议(值的oracle),而不是初始值,该协议最终达成了一致,即在一段时间后调用它时,它将返回相同的值给所有投票者。

定义 1.2. 我们说协议中的oracle A最终是一致的,如果它在未定时间之后返回相同的值给所有参与者。

定义 1.3. 多值的协议拜占庭终结小工具问题有一组值S,一组的选民V,常量的一部分可能是拜占庭的,每个选民的v∈V访问一个最终一致的oracle A,最后,每个选民决定最终值$f_v$∈S,以下是适用的:

  • 协定所有诚实的选民都认为$f_v$值相同
  • 终止所有诚实的选民最终都会决定一个值
  • 有效性所有诚实的选民决定一个值,这个值有时会返回给一些诚实的选民。

​ 对于二元的情况,比如当|S| = 2,拜占庭终结工具问题是可被简化为拜占庭协议问题。对于|S| > 2的情况,这个就不成立了,因为有效性的定义更强。注意,多值拜占庭协议不可能使有效性条件要求我们确定一些诚实的投票者的初始值,并容忍超过1/|S| 的故障部分,因为我们可能有1/|S| 的选民报告每个初始值,并且拜占庭选民的诚实程度足以无法察觉。对于终结小工具,这种更强的有效性条件是可能的,我们将需要更强的版本来量化一个诚实的投票者何时具有价值。

​ 我们在[7.1]中展示了一个异步的、确定性的二进制终结小工具是不可能的,即使只有一个错误。这并不是[3]著名的不可能结果的直接结果,它表明异步的、确定性的二进制拜占庭协议是不可能的,因为我们不知道在必要的方向上,从协议到最终小工具问题的缩减。选民所掌握的额外信息,即A最终会同意所有选民的意见,不足以使这成为可能。

​ 现在,我们怎样扩展这个到块共识上?正式化问题的一个困难是,块生产机制不能完全与终结小工具分离。为了终结新的块,我们必须依赖已经终结过的链。因此最低限度上,块生产机制需要辨认哪个块已经被终结工具终结了。我们也将允许块生产机制在其他方式上与终结工具的状态进行交互。我们想要终结工具尽可能地与大多数普通的块生产机制共同工作。因此,我们需要一个条件,将最终共识的性质与这一要求结合起来,以依赖最后敲定的块,但在其它方面不太严格。我们假设一种有条件的最终共识。如果我们持续依赖最后敲定的B区块,而不敲定任何新的区块,那么最终我们将达成共识,形成一条比B更长的区块链,终结小工具可以用它来敲定另一个区块。我们还希望协议不会终止,继续完成更多的块。

​ 我们假设有一个与终结工具协议G同时运行的块产生协议P,两个协议的参与者在P中的行为可能会根据G中发生的事情而有所不同。然而在相反方向,一个诚实投票人v在G中的行为被P影响唯一的方式是通过投票规则,一个函数A(v,$s_v$,B)依赖v 和它的状态$s_v$,并且需要一个参数区块B,然后在包含区块B的链头返回一个B’。

​ 如果G已经终结了B,然后最终G将终结B的某些继承者,或者,所有链头为$A_v$的,对于在未来状态$s_v$上的所有投票v,$s_v$(B)将包含相同的B的继承者B’。我们说系统G,P和A达到了条件最终共识。

定义 1.4. 设F是一个协议,包含一组投票人V,有常量比例的投票人可能是拜占庭的。如果对于每个块生成协议P有一个投票规则A,我们说F解决了区块链拜占庭终结工具问题,然后我们有下列:

  • 安全: 所有诚实的验证人在每个区块序号上终结同一个区块;
  • 活跃性: 如果系统F,G,A达成了条件共识,那么所有诚实投票人保持终结块们。
  • 有效性: 如果一个诚实投票人终结了块B,那么该区块在最优链上的区块被一些诚实投票人观察到,该链包括 B 的一些已经被终结过的祖先。

​ 作为一个激励的例子,我们把F用来使用工作证明构建包含G终结的最终块的最长链,把A(v,$s_v$,B)当作是最长链,包含v在状态$s_v$中见证的区块B。众所皆知,在正确假设和相似参数下,使用工作证明的最长链达到最终共识,这展示了在这种情况下,我们有条件最终共识。只要我们不通过终结另一个区块来改变我们正在构建的链,那么我们最终就会与比最后敲定的区块更长一些的前缀达成一致。因此,任何满足定义1.4的最终小工具将在这个体系中起作用,让所有诚实的选民最终敲定一个越来越长的共同链条。由于上面的抽象,我们可以将F转换为许多可能的替代一致算法之一,而G仍然可以工作。

​ 为了分析我们的最终性小工具的性能,我们需要最后两个属性的版本,它们适当地依赖于时间:

  • 快速终止: 直到另一个块被终结前,如果最终终结的块包含序号n,被所有参与者观察的最优链将包含序号为n+1的相同区块,那么一个序号为n+1的区块将在T时间内被终结;
  • 最近有效性: 如果一个诚实投票人终结了块B,那么该区块在最优链上的区块被一些诚实投票人观察到,该链包括 B 的一些在比时间T更早之前已经被终结过的祖先。

​ 直观地,快速终止意味着只要块产生机制能够快速达成一致,我们就可以快速完成终结块,而最近的有效性限制了开始达成一致的成本,而块产生机制稍后的一致决定并不是最好的。在这种情况下,我们可能会把时间浪费在一条永远不会最终敲定的链上,因此,确定我们要花多长时间去做这件事很重要。

​ 这些属性通常只具有高概率。在异步的情况下,我们需要测量协议的时间(以轮为单位),而不是以秒为单位来理解这些属性。我们还希望能够驱逐和惩罚拜占庭选民,这是我们所需要的:

  • 可负责的安全: 如果不同链上的块被最终确定,那么我们至少可以识别 f + 1拜占庭的选民。

1.2 我们的结果

1.3 我们的方法

​ 为了找到解决区块链拜占庭终结小工具问题的方法,我们通常会查看各种拜占庭协议协议,并使用这些协议来查找多值拜占庭终结小工具问题的协议。具有适当属性的协议可以考虑在每个块号上并行运行它们,从而找到解决区块链拜占庭式终结小工具问题的协议。如果一个块协议有正确的属性,那么它们将一致同意块,所以如果我们最终确定一个块,那么我们也确定它的祖先,我们可以提出一个简洁的协议。

​ 例如,假设我们有一个区块协议,要求对区块进行投票,要求参与者观察一个绝对多数投票,比如2/3的选民对某个区块的投票,或者参与者观察到投票尚未决定。现在,假设对每个块编号并行地运行这个投票,并让任何诚实的投票者为来自特定链的块投票。拜占庭投票选民可能不止一次,但如果我们将对一个块的投票计数为对该块的每个祖先的投票,该祖先在对一个块的实例的投票中使用其编号,那么拜占庭选民也必须在链上投票,即使他们可以对多条链进行投票。如果我们这样做,我们就会看到,如果一个块在投票中拥有绝对多数,那么它的所有祖先在投票中也是如此。因此具有绝对多数的块形成了一条链。此外,如果只有1/3的投票者模棱两可,那么如果一个参与者看到链投票的子集,那么他们必须看到所有投票都具有绝对多数的块链的前缀。直观地,协议可以同意2/3的投票者同意使用前缀。

​ 为了确保安全,每个参与者保持$E_r$估计在轮次 r 中已经被终结的最终块。这会有这样一个属性,会在未来几轮它高估了已经被终结了的块,以致于在轮次r中,链头为$E_{r-1}$的链包含所有可能已经被终结的块。任何诚实的投票者都只在第 r 轮中投票给包含其估计值为$E_{r-1}$的链,这保证了本会在第 r-1 轮中完成的任何块都将在第r轮中完成。

1.4 相关工作

1.4.1 与Casper比较

在Casper中引入了终结小工具这个友好的终结小工具,它仍然是与我们最相似的终结小工具。所以比较它们是有意义的。但是首先,我们应该提到其他也称为Casper的协议。

​ 第一个是Casper TFG。Casper CBC[4]给出了该协议的一个最新的、明确指定的版本。它的分叉选择规则使用GHOST选择规则的投票。在Casper TFG中,投票是块,但是它们是由参与者(提议者和验证者)像投票一样进行计数的,这与GHOST在工作证明中的使用方式不同。它还有一种灵活的方式,可以根据投票图主观地确定区块。

​ 在Casper FFG[2]中,验证人对检查点之间的链接进行投票,检查点的块号是50的倍数。如果在连续的检查点有2/3的选票支持一个区块,那么我们就可以确定到第一个检查点的区块链。

​ Casper FFG 和GRANDPA 之间有两个主要的区别。一是在GRANDPA,不同的选民可以在不同的高度同时投票。这是通过借用Casper TFG的GHOST投票概念,并将其应用于更传统的拜占庭协议协议中实现的。

​ 另一个主要区别是终结工具如何影响底层块产生机制的分叉选择规则。在GRANDPA中,默认情况下,我们将假定这只会受到必须包含任何最终块的影响。Casper FFG[2]没有指定一个分叉选择规则,但是它要求我们在合理的块上灵活地构建。Casper的后续规范使用了分叉选择的GHOST规则。

​ 只有依靠终结块,才能更清晰地区分块产生机制和终结小工具。因此,它可能更容易适应其他类型的协议,以实现最终的共识——在过去几年中,已经开发了许多不同的协议来实现这一点。这也使得验证活性属性变得更加容易。如果终结小工具没有进行终结,因此没有进行干预,那么底层机制应该会达成最终共识,这应该足以让最终小工具完成我们所达成的任何共识。

​ 另一方面,虽然在没有终结机制的情况下,在最长的链上进行构建以最大化区块奖励是合理的,但对于构建最长的链,包括最后完成的区块,情况并不总是如此。这是因为,可能会有另一条不同的链被终结,在这种情况下,理性的做法可能是在此基础上再建一条。GHOST方法在分叉选择规则上也许更理性。目前尚不清楚它是否存在,也不清楚如何证明这种规则的活性。进一步的研究可能需要表明,有一个分叉选择规则,这是理性的,并导致活跃性的最终小工具。

2 预备知识

网络模型:我们将主要使用部分同步的传播网络模型,如[1]第二部分A所述。参与者通过传播网络进行通信,其中他们连接到其他参与者的一个子集,并将他们收到的所有消息转发给所有已连接的对等方。我们假设网络图是这样的:任何拜占庭式的参与者都不能切断一个诚实的参与者,因此一个诚实的参与者发送或接收的任何消息都会到达所有诚实的参与者。我们将使用的部分同步是在T时间内接收消息的模型,但可能仅在某些全局同步时间(GST)之后。具体地说,某个诚实的参与者在t 时刻发送或接收的任何消息最迟在GST + T 时刻被所有诚实的参与者接收。

投票人们:我们想要改变那些有时主动同意的参与者。为了对此进行建模,我们有大量跟踪消息的参与者。对于每个投票步骤,有n个投票人。我们经常需要假设对于每一个这样的步骤,最多f < n/3 投票者是拜占庭式的。我们需要n - f 的选民同意最终结果。无论块生产者是否投票,他们都需要成为跟踪协议状态的参与者。

投票:投的票是一个块哈希,以及一些元数据,如整数和投票类型,类型如prevote 或precommit ,都是由投票者的私钥签名的。

轮次:每个参与者都对当前的轮数有自己的想法。每个预投票和预提交都有一个相关的整数。诚实的选民在每一轮投票中只投票一次(每种类型的投票),而在前几轮和后几轮投票中都不投票。

​ 参与者须留意他们认为哪个块是最新被终结的,以及估计哪个块可在最后一轮被终结。

​ 对于块B,我们把链头为B的写为链(B)。对于块序号,一个B块的n(B)是链(B)的长度。

​ 对于块B’和B,如果B的块序号更大,那么我们说B在B’之后。对于B和B’在同一个区块链中,并且B’在后面,我们写作B > B’ 或者 B是B’的后继者,即B’∈链(B),条件为:n(B) > n(B’) 并且B < B’ ,或者对于B∈链(B’),n(B’) > n(B),B’是B的祖先结点。B ≥ B’ 和B ≤ B’ 除了允许B = B’ 之外是相似的(//TODO: 这里不是很明白)。 如果B < B’,B = B’ 或者 B > B’ 我们写作 B ~ B’ 或者B和B’ 是在同一条链上的;如果没有这样的一条链,我们写作B ⍭ B’ 或者B和B’ 不是在同一条链上。

​ 块按树的顺序排列,以创世块作为根。所以任何两个块都有一个共同的祖先,但是不在同一链上的两个块没有一个共同的后代。

​ 投票者V对B块的投票v是由V签名的消息,包含B的块哈希和元数据信息,如投票的整数和类型。

​ 如果在投票集合S中投了超过一票,那么一个投票人在其中是模糊的。如果模糊投票人的数量达到了最多的f,我们认为一组投票S是容忍的。如果一组投票人或是给大于等于B的块投过一票,或是至少有(n + f + 1)/2的数量是模糊的,我们说S对于B是绝对多数投票的。我们计算模糊投票人的数量如同投票给任何像这样的,所以监控一个投票是单调的,意味着如果S ⊂ T,那么如果S对于B是绝对多数投票的,那么T也是。同时能够忽视一个模糊投票人更多的模糊投票。

​ 2/3-GHOST 函数g(S) 采用一组投票S,并且返回最高块序号的块B,所以S对于B是绝对多数投票的。如果没有这样的区块,那么它返回’nil’ 。(如果 f ≠ ⌊(n − 1)/3⌋,那么这是一个误称,并且我们相应地会改变函数的名字)

​ 注意,如果S是容忍的,那么我们可以计算g(S) ,通过从创世区块开始,迭代地寻找我们现在的绝对多数投票的区块的孩子,如果孩子块存在的话一定是唯一的。因为我们有如下:

引理 2.1. 设T是一组容忍投票。那么

  1. 之前的定义唯一地定义了g(T)

  2. 如果S ⊆ T 有g(S) ≠ nil, 那么g(S) ≤ g(T)

    1. 如果对于1 ≤ i ≤ n 有$S_i$ ⊆ T ,那么所有的非空g($S_i$)是链头为g(T)的单独链

​ 注意,我们可以很容易地把g(S) 更新到g(S∪{v}),通过检查是否任何g(S)的孩子现在是绝对多数投票的。引理3告诉我们,即使参与者见证了在给定投票轮次中的投票的不同子集,这个规则可以给他们不同的块,但是在该假设下,所有这样的块是在同一个链上的。

​ 接下来,我们定义一个可能性的概念,如果所有在投票T中的投票集合是容忍的,并且一些参与者认为一个子集S ⊆ T对块B是有绝对多数投票的,那么见证了其他子集S’ ⊆ T的所有参与者仍然见证了集合S对于块B是可能有绝对多数投票的。我们需要一个定义来扩展到非容忍的集合。

​ 如果至少(n + f + 1) / 2的投票人要么投给B之前的块,要么在S中是模糊的,那么我们说集合S是不可能对块B有绝对多数投票的。否则,集合S对B是可能有绝对多数投票的。

​ 注意,如果S是容忍的,仅当容忍的T ⊇ S并且T对于B有绝对多数投票,S对于B有绝对多数投票是可能的,这种情况可以这样得到:增加对B的投票,但是这些投票不在集合S中,并且有足够的投票者已经给S投票使得模糊投票人达到f 。

​ 如果S中有至少2f + 1个投票,那么我们说对于任何一个B的后继者,在集合S中是不可能有绝对多数投票的。并且对于B的每一个出现在S中投票的链上的后继者,S是不可能有绝对多数投票的。另外,假设给定S是容忍的,这当且仅当适用于B的任何可能的孩子,不容忍的T⊆S对于那个孩子有绝对多数投票。

​ 注意,一个非容忍的集合S可能同时有S的绝对多数投票,并且不可能在这些定义下有这样的一个绝对多数投票,当我们认为这样的集合是无论如何都不可能的。

引理 2.2. (i) 如果B’ ≥ B 并且S对于B是不可能有绝对多数投票的,那么S对于B’也是不可能有绝对多数投票的。

(ii) 如果S ⊆ T并且S对于B是不可能有绝对多数投票的,那么T对于B是不可能有绝对多数投票的。

(iii) 如果g(S) 存在,并且B ⍭ g(S) ,那么S对于B是不可能有绝对多数投票的。

3 GRANDPA协议

在本节中,我们给出了部分同步设置的最终小工具——GRANDPA协议。

​ 除了每轮投票的两名投票人之外,我们假设每轮都有一个指定为初选的参与者,并且所有参与者都同意投票人和初选。我们通常要么选择主要的伪随机选民,要么在选民集中进行轮换。

​ 我们分别设$V_{r,v}$和$C_{r,v}$为 $v$ 从当前轮次 r 收到的预投票和预提交。

​ 我们定义$E_{r,v}$为 $v$ 对在轮次 r 中将会被终结的块的估计,该估计值被在链头为g($V_{r,v}$)的链上的最终块给定的,$C_{r,r}$对于该区块有绝对多数投票是可能的。然后我们定义一个条件,该条件允许我们安全地决定在轮次 r 中,对于所有可能被终结的B有$E_{r,v}$ ≥ B:如果 $E_{r,v}$ < g($V_{r,v}$) ,或者 $C_{r,v}$ 对于任何g($V_{r,v}$) 的孩子是可能有绝对多数投票的,那么我们说$v$ 见证轮次 r 是完备化的。$E_{0,v}$ 是创世区块,假设从 r = 1 开始。

​ 换句话说,当我们的估计链$E_{r,v}$ 包含了在第r轮中可能完成的所有内容时,轮次r是完备的,这使得开始下一轮r + 1成为可能。

​ 我们有一个时间限制,那就是我们希望有足够的时间给每个人发送信息和传播消息。在一个轮次内,$E_{r,v}$ 具有绝对多数投票,即$E_{r,v}$ < g($V_{r,v}$) ,以及它不可能对某个给定块具有绝对多数投票都是单调的,因此完备性的性质也是单调的。因此,我们希望,如果任何人看到一个轮次是完备的,那么每个人都将在时间内看到这一点。在步骤之间留下2T的差距应该足够确保我们在继续之前得到所有诚实的投票。

​ 在轮次r 中,一个诚实的参与者$v$将会做下列事情:

  1. 当轮次 r - 1 是完备的,并且$v$ 已经在之前的轮次进行了投票,一个投票人 $v$ 可以从轮次 r > 1 开始。设 $t_{r,v}$ 是 $v$ 在轮次 r 开始的时间。

  2. 在时间$t_{r,v}$,如果$v$是该轮次首要的,并且$E_{r-1,v}$还没被终结,那么他们会广播$E_{r-1,v}$ 。如果他们已经终结了它,那么他们可以不受限制地广播$E_{r-1,v}$ (但是不一定需要这样做)。

  3. 如果$v$是轮次r的预投票的投票人,$v$至少会等到 $t_{r,v}$ + 2T 或者轮次r为完备的,然后广播一个预投票。除非我们从初始接收到区块B并且$g(V_{r-1,v})$ ≥ B > $E_{r-1,v}$ ,他们会对包含$E_{r-1,v}$的最优链的链头进行投票,在这种情况下,他们用包含区块B的最优链。

  4. 如果$v$是轮次r中预提交步骤中的投票人,那么他们会等到 $g(V_{r,v})$ ≥ $E_{r-1,v}$ ,并且达到下列条件之一:

    (i) 至少时间到 $t_{r,v}$ + 4T,

    (ii) 轮次r是完备的,或者

    (iii) $V_{r,v}$ 不可能对任何 $g(V_{r,v})$ 的孩子有绝对多数投票,

    然后为 $g(V_{r,v})$ 广播一个预提交( (iii) 是可选的,我们可以只需要(i)和(ii) )。

​ 注意,$C_{r,v}$ 和 $V_{r,v}$ 可能随着时间改变,$E_{r-1,v}$ 也会如此。$E_{r-1,v}$是$V_{r-1,v}$和$C_{r-1,v}$的一个函数,如果$v$见证更多来自之前轮次的投票,那么它也会随着时间改变。

3.1 总结

在轮次r中,如果在轮次r的预提交步骤后任何时候,我们有B = $g(C_{r,v})$ 是晚于最后终结块的和 $V_{r,v}$ 有绝对多数投票,然后我们终结区块B。我们也可以发送一个提交消息,由B和一组 区块≥ B的预提交(理想情况下,是B本身。如果可能的话,看下面是“最后一个区块哈希的替代方案”)。

​ 为了避免垃圾信息,我们只在没有收到任何有效的提交消息的情况下发送提交消息给B和它的后代,并且在广播之前,我们从[0,1]秒左右均匀随机选择一些时间。

​ 如果我们收到了轮次r的有效提交消息,那么它包含了足够的预提交来终结B本身,如果我们还没有完成终结区块B。所以只要我们通过了一轮r的预提交步骤,我们就会终结B。

4 分析

4.1 可负责的安全

第一件我们想展示的事情是同步安全,假设我们最多有f个拜占庭投票人。这是由这样的性质得出的:如果$v$ 认为第r轮是完备的,那么任何具有$E_{r,v}$ > B 的区块B都认为$C_{r,v} $或$V_{r,v}$ 中的任何一个都不可能拥有B的绝对多数投票,因此B没有在第r轮中被终结。这确保了在第r + 1轮中所有诚实的预投票和预提交都是针对包含在第r轮中可能已完成的块的链。通过归纳,这确保了我们不能在不同的链上终结块。为了证明安全可靠,我们需要把这个证据反过来证明相反的情况,当我们最终确定不同的区块时,就会有f +1拜占庭式的选民。如果我们让这个证明具有建设性,那么它就给了我们一个质疑程序,可以把责任归咎于这些选民。

定理 4.1. 如果协议最终确定发送了有效的提交消息,但不在同一条链上的任意两个块B、B’,那么至少有f + 1个拜占庭投票者在特定的投票中进行了投票。此外,还有一个同步过程来找到一些这样的f + 1拜占庭选民的集合X。
挑战过程如下:如果B和B’ 在同一轮中提交,那么它们的预提交的并集必须包含至少f个模棱两可,这样就完成了。否则,我们可以通过对称性假设B在第r轮中提交了,B’在轮次 r’ > r 中提交。至少有 n−f 选民在提交信息中 预提交≥B’ 或在第r轮中模棱两可,因此我们询问那些 预提交 ≥ B 的选民为什么他们这样做。

​ 开始 r’’ = r’,我们询问下列形式:

  • 为什么 $E_{r’’-1}$ < B 当你预投票或者预提交给 B’’ < B 在轮次 r’’ > r 中?

任何诚实的投票人应该能够回应这个问题,如同在下面的引理4.2中展示的。

​ 以下面的形式回应:

  • 一组预投票S给轮次 r’’-1,或者一组预提交给轮次 r’’-1,在任何一个情况下,S是不可能对于B有绝对多数投票的。

​ 任何诚实的投票人应该会进行回应。特别地,如果没有投票人回应,那么我们考虑所有的选民本该如何回应,但不是拜占庭式的,我们返回这组选民,以及任何模糊投票的人,这将总共至少是 n - f 的选民。如果有任何人进行了回应,那么如果 r’’ > r+1,我们可以在轮次r’’-1 中对至少 n-f 个投票人询问相同的问题。然而,我们注意到,如果有任何选民做出回应,那么我们不会惩罚不做出回应的人。

​ 如果我们在 r’’ = r’ 和 r’’ = r+1 之间的所有轮次中这样询问,并且获得有效回复。当轮次 r’’ = r+1 时一些选民反应,然后我们就可以在轮次r中得到一组预投票或者预提交S,这展示了在轮次r中,S不可能对B有一个绝对多数投票。

​ 如果S是一组预提交,那么如果我们采用并集S和在B的提交消息中预提交集合,然后轮次r的预提交的结果集对B有绝对多数投票,并且预提交不可能对B有一个绝对多数投票(//TODO: 很矛盾的话,不太明白)。这是可能的,如果集合是非容忍的,所以必须有至少f + 1 模糊的选民是拜占庭的。

​ 如果我们得到一组预投票S,对于B没有绝对多数投票,那么我们需要以下面形式对所有对B的预提交的投票人询问:

  • 对轮次r 哪个预投票是你见证的?

这些投票人对 B” ≥ B 进行了投票。肯定有 n - f 个这样的投票人,并且一个有效回复是一组轮次r的预投票T,T对于B”和B有绝对多数投票。

​ 如果在和以上条件相似情况下,任何人给予有效回复, S ∪ T将会有 f + 1 个模糊投票人。

​ 因为我们或者发现 f+1 个模糊投票人,或者 n-f > f+1 个投票人或是模糊的或是不能像诚实投票人那样对询问进行有效回复的。

引理 4.2. 一个诚实投票人可以回答询问的第一种类型。

​ 我们首先展示,如果在轮次r中一个预投票或者预提交被一个诚实投票人$v$投给了区块B”,那么在投票的时间我们有 B” ≥ $E_{r-1,v}$ 。通过步骤2或者3,应该为或者包含$E_{r-1,v }$或者包含 B’’’ > $E_{r-1,v}$ 的链的链头预投票。在两个情况下,我们都有B” ≥ $E_{r-1,v}$ 。通过步骤4,应该为$g(V_{r,v})$预提交但是$v$ 要等到 $g(V_{r,v})$ ≥ $E_{r-1,v}$,在预提交之前,所以同样我们有B” ≥ $E_{r-1,v}$ 。因此,如果有 B’’ < B,那么我们有 $E_{r-1,v}$ < B。

​ 我们接下来展示,如果在投票时,我们有 $E_{r-1,v}$ < B,那么我们可以有效地通过证明B不可能获得绝对多数投票来向询问反应。如果B并非与$g(V_{r,v})$在同一链,然后通过引理2.2(iii),如同希望的那样,$V_{r-1,v}$ 是不可能对B有绝对多数投票的。如果B和$g(V_{r,v})$ 在同一条链上,那么它和$E_{r-1,v}$也在同一条链上。在这种情况下,我们必须有B > $E_{r-1,v}$,因为$E_{r-1,v}$ < B。然而,可能使用轮次 r-1 是完备的,在与$g(V_{r,v})$同一条链上$C_{r-1,v}$ 是不可能对任何$E_{r-1,v}$的孩子有绝对多数投票的,特别是链(B)上$E_{r-1,v}$的孩子。根据引理2.2 (i),这意味着$C_{r-1,v}$ 对B没有绝对多数投票,这也是我们想要的。

​ 因此在投票时,我们有$V_{r-1,v}$和$C_{r-1,v}$都不可能对B有绝对多数投票。当前集$V_{r-1,v}$和$C_{r-1,v}$ 是投票时的集合的继承集合,所以通过引理2.2(ii),它仍然是不可能的。因此v可以有效响应。

​ 这足以证明定理4.1。注意,如果v看到轮次 r 为B提交的消息和 $E_{r’,v}$ < B,对于一些可完备化的轮次 r’ ≥ r,然后他们还应该能够开始挑战过程,至少成功地在某些轮次内识别 f + 1 个拜占庭选民。因此我们有:

推论 4.3. 如果在任何投票中最多有 f 个拜占庭选民,B在第 r 轮投票中被终结,一个诚实的参与者 v 看到 r’ ≥ r 是完备的,那么 $E_{r’,v}$ ≥ B。

4.2 活性

我们证明了该协议是死锁无关的,并且它在弱同步模型中快速地完成了新块的定位。在本节中,我们将假设每次投票最多有f < n/3 个拜占庭投票者,因此每轮的预投票和预提交集是宽容的。

​ 我们定义$V_{r,v,t}$ 是集合 $V_{r,v}$ 在时间 t 的集合,同样的,对于$C_{r,v,t}$ 和 $E_{r,v,t}$ 。

​ 我们首先证明,在我们所看到的投票中,一轮投票的完备性和完备性的估计值是单调的,在后一种情况下,估计值是单调递减的:

引理 4.4. 设v,v’为(可能相同)诚实的参与者,t,t’ 为时间,r为轮次。如果 $V_{r,v,t}$ ⊆ $V_{r,v’,t’}$ 和$C_{r,v,t}$ ⊆ $C_{r,v’,t’}$ ,在时间 t 时$v$ 见证了 r 可完备化,那么$E_{r,v’,t’}$ ≤ $E_{r,v,t}$和$v’$ 在 t 时刻见证 r 是可完备化的。

证明。由于在t 时刻 v 看到 r 可完备化的,要么$E_{r,v,}$ < $g(V_{r,v})$ 要求 (n + f + 1) / 2 > 2 f + 1票,要么$C_{r,v}$对于$g(V_{r,v})$的任何孩子有绝对多数投票是不可能的,要求2 f + 1票。在任何一种情况下,$V_{r,v,t}$和$C_{r,v,t}$ 都包含来自2f +1的选民的选票,所以对于$V_{r,v’,t’}$和$C_{r,v’,t’}$ 也是一样的。由引理2.1 (ii) ,$g(V_{r,v’,t’})$ ≥ $g(V_{r,v,t})$。由于$C_{r,v,t}$对于$g(V_{r,v,t})$的任何子元素都不可能具有绝对多数投票,因此根据引理2.2 (i &ii) ,$C_{r,v’,t’}$也是不可能的,所以 $E_{r,v’,t’}$ ≤ $g(V_{r,v,t})$ 和 v’ 都可以见证 r 在 t’ 时刻是完备的。但是现在$E_{r,v,t}$和$E_{r,v’,t’}$是链($g(V_{r,v,t})$)的最后区块,有可能$C_{r,v,t}$和$C_{r,v’,t’}$分别有绝对多数投票,当$C_{r,v’,t’}$对于$E_{r,v’,t’}$有绝对多数投票是可能的,那么$C_{r,v,t}$对于$E_{r,v’,t’}$有绝对多数投票也是可能的,根据引理2.2 (ii)和容忍的假设,所以$E_{r,v,t}$ ≤ $E_{r,v’,t’}$。

4.2.1 死锁自由

现在,我们可以展示异步传播网络模型的死锁自由度,即任何诚实的参与者发送或接收的消息最终被所有诚实的参与者接收。

命题 4.5. 假设我们在异步传播网络模型中,任何投票的 f 投票者都是拜占庭式的。这样协议就没有死锁了。

证明。我们需要表明,如果所有诚实的参与者都能获得一些选票,那么他们最终都会获得下一票。

​ 如果所有诚实的选民都能投票,那么他们就会投票,所有诚实的参与者都能看到他们的选票。我们需要处理两个可能会阻碍算法的条件。为了达到 r 轮的预投票,参与者可以在 r - 1 轮必须完成的条件下被推迟。为了达到预提交,一个投票者可能被 $g(V_{r,v})$ ≥ $E_{r-1,v }$ 的条件所阻碍。

​ 对于第一种情况,即预投票,设S为所有 r - 1 轮预投票的集合,是所有诚实的选民在r - 1轮预投票之前看到的预投票。由引理2.1可知,当投票者v’ 预提交时,他们对$g(V_{r-1,v})$ ≤ g(S)块进行处理。设T为诚实选民在第 r 轮投出的预提交集。然后对于任何块B > g(S)时,T不包含任何≥B的投票,因此T不可能拥有B的绝对多数投票,特别是T不可能拥有g(S)的任何子元素的绝对多数投票。

​ 现在考虑一个投票者$v$ ,根据我们的网络假设,有一个时间t,在此之前他们已经见证了S和T中的投票,考虑任意t’ ≥ t。此时我们有 $g(V_{r,v,t })$ ≥ g (S)。$C_{r,v’,t’}$不可能对于g (S)的任何孩子具有绝对多数投票,因此$E_{r-1,v,t’}$ ≤ g (S),无论这种不等式是否严格,我们为$v$见证轮次 r-1 在 t’ 时刻是完备的满足了两个条件之一。因此,如果所有诚实的选民都达到第r - 1轮的预提交投票,所有诚实的选民都达到第r轮的预提交投票。

​ 现在我们考虑第二种情况,即达到预提交。请注意,任何诚实的前选民在轮次 r 投票一个区块 $B_v$ ≥ $E_{r-1,v,t_v}$,其中$t_v$ 是他们投票的时间。现在考虑一下任何一个诚实的预投票投票人$v’$。在 t’ 时刻,他们已经收到了每个诚实的$v$ 选民在 $t_v$ 时刻和$v’$ 投票前收到的所有信息。根据推论4.3,$B_v$ ≥ $E_{r-1,v,t_v}$ ≥ $E_{r-1,v’,t’v}$ 。因为$V{r,v’,t’}$包含这些$B_v$,$g(V_{r,v’,t’})$ ≥$E_{r-1,v’,t’_v}$ 。因此,如果所有诚实的选民在第r轮预投票,最终所有诚实的选民在第r轮预提交。

​ 一个简单的归纳就完成了这个命题的证明。

4.2.2 弱同步活性

现在我们考虑弱同步传播网络模型。有一些全局稳定时间(GST)的概念,即一个诚实的参与者在时间 t 收到或发送的任何消息都将被所有诚实的参与者在时间max{t,GST} + T 收到。

​ 假设 $t_r$ 是第一次任何诚实的参与者进入第r轮的时间,即 $t_{r,v}$ 的最小值。

引理 4.6. 假设是弱同步传播网络模型,每个投票最多有 f 拜占庭的选民。如果 $t_r$ ≥ GST,我们有:

(i) $t_r$ ≤ $t_{r,v}$ ≤ $t_r$ + T ,对于任何诚实参与者 $v$,

(ii) 在 $t_r$ + 2T 之前没有诚实投票人进行预投票,

(iii) 任何诚实投票人最迟在 $t_{r,v}$ + 4T 进行预提交,

(iv) 对于任何诚实投票人$v$, $t_{r+1,v}$ ≤ $t_r$ + 6T。

证明。假设$v’$ 是第一个进入轮次 r 的诚实参与者,即 $t_{r,v’}$ = $t_r$。通过我们的网络假设,所有$v’$接收到的消息在结束之前,被所有诚实的参与者在时刻$t_r$ + T 之前收到。特别是在时间$t_r$,$v’$ 见证前几轮都是可完备化的,因此根据推论4.3,那么其他诚实参与者在时间$t_r$+ T 也见证了。也因为r’ < r,有时$s_r’$ ≤ $t_r$,$g(V_{r’,v’,s’r})$ ≥ $E{r’,v’,s’r}$ ,再由引理4,对于所有诚实的v,$g(V{r’,v,t_r+T})$ ≥ $E_{r’,v,t_r+T}$ 。看看投票的条件,这意味着任何诚实的选民不需要等待在任何轮 r’ ≤ r 投票。因此,他们投出任何剩余的选票,并在时间 $t_r$ + T 进入轮r。这证明了(i)。

​ 对于 (ii),请注意,一个诚实的选民不会等到时间 $t_{r,v}$ + 2T ≥ $t_r$ + 2T的唯一原因是n - f选民已经预投票了。但是由于n - f的一些投票是诚实的,这在 $t_r$ + 2T之前是不可能的。

​ 现在一个诚实的投票人v’’ 在时间 $t_{r,v’’}$ + 2T ≤ $t_r$ + 3T 时进行预投票,根据我们的网络假设,所有诚实的参与者在时间$t_r$ +4T时都得到了这个选票。一个诚实的预提交v的投票人也收到了v’’ 在他们预投票之前收到的所有消息。因此他们预投票的区块有 $B_v’’$ ≥ $E_{r-1,v”}$ ≥ $E_{r-1,v,t_r+4T}$ ,因为每一个诚实投票人$v’’$都成立该条件,所以 $g(V_{r,v,t_r+4T})$ ≥ $E_{r-1,v,t_r+4T}$ 。因此如同在(iii)在展示的那样,他们会在时刻$t_{r,v}$ + 4T之前进行预提交。

​ 通过网络假设,一个诚实的投票者 v’ 的预提交将被所有诚实的参与者 v 接收到,时间为 $t_{r,v’}$ + 5T ≤ $t_r$ + 6T。因为当他们在这个时候预提交,v也会收到所有的v传播的预投票,他们的投票 $B_v’$ 将会有 $B_v’$ = $g(V_{r,v’})$ ≤ $g(V_{r,v,t_r+6T})$ 。因此,$C(V_{r,v,t_r+6T})$ 包含来自n - f 投票者v’和 $B_v’$ ≤ $g(V_{r,v,t_r +6T})$的预提交,因此,$C(V_{r,v,t_r+6T})$ 不可能对$g(V_{r,v,t_r+6T})$的任何子元素拥有绝对多数的投票。因此,v认为第r轮在 $t_r$ + 6T时刻是完备的。由于他们已经预投票,如果他们是选民,他们将最迟$t_t$ + 6T转到r + 1轮。这是(iv)。

引理 4.7. 假设 $t_r$ ≥ GST 且每一票最多为 f 个拜占庭选民。设$H_r$ 为第r轮诚实选民所投的预投票。那么

(a) 任何诚实投票人给块≥$g(H_r)$ 进行预提交,

(b) 在时刻$t_r$ + 6T 之前,每一个诚实参与人终结$g(H_r)$ 。

证明。对于(a),我们根据(i)-(iii)中我们等待预提交的条件进行分类。

​ 对于(i),所有诚实投票人在时刻$t_r$ + 3T 之前在轮次r中进行预投票。所以任何一个诚实的投票人v在时间$t_{r,v}$ + 4T ≥ $t_r$ + 4T 或之前预提交,并且已经在$H_r$中获得了所有的选票,通过引理2.1,预提交到一个≥$g(H_r)$的块。

​ 对于(ii),我们认为,没有一个诚实的选民首先提交一个 <$g(H_r )$块。一旦处理了其他情况,结果就会很容易地归纳出来。假设没有诚实的选民预提交过到目前为止<$g(H_r )$的块,并且v选民因(ii)提前投票。

​ 请注意,由于我们假设到目前为止所有诚实的选民的预提交都是≥$g(H_r )$,因此$C_{r,v}$ 有可能获得$g(H_r )$的绝对多数投票。为了使投票人v具有条件(ii),即为了使轮次r是完备的,它必须是这样的情况,要么是$C_{r,v}$不可能对 $g(V_{r,v})$有绝对多数的投票,要么是$C_{r,v}$是不可能对$g(V_{r,v})$的任何子元素有绝对多数投票的。由引理2.2可知,不能令 $g(V_{r,v})$ < $g(H_r )$ 。但是根据引理2.1,它们在同一个链上,所以 $g(V_{r,v})$ ≥ $g(H_r )$,因为这是块v的预提交,我们在情况(ii)中完成。

​ 对于(iii),设v为有问题的投票人。注意,由于n - f 诚实选民预投票≥g(H r), $V_{r,v}$是有可能对$g(H_r )$有绝对多数投票的。由引理2.1可知,$g(V_{r,v})$与$g(H_r )$在同一条链上。对于(iii), $V_{r,v}$对于$g(V_{r,v})$的任何子元素都不可能有绝对多数投票。如果有$g(V_{r,v})$ < $g(H_r )$ ,根据引理2.2,这意味着对于$V_{r,v}$也不可能对$g(H_r )$有绝对多数投票。所以$g(V_{r,v})$ ≥ $g(H_r )$是满足要求的。

​ 对于(b),结合(a)和引理4.6 (iii),我们得到任何诚实的投票者v在时间 $t_{r,v}$ +4T之前预提交≥$g(H_r )$。根据我们的网络假设,所有诚实的参与者在时间$t_r$ +6T之前收到这些预提交,因此,如果他们还没有这样做,就终结$g(H_r )$。

引理 4.8. 假设$t_r$ ≥ GST,第一轮r的主要 v 是诚实的,没有选票超过 f 个拜占庭的选民。设B = $E_{r-1,v,t_{v,r}}$ 为v广播的块,如果它不是最终的。然后每个诚实的选前者都为最佳链进行预投票,包括B和所有诚实的选前者在时间 $t_r$ + 6T时确定B。

证明。根据引理4.6和我们的网络假设,没有诚实的投票者在时间$t_r$ +2T≥ $t_{r,v }$ +2T 之前进行预投票,所以在这个时候,他们将见证v在 $t_{r,v }$ 和B块见证的所有预投票和预提交,如果v广播它的话。根据引理4.4,任何诚实的投票者v’ 都有$E_{r-1,v’}$≤ B ≤ $g(V{r-1,v})$ 。

​ 所以如果关键人广播B,那么v’ 就会预投票包括B在内的最佳链。如果关键人没有广播B,那么他们会终结它。根据推论4.3,一定有$E_{r-1,v’ }$ ≥ B,所以$E_{r-1,v’ }$ = B,所以在这种情况下v’ 也为包括B在内的最佳链进行预投票。

​ 由于所有诚实的选民提前投票≥B,$g(H_r )$ ≥ B,由引理4.7可知,所有诚实的参与者在 $t_r$ + 6T时终结B。

引理 4.9. 假设$t_r$ ≥ GST + T,且轮次 r 的关键人为诚实的。让B成为最后一个以轮次< r 终结的区块(即使诚实的参与者直到回合结束后才终结它)。如果在第 r 轮投票前所有诚实的投票者都同意包含B的最佳链包括B的同一子链B’,那么他们都在 $t_r$ + 6T之前终结了B的某个子链。

证明。根据推论4.3,任何诚实的参与者都见证在第一轮r中,$E_{r-1 }$ ≥ B。设v为轮r的关键人, B’’ = $E_{r-1,v,t_{r,v}}$ 。如果B’’ > B,然后由引理4.8,所有诚实的参与者完成B’’在时间$t_r$ + 6T 之前,这意味着他们终结了B的孩子。如果B’’ = B,然后由引理4.7,所有诚实的选民给包括B的最佳链预投票。通过假设这些链包括B’ 和 $g(H_r)$ ≥ B。根据引理4.7,这意味着B’ 在$t_r$ + 6T 之前被终结。

4.2.3 最近有效性

引理 4.10. 假设 $t_r$ ≥ GST,轮次 r 的关键人是诚实的,所有的投票最多为 f 个拜占庭的选民。设 B是一个拥有小于 f + 1 个诚实投票人的块,在第 r 轮诚实的预选者认为在他们预投票时 B的祖先处于最佳链中。然后,要么所有诚实的参与者在时间 $t_r$ + 6T之前终结 B,要么没有诚实的参与者有 $g(V_{r, v})$ ≥ B或 $E_{r,v}$ ≥ B。

证明。设v’ 是轮次 r 的关键人,设B’ = $E_{r-1,v’,t_{r,v’}}$。如果B’ ≥ B,则根据引理4.8,所有诚实的参与者在 $t_r$ + 6T 时终结B。如果 B’ < B,则由引理4.8,最诚实的选民预先投票≥B。在这种情况下,小于 2f + 1 ≤ (n + f + 1)/2 的选民投票 ≥ B 或模棱两可,所以没有诚实的参与者有$g(V_{r, v})$ ≥ B。

推论 4.11. 对于 t - 6T > t’ ≥ GST,假设一个诚实的参与者在时间 t 终结 B,但没有诚实的选民视 B 在最佳链内,该最佳链包含一些在时刻 t’ 和 t 之间的 B 的祖先 ,那么至少连续 ( t−t’ ) / 6T − 1轮有拜占庭关键人。

5 实践

5.1 以异步安全的方式在链上更改投票者集合

5.1.1 异步安全的方式更改投票者集合

假设我们有一个链上的协议,决定我们需要一组不同的选民。一旦所有人都已终结了块,他们知道,我们需要改变投票人集合。该协议能够处理从一些轮次 r 中改变选民。链的主要困难在于不知道当前回合数,即使我们有一个块,指导我们在一轮r中改变选民集合,我们可能只会在r回合结束后才会终结区块。因此,我们不会利用从一轮到下一轮改变集合的能力。

​ 块B可以包含一个指令,我们应该把某个整型m ≥ 0块之后的投票者集改为另一个集合。如果我们的最佳预投票链包含这样一个块B,那么我们在B之后的预投票不会超过m个块,即使我们的最佳链更长。因此,如果当前选民集有n个诚实的选民,他们只会在这样一个B后确定m个区块。

​ 当某个B’ 块,即B结束后的第m块,则新的选民集在第1轮重新开始,此时$E_0$ = B’ 。选票将需要以某种方式包含指示选民集的附加元数据。

5.1.2 暂停后更改选民集的不安全后备方案

在极端情况下,我们可能需要处理三分之一的选民离线的问题。没有一种异步安全的方法可以做到这一点。它还打破了现有选民群体关于未来选民群体应该是谁的签名声明的链。这意味着我们可能很容易被拜占庭式的参与者切断联系。然而,如果我们处于一个状态,许多选民离线,但网络没有分区,然后我们想要一种方法,就一组新选民达成一致,以重新启动终结小工具。

​ 每隔100块左右,我们应该在链上放置一个有效的提交消息。诚实的区块生产者应该把最近的消息放在链上,只要有一个比100个区块更近的区块。然后,如果一名参与者发现他们最佳的投票链在1000个区块内都没有收到这样的信息,并且不知道最近还有更多的区块正在被终结,那么他们就会设置一个新的选民集,由自链上最后一个提交消息以来的第900个块决定。

​ 选择投票者的协议应该要求这些投票者最近在链上签署的消息,这样一来,很可能只有很少一部分投票者是离线的。

​ 我们应该考虑手动批准这个新集合所同意的最终结果,以缓解上面的安全问题。但是,在WW3或新链初始化失败的情况下,这仍然提供了一个在新链上达成一致的方法。

​ 如果我们不想将提交消息放在链上,那么我们可以选择执行以下操作。每个块生成器在其块中放入他们认为终结的最高块号。

​ 那么任何一个参与者见证是否有一个n可以这样:

​ (i)他们的最佳链长度至少为 n+100

​ (ii)n - 100至n块在其最佳链中终结的块高度的中位数最多为n - 1050,并且

​ (iii)n是满足(i)和(ii)的最小值

那么,他们最好切换到由块n给定的选民集合。如果在高度n的相同区块是在每个人最佳链上,对于许多块生产机制,可以证明在给定(i)条件下有高概率发生,那么每个人都会最终同意我们应该切换到由该区块给定的选民集。如果任何最佳链的100块是由诚实的同步区块生产人生产的,那么只有当GRANDPA在生产1000块的时间里没有终结任何一块区块时,这才会发生。

5.2 最后一个块哈希的替代方法

在最佳链上投票给最后一个区块的危险在于,可能没有其他人会见证并处理下一个区块。最好还能充分利用BLS 多签/聚合,它允许对许多消息/签名者进行单个签名,而不是根据签名的不同消息的数量按时间比例进行检查。

​ 为了绕过第一轮,最好是在未终结的链上投3/4给一个区块(之后的轮次),而不是投第一个。

​ 但第二个建议是,或许我们应该在链中包含几个最新区块的签名。我们可以包括最后的2个或3个。我们也可以这样做,例如,块号的最后2次幂的2的倍数从最后一个终结的块,这会记录未终结的链长度的消息,但应该有许多共同的块。

​ 当我们面对一个包含许多块的投票时,我们应该把它们解释为我们见证的最后一块。然后,当它被见证时,我们需要能够更新投票到一个稍后的块。这保持了绝对多数的单调性,因为不可能在一段时间内拥有绝对多数。

​ 这并不重要,如果一些投票是给一个不存在的区块,而每个人都会忽略这部分的投票。但是,如果把选票投给那些被验证了但却没有连在链上的区块,那就是含糊其辞,而且需要被惩罚。我们需要计算这样的选票作为投票中每一个链的拥有票(有人可能会将它们解释为其中任何一个)。

​ 然后,如果我们需要对提交消息或查询响应的投票进行BLS聚合,则可以使用任何为B的投票,不一定是为链头投票。这将减少块哈希签名的数量,在乐观情况下减少到1。

5.3 块产生规则

如果我们采用这一规则,即块生产者应该建立在最佳链上,包括最后终结的块,那么如果我们不终结另一个块,它最终将包括最后终结的块之外的一些前缀,因此协议是由引理4.10决定的。

​ 但问题是,如果协议比区块生产慢得多,那么我们可能会在最后终结的区块的短链上进行预投票,然后最佳链不包括该区块,我们就会构建一条最终从未终结的长链。这个问题可以通过建立在$E_{r-1}$或 $E_r $上来解决。但是如果我们这样做,并且这些变化非常快,那么我们可能永远不会在最佳链上达成一致。

​ 因此,对于块生产者,我们有两个可能的链选择规则:

  1. 建立在最佳链,该链包括最后终结块B。
  2. 建立在包括{$E_r$, $E_{r-1}$, B}任何一个是最后的并且≥B的最佳链。

​ 与出块相比,如果终结速度快,则规则1更好;如果出块快得多,则规则2更好。我们也可以考虑采用规则1这样的混合规则,除非我们看到协议被卡住或变慢,然后我们切换到规则2。

6 为什么?

6.1 为什么我们要在一轮结束时等待,有时还要在预提交之前等待?

如果网络表现不佳,那么这些步骤可能涉及到任意长时间的等待。当网络表现良好时(在我们的模型中GST之后),我们不应该等待。事实上,不等待获得2/3的选票是没有意义的,因为没有他们,我们无法完成任何事情。但如果传播网络不完善,一些信息永远不会到达,那么我们可能需要实施选民问其他选民从前几轮投票类似的挑战程序,以避免僵局。

​ 作为交换,我们得到了一个属性,那就是我们不需要关注前一轮的投票,就可以在这一轮投出正确的一票。如果不等待,我们可能会处于这样一种情况:我们可能在某轮r中终结了某个块,但是网络在许多轮中变得不可靠,并且按时获得的投票很少,在这种情况下,我们需要记住来自轮次 r 的投票,以便稍后终结块。

6.2 为什么要进行初选?

我们需要的只是初选的活性。我们需要某种形式的协调,以击败不断分裂选票的攻击。这种攻击背后的想法是,如果我们处于这样一种情况,即几乎2/3的选民投票支持某件事,其余的选民投票支持另一件事,那么拜占庭式的选民就可以控制我们看到的超级多数。如果他们能够谨慎地把握时机,他们或许能够在下一次投票中平分秋色。如果没有初选,他们可以这样做预投票,在B区块获得绝对多数,然后分割预投票,所以直到很久之后我们都不可能在B区块获得绝对多数。如果B不是最佳区块,但B’ 有相同的区块号码,他们可以阻止任何一个这样的终结,即使拜占庭人的(未知)比例很小。

​ 当网络表现良好时,诚实的初选可以通过决定我们应该在多大程度上达成一致来击败这种攻击。我们也可以用一枚普通硬币来做同样的事情,人们会预投票选出含有$E_{r-1}$ 或$g(V_{r-1,v})$ 的最佳链这取决于普通硬币。对于链上的投票,我们可以使用概率块生产机制的终结——如果我们不终结一块,总是建立在包含最后一个终结块的最佳链上,那么不仅最佳链最终会收敛,而且如果一个区块在最佳链的链头之后和有正概率,它最终会在最佳链被每个人都看到。

​ 在我们的设置中,使用初选是最简单的选择。

7 异步终结小工具问题

在这里,我们给出了一个扩展的[3]结果,显示了不可能有一个异步和确定性的小工具协议,并给出了一个异步协议,使用一个共同的硬币原语。

7.1 确定性协议的不可能性

7.2 使用通用币的1/5 BFT终结小工具

8 GRANDPA的优化版本

参考文献

[1] Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on bft consensus. arXiv preprint arXiv:1807.04938, 2018. URL https://arxiv.org/abs/1807.04938.
[2] Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437, 2017. URL https://arxi v.org/abs/1710.09437.
[3] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374–382, 1985. URL https://groups.csail. mit.edu/tds/papers/Lynch/jacm85.pdf.
[4] Vlad Zamfir. Casper the friendly ghost: A “correct-by-construction” blockchain consensus protocol. 2017. URL https://githu b.com/ethereum/research/blob/master/papers/CasperTFG/CasperTFG.pdf.

本文标题:拜占庭终结工具

文章作者:木南

发布时间:2019年09月30日 - 09:09

最后更新:2019年10月09日 - 15:10

原始链接:http://munan.tech/2019/09/30/拜占庭终结工具/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

点击下方打赏按钮,获得支付宝二维码