
David Mazier在2015年的
科学文章中首次描述了Stellar共识协议。 这是“拜占庭协议的联邦系统”,它允许分散的计算网络,而无需领导者就任何决定有效达成共识。 恒星计费网络使用恒星共识协议(SCP)维护所有成员都能看到的一致的交易历史记录。
共识协议被认为难以理解。 SCP比大多数人更简单,但仍然享有这一声誉-部分是因为错误的想法,即科学文章的前半部分专门讨论的“联邦投票”是SCP。 但是事实并非如此! 这只是一个重要的构建块,在本文的下半部分将用于创建
实际的 Stellar共识协议。
在本文中,我们简要描述了什么是“协议体系”,什么可以使其成为“拜占庭式”,以及为什么使拜占庭式体系为“联邦”。 然后,我们解释SCP文章中描述的联合投票程序,最后解释SCP协议本身。
协议系统
协议系统使一组参与者可以就某个话题达成共识,例如,午餐订购什么。
我们在星际酒店已经实施了自己的就餐安排系统:我们按照运营经理约翰所说的去订购。 这是一个简单有效的协议系统。 我们都相信约翰,并相信他每天都会找到有趣而又有营养的东西。
但是,如果约翰滥用我们的信任怎么办? 他可以单枪匹马地决定我们都应该成为素食主义者。 一两个星期后,我们可能会推翻他,并将权力移交给伊丽莎白。 但是突然之间,她爱鳄梨和凤尾鱼,并认为每个人都应该变得那样。 电源损坏。 因此,最好找到一种更民主的方法:一种确保考虑到不同偏好的方法,同时确保及时而明确的结果,以使没有人下令午餐或五个人下达不同的命令,否则讨论会持续到晚上。
解决方案似乎很简单:投票! 但这是一种误导性的印象。 谁来收集选票并报告结果? 其余的人为什么要相信他的话呢? 也许我们可以
先投票选举我们信任的领导人来领导投票,但是谁将领导这次的
第一次投票? 如果我们无法达成共识,该怎么办? 或者,如果我们同意,而这位领导人陷入会议或休病假?
在分布式计算机网络中发现了类似的问题。 所有参与者或节点都必须在某种解决方案上达成共识,例如,轮到其来更新共享文件或从处理队列中接管任务。 在加密货币网络中,节点不得不反复从有时可能会冲突的几种可能版本中选择全文的外观。 该网络协议为接收者提供了以下保证:硬币(a)有效(不是伪造的)和(b)尚未在其他地方花费。 它还可以确保他将来可以使用硬币,因为新接收者出于相同的原因将具有相同的担保。
分布式计算机网络中的任何匹配系统都必须具有容错能力:尽管出现错误(例如通信线路速度慢,节点无响应以及消息顺序不正确),它也必须给出一致的结果。
拜占庭协议体系还可以抵抗“拜占庭”错误:提供错误信息的节点,无论是由于错误还是故意破坏系统或获得某些优势。 “拜占庭”的应变能力-信任团体决策的能力,即使该团体的某些成员撒谎或以其他方式不遵守决策规则的能力-也被称为试图协调袭击
的拜占庭帝国将军的
寓言 。 安东尼·史蒂文斯(Anthony Stevens)有一个
很好的描述 。
考虑一下加密货币硬币的所有者爱丽丝(Alice),他必须在从鲍勃(Bob)购买美味的冰淇淋和支付卡罗尔(Carol)的债务之间做出选择。 也许爱丽丝想一次付两笔钱,欺骗性地花费同一枚硬币。 为此,她必须说服鲍勃(Bob)的计算机将硬币从未支付给卡罗尔(Carol),并说服Carol(Carol)的计算机从未将硬币支付给Bob(鲍勃)。 拜占庭的惯例制度使用称为
法定人数的多数规则使得这几乎不可能。 这样的网络中的节点拒绝切换到特定版本的历史记录,直到看到足够数量的对等节点(仲裁)同意这种转换为止。 一旦发生这种情况,它们将形成足够大的选举块,以迫使其余的网络节点同意他们的决定。 爱丽丝可能会让一些节点代表她撒谎,但是如果网络足够大,那么诚实节点的声音将抑制她的尝试。
仲裁需要多少个节点? 至少要有多数,或更确切地说是合格的多数,才能打击错误和欺诈行为。 但是为了计算多数,您需要知道参与者的总数。 在星际办公室或地区选举中,这些数字很容易识别。 但是,如果您的组是一个定义不明确的网络,节点可以在不与中心协调的情况下按需进入和退出网络,则您需要一个
联邦拜占庭协议系统,该系统不能从预先确定的节点列表中确定仲裁人数,而可以从不断变化且不可避免地不完整的节点中动态确定仲裁人数某个时间点的节点快照。
就扩展网络中的单个节点而言,创建仲裁似乎是不可能的,但是这是可能的。 这样的法定人数甚至可以保证分散投票的结果。 SCP白皮书显示了如何使用称为
联合投票的程序来执行此操作。
对于急躁的人
本文的其余部分详细介绍了联邦投票和Stellar共识协议。 如果您对这些细节不感兴趣,这里是该过程的一般概述。
- 节点对“被提名人”进行联邦投票。 一轮联邦投票意味着:
- 节点对任何语句投票,例如“我提议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。 一旦提案超过法定阈值,网络的其余部分就会确信所有竞争提案都会失败。 因此网络收敛到结果。
但是在联邦拜占庭式协议体系中,不仅不能有多数(因为没人知道网络的整体规模),而且多数概念通常是没有用的! 如果系统中的成员身份是开放的,那么有人可以通过简单地进行所谓的Sibyl攻击来获得多数:通过多个节点重复加入网络。 那么,为什么将切片的可传递性关闭称为
法定人数 ,又如何能够抑制竞争性报价呢?
从技术上讲,没办法! 想象一下一个由六个节点组成的网络,其中两个三元组被隔离在彼此的仲裁数量中。 第一个子群可以决定第二个子群永远不会听到的声音,反之亦然。 该网络无法达成共识(偶然的情况除外)。
因此,SCP要求网络必须具有称为“
法定人数穿越”的属性才能进行联合投票(并应用重要的商品定理)。 在具有此属性的网络上,可以建立的任何两个仲裁始终在至少一个节点中重叠。 确定网络的普遍情绪与拥有多数情绪一样好。 从直觉上讲,这意味着如果一个法定人数与语句X一致,则其他任何法定人数都无法与其他事物达成一致,因为它必然会包含已经投票支持X的第一个法定人数的某个节点。
如果网络有法定人数的交集...
...那么您可以建立任何两个仲裁...
...将始终相交。

