来源：平行区块链

摘 要 共识算法是区块链技术的核心要素, 也是近年来分布式系统研究的热点. 本文系统性地梳理和讨论了区块链发展过程中的 32 种重要共识算法, 介绍了传统分布式一致性算法以及分布式共识领域的里程碑式的重要研究和结论, 提出了区块链共识算法的一种基础模型和分类方法, 并总结了现有共识算法的发展脉络和若干性能指标, 以期为未来共识算法的创新和区块链技术的发展提供参考.

关键词 区块链, 共识算法, 分布式系统, 拜占庭容错

引用格式 袁勇, 倪晓春, 曾帅, 王飞跃. 区块链共识算法的发展现状与展望. 自动化学报, DOI10.16383/j.aas.2018.c180268

共识问题是社会科学和计算机科学等领域的经典问题, 已经有很长的研究历史. 目前有记载的文献至少可以追溯到 1959 年, 兰德公司和布朗大学的埃德蒙· 艾森伯格 (Edmund Eisenberg) 和大卫· 盖尔 (David Gale) 发表的“Consensus of subjective probabilities: the Pari-Mutuel method”, 主要研究针对某个特定的概率空间, 一组个体各自有其主观的概率分布时, 如何形成一个共识概率分布的问题[1]. 随后, 共识问题逐渐引起了社会学、 管理学、 经济学、 特别是计算机科学等各学科领域的广泛研究兴趣.

计算机科学领域的早期共识研究一般聚焦于分布式一致性, 即如何保证分布式系统集群中所有节点的数据完全相同并且能够对某个提案达成一致的问题, 是分布式计算的根本问题之一. 虽然共识(Consensus) 和一致性 (Consistency) 在很多文献和应用场景中被认为是近似等价和可互换使用的,但二者涵义存在着细微的差别: 共识研究侧重于分布式节点达成一致的过程及其算法, 而一致性研究则侧重于节点共识过程最终达成的稳定状态; 此外,传统分布式一致性研究大多不考虑拜占庭容错问题,即假设不存在恶意篡改和伪造数据的拜占庭节点,因此在很长一段时间里, 传统分布式一致性算法的应用场景大多是节点数量有限且相对可信的分布式数据库环境. 与之相比, 区块链系统的共识算法则必须运行于更为复杂、开放和缺乏信任的互联网环境下, 节点数量更多且可能存在恶意拜占庭节点. 因此, 即使 Viewstamped replication(以下简称 VR)和 Paxos 等许多分布式一致性算法早在上世纪 80年代就已经提出, 但是如何跨越拜占庭容错这道鸿沟、 设计简便易行的分布式共识算法, 仍然是分布式计算领域的难题之一.

2008 年 10 月 31 日, 一位化名为“ 中本聪” 的研究者在密码学邮件组中发表了比特币的奠基性论文“ Bitcoin: a peer-to-peer electronic cash system”[2], 基于区块链 (特别是公有链) 的共识研究自此拉开序幕. 从分布式计算和共识的角度来看, 比特币的根本性贡献在于首次实现和验证了一类实用的、 互联网规模的拜占庭容错算法, 从而打开了通往区块链新时代的大门.

一般而言, 区块链系统的节点具有分布式、 自治性、 开放可自由进出等特性, 因而大多采用对等式网络 (Peer-to-peer network, P2P 网络) 来组织散布全球的参与数据验证和记账的节点.P2P 网络中的每个节点均地位对等且以扁平式拓扑结构相互连通和交互, 不存在任何中心化的特殊节点和层级结构,每个节点均会承担网络路由、 验证区块数据、 传播区块数据、 发现新节点等功能. 区块链系统采用特定的经济激励机制来保证分布式系统中所有节点均有动机参与数据区块的生成和验证过程, 按照节点实际完成的工作量分配共识过程所产生的数字加密货币,并通过共识算法来选择特定的节点将新区块添加到区块链. 以比特币为代表的一系列区块链应用的蓬勃发展, 彰显了区块链技术的重要性与应用价值, 区块链系统的共识也成为一个新的研究热点 [3][4][5].

迄今为止, 研究者已经在共识相关领域做了大量研究工作, 不同领域研究者的侧重点也各不相同.计算机学科通常称为共识算法或者共识协议, 管理和经济学科则通常称为共识机制. 细究之下, 这些提法存在细微的差异: 算法一般是一组顺序敏感的指令集且有明确的输入和输出; 而协议和机制则大多是一组顺序不敏感的规则集. 就区块链领域而言,本文认为比特币和以太坊等可认为是底层协议或机制, 其详细规定了系统或平台内部的节点交互规则、数据路由和转发规则、 区块构造规则、 交易验证规则、 账本维护规则等集合; 而工作量证明 (Proof-ofWork, PoW)、 权益证明 (Proof-of-Stake, PoS) 等则是建立在特定协议或机制基础上、 可灵活切换的算法, 其规定了交易侦听与打包、 构造区块、 记账人选举、 区块传播与验证、 主链选择与更新等若干类顺序敏感的指令集合. 因此, 本文后续叙述均采用共识算法的提法.

