比較區塊鏈專案中常用的共識演算法

買賣虛擬貨幣
本期推送中,我們將基於理論來分析幾個區塊鏈專案廣泛採用的共識演算法;而在下期推送中,我們的工程師會詳細介紹迅雷鏈是如何最佳化提升共識效率和可用性的。共識演算法的分類共識演算法解決的是對某個提案(Proposal),大家達成一致意見的過程。根據共識演算法採取的策略,可以被分為兩大類,即概率一致性演算法和絕對一致性演算法。回顧CAP 原理,兩類演算法的區別在於對可用性和一致性之間的平衡:概率一致性演算法保證了系統的可用性而犧牲了系統的一致性,絕對一致性演算法則與之相反,保證了系統的一致性而犧牲了系統的可用性。
1.概率一致性演算法概率一致性演算法指在不同分散式節點之間,有較大概率保證節點間資料達到一致,但仍存在一定概率使得某些節點間資料不一致。對於某一個資料點而言,資料在節點間不一致的概率會隨時間的推移逐漸降低至趨近於零,從而最終達到一致性。例如工作量證明演算法(Proof of Work, PoW)、權益證明演算法(Proof of Stake, PoS)和委託權益證明演算法(Delegated Proof of Stake, DPoS)都屬於概率一致性演算法。2.絕對一致性演算法而絕對一致性演算法則指在任意時間點,不同分散式節點之間的資料都會保持絕對一致,不存在不同節點間資料不一致的情況。
例如分散式系統中常用的 Paxos 演算法及其衍生出的 Raft 演算法等,以及拜占庭容錯類演算法(類 BFT 演算法),例如PBFT演算法。區塊鏈專案中常用的共識演算法傳統分散式資料庫主要使用Paxos和Raft演算法解決分散式一致性問題,它們假定系統中每個節點都是忠誠、不作惡的,但報文可能發生丟失和延時等問題。當分散式資料庫的所有節點由單一機構統一維護時,此假定成立。在去中心化的區塊鏈網路中,節點由互不瞭解、互不信任的多方參與者共同提供和維護,受各種利益驅動,網路中的參與者存在欺騙、作惡的可能,因此Paxos和Raft演算法不能直接用於區塊鏈的共識。目前被區塊鏈專案廣泛採用的演算法有工作量證明(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共識演算法最初在比特幣系統中提出和應用。

比特幣系統在挖礦的過程中每10分鐘生成一個區塊。為了保證比特幣系統能穩定地發展並不斷產生區塊,比特幣的協議中人為地設定了這個10分鐘規律,這使得系統中的所有節點可以利用這10分鐘的時間,來完成接收,打包,見證的工作,同時將產生的交易在整個網路裡進行廣播。

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

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

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

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

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


PoW共識演算法存在的問題

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

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

3)業務處理效能低下:儘管投入了大量的能源支援系統的執行,但這些能源消耗絕大部份是用於工作量證明中的hash運算,處理交易業務的效能則非常低,例如比特幣每秒只能進行大約7筆交易;以太坊每秒10-20筆。

權益證明(Proof of Stake - PoS)

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

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


POS相對於PoW的好處包括:

1)PoW需要花費大量的電力資源,POS的好處首先當然是去除了大量的算力競爭;
2)不需要透過不停地發行新幣來激勵礦工參與算力競賽。避免了不可知的通脹風險;
3)提出了利用博弈論來避免區塊鏈網路產生中心化的大型參與者的新的方法。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中,併發布block;

2)stake_modifier是對前一個block中部分欄位hash後的值,加入這一項是為了防止使用者提前預知自己何時有權挖礦;

3)difficulty會根據近期的block產出時間動態調整,保證block產出時間間隔穩定;

4)由於每秒只需要完成和自己UTXO數量相等的hash計算,所以需要的算力較低;

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


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

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

2)出現了攢幣齡的現象,即關閉節點,直到age(UTXO)足夠大的時候再啟動節點挖礦,從而節省電力,這樣引起了線上節點數太少系統脆弱的問題;

3)可以攢夠足夠的幣齡後,保證自己有足夠的UTXO能夠連續生產block,從而發動double-spend攻擊。

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

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

