引言：V神近日发布了名为“99%容错共识”的新共识算法，该算法只要求1%的节点保持诚实，即使99%的节点全部选择作恶，区块链网络也能正常运转。
原文翻译：
一直以来我们就知道，在一个同步的网络中能够达到50％容错的共识，在这个网络中的任何诚实节点广播的消息都保证在某个已知时间段内被所有其他诚实节点接收（如果攻击者有超过50％，它们可以执行“51％攻击”，并且对于任何此类算法都有类似的功能）。并且我们也很久就听说过，如果你想放宽同步假设，并且有一个“异步安全”的算法，最大可实现的容错率会下降到33％（PBFT，Casper FFG等都属于这个类别）。但是你知道吗，如果你添加更多的假设（具体来说，你需要假设观察者也积极地观察共识，而不仅仅是事后才下载其输出），是否可以将容错率一直提高到99％呢？
事实上，这很久之前就已经被认识到了:Leslie Lamport1982年那篇著名的论文“The Byzantine Generals Problem”（链接https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf）里就有对这种算法的描述。下面我将尝试简述并重构这种算法。
假设存在N个节点，我们将其标记为0……N-1，并且网络延迟加时间差（例如，D=8秒）的值存在一个已知的界限D。每个节点都能够在时间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 [1] … 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没有按时到达两个中的任何一个节点。在时间T+D，节点0和2重新广播他们已经看到但还尚未广播的所有值，但是却在（x和w表示节点0，y表示节点2）上添加它们的签名。两个诚实的节点都看到{x，y，w}；然后他们可以使用一些标准选择函数（例如按字母顺序最高的y）。
现在，让我们来探讨一下为什么会这样。我们需要证明的是，如果一个诚实的节点已经看到一个特定的值（有效），那么每个其他诚实的节点也看到了这个值（如果我们证明这一点，那么我们知道所有诚实的节点都在运行相同的选择函数，所以他们会输出相同的值）。假设任何诚实的节点接收到它们认为有效（比如，它在时间T+k*D之前到达）的消息v：i[1]：…：i[k]。假设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个随机节点参与算法。有效提议是由阈值相关算法最终确定的任何有效值链。如果一个节点在具有k个签名的时间T+k*D（D=8秒）之前看到一些最终值，则它会将链收纳到其已知链的集合中并且重新广播它并添加其自己的签名；观察者会像以前一样使用T +（k-0.5）*D的阈值。
在结尾所使用的“选择”函数很简单：
- 不是已经同意在上一轮中作为最终值后代的最终值，将被忽略
- 无效的最终值将被忽略
- 要在两个有效的最终值之间进行选择，请选择具有较低哈希值的值
如果5％的验证器是诚实的，那么512个随机选择的节点中没有一个是诚实的概率只有大约1/1万亿，因此只要网络延迟加上时钟差异小于D/2，即使由于阈值相关算法的容错被破坏而呈现多个冲突的最终值，上述算法也将依然有效运作，并正确地协调某些单个最终值的节点。
如果碰到满足“阈值依赖”一致性算法的容错（通常为50％或67％诚实），那么依赖于阈值的一致性算法将不会最终确定任何新检查点，或者它将最终确定彼此兼容的新检查点（例如，一系列检查点，它们中的每个检查点都将前一个作为父项），因此即使网络延迟超过D/2（或甚至D），并且当参与延迟相关算法的节点也不同意它们所接受的值，那么他们接受的值仍然被保证是同一个链的一部分，因此没有实际的分歧。一旦延迟在未来的某一轮中恢复正常，延迟相关的共识将恢复“同步”。
如果阈值依赖和延迟依赖共识算法的假设同时（或在连续轮次中）被破坏，则算法可能被破坏。例如，假设在同一轮中，阈值依赖共识最终确定Z→Y→X并且延迟依赖共识在Y和X之间不一致，并且在下一轮中，阈值依赖共识最终确定W是X的后代，而不是Y的后代；在延迟相关的共识中，同意Y的节点将不会接受W，但是同意X的节点将会接受W。然而这是不可避免的；超过1/3容错的异步安全共识的不可能性是拜占庭容错理论中的一个众所周知的结果，就像大于1/2容错的不可能性，即使允许假定设想也不会允许假定离线观察者。
閱讀更多 幣和 的文章