现有文献研究的共识问题实际上可以分为算法共识和决策共识两个分支, 前者致力于研究在特定的网络模型和故障模型前提下, 如何在缺乏中央控制和协调的分布式网络中确保一致性, 其实质是一种“ 机器共识”; 后者则更为广泛地研究无中心的群体决策中, 如何就最优的决策达成一致的问题, 例如关于比特币系统扩容 [6] 问题和分叉问题的社区讨论与路线选择, 其实质是“ 人的共识”. 二者的区别在于: 前者是机器间的确定性共识, 以工程复杂性为主； 而后者则是以“ 人在环路中 (Human-in-theloop)” 的复杂系统为特点的不确定性共识, 以社会复杂性为主. 区块链共识算法研究应属于算法共识分支的子集, 而决策共识则大多见于分布式人工智能、 多智能体等研究领域.

拜占庭将军问题是分布式共识的基础, 也是上述两个研究分支的根源. 拜占庭将军问题有两个交互一致性条件, 即一致性和正确性. 由于大多数情况下, 正确性涉及到人的主观价值判断, 很难施加到分布式节点上, 因此算法共识采用的是“ 降级的正确性 (Degraded correctness), 即从“ 表达的内容是正确的” 降级为“ 正确地表达”, 这就导致区块链的拜占庭共识实际上是一种机器共识, 其本身等价于分布式一致性 + 正确表达 (不篡改消息). 与之相对的是, 决策共识可以认为是人的共识, 不仅要求一致性, 而且要求所有节点相信“ 表达的内容是正确的”,因而决策共识不仅要求内容的客观一致性, 而且还要求其在共识节点间的主观正确性. 由此可见, 算法共识处理的是客观的二值共识, 即对 (唯一正确的账本) 和错 (所有错误的账本), 而决策共识处理的是主观的多值共识, 即意见 1(及其所属群体)、 意见 2(及其所属群体)、……、 意见 N(及其所属群体), 各节点最终通过群体间的协调和协作过程收敛到唯一意见(共识), 而此过程可能失败 (不收敛).

本文致力于按时间顺序梳理和讨论区块链发展过程中的共识算法, 以期为未来共识算法的创新和区块链技术的发展提供参考. 本文的后续章节安排如下: 首先简要介绍了分布式共识领域重要的里程碑式的研究和结论, 包括两军问题、 拜占庭问题和FLP 不可能定理, 并介绍了传统的分布式一致性算法; 然后提出了区块链共识算法的一种基础模型和分类方法, 并对当前主流的区块链共识算法进行了分析; 最后总结了区块链共识算法的发展和研究趋势.

1 传统分布式一致性算法

1975 年, 纽约州立大学石溪分校的阿克云卢(E. A. Akkoyunlu)、 埃卡纳德汉姆 (K. Ekanadham) 和胡贝尔 (R. V. Huber) 在论文“ Some constraints and tradeofis in the design of network communications” 中首次提出了计算机领域的两军问题及其无解性证明 [7], 著名的数据库专家吉姆· 格雷正式将该问题命名为“ 两军问题”[8]. 两军问题表明, 在不可靠的通信链路上试图通过通信达成一致共识是不可能的, 这被认为是计算机通信研究中第一个被证明无解的问题. 两军问题对计算机通信研究产生了重要的影响, 互联网时代最重要的TCP/IP 协议中的“ 三次握手” 过程即是为解决两军问题不存理论解而诞生的简单易行、 成本可控的“ 工程解”.

分布式计算领域的共识问题于 1980 年由马歇尔· 皮斯 (Marshall Pease)、 罗伯特· 肖斯塔克(Robert Shostak) 和莱斯利· 兰伯特 (Leslie Lamport) 提出 [9], 该问题主要研究在一组可能存在故障节点、 通过点对点消息通信的独立处理器网络中,非故障节点如何能够针对特定值达成一致共识.1982年, 作者在另一篇文章中正式将该问题命名为“ 拜占庭将军问题”[10], 提出了基于口头消息和基于签名消息的两种算法来解决该问题. 拜占庭假设是对现实世界的模型化, 强调的是由于硬件错误、 网络拥塞或断开以及遭到恶意攻击, 计算机和网络可能出现的不可预料的行为. 此后, 分布式共识算法可以分为两类, 即拜占庭容错和非拜占庭容错类共识. 早期共识算法一般为非拜占庭容错算法, 例如广泛应用于分布式数据库的 VR 和 Paxos, 目前主要应用于联盟链和私有链;2008 年末, 比特币等公有链诞生后, 拜占庭容错类共识算法才逐渐获得实际应用. 需要说明的是, 拜占庭将军问题是区块链技术核心思想的根源, 直接影响着区块链系统共识算法的设计和实现,因而在区块链技术体系中具有重要意义.

