99％容错共识指南_链圈子

我们很久以来就听说，在同步网络中，有可能以50％的容错率达成共识，在同步网络中，任何诚实节点广播的消息都可以保证在某个已知时间段内被所有其他诚实节点接收到（如果攻击者拥有更超过50％，就可以执行“51％的攻击”，而有这种用于这种类型的任何算法）的类似物。我们也很久以前就听说过，如果您想放松同步假设，并且拥有一种“异步下安全”的算法，则可实现的最大容错度将降至33％（PBFT，Casper FFG等都属于此类）类别）。但是您知道吗，如果您添加更多假设（具体来说，，即。不积极参与共识但关心其输出，还积极关注共识，而不仅仅是在事实结束后下载其输出的用户），是否可以将容错能力一直提高到99％？

实际上，这已经有很长时间了。莱斯利·兰珀特（Leslie Lamport）1982年著名的论文“拜占庭将军问题”（此处链接）包含对该算法的描述。以下是我尝试以简化形式描述和重新制定算法的尝试。

假设有 ñN参与共识的节点，每个人都同意这些节点是谁提前（取决于上下文，可以由受信任的一方选择它们，或者，如果需要更强的权力下放，则可以通过一些工作证明或权益证明计划来选择它们）。我们标记这些节点0。。。ñ–1个。还假设存在一个已知界限d 网络延迟以及时钟差异（例如 Dd= 8秒）。每个节点都有能力在某个时间发布值ŤT （恶意节点当然可以早于或晚提出值 ŤT）。所有节点都在等待（ñ–1个）⋅d(N-1).D秒，运行以下过程。定义X：一世 作为“价值 X 由节点签名 一世”， X：一世：Ĵ 作为“价值 X被…签名 一世，并且该值和签名由 Ĵ等等。在第一阶段发布的提案将采用以下形式： v：一世 对于一些 v 和 一世，其中包含提出它的节点的签名。

如果验证者 一世 收到一些消息 v：一世[1个]：。。。：一世[ķ]，在哪里 一世[1个]。。。一世[ķ] 是已经（顺序）对消息进行了签名的索引列表（只是 v 本身算作 ķ=0和 v：一世 如 ķ=1个），然后验证器检查（i）时间是否小于 Ť+ķ⋅d，以及（ii）他们尚未看到包含以下内容的有效消息 v; 如果两项检查均通过，他们将发布v：一世[1个]：。。。：一世[ķ]：一世。

在时间 Ť+（ñ–1个）⋅d，节点停止监听。在这一点上，可以保证诚实节点都“有效地看到了”相同的一组值。

但是我们可以塞这个洞。我们需要d受限于两倍的网络延迟和时钟差异。然后，我们对观察者设置了另一个超时：观察者接受v：一世[1个]：。。。。：一世[ķ] 时间之前 Ť+（ķ–0.5）⋅d。现在，假设观察者看到一条消息并接受了它。他们将能够在时间之前将其广播到诚实节点Ť+ķ⋅d，诚实节点将发出带有其签名的消息，该消息将在时间之前到达所有其他观察者 Ť+（ķ+0.5）⋅d，消息超时 ķ+1个 签名。

改造其他共识算法

从理论上讲，以上内容可以用作独立的共识算法，甚至可以用于运行权益证明区块链。验证者套轮ñ+1个 共识本身可以在回合中决定 ñ共识（例如，共识的每一轮也可以接受“存款”和“撤回”交易，如果交易被接受并正确签名，则会在下一轮中添加或删除验证者）。需要添加的主要附加成分是一种机制，用于确定允许谁提出提案（例如，每轮可以有一个指定的提案人）。通过允许参与共识的节点在签名的同时在其公钥之上发布工作量证明解决方案，允许参与共识的节点实时“声明自己”，还可以将其修改为可用作工作量证明区块链。一条消息。

但是，同步性假设非常强，因此在我们不需要超过33％或50％的容错能力的情况下，我们希望能够在没有同步性的情况下工作。有一种方法可以完成此任务。假设我们有一些其他的共识算法（例如，PBFT，卡斯帕FFG，连锁型POS）的输出可以通过不定时在线观察者可以看到（我们称这个门槛依赖共识算法，相对于上述算法，我们将其称为与延迟相关的共识算法）。假设阈值相关的共识算法以一种不断将新块“最终确定”在链上的模式连续运行（即，每个最终确定值都以“父”的形式指向某个先前最终确定的值；如果有一系列指针）一种→。。。→乙，我们会打电话给 一种一个后代的乙）。

我们可以将依赖于延迟的算法改装到这种结构上，使始终在线的观察者可以在检查点上获得某种“强大的确定性”，容错性约为95％（您可以通过添加更多的验证器将其任意逼近100％需要更长的时间）。

每当时间达到4096秒的倍数时，我们运行依赖于延迟的算法，选择512个随机节点参与该算法。有效建议是由阈值相关算法最终确定的任何有效值链。如果节点在时间之前看到某个最终值Ť+ķ⋅d （d = 8秒） ķ签名，它会将链条接受到其已知链条集中，并通过添加自己的签名重新广播；观察者使用阈值Ť+（ķ–0.5）⋅d 和以前一样。

最后使用的“选择”功能很简单：

• 不是上一轮已同意成为最终值的后代的最终值将被忽略
• 无效的最终值将被忽略
• 要在两个有效的最终值之间进行选择，请选择一个哈希值较低的值

如果5％的验证者是诚实的，则随机选择的512个节点中，只有1万亿左右的概率是诚实的，并且只要网络延迟和时钟差异小于 d2 即使由于阈值相关算法的容错性被破坏，即使给出了多个冲突的最终值，上述算法也可以在某个单个最终值上正确地协调节点。

如果满足阈值相关共识算法的容错能力（通常为50％或67％诚实），则阈值相关共识算法将不会最终确定任何新的检查点，或者将最终确定彼此兼容的新检查点（例如，一系列检查点，每个检查点都指向前一个作为父对象），因此即使网络延迟超过 d2 （甚至 d），因此，参与等待时间相关算法的节点在接受哪个值上存在分歧，因此仍然可以保证它们接受的值属于同一链，因此没有实际分歧。一旦延迟在以后的某个回合中恢复正常，依赖于延迟的共识将恢复“同步”。

如果同时（或在连续回合中）打破了阈值相关和延迟相关共识算法的假设，则该算法可能会崩溃。例如，假设在一轮中，取决于阈值的共识最终确定ž→ÿ→X 并且延迟相关的共识不同意 ÿ 和 X，并且在下一轮中，取决于阈值的共识最终确定了后代 w ^ 的 X这是没有的后代ÿ; 在依赖于延迟的共识中，达成共识的节点ÿ 不会接受 w ^，但同意的节点 X将。但是，这是不可避免的。异步安全的共识不可能与1个3容错是拜占庭式容错理论中的一个众所周知的结果，1个2 容错甚至允许同步假设，但假设离线观察者。