2)最佳化了stake_modifier的計算邏輯,讓使用者提前預知自己有權挖礦時間的難度更大了。

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

1)依據權益結餘來選擇,會導致首富賬戶的權力更大,有可能支配記賬權;

2)PoS的一致問題:PoS的挖礦過程,與PoW的問題類似,是全網所有節點共同參與的,每一時刻都有成千上萬個節點同時去爭取產出下一個block,因此會時有發生區塊鏈分叉的問題。由於分叉的存在,block的產出時間間隔不能太短。各區塊鏈透過動態調整的挖礦難度,將block時間間隔穩定在自己期望的水平。出塊時間長,伴隨而來的則是交易確認時間長和交易處理效能低。

權益授權證明(DPoS)

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

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


DPoS專案案例

EOS前身石墨烯框架及bitshares(位元股)專案提出的DPOS方案,其步驟簡述如下:

1)持有token的使用者可以對候選的block producer進行投票;
2)得票最高的n個使用者被選為代表,在下一個週期中負責產出block,目前n=21;
3)打亂代表的順序後,各代表開始依次生產block。每個代表都有自己固定的時間區間,需要在自己的區間中完成block的生產釋出。目前這個區間是3秒,即在正常情況下每3秒產出一個block;
4)每個代表在生產block的時候,需要找當時唯一的最長鏈進行生產,不能在其他分支上進行生產。

透過上述方法,保證了較短的block生產時間,且因為給每個生產者設定了固定的時間區間,則block的產出不會因為某個候選節點的延遲而延遲。

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

DPoS共識演算法存在的問題

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

2)EOS的21個超級節點並不是21個不同實體,節點之間可能存在內在聯絡的共謀;

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

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


實用拜占庭容錯(PBFT)

PBFT演算法的結論是n>=3f+1, n是系統中的總節點數,f是允許出現故障的節點數。換句話說,如果這個系統允許出現f個故障,那麼這個系統必須包括n個節點,才能解決故障。這和上文口頭協議的結論一樣,或者這麼說,PBFT是最佳化了口頭協議機制的效率,但是結論並未改變。


PBFT演算法的步驟:

1)取一個副本作為主節點(圖中0),其他的副本作為備份;
2)使用者(圖中C)向主節點傳送訊息請求;
3)主節點透過廣播將請求傳送給其他節點(圖中1、2、3);
4)所有節點執行請求並將結果發回使用者端;
5)使用者端需要等待f+1個不同副本節點發回相同的結果,即可作為整個操作的最終結果。

PBFT專案案例

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

PBFT不僅具備強一致性的特性,而且提供了較高的共識效率,比較適合對一致性和效能要求較高的區塊鏈專案,但由於PBFT需要兩兩節點需要進行通訊,通訊量是O(n^2)(透過最佳化可以減少通訊量),在公有鏈這種全球性的大環境下,節點數量和網路環境不可控,無法達成這種巨大的通訊量。

不過對於聯盟鏈和私有鏈,節點數量並不是很多,採用PBFT效率更高結果也更好,因此PBFT在聯盟鏈和私有鏈的區塊鏈專案中使用較為廣泛。這也是Fabric專案採用PBFT演算法的原因。

PBFT共識演算法存在的問題

1)通訊量是O(n^2),不適用於節點數量和網路環境不可控的公有鏈專案;
2)PBFT是強一致性演算法,在可用性上作了讓步,當有1/3或以上記賬人停止工作後,系統將無法提供服務。

PoW + PoS

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

例如以太坊社羣提出的正在研發中的共識協議名為Casper,是一個覆蓋在已存在的以太坊PoW提議機制上的PoS,Casper融合了PoW和PoS兩種演算法。

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

Casper的應用邏輯存在於智慧合約的內部。要想在Casper中成為驗證者,必須要有ETH並且要將ETH儲存到Casper智慧合約中作為槓桿的權益。在Casper第一次迭代中區塊提議的機制會被保留:它依然使用Nakamoto PoW共識,礦工可以建立區塊。不過為了最終化區塊,Casper的PoS覆蓋掌握控制權,並且擁有自己的驗證者在PoW礦工之後進行投票。


更多區塊鏈資訊:http://www.qukuaiwang.com.cn/news

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;