歡迎光臨
每天分享高質量文章

從拜占庭將軍問題看:區塊鏈「 共識演算法 」

(點擊上方公號,快速關註我們)


作者:王奎,個人公號:不止思考

假如你是古代某個國家的將軍,你們國家除了你以外,還有另外9個將軍,每個將軍帶領著一支軍隊,總共10支軍隊,這10支軍隊在地域上分散駐扎。你們國家想要進攻一個強大的敵國,這個敵國也有一定的實力,足以抵禦你們5支軍隊的同時襲擊。因此你們10支軍隊必須要成一致意見,起碼要大部分軍隊達成一致,才可順利的消滅掉這個敵國。


而由於地域上特殊原因,你們這10支軍隊不能集合在一起單點進攻,必須在分開的狀態下同時包圍攻擊敵國。如果是單支軍隊單獨進攻的話是毫無勝算的,除非有至少有6支軍隊同時調遣一起襲擊才能攻下敵國。你們分散在敵國的四周,依靠通信兵相互通信來協商進攻意向和進攻時間。

此時困擾著你們10個將軍的問題是,你們沒有一個中心領導,10名將軍都是平等的,且你們當中可能會有叛徒,叛徒可能擅自變更進攻意向或者進攻時間,甚至是傳遞假的進攻訊息,在這種狀態下,你們10名將軍們能否找到一種分佈式的協作方式,來讓你們能夠遠程、準確無誤的協商,從而贏取戰鬥呢?

這就是著名的「拜占庭將軍問題」。

拜占庭將軍問題就是要解決去中心化的共識機制問題,而這個共識問題也是比特幣中區塊鏈網絡所需要解決的。

因為拜占庭將軍們是分散的,沒有一個中心的領導機構,因此他們在進攻敵方的時候必須事先對進攻地點和時間進行協商,達成共識。那麼在有限的時間內,要解決提案(進攻方案)的一致性且獲取大部分將軍的認可,才能解決拜占庭將軍問題。

在區塊鏈網絡中也是類似情況。

區塊鏈的分佈式網絡中可能會有多個人提出打包區塊的請求,並且其中還有可能是有偽造的區塊,那麼只能靠分佈式共識演算法來解決這個問題了。

我們知道區塊鏈的核心價值之一就是共識,這也是大家一直所追捧區塊鏈的特性之一。那今天我們就來重點來聊一聊區塊鏈是怎樣通過「共識機制」來解決上述問題的。

其實共識機制的概念並非是由區塊鏈興起才有的,它早在數學領域就是長期以來在研究和攻剋的方向,尤其是在計算機領域針對分佈式共識機制也已經有了一些知名的解決方案,取得了非常卓越的成就。

區塊鏈算是一個將「共識機制」充分應用的一個場景。

一、什麼是共識演算法?

共識演算法 顧名思義,就是通過演算法手段讓各參與方對某個確定的結果達成一致的方案。
在區塊鏈里,就是指在不可靠的網絡環境里,在不可信的各參與方中,尋找一個傳遞和驗證信息的可靠策略。

不過,這裡的可靠也是相對而言的,非法節點必須控制在一定的比例之內才能保證可靠性。
共識演算法有很多種,目前比特幣所採用的是:工作量證明的共識機制。

二、區塊鏈為什麼需要共識演算法?

拿比特幣舉例,在比特幣的區塊鏈網絡中,因為是去中心化的,每個節點都是平等的,每個節點都會有一個賬本、都可以記賬,那最終就會產生很多個不同的賬本。

但事實上我們是需要所有人都掌握同樣一個賬本,才能保證系統資料的一致性,系統才能有效運行。

那如何保證在一段時間內只有允許一個節點去生成合法賬本、保證大家的賬本是一致的(起碼大部分人的賬本是一致的),如何驗證合法的賬本、鑒別非法賬本呢?

這些問題是在去中心化的區塊鏈網絡中必須要解決的,不然誰都可以隨意篡改賬本內容,然後說自己的賬本才是合法的,這樣的話,比特幣系統就亂套了。

比特幣是怎麼解決這個問題的呢,它採用的是PoW(Proof of Work)的共識演算法。這個演算法不僅可以保證在一段時間內網絡中出現的提案(提出記賬請求)的個數是有限的,同時也放棄了強一致性的要求,改為最終一致性要求(即允許鏈中同一時刻有多個合法區塊,出現鏈路分叉,但最後會以工作量最大的那個鏈路,也就是最長的那條鏈為最終的合法鏈)

除了比特幣,其它一些代幣的區塊鏈網絡都是使用什麼樣的共識演算法呢?

三、共識演算法有哪些?

共識演算法比較多,有 PBFT(Practical Byzantine Fault Tolerance,實用拜占庭容錯演算法)、PoW(Proof of Work,工作量證明)、PoS(Proof of Stake,權益證明)、DPoS(Delegate Proof of Stake,委托權益證明)、Ripple(瑞波),還有 分佈式一致性演算法(Pasox、Raft) 等等,每種演算法的玩法都不一樣。