(当然,重叠的节点在其他方面可能是拜占庭式的或坏的。在这种情况下,仲裁的交集根本无法帮助网络达成一致。因此,SCP技术论文中的许多结果都是基于明确的假设,例如网络上保留的内容为了简化起见,我们在本文的其余部分中都
隐含了这些假设)。
预期在独立节点的网络中可能有可靠的仲裁交叉似乎是不合理的。 但是,这样做有两个原因。
第一个原因是互联网本身的存在。 互联网是具有法定人数交集的独立节点网络的理想示例。 Internet上的大多数站点仅连接到其他几个本地站点,但是这些小的集合重叠得足以使每个站点都可以从特定路由上的每个其他站点访问。
第二个原因特定于Stellar付款网络(SCP的最常见用法)。 Stellar网络中的每项资产都有一个发行人,Stellar的建议要求每个发行人在网络中指定一个或多个节点来处理还款请求。 您直接或间接将这些节点包含在感兴趣的每种资产的仲裁切片中,这符合您的利益。 然后,对该资产感兴趣的所有节点的法定人数将至少在这些还款节点中重叠。 对几种资产感兴趣的节点将在其法定数量中包括各个发行者的所有还款节点,并且他们将努力将所有资产组合在一起。 此外,任何未与网络上的其他资产建立连接且不应连接的资产-这样做是为了使该网络不达到法定人数(例如,美元区域的银行有时希望与欧元区的银行和银行进行交易)来自比索区,因此他们在同一个网络上,但他们都不关心单独的儿童出售棒球卡的网络。
当然,
等待法定人数不能
保证 。 其他拜占庭协议系统的大部分复杂性在于保证了法定人数。 SCP的一项重要创新在于,它消除了共识算法本身创建仲裁的责任,并将其带到了应用程序级别。 因此,尽管联邦投票具有足够的普遍性,可以就任何问题进行投票,但实际上,其可靠性在很大程度上取决于这些价值观的广泛含义。 一些假设的用途可能不如其他人那样方便地建立连接良好的网络。
投票,接受和确认
在联邦投票回合中,节点可以选择开始对V的某个值进行投票。这意味着消息已发送到网络:“我是节点N,法定切片是Q,我投票支持V”。 当节点以这种方式投票时,他承诺不会投票反对V,也永远不会投票。
在对等节点的广播中,每个节点都可以看到其他节点如何投票。 节点收集到足够数量的此类消息后,便可以跟踪仲裁切片并尝试查找仲裁。 如果他看到法定人数也投票支持V,那么他可以继续
接受 V并将此新消息广播到网络:“我是节点N,我的法定人数Q,我接受V”。 接受比简单的投票更有力。 当节点为V投票时,它永远不会为其他选项投票。 但是,如果一个节点接受V,则Web上的任何节点都不会接受另一个选项(技术白皮书SCP中的定理8证明了这一点)。
当然,极有可能不会立即有一定数量的节点同意V。其他节点可能会投票支持其他值。 但是对于该站点,还有另一种方法可以从简单投票到接受。 N可以采用W的不同值,即使它没有投票赞成,也没有看到法定人数。 要决定改变声音,只要看到一
组接受W的阻塞节点就足够了。阻塞集是N个仲裁的每个切片中的一个节点。顾名思义,它可以
阻塞任何其他值。 如果此类集合中的所有节点都接受W,则(根据定理8)将永远不可能形成具有不同值的定额,因此接受W也很安全。
节点N具有三个定额切片。
BDF是N的阻塞集:它包括N个切片中每个切片的一个节点。
BE也是N的阻塞集,因为E出现在N的两个切片中。但是阻塞集不是法定人数。如果足以使N个片中的每一个仅破解一个节点,则诱使节点N接受期望值太容易了,因此,接受该值并不是投票的终点。相反,N必须确认该值,即,查看接收该值的节点的法定人数。如果他走了这么远,那么,如SCP白皮书所证明的(在定理11中),网络的其余部分也将最终确认相同的值,因此N将以特定值结束联合投票。
联合投票。投票,接受和确认的过程是一轮完整的联合投票。《恒星共识协议》结合了许多回合,以创建一个完整的共识系统。恒星共识协议
共识系统的两个最重要的特征是安全性和生存性。如果共识算法永远不能给不同的参与者以不同的结果(鲍勃的故事永远不会与卡罗尔相矛盾),则它是“安全的”。 “活力”表示算法将始终产生结果,即不会卡住。所描述的联合投票程序在以下方面是安全的:如果一个节点确认V的值,则没有其他节点确认另一个值。但是“不确认其他含义”-这并不意味着他一定会确认某些内容。参与者可以投票支持许多不同的价值,以至于没有任何东西能达到接受的门槛。这意味着没有联邦投票。生存能力。《恒星共识协议》使用联合投票,以确保安全性和可生存性。 (SCP的安全性和生存能力的保证有理论上的限制。该设计选择了非常强大的安全保证,牺牲了生存能力的轻微减弱,但在足够的时间下,很可能会达成共识。)简而言之,该想法是对多个值进行几次联合投票,直到其中一个完全通过下面描述的SCP投票的所有阶段。, SCP , , - , , , .
.
(nomination phase), « V», , V. — , .
SCP , ,
(即用于建议值的容器)和可以为其声明提交(提交)的仲裁。如果法定人数进行投票,则其价值将作为共识。但是,在节点可以投票表决投票之前,它必须首先确认取消所有计数器值较低的投票。这些步骤-取消选票以找到可以确认提交的选票-包括对几份选票的几轮联合投票。以下各节更详细地描述了提名和投票。提名奖
在提名阶段开始时,每个节点可以自发选择值V并投票赞成“我正在提名V”的声明。此阶段的目标是通过联邦投票确认确定某个值的提名。也许有足够数量的节点投票赞成完全不同的陈述,并且没有提名可以达到采用的门槛。因此,除了广播自己的提名票外,节点还“反映”其对等方的提名。反射(echo)表示如果节点投票赞成V的提名,但看到邻居的消息投票赞成W的提名,则现在它将投票赞成V和W的提名。(并非所有对等投票都在提名期间得到反映,因为SCP包括调节这些声音的机制,简而言之,有一个从节点的角度确定盛宴的“优先级”的公式,只有高优先级节点的票数得到反映,扩展时间越长,阈值越低,因此节点扩展一系列的宴会,他的声音将体现出来。作为输入数据之一的优先级公式包括插槽号,因此一个插槽的高优先级对等体可以是另一个插槽的低优先级,反之亦然。从概念上讲,V和W的并行提名是单独的联邦投票,每个投票都能独立获得接受或确认。实际上,SCP协议消息将这些单独的声音打包在一起。尽管对提名V进行投票是一个永不反对提名V的承诺,但在应用程序级别(在本例中为SCP)中,定义了“反对”的含义。 SCP没有看到与“我要提名X”投票相矛盾的声明,也就是说,没有“我反对提名X”消息,因此节点可以投票提名任何值。这些提名中的许多提名将一事无成,但最后,该节点将能够接受或确认一个或多个值。提名人一经确认,便成为候选人。
使用联合投票提名SCP。由同级推送并由同级反映的许多“ B”值。提名候选人可能会导致几名已确认的候选人。因此,SCP要求应用程序层提供一些将候选者组合到一个复合物中的方法。(复合)。联合方法可以是任何东西。最主要的是,如果确定了此方法,则每个节点将合并相同的候选者。在午餐投票系统中,“协会”可以简单地表示拒绝两名候选人之一。 (但以确定性的方式:每个节点必须选择相同的值进行重置。例如,按字母顺序进行的较早选择)。在对交易历史进行投票的恒星支付网络中,将两个提议的提名人合并包括合并他们所包含的交易以及两个时间戳中的最后一个。SCP的技术描述证明了(定理12),在扩展阶段结束时,网络最终收敛到了单个组合。但是有一个问题:联合投票是异步协议(如SCP)。换句话说,节点不是在时间上协调,而是仅根据它们发送的消息进行协调。从节点的角度来看,扩展阶段何时结束还不清楚。而且,尽管所有节点最终都将到达同一合成节点,但是它们可以沿着这条路径选择不同的路线,并在此过程中创建不同的合成候选者,并且它们永远无法确定哪个节点是最终的。但这是正常的。提名只是准备。最主要的是限制候选人的数量以达成投票过程中达成的共识。选票
时事通讯是一对<counter,value>,其中counter是一个以1开头的整数,value是提名阶段的候选者。这可以是节点自己的候选者,也可以是该节点采用的邻居候选者。粗略地说,在运行过程中,人们反复尝试通过对选票申请进行潜在的许多联邦投票,迫使该网络对某位候选人进行共识。选票中的计数器跟踪所做的尝试,计数器较高的选票优先于计数器较低的选票。如果投票<计数器,值>被卡住,将开始新的投票,现在是投票<计数器+ 1,值>。区分值很重要(例如,午餐的顺序是什么:比萨饼或沙拉),选票(一对对价)和有关选票的声明。SCP回合包括几轮联邦投票,尤其是在以下声明中:从该节点的角度来看,当它找到可以确认(即,找到接受的法定人数)声明“我声明对公告B的承诺”的公告B时,就达成共识。 从现在开始,您可以安全地按照B中指定的值进行操作-例如,下订单订购午餐。 这称为
外部化值。 一旦确认接受选票,该节点就可以确保其他任何节点都已将相同的值外部化,或者肯定会在将来提交该值。
尽管从概念上讲,许多联合投票会针对许多不同的投票进行申请,但由于每个消息都封装了许多投票,因此它们不会交换太多消息。 因此,一条消息立即促进了许多联邦投票的状态,例如:“我接受从<min,V>到<max,V>范围内的投票委员会”。
术语“准备”和“提交”是什么意思?
当节点确信其他节点不会进行具有不同值的投票时,该节点将投票进行投票。 确信这是准备声明的目的。 表示“我准备提交公告B”的投票表示承诺提交的公告绝不会少于公告B,也就是说,计数器的计数器要低(SCP要求公告中的值具有一定顺序。如果N1 <N2,并且N1 = N2并且V1 <V2),则公告<N1,V1>小于<N2,V2>。 这些较小的选票在筹备投票中被“中止”,而B被认为是“准备中”。
为什么“我准备提交公告B”意味着“我保证永远不会提交少于B的选票”? 因为SCP将中止定义为与提交相反。 投票准备投票还意味着投票取消其他一些投票,而且正如我们前面所讨论的,对一件事进行投票是一个永不反对的承诺。
在广播提交之前,站点必须首先找到公告,它可以确认已准备好。 换句话说,他对“我已经准备好投稿B”进行了联邦投票,也许是针对许多不同的投票,直到他找到一个接受法定人数的投票。
投票选票从哪里来? 首先,节点广播<1,C>的投票准备,其中C是在提名阶段产生的复合候选。 但是,即使在开始准备投票之后,提名也可能导致其他候选人的出现,这些候选人将成为新的选票。 同时,同位体可能具有不同的候选者,他们可以形成一个阻止集,接受“我准备提交B2公告”,这也会说服节点也接受它。 最后,有一个超时机制,可以在当前选票被卡住的情况下,针对具有更高计数器的新选票生成新一轮的联合投票。
节点一旦找到可以确认的公告B,便会广播新消息“公告B提交”。 此投票告诉对等节点,该节点将永不放弃B。实际上,如果B是投票<N,C>,则“ Commit Bulletin <N,C>”表示无条件同意投票以投票赞成<N, C>到<∞,s>。 如果其他节点仍处于协议的早期阶段,则此附加值可帮助其他节点赶上提交。
在这一阶段,值得再次强调这些是异步协议。 仅仅因为一个节点为一次提交发送投票并不意味着它的对等节点也这样做。 他们中的一些人仍然可以对申请进行投票以准备投票,而其他人可能已经将其含义外化了。 SCP解释了节点无论其阶段如何应如何处理每种类型的对等消息。
如果消息“我声明提交<N,C>”不能被接受或确认,即接受或确认消息<N + 1,C>或<N + 2,C>的可能性-或在任何情况下,任何公告的值为C,而不是其他任何值,因为该节点已经承诺永远不会取消<N,C>。 到节点广播该提交的投票时,根据共识进行的程度,它将为C或为零。 但是,这还不足以使节点将C外部化。一些拜占庭式的(宴(根据我们对安全性的假设,不到法定人数)可能在于该节点。 接受并确认特定的选票(或选票范围)是使节点有信心最终将C外部化的原因。
SCP通过联合投票进行投票。 未显示:在任何时候计时器都可以工作,增加选票中的计数器(并可能从其他提名的候选人中产生新的复合材料)。仅此而已! 一旦网络达成共识,就可以一次又一次地做好准备。 在Stellar计费网络上,这种情况大约每5秒发生一次:这项壮举既需要安全性,又需要生存能力,这要由SCP保证。
SCP可以依靠几轮联合投票来实现这一目标。 多亏了仲裁切片的概念,联合投票才成为可能:每个节点决定信任作为其(主观)仲裁的一部分的对等节点集。 这种配置意味着即使在具有开放成员资格和拜占庭欺骗的网络上,您也可以达成共识。
进一步阅读
- SCP的原始技术文档可以在这里找到, 这是其实施的规范草案。
- SCP协议的原始作者David Mazier 在这里进行了简化(但从技术上来说)。
- 您可能对没有在本文中找到“采矿”或“工作量证明”一词感到惊讶。 SCP不使用这些方法,但其他一些共识算法则使用。 赞恩·威瑟斯彭(Zane Witherspoon) 对共识算法进行了无障碍评论 。
- 在一个完整的SCP轮次中达成共识的简单网络的分步说明 。
- 对于对SCP实现感兴趣的读者:请参阅Stellar付款网络使用的C ++代码 ,或为更好地理解SCP而编写的Go代码 。