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

加密谷Live
媒体专栏
热度: 4631
PBFT是基于三阶段投票即可达成共识的协议。prepare和commit阶段中,都需要每个节点广播自己的prepare或commit消息。


通信复杂度问题



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协议达成共识,新区块的生产和旧区块确认的接收同时进行,这极大地优化了出块效率。


(未完待续)


参考

[4] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” 2016.

[5] Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, Alin Tomescu,“a Scalable and Decentralized Trust Infrastructure”,2018.

[6] C. Unchained, “Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain.” [Online]. Available: https://blog.cosmos.network/tendermint-explained-bringing-bft-based-pos-to-the-public-blockchain-domain-f22e274a0fdb.

[7] M. Yin, D. Malkhi, M. K. Reiterand, G. G. Gueta, and I. Abraham, “HotStuff: BFT consensus in the lens of blockchain,” 2019.

[8] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.



共识算法

共识算法

共识算法

声明:本文为入驻“火星号”作者作品,不代表火星财经官方立场。
转载请联系网页底部:内容合作栏目,邮件进行授权。授权后转载时请注明出处、作者和本文链接。 未经许可擅自转载本站文章,将追究相关法律责任,侵权必究。
提示:投资有风险,入市须谨慎,本资讯不作为投资理财建议。
免责声明:作为区块链信息平台,本站所提供的资讯信息不代表任何投资暗示,本站所发布文章仅代表个人观点,与火星财经官方立场无关。鉴于中国尚未出台数字资产相关政策及法规,请中国大陆用户谨慎进行数字货币投资。
语音技术由科大讯飞提供

评论0