99％容错共识指南

liumuhui 2年前 (2023-06-28) 阅读数 179 #技术

我们很久以来就听说，在同步网络中，有可能以50％的容错率达成共识，在同步网络中，任何诚实节点广播的消息都可以保证在某个已知时间段内被所有其他诚实节点接收到（如果攻击者拥有更超过50％，就可以执行“51％的攻击”，而有这种用于这种类型的任何算法）的类似物。我们也很久以前就听说过，如果您想放松同步假设，并且拥有一种“异步下安全”的算法，则可实现的最大容错度将降至33％（PBFT，Casper FFG等都属于此类）类别）。但是您知道吗，如果您添加更多假设（具体来说，，即。不积极参与共识但关心其输出，还积极关注共识，而不仅仅是在事实结束后下载其输出的用户），是否可以将容错能力一直提高到99％？

实际上，这已经有很长时间了。莱斯利·兰珀特（Leslie Lamport）1982年著名的论文“拜占庭将军问题”（此处链接）包含对该算法的描述。以下是我尝试以简化形式描述和重新制定算法的尝试。

假设有 $ñ$ N参与共识的节点，每个人都同意这些节点是谁提前（取决于上下文，可以由受信任的一方选择它们，或者，如果需要更强的权力下放，则可以通过一些工作证明或权益证明计划来选择它们）。我们标记这些节点 $0$ $。$ $。$ $。$ $ñ$ $-$ $1个$ 。还假设存在一个已知界限 $d$ 网络延迟以及时钟差异（例如 D $d$ = 8秒）。每个节点都有能力在某个时间发布值 $Ť$ T （恶意节点当然可以早于或晚提出值 $Ť$ T）。所有节点都在等待 $（$ $ñ$ $-$ $1个$ $）$ $\cdot$ $d$ (N-1).D秒，运行以下过程。定义 $X$ $：$ $一世$ 作为“价值 $X$ 由节点签名 $一世$ ”， $X$ $：$ $一世$ $：$ $Ĵ$ 作为“价值 $X$ 被...签名 $一世$ ，并且该值和签名由 $Ĵ$ 等等。在第一阶段发布的提案将采用以下形式： $v$ $：$ $一世$ 对于一些 $v$ 和 $一世$ ，其中包含提出它的节点的签名。

如果验证者 $一世$ 收到一些消息 $v$ $：$ $一世$ $[$ $1个$ $]$ $：$ $。$ $。$ $。$ $：$ $一世$ $[$ $ķ$ $]$ ，在哪里 $一世$ $[$ $1个$ $]$ $。$ $。$ $。$ $一世$ $[$ $ķ$ $]$ 是已经（顺序）对消息进行了签名的索引列表（只是 $v$ 本身算作 $ķ$ $=$ $0$ 和 $v$ $：$ $一世$ 如 $ķ$ $=$ $1个$ ），然后验证器检查（i）时间是否小于 $Ť$ $+$ $ķ$ $\cdot$ $d$ ，以及（ii）他们尚未看到包含以下内容的有效消息 $v$ ; 如果两项检查均通过，他们将发布 $v$ $：$ $一世$ $[$ $1个$ $]$ $：$ $。$ $。$ $。$ $：$ $一世$ $[$ $ķ$ $]$ $：$ $一世$ 。

在时间 $Ť$ $+$ $（$ $ñ$ $-$ $1个$ $）$ $\cdot$ $d$ ，节点停止监听。在这一点上，可以保证诚实节点都“有效地看到了”相同的一组值。

节点1（红色）是恶意的，节点0和2（灰色）是诚实的。首先，两个诚实的节点提出建议

$ÿ$

和

$X$

，并且攻击者同时提出

$w$

和

$ž$

晚的。

$w$

准时到达节点0，但未到达节点2，并且

$ž$

按时到达两个节点。在时间

$Ť$

$+$

$d$

，节点0和2重新广播他们看到的尚未广播的所有值，但在（

$X$

和

$w$

对于节点0，

$ÿ$

对于节点2）。两个诚实的节点都看到了

$X$

$，$

$ÿ$

$，$

$w$

。

