区块链学习基础篇—共识机制(4)

首先,交易发起方构造交易,加上数字签名,广播到区块链P2P网络之中。然后,
区块链网络中的“矿工”节点陆续收到这笔交易。然后,所有矿工都会把交易打包到自己构建的备选区块之中,然后将自己的备选区块广播。这时候,全网根据”共识机制“来决定哪个矿工负责写入这个区块。然后这个矿工将会负责把这个区块添加到区块链上,完成该区块中的所有交易。最后交易完成,交易参与方可以查询到交易执行结果。那么,
“共识机制”是从什么时候出现的?1982年,
Lamport首次发表了关于拜占庭将军问题解决方案的论文,后来获得了计算机界的最高奖:图灵奖。1999年,Jakobsson发表了关于PoW的论文。2008年11月,中本聪发表了比特币的论文,并用了PoW作为共识机制。2012年,PeerCoin项目开始采用PoS作为共识机制。2016年,Tendermint项目开始采用PBFT作为公示机制。2018年,以太坊项目提出在2.0版本中,通过Casper方法采用PoS作为共识机制。实际上,V神今天正在欧洲介绍这方面的最新进展。共识机制的基本要求和不可能三角这里需要提的是,任何分布式系统(包括比特币甚至货币),都存在一个不可能三角形:性能、可扩展性和去中心化。譬如人民币,性能和可扩展性很高(每天无数人用它来交易),但是去中心化低(央行想印多少就印多少)。对于比特币,去中心化程度高,可扩展性也高,但是性能低。所以在设计、选择共识机制时候,我们必须记住这三点:我们应该优化哪一方面,牺牲哪一方面,因为你不可能同时达到这三点。另外,所有的共识算法必须具备三个基本要求:1.一致性
(safety):所有参与共识的诚实的节点,得到的计算结果是相同的,而且是符合共识协议的。2.
终局性
(liveness):所有参与共识的诚实的节点,最终可以达成一致性结果。3.
容错性 (fault
tolerance):在共识算法的成功执行过程中,可以容许参与共识的节点发生一些错误。

共识机制是什么?

