介绍

我们提出了恒星共识协议（SCP）的简化版本，我们希望它比SCP白皮书和互联网草案更容易阅读。

拜占庭联邦协议

传统的拜占庭协议解决了N个节点的封闭系统中的共识问题。通常，对于某个正整数 f，协议假定 N = 3f + 1，然后保证安全性和某种形式的活动性，只要大多数 f 节点有故障。从概念上讲，这些协议涉及仲裁大小为 2f + 1 的投票。如果只有 N = 3f + 1 个节点，则任何两个大小为 2f + 1 的仲裁必须在至少 f + 1 个节点中重叠，因此即使重叠节点的 f 有故障，两个仲裁至少共享一个无故障节点。这个无故障的公共节点可以确保仲裁永远不会得出相互矛盾的结论。

联合拜占庭协议是拜占庭协议对具有开放成员资格的系统进行的改编，其中不同的节点对哪些节点是重要的以及仲裁应该包含什么有不同的想法。例如，节点v1可能认为仲裁需要包含某些集合 S 中≥ 3/4 的节点，而节点v2认为定额应包含>一些相似但不相同的集合 S′ 的 2/3。节点也可能对仲裁（例如，节点）的对称要求较低v3可能要求仲裁包含由公司 X 运行的大多数节点和由公司 Y 运行的大多数节点，其中 X 运行的节点比 Y 多得多。

节点的事实v1认为仲裁应包含集合 S 的 3/4 并不意味着集合 S 的 3/4 是仲裁。相反，我们说集合 S 的任何 3/4 都构成节点的仲裁切片v1.仲裁是一个集，其中包含其每个成员的至少一个仲裁切片。更准确地说，由于有故障节点可以选择不足或不一致的仲裁切片，因此我们说仲裁是一组非空的节点，每个非故障成员至少包含一个仲裁切片。

因此，联邦拜占庭协议是拜占庭协议的推广。如果每个节点都选择完全相同的仲裁切片，则联合拜占庭协议就是拜占庭协议 - 一种确保所有无故障节点之间一致的机制，同时容忍特定的故障场景。但是，当不同的节点选择不同的仲裁切片时，在某些故障场景下，只有一部分无故障节点可以保证一致。安全性仍然取决于仲裁重叠，但不再是系统范围的属性。具体来说，我们说无故障节点v1和v2如果每个仲裁都包含v1与包含v2在至少一个无故障节点中。联合拜占庭协议只有在两个节点交织在一起时才能保证它们之间的协议。由于SCP提供了这种保证，因此我们说它是安全的最佳选择。

当一组无故障节点 I 是仲裁，并且 I 的每两个节点都交织在“投影系统”中，这是由于从所有仲裁切片中删除不在 I 中的节点而产生的，那么我们说 I 是完整的。SCP 保证完整集合的最终同步下的活动性，即使成员不知道完整集合的成员身份也是如此。

仲裁切片模型支持两种关键机制：联合投票和联合领导人选举。在联合投票中，节点对语句进行投票（例如，“事务集x被提名”，如下一节所述），并且通过两步协议，可以确认语句，并确信交织在一起的节点永远不会确认矛盾的陈述。此外，一组完整的节点我享有额外的保证：我的成员永远无法确认我没有成员投票支持的声明，如果I的任何成员确认了声明，最终我的所有成员都将确认该声明，前提是节点继续在协议中采取步骤。当然，即使对于完整的节点，如果节点在相互矛盾的陈述之间拆分投票，使得任何陈述都无法获得一致的法定人数，那么任何特定的联合投票实例都可能永久卡住。

联盟领导者选择允许节点以服从仲裁切片中隐含的优先级的方式伪随机选择一个或少量领导者。当重复时，完整集合的成员最终将全部（传递地）遵循概率为1的同一唯一完整领导者。

协议说明

SCP包括三个互锁部分。提名是一种机制，通过该机制，节点会聚在一组候选值上。投票是SCP的核心，当成功时，它实际上选择了一个输出值。超时是一种机制，通过这种机制，节点放弃尚未选择值的选票，然后重试。

提名

提名需要对以下形式的声明进行联合投票：

• 提名 x：声明 x 是有效的候选共识值。

节点可以投票提名多个值 - 不同的提名语句永远不会矛盾。但是，一旦节点确认任何提名语句，它就会停止投票以提名新值。联合投票仍然允许节点确认它没有投票的新提名声明，这允许完整集合的成员确认彼此的提名值，同时扣留新的投票。

