区块链共识机制

由于各个节点的自身状态和所处网络环境不尽相同，而交易信息的传递又需要时间，并且消息传递本身不可靠，每个节点接收到的需要记录的交易内容和顺序也难以保持一致。因此，区块链系统的共识问题，或者说账本数据一致性问题，是关系着整个区块链系统的正确性和安全性的关键问题。

共识基本原理与问题

数据一致性问题

区块链系统的分布式账本中，如何确保分散存储于多个不同网络节点的账本数据在任意时刻都是一致与可信的，不会发生数据冲突与错误，这就涉及分布式系统的一致性问题。

在分布式系统中，各个节点数据的一致性与节点数据的可信性并不是一个问题，解决系统一致性问题并不一定能保证系统数据的正确可信，区块链共识机制的关键是需要同时解决好一致性与可信性两个问题

FLP定理

FLP定理1：在异步通信的分布式系统中，即使只有一个进程失败，也没有任何算法能保证非故障进程达到一致性。

FLP定理假设的分布式系统模型如下：

(1) 异步通信：异步通信与同步通信的最大区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序；

(2) 通信健壮：只要进程非失败，消息虽会被无限延迟，但最终会被送达，且消息仅会被送达一次（无重复）；

(3) Fail-Stop模型：进程失败如同宕机，不再处理任何消息，也不会产生错误消息；

(4) 失败进程数量：最多只有一个进程失败或单节点宕机。

FLP定理2：假设在一个分布式系统中，绝大多数进程最初都是正常运行的，且没有进程在运行过程中发生故障，则一定存在一个部分正确的共识协议使所有非故障进程总是能达成一致决议。

安全性（Safety）与活性（Liveness）两种分布式系统特性：

(1)“安全性”是指当分布式系统中即使有节点发生故障时，也不会导致系统产生错误的数据结果。

(2)“活性”是指分布式系统中即使有节点发生故障时，系统也可以一直持续运行下去，不会发生系统瘫痪。

CAP定理

CAP定理：一个分布式系统不可能同时满足一致性、可用性、分区容错等三个特性，最多具有一致性、可用性、分区容错这三个特性中的两个。

CAP定理的名称是其定义中给出的分布式系统的一致性（Consistency）、可用性（Availability）、分区容错（Partition Tolerance）三个特性的英文首字母缩写。

(1) 一致性

在CAP定理中，分布式系统的一致性是指各节点的数据保证一致，即每次从任意节点写入数据后，后续其它节点都能读取到最新的数据。

(2) 可用性

在CAP定理中，分布式系统的可用性是指每次向非故障的节点发送请求，总能保证收到响应数据。

(3) 分区容错

在CAP定理中，分布式系统的分区容错是指系统可以容忍不同节点之间消息传递存在延迟或丢失等错误，而不影响系统整体正常运行。

两军问题

原本是用来分析在一个不可靠的通信链路上试图通过通信以达成一致是存在问题的，后来常被用于阐述分布式系统的一致性和共识问题

拜占庭将军问题

拜占庭将军问题描述了如何在存在恶意行为（如消息被篡改）的情况下实现分布式系统的一致性，该问题既是分布式系统领域最复杂的容错模型之一，也是我们理解分布式共识算法和协议的重要基础。

  • 问题求解

    如果将拜占庭问题中的攻城军队的将军数量对应为分布式系统的节点数量，可以将符合拜占庭问题条件的分布式系统称为“拜占庭系统”，在拜占庭系统中任意两个节点之间的通信是保证可达的，综合上面对最简单的三将军情形分析，可以得出以下结论：

对于一个拜占庭系统，如果系统总节点数为Z，表示叛变将军的不可靠节点数为X，只有当Z≥3X＋1时，可由基于拜占庭容错（BFT）类算法的协议保证系统的一致性。

在实际的系统中，一般把由于系统故障导致节点不响应的情况归类为“非拜占庭错误（Crash Fault）”，把节点伪造或篡改信息进行恶意响应的情况归类为“拜占庭错误（Byzantine Fault）”。

非拜占庭容错类共识算法（CFT）

​ 对于分布式系统，非拜占庭容错类共识算法能在节点发生系统故障或非计划停机等非拜占庭错误时，确保整个分布式系统的可靠性；但是，当系统中存在恶意节点伪造或篡改数据等行为时，非拜占庭容错算法无法保证系统的可靠性。因此，非拜占庭容错类共识算法主要用于实现封闭的、系统节点都受控的企业级分布式系统，如某企业构建的内部分布式应用集群系统或分布式存储系统。非拜占庭容错类共识算法中最有代表性的包括Paxos算法与Raft算法。

Paxos算法

Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致。

前提1：为了保证不出现一些不合法的命令序列，Paxos算法运行的环境必须处在一个可靠的通信网络环境中。即使在异步通信过程中，发送的数据可能会丢失（Lost）、延迟（Delayed）或重复（Duplicated），但不会出现被篡改。

**前提2:**Paxos算法运行的环境不会出现拜占庭将军问题，即节点群在决定命令序列的过程中不存在恶意节点或受到病毒、黑客的影响的节点。