.wqpc_wechat_view *{max-width: 100%!important;box-sizing:
border-box!important;-webkit-box-sizing: border-box!important;
word-wrap: break-word!important;} 微信号 功能介绍 摘
要共识算法是区块链技术的核心要素, 也是近年来分布式系统研究的热点.
本文系统性地梳理和讨论了区块链发展过程中的 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 算法,
    由于文章采用了讲故事的叙事风格且内容过于艰深晦涩, 直到 1998
    年才通过评审、 发表在 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 主流区块链共识算法1993 年, 美国计算机科学家、
    哈佛大学教授辛西娅· 德沃克 (Cynthia Dwork) 首次提出了工作量证明思想
    [15], 用来解决垃圾邮件问题.
    该机制要求邮件发送者必须算出某个数学难题的答案来证明其确实执行了一定程度的计算工作,
    从而提高垃圾邮件发送者的成本.1997 年, 英国密码学家亚当·伯克 (Adam Back)
    也独立地提出、 并于 2002 年正式发表了用于哈希现金 (Hash cash)
    的工作量证明机制 [16].
    哈希现金也是致力于解决垃圾邮件问题,其数学难题是寻找包含邮件接受者地址和当前日期在内的特定数据的
    SHA-1 哈希值, 使其至少包含20 个前导零.1999 年, 马库斯· 雅各布松 (Markus
    Jakobsson) 正式提出了“ 工作量证明” 概念 [17].
    这些工作为后来中本聪设计比特币的共识机制奠定了基础.1999 年,Barbara
    Liskov 等提出了实用拜占庭容错算法 (Practical Byzantine fault
    tolerance,PBFT)[18], 解决了原始拜占庭容错算法效率不高的问题,
    将算法复杂度由指数级降低到多项式级,
    使得拜占庭容错算法在实际系统应用中变得可行.PBFT实际上是 Paxos
    算法的变种, 通过改进 Paxos 算法使其可以处理拜占庭错误, 因而也称为
    Byzantine paxos 算法, 可以在保证活性(Liveness) 和安全性(Safety)
    的前提下提供 (n-1)/3 的容错性, 其中 n 为节点总数.2000 年,
    加利福尼亚大学的埃里克· 布鲁尔(Eric Brewer) 教授在 ACM symposium on
    principles of distributed computing 研讨会的特邀报告中提出了一个猜想:
    分布式系统无法同时满足一致性 (Consistency)、 可用性(Availability)
    和分区容错性 (Partition tolerance), 最多只能同时满足其中两个. 其中,
    一致性是指分布式系统中的所有数据备份在同一时刻保持同样的值;
    可用性是指集群中部分节点出现故障时,
    集群整体是否还能处理客户端的更新请求;
    分区容忍性则是指是否允许数据分区,不同分区的集群节点之间无法互相通信.2002
    年, 塞斯· 吉尔伯特 (Seth Gilbert) 和南希· 林奇 (Nancy Lynch)
    在异步网络模型中证明了这个猜想, 使其成为 CAP 定理或布鲁尔定理 [19].
    该定理使得分布式网络研究者不再追求同时满足三个特性的完美设计,而是不得不在其中做出取舍,
    这也为后来的区块链体系结构设计带来了影响和限制.2008 年 10 月,
    中本聪发表的比特币创世论文催生了基于区块链的共识算法研究.
    前文所提到的传统分布式一致性算法大多应用于相对可信的联盟链和私有链,
    而面向比特币、 以太坊等公有链环境则诞生了 PoW、 PoS
    等一系列新的拜占庭容错类共识算法.比特币采用了 PoW
    共识算法来保证比特币网络分布式记账的一致性,
    这也是最早和迄今为止最安全可靠的公有链共识算法.PoW
    的核心思想是通过分布式节点的算力竞争来保证数据的一致性和共识的安全性.
    比特币系统的各节点 (即矿工)
    基于各自的计算机算力相互竞争来共同解决一个求解复杂但是验证容易的 SHA256
    数学难题 (即挖矿),
    最快解决该难题的节点将获得下一区块的记账权和系统自动生成的比特币奖励.PoW
    共识在比特币中的应用具有重要意义,
    其近乎完美地整合了比特币系统的货币发行、 流通和市场交换等功能,
    并保障了系统的安全性和去中心性. 然而,PoW 共识同时存在着显著的缺陷,
    其强大算力造成的资源浪费 (主要是电力消耗) 历来为人们所诟病, 而且长达 10
    分钟的交易确认时间使其相对不适合小额交易的商业应用.[3]2011 年 7 月, 一
    位 名 为 Quantum Mechanic 的 数 字 货 币 爱 好 者 在 比 特币 论
    坛(www.bitcointalk.org) 首次提出了权益证明 PoS共识算法 [20].
    随后,Sunny King 在 2012 年 8 月发布的点点币 (Peercoin, PPC)
    中首次实现.PoS
    由系统中具有最高权益而非最高算力的节点获得记账权,其中权益体现为节点对特定数量货币的所有权,
    称为币龄或币天数 (Coin days).PPC 将PoW 和 PoS两种共识算法结合起来,
    初期采用 PoW 挖矿方式以使得 Token 相对公平地分配给矿工,
    后期随着挖矿难度增加, 系统将主要由 PoS 共识算法维护.PoS 一定程度上解决了
    PoW 算力浪费的问题, 并能够缩短达成共识的时间,
    因而比特币之后的许多竞争币都采用 PoS 共识算法.2013 年 2 月, 以太坊创始人
    Vitalik Buterin在 比 特 币 杂 志 网 站 详 细 地 介 绍 了 Ripple(瑞 波币)
    及 其 共 识 过 程 的 思 路.Ripple 项 目 实 际 上 早于比特币,2004
    年就由瑞安· 福格尔 (Ryan Fugger) 实现,
    其初衷是创造一种能够有效支持个人和社区发行自己货币的去中心化货币系统;2014年,
    大卫· 施瓦尔茨 (David Schwartz) 等提出了瑞 波 协 议 共 识 算 法 (Ripple
    Protocol Consensus Algorithm,RPCA)[21],
    该共识算法解决了异步网络节点通讯时的高延迟问题, 通过使用集体信任的子网络
    (Collectively-trusted subnetworks),
    在只需最小化信任和最小连通性的网络环境中实现了低延迟、
    高鲁棒性的拜占庭容错共识算法.
    目前,Ripple已经发展为基于区块链技术的全球金融结算网络.2013 年 8 月,
    比特股 (Bitshares) 项目提出了一种新的共识算法, 即授权股份证明算法
    (Delegated Proof-of-Stake, DPoS)[22].DPoS 共识的基本思路类似于“
    董事会决策”, 即系统中每个节点可以将其持有的股份权益作为选票授予一个代表,
    获得票数最多且愿意成为代表的前 N 个节点将进入“
    董事会”,按照既定的时间表轮流对交易进行打包结算、 并且签署 (即生产)
    新区块 [3]. 如果说 PoW 和 PoS 共识分别是“ 算力为王” 和“ 权益为王”
    的记账方式的话,DPoS 则可以认为是“ 民主集中式” 的记账方式,
    其不仅能够很好地解决 PoW
    浪费能源和联合挖矿对系统的去中心化构成威胁的问题, 也能够弥补PoS
    中拥有记账权益的参与者未必希望参与记账的缺点, 其设计者认为 DPoS
    是当时最快速、 最高效、最去中心化和最灵活的共识算法.2013 年,
    斯坦福大学的迭戈· 翁伽罗 (Diego Ongaro) 和约翰· 奥斯特豪特 (John
    Ousterhout)提出了 Raft 共识算法. 正如其论文标题“ In search of an
    understandable consensus algorithm”[23] 所述,Raft
    的初衷是为设计一种比Paxos 更易于理解和实现的共识算法. 要知道, 由于 Paxos
    论文极少有人理解,Lamport 于 2001 年曾专门写过一篇文章“ Paxos made
    simple”[24], 试图简化描述 Paxos算法但效果不好, 这也直接导致了 Raft
    的提出. 目前,Raft 已经在多个主流的开源语言中得以实现.3
    共识算法的模型与分类随着比特币的普及和区块链技术的发展,
    越来越多的新共识算法被提出. 为使读者更为深刻地理解不同的共识算法,
    本节给出区块链共识过程的一个主流模型. 需要说明的是,
    该模型并非通用模型,可能无法涵盖所有种类的共识过程,
    但是可以体现大多数主流共识算法的核心思想.区块链系统建立在 P2P 网络之上,
    其全体节点的集合可记为 P, 一般分为生产数据或者交易的普通节点,
    以及负责对普通节点生成的数据或者交易进行验证、 打包、
    更新上链等挖矿操作的“ 矿工” 节点集合 (记为 M),
    两类节点可能会有交集;矿工节点通常情况下会全体参与共识竞争过程,
    在特定算法中也会选举特定的代表节点、 代替他们参加共识过程并竞争记账权,
    这些代表节点的集合记为 D;通过共识过程选定的记账节点记为 A.
    共识过程按照轮次重复执行,
    每一轮共识过程一般重新选择该轮的记账节点.共识过程的核心是“ 选主” 和“
    记账” 两部分, 在具体操作过程中每一轮可以分为选主 (Leader election)、
    造块 (Block generation)、 验证 (Data validation) 和上链 (Chain updation,
    即记账) 四个阶段.如图 1 所示,
    共识过程的输入是数据节点生成和验证后的交易或数据,
    输出则是封装好的数据区块以及更新后的区块链. 四个阶段循环往复执行,
    每执行一轮将会生成一个新区块.第一阶段: 选主. 选主是共识过程的核心,
    即从全体矿工节点集 M 中选出记账节点 A 的过程:我们可以使用公式 f(M)! A
    来表示选主过程, 其中函数 f 代表共识算法的具体实现方式. 一般来说,jAj=1,
    即最终选择唯一的矿工节点来记账.第二阶段: 造块.
    第一阶段选出的记账节点根据特定的策略将当前时间段内全体节点 P
    生成的交易或者数据打包到一个区块中, 并将生成的新区块广播给全体矿工节点 M
    或其代表节点 D. 这些交易或者数据通常根据区块容量、 交易费用、
    交易等待时间等多种因素综合排序后, 依序打包进新区块.
    造块策略是区块链系统性能的关键因素, 也是贪婪交易打包、
    自私挖矿等矿工策略性行为的集中体现.第三阶段: 验证. 矿工节点 M
    或者代表节点 D收到广播的新区块后,
    将各自验证区块内封装的交易或者数据的正确性和合理性.
    如果新区块获得大多数验证/代表节点的认可,
    则该区块将作为下一区块更新到区块链.第四阶段: 上链.
    记账节点将新区块添加到主链, 形成一条从创世区块到最新区块的完整的、
    更长的链条. 如果主链存在多个分叉链, 则需根据共识算法规定的主链判别标准,
    来选择其中一条恰当的分支作为主链.区块链共识算法可以根据其容错类型、
    部署方式和一致性程度等多个维度加以分类. 例如, 根据容错类型,
    可以将区块链共识算法分为拜占庭容错和非拜占庭容错两类;根据部署方式,
    可以将区块链共识算法分为公有链共识、
    联盟链共识和私有链共识三类;根据一致性程度,
    还可以将区块链共识算法分为强一致性共识和弱 (最终) 一致性共识等.
    本文提出一种按照共识过程的选主策略的新分类方法,
    其优点在于便于刻画共识算法的核心机理. 具体来说,可根据选主策略 (即函数 f
    的具体实现方式) 将区块链共识算法分为选举类、 证明类、 随机类、
    联盟类和混合类共五种类型:选举类共识: 即矿工节点在每一轮共识过程中通过“
    投票选举”
    的方式选出当前轮次的记账节点,首先获得半数以上选票的矿工节点将会获得记账权;多见于传统分布式一致性算法,
    例如 Paxos 和 Raft等.证明类共识: 也可称为“ Proof of X”
    类共识,即矿工节点在每一轮共识过程中必须证明自己具有某种特定的能力,
    证明方式通常是竞争性地完成某项难以解决但易于验证的任务,
    在竞争中胜出的矿工节点将获得记账权;例如 PoW 和 PoS
    等共识算法是基于矿工的算力或者权益来完成随机数搜索任务,
    以此竞争记账权.随机类共识:
    即矿工节点根据某种随机方式直接确定每一轮的记账节点,
    例如下文将要提到的Algorand 和 PoET 共识算法等.联盟类共识:
    即矿工节点基于某种特定方式首先选举出一组代表节点,
    而后由代表节点以轮流或者选举的方式依次取得记账权. 这是一种以“ 代议制”
    为特点的共识算法, 例如 DPoS 等.混合类共识:
    即矿工节点采取多种共识算法的混合体来选择记账节点, 例如 PoW+PoS
    混合共识、 DPoS+BFT 共识等.4 区块链共识算法的新进展自 2014 年起,
    随着比特币和区块链技术快速进入公众视野,
    许多学者开始关注并研究区块链技术,共识算法也因此进入快速发展、
    百花齐放的时期. 许多新共识算法在这段时间被提出.
    它们或者是原有算法的简单变种, 或者是为改进某一方面性能而做出的微创新,
    或者是为适应新场景和新需求而做出重大改进的新算法. 需要说明的是,
    这些共识算法由于提出时间晚, 目前大多尚未获得令人信服的实践验证,
    有些甚至只是科研设想; 但这些算法均具有明显的创新之处,
    具有一定的大规模应用的前景, 因此我们写出来以飨读者,
    并期待能够启发后续的创新研究.4.1 主线一: PoW 与 PoS
    算法的有机结合研究者基于 PoW 和 PoS 算法的有机结合, 相继提出了权益 –
    速度证明 (Proof of Stake Velocity,PoSV)[25]、 燃烧证明 (Proof of Burn,
    PoB)[26]、 行动证明(Proof of Activity, PoA)[27] 和二跳
    (2-hop)[28]共识算法, 致力于取长补短、 解决 PoW 与 PoS
    存在的能源消耗与安全风险问题.2014 年 4 月, 拉里· 雷恩 (Larry Ren)
    在蜗牛币 Reddcoin 白皮书中提出了 PoSV 共识算法, 针对 PoS
    中币龄是时间的线性函数这一问题进行改进, 致力于消除持币人的屯币现象.PoSV
    算法前期使用 PoW 实现代币分配,后期使用 PoSV 维护网络长期安全.PoSV 将
    PoS中币龄和时间的线性函数修改为指数式衰减函数,即币龄的增长率随时间减少最后趋于零.
    因此新币的币龄比老币增长地更快, 直到达到上限阈值,
    这在一定程度上缓和了持币者的屯币现象.2014 年 5月发行的 Slimcoin
    借鉴了比特币和点点币的设计,基于 PoW 和 PoS 首创提出了 PoB 共识算法.
    其中,PoW 共识被用来产生初始的代币供应, 随着时间增长,
    区块链网络累积了足够的代币时, 系统将依赖 PoB 和 PoS 共识来共同维护.PoB
    共识的特色是矿工通过将其持有的 Slimcoin 发送至特定的无法找回的地址
    (燃烧) 来竞争新区块的记账权, 燃烧的币越多则挖到新区块的概率越高.2014 年
    12 月提出的 PoA 共识也是基于 PoW 和 PoS, 其中采用
    PoW挖出的部分代币以抽奖的方式分发给所有活跃节点,而节点拥有的权益与抽奖券的数量即抽中概率成正比.
    二跳共识于 2017 年 4 月提出, 其设计初衷是为解决 PoW 潜在的 51%
    算力攻击问题, 解决思路是在 PoW 算力的基础上引入 PoS 权益,
    使得区块链安全建立在诚实节点占有大多数联合资源 (算力+权益) 的基础上.
    换句话说, 拜占庭节点必须同时控制 51% 以上的算力和 51% 以上的权益,
    才能成功实施 51% 攻击, 这无疑极大地提高了区块链的安全性.4.2 主线二: 原生
    PoS 算法的改进原 生 PoS 共 识 算 法 的 改 进 目 标 主 要是 解 决 其 固
    有 的 “ 无 利 害 关 系 (Nothing at stake)” 问 题, 形 成 了
    Tendermint[29] 以 及 由 其衍生出的Casper[30]、 Ouroboros[31]、
    Tezos[32] 和Honeybadger[33] 等新共识算法. 原生 PoS
    共识一般假设系统中的对等节点都是静态和长期稳定的,这在区块链环境中并不现实.
    2014 年提出的 Tendermint 的重大突破是使用区块、 哈希链接、
    动态验证器集合和循环的领导者选举, 实现了第一个基于PBFT 的 PoS 共识算法.
    为解决无利害关系问题,Tendermint 节点需要缴纳保证金,
    如果作恶则保证金就会被没收. Tendermint 是一种拜占庭容错的共识算法,
    具有抵御双花攻击的鲁棒性,
    并且可以抵御网络中至多三分之一的破坏者的攻击.2015 年提出的 Casper
    是以太坊计划在其路线图中称为宁静 (Serenity) 的第四阶段采用的共识算法,
    尚在设计、 讨论和完善阶段. 目前 Casper 总共有两个版本, 即由 Vlad Zamjir
    领导的 Casper the Friendly Ghost (CTFG)[34] 和由 Vitalik Buterin
    带领实现的 Casper Friendly Finality Gadget(CFFG)[35]. 前者是明确的 PoS
    共识, 而后者则是PoW 和 PoS 共识的有机结合. 同时,PoS
    共识的两个主要原理分别是基于链的 PoS 和基于拜占庭容错的 PoS.Tendermint
    是基于拜占庭容错的 PoS设计. 相比之下,CTFG 是基于链的 PoS 设计, 而CFFG
    则是两者的结合.2016 年提出的 HoneyBadger
    共识是首个实用的异步拜占庭容错共识协议,
    可以在没有任何网络时间假设的前提下保证区块链系统的活性 (Liveness).
    该共识基于一种可实现渐进有效性的原子广播协议,
    能够在广域网的上百个节点上处理每秒上万笔交易.2017 年 8 月提出的
    Ouroboros 共识是首个基于 PoS 并且具有严格安全性保障的区块链协议,
    其特色是提出了一种新的奖励机制来驱动 PoS共识过程,
    使得诚实节点的行为构成一个近似纳什均衡,
    可以有效地抵御区块截留和自私挖矿等由于矿工的策略性行为而导致的安全攻击.4.3
    主线三: 原生 PoW 共识算法的改进原生 PoW
    共识算法的改进目标主要是实现比特币扩容或者降低其能耗.2016 年 3 月,
    康奈尔大学的 Ittay Eyal 等提出一种新的共识算法 BitcoinNG[36],
    将时间切分为不同的时间段. 在每一个时间段上由一个领导者负责生成区块、
    打包交易. 该协议引入了两种不同的区块:
    用于选举领导者的关键区块和包含交易数据的微区块. 关键区块采用比特币 PoW
    共识算法生成, 然后领导者被允许小于预设阈值的速率 (例如 10 秒)
    来生成微区块.BitcoinNG
    可在不改变区块容量的基础上通过选举领导者生成更多的区块,
    从而可辅助解决比特币的扩容问题. 同年 8 月提出的 ByzCoin[37]
    共识算法借鉴了Bitcoin-NG 这种领导者选举和交易验证相互独立的设计思想,
    是一种新型的可扩展拜占庭容错算法,可使得区块链系统在保持强一致性的同时,
    达到超出 Paypal 吞吐量的高性能和低确认延迟.2016 年提出的 Elastico[38]
    共识机制通过分片技术来增强区块链的扩展性,
    其思路是将挖矿网络以可证明安全的方式隔离为多个分片 (Shard),
    这些分片并行地处理互不相交的交易集合.Elastico
    是第一个拜占庭容错的安全分片协议.2017 年,OmniLedger[39] 进一步借鉴
    ByzCoin 和 Elastico 共识, 设计并提出名为ByzCoinX
    的拜占庭容错协议.OmniLedger 通过并行跨分片交易处理优化区块链性能,
    是第一种能够提供水平扩展性而不必牺牲长期安全性和去中心性的分布式账本架构.为改进
    PoW 共识算法的效率 (能耗) 和公平性, 研 究 者 相 继 提 出 了 消 逝时 间
    证 明 (Proof of Elapsed Time, PoET)[40] 和 运 气 证 明 (Proof of Luck,
    PoL)[41].PoET 和 PoL 均是基于特定的可信执行环境 (Trusted execution
    environments, TEE,例如基于 Intel SGX 技术的 CPU) 的随机共识算法.PoET
    是超级账本 HyperLedger 的锯齿湖 Sawtooth 项目采用的共识算法,
    其基本思路是每个区块链节点都根据预定义的概率分布生成一个随机数,来决定其距离下一次获得记账权的等待时间.
    每当一个新区块提交到区块链系统后,SGX 即可帮助节点创建区块、
    生成该等待时间的证明, 而这种证明易于被其他 SGX 节点验证.PoET
    共识的意义在于使得区块链系统不必消耗昂贵算力来挖矿、 从而提高了效率,
    同时也真正实现了“ 一 CPU 一票” 的公平性. 类似地,PoL 共识也采用 TEE
    平台的随机数生成器来选择每一轮共识的领导者 (记账人),
    从而可降低交易验证延迟时间和交易确认时间、
    实现可忽略的能源消耗和真正公平的分布式挖矿.2014 年 提 出 的 空 间 证 明
    (Proof of Space, PoSp)[42] 和 2017 年提出的有益工作证明 (Proof of
    Useful Work, PoUW)[43] 也是为解决 PoW 的能耗问题而提出的共识算法.PoSp
    共识要求矿工必须出具一定数量的磁盘空间 (而非算力) 来挖矿, 而PoUW 则将
    PoW 共识中毫无意义的 SHA256
    哈希运算转变为实际场景中既困难又有价值的运算, 例如计算正交向量问题、
    3SUM 问题、 最短路径问题等.4.4 主线四:
    传统分布式一致性算法的改进及其它传统分布式一致性算法大多是非拜占庭容错的,因而难以应用于区块链场景
    (特别是公有链). 为此,克里斯托弗· 科普兰 (Christopher Copeland) 等结合
    Raft 和 PBFT 算法的优势, 于 2014 年提出拜占庭容错的 Tangaroa
    算法[44].Tangaroa 继承了 Raft简洁和容易理解的优势,
    同时在拜占庭错误环境下也能够维持安全性、 容错性和活性. 受 Tangaroa
    共识启发,2016 年 Github 平台的 Juno 项目提出一种拜占庭容错的 Raft 算法,
    此后该算法演变为一种称为 ScalableBFT[45] 的专用拜占庭容错协议,
    能够实现比 Tangaroa 和 Juno 更好的性能.2015 年, Stellar.org 首 席 科 学
    官 David Mazieres 教授提出了恒星共识协议 (Stellar Consensus Protocol,
    SCP)[46]. SCP 在联邦拜占庭协议和 Ripple 协议的基础上演化而来的,
    是第一个可证明安全的共识机制, 具有分散控制、 低延迟、
    灵活信任和渐进安全四个关键属性. 同年, 超级账本的锯齿湖项目将 Ripple 和
    SCP 共识相结合, 提出了法定人数投票 (Quorum voting) 共识算法,
    以应对那些需要即时交易最终性的应用场景. 2016 年,
    中国区块链社区NEO(原名小蚁) 提出一种改进的拜占庭容错算法 dBFT, 该算法在
    PBFT 的基础上借鉴了 PoS 设计思路, 首先按照节点的权益来选出记账人,
    然后记账人之间通过拜占庭容错算法来达成共识. 该算法改进了 PoW 和 PoS
    缺乏最终一致性的问题, 使得区块链能够适用于金融场景.2016 年, 图灵奖得主、
    MIT 教授 Sivio Micali提出了一种称为 AlgoRand[47]
    的快速拜占庭容错共识算法.
    该算法利用密码抽签技术选择共识过程的验证者和领导者, 并通过其设计的 BA*
    拜占庭容错协议对新区块达成共识. AlgoRand 只需极小计算量且极少分叉,
    被认为是真正民主和高效的分布式账本共识技术.2017 年,
    康奈尔大学提出了一种称为 Sleepy Consensus(休眠共识) 的新算法 [48].
    这种共识针对的是互联网环境下大规模的共识节点中可能多数都处于离线状态,
    仅有少数节点在线参与共识过程的实际情况. 该研究证明,
    传统共识算法无法在这种环境下保证共识的安全性. 而采用休眠共识算法,
    只要在线诚实节点的数量超过故障节点的数量,
    即可保证安全性和鲁棒性.综上所述, 区块链共识算法的演进历史如图 2所示, 表
    1 则给出了每一种共识算法的提出时间、 拜占庭容错性能、
    基础算法以及具有代表性的应用系统或平台.5
    总结与展望共识算法是区块链系统的关键要素之一,
    已成为当前信息领域的一个新的研究热点. 本文对目前已经提出的 32
    种主流区块链共识算法进行了系统性的梳理与分析. 需要说明的是,
    由于近年来共识算法研究发展较快,
    本文讨论的共识算法可能仅为实际共识算法的一个子集,
    尚存在若干新兴或者小众的共识算法未加以讨论,
    同时一些较新的共识算法仍在不断试错和优化阶段.
    本文工作可望为后续的研究与应用提供有益的启发与借鉴.以目前的研究现状而言
    [49] [50],
    区块链共识算法的未来研究趋势将主要侧重于区块链共识算法性能评估、
    共识算法 – 激励机制的适配优化、
    以及新型区块链结构下的共识创新三个方面.首先,
    区块链共识算法在经历过一段百花齐放式的探索和创新之后,
    势必会趋向于收敛到新共识算法的性能评估和标准化方面的研究. 目前,
    共识算法的评价指标各异, 但一般均侧重于社会学角度的公平性和去中心化程度,
    经济学角度的能耗、 成本与参与者的激励相容性,
    以及计算机科学角度的可扩展性 (交易吞吐量、 节点可扩展等)、
    容错性和安全性等. 如何结合具体需求和应用场景 [51][52],
    自适应地实现针对特定性能评价目标的共识机制设计与算法优化,
    将是未来研究的热点之一.其次, 区块链的共识算法与激励机制是紧密耦合、
    不可分割的整体, 同时二者互有侧重点:
    共识算法规定了矿工为维护区块链账本安全性、
    一致性和活性而必须遵守的行为规范和行动次序;
    激励机制则规定了在共识过程中为鼓励矿工忠实、
    高效的验证区块链账本数据而发行的经济权益, 通常包括代币发行机制、
    代币分配机制、 交易费定价机制 [53]等. 从研究角度来看,
    如果将区块链系统运作过程建模为矿工和矿池的大群体博弈过程 [54] 的话,
    那么共识算法将决定其博弈树的结构和形状、
    激励机制将决定矿工和矿池在博弈树中每个叶子结点的收益.因此,
    区块链共识算法和激励机制不仅各自存在独立优化的必要性, 更为重要地是共识 –
    激励二元耦合机制的联合优化、 实现共识与激励的“ 适配”,
    这是解决区块链系统中不断涌现出的扣块攻击、 自私挖矿等策略性行为、
    保障区块链系统健康稳定运行的关键问题, 迫切需要未来研究的跟进.最后,
    随着区块链技术的发展、 特别是数据层的技术和底层拓扑结构的不断创新,
    目前已经涌现出若干新兴的区块“ 链” 数据结构, 例如有向无环图(Directed
    acyclic graph) 和哈希图 (HashGraph)等.
    这些新数据结构将以单一链条为基础的区块链技术的范畴拓展为基于图结构的区块“
    链” 或分布式账本. 例如适用于物联网支付场景的数字货币IOTA 即采用称为“
    Tangle (缠结)” 的 DAG 拓扑结构, 其共识过程以交易 (而非区块) 为粒度,
    每个交易都引证其他两个交易的合法性、 形成 DAG 网络,因而可以实现无区块
    (Blockless) 共识;HashGraph共识则更进一步, 基于 Gossip of gossip
    协议和虚拟投票等技术, 以交易为粒度, 在特定的 DAG
    结构上实现公平和快速的拜占庭容错共识.
    这些新型区块拓扑结构及其共识算法是未来发展趋势之一,
    建立在这些新型数据结构之上的共识算法也值得深入研究.