提名的（不断发展的）结果是已确认的提名声明中所有值的确定性组合。例如，如果 x 表示一组事务，则节点可以采用集合的并集、最大的集合或具有最高哈希值的集合，只要所有节点都执行相同的操作即可。由于节点在确认第一个提名语句后保留新投票，因此已确认的提名语句集只能包含有限多个值。确认值通过完整集合可靠地传播的事实意味着完整的节点最终收敛于同一组指定值，因此具有相同的命名结果。然而，收敛发生在协议中任意晚期的未知点。

节点采用联合领导者选择来减少 NOMINATE 语句中不同值的数量。只有尚未投票支持提名声明的领导者才能在提名投票中引入新的x。其他节点等待接收领导者的声音，然后只复制领导者的提名投票。为了适应故障，领导者的集合随着超时的发生而不断增长，但实际上只有少数节点引入了x的新值。

投票

稻草人共识协议可以直接投票输出提名结果。如果完整集合中的一个成员确认输出，则最终所有成员都将这样做，从而达成协议。不幸的是，节点冒着在提名收敛之前尝试此投票的风险，在这种情况下，不同的节点将投票输出不同的值，并且整个投票可能会永久卡住，没有任何值获得法定人数的可能性。

更糟糕的是，节点无法可靠地确定投票是否卡住。假设输出值比仲裁少一票。也许一个似乎已经崩溃的节点实际上只是缓慢地传播其投票，但实际上确实完成了仲裁。或者，恶意节点向不同的对等节点发送了相互矛盾的投票，使某些对等节点相信输出值已达到仲裁，而其他节点则认为不可能达到仲裁。

为了解决卡住的选票，SCP对一系列编号选票进行投票。即使卡住的投票排除了在选票n中选择一个值，我们也可以超时，用选票n + 1重试。但是，由于节点可能无法确定投票是否卡住，因此节点可以得出关于投票结果n的三个结论之一：

1. 在投票n中的法定人数中，没有一个值曾经或将来会被选择。

2. 值 x 由选票 n 中的法定人数选择。

3. 在投票n中，除了x之外，没有其他值被选择，虽然对x的投票似乎卡住了，但其他节点可能已经得出结论，结果是结果1或2，或者节点可能稍后从结果3过渡到结果1或2。

SCP中不变的原则是，所有结果为2或3的选票必须具有相同的值x。我们通过对两个声明的联合投票来确保这一点：

• 准备⟨n，x⟩：这表示在任何选票中都没有选择x以外的任何值，≤n。（如果一个节点预先投票给 COMMIT ⟨n′， x′⟩，≠ 并且该投票可能仍然完成法定人数，则该节点可能不会为此语句投票。

• COMMIT ⟨n， x⟩：这表示在选票 n 中选择值 x。

节点可以在确认任何 n 的 COMMIT ⟨n， x⟩ 后输出 x，但不能在未首先确认 PREPARE ⟨n， x⟩ 的情况下投票支持 COMMIT ⟨n， x⟩。当 n = 1 时，节点将 x 设置为提名结果，并按照下面的超时中所述选择 x 以进行后续投票。

请注意，完整的SCP协议在每条消息中紧凑地编码发件人的整个相关投票历史记录，从而避免了重新传输丢失的旧消息的需要。在简化的SCP中，我们只是假设在无故障节点之间进行可靠的消息传递。Full SCP 还为存档添加了最终的 EXTERNALIZE 消息，即使节点停用排除了使用历史切片组装仲裁，也可以让慢速节点在事后数周赶上。

超时

如果节点无法确认当前投票的 COMMIT 语句，它们会在超时后放弃，每次投票都会变长，以便调整到网络延迟的任意限制。节点在成为当前（或以后）投票计数器 n 的仲裁的一部分时启动计时器。如果在任何时候，节点的仲裁切片都包含一个具有较高投票计数器的节点，则该节点会立即跳到最低的投票，这样无论任何计时器如何，情况都不再是这种情况。

计时器机制同步节点的选票：仅当仲裁位于最新选票上时，时钟才会开始，但如果存在完整的离散者，则启动时钟的仲裁将与至少一个完整的离散者的所有切片相交，这将立即赶上，从而帮助其他完整的节点赶上，直到最终所有完整的节点都赶上。

当投票 n 在节点 v 上超时时，v 选择一个值 x 并投票给 PREPARE ⟨n + 1， x⟩。有两种策略可用于选取 x：

1. 如果 v 确认了任何 PREPARE ⟨n′， x′⟩ 语句，则它将 x 从 n′ 最高的语句设置为 x′。否则，v 将 x 设置为当前提名结果。

