江苏龙网

  1. 首页 > 人文 > >

中年技术简述 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）共识算法 ， 就不可避免地提到分布式系统的网络模型和故障模型 。 对于网络模型大家都比较熟悉 ， 就不多做介绍了 ， 这里重点介绍一下故障模型 ， 下面我们使用较为广泛的一种分类方法 。
中年技术简述 BFT 共识算法特性与优化方法
本文插图
图 1 分布式系统的故障模型
中年技术简述 BFT 共识算法特性与优化方法
本文插图
实际可分为 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 共识算法的最直接的优化方向 。
典型的两阶段方案
中年技术简述 BFT 共识算法特性与优化方法


推荐阅读


上一篇：白小白的衣橱|张柏芝穿搭有“心机”，身穿牛仔背带裤休闲减龄，哪像3个娃的妈

下一篇：上海嘉定|全市首创！嘉定推出的“学习强国”移动学习机，你体验了吗？