共识机制演绎(6):BFT和它的xBFT们(下)

unitimes.media

全球视角,独到见解

“融合BFT及DPOS的共识协议——Tendermint”

2017年,Cosmos在其白皮书中应用了一种全新的部分同步运作的拜占庭容错共识协议Tendermint1。事实上,Tendermint开源项目始于2014年,旨在解决比特币工作量证明算法的速度、可扩展性以及环境问题。

Tendermint协议源自DLS共识算法,并具备简易性、高性能以及分叉责任制等优点。协议要求有一组固定的验证者,其中每个验证者通过公钥进行身份验证。这些验证者会尝试在某个区块上同时达成共识。在共识过程中,每个区块的共识轮流进行,每一轮都会有一个提议者,由他们来发起区块。此后,验证者分阶段就是否接受该区块,或者是否进入下一轮做出投票。Tendermint采用由绝对多数选票(超过2/3)敲定的最优拜占庭容错算法,以及锁定机制来保证算法的安全性。

为了便于后续讲述,我们先做几项基本约定:

1. 每一个决定下一个区块(假定区块高度为H)的共识过程均包含至少一轮(round)。

2. 新高度(NewHeight),提议 (Propose),预投票(Prevote),预提交(Precommit)和提交(Commit) 分别代表状态机在每一轮的状态,我们不妨称之为步或阶段(step)。

3. 如果我们说某个节点处于(H,R,S)或者(H,R),那就表示这个节点正处于区块高度H,轮次R内的第S步。

4. 一个包含超过2/3的对应于处在(H,R)的特定区块或者(空区块)的预投票的集合,我们称之为锁变化证明(Proof-of-lock-change),简称PoLC。

每一个共识的轮次包含三个常规步骤(提议,预投票和预提交)以及两个特殊步骤(提交和新高度)。这些步骤的顺序如下:

新高度–>(提议–>预投票–>预提交)–>提交–>新高度–>…

一般而言,每一次共识的达成只需要一轮,但下述因素可能会造成共识失败,以致于需要多个轮次:

表1 造成共识失败的因素

这些问题有的将通过进入下一个回合或者替换提议者的方式得到解决,有的将通过在接下来的回合以提高该回合的超时参数来缓解。

总结而言,Tendermint共识算法流程如下:

表2 Tendermint共识流程

上述普通退出状况包含:

表3 普通退出状况

需要注意的是,在Tendermint算法中,如果遇到对同一特定区块的同意及否决信息同时超过2/3的情况,需要启用外部的维护机制去核查是否存在超过1/3的验证节点伪造签名或者投出双重选票。文中还给出了关于Tendermint共识协议安全性及活跃性的证明,以及相关的替代算法,感兴趣的读者可以参考文末附上的参考文献。

至此,关于BFT及其xBFT们的介绍暂时告一段落。下一节,我们一起来谈谈另一庞大的体系——区块链与它的PoX们。

本文作者:喏呗尔

参考文献

[1] Jaekwon. Byzantine Consensus Algorithm[EB/OL]//https://github.com/tendermint/tendermint/wiki/Byzantine-Consensus-Algorithm,2017

[2] Cynthia Dwork,Nancy Lynch,Larry Stockmeyer. Consensus in the presence of partial synchrony[J]//ACM,1988,35(2):288-323

国际金融科技新媒体和社区平台

UNITIMES

网址 : unitimes.media

新浪微博:@Unitimes

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180519G0V7WJ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券