區塊鏈主流共識演算法分析

achain星系研究員 achain平臺 前天

 區塊鏈可以概括為一個分散式的高頻交易系統，其核心的技術可以總結為四個部分：分散式的資料庫，密碼學相關理論，共識機制和p2p網路。本文將詳細探討目前主流的區塊鏈共識演算法。

共識演算法與cap理論

要探討共識演算法，首先就需要了解計算機中的cap理論。cap是由eric brewer在2000年podc會議上，提出分散式系統不能同時完全滿足三個要求的假設,其中包括以下三個方面:

• consistency：一致性，是指在分散式系統中的所有資料備份,在同一時刻是否具有同樣的值。

• avaliability：可用性，是指在叢集中一部分節點故障後，叢集群體是否還能響應客戶端的讀寫請求。

• partition tolerance：分割槽容錯性，以實際效果而言，分割槽相當於對通訊的時限要求。系統如果不能在時限內達成資料一致性，就意味著發生了分割槽的情況，必須就當前操作在c和a之間做出選擇。

和所有的分散式系統一樣，區塊鏈共識演算法設計也是在權衡上面的三個因素。假設區塊鏈中的節點能夠立即確認交易資料，這就滿足了cap理論中的ap,可?險是失去了資料的強一致性，因為其他節點可能丟棄這個區塊，因為區塊所在的區塊鏈分叉在競爭性的選舉中失敗了；如果是為了獲得強一致性，即滿足cp的話，那麼客戶端應該等待區塊鏈中的大多數節點都接受了這筆交易後才能真正的接收它，這說明了這筆交易所在的分叉已經選舉勝利，獲得了大部分的共識，獲得了強一致性。但是代價卻是失去了可用性。

那麼為什麼沒有ca這種情況呢?首先在分散式環境下，網路分割槽是一個自然的事實。因為分割槽是必然的，所以如果捨棄p，意味著要捨棄分散式系統，那這也就沒有必要再討論cap理論了。所以在上述中，我們以系統在滿足p的前提下，探討了cp和ap兩種情況下的得與失。

主流的共識演算法概述

目前業界主流的區塊鏈共識演算法有工作量證明pow，權益證明pos，授權股權證明dpos，用於hyperledger的拜占庭演算法pbft等。下面將對這幾種共識的典型代表進行講解。

工作量證明pow

工作量證明pow(proof-of-work)在區塊鏈中最早被提及的是，2008年中本聰的比特幣白皮書論文《a peer to peer electronic cash system》，並隨後在2009年應用到比特幣(bitcoin)中。該共識演算法的設 計理念是整個分散式系統的節點中，每個節點為整個系統提供計算能力(簡稱算力),透過一個競爭機制， 讓計算工作完成最出色的節點獲得系統的獎勵，從而完成新生成貨幣的分配。

pow工作量證明需要滿足三個要素，分別是：

• 工作量證明函式

  在比特幣中使用的是sha256函式，是密碼雜湊函式家族中輸出值為256位的雜湊演算法。

• 區塊

  在區塊中會利用到merkle演算法，將交易以樹的形式進行組合，然後兩兩進行雜湊運算，當為奇數的時候則多算上最後一個交易進行補充。依次進行以葉子節點向根節點的運算，並最終得到根節點的hash值。包含在區塊頭中。

• 難度值

  難度值預設是每2016個區塊調節一次(大概2周)。

  難度係數 = 期望2016個區塊生成所有的時間 / 實際所用的分鐘數 = 20160 / 實際所用的分鐘數

  如果礦工可以比預期更快的構建區塊，比如9分鐘出一個塊，套用公式：

  難度係數 = (2016 * 10) / (2016 * 9) = 1.11

  每個節點使用這個數值來計算下一個階段2016區塊的難度值：

  difficulty * 1.11 = new difficulty

  如果係數大於1(即區塊出塊速度大於預期)，難度值將提高;

  如果係數小於1(即區塊出塊速度小於預期),難度值降低。

pow工作量證明的流程如下:

從流程圖中可以看出，pow工作量證明的流程主要經歷三步:

• 生成merkle根雜湊 

• 組裝區塊頭 

• 計算出工作量證明的輸出

  
  

在這裡，我們以虛擬碼的形式去理解工作量證明的輸出:

i. 工作量證明的輸出 = sha256(sha256(區塊頭 + 變更的隨機數))
ii. if (工作量證明的輸出 >= 目標值),變更隨機數，遞迴i的邏輯，繼續與目標值比對。

iii. if (工作量證明的輸出 >= 目標值),變更隨機數，遞迴i的邏輯，繼續與目標值比對。

最後，生成的符合難度的區塊，將透過p2p傳遞到比特幣的全網路節點並接收，新增到原有區塊鏈的尾部。

由此，我們可以看到pow主要是透過cpu的算力來保證全網的共識安全。

權益證明pos

pos(proof of stake)即權益證明機制，最早出現在點點幣的白皮書中，其核心思想是將貨幣持有人的數 目和持有的時間累計作為被選為共識節點的資本。

pos權益證明的運作主要包含兩部分:

驗證

在整個區塊鏈網路中，參與者會把他們的代幣投給他們認為有效的區塊，如果他們跟網路中的大部分參與者達成一致，就可以獲得和他們代幣成正比的獎勵；而試圖作弊則要冒著失去保證金的?險，例如同時給兩個不同的區塊投票。

