零点课堂 | V神详述:如何实现99%的容错共识?(2)

改进其它共识算法

理论上讲,上述算法可以作为独立的共识算法使用,甚至可以用于运行权益证明的区块链。

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

最后使用的“选择”函数很简单:

  • 忽略不是在前一轮中已经商定的最终确定值的后代的值
  • 忽略最终的无效值
  • 在两个有效的最终值中进行选择时,选择哈希值较低的那个

如果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

本文由 零点财经 作者:tao 发表,其版权均为 零点财经 所有,文章内容系作者个人观点,不代表 零点财经 对观点赞同或支持。如需转载,请注明文章来源。
分享生成图片
25

发表回复

零点课堂 | V神详述:如何实现99%的容错共识?(2)

2021-05-28 11:50:22

改进其它共识算法

理论上讲,上述算法可以作为独立的共识算法使用,甚至可以用于运行权益证明的区块链。

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

最后使用的“选择”函数很简单:

  • 忽略不是在前一轮中已经商定的最终确定值的后代的值
  • 忽略最终的无效值
  • 在两个有效的最终值中进行选择时,选择哈希值较低的那个

如果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