區(qū)塊鏈主流共識(shí)算法你了不了解

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

共識(shí)算法與CAP理論

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

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

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

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

主流的共識(shí)算法概述

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

工作量證明POW

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

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

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

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

· 難度值

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

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

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

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

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

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

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

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

權(quán)益證明POS

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

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

驗(yàn)證

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

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

下圖為驗(yàn)證的過程:

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

委托

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

小結(jié)

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

責(zé)任編輯：ct