当前位置: 主页 > 比特币 >

V神论文:99%容错共识指南



  特别感谢Emin Gun Sirer的审阅。

  在很长一段时间里,我们一直认为在同步网络中,50%容错共识是可以实现的。所谓同步网络,是指其中任一诚实节点广播的消息都能保证在某个已知时间段内被所有其他诚实节点所接收(如果攻击者的占比超过50%,那么他们可以执行“51%攻击”,这是此类算法的通病)。

  很长时间内,我们一直认为如果你想放宽同步假设,并提出一个“在异步条件下保证安全性”的算法,那么其最大可实现的容错率将下降为33%(PBFT,Casper FFG等都属于这个类别)。

  但是你是否知道,如果你添加更多的假设(具体来说,你需要观察者的存在,即不积极参与共识过程,但却关心最终输出、同时积极观察共识,而不仅仅是在事后下载其输出的用户),你可以将容错率一直提高到99%?

  事实上,在很久以前就已经有人发现了这一结论。Leslie Lamport于1982年发表的着名的论文“拜占庭将军问题(The Byzantine Generals Problem)1”对此算法进行了描述。以下是我尝试以简化形式来对该算法进行描述与重构。

  假设存在N个共识参与节点,并且每个人都提前同意这些节点的身份(取决于具体场景,他们可能是从可信方当中挑选出来的,或者,如果需要更高的去中心化程度,那么可以使用工作量证明或者权益证明方案进行挑选)。

  我们将这些节点标记为0 .... N-1。此外,我们假设网络延迟加上时钟差异的界限为D(例如,D = 8秒)。每个节点都能够在时间T发布一个值(恶意节点当然可以提前或晚于T来提议这些值)。

  所有节点等待(N-1) * D秒,同时运行以下过程:我们不妨将x: i定义为“由节点i签名的值x”,将x: i: j定义为“由i 和j 同时签署的值x”,以此类推。在第一阶段发布的提案的形式为v:i,其中v,i代表特定的值及节点i,同时包含提出该提案的节点的签名。

  如果验证者i 收到消息v:i [1]:...:i [k],其中i [1] ... i [k]是已经(按序)签署消息的索引列表(只有v本身时,k = 0,而v:i为k = 1),然后验证者将会检查(i)时间是否小于T k * D,以及(ii)他们是否还没有一条看到包含v的有效消息。如果两个检查全部通过,他们将发布v:i [1]:...:i [k]:i。

  在T (N-1) * D时,节点停止监听。这时,我们可以保证所有诚实节点都能够“有效地看到”同一组值。

节点1(红色)是恶意的,节点0和2(灰色)是诚实的。一开始,两个诚实的节点提出他们的提案y和x,其后攻击者提议w和z。w按时到达节点0但未到达节点2,并且z没有按时到达这两个节点。在时间T D,节点0和2重新广播所有他们已经看到但尚未广播的值,并在其上加入自己的签名(节点0签署了x和w,节点2签署了y)。两个诚实的节点都看到{x,y,w}。

  如果这个问题需要节点从中选择一个值,那么他们可以使用“choice”函数来从他们看到的值当中选出一个(例如,他们采用具有最小哈希的值),然后节点可以就此值达成一致。

  现在,我们来探讨一下为什么这种方式能够奏效。我们需要证明的是,如果一个诚实的节点已经(有效地)看到某个特定的值,那么其他诚实的节点也看到了这个值(如果我们证明了这一点,那么我们知道所有诚实的节点都看到了相同的一组值。所以,如果所有诚实节点都运行相同的choice函数,他们会选择相同的值)。

  假设任一诚实节点接收到一条他们认为有效的消息v:i [1]:...:i [k](即这条消息在时间T k * D之前到达)。假设x是一个其他诚实节点的索引。x要么是{i [1] ... i [k]}的一部分,要么不是。

  • 在第一种情况下(比如对于这条消息,x = i [j]),我们知道诚实节点x已经广播了这条消息,并且他们这样做是为了响应他们在时间T (j-1) * D之前收到的带有j-1个签名的消息,因此他们在那时广播他们的消息。所以,在时间T j * D之前,所有诚实节点必然已经接收到该消息。

  • 在第二种情况下,由于诚实节点在时间T k * D之前看到消息,那么他们将广播附有他们签名的消息,并保证每个人(包括x)在时间T (k 1) 之前看到这条信息。

  请注意,这一算法使用添加自己签名这一行为来作为消息超时的“碰撞”,并且这种能力可以保证如果一个诚实的节点按时看到消息,他们可以确保其他人同样按时看到消息,因为“准时”的定义通过增加每一个签名的网络延迟得到增强。

  在一个节点诚实的情况下,我们是否可以保证被动观察者(即只关注结果而不参与共识的节点)也可以看到结果,即使我们要求他们一直在观察整个过程?随着这一方案的编写,里面存在一个问题。假设某个指挥者和k个(恶意的)验证者的子集捏造一条消息v:i [1]:....:i [k],并在时间T k * D之前将其直接广播给某些“受害者”。受害者认为这条消息是“准时”的,但是当他们重新广播这条信息时,这条信息只在时间T k * D之后到达所有诚实的共识参与节点,因此所有诚实的共识参与节点都将拒绝这条信息。

