作者：qinyutong、chengyueqiang
共识机制（Consensus Mechanism）是区块链事务达成分布式共识的算法，随着区块链这一技术不断被推广，共识机制作为区块链的核心，也愈加受到人们的关注。共识机制在保护数据的一致性方面具有重要作用。本文选取了 8 种常用的共识机制，根据机制的原理、运行过程中的角色、算法流程以及优缺点等方面，对工作量证明、权益证明、容量证明等机制进行详细介绍。同时，文章也对相似的机制进行对比分析。从而加深人们对共识机制的了解，加速区块链技术的发展。
1 引言
区块链是比特币的底层技术，类似于数据库账本，而共识机制是去中心化的分布式账本中的规则核心，决定了区块链的安全性、可扩展性和去中心化程度等许多重要特性。
共识机制是指以去中心化的方式就网络的状态达成统一协议的过程。也被称为共识算法，有助于验证和验证信息被添加到分类账簿，确保只有真实的事务记录在区块链上 [12]。因此，共识机制负责安全地更新分布式网络中的数据状态。已经硬编码到协议中的规则确保在全球计算机网络中总是能找到唯一的数据来源并达成一致。这些规则保护整个网络，实现无需信任的网络，而无需中央数据或中介。
共识机制是决定按照哪一个参与节点记账，和确保交易安全完成的重要手段。[8] 共识机制需要平衡效率和安全的关系，安全措施越复杂，相应的处理时间越慢。而想要提高处理速度，简化安全措施的复杂度是非常重要的一步。
共识机制同时满足一致性和有效性。一致性是指所有诚实节点保存的区块链前缀部分完全相同，而有效性是指由某诚实节点发布的信息终将被其他所有诚实节点记录在自己的区块中 [11]。共识机制确保区块链是容错的，因此是可靠和一致的。与中心化系统不同，用户不必信任系统中的任何人，区块链共识机制中嵌入的协议规则可以确保只有有效和真实的交易才可以被记在公共透明的账簿中，嵌入网络的协议规则保证了公共分类帐的状态总是随着大众的共识变换而更新。
区块链的去中心化的一个重要优势是分配授权，任何人都能在同一个基础上参与进来。而共识机制可以确保区块链不存在区别对待，从而达到公平分配。由于公共区块链具有开源这一特性，使任何人都可以监督并验证底层源代码对网络中的所有参与者是否公平 [7]。
共识机制可以通过激励好的行为，在某些情况下，惩罚坏的行为者来实现这一点。例如在工作量证明这一机制中，通过奖励比特币给矿工这一方式，奖励他们每一笔交易的担保和验证。任何运算和安全维护都需要大量的算力和钱财，而共识机制可以使这些资源将更好地用于为系统工作，而不是针对系统。
常见的共识机制有：PoW（工作量证明）、PoS（权益证明）、DPoS（委任权益证明）、PBFT（实用拜占庭容错算法）、POOL（验证池）等。
2 PoW：Proof of Work（工作量证明）
2008 年，在比特币白皮书（Bitcoinswhitepaper）上，PoW 第一次得到重视。PoW 是依赖机器进行数学运算（与或运算，计算出一个满足规则的随机数）来获得本次记账权 [1]，向全网其他节点发送本次需要记录的数据，由其他节点验证后，达成共识后对数据进行存储。PoW 最早是一个经济学名词，它是指系统为达到某一目标而设置的度量方法。简单理解就是一份证明 [3]，用来确认你做过一定量的工作。监测工作的整个过程通常是极为低效的，而通过对工作的结果进行认证来证明完成了相应的工作量，则是一种非常高效的方式。
举例说明，10+？=12，谁先解出来答案，谁就收获。
一句话概括：干的越多，收的越多（有且仅有实际劳动，才能获得成果）
图 1: PoW 的工作原理图示
2.1 名词解释
哈希函数 Hash 哈希函数是一个单向加密函数，哈希算法能够获取任意数量的数据，并返回一个固定长度的字符串 [6]，该字符串对于特定的输入是完全唯一的。
Nonce 一个只能使用一次的随机数。
矿工 Miners 加密货币网络中独立的交易处理器，其目标是验证交易。通常也被称作 Full Node 或 Node。
2.2 角色
工作者 需要完成的工作必须有一定的量，这个量由工作验证者给出；
工作者无法找到很快完成工作的办法；
工作者无法自己”创造工作”，必须由验证者发布工作。
验证者 可以迅速的检验工作量是否达标。
2.3 优点
1. 算法简单，容易实现。
2. 节点间无需交换额外的信息即可达成共识（节点间自由进出）。
3. 破坏系统需要投入极大的成本。
4. 需要全网所有节点参与，完全去中心化。
2.4 缺点
1. 目前比特币已经吸引全球大部分的算力，新的区块链必须找到一种不同的散列算法，很难使用与过去相同的算力得到相同的安全保障。
2. 大量的资源浪费。
3. 共识达成的周期较长，不适合商业应用（容易产生分叉，需要等待多个确认，区块的确认时间难以缩短）。
4. 永远没有最终性，需要检查点机制来弥补最终性。
2.5 应用实例
比特币中，使用 PoW 确认区块的有效性（只要该 CPU 耗费的工作量能够满足该工作量的证明机制，那么除非重新完成相当的工作量，该区块的信息就不可更改）
2.6 问题解释
为什么说 PoW 消耗能源的问题严重？
——因为矿工（Miners）的每一个猜测（guess）都需要消耗一台计算机产生一定数量的能量。目前，整个比特币网络的哈希率（Hash rate）为～17，000，000 TH/s，即整个网络每秒 17,000,000,000,000,000,000 个猜测（guess）。这种能源需求与匈牙利的消费量大致相同。
3 PoS：Proof of Stake（权益证明）
2012 年，PoS 作为点点币（Peercoin）的介绍首次被提出。PoS 是 PoW 的一种升级共识机制，不需要消耗电力来进行运算，根据每个节点记账权的获得难度，令其与节点持有的权益成反比，等比例的降低挖矿难度，从而加快找随机数的速度。为了保证其简单，PoS 中没有矿工（Miners），而是改为了验证员（Validators）。仍然是基于哈希运算竞争获取记账权的方式，容错性与 PoW 相同。PoS 是基于矿工们目前拥有的数字货币数量分配，一种根据你持有货币的量和时间进行利息分配的制度，在 PoS 模式下，你的“挖矿”收益与你的币龄成正比，而与电脑的计算性能无关。
举例说明，PoS 类比成我们手中的钞票。当我们拥有的钞票越多，那在生活中所获得的权益就越多。一句话概括：持有越多，获得越多（在银行存钱得利息）
3.1 名词解释
验证员 Validators 验证器，要验证交易，验证器必须下注一定数量的 stake，stake 的大小决定了验证器验证下一区块的可能性。
3.2 优点
1. 在一定程度上缩短了共识达成的时间，转账效率提高。
2. 不再需要大量消耗能源和算力挖矿。
3.3 缺点
1. 还是需要挖矿，本质上没有解决商业应用的痛点。
2. 所有的确认都只是一个概率上的表达，而不是一个确定性的事情，理论上有可能存在其他攻击影响。
3. 去中心化程度，容易出现强者恒强的情况，持币大户持币生息，从而出现垄断问题。
3.4 问题解释
PoS 在改善了 PoW 消耗能源的问题后，还有哪些问题需要考虑？
——诸多问题中拥有最大争议的问题是，如果过多的权重被赋予非常多的财富或旧节点，网络会很快变得不公平。
表 1: PoW 和 PoS 的比较
4 DPoS：Delegated Proof of Stake（委任权益证明）
与 PoS 的主要区别在于节点选举若干代理人，向代理人授权选票后，由代理人验证和记账，钱包即为状态监视器。其合规监管、性能、资源消耗和容错性与 PoS 相似。类似于董事会投票，持币者投出一定数量的节点，由节点选择代理人，代理他们进行验证和记账。
举例说明，如果持币者 A 支持了代理人 50 个币，持币者 B 支持了代理人 10 个币，那么 A 的投票权重是 B 的 5 倍。
一句话概括：节点选举若干代理人，由代理人验证和记账
4.1 组成部分
1. 选出一组区块生产者：选举过程由 token 持有者决定，选举出的生产者的表现会影响到整个网络的工作情况，进而影响到 token 持有者的利益。
2. 调度生产
4.2 算法流程（以正常操作和少数分叉为例）
1. 正常操作：正常情况下区块生产者按顺序进行生产，间隔时间是 3s。没有人错失生产，如下便是最长的链（箭头指向前一个区块）。
图 2: 正常操作
2. 少数分叉：当不超过 1/3 的节点有恶意或不能工作，而产生一个分叉时，如下图的 B，这条分叉每 8 秒出一个块，而正常工作的节点每 8 秒出 2 个块 [13]。原因是按照 A,B,C,A… 的顺序，每个节点要等待相应时间才可以出块。根据最长链原则，系统依然能运行。
图 3: 少数分叉
4.3 优点
1. 大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证。
2. 通过赞成投票制，可以确保即使一个人拥有 50%的有效投票权，也不能独自选择一个出块人，保证算法安全。
3. 大多数出块人出现问题时，DPoS 仍可以继续工作。
4.4 缺点
1. 整个共识机制还是依赖于代币，很多商业应用是不需要代币存在的。
2. 弱中心化，去中心化程度不高。
4.5 应用实例
EOSIO：EOSIO 由委托证明 (DPoS) 系统维护，该系统最初是由 Larimer 创建的，现在仍被 Steemit 使用。Dan Larimer 第一次在 BitShares 使用 DPOS，它立即成为最快的区块链之一。后来 BM 将 DPOS 引入 Steem，Steem 被认为是最快和最稳定的区块链项目之一，每天处理超过 100 万交易，而只使用其容量的百分之一。
5 PBFT：Practical ByzantineFault Tolerance（实用拜占庭容错算法）
PBFT 是一种状态机副本复制算法，一般包括三种协议：一致性协议 (agreement)、检查点协议 (checkpoint) 和视图更换协议 (view change)。在保证活性和安全性（liveness and safety）的前提下提供了 (n-1)/3 的容错性。在分布式计算上，不同的计算机透过讯息交换，尝试达成共识；但有时候，系统上协调计算机（Coordinator / Commander）或成员计算机（Member/Lieutanent）可能因系统错误并交换错的讯息，导致影响最终的系统一致性[9]。拜占庭将军问题就根据有多少错误计算机来寻找可能的解决办法，虽然无法找到一个绝对答案，但只可以用来验证一个机制是否有效。而拜占庭问题的可能解决方法为：在 N ≥ 3F + 1 的情况下一致性是可能解决。其中，N 为计算机总数，F 为有问题计算机总数。信息在计算机间互相交换后，各计算机列出所有得到的信息，以大多数的结果作为解决办法。
一句话概括：每个“将军”根据内部状态和新消息结合运行计算或操作，从而达成个人决定，个体将决定共享，根据全部决定确定共识决定。
5.1 协议
一致性协议 至少包含若干个阶段：请求（request）、序号分配（pre-prepare）和响应（reply）。根据协议设计的不同，可能包含相互交互（prepare），序号确认（commit）等阶段。
检查点协议 算法设置周期性的检查点协议, 将系统中的服务器同步到某一个相同的状态，系统会设置一个 check-point 的时间点，在这个时刻可以定期地处理日志、节约资源并及时纠正服务器状态。
视图更 换协议 某个副本节点 i 检测出主节点作恶或者下线，会产生超时机制，启动视图更换，并将视图编号 v 变更为 v+1，同时不再接受除检查点消息（checkpoint）、视图更换消息 (view-change) 和新视图消息（new-view）外的其他消息请求。
基于全同态加密的 PSI 全同态加密技术使得对于明文的数学操作可以直接在密文上进行而不需要先将密文解密。早期的全同态加密十分低效，而它的性能在近几年才有所提高。使用全同态加密技术的 PSI 协议，通过拥有较小集合的一方将自己的集合加密以后发送给另一方，而另一方负责基于密文求两个集合的交集，然后将结果交给对方解密。使用全同态加密实现 PSI 可以达到相对较小的交互复杂度，但它的计算复杂度通常非常高，导致协议效率低下。所以，在不牺牲太多交互复杂度的情况下降低计算复杂度是基于全同态加密的 PSI 协议主要面临的挑战。
5.2 算法流程
1. 客户端发起消息：客户端 C 向主节点发送操作请求 <REQUEST,o,t,c>
o: 请求执行状态机操作
t: 客户端追加的时间戳
c: 客户端标志
REQUEST: 包含消息内容 m，以及消息摘要 d(m) 等
2. 预准备阶段: 在预准备阶段，主节点对收到的客户端请求消息签名进行验证，验证通过，基于当前视图 v 分配一个序列号 n 给收到的客户端请求，然后向所有备份节点群发送预准备消息 < <PRE-PREPARE, v, n , d>, m>
v：视图编号 m：客户端发送的请求消息 d：请求消息 m 的摘要 n：预准备消息序号
预准备消息的目的是作为一种证明，确定该请求已在视图 v 中被赋予了序号 n，从而在视图变更的过程中消息仍可被追溯。
3. 准备阶段: 副本节点 i 收到主节点的 PRE-PREPARE 消息，需要进行以下校验：
• 主节点 PRE-PREPARE 消息签名是否正确。
• 当前副本节点是否已经收到了一条在同一 v 下并且编号也是 n，但是签名不同的 PRE-PREPARE 信息。
• d 与 m 的摘要是否一致。
• n 是否在区间 [h, H] 内。
校验通过后，副本节点 i 向所有副本节点发送准备消息 <PREPARE,v, n, d, i>，并将预准备消息和准备消息在节点 i 进行保存，用于 View Change 过程中恢复未完成的请求操作。当节点 i 收到接超过 2f+1 个节点的准备消息后，就可以进入确认阶段。其中会检查这些消息的视图编号 v，消息序号 n 和摘要 d。
4. 确认阶段：进入确认阶段的节点向其他节点包括主节点发送一条 <COMMIT, v, n, d, i> 确认消息。当节点 i 接受到 2f+1 个 m 的确认消息后并满足相应条件后，消息 m 变更为 committed-local 状态，节点执行 m 的请求。在完成 m 请求的操作之后，每个副本节点都向客户端发送回复。进入 reply 阶段。
5. 回应客户端：节点 i 返回 <REPLY, v, t, c, i, r> 给客户端，r：请求操作结果。客户端如果收到 f +1 个相同的 REPLY 消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。
图 4: 注：副本 0 是主节点，副本 3 是失效节点，C 是客户端。
5.3 优点
1. 系统运转可以脱离币的存在，PBFT 算法共识各节点由业务的参与方或者监管方组成，安全性与稳定性由业务相关方保证。
2. 共识的时延大约在 2~5 秒钟，基本达到商用实时处理的要求。
3. 共识效率高，吞吐量高，可满足高频交易量的需求。
4. 不使用工作量证明的耗电模式，更加节能环保。
5.4 缺点
1. 受到节点数量的限制以及节点需要选举或许可，可扩展性及去中心化程度较弱。
2. 容错性较低，当有 1/3 或以上记账人停止工作后，系统将无法提供服务；当有 1/3 或以上记账人联合作恶，且其它所有的记账人被恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据。
6 POOL（验证池）
验证池机制是基于传统的分布式一致性技术和数据验证机制的结合，它使得在成熟的分布式一致性算法（Paxos、Raft）基础上，不需要代币也能实现秒级共识验证。
6.1 优点
1. 不需要代币也可以工作，在成熟的分布式一致性算法（Paxos、Raft）基础上，实现秒级共识验证。
2. 提高应用程序的运行速度，改善效率并降低开销。
6.2 缺点
1. 去中心化程度不如比特币。
2. 更适合多方参与的多中心商业模式。
7 PoC：Proof of Capacity（容量证明）
2015 年，该理念被 Dziembowski 等进行了形式化定义。PoC 通过分配一定数量的内存或磁盘空间用于解决服务提供者所提供挑战的方式，显示了某个人对某个服务（例如发送邮件）具有合法的兴趣。虽然 Ateniese 等人的论文 名称也是“Proof-of-space”，但它事实上一种采用 MHF（Memory Hard Function，一种计算代价取决内存的哈希算法）的 PoW 协议。PoC 是使用缓存大量数据的方法来对计算时间进行节省。
举例说明，将彩票填满硬盘驱动器，生成一个随机数，然后检查匹配数字最多的人。如果你有最匹配的号码，你就会赢得奖励。
一句话概括：储存空间越大，收的越多（有且仅有实际劳动，才能获得成果）
7.1 名词解释
哈希值 Shabal Shabal算法是一种很慢的算法，允许输入任意长度的有序位序列，甚至是一个空序列。也适应任何长度的字节流，但是由于考虑到安全性，适用长度最好小于 27 位。输入长度可以是任何整数值和 8 的倍数。假如给定一个 bit 序列，按其左右顺序索引编号，即第一位的索引为 0。使用左和右来描述有序的位序列：序列中的第一位称为最左位，最后一位称为最右位。
Plotting 绘图 产生存储大量预计算哈希值的文件，在存储器充满哈希值的文件后，仍可以参与块的创建过程。这个过程叫做绘图。
7.2 算法流程
1. 硬盘驱动器的绘图：根据硬盘驱动器的大小，制作独特的绘图文件可能需要几天甚至几周的时间。绘图时使用被称为 Shabal 的非常慢的哈希值。与 SHA-256 哈希值不同，Shabal 是比特币矿商快速使用的哈希值。由于 Shabal 哈希值很难计算，所以我们必须预先计算它们并将它们存储在硬盘上。这个过程称为绘制硬盘驱动器。
2. 块的实际挖矿：计算 0 到 4085 之间的铲斗数。假设你的计算结果是 42。然后你会去舀 42 勺 nonce 1 然后用舀的数据来计算一段时间，这叫做截止时间[5]。对硬盘上的所有 nonces 重复此过程。在计算完所有的截止日期后，你会选择最小的截止日期。截止日期表示“在允许您伪造一个块之前，自最后一个块被伪造以来必须经过的秒数”。如果在这段时间内没有其他人锻造了一个块，你可以锻造一个块并获得一个块奖励。
图 5: PoC 的工作过程图示
7.3 优点
1. 你可以使用任何普通硬盘，这样其他矿商就不会从购买专门设备中获得优势，比如用 ASIC 挖矿比特币。
2. 使用硬盘驱动器的能源效率是基于 ASIC 的采矿的 30 倍。
3. 容量证明更加分散，因为每个人都有一个硬盘驱动器。你甚至可以从你的 Android 手机的硬盘上进行挖矿。
4. 矿商不需要不断升级设备。旧硬盘可以像新硬盘一样存储数据。
5. 完成挖矿后可以清除硬盘驱动器，并将其用于最初的目的。
7.4 缺点
1. 产能开采的普遍证据可能会导致另一场军备竞赛。今天人们使用 tb 的硬盘，但是我们最终会看到 pb、exabytes 和 zettabytes。
2. 容量证明是一项相对较新的技术，在现实世界中没有经过严格的测试和挑战。
3. 目前，硬盘驱动器绘制的数据除了挖矿用途外是无用的。然而，有计划将硬盘用作重要开源信息的冗余存储。硬盘可以存储地图、维基百科文章或其他值得保存的信息。
4. 已经有恶意软件在人们的电脑上挖矿比特币。如果容量证明变得流行起来，你可能会看到恶意软件在密谋人们的硬盘。
7.5 问题解释
为什么说 PoC 是一种低电力消耗的共识机制？
——在容量证明的环境下，由于机械硬盘天生对（相对的）电力不敏感，电力成本短期内不再是矿工加入网络的敲门 砖，而机械硬盘的广泛适配性，更进一步降低了矿工加入网络的难度，目前家用电脑常用之 1~2T 硬盘即可成为挖矿设备。更进一步，容量证明实际上不储存网络数据，即使硬盘损坏也不会导致网络内容丢失，避免了 FIlecoin 时空证明中数据丢失对网络使用性的影响。
图 6: PoC 和 PoW 的比较
8 Paxos
Paxos 由 Lamport 于 1888 年在《The Part-Time Parliament》论文中首次公开。Paxos 算法解决的问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致。
Paxos 算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了 2F+1 的容错能力，即 2F+1 个节点的系统最多允许 F 个节点同时出现故障 [2]。一个或多个提议进程 (Proposer) 可以发起提案 (Proposal)，Paxos 算法使所有提案中的某一个提案，在所有进程中达成一致。系统中的多数派同时认可该提案，即达成了一致。最多只针对一个确定的提案达成一致。
8.1 角色
Proposer 提出提案 (Proposal)。Proposal 信息包括提案编号(Proposal ID) 和提议的值(Value)。
Acceptor 参与决策，回应 Proposers 的提案。收到 Proposal 后可以接受提案，若 Proposal 获得多数 Acceptors 的接受，则称该 Proposal 被批准。
Learner 不参与决策，从 Proposers/Acceptors 学习最新达成一致的提案（Value）。
8.2 原则
8.2.1 安全原则
保证不能做错的事。
1. 针对某个实例的表决只能有一个值被批准，不能出现一个被批准的值被另一个值覆盖的情况；(假设有一个值被多数 Acceptors 批准了，那么这个值就只能被学习)。
2. 每个节点只能学习到已经被批准的值，不能学习没有被批准的值。
8.2.2 存活原则
只要有多数服务器存活并且彼此间可以通信，最终都要做到的下列事情：
1. 最终会批准某个被提议的值。
2. 一个值被批准了，其他服务器最终会学习到这个值。
8.3 算法流程
1. 第一阶段：Prepare 阶段。Proposer 向 Acceptors 发出 Prepare 请求，Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。
2. 第二阶段：Accept 阶段。Proposer 收到多数 Acceptors 承诺的 Promise 后，向 Acceptors 发出 Propose 请求，Acceptors 针对收到的 Propose 请求进行 Accept 处理。
3. Learn 阶段。Proposer 在收到多数 Acceptors 的 Accept 之后，标志着本次 Accept 成功，决议形成，将形成的决议发送给所有 Learners。
8.3.1 算法描述
1. Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID)，向所有 Acceptors 发送 Prepare 请求，这里无需携带提案内容, 只携带 Proposal ID 即可。
2. Propose: Proposer 收到多数 Acceptors 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value，作为本次要发起的提案。如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value。然后携带当前 Proposal ID，向所有 Acceptors 发送 Propose 请求。
3. Acceptors 收到 Prepare 请求后，做出“两个承诺，一个应答”。
4. Accept: Acceptor 收到 Propose 请求后，在不违背自己之前作出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。
5. Learn: Proposer 收到多数 Acceptors 的 Accept 后，决议形成，将形成的决议发送给所有 Learners。
图 7: Paxos 算法过程
8.3.2 两个承诺，一个应答 [4]
1. 两个承诺：不再接受 Proposal ID 小于等于当前请求的 Prepare 请求；不再接受 Proposal ID 小于当前请求的 Propose 请求。
2. 一个应答：不违背以前作出的承诺下，回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID，没有则返回空值。
8.4 优点
1. 高效，节点通信无须验证身份签名。
2. Paxos 算法有严格的数学证明，系统设计精妙。
3. 容错性能: 允许半数以内的 Acceptor 失效、任意数量的 Proposer 失效，都能运行。一旦 value 值被确定，即使半数以内的 Acceptor 失效，此值也可以被获取，并不会再修改。
8.5 缺点
1. 工程实践比较难，达到工业级性能需要进行不同程度的工程优化，而有时工程设计的偏差会造成整个系统的崩溃。
2. 只适用于 permissionedsystems(私有链)，只能容纳故障节点 (fault)，不容纳作恶节点 (corrupt)。
3. 持 CFT(Crash FaultTolerant)，不支持拜占庭容错 (ByzantineFault Tolerance)。
8.6 问题解释
Multi-Paxos 和 Paxos 的关系？
——朴素 Paxos 算法通过多轮的 Prepare/Accept 过程来确定一个值，我们称这整个过程为一个 Instance。Multi-Paxos 是通过 Paxos 算法来确定很多个值，而且这些值的顺序在各个节点完全一致，概括来讲就是确定一个全局顺序 [10]。
9 Raft
Raft 最初是一个用于管理复制日志的共识算法，它是一个为真实世界应用建立的协议，主要注重协议的落地性和可理解性。Raft 是在非拜占庭故障下达成共识的强一致协议，是一种管理复制日志的一致性算法。它的首要设计目的就是易于理解，所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。Paxos 有效的基本保障是：任意两个法定集合，必定存在一个公共的成员。分布式系统除了提升整个体统的性能外还有一个重要特征就是提高系统的可靠性。提供可靠性可以理解为系统中一台或多台的机器故障不会使系统不可用（或者丢失数据）。保证系统可靠性的关键就是多副本（即数据需要有备份），一旦有多副本，那么久面临多副本之间的一致性问题。一致性算法正是用于解决分布式环境下多副本之间数据一致性的问题的。
业界最著名的一致性算法就是大名鼎鼎的 Paxos（Chubby 的作者曾说过：世上只有一种一致性算法，就是 Paxos）。
但 Paxos 是出了名的难懂，而 Raft 正是为了探索一种更易于理解的一致性算法而产生的。
9.1 角色
Raft 要求系统在任意时刻最多只有一个 Leader，正常工作期间只有 Leader 和 Followers。
Leader 领导者 接受客户端请求，并向 Follower 同步请求日志，当日志同步到大多数节点上后告诉 Follower 提交日志。所有对系统的修改都会先经过 Leader，每个修改都会写一条日志 (Log Entry)。Leader 收到修改请求后的过程如下，这个过程叫做日志复制(Log Replication)：
图 8: 日志复制
Follower 跟从者 所有结点都以 Follower 的状态开始。如果没收到 Leader 消息则会变成 Candidate 状态。接受并持久化 Leader 同步的日志，在 Leader 告之日志可以提交之后，提交日志。
Candidate 候选人Leader 选举过程中的临时角色。会向其他结点“拉选票”，如果得到大部分的票则成为 Leader。
图 9: 三个角色之间的关系图
9.2 算法流程
1. Leader Election 领导人选举：当 Follower 在选举超时时间内未收到 Leader 的心跳消息，则转换为 Candidate 状态。为了避免选举冲突，这个超时时间是一个 150~300ms 之间的随机数。一般而言，在 Raft 系统中：
• 任何一个服务器都可以成为一个候选者 Candidate，它向其他服务器 Follower 发出要求选举自己的请求。
• 其他服务器同意了，发出 OK。注意，如果在这个过程中，有一个 Follower 宕机，没有收到请求选举的要求，此时候选者可以自己选自己，只要达到 N/2+1 的大多数票，候选人还是可以成为 Leader 的。
• 这样这个候选者就成为了 Leader 领导人，它可以向选民也就是 Follower 发出指令，比如进行记账。
• 通过心跳进行记账的通知。
• 一旦这个 Leader 崩溃了，那么 Follower 中有一个成为候选者，并发出邀票选举。
• Follower 同意后，其成为 Leader，继续承担记账等指导工作。
2. Log Replication 日志复制：Raft 的记账过程按以下步骤完成：
图 10: 记账过程
对于每个新的交易记录，重复上述过程。在这一过程中，若发生网络通信故障，使得 Leader 不能访问大多数 Follower 了，那么 Leader 只能正常更新它能访问的那些 Follower 服务器。而大多数的服务器 Follower 因为没有了 Leader，他们将重新选举一个候选者作为 Leader，然后这个 Leader 作为代表与外界打交道，如果外界要求其添加新的交易记录，这个新的 Leader 就按上述步骤通知大多数 Follower。当网络通信恢复，原先的 Leader 就变成 Follower，在失联阶段，这个老 Leader 的任何更新都不能算确认，必须全部回滚，接收新的 Leader 的新的更新。
9.3 优点
1. 比 Paxos 算法更容易理解，而且更容易工程化实现。
2. Raft 与 Paxos 一样高效，效率上 Raft 等价于 (multi-)Paxos。
3. 适用用于 permissionedsystems(私有链)，只能容纳故障节点（CFT），不支持作恶节点。最大的容错故障节点是(N-1)/2，其中 N 为集群中总的节点数量。强化了 Leader 的地位，整个协议可以分割成两个部分：Leader 在时，由 Leader 向 Follower 同步日志；Leader 失效了，选一个新 Leader。
4. 强调合法 Leader 的唯一性协议，它们直接从 Leader 的 度描述协议的流程，也从 Leader 的角度出发论证正确性。
9.4 缺点
1. 只适用于 permissioned systems (私有链)，只能容纳故障节点 (CFT)，不容纳作恶节点。
表 2: Raft 和 Multi-Paxos 的比较
参考文献
[1] Beccuti, J., and Jaag, C. The bitcoin mining game:On the optimality of honesty in proof-of-work consensus mechanism. WorkingPapers (2017).
[2] From Wikipedia, t. f. e. Paxos (computer science). https://en.wikipedia.org/wiki…_(computer_science).
[3] From Wikipedia, t. f. e. Proof of work. https://en.wikipedia.org/wiki…_of_work.
[4] Lamport, L. Paxos madesimple. https://www.microsoft.com/en-…
made-simple/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fum%2Fpeople%2Flamport%2Fpubs%2Fpaxos-simple.pdf.
[5] Team, E. Proof of capacity explained: Theeco-friendly mining algorithm. https://www.coinbureau.com/ed…
[6] 杜江天. 区块链工作量证明机制中的哈希算法探讨. 电脑编程技巧与维护 _No.394_, 4 (2018), 42–44.
[7] 杨宇光, and 张树新. Review and research for consensus mechanism of block chain 信息安全研究_004_, 4 (2018), 369–379.
[8] 梁斌. 从”比特币挖矿”看区块链技术的共识机制. 中国金融电脑, 9 (2016), 45–46.
[9] 甘俊, 李强, 陈子豪, and 张超. 区块链实用拜占庭容错共识算法的改进. 计算机应用, 7 (2019).
[10] 祝朝凡, 郭进伟, and 蔡鹏. 基于 paxos 的分布式一致性算法的实现与优化. 华东师范大学学报 _(_自然科学版_)_, 10 (2019), 168–177.
[11] 程书芝, 师文轩, and 刘俪婷. 区块链技术综述.
[12] 韩璇, and 刘亚敏. 区块链技术中的共识机制研究. 信息网络安全, 9 (2017).
[13] 黄嘉成, 许新华, and 王世纯. 委托权益证明共识机制的改进方案. 计算机应用, 7 (2019),2162–2167