PlatON的Giskard共识协议由概率性权益证明PPoS(PlatON proof of stake)和Giskard拜占庭容错协议-Giskard BFT(Giskard Byzantine Fault Tolerance) 组成。PPoS使用质押、委托、随机选取的形式选出参与共识的验证节点,Giskard BFT使用类BFT算法实现区块的生产和验证。

本次专题,我们会做两期技术科普。第一期简单介绍PPoS共识和BFT理论,并分析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提供了一种尽可能公平、随机地从众多参与节点中选取出若干验证节点的方案。

针对验证人选取的随机性问题,我们也做了专题研究,请参看《PoS共识中的验证人选取》一文:

【技术云图】PoS共识中验证人选举的随机方案(上)

【技术云图】PoS共识中验证人选举的随机方案(下)

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)。

安全性:在Crash节点和Byzantine节点两类错误发生时,共识系统不能产生错误的结果。在区块链中,指的是不会产生双重花费和分叉。

活跃性:系统一直能持续产生提交,在区块链中,指的是共识会持续进行,不会卡住。假如一个区块链系统的共识不可持续,那么系统无法响应客户端新的交易请求,也就是不满足liveness。

我们直接以PBFT算法在区块链共识的应用为例,总结算法的核心流程:

PBFT的共识过程

由上图可知,PBFT是一个典型的三阶段提交算法:

pre-prepare(预备阶段):各节点负责接收区块、执行区块,产生区块投票签名,开始广播签名给所有共识节点

prepare(准备阶段):各节点负责收集签名,某节点收集满2*f的签名后,表明自身达到可以提交区块的状态,开始广播Commit包

Commit(提交阶段):各节点负责收集Commit包,某节点收集满2*f+1的Commit包后,直接将本地缓存的最新区块提交到数据库

看到这里,也许你会有以下疑问:

为什么不同阶段所需要的签名个数不同

对于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-change:各副本节点(Replica) 认为主节点(Primary)有问题时,会向其它节点发送view-change消息

view-change-ack:各节点接收到2*f+1 个view-change消息后,选举当前存活的节点编号最小的节点成为新的主节点,并向该节点发送view-change-ack消息

new-view:当新的主节点收到2*f+1个其它节点的view-change-ack消息后,向其它节点广播new-view消息。注意:从节点不会发起new-view事件

通过对共识流程的分析,相信大家对view切换流程都能够很好地理解,这里我们不再赘述。下篇我们着重分析PBFT算法存在的问题,以及Giskard BFT改进优化。

小结

本期科普,简单介绍了PoS共识方案的发展,分析了PPoS共识和BFT理论,并以PBFT算法在区块链共识的应用为例,详细分析了PBFT的共识流程和视图切换流程。下期,我们将基于这些技术背景,继续阐述Giskard BFT共识的优化思路。敬请期待。