據(jù)庫，密碼學(xué)相關(guān)理論，共識機(jī)制和P2P網(wǎng)絡(luò)。本文將詳細(xì)探討目前主流的區(qū)塊鏈共識算法。

共識算法與CAP理論

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

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

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

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

主流的共識算法概述

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

工作量證明POW

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

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

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

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

· 難度值

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

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

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

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

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

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

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

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

權(quán)益證明POS

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

POS權(quán)益證明的運(yùn)作主要包含兩部分:

驗證

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

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

下圖為驗證的過程:

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

委托

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

授權(quán)股權(quán)證明DPOS

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

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

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

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

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

拜占庭共識機(jī)制PBFT

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

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

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

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

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

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

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

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

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

小結(jié)

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

責(zé)任編輯：ct