我们已经听过很长一段时间了，在同步网络中可以达到50％容错的共识，其中任何诚实节点广播的消息都保证在某个已知时间段内被所有其他诚实节点接收（如果攻击者有 超过50％，它们可以执行“51％攻击”，并且对于任何此类算法都有类似的功能）。 我们也听说很长一段时间，如果你想放宽同步假设，并且有一个“异步安全”的算法，最大可实现的容错率下降到33％（PBFT，Casper FFG等都属于这个 类别）。 但是你知道吗，如果你添加更多的假设（具体来说，你需要观察者也积极地观察共识，而不仅仅是事后才下载它的输出），你可以将容错率一直提高到99％？
事实上，这一点早已为人所知；莱斯利·兰波特1982年的著名论文“拜占庭将军问题”包含算法的描述。以下是我试图以简化的形式描述和重新表述该算法的尝试。
假设有N个节点，我们将其标记为0....N-1，有一个已知的界限D关于网络延迟加上时钟差异(例如。D=8秒)。每个节点都有能力在T时刻同时发布一个值。 (恶意节点当然可以早于或晚于T)所有节点等待(N-1) * D秒，运行以下进程。定义x : i作为“价值”x节点签名i”, x : i : j作为“价值”x由i，这个值和签名一起由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）。
现在，让我们探索一下为什么会这样。我们需要证明的是，如果一个诚实节点已经看到了一个特定的值(有效地)，那么每个其他诚实节点也看到了这个值(如果我们证明了这一点，那么我们就知道所有诚实节点都运行着相同的选择函数，因此它们将输出相同的值)。假设任何诚实的节点接收到消息v：i [1]：...：i [k]他们认为有效（即，它在T + k * D时刻之前到达）。 假设x是单个其他诚实节点的索引。 x是{i [1] ... i [k]}的一部分，或者不是。
●在第一种情况下（比如说这个消息的x = i [j]），我们知道诚实节点x已经广播了该消息，并且他们这样做是为了响应他们在时刻T之前收到的带有j-1签名的消息。因此他们在T+（j-1）* D时广播他们的消息，因此在时刻T + j * D之前所有诚实节点必须已经接收到该消息。
●在第二种情况下，因为诚实节点在T + k * D时之前看到消息，然后他们将用他们的签名广播信息，并保证每个人，包括x，会在T + (k+1) * D时之前看到。
请注意，该算法使用添加自己签名的行为作为消息超时的一种“凸点”，正是这种能力保证了如果一个诚实的节点按时看到消息，他们可以确保其他人也能按时看到消息，因为“准时”的定义是通过以下方式递增的超过网络延迟与每个添加的签名。
在一个节点诚实的情况下，我们能保证被动的观察员是否也能看到结果，即使我们要求他们一直在观察这个过程？按照所写的计划，有个问题。假设一个指挥官和一些k（恶意）验证器的子集产生一个消息v：i [1]：....：i [k]，并在T + k * D时之前将其直接广播给一些“受害者” 受害者将消息视为“准时”，但是当他们重新广播时，它只会在T + k * D时之后到达所有诚实的共识参与节点，因此所有诚实的共识参与节点都拒绝它。
但我们可以填补这个漏洞。我们要求D受两倍网络延迟加上时钟差异的约束。然后我们对观察者施加不同的超时：观察者接受v：i [1]：....：i [k]在时刻T +（k - 0.5）* D之前。现在，假设观察者看到一条消息并接受它。 他们将能够在时刻T + k * D之前将其广播到一个诚实的节点，并且诚实节点将发出附有其签名的消息，该具有k + 1个签名的消息的超时的消息将在时刻T +（k + 0.5）* D之前到达所有其他观察者。
对其他协商一致算法的改进
假设我们有一些其他的一致性算法（例如，PBFT，Casper FFG，基于链的PoS），其输出可以偶尔在线观察者看到（我们称之为阈值相关的一致性算法，与上面的算法相反） ，我们将其称为延迟相关的一致性算法。假设依赖于阈值的一致性算法连续运行，其模式是不断地将新块“最终化”到链上（即，每个最终值指向一些先前的最终值作为“父”;如果存在一系列指针 A - > ... - > B，我们称A为B的后代。我们可以将依赖于延迟的算法改造到这个结构上，让总是在线的观察者能够在检查点上获得一种“强大的终结性”，容错率达到95％（你可以通过增加更多的验证器和任意方式将其任意接近100％） 要求这个过程需要更长的时间）。
每次时间达到4096秒的倍数时，我们运行与延迟相关的算法，选择512个随机节点参与该算法。有效方案是由阈值相关算法最终确定的任何有效的值链。如果节点在具有k个签名的时间T + k * D（D = 8秒）之前看到一些最终值，则它将链接到其已知链的集合中并且重新广播它并添加其自己的签名; 观察者像以前一样使用T +（k-0.5）* D的阈值。
结尾处使用的“选择”函数很简单：
●最后确定的最终值，如果不是上一轮中已商定的最终值的后代，就会被忽略。
●无效的最终值将被忽略。
●若要在两个有效的最终值之间进行选择，选择一个哈希值较低的值。
如果5％的验证器是诚实的，那么只有大约1/1万亿的机会512个随机选择的节点中没有一个是诚实的，因此只要网络延迟加上时钟差异小于D / 2，上述算法 即使由于阈值相关算法的容错被破坏而呈现多个冲突的最终值，也将工作，正确地协调某些单个最终值的节点。
如果满足阈值相关一致性算法的容错（通常为50％或67％诚实），那么依赖于阈值的一致性算法将不会最终确定任何新检查点，或者它将最终确定彼此兼容的新检查点 （例如，一系列检查点，其中每个检查点指向前一个作为父项），因此即使网络延迟超过D / 2（或甚至D），因此参与延迟相关算法的节点也不同意它们的值 接受，他们接受的价值仍然保证是同一个链的一部分，因此没有实际的分歧。 一旦延迟在未来一轮恢复正常，延迟相关的共识将恢复“同步”。
如果阈值相关和延迟相关的共识算法的假设同时（或在连续轮次中）被破坏，则算法可以分解。 例如，假设在一轮中，阈值依赖共识最终确定Z - > Y - > X并且延迟依赖共识在Y和X之间不一致，并且在下一轮中，阈值依赖共识最终确定X的后代W，其中 不是Y的后代; 在延迟相关的共识中，同意Y的节点将不接受W，但是同意X的节点将接受。 但是，这是不可避免的; 超过1/3容错的安全欠不同步共识的不可能性是拜占庭容错理论中众所周知的结果，即使允许同步假设但假设离线观察者也不可能超过1/2容错。
