（李升林）简述BFT共识算法特性与优化方法
2020年8月17日 09:01 技术简述 BFT 共识算法特性与优化方法
2020年8月17日 09:09 一文读懂 BFT 共识算法优化
撰文：李升林，矩阵元首席架构师
降低复杂度是 BFT 共识算法的最直接的优化方向，除此之外，并发优化也是重要的优化方向。
拜占庭容错问题最早由 Leslie Lamport 等学者于 1982 年在论文《The Byzantine Generals Problem》中正式提出，主要描述分布式网络节点通信的容错问题。
从 20 世纪 80 年代起，提出了很多解决该问题的算法，这类算法被统称为 BFT 算法。实用拜占庭容错（Practical BFT,PBFT）算法是最经典的 BFT 算法，由 Miguel Castro 和 Barbara Liskov 于 1999 年提出。PBFT 算法解决了之前 BFT 算法容错率较低的问题，且降低了算法复杂度，使 BFT 算法可以实际应用于分布式系统。但 PBFT 的过高的通信复杂度无疑给共识效率带来了严重的影响，极大地制约了 PBFT 的可扩展性。
分布式系统故障模型
说起拜占庭容错（Byzantine Fault Tolerance，简称 BFT）共识算法，就不可避免地提到分布式系统的网络模型和故障模型。对于网络模型大家都比较熟悉，就不多做介绍了，这里重点介绍一下故障模型，下面我们使用较为广泛的一种分类方法。
图1，分布式系统的故障模型
表1，分布式系统的故障模型说明
实际可分为 byzantine failures 和 crash failures 两大类，大数据或云计算中常用的 Paxos/RAFT 共识算法只能解决 crash failure，BFT 共识算法能解决 byzantine failure。所有 BFT 协议都有一个基本假设：节点总数大于 3f 时，恶意节点最大为 f ，诚实节点可以达成一致的正确结果。
BFT 共识算法的属性
一般来说，共识算法需要满足以下属性：
- 正确性 (Validity)：诚实节点最终达成共识的值必须是来自诚实节点提议的值。
- 一致性 (Agreement)：所有的诚实节点都必须就相同的值达成共识。
- 终止性 (Termination)：诚实的节点必须最终就某个值达成共识。
换个说法，实际上就是我们常说的安全性（Safety）和活性（liveness），其中 正确性 (Validity) 和一致性 (Agreement) 决定了安全性 (safety)，而终止性 (Termination) 就是活性（Liveness）。
- 安全性（Safety）：在故障发生时，共识系统不能产生错误的结果。在区块链的语义下， 指的是不会产生双重花费和分叉。
- 活性（Liveness）：系统一直能持续产生提交，在区块链的语义下，指的是共识会持续进行，不会卡住。假如一个区块链系统的共识卡在了某个高度，那么新的交易是没有回应的，也就是不满足 liveness。
BFT 共识一般是基于视图（View）的共识协议，View 表示一个共识单元，共识过程是由一个接一个的 View 组成。在一个 View 中，存在一个确定 Leader 来主导共识协议，View 切换时需要更换 Leader。按照 Hotstuff[1]，视图切换流程需要满足两个属性：
- 线性（Linearity）：复杂度与共识节点数呈线性关系。
- 响应性（Responsiveness）：不管网络状态如何，收到足够的响应马上进入下一步。
BFT 共识算法的优化
复杂度优化
一般来说，随着硬件资源的增加，分布式系统的处理能力能得到线性或接近线性的提升。但是区块链系统运行在 P2P 的网络条件下，所有的消息包括共识都是通过 P2P 方式广播，其通信复杂度随着节点数的增加呈线性或指数增加，处理能力也相应下降甚至停止。另外，签名认证的复杂度也是重要的衡量因素，因为产生或验证数字签名的密码学操作通常是共识协议中计算量最大的操作。
因此，降低复杂度是 BFT 共识算法的最直接的优化方向。
典型的两阶段方案
图 2 典型的两阶段共识方案
上图是典型的两阶段 BFT 共识方案，如 Tendermint[2] 和 Casper[3] 都是这种方案。在两阶段方案中，每个区块经过两轮投票后才能生产下一个区块，可保证区块的即时确认，但是在某些异常情况下存在 Liveness 问题，需要采取以下方案避免。
- 增加锁定解锁机制，简化 View Change 复杂度，但是 View Change 需要等待固定的时间 (Δ) 收集足够的提交证明，因而损失 Responsiveness，Tendermint[2] 和 Casper[3] 是这种方案。
- View Change 时带上提交证明，具备 Responsiveness，但是提高了 View Change 的复杂度， PBFT[4] 是这种方案。
Pipeline 确认
图 3 三阶段 Pipeline 共识方案
Pipeline 方案可进一步降低复杂度，一个区块经过一轮投票达成后即可进入下一个区块的共识， 但是一般需要经过后续多个区块投票达成后才能保证不可逆，TTF （Time To Finality）相对稍长。
通信机制优化
通信机制上可采用 Leader 和聚合签名进一步降低通信复杂度和通信量。下图为 Hotstuff[1] 的共识算法。
图 4 基于 Leader 和聚合签名的 Hotstuff 共识算法
视图切换（View Change）优化
视图切换一般有两种优化方法降低复杂度：
- 将视图切换流程整合到正常流程，无需独立的视图切换流程
- 采用锁定解锁机制减少提交证明，上一个 View 的提交证明无需传递给下一个 View
并行 BFT （Concurrent BFT，简称 CBFT）
典型的 BFT 算法要求交易按顺序执行，即使经过复杂度优化，吞吐量仍然还会受到较大的限制。因此 BFT 共识算法的并发优化也是非常重要的方向。
CBFT 在学术上代表一类共识算法，也一直是共识算法的重点研究方向，之前已经有很多的研究成果。Kotla 和 Dahlin[5] 通过并行化执行独立的交易来提高吞吐量，他们设计了一些规则用以确定一个交易是否依赖于其他交易。Distler and Kapitza[6] 进一步扩展了 Kotla 和 Dahlin 的工作， 引入了一种只在选定的副本子集上执行交易的方案。这个方案假设每个交易访问的状态变量是已知的，状态对象分布和对象访问是统一的。2012 年，Honglei Zhang and Wenbing Zhao[7] 提出一种 CBFT 算法，使用软件事务性内存动态地检测并发操作的依赖性。
大部分 BFT 类共识都可算作 PBFT 的变种，因此都可抽象为四个阶段：
- Prepare：提议人生产区块并广播到整个区块链网络。
- Pre-Commit：进行第一轮投票，收到 N--f 个验证人的确认签名进入下一阶段。
- Commit：进行第二轮投票，收到 N-f 个验证人的确认签名进入下一阶段。
- Decide：最终提交区块。
业界有些区块链系统在 Pre-Prapare 阶段根据交易的依赖性进行并行打包区块，有些在其他阶段进行并行处理，PlatONE 云图联盟链的 CBFT 算法在 Prepare、Pre-Commit 和 Commit 阶段进行并行处理。
PlatONE 云图联盟链的 CBFT 共识算法
PlatONE 云图联盟链的优化
图 5 PlatONE 云图联盟链的 CBFT 共识算法
PlatONE 云图联盟链的 CBFT 算法包含多个方面的优化，在降低复杂度的同时通过并行进一步提高吞吐量。
- 三阶段 Pipeline 验证：一个区块经过一轮投票达成后即可进入下一个区块的共识，经过三个区块投票达成可最终确认。
- 并行出块和验证：将出块与确认分离，在 Prepare、Pre-Commit 和 Commit 阶段进行并行处理。
- 通信优化：采用聚合签名减少通信量，也提供基于 Leader 的优化版本，进一步降低通信复杂度。
- 视图切换优化：将视图切换流程整合到正常流程，无需独立的视图切换流程。
复杂度分析
下表为各类 BFT 共识算法的复杂度分析，PlatONE 云图联盟链的 CBFT 有两个版本，广播版本具有 O(N2) 的复 杂度，Leader 版本具有 O(N) 的复杂度。
几种 BFT 共识算法复杂度分析对比
参考文档
[1] M. Yin, D. Malkhi, M. K. Reiterand, G. G. Gueta, and I. Abraham, “HotStuff: BFT consensus in the lens of blockchain,” 2019. http://arxiv.org/abs/1803.05069v4
[2] Ethan Buchman. Tendermint: Byzantine fault tolerance in the age of blockchains. PhD thesis, 2016.
[3] Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. CoRR, abs/1710.09437, 2017.
[4] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22-25, 1999, pages 173–186, 1999.
[5] R. Kotlan and M. Dahlin, “High throughput byzantine fault tolerance,” Proceedings of International Conference on Dependable Systems and Networks, 2004.
[6] T. Distler and R. Kapitza, “Increasing performance in byzantine fault-tolerant systems with on- demand replica consistency,” Proceedings of the sixth Eurosys conference, 2011.
[7] Honglei Zhang and Wenbing Zhao, "Concurrent Byzantine Fault Tolerance for Software- Transactional-Memory Based Applications", International Journal of Future Computer and Communication, Vol. 1, No. 1, June 2012.
[8] Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. Consensus in the presence of partial synchrony. J.ACM, 35(2):288–323, 1988.
[9] Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: a scalable decentralized trust infrastructure for blockchains. CoRR, abs/1804.01626, 2018.
