V神详细描述：怎样完成99%的容错机制共识_跨链

V神详细描述：怎样完成99%的容错机制共识

较长一段时间至今，大家一直听闻在同歩互联网中,完成50%容错机制的共识是有可能的。在同歩互联网中，一切可靠节点广播节目的消息都能够确保在某一已经知道时间范围内被全部其他可靠节点接受。

假如网络攻击超出50%，她们就可以实行“51%进攻”，针对区块链技术高度一致种类的一切优化算法都是有很有可能发生相近的状况。

大家也一直听过那样的叫法：假如你要释放压力同歩假设，而且有着一种“多线程下安全性”的优化算法，较大 可做到的容错性可降低到33% (PBFT、Casper FFG等都归属于该类)。

殊不知，假如加上大量假设(从总体上，你不但必须观测者来关心这些不积极开展共识但关注其輸出的客户，还要积极地关心共识，而不仅是在結果发生后免费下载其輸出)，那样能够把容错性一路提升 到99%吗?

实际上，这一点 早就众人皆知。阿什莉·兰伯特（Leslie Lamport）1982年在知名的谈起“拜占庭一般难题”的毕业论文中包括了对优化算法的叙述。下边我将试着用简单化的方式再次来叙述和描述这一优化算法。

假设有N个参加共识的节点，每一个人都提早愿意这种节点意味着谁(依据前后文，他们能够由可靠方挑选，或是假如必须更强的区块链技术水平，能够根据一些工作单位证明或利益关系开展证实)。

大家把这种节点标识为0…N-1。此外，还假设网络延时和数字时钟差别上有一个已经知道的限定D。（比如，D = 8秒)。每一个节点都是有工作能力在T時刻公布值(故意节点当然可以先于T或晚于T地公布值)。

全部节点等候(N - 1)∙D秒，运作以下过程。界定x: i为“节点i签名的值x”，x: i: j为“节点i签名的值x，而且x与j一起签名”，这些。在第一阶段发布的提议将选用v的方式: i的方式为一些v和i，在其中包含明确提出该提议的节点的签名。

假如一个认证器i接到一些消息v: i:…: i[k]， 在其中 i:…:i[k]是早已按序对消息开展了签名的数据库索引目录（仅仅v自身会算是k = 0,而v:i则为k = 1),那麼认证程序流程查验(i)的時间将低于T k∙D,另外她们并未见到包括以下几点的合理消息;假如二项查验均根据了，则会公布v: i:…: i[k]: i。

在T (N - 1)∙D时，节点终止监视。这时，就可以确保全部的可靠节点都“合理地看到了”同样的一组值。

假如难题规定挑选一个值，则能够应用一些“挑选”涵数从她们见到的值中挑选一个值（比如选用哈希值最少的值）。随后节点能够就该值达到共识。

如今，使我们来研究一下为何这类方法合理。大家必须证实的是,假如一个诚信节点（合理地）看到了特殊的值,随后其他的诚信节点也见到该值(如果我们证实了这一点,那麼我们知道全部诚信节点都看到了同一组值,因而假如全部诚信节点都运作同样的挑选作用,她们会挑选同样的值)。

假设一切诚信节点接到一条消息v: i:…i[k]，她们觉得是合理的。在時间T k∙D以前抵达)，假设x是另一个诚信节点的数据库索引。x要不是i的一部分:…要不并不是。

在第一种状况下(针对此消息，x=i[j]),我们知道诚信节点x早已广播节目该消息,她们那样做是为了更好地回应她们在時间T （j - 1）·D以前接到的含有j-1签名的消息。这时她们广播节目了她们的消息,那麼全部诚信节点一定都是会在時间T j∙D前接到消息。

在第二种状况下，因为诚信节点在時间T k∙D以前见到消息，那麼他们便会用自身的签名散播消息，并确保包含x以内的任何人都是会在時间T (k 1)∙D以前见到它。

留意，该优化算法应用加上自身签名的个人行为做为消息请求超时的一种“撞击”。恰好是这类工作能力确保了一个诚信的节点假如立即看到了消息，那他们还可以保证 其他全部节点也可以立即见到消息，由于“按时”的界定提升的時间超出了每加上一个签名的网络延时。

在一个节点是诚信的状况下，大家可否确保处于被动的观测者(例如关注結果的非共识参加节点)还可以见到結果。

依照方案，存有一个难题。假设一个指挥者和k(故意)认证器的某一非空子集转化成一条消息v: i:…i[k]，而且在T k∙D前广播节目给一些受害人，受害人觉得消息是“按时”,但当她们分享时,消息总是在T k∙D以后做到全部的早已协商一致的诚信节点,而全部协商一致的诚信节点可能回绝它。

但我们可以塞住这一洞，明确提出一个新的管束：规定D在二倍的网络延时再加上时差。随后大家给观测者一个不一样的请求超时:观测者接纳v: i:…i[k]务必在 T (k - 0.5)∙D以前。

如今，假设观测者见到一条消息并接纳了它。她们可以在時间T k∙D以前将其广播节目到一个诚信节点,而且诚信节点将公布含有签名的消息,该消息将在T D (k 0.5)以前抵达全部其他观测者，另外含有k 一个签名的消息可能请求超时。

改善其他共识优化算法

理论上讲，以上优化算法能够做为单独的共识优化算法应用，乃至能够用以运作利益证实的区块链技术。

第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的阀值。

最终应用的“挑选”涵数非常简单:

忽视并不是在前一轮中早已商谈的最后明确值的子孙后代的值

忽视最后的失效值

在2个合理的最后值中开展挑选时，挑选哈希值较低的那一个

假如5%的认证器是诚信的,那麼任意挑选的 512 个节点中，仅有大概 1 万亿元分之一的机遇是诚信的，因而当以上优化算法工作中，可能融洽得到单一最后值的节点。

假如阀值依靠的共识优化算法的容错性被达到(一般 50%或67%的节点是诚信的)，那麼阀值依靠的共识优化算法将不容易明确一切新的控制点，或是它将明确最后彼此之间兼容的新控制点(比如，每一个控制点都偏向前一个控制点做为父控制点)。

因而，参加取决于延迟时间的优化算法的节点不容易愿意他们接纳的值，他们接纳的值依然维持为同一链的一部分，不会有沒有具体的矛盾。一旦延迟时间在未来的某一连击恢复过来，取决于延迟时间的共识将修复“同歩”。

假如依靠阀值和依靠延迟时间的共识优化算法的假设另外被摆脱(或在持续的二轮中被摆脱)，那麼优化算法便会溶解。比如,假设在一轮中,阀值依靠共识最后明确Z→X→Y，而延迟时间至今共识在X,Y中间建议不一，那麼共识可能在没有达成共识状况下完毕。下一轮阀值依靠共识可能在最后明确W不来源于 X，且X不来源于Y的状况下完毕;在依靠延迟时间的共识中，愿意Y的节点不容易接纳W，而愿意X的节点会。殊不知，它是难以避免的;多线程下的安全性共识是不太可能的。

容错机制是拜占庭容错机制基础理论中一个大家都知道的结果，如同许多的不可能事件一样，容错机制乃至在观察器线下状况下容许同歩假设。

创作者：Vitalik Buterin（V神）

汉语翻译 | Katie 责编 | 晋兆雨

全文连接：

https://hackernoon.com/how-to-achieve-99percent-fault-tolerant-consensus-n25b31m

假如一个认证器i接到一些消息v: i:…: i[k]， 在

标签：

区块链热门资讯