区块链共识机制

2.1 名词解释

哈希函数 Hash 哈希函数是一个单向加密函数，哈希算法能够获取任意数量的数据，并返回一个固定长度的字符串 [6]，该字符串对于特定的输入是完全唯一的。

Nonce一个只能使用一次的随机数。

矿工 Miners加密货币网络中独立的交易处理器，其目标是验证交易。通常也被称作Full Node或Node。

2.2 角色

工作者需要完成的工作必须有一定的量，这个量由工作验证者给出；

工作者无法找到很快完成工作的办法；

工作者无法自己” 创造工作”，必须由验证者发布工作。

验证者可以迅速的检验工作量是否达标。

2.3 优点

1. 算法简单，容易实现。

2. 节点间无需交换额外的信息即可达成共识（节点间自由进出）。

3. 破坏系统需要投入极大的成本。

4. 需要全网所有节点参与，完全去中心化。

2.4 缺点

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 应用实例

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 缺点

7.3 优点

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)，不容纳作恶节点。