Paxos算法的原理

​ Paxos算法把一个分布式系统中节点划分为3种角色：Proposer（提出提案者）、Acceptor（接受提案者）和Learner（学习决议者）。一个节点可以同时拥有多个角色。

Proposer（提出提案者）：提出提案，提案信息包括提案编号n和提案内容v。常常是分布式系统的发送消息数据的节点担任该角色。

Acceptor（接受提案者）：收到并审批提案，若提案获得多数Acceptor的接受，则该提案被批准。常常是分布式系统接收消息数据的节点担任该角色，一般需要至少3个且节点个数为奇数，因为Paxos算法最终要产生一个大多数决策者都同意的提案。

Learner（学习决议者）：被告知提案结果，并与之统一，不参与审批过程，执行被批准的提案中包含的提案内容。

一个Paxos算法实例的执行包括准备提案（Prepare）和提交提案（Commit）两个阶段，Paxos算法流程如图所示。

1.png

(1) 准备提案阶段

Proposer节点收到Acceptor节点的响应，可能存在抢占失败或抢占成功两种情况：

如果Proposer节点收到超半数以上的Acceptor节点回复的提案编号要大于自己发送的提案编号；则抢占失败。

如果Proposer节点收到超半数以上Acceptor节点的回复的提案编号等于自己发送的提案编号，则抢占成功；这时Proposer节点就可以进入下一个“提交提案”阶段。

(2) 提交提案阶段

Proposer节点将抢占的提案编号 n 和提案内容v发送给Acceptor节点。Acceptor节点只批准比自己已经接受提案的编号N大或等于的提案（称为“审批成功”）；并承诺不再接受小于 n 的提案。

Acceptor节点收到提案后，如果提案的编号大于等于它已经接受的所有提案编号，则Acceptor节点将批准此提案内容并将此批准过的提案回复给Proposer节点。如果提交审批的提案编号小于它已经接受的提案编号，则审批失败，并回复所接受的提案编号。

如果Proposer节点收到多数派审批失败（此种情况也称为“提案失败”），则将提案编号递增一，重新进入“准备提案阶段”。

如果Proposer节点收到多数派提案内容相同，则此决议案已经形成。

Paxos算法的局限性

​ Paxos算法虽然可以容忍已经申请到访问权的Proposer节点故障，可以容忍少数Acceptor节点故障；但在出现竞争的情况下，其收敛速度很慢，甚至可能出现活锁的情况，例如当有等于或多于Acceptor节点数量的Proposer节点同时发送提案请求后，很难有一个Proposer节点收到半数以上的回复而不断地执行第一阶段的协议。

Raft算法

Raft算法名字来源于可靠（Reliable）、可复制（Replicated）、可冗余（Redundant）与可容错（Fault-Tolerant）。

​ Raft算法要解决核心问题仍然是在没有拜占庭错误下的分布式系统的共识问题，即在系统节点不会做恶，传递的消息也不会被篡改的前提下如何保证每个节点在执行相同的命令序列。

前提1：原来的Leader节点发生故障失效后，必须选出一个新的Leader节点，日志复制的顺序也是确定的，必须从Leader节点流向Follower节点。

前提2：日志复制只允许Leader节点从客户端接收日志，并复制到整个分布式系统的节点中。

前提3：与Paxos算法一样，Raft算法运行的环境不会出现拜占庭将军问题，即节点群在决定命令序列的过程中不存在恶意节点或受到病毒、黑客的影响的节点。

Raft算法的原理

​ Raft算法中，分布式系统的各节点通过心跳（Heartbeat）消息来保持通信，一个节点可以是以下三种角色中的一种：

Leader（领导者）：Leader节点也称为“主节点”，用于对所有用户的请求进行处理。Leader 节点将带领分布式系统中的所有节点对数据更改达成一致，这个过程被称为日志同步。

Follower（跟随者）：Follower节点也称为“从节点”，不会主动发送消息，只响应来自Leader节点与Candidate节点的请求。最开始时，所有的节点都是Follower节点，如果Follower节点收不到Leader节点的心跳消息，那么Follower节点会变为Candidate节点。

Candidate（候选人）：Candidate节点是准备竞选Leader的节点。Candidate节点会向其他节点发起投票（包括投给自己的一票），如果一个Candidate节点收到了半数以上的选票，那么它就当选为新的Leader节点。

Raft算法为了清晰易懂，将分布式系统一致性共识问题分解为选举主节点（Leader Election）、日志复制（Log Replication）、安全性（Safety）、成员变更（Membership Changes）等几个子问题，每个子问题都可以独立求解，因此理解 Raft 算法只需要相对独立地弄清几个子问题即可。

Raft算法的局限性

Raft算法有一个很强的前提就是Leader节点和Follower节点都必须按顺序投票。例如一个基于Raft算法的分布式数据库系统中，必须按照以下顺序处理事务：

(1)主库节点按事务顺序发送事务日志；

(2)备库节点按事务顺序持久化事务，并应答主库节点；

(3)主库节点按事务顺序提交事务。

