恒星共识协议首次描述于 大卫·马齐尔，2015 年。 这是一个“联邦拜占庭协议系统”，允许去中心化、无领导的计算网络有效地就决策达成共识。 恒星支付网络使用恒星共识协议（SCP）来维护所有参与者都可见的一致交易历史记录。
共识协议被认为难以理解。 SCP 比它们中的大多数简单，但仍然享有这样的声誉 - 部分原因是由于科学文章前半部分的主题“联合投票”就是 SCP 的错误想法。 但事实并非如此！ 这只是本文后半部分用来创建的一个重要构建块 实际的 恒星共识协议。
在本文中，我们将简要解释什么是“协议体系”，什么可以使其成为“拜占庭体系”以及为什么使拜占庭体系成为“联邦体系”。 然后我们将解释 SCP 文章中描述的联合投票程序，最后我们将解释 SCP 协议本身。
协议系统
协议系统允许一组参与者就某个主题达成共识，例如午餐要点什么。
在Interstellar，我们实施了自己的就餐协议系统：我们按照运营经理约翰的吩咐点餐。 这是一个简单而有效的协议体系。 我们都信任约翰，相信他每天都会找到一些有趣且有营养的东西。
但如果约翰滥用了我们的信任怎么办？ 他可以单枪匹马地决定我们都应该成为素食主义者。 一两周后，我们可能会推翻他并将权力移交给伊丽莎白。 但突然间，她喜欢上了牛油果和凤尾鱼，并认为每个人都应该这样。 权力导致腐败。 因此，最好找到一些更民主的方法：某种方式确保考虑到不同的偏好，同时确保及时且明确的结果，以便最终没有人点午餐，或者五个人下不同的订单，或者讨论一直拖到晚上。
解决方案似乎很简单：举行投票！ 但这是一种误导性的印象。 谁将收集选票并报告结果？ 为什么别人要相信他说的话？ 也许我们可以 起初 投票给我们信任的领导者，他将领导投票 - 但谁将领导投票 第一 通过投票？ 如果我们不能就领导者达成一致怎么办？ 或者，如果我们达成协议，但这位领导者陷入会议或请病假怎么办？
类似的问题也出现在分布式计算机网络中。 所有参与者或节点必须就某些决定达成一致，例如轮到谁更新共享文件或从处理队列中删除任务。 在加密货币网络中，节点必须反复从多个可能的版本中选择完整的故事，这些版本有时会发生冲突。 该网络协议向接收者保证代币 (a) 有效（不是伪造的）并且 (b) 尚未在其他地方使用。 这也确保了他将来能够使用这些代币，因为新的接收者将出于相同的原因获得相同的保证。
分布式计算网络中的任何共识系统都必须是容错的：尽管存在诸如链接缓慢、节点无响应和消息排序不正确等错误，它也必须产生一致的结果。 拜占庭式 该协议系统还可以抵抗“拜占庭”错误：节点提供虚假信息，无论是由于错误还是故意试图破坏系统或获得某种优势。 “拜占庭式”容错能力——即使某些群体成员可能撒谎或不遵守决策规则，也能相信群体决策的能力——被称为 谁试图协调这次袭击。 在安东尼·史蒂文斯。
以加密货币所有者爱丽丝为例，她必须在从鲍勃那里购买美味的冰淇淋和偿还卡罗尔的债务之间做出选择。 也许爱丽丝想通过欺骗性地花费同一个硬币来同时支付给他们两个。 为此，她必须让鲍勃的计算机相信该硬币从未支付给卡罗尔，并让卡罗尔的计算机相信该硬币从未支付给鲍勃。 拜占庭协议体系使这几乎成为不可能，它使用了一种称为“多数规则”的形式 法定人数。 这种网络中的节点拒绝转移到历史的特定版本，直到它看到足够数量的对等点（法定人数）同意这种转变。 一旦发生这种情况，他们将形成一个足够大的投票集团，以迫使剩余的网络节点同意他们的决定。 Alice 可以强迫一些节点代表她撒谎，但如果网络足够大，她的尝试将被诚实节点的投票压倒。
仲裁需要多少个节点？ 至少需要多数人，或者更确切地说，合格的多数人来打击错误和欺诈。 但要统计大多数，您需要知道参与者的总数。 在星际办公室或者区选举中，这些数字很容易查到。 但如果你的组是一个松散定义的网络，其中节点可以随意进入和离开而无需中心批准，那么你需要 联邦 拜占庭协议系统能够不根据预定的节点列表，而是根据给定时间点不断变化且不可避免地不完整的节点快照动态地确定法定人数。
从庞大网络中单个节点的角度来看，创建仲裁似乎是不可能的，但这是可能的。 这样的法定人数甚至可以保证去中心化投票的结果。 SCP 白皮书展示了如何使用称为 通过联邦投票.
对于不耐烦
本文的其余部分更详细地描述了联合投票和恒星共识协议。 如果您对细节不感兴趣，这里是该过程的总体概述。
- 节点对“提名人”进行多轮联邦投票。 联邦投票意味着：
- 节点对某些声明进行投票，例如“我提出V的值”；
- 该节点监听对等体的声音，直到找到一个可以“接收”的声音；
- 该节点为此断言寻找“法定人数”。 法定人数“确认”被提名人。
- 一旦节点可以确认一个或多个提名人，它就会尝试通过几轮联合投票来“准备”“选票”。
- 一旦节点能够验证选票已准备好，它就会尝试通过更多轮的联合投票来提交选票。
- 一旦节点可以确认选票的提交，它就可以通过将该选票用作共识结果来“外部化”该选票的值。
这些步骤涉及多轮联合投票，共同构成一轮 SCP。 让我们仔细看看每一步发生了什么。
联合投票
联合投票是确定网络是否可以就提案达成一致的程序。 在投票轮中，每个节点必须从许多可能的值中选择一个。 除非确信网络中的其他节点不会选择不同的结果，否则它无法做到这一点。 为了确保这一点，节点来回交换大量消息，以便每个人 确认该 法定人数 结 需要 同样的事情 决定。 本节的其余部分解释了这句话中的术语以及整个过程如何发生。
法定人数和法定人数切片
让我们从定义法定人数开始。 正如我们上面所讨论的，在具有动态成员资格的去中心化网络中，不可能提前知道节点的数量，因此不可能知道大多数人需要多少个节点。 联合投票通过引入新的想法解决了这个问题 法定人数削减 （仲裁切片）：节点信任的一小组对等点，用于将投票状态信息传达给网络的其余部分。 每个节点定义自己的仲裁片（它成为该仲裁片的事实上的成员）。
法定人数的形成始于法定人数的削减。 对于每个节点，都会添加其剪切节点。 然后添加切片项 这些节点 等等。 随着您继续，越来越多的节点无法添加，因为它们已经包含在切片中。 当没有更多的新节点要添加时，该过程停止：我们通过初始节点的仲裁切片的“传递闭包”形成了仲裁。
要从给定节点查找仲裁...
...添加其切片的成员...
...然后我们添加这些节点的切片成员。
我们继续，直到没有剩余的节点可供添加。
没有剩余节点可供添加。 这是法定人数。
事实上，每个节点可以出现在多个切片中。 要形成法定人数，请仅选择其中一个切片并添加成员； 然后为每个成员选择任意切片并添加成员 它 切等。 这意味着每个节点都是许多可能的法定群体的成员。
每一步仅选择一个仲裁片。
一个可能的法定人数。 或者另一种选择...
...选择其他切片...
……（如果可能的话）……
...创建另一个法定人数。
节点如何知道其他节点位于哪些切片中？ 与其他节点的其他信息一样：来自每个节点在其投票状态发生变化时向网络广播的传输。 每个广播都包含有关发送节点的切片的信息。 SCP白皮书没有指定通信机制。 实现通常使用 确保消息在整个网络中的广播。
回想一下，在非联邦拜占庭协议系统中，法定人数被定义为所有节点的大多数。 拜占庭协议系统是从这个问题的角度来设计的：系统可以容忍多少个不诚实的节点？ 在一个由 N 个节点组成的系统中，设计可以承受 f 个故障，一个节点应该能够通过接收来自 N−f 个对等点的反馈来取得进展，因为其中有 f 个节点可能已关闭。 但是，在收到来自 N−f 个对等点的响应后，我们可以假设所有 f 个对等点（节点未从其中收到响应）实际上都是诚实的。 因此，N−f 个对等点（从中收到响应）中的 f 个是恶意的。 为了让节点达成相同的共识，剩余的大多数节点必须是诚实的，也就是说，我们需要 N−f 大于 2f 或 N > 3f。 因此，通常设计为能够承受 f 次故障的系统总共有 N=3f+1 个节点，仲裁大小为 2f+1。 一旦提案通过了法定人数阈值，网络的其余部分就会确信任何竞争提案都会失败。 这就是网络收敛到结果的方式。
但在联邦拜占庭协议体系中，不仅不能有多数（因为没有人知道网络的总规模），而且多数的概念完全没有用！ 如果系统中的成员资格是开放的，那么有人只需通过执行所谓的 Sybil 攻击即可获得多数席位：跨多个节点重复加入网络。 那么为什么可以调用传递切片闭包 法定人数，以及它如何能够抑制竞争提案？
从技术上来说，不可能！ 想象一个由六个节点组成的网络，其中两个三元组在彼此的仲裁切片中相互隔离。 第一个小组可能会做出第二个小组永远不会听说的决定，反之亦然。 这个网络没有办法达成共识（除非偶然）。
因此，SCP 要求，对于联邦投票（以及要应用本文的重要定理），网络必须具有称为 法定人数的交集。 在具有这一属性的网络中，可以构造的任何两个仲裁总是在至少一个节点中重叠。 为了确定网络的普遍情绪，这与拥有多数票一样好。 直观地说，这意味着如果任何法定人数同意声明 X，则其他任何法定人数都不能同意其他任何内容，因为它必然包括第一个法定人数中已经投票给 X 的某个节点。
如果网络中存在法定人数的交集......
...然后您可以建立任意两个法定人数...
……总会相交的。
（当然，重叠的节点可能会被证明是拜占庭式的谎言或其他不好的情况。在这种情况下，仲裁交集根本无助于网络达成一致。因此，SCP 白皮书中的许多结果都是基于明确的假设，例如网络仲裁交叉中还剩下什么 即使删除坏节点后。 为了简单起见，让我们保留这些假设 隐含的 在本文的其余部分）。
期望在独立节点的网络中实现可靠的群体交叉似乎是不合理的。 但造成这种情况的原因有两个。
第一个原因是互联网本身的存在。 互联网是具有交叉群体的独立节点网络的完美示例。 互联网上的大多数节点仅连接到少数其他本地节点，但这些小集合重叠得足够多，以至于可以沿着某些路线从每个其他节点到达每个节点。
第二个原因特定于 Stellar 支付网络（SCP 最常见的用途）。 Stellar网络上的每一项资产都有一个发行人，Stellar的指导方针要求每个发行人指定网络上的一个或多个节点来处理赎回请求。 对于您感兴趣的每个资产，直接或间接将这些节点包含在仲裁切片中符合您的最佳利益。 对给定资产感兴趣的所有节点的法定人数将至少在那些兑换节点上重叠。 对多种资产感兴趣的节点会将各个发行人的所有赎回节点纳入其法定人数切片中，并且他们将寻求将所有资产集中在一起。 此外，任何未以这种方式链接到网络上其他资产的资产，以及 不应连接 - 这样设计是为了使该网络没有法定人数重叠（例如，美元区的银行有时希望与欧元区的银行和比索区的银行进行交易，因此它们位于同一网络上，但没有他们中的一些人关心出售棒球卡的儿童独立网络）。
当然， ожидание 法定人数交叉不是 保证。 其他拜占庭协议系统的复杂性很大程度上归功于法定人数的保证。 SCP 的一个重要创新在于，它将创建仲裁的责任从共识算法本身中移除，并将其带到了应用程序级别。 因此，尽管联邦投票足够普遍，可以对任何问题进行投票，但其可靠性实际上关键取决于这些含义的更广泛含义。 某些假设用途可能不像其他用途那样有利于创建连接良好的网络。
投票、接受和确认
在联合投票轮中，节点可以选择开始对某个值 V 进行投票。这意味着向网络广播一条消息：“我是节点 N，我的仲裁切片是 Q，我正在为 V 投票。” 当节点以这种方式投票时，它承诺它从未投票反对 V，也永远不会。
在点对点广播中，每个节点都可以看到其他节点如何投票。 一旦节点收集了足够的这些消息，它就可以跟踪仲裁切片并尝试查找仲裁。 如果他看到法定人数的同行也投票给 V，他可以继续 采用 V 并向网络广播这条新消息：“我是节点 N，我的仲裁切片是 Q，我接受 V。” 接受比简单的投票提供了更有力的保证。 当一个节点投票给 V 时，它永远不能投票给其他选项。 但如果一个节点接受 V，网络上的任何节点都不会接受其他选项（SCP 白皮书中的定理 8 证明了这一点）。
当然，很可能不会立即出现与 V 一致的节点法定人数。其他节点可能会投票支持其他值。 但节点还有另一种方式从简单投票转向接受。 N 可能会接受 W 的不同值，即使他没有投票支持它，即使他没有看到它的法定人数。 要决定更改您的投票，只需查看 阻塞集 已接受 W 的节点。阻塞集是每个仲裁片 N 中的一个节点。顾名思义，它可以 封锁 任何其他含义。 如果这样一个集合中的所有节点都接受 W，那么（根据定理 8）将永远不可能形成采用不同值的法定人数，因此 N 接受 W 也是安全的。
具有三个仲裁切片的节点 N。
BDF 是 N 的阻塞集：它包括 N 的每个切片中的一个节点。
BE 也是 N 的阻塞集，因为 E 出现在 N 的两个切片中。
但阻塞集不是法定人数。 如果只攻击 N 的每个切片中的一个节点就足够了，那么欺骗节点 N 接受所需的值就太容易了。因此，接受该值并不是投票的结束。 相反，N 必须确认该值，即查看接受该值的节点的法定数量。 如果走到这一步，那么，正如 SCP 白皮书所证明的那样（定理 11），网络的其余部分最终也将确认相同的值，因此 N 将以某个值作为结果结束联邦投票。
联合投票。
投票、接受、确认的过程构成一轮完整的联合投票。 Stellar共识协议结合了许多这样的轮次来创建一个完整的共识系统。
恒星共识协议
共识系统的两个最重要的属性是 - 安全 и 生存能力。 如果共识算法永远不会向不同的参与者给出不同的结果（鲍勃的历史副本永远不会与卡罗尔相矛盾），那么它就是“安全的”。 “宜居性”是指算法总会产生一个结果，即不会卡住。
描述联邦投票程序 安全的 从某种意义上说，如果一个节点确认了 V 的值，则其他节点都不会确认另一个值。 但“不会证实另一种含义”并不意味着它一定会证实某事。 参与者可以对如此多的不同值进行投票，以至于没有任何值会达到接受阈值。 这意味着在联邦投票中没有 生存能力.
Stellar共识协议使用联合投票来确保安全性和生存性。 （SCP的安全性和生存性保证有理论上的限制。设计选择了非常强的安全性保证，牺牲了少量的生存性缓解措施，但如果有足够的时间，达成共识的可能性很大。） 简而言之，这个想法是对多个值进行多次联合投票，直到其中一个值通过下面描述的所有 SCP 投票阶段。
SCP寻求共识的价值观可以是交易历史或午餐订单或其他东西，但需要注意的是，这些并不是被接受或确认的价值观。 相反，联邦投票是根据 关于这些价值观的陈述.
第一轮联邦投票于 提名阶段 （提名阶段），在一组类似“我提名V”的陈述上，可能是针对V的许多不同值。提名的目的是找到一个或多个经过接受和确认的陈述。
找到可验证的候选人后，SCP 进入投票阶段，目标是找到某个特定的候选人 时事通讯 （即，建议值的容器）和可以声明的法定人数 犯罪 为了它（提交）。 如果法定人数进行投票，则其值将被接受为共识。 但在节点对选票提交进行投票之前，它必须首先确认 消除 所有票数较低的选票。 这些步骤——取消选票以找到可以提交的选票——涉及对多个选票主张进行多轮联合投票。
以下部分更详细地描述了提名和投票。
提名
在提名阶段开始时，每个节点可以自发地为V选择一个值，并对“我提名V”这一声明进行投票。 此阶段的目标是通过联合投票确认某些价值的提名。
也许有足够多的节点对完全不同的提案进行投票，以至于没有提名能够达到接受门槛。 因此，除了广播自己的提名投票之外，节点还“反映”其同行的提名。 Echo 意味着，如果一个节点投票给提名 V，但看到来自邻居的消息投票给提名 W，那么它现在将同时投票给 V 和 W。（并非所有节点投票都会在提名期间回显，因为这可能会导致投票激增） SCP包含了一个机制来调节这些投票，简而言之，有一个公式可以从节点的角度来确定peer的“优先级”，并且只反映高优先级节点的投票。提名时间越长接受，阈值越低，因此节点扩展了将反映其投票的对等点集合。优先级公式包括槽号作为其输入之一，因此一个槽的高优先级对等点可能是一个低优先级对等点另一个，反之亦然）。
从概念上讲，提名是平行的，V和W都是单独的联邦投票，每一个都能够获得接受或确认。 实际上，SCP 协议消息将这些单独的投票打包在一起。
尽管投票支持 V 的提名意味着永远不会投票反对 V 的提名，但“反对”的含义是在应用程序级别（在本例中为 SCP）确定的。 SCP 没有看到与“我提名 X”投票相矛盾的声明，即不存在“我反对提名 X”的消息，因此节点可以投票提名任何值。 其中许多提名将一事无成，但最终节点将能够接受或确认一个或多个值。 一旦提名人被确认，他就成为 候选人.
使用联合投票的 SCP 提名。 可以有许多由对等方提出并由节点“反映”的“B”值。
提名可能会产生多个已确认的候选人。 因此，SCP要求应用层提供某种方法将候选者组合成一个 综合 （合成的）。 连接方法可以是任何方法。 最主要的是，如果这种方法是确定性的，那么每个节点将组合相同的候选者。 在午餐投票系统中，“统一”可能仅仅意味着拒绝两名候选人之一。 （但以确定性方式：每个节点必须选择相同的值来重置。例如，按字母顺序排列的较早选择）。 在恒星支付网络上，对交易历史进行投票，合并两个提议的提名人涉及合并它们包含的交易以及两个时间戳中最新的交易。
SCP 白皮书证明（定理 12），在扩展阶段结束时，网络最终收敛为单个组合。 但有一个问题：联合投票是一种异步协议（如 SCP）。 换句话说，节点不通过时间进行协调，而仅通过它们发送的消息进行协调。 从节点的角度来看，尚不清楚何时 结束 延伸阶段。 尽管所有节点最终都会到达同一个组合，但它们可能会沿途采取不同的路线，沿途创建不同的组合候选，并且永远无法判断哪一个是最终的。
但也很正常。 提名只是准备。 主要是限制候选者的数量以达成共识，这发生在这个过程中 跑步 （投票）。
跑步
公告是一对，其中 counter 是从 1 开始的整数，value 是提名阶段的候选者。 这可以是节点自己的候选者或该节点接受的相邻节点的候选者。 粗略地说，投票涉及反复尝试，通过在选票声明上持有潜在的许多联合投票，迫使网络在某些选票上就某些候选人达成共识。 选票上的计数器会记录所做的尝试，计数较高的选票优先于计数较低的选票。 如果时事通讯陷入困境，新的投票开始，现在在选票上。
区分是很重要的 意 （例如，午餐应该是什么：披萨或沙拉）， 时事通讯 （反值对）和 报表 关于选票。 SCP 轮包括多轮联邦投票，特别是针对以下声明：
- “我已准备好进行 B 选票”并且
- “我宣布投票 B 的提交”
从给定节点的角度来看，当它找到可以确认（即找到法定人数接受）声明“我提交选票 B”的选票 B 时，就达成了共识。 从此时起，可以安全地按照 B 中指定的值采取行动 - 例如，下午餐订单。 它被称为 外在化 含义。 一旦确认接受选票，节点就可以确定任何其他节点已经外部化了相同的值或将来会这样做。
尽管许多联合投票在概念上是针对许多不同选票的主张进行的，但它们不会交换那么多消息，因为每个消息都封装了许多选票。 因此，一条消息会同时促进许多联合投票的状态，例如：“我接受范围从前”
“准备”和“提交”这两个词是什么意思？
当节点确信其他节点不会提交具有不同值的选票时，节点会投票提交选票。 准备申请的目的就是要证明这一点。 表示“我准备好提交选票 B”的投票是承诺永远不会提交小于 B 的选票，即计数较小的选票（SCP 要求选票中的值按一定顺序排列。因此，时事通讯较少的，如果 N1
为什么“我准备好提交选票 B”意味着“我保证永远不会提交小于 B 的选票”？ 因为 SCP 将中止定义为提交的反义词。 准备选票的投票还涉及取消其他一些选票资格的投票，正如我们之前讨论的，投票支持一件事就是承诺永远不会投票反对它。
在广播提交之前，节点必须首先找到一个可以确认已准备好的公告。 换句话说，它对主题“我准备好提交选票 B”进行联合投票，可能对许多不同的选票进行联合投票，直到找到接受法定人数的选票。
准备投票所需的选票从哪里来？ 首先，节点广播投票<1,C>的准备情况，其中C是提名阶段产生的复合候选人。 然而，即使在投票准备工作开始之后，提名也可能导致更多候选人成为新的选票。 同时，同级可以有不同的候选人，他们可以形成一个阻塞集，接受“我准备好提交 B2 选票”，这将说服节点也接受它。 最后，还有一个超时机制，如果当前选票被卡住，它会针对计数较高的新选票生成新一轮的联合投票。
一旦节点发现可以确认已准备好的选票 B，它就会广播一条新消息“提交选票 B”。 这个投票告诉peer节点该节点永远不会放弃B。事实上，如果B是一张选票，然后“提交选票" 指无条件同意投票支持每张选票的准备情况到 < 无穷大， s >。 如果其他对等方仍处于协议的早期阶段，则此额外值可帮助其他对等方赶上提交对等方。
在这个阶段，值得再次强调的是，这些都是异步协议。 仅仅因为一个节点对提交发送赞成票并不意味着它的对等节点也会这样做。 他们中的一些人可能仍在对声明进行投票，准备投票，另一些人可能已经将其含义具体化了。 SCP 解释了节点应如何处理每种类型的对等消息，无论其处于什么阶段。
如果消息“我已经宣布提交» 无法接收或确认，即消息被接受或确认的概率或者- 或者，在任何情况下，任何值为 C 的选票，而不是任何其他选票，因为节点已经承诺永远不会取消。 当节点广播对提交的投票时，它将是 C 或什么都没有，具体取决于共识的进展程度。 然而，这还不足以让节点外部化 C。一些拜占庭对等点（根据我们的安全假设，其构成少于法定人数）可能会对节点撒谎。 接受并然后确认一些选票（或选票范围）使节点有信心最终将 C 外化。
SCP通过联合投票进行投票。 未显示：计时器可能随时响起，增加选票计数（并可能产生新的额外提名候选人组合）。
这就是全部！ 一旦网络达成共识，就准备好一次又一次地这样做。 在 Stellar 支付网络上，这种情况大约每 5 秒发生一次：这一壮举需要 SCP 保证的安全性和生存性。
SCP 可以通过多轮联合投票来实现这一目标。 联合投票是通过仲裁切片的概念实现的：每个节点决定信任的对等点集合，作为其（主观）仲裁的一部分。 这种配置意味着即使在具有开放成员资格和拜占庭欺骗的网络中也可以达成共识。
进一步阅读
- 原始SCP白皮书可以找到 和 草案实施规范。
- SCP 协议的原作者 David Mazier 以简化（但仍然是技术性的）方式对其进行了解释。 .
- 您可能会惊讶地发现本文中没有“挖矿”或“工作量证明”等术语。 SCP 没有使用这些方法，但其他一些共识算法却使用了这些方法。 赞恩·威瑟斯彭 (Zane Witherspoon) 写道： .
- 一个在一轮 SCP 中达成共识的简单网络。
- 对于对 SCP 实现感兴趣的读者：请参阅 ，由 Stellar 支付网络使用，或 ，我写这篇文章是为了更好地理解 SCP。
来源： habr.com