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

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