如果不严格按照上述顺序，Raft算法的正确性无法得到保证。但是，对于高峰期每秒钟处理成千上万的事务的分布式数据库，可能会造成无法忽视的潜在性能和稳定性风险。此外，Raft算法的顺序投票策略也会对数据库的多表事务、故障恢复产生影响。

拜占庭容错类共识算法（BFT）

拜占庭容错类共识算法能允许分布式系统节点发生任何类型的错误但错误节点数量不超过一定比例时，确保整个分布式系统的可靠性。简单的说，只要分布式系统的故障（由于非拜占庭错误或拜占庭错误导致）节点数与系统总节点数相比，小于一定比例，拜占庭容错类共识算法就能保证分布式系统的可靠性。由于像比特币、以太坊等区块链系统中，存在大量彼此不信任的网络节点，不排除有恶意节点企图伪造或篡改系统数据，因此，拜占庭容错类共识算法是区块链共识机制主要采用的共识算法。拜占庭容错类共识算法中最有代表性的包括PBFT实用拜占庭容错算法、PoW工作量证明算法、PoS权益证明算法等。

PBFT实用拜占庭容错算法

PBFT（Practical Byzantine Fault Tolerance）算法中文译为实用拜占庭容错算法，简称PBFT算法。

解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得在实际系统中解决拜占庭错误（Byzantine Failure）变得可行。

PBFT算法的原理

PoW工作量证明算法

PoS权益证明算法

DPoS委托权益证明算法

DPoS算法的目的是为了解决PoW算法的性能与巨大算力资源消耗问题以及PoS算法后期可能出现的少数节点持有大量权益带来的中心化风险问题****。在DPoS算法中，保留了PoS算法的权益机制，借鉴了类似于股份制企业中董事会投票机制的方式，节点用持有的股份投票选出少量称为见证人的节点，这些见证人节点会代理其余节点完成区块的生成和验证。通过减少对确认数量的要求，DPoS算法大大提高了交易的性能。

DPoS算法的原理

DPoS共识算法引入了一种类似民主代表大会的机制，系统中所有拥有权益的普通节点投票选举出代表自身权益的见证人节点来实际运营网络，见证人节点提供专业运行的网络服务器来保证区块链网络的安全和性能。

前提1：见证人节点必须代表普通节点行使区块链出块权利，如果见证人节点不称职，随时都可能被投票出局。

前提2：见证人节点的数量是固定的，一般是奇数，取决于区块链系统的设计，如在EOS系统中有21个，Bitshares系统中有101个。

DPoS算法中，区块链系统的节点被划分为普通节点、见证人节点两大类角色。

(1) 普通节点

​ 普通节点又称为“权益相关者”节点，是系统中占比最大的节点类型，具有投票权和被选举权，普通节点持有的权益（如货币量、币龄）越多，投票的权重就越高。

(2) 见证人节点

见证人节点是被普通节点选举出来，代表广大普通节点为区块链添加新区块，执行记帐权利的节点。见证人节点一般会保持中立，维护区块链系统分布式帐本的安全，因为见证人节点始终处于普通节点（利益相关者）的选举控制之下，当见证人节点因不良行为（未记帐或签署无效区块等）时，会造成普通节点的权益损失，因此，普通节点可随时将其选票重新分配给其他见证人节点。

见证人节点需要具体负责：

  1. 确保节点的正常运行；

  2. 收集区块链网络里的交易信息，验证交易，把交易打包到区块；

  3. 向所有见证人节点广播新区块，其它见证人节点验证后把区块添加到本地账本数据库中；

  4. 组织领导并促进区块链项目的发展，对区块链网络发展做出积极的贡献（如贡献代码、筹集资金、建立社群等）来不断提高声誉。

DPoS算法参考流程如下：

(1) 新节点加入系统作为普通节点运行；

(2) 系统各节点投票选出固定数量的见证人节点；

(3) 系统对见证人节点进行排序；

(4) 见证人节点按照排序，根据系统规定的时间间隔（如EOS系统为0.5秒）轮流生成新区块，如果见证人节点没有成功生成区块，则跳过该见证人节点，由下一见证人节点继续生成区块；

(5) 根据见证人节点的排序，新生成的区块交由后续的见证人节点进行区块验证，一个新区块得到超过2/3个见证人节点的验证确认后，才能被正式加入到区块链中。

DPoS算法的局限性

(1) DPoS算法中选举少数见证人节点代表其它节点生产区块，系统长期运行下去，可能导致少数见证人节点获得的权益激励积累远远多于其它节点，当见证人节点拥有的权益过多时，就拥有了控制见证节点选举的能力，进而破坏选举的民主性。

(2) DPoS算法中被选举出来的见证人节点可能是恶意节点，当恶意节点不能成功生成区块时，DPoS算法只是选择跳过该节点由下一节点继续生产区块，并且只寄希望于在后续通过投票的方式将其从见证人节点集合中淘汰。缺乏对恶意节点的惩罚措施，该节点仍然可以参与后续的共识过程和见证人节点竞选，继续影响着区块链系统的安全性。