此文已由作者苏州授权网易云社区发布。

欢迎访问网易云社区，了解更多网易技术产品运营经验

1. 共识算法是什么

共识（Consensus），很多时候会见到与一致性（Consistency）术语放在一起讨论。严谨地讲，两者的含义并不完全相同。一致性的含义比共识宽泛，在不同场景（基于事务的数据库、分布式系统等）下意义不同。具体到分布式系统场景下，一致性指的是多个副本对外呈现的状态。如前面提到的顺序一致性、线性一致性，描述了多节点对数据状态的共同维护能力。而共识，则特指在分布式系统中多个节点之间对某个事情（例如多个事务请求，先执行谁？）达成一致看法的过程。因此，达成某种共识并不意味着就保障了一致性。实践中，要保障系统满足不同程度的一致性，往往需要通过共识算法来达成。

共识算法解决的是分布式系统对某个提案（Proposal），大部分节点达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是主节点……等等。可以认为任何可以达成一致的信息都是一个提案。对于分布式系统来讲，各个节点通常都是相同的确定性状态机模型（又称为状态机复制问题，State-Machine Replication），从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。因此，系统中多个节点最关键地是对多个事件的顺序进行共识，即排序。

2. 区块链中的共识算法?

区块链是一个典型的分布式系统,它具有去中心化的特点,相比阿里云等一般意义上的分布式系统,一些公有链例如 BTC、ETH 等还会面临着拜占庭节点问题。为了增加可信性,在区块链系统中所有节点共同维护着同一份账本。在以太坊中,由于所有节点都维护了同一个账本,因此这里的共识算法所要达成共识的点就是所有节点维护的账本。如果没有共识算法,那么所有的节点所维护的账本就会不一致甚至出现各自维护自己的一份账本,由于 BTC、ETH 等由于没有政府的信用背书,因此他是一种信心币,即信任他的人越多那么他的价值也就越大,因此,若没有一个共识算法来维护这同一个账本,那么这个账本就没有信服力,那么实际上这些币的价值也就失去了。所以,共识算法是区块链的价值基础,而加密算法则是价值的保护,P2P 技术是价值传播。

3. 设计共识算法需要考虑的点

在以太坊或者比特币这种公有链的场景下,面临着如下的几个问题。1. 相比内部集群,面向整个互联网的公有链的网络环境较差,主要的表现为网络时延较大,丢包率高。2. 相比集群的服务器,公链节点非常不稳定,主要表现为用户可以随意的退出加入、宕机等。3. 相比集群中,例如 spark、Hadoop 等往往有个 master 节点会对集群的运行进行管理,区块链所倡导的是去中心化,表现为所有节点是平等的,即没有所谓的 master 节点对整个分布式系统进行管理。4.公有链下由于所有节点是平等的,因此是存在拜占庭节点,主要表现为节点会进行某些恶意行为。在分布式系统中,有一个 CAP 理论:理论首先把分布式系统中的三个特性进行了如下归纳:

• 一致性(C):在分布式系统中的所有数据备份,在同一时刻是否同样的值。(等同于所有节点访问同一份最新的数据副本)

• 可用性(A):在集群中一部分节点故障后,集群整体是否还能响应客户端的读写请求。(对数据更新具备高可用性)

• 分区容错性(P):以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在 C 和 A 之间做出选择。

一般来说一个分布式系统是不能同时满足三个条件,对于公有链来说,为了保证用户的体验和可用性等,往往是满足 AP,而弱化了 C。AP 对应着上述的 1,2 两个条件。那么如何保证在存在拜占庭节点情况下,满足弱一致性呢?