类似比特币这样的去中心化数字货币系统,要求在没有中心节点的情况下保证各个诚实节点记账的一致性,就需要区块链来完成。

所以区块链技术的核心是在没有中心控制的情况下,在互相没有信任基础的个体之间就交易的合法性等达成共识的共识机制。

区块链为什么需要共识机制?

分布式系统中,多个主机通过异步通信方式组成网络集群。在这样的一个异步系统中,需要主机之间进行状态复制,以保证每个主机达成一致的状态共识。

异步系统中,可能出现无法通信的故障主机,而主机的性能可能下降,网络可能拥塞,这些可能导致错误信息在系统内传播。因此需要在默认不可靠的异步网络中定义容错协议,以确保各主机达成安全可靠的状态共识。

利用区块链构造基于互联网的去中心化账本,需要解决的首要问题是如何实现不同账本节点上的账本数据的一致性和正确性。

这就需要借鉴已有的在分布式系统中实现状态共识的算法,确定网络中选择记账节点的机制,以及如何保障账本数据在全网中形成正确、一致的共识。

算法的假设条件

在实际情况下,根据不同的假设条件,有很多不同的共识算法被设计出来。这些算法各有优势和局限。算法的假设条件有以下几种情况:

1)故障模型:非拜占庭故障/拜占庭故障。

