基于CAP理論的區(qū)塊鏈共識機制的分析*

姬曉濤 劉建華

（西安郵電大學 西安 710121）

1 引言

區(qū)塊鏈是一種全新的分布式計算范式，其不需要中心節(jié)點來統(tǒng)一處理，管理網(wǎng)絡，網(wǎng)絡中各節(jié)點同步運行并通過共識機制保證一致［1］。Leslie Lamport［2］在1998提出了Paxos共識算法，2014年斯坦福教授Diego Ongaro［3］發(fā)布了Raft算法（Paxos算法的變種）。1999年，Castro和Liskov提出了實用拜占庭容錯協(xié)議（PBFT），使拜占庭協(xié)議的復雜度有所降低［4］，同年“工作量證明”這一概念被Markus Jakobsson［5］首次提出，2008年工作量首次被應用到中本聰［6］提出的比特幣中。2011年，權(quán)益證明POS算法由一位名為Quantum Me-chanic的數(shù)字貨幣愛好者首次提出［7］，2012年Sunny King［8］在點點幣中首次使用了權(quán)益證明。為了解決工作量證明機制和權(quán)益證明存在的問題，F(xiàn)abian Schuh提出了股份授權(quán)證明機制，比特股［9］是該機制的首次應用。2017年韓璇劉亞敏對現(xiàn)有的共識機制進行了總結(jié)，并從安全性等方面進行了評價［10］。

共識機制的研究主要集中在創(chuàng)新研究出更好的共識算法以及對其安全性、性能的分析等方面。共識機制作為區(qū)塊鏈這一分布式系統(tǒng)的核心技術(shù)之一，目前并沒有對其在CAP理論方面的權(quán)衡分析。因此本文在詳細了解了幾大主流共識算法的共識流程后，從CAP理論的角度分析了各算法對三屬性的考量與權(quán)衡，將共識算法進行了分類，這將為區(qū)塊鏈未來的應用提供了理論基礎。

2 基本技術(shù)

2.1 共識機制的定義

百度百科定義：“‘共識機制’是通過特殊節(jié)點的投票，在很短的時間內(nèi)完成對交易的驗證和確認；對一筆交易，如果利益不相干的若干個節(jié)點能夠達成共識，我們就可以認為全網(wǎng)對此也能夠達成共識”［11］。本文認為共識機制就是網(wǎng)絡中所有節(jié)點通過某種特定規(guī)則對某個提案達成一致的過程。目前主流的區(qū)塊鏈共識機制包括工作量證明機制（POW）、權(quán)益證明機制（POS）、股份授權(quán)證明機制（DPOS）、實用拜占庭容錯協(xié)議（PBFT）、Paxos共識算法以及Raft共識算法。

2.2 CAP理論

CAP理論最早是Eric Brewer［12］在2000年提出的，Gilbert等［13］在2002年對其進行了證明。CAP原理指的是分布式系統(tǒng)不能同時滿足一致性、可用性、分區(qū)容錯性三屬性，必須選擇一個進行一定程度的弱化。三屬性的含義如下：

2）可用性（Availability）：對于系統(tǒng)的每一個請求在一定時間內(nèi)無論成功還是失敗都必須有回應。

3）分區(qū)容錯性（Partition Tolerance）：網(wǎng)絡中部分節(jié)點發(fā)生故障，對整個系統(tǒng)的使用不會產(chǎn)生影響。

3 幾種共識機制的CAP理論分析

3.1 分析思路

本文對共識機制的CAP理論分析按照下述步驟進行：

1）了解算法的共識過程，畫出其共識過程的流程圖；

2）根據(jù)流程圖，判斷共識算法對交易的確認是否需要等到多個區(qū)塊的確認才算達成一致。如果需要多次確認，就是最終一致性，相反，則是強一致性；

3）根據(jù)CAP理論三選二的原則給出結(jié)論。

3.2 具體的分析

3.2.1 工作量證明機制（POW）

鮑照的《東武吟》作于元嘉二十七年北伐失利后，南朝國力已衰時。詩歌未脫去民歌說唱的痕跡，如開篇的稱呼：主人指聽者，“賤子”與“仆”皆說唱者謙稱。

POW是一個參與者對其他參與者關(guān)于他做過一定工作的證明。圖1是比特幣的POW共識流程，其中只要每新增2016個區(qū)塊，難度值就會進行調(diào)整，調(diào)整的公式為新難度值=舊難度值*（過去2016個區(qū)塊耗費的時長/20160min）［14］。

POW在對區(qū)塊達成共識的過程中，可能存在分叉問題，因此為了保證各節(jié)點數(shù)據(jù)的一致性，POW設計一筆交易被全網(wǎng)確認需要6個區(qū)塊被確認，即一個小時。故POW是保證了可用性和分區(qū)容錯性，對一致性進行了弱化。

3.2.2 權(quán)益證明機制（POS）