我们知道,一个分布式系统中,为了保证所有节点的账本一样,前提条件是必须有一个唯一的账本,如果这个条件不能满足,那么就会产生政令二出,那么就不用提共识了。其次,如何保证该账本是可信任的,如果这个条件不能满足,那么账本的价值就失去了。如果满足了上述两个条件,那么就能保证政令一致并且是可信的。以太坊和比特币都采用了 PoW 公式算法,这是一个比较简单却有效的做法。首先为了保证政令不二出,即只有一个节点能记账,我们需要找到一种选择记账节点的规则,在 PoW 中采用算力作为规则,即哪个节点的算力强,那么就选择该节点作为记账节点,这个方式较为简单粗暴,但是也很有效果,原因在于算力是无法虚拟化的,是较为公平的方式。接着,如何保证该账本是可信的?首先,挖矿时所需的 hash 是与当前挖的 block的 hash 相关的,并且 block 中通过 Merkle Tree 以及 parent block hash 来确保了一旦 block产生后,就无法被修改。所有的节点接收到该记账节点发布的 block 都可以快速的进行验证,因此可以保证记账节点发布的 block 的可信性。当然,由于每个节点可以作恶,因此可以选择不信任一个合法的 block,但是由于账本是所有人共同维护,因此除非全网51%以上的节点作恶,那么该合法的 block 才有可能被拒绝加入到账本中,但是作恶成本会非常大,所以从博弈的角度来说,很少会做这种零合博弈。

4. 主流的共识算法

目前除了 PoW 以为还存在其他许多共识算法,主流的共识算法还有 PoS,DPoS,

PBFT,Paxos,Raft 等等,这些共识算法在不同的场景下有其合理之处。

1) POW

POW 算法即工作量证明算法,被应用于比特币以太币等公有链场景下,是一种简单粗暴的共识算法,但是该算法是一种弱一致性算法,从表现上来看即存在分叉的情况。同时,POW 会浪费极大的算力,因此整个系统的效率较为低下。POW 的过程可以理解为寻找一个 nonce 值,使之满足hash(block,nonce) <=x^256/difficulty。当某个矿工得到了满足条件的 nonce 值后,那么该矿工就获得了出块权。那么 POW选举 leader 的条件便是有强大的算力和运气。

2) POS

POS 算法即为股权证明算法,由于 POW 会浪费极大的算力并且系统的效率低下,因此为了改善 POW 的不足,提出了 POS 算法。POS 算法与 POW 较为类似,都是需要挖矿,但是相比 POW 所要的算力,POS 只需提供较少的算力。他的原理可以表示如下:Hash(hash(Bp),A,t)<=balance(A)m

这里的 Bp 表示上一个 block,balance(A)表示币龄,m 表示一个固定数量,可以理解为是 difficulty 值。因此,这里相当于通过查找一个满足条件的 t 来获得出矿权,由于这里加上了 balance(A)这个放大系数,因此相比 POW 来说 t 的查找范围要小于 POW的 nonce,因此可以极大的降低算力。

这里的币龄表示账户 A 的余额×持币时间。这里的持币时间一般可以理解为从上一次挖矿到目前所持有的时间。比如账户 A 有 100 余额,并且该 100 余额自从上一次用于挖矿后的时间为 100s,那么他的币龄便是 100*100。因此,POS 选举 leader 的条件便是余额和他的持有时间。

3) DPOS

由于 POS 会造成一定的中心化,同时 POS 和 POW 中任何一个 block 的加入都需要被整个网络中的节点确认因此效率还是较为低下,所以 DPOS 算法被提出来用于改善这种情况。DPOS 是委托股权证明,他的策略是减少确认节点的数量,POW 类似于从全国通过做高考题目选举出分数最高的考生作为 leader,POS 则类似与选举最有钱的人作为leader。DPOS 则类似人民代表大会制度,底层百姓通过投票选举出人大代表,由人大代表轮流当 leader。这种间接民主的效率是高于全民主的。

具体的,DPOS 的做法是每个用户在注册的时候可以选择将手中的票投给某个代表,这里的票可以理解为 token,并且是一个 token 一张选票,投票的请求也是一个交易,因此会被写入 block 中,从而保证其公正性。在 bitshares 中,会有一个委员会组织,该组织会规定代表的数量以及出块时间,比如 101 个代表,出块时间为 10s。因此,在每一轮周期开始时,会统计投票数前 101 个用户作为代表,并且会通过随机算法规定好他们的出块顺序:

function shuffle(height) {
var truncDelegateList = [];
for (var i = 0; i < 101; i++) {
truncDelegateList.push(i);
}
var seedSource = String(Math.floor(height / 101) + (height % 101 > 0 ? 1 : 0));
console.log(seedSource);
var currentSeed = crypto.createHash('sha256').update(seedSource, 'utf8').digest();
for (var i = 0, delCount = truncDelegateList.length; i < delCount; i++) {
for (var x = 0; x < 4 && i < delCount; i++, x++) {
var newIndex = currentSeed[x] % delCount;
var b = truncDelegateList[newIndex];
truncDelegateList[newIndex] = truncDelegateList[i];
4truncDelegateList[i] = b;
}
currentSeed = crypto.createHash('sha256').update(currentSeed).digest();
}
return truncDelegateList;
}

为了激励代表能正确的出块,当一个在规定的时间出块后,会得到奖励。在 bitshares中,该奖励会给代表和委员会,并不会反馈给支持该代表的普通用户。委员会在获得奖励后,会将该奖励用于社区的建设等。

因为代表数量有限,因此会出现竞争上岗的状况。代表会通过主动降低自己的收入,来吸引选票,最终的效果就是他们之间的竞争既可以确保网络安全,又能够降低维护成本。同时,代表也会降低交易费用等来吸引普通用户,因此,虽然普通用户在投票的时候并不会直接获得激励,但是由于代表降低了交易费用,因此可以获得间接的好处。类似总统选举时承诺降低税收,增加就业岗位等,虽然不会直接有利于每个选民,但是会间接的利好。

因此, DPOS 中通过票数的形式来选举出人大代表,并以轮流坐庄的形式选举 leader。

4) PBFT

        pbft共识算法的实现主要分为pre-prepare、prepare、commit和reply四个阶段，每个阶段的处理流程如下图所示：

REQUEST：

客户端c向主节点p发送<REQUEST, o, t, c>请求。o: 请求的具体操作，t: 请求时客户端追加的时间戳，c：客户端标识。REQUEST: 包含消息内容m，以及消息摘要d(m)。客户端对请求进行签名。

 PRE-PREPARE：

主节点收到客户端的请求，需要进行以下交验：

a. 客户端请求消息签名是否正确。

非法请求丢弃。正确请求，分配一个编号n，编号n主要用于对客户端的请求进行排序。然后广播一条<<PRE-PREPARE, v, n, d>,  m>消息给其他副本节点。v：视图编号，d客户端消息摘要，m消息内容。<PRE-PREPARE, v, n, d>进行主节点签名。n是要在某一个范围区间内的[h, H]。

PREPARE：

副本节点i收到主节点的PRE-PREPARE消息，需要进行以下交验：

a. 主节点PRE-PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了一条在同一v下并且编号也是n，但是签名不同的PRE-PREPARE信息。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。正确请求，副本节点i向其他节点包括主节点发送一条<PREPARE, v, n, d, i>消息, v, n, d, m与上述PRE-PREPARE消息内容相同，i是当前副本节点编号。<PREPARE, v, n, d, i>进行副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中，用于View Change过程中恢复未完成的请求操作。

COMMIT：

主节点和副本节点收到PREPARE消息，需要进行以下交验：

a. 副本节点PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. n是否在区间[h, H]内。

d. d是否和当前已收到PRE-PPREPARE中的d相同

非法请求丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息，则向其他节点包括主节点发送一条<COMMIT, v, n, d, i>消息，v, n, d,  i与上述PREPARE消息内容相同。<COMMIT, v, n, d, i>进行副本节点i的签名。记录COMMIT消息到日志中，用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的PREPARE消息到log中。

REPLY：

      主节点和副本节点收到COMMIT消息，需要进行以下交验：

a. 副本节点COMMIT消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

       非法请求丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息，说明当前网络中的大部分节点已经达成共识，运行客户端的请求操作o，并返回<REPLY, v, t, c, i, r>给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的COMMIT消息到log中。

5) Paxos

paxos 是一个两阶段的一致性算法,该算法被广泛的应用于各种分布式系统中,例如chubby,Zookeeper 等。Paxos 要求存储必须是可靠的,即没有数据丢失和错误,也就是不存在拜占庭节点。但是 Paxos 可以容忍消息丢失和乱序的情况。

在 Paxos 中有如下几个重要概念

• Proposer:发起 Paxos 的进程。

• Acceptor:存储节点,接受、处理和存储消息。

