V 神推荐 99% 容错共识新算法

Vitalik 最近在他的博客上发布了一篇名为《99% 容错共识算法指南》，并表示该算法由计算机科学家 Leslie Lamport 发明。Vitalik 对该共识进行了解释，并对其调整以适用于区块链环境中。

通常，所有区块链共识算法，关心的是链的验证者（即矿工）所做的事情。 Vitalik 建议，如果网络流量的独立观察者（即只是用户正在运行的区块链客户端，而不是矿工 / 验证者）实时监视正在发生的事情，并注意消息何时出现，那么他们可以检测到由矿工发起的 51％ 攻击这种“犯规游戏”，这就可以提供额外的安全保障，来防范此类攻击。

正如 Vitalik 自己所说，这一共识算法仍是经典拜占庭将军问题。如果真的实现这种 1％一致性算法的方法，那么现在的 51% 攻击将不会存在。Vitalik 在文中表示在此基础上把各类经典分布式算法和加密算法改造应用于区块链领域内，也将有可能获得不错的效果。

我们将 Vitalik Buterin 博客原文翻译如下：

很长时间以来，我们都听说过在同步网络中有可能实现 50% 容错共识，其中通过任何诚实节点广播的消息保证能够在某个已知时段内被所有其他诚实节点收到（如果攻击者拥有超过 50% 的节点，他们能够实施“51% 攻击”，对于任何此类的算法来说，都有类似的情况）。

我们也一直听说，如果您希望放宽同步假设，并有个“在异步下安全”的算法，那么最大可实现的容错率下降到 33%（ PBFT ， Casper FFG 等都属于这一类）。但是，如果增加更多的假设（具体来说，需要观察者也积极地观察共识，并且不只是事后才下载它的输出），就能够将容错率一直提高到 99%。

事实上，这早已为人所知，Leslie Lamport 写于 1982 年的著名论文《拜占庭将军问题》描述了该算法。下面是我尝试用简化的形式描述和重构该算法。

假设有 N 个节点，我们分别用 0，……，N-1 来标识，并且在网络延迟加上时钟差异有个已知的界限 D（比如，D = 8 秒）。每个节点具有在时间 T（恶意节点当然能够早于或晚于时间 T）发布一个值的能力。所有节点等待 (N - 1) * D 秒，运行以下过程。定义 x : i 是“节点 i 签署的值 x”，x : i : j 是“节点 i 签署的值 x，并且由节点 j 签署该值和签名”，等等。在第一个阶段发布的提议以 v : i 的形式出现，代表某些 v 和 i，包含提出它的节点的签名。

如果验证节点 i 收到一些消息 v : i[1] : … : i[k]，其中 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 既没有准时到达节点 0，也没有准时到达节点 2。在 T + D 时刻，节点 0 和节点 2 重新广播了它们看到但还没有广播过的所有值，并在上面添加了它们的签名（x 和 w 用于节点 0，y 用于节点 2）。两个诚实节点都看到了{x，y，w}，然后，它们可以使用一些标准选择函数（即，按字母顺序，最高的：y）。

现在，我们来探究一下这个为什么可行。我们需要证明的是，如果一个诚实节点已经看到一个特定值（有效的），然后，其他各个诚实节点也看到了该值（如果我们能证明这个，那么我们就知道所有的诚实节点在运行同样的选择函数，因此它们会输出相同的值）。假设任意一个诚实节点收到消息 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) * D 时刻前看到该消息。

注意，该算法使用添加自己签名的操作，作为一种在超时消息上的“撞击”，并且这种能力保证，如果一个诚实节点看到准时的消息，它们可以确保其他任何节点也能准时看到该消息，因为“准时”的定义随着每个增加的签名而增加更多的网络延时。

在这种情况下，如果一个节点是诚实的，我们能否保证被动观察者也能够看到输出，就算我们要求它们一直观察过程？按照所写的计划，存在一个问题。假设命令者和一些 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 时刻前达到所有其他观察者，那么，具有 k+1 个签名的消息超时。



改造其他共识算法

假设我们有一些其他共识算法（例如，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 个节点没有一个是诚实节点，并且只要网络延迟加上时钟差异小于 D/2，上述算法就有用，就算因为延时相关算法的缺省容错率被破坏而呈现多个冲突的最终确定的值，也能正确地协调在某些单独最终确定的值上的节点。

如果满足阈值相关共识算法的默认容错率（通常是 50%，或是 67% 诚实），那么阈值相关共识算法将不会最终确定任何新的检查点，或者，它将最终确定那些相互兼容的新检查点（即，一系列把前一个点作为父节点的检查点），因此，即使网络延迟超过 D/2（或 D），作为结果，参与延迟相关算法的节点不同意它们接受的值，它们接受的的值仍然被保证是同一个链上的一部分，因此，没有实际的分歧。一旦在未来某一轮，延迟恢复正常，那么，延迟相关共识将回到“同步”状态。

如果阈值相关和延迟相关共识算法的假设同时（或在连续的轮次中）被破坏，那么该算法可以崩溃。比如，假设在某一轮次，阈值相关共识算法最终确定 Z -> Y -> X，并且延迟相关共识算法在 Y 和 X 之间不一致，那么在下一轮次中，该阈值相关共识算法最终确定 X 的后代 W，其中 X 不是 Y 的后代；在该延迟相关共识算法中，那些跟 Y 一致的节点将不接受 W，但是，跟 X 一致的节点会接受 W。无论如何，这是不可避免的，在拜占庭容错理论中，不存在超过 1/3 容错率的安全同步共识，这是一个众所周知的结果，因为即使允许同步假设，但是假设离线观察者不可能超过 1/2 缺省容错率。

原文链接： https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html

感谢杜小芳对本文的策划和审校。