共識算法的分類

共識算法解決的是對某個提案（Proposal），大家達(dá)成一致意見的過程。

根據(jù)共識算法采取的策略，可以被分為兩大類，即概率一致性算法和絕對一致性算法。

回顧C(jī)AP 原理，兩類算法的區(qū)別在于對可用性和一致性之間的平衡：

概率一致性算法保證了系統(tǒng)的可用性而犧牲了系統(tǒng)的一致性，絕對一致性算法則與之相反，保證了系統(tǒng)的一致性而犧牲了系統(tǒng)的可用性。

1.概率一致性算法

概率一致性算法指在不同分布式節(jié)點(diǎn)之間，有較大概率保證節(jié)點(diǎn)間數(shù)據(jù)達(dá)到一致，但仍存在一定概率使得某些節(jié)點(diǎn)間數(shù)據(jù)不一致。

對于某一個數(shù)據(jù)點(diǎn)而言，數(shù)據(jù)在節(jié)點(diǎn)間不一致的概率會隨時間的推移逐漸降低至趨近于零，從而最終達(dá)到一致性。

例如工作量證明算法（Proof of Work， PoW）、權(quán)益證明算法（Proof of Stake， PoS）和委托權(quán)益證明算法（Delegated Proof of Stake， DPoS）都屬于概率一致性算法。

2.絕對一致性算法

而絕對一致性算法則指在任意時間點(diǎn)，不同分布式節(jié)點(diǎn)之間的數(shù)據(jù)都會保持絕對一致，不存在不同節(jié)點(diǎn)間數(shù)據(jù)不一致的情況。

例如分布式系統(tǒng)中常用的 Paxos 算法及其衍生出的 Raft 算法等，以及拜占庭容錯類算法（類 BFT 算法），例如PBFT算法。

區(qū)塊鏈項(xiàng)目中常用的共識算法

傳統(tǒng)分布式數(shù)據(jù)庫主要使用Paxos和Raft算法解決分布式一致性問題，它們假定系統(tǒng)中每個節(jié)點(diǎn)都是忠誠、不作惡的，但報(bào)文可能發(fā)生丟失和延時等問題。

當(dāng)分布式數(shù)據(jù)庫的所有節(jié)點(diǎn)由單一機(jī)構(gòu)統(tǒng)一維護(hù)時，此假定成立。在去中心化的區(qū)塊鏈網(wǎng)絡(luò)中，節(jié)點(diǎn)由互不了解、互不信任的多方參與者共同提供和維護(hù)，受各種利益驅(qū)動，網(wǎng)絡(luò)中的參與者存在欺騙、作惡的可能，因此Paxos和Raft算法不能直接用于區(qū)塊鏈的共識。

目前被區(qū)塊鏈項(xiàng)目廣泛采用的算法有工作量證明（PoW）、權(quán)益證明（PoS）、股份授權(quán)證明（DPoS）、實(shí)用拜占庭容錯（PBFT）等， 另外一些項(xiàng)目則采用2種算法的混合算法，如PoW+PoS、DPoS+PBFT等， 此外還有燃燒證明（PoB，Proof of Burn）、沉淀證明（PoD，Proof of Deposit）、能力證明（PoC，Proof of Capacity）、消逝時間證明（PoET，Proof of Elapsed Time）等尚不成熟的算法。

工作量證明（Proof-of-Work， PoW）

工作量證明（Proof-of-Work， PoW），要求工作端進(jìn)行一些耗時適當(dāng)?shù)膹?fù)雜運(yùn)算，并且答案能被服務(wù)方快速驗(yàn)算，以此耗用的時間、設(shè)備與能源做為擔(dān)保成本，以確保服務(wù)與資源是被真正的需求所使用。

工作量證明最常用的技術(shù)原理是哈希散列函數(shù)。由于輸入哈希函數(shù)h（）的任意值n，會對應(yīng)到一個h（n）結(jié)果，而n只要變動一個比特，得到的結(jié)果就完全不同，所以幾乎無法從h（n）反推回n，因此借由指定查找h（n）的特征（例如要求小于某個數(shù)值，即哈希值前綴要求一定數(shù)量的0，增加難度即增加前綴0的數(shù)量），讓用戶進(jìn)行大量的窮舉運(yùn)算，就可以達(dá)成工作量證明。

PoW項(xiàng)目案例

PoW共識算法最初在比特幣系統(tǒng)中提出和應(yīng)用。

