據(jù)庫，密碼學相關理論，共識機制和P2P網絡。本文將詳細探討目前主流的區(qū)塊鏈共識算法。

共識算法與CAP理論

要探討共識算法，首先就需要了解計算機中的CAP理論。CAP是由Eric Brewer在2000年PODC會議上，提出分布式系統(tǒng)不能同時完全滿足三個要求的假設,其中包括以下三個方面:

· Consistency：一致性，是指在分布式系統(tǒng)中的所有數(shù)據(jù)備份,在同一時刻是否具有同樣的值。
· Avaliability：可用性，是指在集群中一部分節(jié)點故障后，集群群體是否還能響應客戶端的讀寫請求。
· Partition tolerance：分區(qū)容錯性，以實際效果而言，分區(qū)相當于對通信的時限要求。系統(tǒng)如果不能在時限內達成數(shù)據(jù)一致性，就意味著發(fā)生了分區(qū)的情況，必須就當前操作在C和A之間做出選擇。

和所有的分布式系統(tǒng)一樣，區(qū)塊鏈共識算法設計也是在權衡上面的三個因素。假設區(qū)塊鏈中的節(jié)點能夠立即確認交易數(shù)據(jù)，這就滿足了CAP理論中的AP,可?險是失去了數(shù)據(jù)的強一致性，因為其他節(jié)點可能丟棄這個區(qū)塊，因為區(qū)塊所在的區(qū)塊鏈分叉在競爭性的選舉中失敗了；如果是為了獲得強一致性，即滿足CP的話，那么客戶端應該等待區(qū)塊鏈中的大多數(shù)節(jié)點都接受了這筆交易后才能真正的接收它，這說明了這筆交易所在的分叉已經選舉勝利，獲得了大部分的共識，獲得了強一致性。但是代價卻是失去了可用性。

那么為什么沒有CA這種情況呢?首先在分布式環(huán)境下，網絡分區(qū)是一個自然的事實。因為分區(qū)是必然的，所以如果舍棄P，意味著要舍棄分布式系統(tǒng)，那這也就沒有必要再討論CAP理論了。所以在上述中，我們以系統(tǒng)在滿足P的前提下，探討了CP和AP兩種情況下的得與失。

主流的共識算法概述

目前業(yè)界主流的區(qū)塊鏈共識算法有工作量證明POW，權益證明POS，授權股權證明DPOS，用于Hyperledger的拜占庭算法PBFT等。下面將對這幾種共識的典型代表進行講解。

工作量證明POW

工作量證明POW(Proof-of-work)在區(qū)塊鏈中最早被提及的是，2008年中本聰?shù)?a href="http://www.solar-ruike.com.cn/tags/比特幣/" target="_blank">比特幣白皮書論文《A peer to peer electronic cash system》，并隨后在2009年應用到比特幣(Bitcoin)中。該共識算法的設 計理念是整個分布式系統(tǒng)的節(jié)點中，每個節(jié)點為整個系統(tǒng)提供計算能力(簡稱算力),通過一個競爭機制， 讓計算工作完成最出色的節(jié)點獲得系統(tǒng)的獎勵，從而完成新生成貨幣的分配。

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

· 工作量證明函數(shù)
在比特幣中使用的是SHA256函數(shù)，是密碼哈希函數(shù)家族中輸出值為256位的哈希算法。

· 區(qū)塊
在區(qū)塊中會利用到merkle算法，將交易以樹的形式進行組合，然后兩兩進行哈希運算，當為奇數(shù)的時候則多算上最后一個交易進行補充。依次進行以葉子節(jié)點向根節(jié)點的運算，并最終得到根節(jié)點的hash值。包含在區(qū)塊頭中。

· 難度值

難度值默認是每2016個區(qū)塊調節(jié)一次(大概2周)。
難度系數(shù) = 期望2016個區(qū)塊生成所有的時間 / 實際所用的分鐘數(shù) = 20160 / 實際所用的分鐘數(shù)
如果礦工可以比預期更快的構建區(qū)塊，比如9分鐘出一個塊，套用公式：
難度系數(shù) = (2016 * 10) / (2016 * 9) = 1.11
每個節(jié)點使用這個數(shù)值來計算下一個階段2016區(qū)塊的難度值：
Difficulty * 1.11 = new Difficulty
如果系數(shù)大于1(即區(qū)塊出塊速度大于預期)，難度值將提高;
如果系數(shù)小于1(即區(qū)塊出塊速度小于預期),難度值降低。
?

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

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