2)通信类型:同步/异步。

3)通信网络连接:节点间直连数。

4)信息发送者身份:实名/匿名。

5)通信通道稳定性:通道可靠/不可靠。

6)消息认证性:认证消息/非认证消息。

在区块链网络中,由于应用场景的不同,所设计的目标各异,不同的区块链系统采用了不同的共识算法。

一般来说,在私有链和联盟链情况下,对一致性、正确性有很强的要求。一般来说要采用强一致性的共识算法。而在公有链情况下,对一致性和正确性通常没法做到百分之百,通常采用最终一致性(Eventual
Consistency)的共识算法。

区块链的共识机制目前主要有4类:PoW、PoS、DPoS、分布式一致性算法

(1)PoW

PoW(工作量证明),也就是像比特币的挖矿机制,矿工通过把网络尚未记录的现有交易打包到一个区块,然后不断遍历尝试来寻找一个随机数,使得新区块加上随机数的哈希值满足一定的难度条件,例如前面10位是零。

找到满足条件的随机数,就相当于确定了区块链最新的一个区块,也相当于获得了区块链的本轮记账权。

矿工把满足挖矿难度条件的区块在网络中广播出去,全网其他节点在验证该区块满足挖矿难度条件,同时区块里的交易数据符合协议规范后,将各自把该区块链接到自己版本的区块链上,从而在全网形成对当前网络状态的共识。

