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

区块链共识算法的发展现状与展望
摘 要 一起算法是区块链技能的中心要素, 也是近年来散布式体系研讨的热门. 本文体系性地整理和评论了区块链开展进程中的 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 结构上完结公正和快速的拜占庭容错一起. 这些新式区块拓扑结构及其一起算法是未来开展趋势之一, 建立在这些新式数据结构之上的一起算法也值得深化研讨.

发表评论

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