比特幣系統(tǒng)在挖礦的過程中每10分鐘生成一個區(qū)塊。為了保證比特幣系統(tǒng)能穩(wěn)定地發(fā)展并不斷產(chǎn)生區(qū)塊，比特幣的協(xié)議中人為地設(shè)置了這個10分鐘規(guī)律，這使得系統(tǒng)中的所有節(jié)點(diǎn)可以利用這10分鐘的時間，來完成接收，打包，見證的工作，同時將產(chǎn)生的交易在整個網(wǎng)絡(luò)里進(jìn)行廣播。

比特幣將區(qū)塊間隔設(shè)計(jì)為10分鐘，其實(shí)是在更快速的交易確認(rèn)和更低的分叉概率間作出的妥協(xié)。盡管如此，分叉也不可避免，例如當(dāng)有兩名礦工A和B在幾乎在相同的時間內(nèi)，各自都算得了工作量證明解，便立即傳播自己的區(qū)塊到網(wǎng)絡(luò)中，這樣導(dǎo)致網(wǎng)絡(luò)中一部分節(jié)點(diǎn)跟隨A的區(qū)塊，另一部分節(jié)點(diǎn)會跟隨B的區(qū)塊，兩部分網(wǎng)絡(luò)數(shù)據(jù)產(chǎn)生了不一致，即分叉。

比特幣的策略是，在產(chǎn)生分叉后，兩個分叉的網(wǎng)絡(luò)各自繼續(xù)挖礦，由于算力不一樣，一段時間后，兩個分叉的鏈的長度就會不一致，當(dāng)網(wǎng)絡(luò)上的節(jié)點(diǎn)收到兩個分叉廣播過來的區(qū)塊后，就選擇包含最多區(qū)塊的那個鏈（最長鏈）為主鏈，這樣，較短的分叉上的工作就會停止，這樣每個人就會都在同一個順序的這樣上工作了。盡管在一段時間內(nèi)會出現(xiàn)不一致，但保證最終能達(dá)成一致。

同時比特幣由于分叉問題的存在，為防止出現(xiàn)雙重支付問題，規(guī)定每個交易需要至少有5個驗(yàn)證過的區(qū)塊在其后面得到驗(yàn)證才能算作確認(rèn)，也就是說比特幣的共識機(jī)制認(rèn)為等待6個確認(rèn)的情況下，分叉切換的概率就足夠低了（例如按一個節(jié)點(diǎn)1%的算力來計(jì)算，6個區(qū)塊后被長度被趕超的概率是100的6次方分之1）。

以太坊是另一個這類協(xié)議的典型，其同步假設(shè)的出塊時間僅為15秒。以太坊的出塊速度較比特幣的10分鐘大幅縮短，這使得以太坊系統(tǒng)在產(chǎn)出速度上有更高的效率，交易在全網(wǎng)廣播所費(fèi)的時間更短，但也正因?yàn)槿绱?，結(jié)果形成了許多孤立區(qū)塊。

總結(jié)PoW共識算法思路，其實(shí)是放寬對最終一致性確認(rèn)的需求，約定好大家都選擇已知最長的鏈進(jìn)行確認(rèn)，PoW系統(tǒng)的最終確認(rèn)是概率意義上的，是被強(qiáng)制推遲的。這樣的好處是，即便有人試圖惡意破壞，也會付出很大的經(jīng)濟(jì)代價(jià)（付出超過系統(tǒng)一半的算力）。

PoW共識算法存在的問題

1）算力競爭的設(shè)計(jì)導(dǎo)致了集中化的礦池：盡管PoW的目的是為了保證系統(tǒng)可以去中心化的運(yùn)行，然而系統(tǒng)運(yùn)行到現(xiàn)在，卻事實(shí)上形成中心化程度很高的五大礦池。五大礦池壟斷了世界上90%以上的算力，這可能導(dǎo)致大礦池破壞整個網(wǎng)絡(luò)的行為。

2）算力競爭的設(shè)計(jì)導(dǎo)致了大量的能源消耗： 另外，PoW系統(tǒng)需要產(chǎn)生大量的能源消耗：比特幣挖礦比159個國家消耗的能源還多；目前77.7%的全球比特幣網(wǎng)絡(luò)算力仍在中國境內(nèi)；受益于內(nèi)蒙古和四川兩地充沛的電力資源，中國擁有世界上最多的比特幣礦場；到2019年7月，比特幣網(wǎng)絡(luò)將需要比美國目前的用電量更多的電力；到2020年2月，它將使用和今天全世界一樣多的電力。

3）業(yè)務(wù)處理性能低下：盡管投入了大量的能源支持系統(tǒng)的運(yùn)行，但這些能源消耗絕大部份是用于工作量證明中的hash運(yùn)算，處理交易業(yè)務(wù)的性能則非常低，例如比特幣每秒只能進(jìn)行大約7筆交易；以太坊每秒10-20筆。

