基于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理論的角度按照分析思路給共識機制進行了分析；最后進行了總結。目前區塊鏈的應用場景越來越多，本文的分析為區塊鏈的應用提供了參考價值。我們可以根據應用場景的需求，選取滿足需求的共識算法。