據庫，密碼學相關理論，共識機制和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)下完成，所有節點采取一致的行動。一個客戶端會發送請求

給replicas，其中，o表示具體的操作，t表示timestamp，給每一個請求加上時間戳， 這樣后來的請求會有高于簽名的時間戳。Replicas接收到請求后，如果驗證通過，他就會將其寫入自己的log中。在此請求執行完成后，replicas會返回client一個回復,其中:

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里都將被遺棄。

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

小結

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

責任編輯：ct