最早的一致性算法是“两军问题” ，两军 问题表明, 在不可靠的通信链路上试图通过通信达 成一致共识是不可能的, 这被认为是计算机通信研 究中第一个被证明无解的问题. 两军问题对计算机 通信研究产生了重要的影响, 互联网时代最重要的 TCP/IP 协议中的 “三次握手” 过程即是为解决两 军问题不存在理论解而诞生的简单易行、成本可控 的 “工程解”. 分布式计算领域的共识问题主要研究在一组可能存在故障 节点、通过点对点消息通信的独立处理器网络中, 非 故障节点如何能够针对特定值达成一致共识. 这就是后来著名的“拜占 庭将军问题”，提出了基于口头消息和基于签名消 息的两种算法来解决该问题. 分布式共识算法可以分为两 类, 即拜占庭容错和非拜占庭容错类共识. 早期共识 算法一般为非拜占庭容错算法, 例如广泛应用于分 布式数据库的 VR 和 Paxos, 目前主要应用于联盟 链和私有链; 2008 年末, 比特币等公有链诞生后, 拜 占庭容错类共识算法才逐渐获得实际应用. 1985 年, 迈克尔 · 费舍尔 (Michael Fisher)、 南希 · 林奇 (Nancy Lynch) 和迈克尔 · 帕特森 (Michael Paterson) 共同发表了论文 “Impossibility of distributed consensus with one faulty process”[11]. 这篇文章证明: 在含有多个确定性进程的 异步系统中, 只要有一个进程可能发生故障, 那么就 不存在协议能保证有限时间内使所有进程达成一致. 按照作者姓氏的首字母, 该定理被命名为 FLP 不可 能定理, 是分布式系统领域的经典结论之一, 并由此 获得了 Dijkstra 奖. 需要说明的是, VR 和 Paxos 算法均假 设系统中不存在拜占庭故障节点, 因而是非拜占庭 容错的共识算法.
首次提出了工作量 证明思想是用来解决垃圾邮件问题. 该机制要求 邮件发送者必须算出某个数学难题的答案来证明其 确实执行了一定程度的计算工作, 从而提高垃圾邮 件发送者的成本.用拜占 庭容错算法 (Practical Byzantine fault tolerance, PBFT)[18], 解决了原始拜占庭容错算法效率不高 的问题, 将算法复杂度由指数级降低到多项式级, 使得拜占庭容错算法在实际系统应用中变得可 行. PBFT 实际上是 Paxos 算法的变种, 通过改 进 Paxos 算法使其可以处理拜占庭错误, 因而也称 为 Byzantine paxos 算法, 可以在保证活性 (Liveness) 和安全性 (Safety) 的前提下提供 (n−1)/3 的 容错性, 其中 n 为节点总数. 分布式系统无法同时满足一 致性 (Consistency)、可用性 (Availability) 和分区 容错性 (Partition tolerance), 最多只能同时满足其 中两个. 其中, 一致性是指分布式系统中的所有数据 备份在同一时刻保持同样的值; 可用性是指集群中 部分节点出现故障时, 集群整体是否还能处理客户 端的更新请求; 分区容忍性则是指是否允许数据分 区, 不同分区的集群节点之间无法互相通信. POS最早应用在点点币。瑞波 协议共识算法 (Ripple Protocol Consensus Algorithm, RPCA)[21], 该共识算法解决了异步网络节点 通讯时的高延迟问题, 通过使用集体信任的子网络 (Collectively-trusted subnetworks), 在只需最小化 信任和最小连通性的网络环境中实现了低延迟、高 鲁棒性的拜占庭容错共识算法. 目前, Ripple 已经 发展为基于区块链技术的全球金融结算网络. DPoS 共识的基本思路 类似于 “董事会决策”, 即系统中每个节点可以将其 持有的股份权益作为选票授予一个代表, 获得票数 最多且愿意成为代表的前 N 个节点将进入 “董事 会”, 按照既定的时间表轮流对交易进行打包结算、 并且签署 (即生产) 新区块。 Raft 的初衷是为设计一种比 Paxos 更易于理解 和实现的共识算法.
区块链共识算法可以根据其容错类型、部署方 式和一致性程度等多个维度加以分类. 例如, 根据容 错类型, 可以将区块链共识算法分为拜占庭容错和 非拜占庭容错两类; 根据部署方式, 可以将区块链共 识算法分为公有链共识、联盟链共识和私有链共识 三类; 根据一致性程度, 还可以将区块链共识算法分 为强一致性共识和弱 (最终) 一致性共识等. 本文提 出一种按照共识过程的选主策略的新分类方法, 其 优点在于便于刻画共识算法的核心机理. 具体来说, 可根据选主策略 (即函数 f 的具体实现方式) 将区 块链共识算法分为选举类、证明类、随机类、联盟类 和混合类共 5 种类型: 选举类共识: 即矿工节点在每一轮共识过程中 通过 “投票选举” 的方式选出当前轮次的记账节点, 首先获得半数以上选票的矿工节点将会获得记账权; 多见于传统分布式一致性算法, 例如 Paxos 和 Raft 等. 证明类共识: 也可称为 “Proof of X” 类共识, 即矿工节点在每一轮共识过程中必须证明自己具有 某种特定的能力, 证明方式通常是竞争性地完成某 项难以解决但易于验证的任务, 在竞争中胜出的矿 工节点将获得记账权; 例如 PoW 和 PoS 等共识算 法是基于矿工的算力或者权益来完成随机数搜索任 务, 以此竞争记账权. 随机类共识: 即矿工节点根据某种随机方式 直接确定每一轮的记账节点, 例如下文将要提到的 Algorand 和 PoET 共识算法等. 联盟类共识: 即矿工节点基于某种特定方式首先选举出一组代表节点, 而后由代表节点以轮流或 者选举的方式依次取得记账权. 这是一种以 “代议 制” 为特点的共识算法, 例如 DPoS 等. 混合类共识: 即矿工节点采取多种共识算法的 混合体来选择记账节点, 例如 PoW + PoS 混合共 识、DPoS+BFT 共识等.
研究者基于 PoW 和 PoS 算法的有机结合, 相 继提出了权益–速度证明 (Proof of stake velocity, PoSV)[25]、燃烧证明(Proof of burn, PoB)、行动 证明 (Proof of activity, PoA) 和二跳 (2-hop) 共识算法, 致力于取长补短、解决 PoW 与 PoS 存 在的能源消耗与安全风险问题. PoSV 共识算法, 针对 PoS 中币龄是时间的线 性函数这一问题进行改进, 致力于消除持币人的屯 币现象. PoSV 算法前期使用 PoW 实现代币分配, 后期使用 PoSV 维护网络长期安全. PoSV 将 PoS 中币龄和时间的线性函数修改为指数式衰减函数, 即币龄的增长率随时间减少最后趋于零. 因此新币 的币龄比老币增长地更快, 直到达到上限阈值, 这在 一定程度上缓和了持币者的屯币现象.基 于 PoW 和 PoS 首创提出了 PoB 共识算法. 其中, PoW 共识被用来产生初始的代币供应, 随着时间增 长, 区块链网络累积了足够的代币时, 系统将依赖 PoB 和 PoS 共识来共同维护. PoB 共识的特色是 矿工通过将其持有的 Slimcoin 发送至特定的无法找 回的地址 (燃烧) 来竞争新区块的记账权, 燃烧的币 越多则挖到新区块的概率越高.PoA 共识也是基于 PoW 和 PoS, 其中采用 PoW 挖出的部分代币以抽奖的方式分发给所有活跃节点, 而节点拥有的权益与抽奖券的数量即抽中概率成正比。二跳共识解决 PoW 潜在的 51% 算力攻击问题, 解决思路是 在 PoW 算力的基础上引入 PoS 权益, 使得区块链 安全建立在诚实节点占有大多数联合资源 (算力 + 权益) 的基础上. 换句话说, 拜占庭节点必须同时控 制 51% 以上的算力和 51% 以上的权益, 才能成功 实施 51% 攻击, 这无疑极大地提高了区块链的安全 性.
原生 PoS 共识算法的改进目标主要是解决 其固有的 “无利害关系 (Nothing at stake)” 问 题, 形成了 Tendermint[29] 以及由其衍生出的 Casper[30]、Ouroboros[31]、Tezos[32] 和 Honeybadger[33] 等新共识算法. 原生 PoS 共识一般假设系统 中的对等节点都是静态和长期稳定的, 这在区块链 环境中并不现实. 2014 年提出的 Tendermint 的重 大突破是使用区块、哈希链接、动态验证器集合和循 环的领导者选举, 实现了第一个基于 PBFT 的 PoS 共识算法. 为解决无利害关系问题, Tendermint 节 点需要缴纳保证金, 如果作恶则保证金就会被没收. Tendermint 是一种拜占庭容错的共识算法, 具有抵 御双花攻击的鲁棒性, 并且可以抵御网络中至多三 分之一的破坏者的攻击. 2016 年提出的 HoneyBadger 共识是首个实用 的异步拜占庭容错共识协议, 可以在没有任何网络 时间假设的前提下保证区块链系统的活性 (Liveness). 该共识基于一种可实现渐近有效性的原子广 播协议, 能够在广域网的上百个节点上处理每秒上 万笔交易. 2017 年 8 月提出的 Ouroboros 共识是 首个基于 PoS 并且具有严格安全性保障的区块链协 议, 其特色是提出了一种新的奖励机制来驱动 PoS 共识过程, 使得诚实节点的行为构成一个近似纳什 均衡, 可以有效地抵御区块截留和自私挖矿等由于 矿工的策略性行为而导致的安全攻击.
原生 PoW 共识算法的改进目标主要是实现比 特币扩容或者降低其能耗. Elastico 是第一个拜占庭容错的安 全分片协议. OmniLedger 通过并行 跨分片交易处理优化区块链性能, 是第一种能够提 供水平扩展性而不必牺牲长期安全性和去中心性的 分布式账本架构.
Tangaroa 继承了Raft 简洁和容易理解的优势, 同时在拜占庭错误环境下 也能够维持安全性、容错性和活性. 受 Tangaroa 共 识启发, 2016 年 Github 平台的 Juno 项目提出一 种拜占庭容错的 Raft 算法, 此后该算法演变为一种 称为 ScalableBFT[45] 的专用拜占庭容错协议, 能够 实现比 Tangaroa 和 Juno 更好的性能. SCP 在联邦拜占庭协议 和 Ripple 协议的基础上演化而来的, 是第一个可证 明安全的共识机制, 具有分散控制、低延迟、灵活信 任和渐近安全 4 个关键属性. 同年, 超级账本的锯 齿湖项目将 Ripple 和 SCP 共识相结合, 提出了法 定人数投票 (Quorum voting) 共识算法, 以应对那 些需要即时交易最终性的应用场景. 2016 年, 中国 区块链社区 NEO (原名小蚁) 提出一种改进的拜占 庭容错算法 dBFT, 该算法在 PBFT 的基础上借鉴 了 PoS 设计思路, 首先按照节点的权益来选出记账 人, 然后记账人之间通过拜占庭容错算法来达成共 识. 该算法改进了 PoW 和 PoS 缺乏最终一致性的 问题, 使得区块链能够适用于金融场景.