權(quán)益證明（Proof of Stake - PoS）

權(quán)益證明（Proof of Stake - POS）， 所有持有該區(qū)塊鏈電子貨幣的使用者都可通過一個特殊交易將他們的電子貨幣鎖定存入一個資金庫，之后他們就可以成為驗(yàn)證者。

算法通過固定時間協(xié)調(diào)所有節(jié)點(diǎn)參與投票，根據(jù)某種規(guī)則（例如持代幣數(shù)量、或提供存儲空間大小等）判斷每個節(jié)點(diǎn)的權(quán)重，最后選取權(quán)重最高的節(jié)點(diǎn)作為檢查。

POS相對于PoW的好處包括：

1）PoW需要花費(fèi)大量的電力資源，POS的好處首先當(dāng)然是去除了大量的算力競爭；

2）不需要通過不停地發(fā)行新幣來激勵礦工參與算力競賽。避免了不可知的通脹風(fēng)險(xiǎn)；

3）提出了利用博弈論來避免區(qū)塊鏈網(wǎng)絡(luò)產(chǎn)生中心化的大型參與者的新的方法。PoW的算力競爭設(shè)計(jì)模式導(dǎo)致了算力越來越向大礦池集中，這可能導(dǎo)致大礦池破壞整個網(wǎng)絡(luò)的行為；

4）PoS還可以使51%攻擊變的異常昂貴。惡意參與者將存在保證金被罰沒的風(fēng)險(xiǎn)。

PoS項(xiàng)目案例

最初的一版PoS由Peercoin設(shè)計(jì)實(shí)現(xiàn)。用戶要產(chǎn)出block必須滿足以下條件：

hash（stake_modifier， current_time， UTXO） 《 coin（UTXO） * age（UTXO） * difficulty.

具體解釋如下：

1）用戶在每一秒時間（current_time），遍歷自己所有的UTXO，代入上述公式中，看是否能滿足不等式條件；如果滿足，就把相應(yīng)的UTXO記錄在block中，并發(fā)布block；

2）stake_modifier是對前一個block中部分字段hash后的值，加入這一項(xiàng)是為了防止用戶提前預(yù)知自己何時有權(quán)挖礦；

3）difficulty會根據(jù)近期的block產(chǎn)出時間動態(tài)調(diào)整，保證block產(chǎn)出時間間隔穩(wěn)定；

4）由于每秒只需要完成和自己UTXO數(shù)量相等的hash計(jì)算，所以需要的算力較低；

5）從不等式可以看出，持有的UTXO越多、UTXO中token數(shù)額越大（coin（UTXO））、UTXO持有時間越長（age（UTXO），或稱之為幣齡），不等式越容易成立，越容易進(jìn)行挖礦。

該版本的PoS面臨著如下的問題

1）因?yàn)闃?gòu)造新的block沒有算力成本，所以當(dāng)區(qū)塊鏈出現(xiàn)fork的時候，用戶有可能會傾向于同時在多個branch一起挖礦來獲得潛在更高的收益，這樣制造了大量的分支，破壞了一致性；

2）出現(xiàn)了攢幣齡的現(xiàn)象，即關(guān)閉節(jié)點(diǎn)，直到age（UTXO）足夠大的時候再啟動節(jié)點(diǎn)挖礦，從而節(jié)省電力，這樣引起了在線節(jié)點(diǎn)數(shù)太少系統(tǒng)脆弱的問題；

3）可以攢夠足夠的幣齡后，保證自己有足夠的UTXO能夠連續(xù)生產(chǎn)block，從而發(fā)動double-spend攻擊。

Blackcoin在Peercoin的基礎(chǔ)上進(jìn)行了修改，從而緩解了上述問題，主要改動有：

1）去掉了不等式公式右邊的age（UTXO），從而解決了問題3中攢幣齡然后進(jìn)行double-spend的現(xiàn)象；但是block獎勵還是使用了幣齡，因此并不能完全解決問題2中節(jié)點(diǎn)關(guān)閉的現(xiàn)象；

2）優(yōu)化了stake_modifier的計(jì)算邏輯，讓用戶提前預(yù)知自己有權(quán)挖礦時間的難度更大了。

PoS機(jī)制雖然考慮了PoW的不足，但也有缺點(diǎn)：

1）依據(jù)權(quán)益結(jié)余來選擇，會導(dǎo)致首富賬戶的權(quán)力更大，有可能支配記賬權(quán)；