• Quorum:Acceptor 的多数派,n/2+1 个 Acceptor。

Round:一轮包含两个阶段,phase-1&phase-2。每一轮的编号 rnd 都会单调递增,后写者胜出,保证全局唯一,用于区分不同的 Proposer。为了保证写前读的顺序性,每个Acceptor 会记录当前最大的 rnd,通过记录该 rnd 来识别哪个 Proposer 具有写的权限。Value(V):Acceptor 接受的值。

Value round number(vrnd):Acceptor 接受 v 的时候的 rnd。被确定的值:当某个值被 Quorum 个 Acceptor 接受后,该值便被确定了。

在 Phase-1 中

对于阶段 1 来说(prepare),propose 只发送一个 rnd 给 acceptor,当 acceptor 接收到 rnd 后,会判断接收到的 rnd 和当前的 last_rnd,这个 last_rnd 就表示哪个 propose 可以写。如果 rnd 大于 last_rnd,那么 acceptor 就会接收这个请求,并将 rnd 保存到 last_rnd中,然后返回 last_rnd 以及已经接收的 v。

接着, propose 接收到 acceptor 返回的应答后,如果 last_rnd 大于发出的 rnd,就退出。这里之所以不能改变 vrnd 对应的 v 值,是因为这里的 v 已经是确定了的,因此 propose提出的 value 是应该不能变。也就是说 propose(t,v),若 t'>t,那么 v'>v。即 propose(t',v')中的 v'=v。当然,如果 v 是空的,那么说明没有冲突,所以可以直接写入 v。

在 phase-2 中

在阶段 2 中, propose 发送 v 和 rnd 给 acceptor,当 Acceptor 接收后,如果 rnd 与 Acceptor

的 last_rnd 不一致,那么就会拒绝该请求,否则就会将 v 写入本地,并将该 v 标记为已接受的值。这里通过 last_rnd==rnd 来保证没有其他的 Proposer 在此过程中将值写入。最后,通过上述的两阶段,可以保证在一个没有拜占庭节点的分布式环境下系统的一致性。

6) Raft

Raft 是一种用来管理日志复制的一致性算法。它和 Paxos 的性能和功能是一样的,但是它和 Paxos 的结构不一样;这使得 Raft 更容易理解并且更易于建立实际的系统。为了提高理解性,Raft 将一致性算法分为了几个部分,例如领导选取(leader selection),7日志复制(log replication)和安全性(safety),同时它使用了更强的一致性来减少了必须需要考虑的状态。从用户学习的结果来看,Raft 比 Paxos 更容易学会。Raft 还包括了一种新的机制来使得动态改变集群成员,它使用重叠大多数(overlapping majorities)来保证安全。

Raft 相比 Paxos 具有如下几个特性:

强领导者(Strong Leader):Raft 使用一种比其他算法更强的领导形式。例如,日志条目只从领导者发送向其他服务器。这样就简化了对日志复制的管理,使得 Raft 更易于理解。

领导选取(Leader Selection):Raft 使用随机定时器来选取领导者。这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化,它使得在解决冲突时更简单和快速。

成员变化(Membership Change):Raft 为了调整集群中成员关系使用了新的联合一致性(joint consensus)的方法,这种方法中大多数不同配置的机器在转换关系的时候会交迭(overlap)。这使得在配置改变的时候,集群能够继续操作。

4. 如何选择适合我们的共识算法

从面向的场景区分,paxos 和 raft 是无法处理拜占庭节点的,因此此类共识算法比较适合应用于私有链这种节点间信任程度高的场景下。而 pbft 中的节点通信复杂度为 n^2,因此若面向公有链这种节点数量较大的场景下,pbft 的性能会非常差,因此 pbft 比较适合规模较小,对性能要求较高,且存在拜占庭节点的联盟链环境。而 PoS,DPoS,PoW能处理拜占庭节点,且扩展性较高,因此较适合于公有链场景。但个人认为 PoS 和 DPoS并不是严格的去中心化,其节点存在层次结构,因此可以被借鉴到联盟链的设计中。此文已由作者黎星授权网易云社区发布。

免费领取验证码、内容安全、短信发送、直播点播体验包及云服务器等套餐

更多网易技术、产品、运营经验分享请点击。