共識算法的分類

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

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

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

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

1.概率一致性算法

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

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

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

2.絕對一致性算法

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

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

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

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

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

目前被區(qū)塊鏈項目廣泛采用的算法有工作量證明（PoW）、權益證明（PoS）、股份授權證明（DPoS）、實用拜占庭容錯（PBFT）等， 另外一些項目則采用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），要求工作端進行一些耗時適當的復雜運算，并且答案能被服務方快速驗算，以此耗用的時間、設備與能源做為擔保成本，以確保服務與資源是被真正的需求所使用。

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

PoW項目案例

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

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

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

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

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

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

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

PoW共識算法存在的問題

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

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

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

權益證明（Proof of Stake - PoS）

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

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

POS相對于PoW的好處包括：

1）PoW需要花費大量的電力資源，POS的好處首先當然是去除了大量的算力競爭；

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

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

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

PoS項目案例

最初的一版PoS由Peercoin設計實現。用戶要產出block必須滿足以下條件：

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

具體解釋如下：

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

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

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

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

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

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

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

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

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

Blackcoin在Peercoin的基礎上進行了修改，從而緩解了上述問題，主要改動有：

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

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

PoS機制雖然考慮了PoW的不足，但也有缺點：

1）依據權益結余來選擇，會導致首富賬戶的權力更大，有可能支配記賬權；

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

權益授權證明（DPoS）

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

DPoS 算法將成千上萬個 PoS 節(jié)點，通過某種機制（例如持有代幣的數量）選舉出若干節(jié)點， 在它們之間進行投票選舉（一些實現中甚至會以令牌環(huán)的方式進行輪詢，進一步減少投票開銷）出每次的檢查點（出塊）節(jié)點，而不用在網絡中全部節(jié)點之間進行選擇。

DPoS項目案例

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

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

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

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

4）每個代表在生產block的時候，需要找當時唯一的最長鏈進行生產，不能在其他分支上進行生產。

通過上述方法，保證了較短的block生產時間，且因為給每個生產者設置了固定的時間區(qū)間，則block的產出不會因為某個候選節(jié)點的延遲而延遲。

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

DPoS共識算法存在的問題

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

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

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

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

實用拜占庭容錯（PBFT）

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

PBFT算法的步驟：

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

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

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

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

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

PBFT項目案例

Hyperledger Fabric推薦并實現的就是PBFT共識算法。

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

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

PBFT共識算法存在的問題

1）通信量是O（n^2），不適用于節(jié)點數量和網絡環(huán)境不可控的公有鏈項目；

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

PoW + PoS

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

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

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

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