基于CAP理论的区块链共识机制的分析*

姬晓涛 刘建华

（西安邮电大学 西安 710121）

1 引言

区块链是一种全新的分布式计算范式，其不需要中心节点来统一处理，管理网络，网络中各节点同步运行并通过共识机制保证一致［1］。Leslie Lamport［2］在1998提出了Paxos共识算法，2014年斯坦福教授Diego Ongaro［3］发布了Raft算法（Paxos算法的变种）。1999年，Castro和Liskov提出了实用拜占庭容错协议（PBFT），使拜占庭协议的复杂度有所降低［4］，同年“工作量证明”这一概念被Markus Jakobsson［5］首次提出，2008年工作量首次被应用到中本聪［6］提出的比特币中。2011年，权益证明POS算法由一位名为Quantum Me-chanic的数字货币爱好者首次提出［7］，2012年Sunny King［8］在点点币中首次使用了权益证明。为了解决工作量证明机制和权益证明存在的问题，Fabian Schuh提出了股份授权证明机制，比特股［9］是该机制的首次应用。2017年韩璇刘亚敏对现有的共识机制进行了总结，并从安全性等方面进行了评价［10］。

共识机制的研究主要集中在创新研究出更好的共识算法以及对其安全性、性能的分析等方面。共识机制作为区块链这一分布式系统的核心技术之一，目前并没有对其在CAP理论方面的权衡分析。因此本文在详细了解了几大主流共识算法的共识流程后，从CAP理论的角度分析了各算法对三属性的考量与权衡，将共识算法进行了分类，这将为区块链未来的应用提供了理论基础。

2 基本技术

2.1 共识机制的定义

百度百科定义：“‘共识机制’是通过特殊节点的投票，在很短的时间内完成对交易的验证和确认；对一笔交易，如果利益不相干的若干个节点能够达成共识，我们就可以认为全网对此也能够达成共识”［11］。本文认为共识机制就是网络中所有节点通过某种特定规则对某个提案达成一致的过程。目前主流的区块链共识机制包括工作量证明机制（POW）、权益证明机制（POS）、股份授权证明机制（DPOS）、实用拜占庭容错协议（PBFT）、Paxos共识算法以及Raft共识算法。

2.2 CAP理论

CAP理论最早是Eric Brewer［12］在2000年提出的，Gilbert等［13］在2002年对其进行了证明。CAP原理指的是分布式系统不能同时满足一致性、可用性、分区容错性三属性，必须选择一个进行一定程度的弱化。三属性的含义如下：

2）可用性（Availability）：对于系统的每一个请求在一定时间内无论成功还是失败都必须有回应。

3）分区容错性（Partition Tolerance）：网络中部分节点发生故障，对整个系统的使用不会产生影响。

3 几种共识机制的CAP理论分析

3.1 分析思路

本文对共识机制的CAP理论分析按照下述步骤进行：

1）了解算法的共识过程，画出其共识过程的流程图；

2）根据流程图，判断共识算法对交易的确认是否需要等到多个区块的确认才算达成一致。如果需要多次确认，就是最终一致性，相反，则是强一致性；

3）根据CAP理论三选二的原则给出结论。

3.2 具体的分析

3.2.1 工作量证明机制（POW）

鲍照的《东武吟》作于元嘉二十七年北伐失利后，南朝国力已衰时。诗歌未脱去民歌说唱的痕迹，如开篇的称呼：主人指听者，“贱子”与“仆”皆说唱者谦称。

POW是一个参与者对其他参与者关于他做过一定工作的证明。图1是比特币的POW共识流程，其中只要每新增2016个区块，难度值就会进行调整，调整的公式为新难度值=旧难度值*（过去2016个区块耗费的时长/20160min）［14］。

POW在对区块达成共识的过程中，可能存在分叉问题，因此为了保证各节点数据的一致性，POW设计一笔交易被全网确认需要6个区块被确认，即一个小时。故POW是保证了可用性和分区容错性，对一致性进行了弱化。

3.2.2 权益证明机制（POS）

