區(qū)塊鏈項(xiàng)目中共識算法的分類，及存在的問題分析

共識算法的分類

共識算法解決的是對某個(gè)提案（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ù)不一致。

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

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

2.絕對一致性算法

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

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

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

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

當(dāng)分布式數(shù)據(jù)庫的所有節(jié)點(diǎn)由單一機(jī)構(gòu)統(tǒng)一維護(hù)時(shí)，此假定成立。在去中心化的區(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í)用拜占庭容錯(cuò)（PBFT）等， 另外一些項(xiàng)目則采用2種算法的混合算法，如PoW+PoS、DPoS+PBFT等， 此外還有燃燒證明（PoB，Proof of Burn）、沉淀證明（PoD，Proof of Deposit）、能力證明（PoC，Proof of Capacity）、消逝時(shí)間證明（PoET，Proof of Elapsed Time）等尚不成熟的算法。

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

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

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

PoW項(xiàng)目案例

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

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

比特幣將區(qū)塊間隔設(shè)計(jì)為10分鐘，其實(shí)是在更快速的交易確認(rèn)和更低的分叉概率間作出的妥協(xié)。盡管如此，分叉也不可避免，例如當(dāng)有兩名礦工A和B在幾乎在相同的時(shí)間內(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)生分叉后，兩個(gè)分叉的網(wǎng)絡(luò)各自繼續(xù)挖礦，由于算力不一樣，一段時(shí)間后，兩個(gè)分叉的鏈的長度就會不一致，當(dāng)網(wǎng)絡(luò)上的節(jié)點(diǎn)收到兩個(gè)分叉廣播過來的區(qū)塊后，就選擇包含最多區(qū)塊的那個(gè)鏈（最長鏈）為主鏈，這樣，較短的分叉上的工作就會停止，這樣每個(gè)人就會都在同一個(gè)順序的這樣上工作了。盡管在一段時(shí)間內(nèi)會出現(xiàn)不一致，但保證最終能達(dá)成一致。

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

以太坊是另一個(gè)這類協(xié)議的典型，其同步假設(shè)的出塊時(shí)間僅為15秒。以太坊的出塊速度較比特幣的10分鐘大幅縮短，這使得以太坊系統(tǒng)在產(chǎn)出速度上有更高的效率，交易在全網(wǎng)廣播所費(fèi)的時(shí)間更短，但也正因?yàn)槿绱耍Y(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)致大礦池破壞整個(gè)網(wǎng)絡(luò)的行為。

2）算力競爭的設(shè)計(jì)導(dǎo)致了大量的能源消耗： 另外，PoW系統(tǒng)需要產(chǎn)生大量的能源消耗：比特幣挖礦比159個(gè)國家消耗的能源還多；目前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ū)塊鏈電子貨幣的使用者都可通過一個(gè)特殊交易將他們的電子貨幣鎖定存入一個(gè)資金庫，之后他們就可以成為驗(yàn)證者。

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

POS相對于PoW的好處包括：

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

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

3）提出了利用博弈論來避免區(qū)塊鏈網(wǎng)絡(luò)產(chǎn)生中心化的大型參與者的新的方法。PoW的算力競爭設(shè)計(jì)模式導(dǎo)致了算力越來越向大礦池集中，這可能導(dǎo)致大礦池破壞整個(gè)網(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）用戶在每一秒時(shí)間（current_TIme），遍歷自己所有的UTXO，代入上述公式中，看是否能滿足不等式條件；如果滿足，就把相應(yīng)的UTXO記錄在block中，并發(fā)布block；

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

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

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

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

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

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

2）出現(xiàn)了攢幣齡的現(xiàn)象，即關(guān)閉節(jié)點(diǎn)，直到age（UTXO）足夠大的時(shí)候再啟動節(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獎(jiǎng)勵(lì)還是使用了幣齡，因此并不能完全解決問題2中節(jié)點(diǎn)關(guān)閉的現(xiàn)象；

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

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

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

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

DPoS 算法將成千上萬個(gè) 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個(gè)用戶被選為代表，在下一個(gè)周期中負(fù)責(zé)產(chǎn)出block，目前n=21；

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

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

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

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

DPoS共識算法存在的問題

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

2）EOS的21個(gè)超級節(jié)點(diǎn)并不是21個(gè)不同實(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)之間被鼓勵(lì)互相串通，這樣他們就可以改變他們與選民分享獎(jiǎng)勵(lì)的比例；

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

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

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

PBFT算法的步驟：

1）取一個(gè)副本作為主節(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個(gè)不同副本節(jié)點(diǎn)發(fā)回相同的結(jié)果，即可作為整個(gè)操作的最終結(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，是一個(gè)覆蓋在已存在的以太坊PoW提議機(jī)制上的PoS，Casper融合了PoW和PoS兩種算法。

Casper的基本思路是，任何人抵押足夠多的以太幣到系統(tǒng)中就可以成為礦工參與到挖礦過程。共識算法要求所有的礦工誠實(shí)工作，如果一個(gè)礦工有意破壞，不遵守協(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)行投票。