区块链共识算法的发展现状与展望

来源：平行区块链

摘 要共识算法是区块链技术的核心要素, 也是近年来分布式系统研究的热点. 本文系统性地梳理和讨论了区块链发展过程中的 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 不可能定理, 并介绍了传统的分布式一致性算法; 然后提出了区块链共识算法的一种基础模型和分类方法, 并对当前主流的区块链共识算法进行了分析; 最后总结了区块链共识算法的发展和研究趋势.