比特币和以太坊都是基于PoW的共识机制。

优点:1.完全去中心化,节点自由进出,避免了建立和维护中心化信用机构的成本。

2.只要网络破坏者的算力不超过网络总算力的50%,网络的交易状态就能达成一致。

缺点:1.目前比特币挖矿造成大量的资源浪费;

2.挖矿的激励机制也造成矿池算力的高度集中,背离了当初去中心化设计的初衷。

3.更大的问题是PoW机制的共识达成的周期较长,每秒只能最多做7笔交易,不适合商业应用。

(2)PoS

PoS权益证明,要求节点提供拥有一定数量的代币证明来获取竞争区块链记账权的一种分布式共识机制。

如果单纯依靠代币余额来决定记账者必然使得富有者胜出,导致记账权的中心化,降低共识的公正性,因此不同的PoS机制在权益证明的基础上,采用不同方式来增加记账权的随机性来避免中心化。

例如点点币(PeerCoin)PoS机制中,拥有最多链龄长的比特币获得记账权的几率就越大。NXT和Blackcoin则采用一个公式来预测下一个记账的节点。拥有多的代币被选为记账节点的概率就会大。

以太坊将会从目前的PoW机制转换到PoS机制,从目前看到的资料看,以太坊的PoS机制将采用节点下赌注来赌下一个区块,赌中者有额外以太币奖,赌不中者会被扣以太币的方式来达成下一区块的共识。

