本文由作者苏州授权网易易盾发布
1. 共识算法是什么
共识表示对于某个事件的共同认识,因此共识算法所做的就是保证在一个分布式系统下各个节点可以对某个事件具有一致的认识。由于分布式系统存在网络延迟、节点宕机等不可预知的错误,以及某些拜占庭节点存在一些恶意行为,因此设计一个良好的共识算法来抵御上述问题是一个极具挑战性的工作。
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
基于拜占庭将军问题,一致性的确保主要分为这三个阶段:预准备(pre-prepare)、准备(prepare)和确认(commit)。
其中 C 为发送请求端,0123 为服务端,3 为宕机的服务端,具体步骤如下:
1）Request:请求端 C 发送请求到任意一节点,这里是 0
2）Pre-Prepare:服务端 0 收到 C 的请求后进行广播,扩散至 123
3）Prepare:123,收到后记录并再次广播,1->023,2->013,3 因为宕机无法广播
4）Commit:0123 节点在 Prepare 阶段,若收到超过一定数量的相同请求,则进入
5）Commit 阶段,广播 Commit 请求
6）Reply:0123 节点在 Commit 阶段,若收到超过一定数量的相同请求,则对 C 进行
7）反馈
三阶段协议可以很好的处理如下的场景:
场景 1,主节点修改客户的请求发给了所有的备份节点?客户端发起请求时,会对请求做签名,当得到响应时会去验证过程中请求是否被篡改过.
场景 2,主节点发给不同备份节点不同的请求?这个时候在准备阶段需要 2f 个节点的相同回应,如果没有达到这个要求,那么就会进行 view change
场景 3,主节点发给不同备份节点时,调整请求的顺序?prepare 阶段结束时,每个节点会校验主节点和其他备节点的消息是否一致.
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)。这使得在配置改变的时候,集群能够继续操作。
5. 如何选择适合我们的共识算法
从面向的场景区分,paxos 和 raft 是无法处理拜占庭节点的,因此此类共识算法比较适合应用于私有链这种节点间信任程度高的场景下。而 pbft 中的节点通信复杂度为 n^2,因此若面向公有链这种节点数量较大的场景下,pbft 的性能会非常差,因此 pbft 比较适合规模较小,对性能要求较高,且存在拜占庭节点的联盟链环境。而 PoS,DPoS,PoW能处理拜占庭节点,且扩展性较高,因此较适合于公有链场景。但个人认为 PoS 和 DPoS并不是严格的去中心化,其节点存在层次结构,因此可以被借鉴到联盟链的设计中。
相关阅读：