推荐星级：
- 1
- 2
- 3
- 4
- 5
区块链共识算法的发展现状与展望
资料介绍
共识算法是区块链技术的核心要素,也是近年来分布式系统研究的热点.本文系统性地梳理和讨论了区块链发展过程中的32种重要共识算法,介绍了传统分布式一致性算法以及分布式共识领域的里程碑式的重要研究和结论,提出了区块链共识算法的一种基础模型和分类方法,并总结了现有共识算法的发展脉络和若干性能指标,以期为未来共识算法的创新和区块链技术的发展提供参考.
部分文件列表
| 文件名 | 大小 |
| 区块链共识算法的发展现状与展望.pdf | 661K |
部分页面预览
（完整内容请下载后查看）第 44 卷 第 11 期
2018 年 11 月
自
动
化
学
报
Vol. 44, No. 11
ACTA AUTOMATICA SINICA
November, 2018
区块链共识算法的发展现状与展望
倪晓春 1
2
2
2
3 4
袁 勇 1
曾 帅 1
王飞跃 1
摘
要
共识算法是区块链技术的核心要素, 也是近年来分布式系统研究的热点. 本文系统性地梳理和讨论了区块链发展过
程中的 32 种重要共识算法, 介绍了传统分布式一致性算法以及分布式共识领域的里程碑式的重要研究和结论, 提出了区块链
共识算法的一种基础模型和分类方法, 并总结了现有共识算法的发展脉络和若干性能指标, 以期为未来共识算法的创新和区
块链技术的发展提供参考.
关键词 区块链, 共识算法, 分布式系统, 拜占庭容错, P2P 网络
引用格式 袁勇, 倪晓春, 曾帅, 王飞跃. 区块链共识算法的发展现状与展望. 自动化学报, 2018, 44(11): 2011−2022
DOI 10.16383/j.aas.2018.c180268
Blockchain Consensus Algorithms: The State of the Art and Future Trends
2
2
2
3 4
YUAN Yong1
NI Xiao-Chun1
ZENG Shuai1
WANG Fei-Yue1
Abstract Consensus algorithm is a key component of the blockchain technology, and also a hot topic in distributed
systems research. In this paper, we systematically review and discuss 32 mainstream consensus algorithms emerged
in the development process of blockchain. We introduce the classic distributed consistency algorithms, as well as the
milestone research efforts and the key conclusions of distributed consensus algorithms. We also propose a novel model
and classification approach of blockchain consensus algorithms. In the end, we summarize the consensus algorithms and
their performance measures using an evolutionary tree. This is our preliminary research effort towards the blockchain
consensus algorithm, aiming at offering useful guidance and reference for future innovation of novel consensus algorithms
and the development of blockchain technology.
Key words Blockchain, consensus algorithms, distributed systems, Byzantine fault tolerance, peer-to-peer network
(P2P)
Citation Yuan Yong, Ni Xiao-Chun, Zeng Shuai, Wang Fei-Yue. Blockchain consensus algorithms: the state of the art
and future trends. Acta Automatica Sinica, 2018, 44(11): 2011−2022
共识问题是社会科学和计算机科学等领域的经
典问题 已经有很长的研究历史 目前有记载的文献
德蒙 · 艾森伯格
和大卫 · 盖
尔
发表的
至少可以追溯到
年 兰德公司和布朗大学的埃
主要研究
针对某个特定的概率空间 一组个体各自有其主
观的概率分布时 如何形成一个共识概率分布的问
题[1] 随后 共识问题逐渐引起了社会学、管理学、
经济学、特别是计算机科学等各学科领域的广泛研
究兴趣
收稿日期 2018-04-29 录用日期 2018-09-17
Manuscript received April 29, 2018; accepted September 17,
2018
国家自然科学基金 (71472174, 61533019, 71232006, 61233001,
71702182), 青岛智能产业智库基金资助
Supported by National Natural Science Foundation of China
(71472174, 61533019, 71232006, 61233001, 71702182), Qingdao
Think-Tank Foundation on Intelligent Industries
本文责任编委 刘艳军
Recommended by Associate Editor LIU Yan-Jun
1. 中国科学院自动化研究所复杂系统管理与控制国家重点实验室 北
计算机科学领域的早期共识研究一般聚焦于分
布式一致性 即如何保证分布式系统集群中所有节
点的数据完全相同并且能够对某个提案达成一致
的问题 是分布式计算的根本问题之一 虽然共识
京 100190 2. 青岛智能产业技术研究院平行区块链技术创新中心 青
岛 266109
3. 国防科学技术大学军事计算实验与平行系统技术中心
和一致性
在很多文献
长沙 410073 4. 中国科学院大学中国经济与社会安全研究中心 北京
101408
1. The State Key Laboratory for Management and Control of
Complex Systems, Institute of Automation, Chinese Academy
of Sciences, Beijing 100190 2. Innovation Center for Parallel
Blockchain, Qingdao Academy of Intelligent Industries, Qing-
和应用场景中被认为是近似等价和可互换使用的
但二者涵义存在着细微的差别 共识研究侧重于分
布式节点达成一致的过程及其算法 而一致性研究
则侧重于节点共识过程最终达成的稳定状态 此外
传统分布式一致性研究大多不考虑拜占庭容错问题
即假设不存在恶意篡改和伪造数据的拜占庭节点
因此在很长一段时间里 传统分布式一致性算法的
dao 266109
3. Research Center of Military Computational
Experiments and Parallel Systems, National University of De-
fense Technology, Changsha 410073 4. Center of China Eco-
nomic and Social Security, The University of Chinese Academy
of Sciences, Beijing 101408
2012
自
动
化
学
报
44 卷
应用场景大多是节点数量有限且相对可信的分布式
数据库环境 与之相比 区块链系统的共识算法则必
须运行于更为复杂、开放和缺乏信任的互联网环境
算法的提法
现有文献研究的共识问题实际上可以分为算法
共识和决策共识两个分支 前者致力于研究在特定
的网络模型和故障模型前提下 如何在缺乏中央控
制和协调的分布式网络中确保一致性 其实质是一
种 机器共识 后者则更为广泛地研究无中心的群
体决策中 如何就最优的决策达成一致的问题 例
如关于比特币系统扩容[6] 问题和分叉问题的社区讨
论与路线选择 其实质是 人的共识 二者的区别
在于 前者是机器间的确定性共识 以工程复杂性
为主 而后者则是以 人在环路中
下 节点数量更多且可能存在恶意拜占庭节点
因
此 即使
和
等许多分布式一致性算法早在上世纪
年代就已
经提出 但是如何跨越拜占庭容错这道鸿沟、设计简
便易行的分布式共识算法 仍然是分布式计算领域
的难题之一
年
月
日 一位化名为 中本聪
的研究者在密码学邮件组中发表了比特币的奠基
性论文
[2]
的复杂系统为特点的不确定性共识 以社会
基于区块链 特别是公有链 的共识研
复杂性为主 区块链共识算法研究应属于算法共识
分支的子集 而决策共识则大多见于分布式人工智
能、多智能体等研究领域
究自此拉开序幕 从分布式计算和共识的角度来看
比特币的根本性贡献在于首次实现和验证了一类实
用的、互联网规模的拜占庭容错算法 从而打开了通
往区块链新时代的大门
拜占庭将军问题是分布式共识的基础 也是上
述两个研究分支的根源 拜占庭将军问题有两个交
互一致性条件 即一致性和正确性 由于大多数情况
下 正确性涉及到人的主观价值判断 很难施加到分
布式节点上 因此算法共识采用的是 降级的正确性
即从 表达的内容是正确
一般而言 区块链系统的节点具有分布式、自治
性、开放可自由进出等特性 因而大多采用对等式网
络
网络 来组织散布
全球的参与数据验证和记账的节点 网络中的
每个节点均地位对等且以扁平式拓扑结构相互连通
和交互 不存在任何中心化的特殊节点和层级结构
每个节点均会承担网络路由、验证区块数据、传播区
块数据、发现新节点等功能 区块链系统采用特定的
经济激励机制来保证分布式系统中所有节点均有动
机参与数据区块的生成和验证过程 按照节点实际
完成的工作量分配共识过程所产生的数字加密货币
并通过共识算法来选择特定的节点将新区块添加到
区块链 以比特币为代表的一系列区块链应用的蓬
勃发展 彰显了区块链技术的重要性与应用价值 区
块链系统的共识也成为一个新的研究热点[3−5]
的 降级为 正确地表达 这就导致区块链的拜占
庭共识实际上是一种机器共识 其本身等价于分布
式一致性 正确表达 不篡改消息 与之相对的是
决策共识可以认为是人的共识 不仅要求一致性 而
且要求所有节点相信 表达的内容是正确的 因而
决策共识不仅要求内容的客观一致性 而且还要求
其在共识节点间的主观正确性 由此可见 算法共识
处理的是客观的二值共识 即对 唯一正确的账本
和错 所有错误的账本 而决策共识处理的是主观
的多值共识 即意见
及其所属群体 、意见
及
其所属群体 、· · · 、意见
及其所属群体 各节点
迄今为止 研究者已经在共识相关领域做了大
量研究工作 不同领域研究者的侧重点也各不相同
计算机学科通常称为共识算法或者共识协议 管理
和经济学科则通常称为共识机制 细究之下 这些
提法存在细微的差异 算法一般是一组顺序敏感的
指令集且有明确的输入和输出 而协议和机制则大
多是一组顺序不敏感的规则集 就区块链领域而言
本文认为比特币和以太坊等可认为是底层协议或机
最终通过群体间的协调和协作过程收敛到唯一意见
共识 而此过程可能失败 不收敛
本文致力于按时间顺序梳理和讨论区块链发展
过程中的共识算法 以期为未来共识算法的创新和
区块链技术的发展提供参考 本文的后续章节安排
如下 首先 简要介绍了分布式共识领域重要的里
程碑式的研究和结论 包括两军问题、拜占庭问题和
不可能定理 并介绍了传统的分布式一致性算
制 其详细规定了系统或平台内部的节点交互规则、 法 然后 提出了区块链共识算法的一种基础模型和
数据路由和转发规则、区块构造规则、交易验证规
则、账本维护规则等集合 而工作量证明
分类方法 并对当前主流的区块链共识算法进行了
分析 最后 总结了区块链共识算法的发展和研究趋
势
、权益证明
等则
是建立在特定协议或机制基础上、可灵活切换的算
法 其规定了交易侦听与打包、构造区块、记账人选
举、区块传播与验证、主链选择与更新等若干类顺
序敏感的指令集合 因此 本文后续叙述均采用共识
1 传统分布式一致性算法
年 纽约州立大学石溪分校的阿克云卢
、埃卡纳德汉姆
全部评论(0)