2）PoS的一致問題：PoS的挖礦過程，與PoW的問題類似，是全網(wǎng)所有節(jié)點(diǎn)共同參與的，每一時刻都有成千上萬個節(jié)點(diǎn)同時去爭取產(chǎn)出下一個block，因此會時有發(fā)生區(qū)塊鏈分叉的問題。由于分叉的存在，block的產(chǎn)出時間間隔不能太短。各區(qū)塊鏈通過動態(tài)調(diào)整的挖礦難度，將block時間間隔穩(wěn)定在自己期望的水平。出塊時間長，伴隨而來的則是交易確認(rèn)時間長和交易處理性能低。

權(quán)益授權(quán)證明（DPoS）

股份授權(quán)證明機(jī)制（Delegated Proof of Stake，DPoS），是針對PoW、PoS的不足提出的。

DPoS 算法將成千上萬個 PoS 節(jié)點(diǎn)，通過某種機(jī)制（例如持有代幣的數(shù)量）選舉出若干節(jié)點(diǎn)， 在它們之間進(jìn)行投票選舉（一些實(shí)現(xiàn)中甚至?xí)粤钆骗h(huán)的方式進(jìn)行輪詢，進(jìn)一步減少投票開銷）出每次的檢查點(diǎn)（出塊）節(jié)點(diǎn)，而不用在網(wǎng)絡(luò)中全部節(jié)點(diǎn)之間進(jìn)行選擇。

DPoS項(xiàng)目案例

EOS前身石墨烯框架及bitshares（比特股）項(xiàng)目提出的DPOS方案，其步驟簡述如下：

1）持有token的用戶可以對候選的block producer進(jìn)行投票；

2）得票最高的n個用戶被選為代表，在下一個周期中負(fù)責(zé)產(chǎn)出block，目前n=21；

3）打亂代表的順序后，各代表開始依次生產(chǎn)block。每個代表都有自己固定的時間區(qū)間，需要在自己的區(qū)間中完成block的生產(chǎn)發(fā)布。目前這個區(qū)間是3秒，即在正常情況下每3秒產(chǎn)出一個block；

4）每個代表在生產(chǎn)block的時候，需要找當(dāng)時唯一的最長鏈進(jìn)行生產(chǎn)，不能在其他分支上進(jìn)行生產(chǎn)。

通過上述方法，保證了較短的block生產(chǎn)時間，且因?yàn)榻o每個生產(chǎn)者設(shè)置了固定的時間區(qū)間，則block的產(chǎn)出不會因?yàn)槟硞€候選節(jié)點(diǎn)的延遲而延遲。

EOS最初使用的是DPoS算法，后來為了縮短出塊時間，改成BPT-DPoS算法。

DPoS共識算法存在的問題

1）以EOS為代表的DPoS算法設(shè)計(jì)成由少數(shù)節(jié)點(diǎn)代替多數(shù)節(jié)點(diǎn)進(jìn)行共識，其實(shí)是犧牲了區(qū)塊鏈去中心化的特性，以此來換取共識效率的提升；

2）EOS的21個超級節(jié)點(diǎn)并不是21個不同實(shí)體，節(jié)點(diǎn)之間可能存在內(nèi)在聯(lián)系的共謀；

3）超級節(jié)點(diǎn)競選爭議。由于網(wǎng)絡(luò)無法解決女巫攻擊問題，1人1票的民主投票制會被1代幣1票制度所取代，導(dǎo)致“富豪統(tǒng)治”的結(jié)果；而相對不富裕的、擁有投票權(quán)較少的投資者則會對投票這件事漠不關(guān)心；超級節(jié)點(diǎn)可以花錢買選民們的投票；超級節(jié)點(diǎn)之間被鼓勵互相串通，這樣他們就可以改變他們與選民分享獎勵的比例；

4）DPoS允許不超過節(jié)點(diǎn)總數(shù)三分之一的惡意或故障節(jié)點(diǎn)可能創(chuàng)建少數(shù)分叉。在這種情況下，少數(shù)分叉每9秒只能產(chǎn)生一個塊，而多數(shù)分叉每9秒可以產(chǎn)生兩個塊。這樣，誠實(shí)的2/3多數(shù)將永遠(yuǎn)比少數(shù)（的鏈）更長。

實(shí)用拜占庭容錯（PBFT）

PBFT算法的結(jié)論是n》=3f+1， n是系統(tǒng)中的總節(jié)點(diǎn)數(shù)，f是允許出現(xiàn)故障的節(jié)點(diǎn)數(shù)。換句話說，如果這個系統(tǒng)允許出現(xiàn)f個故障，那么這個系統(tǒng)必須包括n個節(jié)點(diǎn)，才能解決故障。這和上文口頭協(xié)議的結(jié)論一樣，或者這么說，PBFT是優(yōu)化了口頭協(xié)議機(jī)制的效率，但是結(jié)論并未改變。