2. v 使用单轮联合领导者选择来选择领导者。如果 v 选择自己作为领导者，则使用策略 1。否则，v复制其领导人的PREPED投票，如果它可以合法地这样做;旧的 COMMIT 投票 v 限制了它可以投票的 PREPARE 语句，除非 COMMIT 投票已被推翻并且无法再完成法定人数。如果发生第二次超时，并且 v 仍未收到其领导者的消息或推翻其过去相互冲突的 COMMIT 投票，则 v 将回退到策略 1。

   请注意，当 v 由于每个仲裁切片都包含一个位于较高投票的节点而赶上时，v 不能等待其前导符，并且如果 v 尚未从其前导方听到 PREPARE 消息，则必须立即使用策略 1。

在部分同步下，策略 1 保证使用故障停止节点终止，但允许具有良好网络计时的恶意节点延迟终止，直到从仲裁切片中手动删除它们。策略 2 保证在拜占庭失败的情况下以概率 1 的概率终止。由于失效停止行为是常见的情况，因此混合方法是每k张选票（例如，k = 5）仅遵循策略2。

积木

本节详细介绍了上述协议描述中使用的两个较低级别的构建块，即联合投票和联盟领袖选择。

联合投票

联合投票由节点投票消息组成，这些消息还指定其仲裁切片。这些消息的收件人可以根据选民声明的切片动态发现仲裁。仲裁重叠可确保相互交织的节点不会发现自己处于矛盾的一致仲裁中。

但是，知道没有法定人数会与 a 相矛盾，这不足以确认 a;当完整集合的成员确认 a 时，我们还需要保证集合的其余部分最终会这样做。这要求不仅要确保收到仲裁，还要确保仲裁知道收到仲裁。此外，此仲裁必须能够说服其他节点（包括投票反对 a 的节点）确认 a。

为此，联合投票采用三阶段协议，其中节点首先投票支持声明（广播此效果的消息），然后接受它（再次广播事实），最后确认它。节点 v 可以对任何与其它未决投票和已接受的声明一致的有效声明进行投票。当 v 是仲裁的成员时，v 接受 a，其中每个节点要么投票支持 a，要么接受 a。即使 v 没有投票支持 a，如果 v 的每个仲裁切片都包含一个节点，接受 a 并且 v 没有接受任何与 a 相矛盾的节点，则 v 也接受 a;与所有 v 的定额切片相交的接受节点的集合通过证明这些矛盾的投票不可能是仲裁的一部分，推翻了 v 之前可能投出的任何矛盾投票。最后，当 v 是每个节点都接受 a 的仲裁的成员时，v 确认 a。

两个相互交织的节点无法确认矛盾的陈述，因为两个必需的仲裁必须共享一个无法接受矛盾陈述的无故障节点。此外，如果完整集合 I 中的节点确认了语句，则接受该语句的仲裁包含 I，或者该仲裁将与 I 的至少一个其他成员的所有仲裁切片相交。因此，通过级联效应，最终我所有人都会接受并确认一个。当然，不能保证一个完整的节点会首先确认一个，这就是为什么投票协议旨在通过卡住的选票。

联盟领导人选择

领导者选择允许每个节点以这样一种方式选择领导者，即节点通常只选择一个或少量的领导者。为了适应领导者的失败，领导者选择通过回合进行。如果当前一轮的领导者似乎没有履行职责，那么在一定的超时期之后，节点将进入下一轮，以扩大他们跟随的领导者集。

每轮都使用两个独特的加密哈希函数，H0和H1，则输出区域中的整数[0、 h麦克斯).例如，我们可以设置H我(m） = SHA256（i∥b∥n∥r∥m)，其中 b 是整个 SCP 实例（区块或分类帐编号），n 标识正在选择领导者的选票（0 表示提名或投票编号表示超时），r 表示领导者选择轮次编号，以及h麦克斯= 2256.在一轮中，我们将节点 v 的优先级定义为：

优先级（v） = H1(v)

一个稻草人是每个节点选择具有最高优先级（v）的节点v作为领导者。此方法适用于几乎相同的仲裁切片，但不能正确捕获不平衡配置中节点的重要性。例如，如果欧洲和中国每个仲裁各贡献3个节点，但中国运行1，000个节点，欧洲4个，那么中国将在99.6%的时间内拥有最高优先级的节点。

因此，我们引入了切片权重的概念，其中 weight（u，v） ∈ [0，1] 是节点 u 的包含节点 v 的仲裁切片的分数。当节点 u 选择新的引线时，它只考虑相邻节点，定义如下：

邻居（u） = { v ∣ H0(v） < h麦克斯⋅ 重量（u，v) }

然后，节点 u 以一组空的引线开始，并在每一轮中向其添加具有最高优先级 （v） 的邻居 （u） 中的节点 v。如果相邻节点集在任何舍入中为空，则 u 将节点 v 的最小值为H0(v）/重量（u，v).