這裡重點來介紹一下區塊鏈中常用的幾種:

  1. PoW (Proof of Work,工作量證明)


比特幣和以太坊都是基於這種演算法來實現的。簡單來說,PoW 就是一份確認工作端做過一定量工作的證明。PoW 系統的主要特征是計算的不對稱性,工作端需要做一定難度的工作才能得出一個結果,而驗證方卻很容易通過結果來檢查工作端是不是做了相應的工作,哈哈,這就是俗話說的 完成工作很辛苦,檢查工作很容易。

在比特幣系統中,大約每10分鐘就開始一輪算力的競爭工作,大家將特定的字串+隨機nonce數進行SHA256運算,期望得到一個符合系統預期的值,如果算出來的結果不滿足預期,則不斷的調整nonce值,重新計算,一直到滿足預期值為止,所以要找到預期值還是比較難的,而且沒有捷徑可走,必須要不停的嘗試nonce值,會消耗巨大的計算量,這也就是所謂的挖礦(這裡為方便理解對工作原理介紹的比較粗略,更為具體的我會在另外一篇講區塊鏈哈希演算法的文章中介紹)。

如果某一個節點運氣好,計算的結果恰好滿足預期值,那麼這個節點就需要告訴全網的其它節點,讓其它節點來驗證它的工作是否正確,別人驗證起來運算量是非常簡單的,所以說PoW是一種計算力不對稱性的演算法。如果其它節點經過快速驗證沒有問題,那麼這個運氣好的節點就擁有了記賬權,可以將自己剛纔打包的區塊放到區塊鏈里。

PoW 的特點是:

  • 完全去中心化,節點自由進出

  • 只要網絡中非法節點的算力不超過50%,那麼這種驗證方法就是可靠的

  • 造成大量的計算資源的浪費(因為這種尋找隨機數的挖礦行為消耗GPU等算力但不產生價值)

所以PoW的優點和缺點都挺明顯的,尤其是算力空耗的問題在比特幣上經常被人詬病,因此以太坊的規劃標的是變更為PoS演算法。

  1. PoS  (Proof of Stake,權益證明)

PoS演算法解決了PoW的算力空耗的問題。POS叫權益證明,也可以稱為股權證明,它其實是一種要求各節點提供擁有一定數量虛擬幣證明的方式來競爭區塊鏈記賬權的共識機制。

在PoS樣式下,記賬權不再像PoW那樣由誰的算力大誰就有更高的概率來記賬,而是由誰的代幣多,誰就越有可能獲得記賬權。可以想象一下, PoW類似於多勞多得,PoS類似於有錢人多得。

單純靠代幣多少來分配記賬權,很有可能會導致記賬權的中心化,所以有些代幣系統在記賬權的競爭中,除了計算誰的代幣多以外,還會計算持有代幣的時間長短,例如點點幣。

雖然PoS很明顯的解決了算力空耗的問題,且縮短了共識的達成時間。但PoS演算法也可能會導致一些新的問題,比如,由於馬太效應,系統的決策權和收益會越來越集中到少數人手中,失去公正。另外,在PoS系統上容易受到「分叉攻擊」導致「雙重支付」等問題。

因此POS演算法也有了各種變化和升級,比如DPos演算法。

  1. DPoS (Delegate Proof of Stake,委托權益證明)

DPos演算法稱為 委托權益證明或股權委托證明。它相比較於PoW與PoS,更進一步的提高了區塊鏈的效率。

DPoS機制不需要網絡中的所有節點都參與區塊的創建和校驗,它會不定期的選出一小群節點,讓這小群節點去做區塊鏈的創建和校驗,這樣對整個網絡的資源消耗進一步減少了,也提高了區塊鏈的工作效率,例如EOS。

但這一小群節點是怎麼定出來的呢?其實是由大家投票選出來的,在DPoS系統下,每個token都是一個選票,充分利用了持股人的投票,以公平的方式達成共識,大家選出N個見證人(也就是N個礦池),這N個見證人權力平等,只有見證人才可以生成和管理區塊。另外,持股人可以隨時通過投票來更換這些見證人。

還有一些其它共識演算法就不在這裡一一展開了。在區塊鏈中,由於每個專案的場景不同,所以設計的架構和採用的共識演算法都不盡相同。主要還是從 去中心化、安全、性能 三要素中根據不同的應用場景,進行不同的組合。

【關於作者】


王奎:不止思考的技術人,一名駐扎在武漢互聯網的程式員老兵,我有一個公眾號 bzsikao 平時寫一些工作的心得和技術文章。

【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】
《不要自稱是程式員,我十多年的 IT 職場總結》:http://blog.jobbole.com/94148/


③ 最後請附上您的個人簡介哈~

覺得本文有幫助?請分享給更多人

關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