doi：10.3969/j.issn.1671-1122.2021.06.005
吴奕，仲盛
（南京大学计算机科学与技术系，南京 210023）
摘 要：共识算法作为区块链技术的关键要素和核心组件，是近年来分布式系统技术发展前沿热点。随着比特币和区块链技术快速发展，新的共识算法不断被提出，
改进的算法不断被验证。粗略统计，当前有正式名称的共识算法超过50种。文章首先
系统地阐述和讨论了当前区块链技术中多种共识算法的分类和优缺点，然后详细论述
了分布式一致性算法及共识领域里程碑式的成果和结论，最后结合相关研究对Raft区
块链共识算法进行改进。
关键词：区块链；共识算法；分布式系统；Raft
中图分类号：TP309 文献标志码： A 文章编号：1671-1122（2021）06-0036-09
中文引用格式：吴奕，仲盛.区块链共识算法Raft研究[J].信息网络安全，2021，21（6）：36-44.
英文引用格式：WU Yi, ZHONG Sheng. Research on Raft Consensus Algorithm for Blockchain[J]. Netinfo Security, 2021, 21(6): 36-44.
Research on Raft Consensus Algorithm for Blockchain
WU Yi, ZHONG Sheng
(Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China)
Abstract: Consensus algorithm is not only a key component of blockchain technology, but also a hot topic in distributed systems research in recent years. New consensus algorithms
have been proposed during the quickly-growing of Bitcoin and blockchain technology,
followed by the verification of those improved algorithms. And there are more than 50
consensus algorithms which have official names. This paper studies some consensus
algorithms and introduces the classic distributed consistency algorithms, as well as the
milestone research efforts and the key conclusions of distributed consensus algorithms.
This paper propose two approaches to improve the Raft consistency algorithms, and hope
this paper could be a useful guidance and reference for the future innovation work of novel
consensus algorithms and the development of blockchain technology.
Key words: blockchain; consensus algorithms; distributed systems; Raft
收稿日期：2021-02-04
基金项目：国家重点研发计划[2020YFB1005900]
作者简介：吴奕（1975—），男，江苏，工程师，硕士，主要研究方向为网络空间安全；仲盛（1974—），男，江苏，教授，博士，主要研究方向为网络空间安全、应用密码学。
通信作者：
0 引言
从中本聪发布比特币白皮书[1]的一刻起，互联网便处于新的变革起点——价值互联网。区块链技术既具有广阔的应用前景又存在各种分歧，其带来的价值表示和价值转移功能正在逐步显现出来。区块链领域的专家、学者关注的是该技术的性能和安全，并以此为基础实现应用的落地。因此，无论将区块链看做P 2P 分布式系统还是分布式数据库，都应关心其技术优势并不断完善，以求突破现在的局限性。本文首先对区块链技术框架进行介绍，阐述了共识算法的重要性和必要性；然后分类对现有区块链共识算法进行比较，并介绍了共识领域里程碑式的成果和结论；接着详细论述了Raft 区块链共识算法；最后结合相关研究对Raft 区块链共识算法进行了改进。
1 区块链基础框架
目前还没有对区块链规范的统一定义，被广泛接受的概念认为：区块链是将数据按区块组织并加密，然后按照生成的时间顺序形成的一种链式结构，其不可篡改性和去中心化性通过共识算法维护，是一
种分布式数据库或共享账本[2-5]。区块链技术提供了一个基于P 2P 网络、去中心化、开放的应用环境，其架构如图1所示。
应用层
Dapp 加密货币
企业级联盟
共识层
网络层
证明类Pox
BFT 类混合类
数据层
账本副本存储数据打包聚合数据序列化原子数据记录
加密函数组件
哈希函数
数字签名非对称加密Merkle 树
图1 区块链架构
1）数据层
数据区块和链式结构组成数据层，通过哈希指针为每个节点进行统一链接，从而形成完整的链式结构。
2）网络层
网络层由组网方式和网络数据传输协议组成，根据区块链系统使用的网络架构封装相关的协议模块。最早由中本聪提出的区块链网络架构基于P 2P 网络，可以连接并组织分布在世界各地的节点。分布式系统具有平等、自治、开放的特性。
3）共识层
共识层由各类共识算法及其相关组件构成，也是区块链系统的核心，是对分布式系统长期研究成果的应用。一些共识算法采用了激励机制，鼓励公有链中的节点参与出块。
4）应用层
应用层作为系统开发和应用部署的接口，已从脚本代码发展到支持多种编程语言接口的智能合约。
2 分布式一致性和共识算法
分布式系统的核心问题之一是如何保证一致性。为保证系统中所有节点的数据完全相同，经典的方法是利用状态机机制保证某提案的一致性。将较抽象的状态机机制实现方法称为共识算法。
2.1 CAP 和FLP
由于分布式系统（如区块链系统）引入了多个节点，所以系统复杂性会增大，导致各种情况出现。随
着节点数量的增加，区块链复杂性不断加大，节点故障、失效甚至宕机的概率不断上升，从而增加了解决分布式系统的各种边界条件、意外情况及分布式一致
性问题的难度。客观来说，在一个分布式系统中，除了节点失效会导致一致性不易达成外，节点之间
的网络通信受到干扰甚至阻断、分布式系统中各节点存在的运行速度差异、可能存在的恶意节点等因素都是解决分布式一致性面临的难题。
1985年，FISCHER [6]等人提出了FLP 定理：在异步通信场景中，即使只有一个进程失败，也不存在任何
算法能够保证进程能够达到一致性，即不存在一个可以解决一致性问题的确定性算法。2002年，GILBERT[7]等人证明了BREWER[8]提出的猜想，并确立为CAP定理[7]：在一个分布式系统中，一致性（Consistency）、可用性（A vailability）、分区容错性（Partition Tolerance）三者不可得兼。由CAP和FLP定理的证明可知，如果适当放宽条件，则可能设计出满足某一特定系统环境、符合实际需要的共识算法。
在异步网络模型中，所有节点没有共同时钟，只能根据接收到的消息作出判断，不能同时保证一致性、可用性和分区容错性，因此这样的系统只能满足3种特性中的2种。此处的一致性指强一致性，即所有节点接收到同样的操作时必须按照完全相同的顺序执行，被一个节点提交的更新操作必须立即反
映到其他通过异步或部分同步网络连接的节点上。因此，异步网络中要同时满足一致性和分区容错性，只能中心化存储所有数据，并通过其他节点将请求发送到中心节点。
在实际应用中并不存在绝对异步的网络环境，每个节点都可以拥有自己的时钟，虽然这些时钟的时间完全不同，但刷新频率完全相同。因此可以通过时钟得到接收消息的间隔时间，在这种较为宽松的前提下，就能获得到更好的效果。在部分同步的网络环境中依然无法同时保证一致性、可用性和分区容错性，但通过时钟可以得到消息发出到消息回应的间隔，进而通过设置超时时间解决信息丢失问题，在一定程度上缓解了不一致问题。
另外，主流的分布式系统都选择最终一致性替代强一致性。网络延时导致分布式系统无法同时保证强一致性和可用性。一味追求强一致性的系统必然导致系统的可用性急剧降低，设计分布式系统时可考虑在一致性和可用性之间做出权衡，降低对一致性的要求。假设可以满足以下两个条件：1）节点之间可以正常直接通信；2）出现的冲突可以并能够在可容忍的有限时间内解决。当多个节点的状态出现冲突，如果系统中存在足够多的节点能够沟通，就能在有限时间内将冲突解决，这样状态冲突的节点就可恢复一致，分布式系统就能够达到最终一致性。
排灌机械工程学报
2.2 共识算法分类
自20世纪以来，众多学者致力于共识算法的研究，随着CAP和FLP定理的提出及区块链技术的发展，
学者更加关注共识算法的实际应用。随着比特币和区块链技术的快速发展，新的共识算法不断被提出，改进的算法不断被验证。粗略统计，当前有正式名称的共识算法超过50种[9-12]。新的共识算法因为提出时间较晚，目前大多处于实践验证阶段，但很多算法具有明显的科研创新特，具有很大的应用潜力[13]。本文结合共识算法的历史演进，将当前共识算法划分为以下6类。
1）工作量证明类共识算法
粘着语
工作量证明（Proof of W ork，PoW）共识算法是第一个被应用到区块链中的共识算法。比特币白皮书指出该算法是能够识别“双花（Double Spend）”问题的分布式无信任共识算法。以比特币PoW共识算法为例，参与者如果想要在区块链中添加一块交易，必须花费金钱或资源完成某种“复杂但无用”的工作，类似投名状，在危害系统的同时自身利益也会受损。该环境下如果参与者提交的超过一半的工作是可信任的，则区块链系统是安全的。
PoW共识算法出块速度慢、耗能巨大，“复杂但无用”的计算是算力的浪费，因此该算法饱受争议，但其改进和变种算法也很多。常见的PoW类共识算法有容量证明（Proof of Capacity，PoC）共识算法、空间证明（Proof of Space，PoSpace）共识算法、历史证明（Proof of History，PoHistory）共识算法、燃烧证明（Proof of Burn，PoBurn）共识算法、存在证明（Proof of Existence，PoExistence）共识算法。
2）权益证明类共识算法
权益证明（Proof of Stake，PoS）共识算法用来替代PoW算法，不需要节点完成“复杂但无用”的工作，从而克服了PoW的缺点。PoS算法根据用户具有的系统的一些权益确定出块节点，用户拥有的权益越大，
出块的可能性越大。不仅如此，攻击PoS系统也比攻击PoW系统的代价大，攻击PoS系统可能意味着攻击者会失去自己的全部权益。常见的PoS类算法有授权PoS（Delegated Proof of Stake，DPoS）共识算法、权重证明（Proof of W eight，PoW eight）共识算法、声誉证明（Proof of Reputation，PoR）共识算法、所用时间证明（Proof of Elapsed Time，PoET）共识算法、置信度证明（Proof of Believability，PoB）共识算法。
3）拜占庭容错类共识算法
区块链网络环境是典型的拜占庭将军问题环境，有运行正常的服务器，有宕机的服务器，还可能有恶
王茂俊意的服务器，即拜占庭错误节点。拜占庭容错（Byzantine Fault Tolerance，BFT）共识算法的核心是形成正常节点间对网络状态的共识。目前，BFT共识算法有多个版本和变体，每种版本都具有自身的优势和缺点。常见的BFT类共识算法有BFT、实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）算法、授权拜占庭容错（Delegated Byzantine Fault Tolerance，DBFT）算法、恒星共识（Stellar Consensus）算法。
4）有向无环图类共识算法
有向无环图（Directed Acyclic Graphs，DAG）被看作是具有更通用形式的区块链，其独特的组织结构不同于传统区块链数据以树型结构进行组织，而是以DAG结构进行组织。树型结构是DAG的一种特例，显而易见，DAG上的共识算法适用于树型结构，即DAG 共识算法可用于传统区块链。与树型结构相比，DAG 可支持并发出块和执行。当前存在多种变体DAG，常见的有Tangle（IOT A）共识算法、Hashgraph共识算法、Holochain共识算法、Nano共识算法、ByteBall共识算法。
5）经典Paxos类共识算法
经典Paxos类共识算法主要包括Paxos和Raft两种共识算法及其变种[14]。LAMPORT[14]提出了近乎公理化的分布式一致性算法Paxos，虽然后续不断改进，但仍难以理解，不易实现应用。2014年，ONGARO[15]等人提出了Raft算法，并证明了Raft算法和Paxos算法一
样安全，用于替代Paxos算法。
6）混合类
该类算法是其他5类算法的混合应用，主要面对特定的应用场景，常见的算法有延迟工作量证明（Delayed Proof-of-work，DPoW）共识算法、权益流通证明（Proof of Stake V elocity，PoSV）共识算法、活动证明（Proof Of Activity，PoActivity）共识算法、身份证明（Proof of Identity，PoI）共识算法、SPECTRE共识算法。
2.3 Paxos算法与Raft算法
分布式系统领域中，Paxos算法和Raft算法主要用于解决分布式系统中的一致性问题，Raft算法提出之前，主要应用Paxos算法解决一致性问题。Paxos算法首先实现单条日志项的复制以达成单一决策一致，进而通过组合单决策实例促进一系列决策达成。Paxos算法中集成员关系是可变的，并能够保证活性和安全性。通常情况下Paxos算法很高效，且其正确性已经被证明。但Paxos算法有两大明显的缺点：1）Paxos算法特别难以理解；2）Paxos算法没有提供较好的构建现实系统的基础，以至于难于实际应用[14,15]。
2.3.1 Paxos算法
Paxos算法可使分布式网络中的节点出现错误时仍然保持一致，在没有恶意节点的前提下保证系统中节点的一致性，也是第一个被证明的完备的共识算法。作为一类协议，Paxos算法包含Basic Paxos、Multi-Paxos等变种。
2.3.2 Raft算法
Raft算法本质是Paxos算法的完备变种。Raft算法以简洁的方式解决了Paxos算法难以理解及难以实现的缺点。Raft算法通过简化Paxos算法模型，设置领导人（Leader）、跟随者（Follower）和候选人（Candidate）3种角，并在Paxos算法的基础上进行限制：1）虽然节点内部的状态机是有序的，但在Raft算法中追加日志的操作必须是连续的。2）Raft算法只允许拥有最新、最全日志的节点当选Leader。Paxos算法选择Leader没
有限制，但选择Leader之后必须将Leader中的日志补全，因为任意节点都可以写日志。与Paxos算法不同，Raft 算法所有Follower的日志都是Leader的子集，且Raft算法对日志追加的方式和选举过程进行了限制，所以选举出一个强领导人在实现上更加容易和简单。
Leader决定是否存储新日志条目及存储在何处，且数据都是由Leader发送到其他节点。如果Leader和其他节点失去连接（宕机或网络故障），则会重新选举Leader。通过Leader方式，Raft算法采用以下3个相对独立的子问题将一致性问题分解。
1）Leader选举：当现任Leader宕机时，需要选举一个新Leader。
2）日志复制：Leader从某个节点接收日志后，必须将该日志复制到系统中的其他节点，强制要求其他节点的日志与自己保持一致。
极端主义3）安全性：状态机安全是Raft算法安全性的关键。如果一个确定的日志条目被节点应用到状态机中，那么该日志索引位置不能被其他节点应用到不同的指令中。
从理论上讲，支持并发日志追加的Paxos算法比Raft算法有更优秀的性能，但其理解和实现比较复杂。Raft算法实现更简洁，可以避免一些边界问题带来的复杂性。
下面介绍Raft算法的选主（Leader）过程和节点的角转换。当一个节点加入系统时，该节点是Follower 角，如果此时系统中存在Leader，该节点会一直保持Follower角，直到新的选举开始；如果系统中没有Leader或当前Leader任期已满，系统会发起选举，所有节点变成Candidate，并向其他节点邀票，当某个Candidate节点首先获得系统认可的足够多的选票时，该节点成为新一任Leader，其他节点则由Candidate转换为Follower。反复重复该过程。
然而，这样的工作流程可能产生投票分歧问题，即在选举过程中多个节点获得了相同数量的选票，而且都是获得选票最多的节点。这样系统就无法确定唯一的节点成为Leader，导致选举失败，只能重新发起选举。针对这一问题，本文对Raft算法进行改进，以减少选举失败次数。
3 Raft算法改进
本文主要从以下两个方面对Raft算法进行改进：1）改变选主方式，提高选主成功率，减少选举失败次数；2）在不影响Raft算法性能的前提下，针对区块链应用场景，通过增加Follower对数据块的校验，发现和主动屏蔽潜在的恶意节点（包括Leader）。
3.1 Raft算法的选主改进
失歌症测试
Raft算法采用随机的选举超时时间来解决投票分歧问题。具体流程如下：为了防止投票分歧，Raft算法从一个固定的时间间隔中随机选择选举的超时时间。该方法可把节点分散开来，大多数情况下只会有1个节点发生超时，且能够保证在其他节点在超时之前赢得选举，并发送心跳包。处理投票分歧时，每个Candidate在一次选举开始时重置其随机的选举超时时间，等待开始下一次选举。该方法减少了新一轮选举中再次发生选举分歧的可能性。然而，随着系统节点数的增加，各节点随机固定的超时时间的重复几率也会增加，加上众多节点间的网络延时，必然会导致整个系统的分区化，即同时在各分区产生一个伪Leader（得到部分投票但不满足当选Leader所必须投票数量）分票，从而导致这一
天津水灾轮选主失败，进入下一轮重新选举。
为了易于理解和实现，Raft算法将一致性问题分解成3个相对独立的子问题，Leader选举就是其中之一。作为单独的功能模块，本文采取以下改进方法：为每个节点增加1 bit的标志数据位（简称“C标志位”，0表示不可以从Follower切换到Candidate，1表示可以从Follower切换到Candidate，初始值为1），表征该节点因没有收到Leader发送的心跳包而超时后是否具有从Follower切换到Candidate的资格。需要说明的是，以下两种情况可能导致Follower无法收到Leader发送的心跳包。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议