Pi Network细谈共识算法，联邦拜占庭协议（FBA）和恒星共识协议（SCP）

Admin

2021-07-16 8865 0条评论

拜占庭将军问题

提到共识算法，不得不提到这个经典问题，共识算法都在想办法完美地解决拜占庭将军问题，先来看下什么是拜占庭将军问题。

1982年，图灵奖获得者莱斯利 · 兰伯特（Leslie Lamport）发表了论文《拜占庭将军问题》，从此，关于如何在分布式系统中有节点被故意破坏的情况下达成共识的讨论，延续至今，尤其是区块链技术的出现，让这种讨论更加热烈。

拜占庭将军问题，在莱斯利的论文中涉及到9位将军，相当复杂，我们简化地举一个例子来理解：A、B两支军队从东西两侧将要进攻敌方城市，各自一名将军，两名将军为了同时发动总攻，需要派出信使进行沟通合适的统一时间。但两军之间的必经之路上有一支敌方军队，信使必须来回穿过地方军队才能让A和B军队顺利沟通。而信使在穿越敌军的过程中有着很多种不同的问题出现方式：信使压根没能通过，通过一次返回的时候被截杀，顺利返回后需要做出确认收到的回复，以保证另一位将军不再担忧，又一次穿越敌军，如果信使是叛徒传递虚假情报呢等等问题......这中间由于沟通的信息增加，涉及到不确定性就越多。两位将军不能保证在有限的时间内确认信息已经传递给彼此。

还以莱斯利论文中的原型为基础，如果将军们在存在叛徒的情况下仍然达成一致，这种情况被成为“拜占庭容错”。反映到区块链之中，我们可以把将军们看做不同的节点，信使看做网络情况，而叛徒就是出错的节点甚至是恶意投票节点。

拜占庭协议（传统协议）

主要特性包括中心化和任意行为容忍，拜占庭协议中要求参与方都要达成一致，所以就必须要对每个节点进行验证，不会让随便任何人都能加入参与进来，以保证一致性的顺利达成，这就形成了一个中心化系统，这是非联邦拜占庭协议的普遍要求。它也只保证了这个中心化系统之下的分布式共识，同时要忽略掉任意非理性行为造成的“拜占庭错误”。

拜占庭协议是恒星网络（Stellar）最初的基础，同时也是竞争对手Ripple Labs所使用的系统，这种系统我们称之为拜占庭容错系统（BFT）。直到2014年9月恒星出现网络问题，12月就开始着手进行协议的更新升级。

联邦拜占庭协议（FBA）

我们都知道Pi Network白皮书中提到：Pi采用了恒星共识协议为解决方案，而恒星共识协议使用了联邦拜占庭协议的新颖机制来确保对分布式分类账的准确性和可信赖性。所以我们先来了解联邦拜占庭协议，这块内容很生涩，但是了解之后再去看恒星共识协议这样的顺序就能看的更方便一些。

联邦拜占庭协议全称Federated Byzantine Agreement，简称FBA，在Gawen白皮书解读那期内容中，对于几个小概念解释的比较模糊，我们详细聊一聊联邦拜占庭协议。一个FBA系统通过商定来确定应该应用哪些更新，节点之间得以避免矛盾、不可调和的状态。它是通过唯一的插槽来识别每个更新的，从中可以推断更新之间的依赖关系，比如，插槽可以是顺序应用日志里的连续编号位置。FBA系统运行一个达成一致的协议，确保节点在插槽内容上达成一致，那么节点X可以在Y插槽中应用Z更新，因为X节点已经安全应用了所依赖的所有插槽的更新，同时X节点相信其他正常运行的节点都会就Y插槽中应用Z更新达成一致。

在达成一致的协议中，节点交换关于插槽声明的消息。当一个节点获取到一组充分的节点声明消息时，它假定没有任何功能节点会与这个消息矛盾，这时候就形成了一个集合，而我们把这样的集合称作仲裁切片。当然了，这只是一个切片，考虑到节点失败的情况，为了取得进展，节点可能有多个切片，这中间任何一个都足以说服节点相信这个消息。FBA系统是由松散的节点联盟组成，每个节点都选择了一个或者多个切片。仲裁是一组足以达成协议的节点，而仲裁切片是一个特定协议节点具有说服力的仲裁片的子集。

恒星共识协议（SCP）

http://Stellar.org的首席科学家David Mazières教授的论文介绍了恒星共识协议（Stellar Consensus Protocol，SCP），同时它也是联邦拜占庭协议第一个安全可证的实现成果，所以说恒星共识协议是基于联邦拜占庭共识算法的，SCP让恒星网络无需依赖封闭系统即可完成共识。

恒星共识协议具有四个属性：分散控制、灵活信任、低延迟、渐进安全。它保证了面对非理性行为时的安全性，又只需有限的计算资源，降低了准入门槛；用户可以自由信任自认合适的任意组合参与方；而安全性建立在数字签名和散列家族的基础上，那么密码长度可以随着攻击者的计算能力增长而增加。

在一组节点中，如果每个节点对同一个插槽所对应的值保持相同的观点，那这些节点享有安全性。反过来讲，如果我认为一号插槽的值是m，你认为一号插槽的值是n，并且m≠n，那么我和你之间不具有安全性。