以太坊创始人V神介绍99%容错的共识机制

image

我们已经听过很长一段时间了，在同步网络中可以达到50％容错的共识，其中任何诚实节点广播的消息都保证在某个已知时间段内被所有其他诚实节点接收（如果攻击者有更超过50％，就可以执行“51％的攻击”，而有这种用于这种类型的任何算法）的类似物。我们也听说很长一段时间，如果你想放宽同步假设，并且有一个“异步安全”的算法，最大可实现的容错率下降到33％（PBFT，Casper FFG等都属于这个类别）。

但是你知道吗，如果你添加更多的假设（具体来说，你需要观察者，即：如果用户没有积极参与共识但关心其输出，也要积极观察共识，而不仅仅是事后下载其输出），您可以将容错率一直提高到99％？

事实上，这已经知道了很长时间; Leslie Lamport着名的1982年论文“The Byzantine Generals Problem”（链接在这里）包含了算法的描述。以下是我尝试以简化形式描述和重新构造算法。

假设存在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:ik = 1），则验证器检查（i）时间小于T + k * D，和（ii）他们还没有看到包含的有效信息v; 如果两个检查通过，他们发布v : i[1] : ... : i[k] : i。

当时T + (N-1) * D，节点停止收听。此时，可以保证诚实节点全部“有效地看到”同一组值。

image

节点1（红色）是恶意的，节点0和2（灰色）是诚实的。比赛一开始，两位诚实的节点让他们的建议y和x，而攻击者提出了两个w和z后期。w准时到达节点0但不z到达节点2，并且没有按时到达节点。在时间T + D，节点0和2重播他们已经看到了，他们还没有广播的所有值，但增加了他们的签名上（x与w节点0，y节点2）。这两个节点诚实看到{x, y, w}。

如果问题需要选择一个值，他们可以使用一些“选择”函数从他们看到的值中选择一个值（例如，他们采用具有最低哈希的值）。然后节点可以就此值达成一致。

现在，让我们来探讨一下为什么会这样。我们需要证明的是，如果一个诚实的节点已经看到了一个特定的值（有效地），那么每个其他诚实的节点也看到了这个值（如果我们证明了这一点，那么我们知道所有诚实的节点都看到了相同的一组值，所以如果所有诚实节点都运行相同的选择函数，它们将选择相同的值）。假设任何诚实节点接收v : i[1] : ... : i[k]到他们认为有效的消息（即，它在时间之前到达T + k * D）。假设x是单个其他诚实节点的索引。要么x是其中的一部分，{i[1] ... i[k]}要么不是。

在第一种情况下（比如说x = i[j]这个消息），我们知道诚实节点x已经广播了该消息，并且他们这样做是为了响应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，所以所有诚实的共识参与节点都拒绝它。

image

但我们可以填补这个漏洞。我们要求D受到两倍的网络延迟和时钟差异的限制。然后我们对观察者施加不同的超时：观察者v : i[1] : .... : i[k]在时间之前接受T + (k - 0.5) * D。现在，假设观察者看到一条消息接受它。他们将能够在一段时间之前将它广播到一个诚实的节点T + k * D，并且诚实的节点将发出带有其签名的消息，该消息将在时间之前到达所有其他观察者T + (k + 0.5) * D，具有k+1签名的消息的超时。

image

改造其他共识算法

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

但是，同步假设非常强，因此我们希望能够在没有超过33％或50％容错的情况下在没有它的情况下工作。有一种方法可以实现这一目标。假设我们有一些其他的一致性算法（例如，PBFT，Casper FFG，基于链的PoS），其输出可以偶尔在线观察者看到（我们称之为阈值相关的一致性算法，与上面的算法相反） ，我们称之为延迟依赖共识算法）。假设依赖于阈值的一致性算法连续运行，其模式是不断地将新块“最终化”到链上（即，每个最终值指向一些先前的最终值作为“父”;如果存在一系列指针A -> ... -> B，我们称A 为B 的后代。

我们可以将依赖于延迟的算法改造到这个结构上，让总是在线的观察者能够在检查点上获得一种“强大的终结性”，容错率达到95％（你可以通过增加更多的验证器和任意方式将其任意接近100％）要求这个过程需要更长的时间）。

每次时间达到4096秒的倍数时，我们运行与延迟相关的算法，选择512个随机节点参与算法。有效提议是由阈值相关算法最终确定的任何有效值链。如果一个节点在T + k * D带有k签名的时间（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。但是，这是不可避免的; 具有超过1/3容错性的安全欠不同步共识的不可能性是a众所周知拜占庭容错理论的结果，即使允许同步假设，但假设离线观察者不可能超过1/2容错。

内容来源：区块链兄弟

作者：V神

原文链接：http://t.cn/RD93GS2

image