一文读懂Giskard共识协议

PlatON的Giskard共识协议由概率性权益证明PPoS(PlatON proof of stake)和Giskard拜占庭容错协议-Giskard BFT(Giskard Byzantine Fault Tolerance) 组成。PPoS使用质押、委托、随机选取的形式选出参与共识的验证节点，Giskard BFT使用类BFT算法实现区块的生产和验证。本文我们将简单介绍PPoS共识和BFT理论，并分析PBFT算法特性及PBFT存在的问题，其后重点分析Giskard BFT借鉴PBFT、Tendermint、Hotstuff等共识协议的演进之路。区块链技术本质脱离不开传统分布式系统。分布式一致性算法是传统分布式系统的一大难题，经过长期的研究和应用，诞生了如paxos、raft、zab等成熟安全的算法。相比于传统的分布式系统，公共区块链中没有中心化的假设，任何节点都可以加入并自由访问所有的数据，因此公链中不可避免会存在恶意节点。所以，区块链系统中的共识机制不仅需要支持CFT(Crash fault tolerance) 还需要支持BFT(Byzantine Fault Tolerance) 。BFT是一个已经被研究得比较透彻的理论，PBFT是其中最为著名的实现算法，目前广泛应用于各大区块链系统中。PlatON的Giskard共识协议由概率性权益证明PPoS(PlatON proof of stake)和Giskard拜占庭容错协议-Giskard BFT(Giskard Byzantine Fault Tolerance) 组成。PPoS使用质押、委托、随机选取的形式选出参与共识的验证节点，Giskard BFT使用类BFT算法实现区块的生产和验证。PPOS——验证节点选取在介绍PPoS之前，我们先科普一下PoS，目前PoS共识方案可以分为四类：PoS共识概述Chain-Based这是早期的一代PoS。根据持有token的数量伪随机地选择验证人进行区块生产。其中还有PoS+PoW方案，一般是PoW出块，通过PoS选择验证人进行验证，以太坊的Casper1.0也是一种混合PoS/PoW的方案，作为其从PoW转换到PoS的中间方案。DPoS (Delegated Proof of Stake)委托权益证明。每个token持有人可以把权利委托给部分代表，由代表参与区块的生产和验证。VRF (Verifiable Random Function)可验证随机函数用于验证节点的随机选取。目前，Dfinity、Cardano和Algorand等采用了这种方案。BFT (Byzantine Fault Tolerance)拜占庭容错。选出验证节点后通过运行BFT协议经过多轮投票确认区块完成共识。目前Tendermint、Stellar、Ontology、Zilliqa、NEO等都是采用这类共识算法。PlatON的共识方案PPoS，也就是我们常说的概率性权益证明，它本质是一种PoS共识方案，根据节点的权益绘制成二项分布累积分布曲线，并使用VRF随机选取验证节点。PPoS解决的关键核心点在于验证人的选取不仅与节点权益的大小有关，还兼具随机性，也就是说选出的验证节点不一定是权益最高的节点，权益较低的节点也有一定的选中概率。随机性算法可以保证选取的结果不可预测、不可操控且公平可靠。PPoS本质上是PoS+VRF方案的结合。简单总结就是：PPoS提供了一种尽可能公平、随机地从众多参与节点中选取出若干验证节点的方案。BFT——区块共识验证节点被选举出来之后，运行共识协议进行区块生产和验证，整个过程需要节点之间相互协作，对区块进行相互确认，得出一致结论，达成区块共识。上文中提到，区块链中的共识算法不仅需要考虑Crash节点，还需要考虑Byzantine节点。什么是拜占庭节点？我们从一个故事说起。拜占庭将军问题拜占庭罗马帝国国土辽阔，为了达到防御目的，每块封地都驻扎一支由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。 在战争的时候，拜占庭军队内所有将军必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定影响将军们达成一致共识。在已知有将军是叛徒的情况下，其余忠诚的将军如何达成一致协议的问题，这就是拜占庭将军问题。拜占庭将军问题所描述的是好的将军不知道其他将军是好的，还是坏的，但所有好的将军的目的是：行动一致，共同进退。所以，他们需要在策略上达成一致。看到这里，相信大家对拜占庭节点也有了初步的理解。简单地说，在区块链系统中存在以下两类错误：要让这个问题有解，还需要先引入一个概念——分布式网络模型，按照分布式系统理论，分布式系统的网络模型分为三类：拜占庭将军问题的解决，有一个十分重要的前提，那就是通信信道必须是可靠的。如果信道不能保证可靠，那么拜占庭问题无解。这也就是FLP不可能原理，即在异步网络模型假定下，共识算法不可能同时满足安全性（safety）和活跃性（liveness），也就是说，在一个不可靠的通信链路上试图通过通信以达成一致是基本不可能或者十分困难的。至于什么是安全性和活跃性，我们后面再说。其实，拜占庭将军问题最早是由Leslie Lamport在1982年发表的论文《The Byzantine Generals Problem》提出的，他证明了在将军总数大于3f，背叛者为f或者更少时，忠诚的将军可以达成命令上的一致，即3f+1<=n。而Miguel Castro和Barbara Liskov在1999年发表的论文《Practical Byzantine Fault Tolerance》中首次提出PBFT算法，该算法容错数量也满足3f+1<=n。BFT是一个已经被研究得比较透彻的理论，它告诉我们，基于部分同步网络模型的假定，在不超过三分之一的故障节点和作恶节点情况下，非拜占庭节点之间可达到最终一致性。PBFT是其中最为著名的实现算法，意为实用拜占庭容错算法。目前，区块链的共识算法大多都是基于BFT的实现。Giskard BFT也是由PBFT演进而来。PBFT算法在区块链共识的应用PBFT算法被广泛应用于各类区块链共识，它不仅解决了共识过程中可能发生的拜占庭节点问题，同时也使系统始终能够保持两个属性：安全性（safety）和活跃性（liveness）。我们直接以PBFT算法在区块链共识的应用为例，总结算法的核心流程：PBFT的共识过程由上图可知，PBFT是一个典型的三阶段提交算法：看到这里，也许你会有以下疑问：为什么不同阶段所需要的签名个数不同对于prepare和commit阶段来说，考虑最坏的情况：我们假设收到f个是正常节点发过来的签名，也有f个是恶意节点发过来的，那么，第2*f+1个签名只可能是正常节点发过来的（因为我们限制了最多只有f个恶意节点）。由此可知，「大多数」正常的节点还是可以让系统工作下去的。所以2*f+1这个参数和n>=3f+1的要求是逻辑自洽的。而在prepare阶段，节点0发出消息即可认为确认消息，所以prepare阶段只需收集2*f个签名。为什么只有两阶段消息不能达成一致性只有pre-prepare和prepare两个阶段消息是无法达成一致的。举例说明，假设没有commit阶段，节点1在prepare阶段收集满2*f的签名后，达到Prepared状态，然而这个Prepared仅是节点1的一个局部视角，不是全局一致，此时节点1不能保证其余节点都达到Prepared状态，如果少于f个非拜占庭节点成为Prepared状态，节点1又确认了该消息，那么系统就出现了不一致。为什么三阶段消息可以达成一致性说到这里，其实就很好理解为什么三阶段消息可以达成一致性，某节点收集满2*f+1的Commit包意味着有f+1个非拜占庭节点达成了Prepared状态，也就意味着「多数」节点已经认同了消息。下面，我们再介绍PBFT的视图和视图切换流程。PBFT共识算法使用视图view记录每个节点的共识状态，相同视图节点维护相同的Leader和Replicas节点列表。当Leader出现故障，为了保证协议活跃性（liveness），会发生视图切换，若视图切换成功(至少2*f+1个节点达到相同视图)，则根据新的视图选出新leader 。话不多说，直接上视图切换流程图：PBFT的视图切换流程PBFT的视图切换流程也分为三个阶段：通过对共识流程的分析，相信大家对view切换流程都能够很好地理解，这里我们不再赘述。接下来我们着重分析PBFT算法存在的问题，以及Giskard BFT改进优化。PBFT存在的问题通过对PBFT共识流程三阶段的详细分析，可以看到消息传输的开销很大。系统在尝试达成状态共识时，涉及到n个节点都需要广播消息到n-1个其它节点，因此算法通信复杂度达到 O(n²)，在节点数目为1000的情况下所需要交换的通信量为1,000,000。有实验得出当节点数量超过20时，算法的性能会急剧下降。另外，在PBFT选举Leader的过程中，有可能经过多轮交互，选举出的Leader一直长时间运行，直到Leader节点出现故障才发起视图切换流程。但在区块链系统中，视图view表示一个共识单元，共识过程由一个接一个的view组成，每个view中由一个确定的提议人来主导共识协议，产生区块，其余验证人对区块进行投票签名达成共识。因为节点产生区块与利益相关（如记账权，区块奖励等），因此需要频繁地更换出块节点，也就是需要频繁地切换视图view，这势必会带来巨大的网络资源消耗。Giskard BFT共识优化所以我们基于BFT协议，结合区块链的特性，主要围绕着以下几点进行协议优化，设计了Giskard BFT 。所有的BFT协议都通过view-change来更换主节点。PBFT，SBFT等协议具有独立的view-change流程，当主节点出问题后才触发。而在Tendermint、HotStuff等协议中没有显式的view-change流程、view-change流程合入正常流程中，因此提高了view-change的效率，将view-change的通信复杂度降低。Giskard BFT也是基于view的的共识协议，为降低通讯复杂度，Giskard BFT也没有显式的view change流程，而是把这个流程和正常出块流程结合。Giskard BFT约定每个提议节点在本视图内连续产生10个区块，并且每个区块都达成QC（Quorum Certificate，表示节点收到针对该区块的2*f+1个签名）状态后，则自动切换到下一个view ，不需要单独的view-change投票流程。下图是显式的ViewChange流程，可以看到它并没有类似PBFT中的view-change-ack和new-view阶段，这两个流程被后续的prepareQC(n)进行代替。Giskard BFT viewchange投票流程总结一下，view-change流程优化的两个重点：应用BLS聚合签名为了进一步减少消息通讯量，我们采用了聚合签名技术。业界主流的聚合签名方案是BLS聚合签名。BLS聚合签名是在BLS签名方案基础上的扩展方案。在Giskard BFT中，我们把针对block和view-change消息的多个节点签名聚合成一个签名，可以简单地理解为：把多个节点的一段很长的签名「压缩」为一个签名。这种做法极大地降低了通讯量，对提高协议的通信效率也起到了很大的作用。区块生产和验证并行化此处优化是Giskard BFT的独到创新之处。这里的并行指的是：区块生产和区块验证的并行化。上文提到，Giskard BFT是基于视图view的共识协议，每个提议节点在本视图内连续产生10个区块，并行流程如下：这种做法极大提高出块速度，也提高了系统的共识性能。引进pipeline方式对区块进行确认在传统BFT主导的区块链系统中，每个区块的共识通常都需要经历明确的Pre-Commit和Commit阶段才最终确认：Giskard BFT中的每个区块只有Prepare投票，没有明确的Pre-Commit和Commit阶段，那么区块如何达到最终的确认呢？Giskard BFT可看作Pipeline版本的BFT ，每个prepareQC都是对前面区块更高阶段的确认。Giskard BFT 的区块确认流程如图所示prepareQC(2)作为Block(1)的Pre-Commit阶段prepareQC(3)作为Block(1)的Commit阶段，Block(2)的Pre-Commit阶段。简单来说，就是「省略」了PBFT的Commit阶段，这里读者可能有疑虑：前文不是明确给出结论，必须通过三阶段消息才能达成一致性？其实Giskard BFT不是真的没有Commit阶段，而是结合区块链特性，将下一个区块的QC状态作为上一个区块的Commit间接确认。Giskard BFT结合区块链的链式结构，引进pipeline方式对区块进行确认，使得协议变得简洁而优美，能够很好地进行流程化作业，提高了协议的性能，另外也对协议的可扩展性留足了设计空间。结语目前，应用了Giskard共识协议的PlatON测试网、主网和Alaya网络都已经长时间稳定、高效运行，它的安全性（safety）和活跃性（liveness）得到了充分的验证，同时Giskard共识对解决系统过于中心化，降低网络通信复杂度、消息复杂度，提升共识效率以及整个区块链的交易处理性能所起到的作用毋庸置疑。在后期的协议版本中，我们将继续深入优化：验证人的选取不仅采用VRF，还计划结合可验证秘密分享PVSS、BLS等密码算法进一步增加随机性；引入分组共识再次提升算法的可扩展性，以高效支持更多的验证节点加入，增加网络的安全性和容错性。