POS是以系统相关的权益为依据来竞争对某个区块的记账权。这里通过点点币的共识来说明POS共识算法的流程，如图2。点点币选取的权益是币龄，节点获得记账权的机会与币龄大小成正比，其中币龄=币数*持有币的天数［15］。

图1 比特币POW共识流程图

图2 POS共识算法流程

POS目标值的调整是由两个区块生成的时间间隔决定的，出块速率控制在10min一个，当一个区块被加入后，经过多个区块的确认，默认其被全网写入。以CAP理论为指导，POS采取的是弱化一致性，换取高可用性和分区容错性。

3.2.3 股份授权证明机制（DPOS）

股份授权证明机制是由所有节点投票选出见证人，见证人有生成区块的权利。这里以比特股采用的DPOS机制为例，详细说明其共识的过程，如图3。其中，节点投票的权重与持有的比特股数成正比。

图3 DPOS共识过程

DPOS中，每个见证者有2s的时间生成区块，当所有见证者一次循环结束后，该区块得到确认。由此可见，股份授权证明机制是达到最终一致的状态。因此以CAP理论为指导，DPOS采取的是弱化一致性，换取高可用性和分区容错性。

3.2.4 实用拜占庭容错协议（PBFT）

PBFT中R代表系统节点的集合，假设故障节点数为f个，则整个系统的节点数为|R|=3f+1。因此为了保证系统的一致性，至少需要2f+1个节点进行确认才能达成共识。具体的共识流程如图4。其中V代表视图的编号，N代表当前请求的编号，n指的是i节点的stable checkpoint的编号，M指的是消息的具体内容，d或D（m）指的是消息内容提取的摘要，i代表当前节点编号，C代表2f+1个节点的有效checkpoint信息的集合，P代表i节点中上一个view中编号大于n并且到达prepared状态的请求消息的集合，O代表pre-prepare消息的集合。

图4 PBFT共识过程

从PBFT的共识流程发现，PBFT不需要经过多个区块的确认，只需要至少2f+1个节点达成共识即可，一旦共识不可修改，可见其注重一致性，那么只能对可用性作一定的妥协。一旦故障节点大于m，那么系统就不能继续执行客户端的请求。因此PBFT采取的是弱化可用性，换取强一致性和分区容错性。

3.2.5 Paxos共识算法

Paxos算法包括客户端（Client）、提议者（Proposer）、接受者（Acceptor）、学习者（Learner）、领导者（Leader）五个角色，其中每个节点可以同时是多种角色。具体的共识流程如图5。其中流程中的f代表最多可能出现的故障接受者节点，那么至少需要2f+1个接受者节点。

图5 Paxos算法共识过程

从Paxos共识算法流程来说，其只需要f+1个节点达成共识即可，一旦共识，各个节点的账本将保持一致，不需等待。因此Paxos是保证了强一致性和分区容错性，而对可用性进行了弱化。

3.2.6 Raft共识算法

Raft算法将节点的状态分为领导人（leader）、候选者（candidate）、跟随者（follower）三种状态，每个节点只能同时处于一种状态。其中领导人只有一个。具体的共识流程如图6。

Raft共识算法将所有的权利交给领导人，只要领导人加入新交易记录，那么其他的跟随者也必须将交易写入自己的账本。各节点的数据始终保持一致。故Raft是在确保强一致性和分区容错性的情况下，对可用性进行了一定的弱化。

图6 Raft共识流程

4 共识机制的比较

根据上述的分析，我们将共识机制的分析结果总结为表1。

表1 各共识机制的分析对比

5 结语

本文从CAP理论的角度，对区块链的部分共识算法进行了分析与总结。首先给出了共识机制的定义，并说明了分析思路；然后以流程图的形式详细说明了部分共识机制的流程，并从CAP理论的角度按照分析思路给共识机制进行了分析；最后进行了总结。目前区块链的应用场景越来越多，本文的分析为区块链的应用提供了参考价值。我们可以根据应用场景的需求，选取满足需求的共识算法。