· 生成Merkle根哈希?
· 組裝區(qū)塊頭?
· 計算出工作量證明的輸出

在這里，我們以偽代碼的形式去理解工作量證明的輸出:

i. 工作量證明的輸出 = SHA256(SHA256(區(qū)塊頭 + 變更的隨機數(shù)))
ii. if (工作量證明的輸出 >= 目標值),變更隨機數(shù)，遞歸i的邏輯，繼續(xù)與目標值比對。
iii. if (工作量證明的輸出 >= 目標值),變更隨機數(shù)，遞歸i的邏輯，繼續(xù)與目標值比對。

最后，生成的符合難度的區(qū)塊，將通過P2P傳遞到比特幣的全網絡節(jié)點并接收，添加到原有區(qū)塊鏈的尾部。

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

權益證明POS

POS(Proof of Stake)即權益證明機制，最早出現(xiàn)在點點幣的白皮書中，其核心思想是將貨幣持有人的數(shù) 目和持有的時間累計作為被選為共識節(jié)點的資本。

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

驗證

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

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

下圖為驗證的過程:

節(jié)點之間會通過接收、簽名、發(fā)送消息來達成區(qū)塊的共識。這種權益和節(jié)點基礎設施的組合通常被稱作驗證者。通過這種方式注冊的權益數(shù)量決定了相關驗證者在共識過程中的影響力、以及驗證者因工作而獲得的獎勵。

委托

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

授權股權證明DPOS

授權股權證明機制(Delegated Proof of Stake)最早由Daniel Larimer提出，BitShares是第一個提出并采用DPOS的分布式賬本。簡單來說，DPOS的工作原理類似于董事會投票，給持幣者一把可以開啟他們所持股份對應的表決權鑰匙，而不是給他們一把能夠挖礦的鏟子。

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

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

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

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

拜占庭共識機制PBFT

PBFT(Practical Byzantine Fault Tolerance)，意為實用拜占庭容錯算法，是目前最常用的BFT算法之一。最早由Miguel Castro和Barbara Liskov在1999年提出，解決了原始拜占庭容錯算法效率不高的問題，將算法復雜度由指數(shù)級降低到多項式級。

PBFT算法中主要有以下一些參數(shù)的定義:

client: 客戶端，發(fā)出調用請求的實體
view:視圖，內容為連續(xù)的編號
replica:網絡節(jié)點
primary:主節(jié)點，負責生成消息序列號
backup:支撐節(jié)點，輔助整體共識過程
state:節(jié)點狀態(tài)

PBFT算法要求整個系統(tǒng)流程要在同一個視圖(view)下完成，所有節(jié)點采取一致的行動。一個客戶端會發(fā)送請求

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

v是當前的view序號
t是對應請求的時間戳
i是replica節(jié)點的編號
r是執(zhí)行結果

每一個replica會與每一個處于active狀態(tài)的client共享一份密鑰。密鑰所占據(jù)空間較少，加上會限制active client的數(shù)量，所以不必擔心以后出現(xiàn)的擴展性問題。

PBFT采用三階段提交協(xié)議來廣播請求給replicas，分別是pre-parpare、prepare，commit。pre- prepare階段和prepare階段用來把在同一個view里發(fā)送的請求排序，然后讓各個replicas節(jié)點都認可這 個序列，照序執(zhí)行prepare階段和commit階段用來確保那些已經達到commit狀態(tài)的請求，即使在發(fā)生視圖改變后，在新的view里依然保持原有的序列不變，比如一開始在view 0中有req 0，req 1，req 2三個請求依次進入了commit階段，假設沒有惡意階段，那么這四個replicas即將要依次執(zhí)行者三條請求并返回給client。但這時主節(jié)點問題導致view change的發(fā)生，view 0變成view 1，在新的view里，原本的req 0，req 1，req 2三條請求的序列將被保留。但是處于pre-prepare和prepare階段的請求在view change發(fā)生后，在新的view里都將被遺棄。

下圖是三階段提交協(xié)議的時序圖:

小結

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

責任編輯：ct