1985 年, 迈克尔· 费舍尔 (Michael Fisher)、南 希 · 林 奇 (Nancy Lynch) 和 迈 克 尔 ·帕 特 森 (Michael Paterson) 共 同 发 表 了 论文“ Impossibility of distributed consensus with one faulty process”[11]. 这篇文章证明: 在含有多个确定性进程的异步系统中, 只要有一个进程可能发生故障, 那么就不存在协议能保证有限时间内使所有进程达成一致. 按照作者姓氏的首字母, 该定理被命名为 FLP 不可能定理, 是分布式系统领域的经典结论之一, 并由此获得了 Dijkstra 奖.FLP 不可能定理同样指出了存在故障进程的异步系统的共识问题不存在有限时间的理论解, 因而必须寻找其可行的“ 工程解”. 为此, 研究者们只能通过调整问题模型来规避FLP 不可能定理, 例如牺牲确定性、 增加时间等; 加密货币则是通过设定网络同步性 (或弱同步性) 和时间假设来规避 FLP 不可能性, 例如网络节点可以快速同步, 且矿工在最优链上投入有限时间和资源等.

早期的共识算法一般也称为分布式一致性算法.与目前主流的区块链共识算法相比, 分布式一致性算法主要面向分布式数据库操作、 且大多不考虑拜占庭容错问题, 即假设系统节点只发生宕机和网络故障等非人为问题, 而不考虑恶意节点篡改数据等问题.1988 年, 麻省理工学院的布莱恩· 奥奇 (Brian M. Oki) 和芭芭拉· 里斯科夫 (Barbara H. Liskov,著名计算机专家、 2008 年图灵奖得主) 提出了 VR一致性算法, 采用主机 – 备份 (Primary-backup) 模式, 规定所有数据操作都必须通过主机进行, 然后复制到各备份机器以保证一致性 [12].1989 年, 莱斯利· 兰伯特 (Leslie Lamport) 在工作论文“ The part-time parliament” 中提出 Paxos 算法, 由于文章采用了讲故事的叙事风格且内容过于艰深晦涩, 直到 18 年才通过评审、 发表在 ACM transactions on computer systems 期刊上 [13].Paxos 是基于消息传递的一致性算法, 主要解决分布式系统如何就某个特定值达成一致的问题. 随着分布式共识研究的深入,Paxos 算法获得了学术界和工业界的广泛认可, 并衍生出 Abstract paxos、 Classic paxos、Byzantine paxos 和 Disk paxos 等变种算法,成为解决异步系统共识问题最重要的算法家族 [14].实际上,Liskove 等提出的 VR 算法本质上也是一类Paxos 算法. 需要说明的是,VR 和 Paxos 算法均假设系统中不存在拜占庭故障节点, 因而是非拜占庭容错的共识算法. 除以上共识算法外, 获得较多研究关注的早期共识算法还有两阶段提交 (Two-phase commit) 算法、 三阶段提交 (Three-phase commit)算法、 Zab、 Zyzzyva、Kafka 等, 本文限于篇幅不加详述.

2 主流区块链共识算法

13 年, 美国计算机科学家、 哈佛大学教授辛西娅· 德沃克 (Cynthia Dwork) 首次提出了工作量证明思想 [15], 用来解决垃圾邮件问题. 该机制要求邮件发送者必须算出某个数学难题的答案来证明其确实执行了一定程度的计算工作, 从而提高垃圾邮件发送者的成本.17 年, 英国密码学家亚当·伯克 (Adam Back) 也独立地提出、 并于 2002 年正式发表了用于哈希现金 (Hash cash) 的工作量证明机制 [16]. 哈希现金也是致力于解决垃圾邮件问题,其数学难题是寻找包含邮件接受者地址和当前日期在内的特定数据的 SHA-1 哈希值, 使其至少包含20 个前导零.19 年, 马库斯· 雅各布松 (Markus Jakobsson) 正式提出了“ 工作量证明” 概念 [17]. 这些工作为后来中本聪设计比特币的共识机制奠定了基础.

19 年,Barbara Liskov 等提出了实用拜占庭容错算法 (Practical Byzantine fault tolerance,PBFT)[18], 解决了原始拜占庭容错算法效率不高的问题, 将算法复杂度由指数级降低到多项式级, 使得拜占庭容错算法在实际系统应用中变得可行.PBFT实际上是 Paxos 算法的变种, 通过改进 Paxos 算法使其可以处理拜占庭错误, 因而也称为 Byzantine paxos 算法, 可以在保证活性(Liveness) 和安全性(Safety) 的前提下提供 (n-1)/3 的容错性, 其中 n 为节点总数.