欢迎您访问科普小知识本站旨在为大家提供日常生活中常见的科普小知识,以及科普文章!
您现在的位置是:首页  > 经济金融

硬核丨如何改进 BFT 共识算法?

科普小知识2022-04-28 13:14:49
...

通信复杂度问题

PBFT是基于三阶段投票即可达成共识的协议。prepare和commit阶段中,都需要每个节点广播自己的prepare或commit消息,因此通信复杂度是。

view change过程中,需要所有的副本节点发现主节点time out,每个副本节点会广播view change消息,所有副本节点对view change达成共识后,新的主节点会把这个消息广播出去宣布view change。由于view change消息是P2P广播,且每个view change消息中都包含达到prepared状态的请求,因此view change的验证复杂度是。

高达的复杂度无疑给PBFT的共识效率带来了严重的影响,极大地制约了PBFT的可扩展性。

BFT协议的优化

那么如何把的通信复杂度降到,提高共识效率,是BFT共识协议在区块链场景中面临的挑战。针对BFT共识效率的优化方法,共有以下几类:

1. 聚合签名

E.Kokoris-Kogias等在其论文中提出了在共识机制中使用聚合签名的方法。论文中提到的ByzCoin[4]以数字签名方式替代原有PBFT使用的MAC将通信延迟从降低至,使用聚合签名方式将通信复杂度进一步降低至。但ByzCoin在主节点作恶或33%容错等方面仍有局限。

之后一些公链项目基于这种思想,采用EC-Schnorr多签算法提高PBFT过程中prepare和commit阶段的消息传递效率。

2. 通信机制优化

PBFT使用多对多(all-to-all)的消息模式,因此需要的通信复杂度。

SBFT(Scale optimized PBFT)[5]提出了一个使用收集器(collector)的线性通信模式。这种模式下不再将消息发给每一个副本节点,而是发给收集器,然后再由收集器广播给所有副本节点,同时通过使用门限签名(threshold signatures)可以将消息长度从线性降低到常数,从而总的开销降低到。

Tendermint[6]使用gossip通信机制,乐观情况下可以将通信复杂度降低到。

3. view-change流程优化

所有的BFT协议都通过view-change来更换主节点。PBFT,SBFT等协议具有独立的view-change流程,当主节点出问题后才触发。而在Tendermint、HostStuff[7]等协议中没有显示的view-change流程,view-change流程合入正常流程中,因此提高了view-change的效率,将view-change的通信复杂度降低。

Tendermint将roundchange(和viewchange类似)合入正常流程中,因此roundchange和正常的区块消息commit流程一样,不像PBFT一样有单独的viewchange流程,因此通信复杂度也就降为。

HotStuff参考Tendermint,也将视图切换流程和正常流程进行合并,即不再有单独的视图切换流程。通过引入二阶段投票锁定区块,并采用leader节点集合BLS聚合签名的方式,将视图切换的通信复杂度降低到了。

4. 链式BFT

传统BFT需要对每个区块进行两轮共识,的通信复杂度可以让区块达到prepareQC,但是必须要的通信复杂度才能让区块达到commitQC。

Hotstuff将传统BFT的两轮的同步BFT改为三轮的链式BFT,没有明确的prepare,commit共识阶段,每个区块只需要进行一轮QC,后一个区块的prepare阶段为前一个区块的pre-commit阶段,后一个区块的pre-commit阶段为前一个区块的commit阶段。每次出块的时候都只需要的通信复杂度,通过两轮的通信复杂度,达到了之前的效果。

5. 流水线(Pipelining)和并行处理(Concurrency)

PBFT、Tendermint等协议具有即时确定(Instant Finality)的特性,几乎不可能出现分叉。在PBFT中,每个区块被确认后才能出下一个区块,Tendermint还提出区块锁定的概念,进一步确保了区块的即时确定性,即在某个round阶段,节点对区块消息投了pre-commit票,则在下一个round中,该节点也只能给该区块消息投pre-commit票,除非收到新proposer的针对某个区块消息的解锁证明。

这类BFT共识协议本质上是一个同步系统,将区块的生产和确认紧密耦合,一个区块确认后才能生产下一个区块,需要在块与块间等待最大的可能网络延迟,共识效率受到很大的限制。

HotStuff的Pipelining方法将区块的生产和确认分离,每个区块的最终确认需要后两个区块达到QC,也就意味着上一个区块没有完全确认(需要满足Three-Chain)的情况下可以生产下一个区块。这种方式实际上还是一个半同步系统,每个区块的产生还是需要等上一个区块达到QC。

EOS[8]的BFT-DPoS共识协议可认为是一种完全并行的Pipelining方案:每个区块生产后立即全网广播,区块生产者一边等待0.5秒生产下一个区块,一边接收其他见证人对于上一个区块的确认结果,使用BFT协议达成共识,新区块的生产和旧区块确认的接收同时进行,这极大地优化了出块效率。

(未完待续)