在pos中，金錢即力量；pos要求參與者將他們的網路代幣作為安全保證金，使其與網路利益達成一致， 而不是透過消耗電能來加固網路安全。

下圖為驗證的過程:

節點之間會透過接收、簽名、傳送訊息來達成區塊的共識。這種權益和節點基礎設施的組合通常被稱作驗證者。透過這種方式註冊的權益數量決定了相關驗證者在共識過程中的影響力、以及驗證者因工作而獲得的獎勵。

委託

將自己的代幣拖尾給驗證者，以換取獲得獎勵的份額。通常委託人會將代幣存放在智慧合約之中，指定他們想要委託的驗證者。這樣當該驗證者獲得驗證獎勵的時候，委託人也能獲得與其委託代幣數量成正 比的獎勵。整個過程如下:

授權股權證明dpos

授權股權證明機制(delegated proof of stake)最早由daniel larimer提出，bitshares是第一個提出並採用dpos的分散式賬本。簡單來說，dpos的工作原理類似於董事會投票，給持幣者一把可以開啟他們所持股份對應的表決權鑰匙，而不是給他們一把能夠挖礦的鏟子。

dpos引入了?證人的概念，?證人可以生成區塊，每個持股人都可以投票選舉?證人。得到總票數前n(通常為101)的候選者，可以當選?證人。?證人的候選者名單每個維護週期(通常為1天)更新一次。

在bitshares的設計中，利益相關者可以選舉一定數量的?證人來生成區塊。每個賬戶允許對?證人投一票，這個投票過程被稱為"批准投票"。選擇出來的n個?證人被認為是對至少50%的投票利益相關者的代表。每次?證人產生一個區塊，?證人將得到一定的出塊獎勵，如果?證人因為違規來沒有生成區塊，將不能得到獎勵，並且會加入到"黑名單"，從而再次成為?證人的機會會大大降低。

每組被選舉出來的?證人的活躍狀態在每一個週期將會被更新，隨後這組?證人將會被解散。每個?證人給一個2秒的流轉機會用來出塊，當所有的?證人都流轉完成後，該組?證人也會被解散。如果一個?證人在它的時間週期內沒有產生區塊，它的時間機會將會被錯過，下一個?證人將產生下一個區塊。任何節點都可以透過觀察證人的參與率來監控網路的健康狀況。歷史上bitshares曾經維持了99%的?證參與。

所有的?證人會成為特權賬戶的共同簽署者，該賬戶有權提出對網路引數的更改。這個賬戶被稱為起源賬戶。這些引數包括從交易費用到塊大小，?證支付和出塊間隔等。在大多數的?證人批准了一項擬議的變更後，利益相關者將獲得2周的審查期間，在此期間，他們可以對代表進行投票，並根據建議變更或者取消。選擇這種設計是為了確保代表在技術上不具有直接的權利，所有對網路引數的更改最終都得 到利益相關者的批准。在dpos中，我們可以說，行政的權利是由使用者掌握，而不是代表或者證人。

拜占庭共識機制pbft

pbft(practical byzantine fault tolerance)，意為實用拜占庭容錯演算法，是目前最常用的bft演算法之一。最早由miguel castro和barbara liskov在1999年提出，解決了原始拜占庭容錯演算法效率不高的問題，將演算法複雜度由指數級降低到多項式級。

pbft演算法中主要有以下一些引數的定義:

• client: 客戶端，發出呼叫請求的實體

• view:檢視，內容為連續的編號

• replica:網路節點

• primary:主節點，負責生成訊息序列號

• backup:支撐節點，輔助整體共識過程

• state:節點狀態

pbft演算法要求整個系統流程要在同一個檢視(view)下完成，所有節點採取一致的行動。一個客戶端會傳送請求

<request,o,t,c>給replicas，其中，o表示具體的操作，t表示timestamp，給每一個請求加上時間戳， 這樣後來的請求會有高於簽名的時間戳。replicas接收到請求後，如果驗證透過，他就會將其寫入自己的log中。在此請求執行完成後，replicas會返回client一個回覆<reply,v,t,c,i,r>,其中:

• v是當前的view序號

• t是對應請求的時間戳

• i是replica節點的編號

• r是執行結果

每一個replica會與每一個處於active狀態的client共享一份金鑰。金鑰所佔據空間較少，加上會限制active client的數量，所以不必擔心以後出現的擴充套件性問題。

pbft採用三階段提交協議來廣播請求給replicas，分別是pre-parpare、prepare，commit。pre- prepare階段和prepare階段用來把在同一個view裡傳送的請求排序，然後讓各個replicas節點都認可這 個序列，照序執行prepare階段和commit階段用來確保那些已經達到commit狀態的請求，即使在發生檢視改變後，在新的view裡依然保持原有的序列不變，比如一開始在view 0中有req 0，req 1，req 2三個請求依次進入了commit階段，假設沒有惡意階段，那麼這四個replicas即將要依次執行者三條請求並返回給client。但這時主節點問題導致view change的發生，view 0變成view 1，在新的view裡，原本的req 0，req 1，req 2三條請求的序列將被保留。但是處於pre-prepare和prepare階段的請求在view change發生後，在新的view裡都將被遺棄。

下圖是三階段提交協議的時序圖:

小結

本篇中主要講解了區塊鏈的主流共識演算法，下篇中我們將講解與區塊鏈相關的密碼學理論。敬請期待~