但我们可以填补这个漏洞。我们要求D是网络延迟加上时钟差异的两倍。然后我们对观察者实行不同的超时标准:观察者在时间T (k - 0.5) * D之前接受v:i [1]:....:i [k]。现在,假设观察者看到一条消息接受它。他们将能够在时间T k * D之前将其广播到某个诚实的节点,并且诚实节点将发出附有其签名的消息,该消息将在时间T (k 0.5) * D之前到达所有其他观察者,其中,T (k 0.5) * D是信息附有k 1个签名的超时时限。

但我们可以填补这个漏洞。我们要求D是网络延迟加上时钟差异的两倍。然后我们对观察者实行不同的超时标准:观察者在时间T (k - 0.5) * D之前接受v:i [1]:....:i [k]。

  现在,假设观察者看到一条消息接受它。他们将能够在时间T k * D之前将其广播到某个诚实的节点,并且诚实节点将发出附有其签名的消息,该消息将在时间T (k 0.5) * D之前到达所有其他观察者,其中,T (k 0.5) * D是信息附有k 1个签名的超时时限。

与其它共识算法整合

  理论上,上述内容可以用作独立的共识算法,甚至可以用于运行权益证明区块链。共识的第N 1轮验证者集合本身可以在共识的第N轮中决定(例如,每轮共识也可以接受“抵押”和“提现”交易,这些交易是否被接受以及是否被正确地签署将影响验证者是否能够进入下一轮)。这里面还需要添加的主要附加成分是决定谁能成为区块提议者的机制(例如,每轮可以有一个指定的提议者)。

  这个共识算法还可以被修改为用于工作量证明区块链。比如允许参与共识的节点通过在签名的同时基于其公钥发布工作量证明解决方案来实时“声明自己”。

  但是,这一方案过于依赖同步假设,因此我们希望能够在不需要超过33%或者50%容错的情况下摆脱这一依赖。有一种方法可以实现这一目标。假设我们有其它共识算法(例如,PBFT,Casper FFG,基于链的PoS),其输出可以被偶尔在线的观察者看到(我们称之为阈值依赖型共识算法,与之相反,上述算法我们成为延迟依赖型共识算法)。

  假设阈值依赖型共识算法以不断地将新区块“最终”到链上的模式运行(即每个最终值指向某个先前的最终值,以该最终值为“父值”。如果存在一系列指针A - > ... - > B,我们称A为B的后代)。

  我们可以将延迟依赖型算法整合到这个结构中,让总是在线的观察者能够在检查点上获得一种“强大的最终性”,其容错率达到95%(你可以通过增加更多验证者以及将该过程的时间延长以使其无限接近100%)。

  每一次当时间达到4096秒的倍数时,我们将运行延迟依赖型算法,选择512个随机节点参与到算法当中。一个有效的提案是由阈值依赖型算法最终敲定的值所组成的任意有效链。如果某个节点在时间T k * D(D = 8秒)之前看到某个附有k个签名的最终值,那么他将把这条链接纳进其已知链的集合中,并在这个值后面自己的签名,然后重新广播出去。观察者的阈值跟原来一样,依旧是T (k-0.5) * D。

  最后,“choice”函数的用法很简单:

  •如果某个最终值不是已经在上一轮达成一致的最终值的后代,那么其将被忽略。

  •忽略无效的最终值

  •如果要在两个有效的最终值之间进行选择,则选择哈希值较小的最终值。

  如果有5%的验证者是诚实的,那么512个随机选择的节点都不诚实的概率只有大约一万亿分之一。因此,只要网络延迟加上时钟差异小于D / 2,上述算法就能发挥作用。即使阈值依赖型算法的容错遭到破坏,导致多个冲突的最终值出现,也不会造成影响。

  如果阈值依赖型共识算法的容错范围(通常为50%或67%节点是诚实的),那么阈值依赖型共识算法要么不再最终化任何新的检查点,或者它将最终化彼此兼容的新检查点(例如,一系列检查点,其中每个检查点指向前一个作为父项)。

  因此,即使网络延迟超过D / 2(或者甚至为D),从而导致参与延迟依赖型算法的节点也不同意他们所接受的值,他们所接受的值仍然会被保证是同一条链的一部分,因此,这实际上等同于节点同意这些值。一旦在未来的轮次里,延迟恢复正常,那么延迟依赖型共识也将恢复“同步”。

  如果阈值依赖型和延迟依赖型共识算法的假设同时(或在连续轮次中)遭到破坏,则这个算法将会崩溃。例如,假设在某一轮中,阈值依赖型共识最终敲定Z - > Y - > X,并且延迟依赖型共识对Y和X的排序有争议。

  此外,在下一轮中,阈值依赖型共识最终敲定W为X的后代,而X不是Y的后代;在延迟依赖型共识中,认同Y的节点不会接受W,但是认同X的节点会接受W。然而,这是不可避免的。

  拜占庭容错理论已经昭示了,超过1/3的容错对于在同步状况下保证安全性的共识来说是不可能实现的。同理,在同步状况下,假设观察者离线也不可能实现超过1/2容错。

  翻译:喏呗尔

  原文作者:VitalikButerin

  原文链接:

  https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html

  参考文献

  [1]论文原文链接:

  https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html 【文章版权归原作者所有,其内容与观点不代表Unitimes立场。转载文章仅为传播更有价值的信息,合作或授权联系请发邮件至 cONTact@unitimes.media或添加微信unitimes2017】

全球金融科技知识交互平台

NITIMES

  网址 : unitimes.io

  新浪微博:@Unitimes

  等你点赞转发都等出蜘蛛网了

【版权声明】该文章由本站整理于网络的相关信息,本站不拥有所有权,不承担相关法律责任。


相关资讯

站长统计