PBFT算法的步驟：

1）取一個副本作為主節(jié)點(diǎn)（圖中0），其他的副本作為備份；

2）用戶（圖中C）向主節(jié)點(diǎn)發(fā)送消息請求；

3）主節(jié)點(diǎn)通過廣播將請求發(fā)送給其他節(jié)點(diǎn)（圖中1、2、3）；

4）所有節(jié)點(diǎn)執(zhí)行請求并將結(jié)果發(fā)回用戶端；

5）用戶端需要等待f+1個不同副本節(jié)點(diǎn)發(fā)回相同的結(jié)果，即可作為整個操作的最終結(jié)果。

PBFT項(xiàng)目案例

Hyperledger Fabric推薦并實(shí)現(xiàn)的就是PBFT共識算法。

PBFT不僅具備強(qiáng)一致性的特性，而且提供了較高的共識效率，比較適合對一致性和性能要求較高的區(qū)塊鏈項(xiàng)目，但由于PBFT需要兩兩節(jié)點(diǎn)需要進(jìn)行通信，通信量是O（n^2）（通過優(yōu)化可以減少通信量），在公有鏈這種全球性的大環(huán)境下，節(jié)點(diǎn)數(shù)量和網(wǎng)絡(luò)環(huán)境不可控，無法達(dá)成這種巨大的通信量。

不過對于聯(lián)盟鏈和私有鏈，節(jié)點(diǎn)數(shù)量并不是很多，采用PBFT效率更高結(jié)果也更好，因此PBFT在聯(lián)盟鏈和私有鏈的區(qū)塊鏈項(xiàng)目中使用較為廣泛。這也是Fabric項(xiàng)目采用PBFT算法的原因。

PBFT共識算法存在的問題

1）通信量是O（n^2），不適用于節(jié)點(diǎn)數(shù)量和網(wǎng)絡(luò)環(huán)境不可控的公有鏈項(xiàng)目；

2）PBFT是強(qiáng)一致性算法，在可用性上作了讓步，當(dāng)有1/3或以上記賬人停止工作后，系統(tǒng)將無法提供服務(wù)。

PoW + PoS

共識機(jī)制目前已經(jīng)成為了區(qū)塊鏈系統(tǒng)性能的關(guān)鍵瓶頸。單一的共識算法均存在各種問題，例如PoW算法存在消耗大量計(jì)算資源及性能低下的問題；PoS或DPoS存在“富豪統(tǒng)治”問題；而有著完善理論證明的PBFT算法面臨著廣播帶來的網(wǎng)絡(luò)開銷過大的問題。融合多種共識算法優(yōu)勢的想法正受到越來越廣泛的關(guān)注。

例如以太坊社區(qū)提出的正在研發(fā)中的共識協(xié)議名為Casper，是一個覆蓋在已存在的以太坊PoW提議機(jī)制上的PoS，Casper融合了PoW和PoS兩種算法。

Casper的基本思路是，任何人抵押足夠多的以太幣到系統(tǒng)中就可以成為礦工參與到挖礦過程。共識算法要求所有的礦工誠實(shí)工作，如果一個礦工有意破壞，不遵守協(xié)議，系統(tǒng)就會對礦工做出懲罰：沒收之前抵押的以太幣。有人把Casper這樣的挖礦機(jī)制稱為“虛擬挖礦”，比特幣的礦工要參與挖礦需要先購買礦機(jī)，Casper則要先抵押以太幣到系統(tǒng)中；比特幣的礦工如果不按規(guī)則挖礦，則會損失電費(fèi)以及可能的挖礦收益，而Casper中，不守規(guī)則的懲罰更為嚴(yán)重，除了失去挖礦收益，還要銷毀“礦機(jī)”：抵押的以太幣會被系統(tǒng)沒收！

Casper的應(yīng)用邏輯存在于智能合約的內(nèi)部。要想在Casper中成為驗(yàn)證者，必須要有ETH并且要將ETH存儲到Casper智能合約中作為杠桿的權(quán)益。在Casper第一次迭代中區(qū)塊提議的機(jī)制會被保留：它依然使用Nakamoto PoW共識，礦工可以創(chuàng)建區(qū)塊。不過為了最終化區(qū)塊，Casper的PoS覆蓋掌握控制權(quán)，并且擁有自己的驗(yàn)證者在PoW礦工之后進(jìn)行投票。