优点:在一定程度上缩短了共识达成的时间,降低了PoW机制的资源浪费。

缺点:1.破坏者对网络攻击的成本低,网络的安全性有待验证。

2.拥有代币数量大的节点获得记账权的几率更大,会使得网络的共识受少数富裕账户支配,从而失去公正性。

(3)DPoS

DPoS(股份授权证明)机制,类似于董事会投票。

比特股(bitshares)和steem采用的DPoS机制是持股者投票选出一定数量的见证人,每个见证人按序有两秒的权限时间生成区块,若见证人在给定的时间片不能生成区块,区块生成权限交给下一个时间片对应的见证人。

持股人可以随时通过投票更换这些见证人。DPoS的这种设计使得区块的生成更为快速,也更加节能。

优点:大幅缩小参与验证和记账节点的数量,可以达到秒级的共识验证。

缺点:1.选举固定数量的见证人作为记账候选人有可能不适合于完全去中心化的场景。

2.在网络节点数少的场景,选举的见证人的代表性也不强。

以上三种算法多用于共有链。

(4)分布式一致性算法

分布式一致性算法是基于传统的分布式一致性技术。其中有分为解决拜占庭将军问题的拜占庭容错算法,如PBFT。

另外解决非拜占庭问题的分布式一致性算法(Pasox、Raft),该类算法目前是联盟链和私有链链场景中常用的共识机制。

优点:实现秒级的快速共识机制,保证一致性。

缺点:去中心化程度不如公有链上的共识机制;更适合多方参与的多中心商业模式。

上述内容是根据《区块链技术指南》整理出来的共识机制的基础内容。

共识机制是区块链的核心技术,而PoW和DPoS这两种共识机制的优点在于依靠审核、匿名性较好、流动相对自由,这两种机制是目前在数字货币领域应用较为广泛的。

共识机制的基础知识——读《区块链技术指南》笔记

区块链学习基础篇—模型结构(5) –
简书

图片 1

发表评论

电子邮件地址不会被公开。 必填项已用*标注

CopyRight © 2015-2020 普京集团娱乐网 All Rights Reserved.
网站地图xml地图