如果问题要求选择一个值，则他们可以使用一些“选择”功能从他们所看到的值中选择一个值（例如，他们选择哈希值最低的值）。然后，节点可以就该值达成共识。

现在，让我们探讨一下为什么它起作用。我们需要证明的是，如果一个诚实节点（有效地）看到了一个特定值，那么每个其他诚实节点也都看到了该值（如果我们证明这一点，那么我们知道所有诚实节点都看到了相同的一组值。值，因此，如果所有诚实节点都运行相同的选择功能，则它们将选择相同的值）。假设任何诚实节点都收到一条消息 $v$ $：$ $一世$ $[$ $1个$ $]$ $：$ $。$ $。$ $。$ $：$ $一世$ $[$ $ķ$ $]$ 他们认为是有效的（即，它早于时间到达） $Ť$ $+$ $ķ$ $\cdot$ $d$ ）。假设 $X$ 是其他单个诚实节点的索引。要么 $X$ 是其一部分 $一世$ $[$ $1个$ $]$ $。$ $。$ $。$ $一世$ $[$ $ķ$ $]$ 或不是。

在第一种情况下（例如 $X$ $=$ $一世$ $[$ $Ĵ$ $]$ 对于此消息），我们知道诚实节点 $X$ 已经广播了该消息，而他们这样做是为了回应 $Ĵ$ $-$ $1个$ 他们在时间之前收到的签名 $Ť$ $+$ $（$ $Ĵ$ $-$ $1个$ $）$ $\cdot$ $d$ ，因此他们当时广播了他们的消息，因此所有诚实节点必须在时间之前已收到该消息 $Ť$ $+$ $Ĵ$ $\cdot$ $d$ 。
在第二种情况下，由于诚实节点会在时间之前看到消息 $Ť$ $+$ $ķ$ $\cdot$ $d$ ，然后他们将广播带有签名的消息，并确保所有人（包括 $X$ ，会在时间之前看到 $Ť$ $+$ $（$ $ķ$ $+$ $1个$ $）$ $\cdot$ $d$ 。

请注意，该算法使用在消息超时时添加自己的签名作为一种“突击”的行为，正是这种能力保证了，如果一个诚实节点按时看到消息，他们可以确保其他人都能看到准时消息以及“准时”的定义与每个添加的签名相比，增加的延迟都超过网络延迟。

如果一个节点是诚实的，我们是否可以保证被动观察者（即关心结果的不参与共识的节点）也可以看到结果，即使我们要求他们一直在监视整个过程？按照书面计划，存在一个问题。假设一个指挥官和 $ķ$ （恶意）验证者产生一条消息 $v$ $：$ $一世$ $[$ $1个$ $]$ $：$ $。$ $。$ $。$ $。$ $：$ $一世$ $[$ $ķ$ $]$ ，并将其直接广播给某些“受害者” $Ť$ $+$ $ķ$ $\cdot$ $d$ 。受害者认为消息是“准时”的，但是当他们重新广播时，消息只会在到达之后才到达所有诚实的，参与共识的节点。 $Ť$ $+$ $ķ$ $\cdot$ $d$ ，因此所有诚实的参与共识的节点都拒绝接受它。

但是我们可以塞这个洞。我们需要 $d$ 受限于两倍的网络延迟和时钟差异。然后，我们对观察者设置了另一个超时：观察者接受 $v$ $：$ $一世$ $[$ $1个$ $]$ $：$ $。$ $。$ $。$ $。$ $：$ $一世$ $[$ $ķ$ $]$ 时间之前 $Ť$ $+$ $（$ $ķ$ $-$ $0.5$ $）$ $\cdot$ $d$ 。现在，假设观察者看到一条消息并接受了它。他们将能够在时间之前将其广播到诚实节点 $Ť$ $+$ $ķ$ $\cdot$ $d$ ，诚实节点将发出带有其签名的消息，该消息将在时间之前到达所有其他观察者 $Ť$ $+$ $（$ $ķ$ $+$ $0.5$ $）$ $\cdot$ $d$ ，消息超时 $ķ$ $+$ $1个$ 签名。

改造其他共识算法