POS是以系統(tǒng)相關(guān)的權(quán)益為依據(jù)來競爭對某個區(qū)塊的記賬權(quán)。這里通過點點幣的共識來說明POS共識算法的流程，如圖2。點點幣選取的權(quán)益是幣齡，節(jié)點獲得記賬權(quán)的機會與幣齡大小成正比，其中幣齡=幣數(shù)*持有幣的天數(shù)［15］。

圖1 比特幣POW共識流程圖

圖2 POS共識算法流程

POS目標值的調(diào)整是由兩個區(qū)塊生成的時間間隔決定的，出塊速率控制在10min一個，當一個區(qū)塊被加入后，經(jīng)過多個區(qū)塊的確認，默認其被全網(wǎng)寫入。以CAP理論為指導，POS采取的是弱化一致性，換取高可用性和分區(qū)容錯性。

3.2.3 股份授權(quán)證明機制（DPOS）

股份授權(quán)證明機制是由所有節(jié)點投票選出見證人，見證人有生成區(qū)塊的權(quán)利。這里以比特股采用的DPOS機制為例，詳細說明其共識的過程，如圖3。其中，節(jié)點投票的權(quán)重與持有的比特股數(shù)成正比。

圖3 DPOS共識過程

DPOS中，每個見證者有2s的時間生成區(qū)塊，當所有見證者一次循環(huán)結(jié)束后，該區(qū)塊得到確認。由此可見，股份授權(quán)證明機制是達到最終一致的狀態(tài)。因此以CAP理論為指導，DPOS采取的是弱化一致性，換取高可用性和分區(qū)容錯性。

3.2.4 實用拜占庭容錯協(xié)議（PBFT）

PBFT中R代表系統(tǒng)節(jié)點的集合，假設故障節(jié)點數(shù)為f個，則整個系統(tǒng)的節(jié)點數(shù)為|R|=3f+1。因此為了保證系統(tǒng)的一致性，至少需要2f+1個節(jié)點進行確認才能達成共識。具體的共識流程如圖4。其中V代表視圖的編號，N代表當前請求的編號，n指的是i節(jié)點的stable checkpoint的編號，M指的是消息的具體內(nèi)容，d或D（m）指的是消息內(nèi)容提取的摘要，i代表當前節(jié)點編號，C代表2f+1個節(jié)點的有效checkpoint信息的集合，P代表i節(jié)點中上一個view中編號大于n并且到達prepared狀態(tài)的請求消息的集合，O代表pre-prepare消息的集合。

圖4 PBFT共識過程

從PBFT的共識流程發(fā)現(xiàn)，PBFT不需要經(jīng)過多個區(qū)塊的確認，只需要至少2f+1個節(jié)點達成共識即可，一旦共識不可修改，可見其注重一致性，那么只能對可用性作一定的妥協(xié)。一旦故障節(jié)點大于m，那么系統(tǒng)就不能繼續(xù)執(zhí)行客戶端的請求。因此PBFT采取的是弱化可用性，換取強一致性和分區(qū)容錯性。

3.2.5 Paxos共識算法

Paxos算法包括客戶端（Client）、提議者（Proposer）、接受者（Acceptor）、學習者（Learner）、領(lǐng)導者（Leader）五個角色，其中每個節(jié)點可以同時是多種角色。具體的共識流程如圖5。其中流程中的f代表最多可能出現(xiàn)的故障接受者節(jié)點，那么至少需要2f+1個接受者節(jié)點。

圖5 Paxos算法共識過程

從Paxos共識算法流程來說，其只需要f+1個節(jié)點達成共識即可，一旦共識，各個節(jié)點的賬本將保持一致，不需等待。因此Paxos是保證了強一致性和分區(qū)容錯性，而對可用性進行了弱化。

3.2.6 Raft共識算法

Raft算法將節(jié)點的狀態(tài)分為領(lǐng)導人（leader）、候選者（candidate）、跟隨者（follower）三種狀態(tài)，每個節(jié)點只能同時處于一種狀態(tài)。其中領(lǐng)導人只有一個。具體的共識流程如圖6。

Raft共識算法將所有的權(quán)利交給領(lǐng)導人，只要領(lǐng)導人加入新交易記錄，那么其他的跟隨者也必須將交易寫入自己的賬本。各節(jié)點的數(shù)據(jù)始終保持一致。故Raft是在確保強一致性和分區(qū)容錯性的情況下，對可用性進行了一定的弱化。

圖6 Raft共識流程

4 共識機制的比較

根據(jù)上述的分析，我們將共識機制的分析結(jié)果總結(jié)為表1。

表1 各共識機制的分析對比

5 結(jié)語

本文從CAP理論的角度，對區(qū)塊鏈的部分共識算法進行了分析與總結(jié)。首先給出了共識機制的定義，并說明了分析思路；然后以流程圖的形式詳細說明了部分共識機制的流程，并從CAP理論的角度按照分析思路給共識機制進行了分析；最后進行了總結(jié)。目前區(qū)塊鏈的應用場景越來越多，本文的分析為區(qū)塊鏈的應用提供了參考價值。我們可以根據(jù)應用場景的需求，選取滿足需求的共識算法。