从理论上讲，以上内容可以用作独立的共识算法，甚至可以用于运行权益证明区块链。验证者套轮 $ñ$ $+$ $1个$ 共识本身可以在回合中决定 $ñ$ 共识（例如，共识的每一轮也可以接受“存款”和“撤回”交易，如果交易被接受并正确签名，则会在下一轮中添加或删除验证者）。需要添加的主要附加成分是一种机制，用于确定允许谁提出提案（例如，每轮可以有一个指定的提案人）。通过允许参与共识的节点在签名的同时在其公钥之上发布工作量证明解决方案，允许参与共识的节点实时“声明自己”，还可以将其修改为可用作工作量证明区块链。一条消息。

但是，同步性假设非常强，因此在我们不需要超过33％或50％的容错能力的情况下，我们希望能够在没有同步性的情况下工作。有一种方法可以完成此任务。假设我们有一些其他的共识算法（例如，PBFT，卡斯帕FFG，连锁型POS）的输出可以通过不定时在线观察者可以看到（我们称这个门槛依赖共识算法，相对于上述算法，我们将其称为与延迟相关的共识算法）。假设阈值相关的共识算法以一种不断将新块“最终确定”在链上的模式连续运行（即，每个最终确定值都以“父”的形式指向某个先前最终确定的值；如果有一系列指针） $一种$ $\to$ $。$ $。$ $。$ $\to$ $乙$ ，我们会打电话给 $一种$ 一个后代的 $乙$ ）。

我们可以将依赖于延迟的算法改装到这种结构上，使始终在线的观察者可以在检查点上获得某种“强大的确定性”，容错性约为95％（您可以通过添加更多的验证器将其任意逼近100％需要更长的时间）。

每当时间达到4096秒的倍数时，我们运行依赖于延迟的算法，选择512个随机节点参与该算法。有效建议是由阈值相关算法最终确定的任何有效值链。如果节点在时间之前看到某个最终值 $Ť$ $+$ $ķ$ $\cdot$ $d$ （ $d$ = 8秒） $ķ$ 签名，它会将链条接受到其已知链条集中，并通过添加自己的签名重新广播；观察者使用阈值 $Ť$ $+$ $（$ $ķ$ $-$ $0.5$ $）$ $\cdot$ $d$ 和以前一样。

最后使用的“选择”功能很简单：

不是上一轮已同意成为最终值的后代的最终值将被忽略
无效的最终值将被忽略
要在两个有效的最终值之间进行选择，请选择一个哈希值较低的值

如果5％的验证者是诚实的，则随机选择的512个节点中，只有1万亿左右的概率是诚实的，并且只要网络延迟和时钟差异小于 $d$ $\frac{}{}$ $2$ 即使由于阈值相关算法的容错性被破坏，即使给出了多个冲突的最终值，上述算法也可以在某个单个最终值上正确地协调节点。

如果满足阈值相关共识算法的容错能力（通常为50％或67％诚实），则阈值相关共识算法将不会最终确定任何新的检查点，或者将最终确定彼此兼容的新检查点（例如，一系列检查点，每个检查点都指向前一个作为父对象），因此即使网络延迟超过 $d$ $\frac{}{}$ $2$ （甚至 $d$ ），因此，参与等待时间相关算法的节点在接受哪个值上存在分歧，因此仍然可以保证它们接受的值属于同一链，因此没有实际分歧。一旦延迟在以后的某个回合中恢复正常，依赖于延迟的共识将恢复“同步”。

如果同时（或在连续回合中）打破了阈值相关和延迟相关共识算法的假设，则该算法可能会崩溃。例如，假设在一轮中，取决于阈值的共识最终确定 $ž$ $\to$ $ÿ$ $\to$ $X$ 并且延迟相关的共识不同意 $ÿ$ 和 $X$ ，并且在下一轮中，取决于阈值的共识最终确定了后代 $w ^$ 的 $X$ 这是没有的后代 $ÿ$ ; 在依赖于延迟的共识中，达成共识的节点 $ÿ$ 不会接受 $w ^$ ，但同意的节点 $X$ 将。但是，这是不可避免的。异步安全的共识不可能与 $1个$ $\frac{}{}$ $3$ 容错是拜占庭式容错理论中的一个众所周知的结果， $1个$ $\frac{}{}$ $2$ 容错甚至允许同步假设，但假设离线观察者。