區塊鏈 Blockchain – 共識機制之實用拜占庭容錯 PBFT

/ 2 評 / 4

區塊鏈技術中,其中最重要的一部份-共識機制,在早前介紹過的 PoW 工作量證明、PoS 權益證明、DPoS 委託權益證明,而為何先介紹這些共識機制,其實有原因的。

因為區塊鏈可大致分為公有鏈、聯盟鏈(許可鏈)、私有鏈。早前提及這幾個共識機制都是相對適用於公有鏈,需要透過某種"證明",從而使大家達成一致的信任,而且利用Token(或稱為發行某種虛擬貨幣)去激勵礦工們努力挖礦,為公有鏈上交易數據打包出塊,賺取 Token,這是公有鏈的一些基本條件激勵機制和共識機制,但這些共識機制都其各自的問題存在,最大的問題是效率;而有人會問,如果系統的設計並不需要發 Token(發幣)以及鏈上的各個節點都是可信的,加上需要高效率地出塊,那麼使用上述幾種共識機制可能就不太合適了。

然而,傳統的共識機制中的 拜占庭容錯 PBFT、RAFT、PAXOS 等就成為了聯盟鏈(許可鏈)及私有鏈中相對適用的共識機制選項。

這次不同的是,在看定義和後面的解釋時,先看一下歷史和故事。

歷史

1982年,Leslie Lamport 提出拜占庭將軍問題(Byzantine Generals Problem),主要是用來解釋一致性問題的一個虛構模型。

這個故事起源於古代東羅馬帝國的帝都,一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題,將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性後果,因此各位將軍必須通過投票來達成一致策略,即所有軍隊一起進攻或所有軍隊一起撤離。

因為各位將軍分處城市不同方向,他們只能通過信使互相聯繫。在投票過程中每位將軍都將自己投票給進攻還是撤退的資訊通過信使分別通知其他所有將軍,這樣一來每位將軍根據自己的投票和其他所有將軍送來的資訊就可以知道共同的投票結果而決定行動策略。不過由於這些將軍中可能存在叛徒,而這些叛徒又努力地嘗試向不同將軍發送不同的消息,擾亂大家達成一致的決定。

而拜占庭將軍問題主要就是就這種情況下,如何令其餘忠心的將軍們能達成一致的決定。但同時,拜占庭將軍算法的複雜度也隨將軍(節點)數目的增加而呈指數級增加。

1999年,Miguel CastroBarbara Liskov2008年圖靈獎得主)在操作系統設計與實現國際會議(OSDI99)上提出了實用拜占庭容錯算法(PBFT),旨在為了解決原始拜占庭容錯算法效率不高的問題,並將算法的複雜度大大降低,令到拜占庭容錯算法在實際系統中能夠得以應用,能提供高效能的運算,使得系統可以每秒處理上千請求。

定義(概念)

實用拜占庭容錯 PBFT(Practical Byzantine Fault Tolerance),是一種基於嚴格數據證明的算法,至少需要經過三個階段的信息交換和通過局部共識達至最終的一致性結果。

核心的思路就是,只要系統中有問題的節點不超過 1/3 時,不管這些節點如何廣播有問題的信息,可信節點之間都一定能達到一致共識;

簡單來說,PBFT 實際上是對於每一個收到信息的節點,都會廣播至其他人,就是說不斷重複進行信息交換,相互驗證,讓可信的節點之間能夠確認正確的信息,識別出有問題的節點。

所以一個能夠保證達到一致共識的拜占庭系統節點數至少為4個,容許出現1個壞的節點。

亦即 N ≥ 3F + 1N為節點總數,F為有問題的節點總數)。

對於拜占庭將軍問題,PBFT 算法至少通過三個階段達成一致性的協議:

請求 Request、預準備 Pre-Prepare、回覆 Reply 

根據不同的協議設計,亦可能同時包含

準備 Prepare、確認 Commit

運作流程

以上這張圖看起來好像有點亂,不要緊,舉個例子解釋一下:

首先背景套用上面拜占庭將軍的故事,同時 PBFT算法最少要求有4個參與者,

那就以 C代表元帥、0代表司令、1代表1號將軍、2代表2號將軍、3代表3號將軍。

而勝利條件就是大部份(2/3)的軍隊都共同發起"進攻"。

1. 元帥命令司令"進攻"C 發送"請求"到 0);

2. 司令收到"進攻"命令後,分別傳遞給所有的將軍(0 發送"預準備"到123

3. 1號將軍收到由司令和2號將軍的"進攻"通知,但遲遲沒有收到3號將軍的回應,就將3號將軍忽略,並認為"進攻"是正確的,就下令"進攻"。並把"進攻"命令傳遞給其餘將軍(1收到02"準備",但並沒有收到31 發送"準備"給2、3,發送 "確認" 0);

2號將軍收到由司令和1號將軍的"進攻"通知,但遲遲沒有收到3號將軍的回應,就將3號將軍忽略,並認為"進攻"是正確的,就下令"進攻"。並把"進攻"命令傳遞給其餘將軍(2收到01"準備",但並沒有收到32 發送"準備"130,發送 "確認" 0);

4. 3號將軍收到司令、1號將軍、2號將軍的"進攻"通知,這次不一樣的是,3號將軍沒有把"進攻"要求傳遞給其他將軍,而是害怕得臨陣逃跑了,(3並沒有發送"準備"給0、12,而且沒有發送 "確認" 0);

5. 最後,所有的將軍親自向元帥匯報執行的情況(司令、1號將軍、2號將軍),而3號將軍並沒有回覆,所以將其視為逃跑或陣亡了,也就不理會他的結果,元帥也就認為大部份軍隊都"進攻",而且勝利了,不過同時亦發現3號將軍有問題。

在以上這個過程,如在 N ≥ 3F + 1 的情況下,N為節點總數,F為有問題的節點總數。即使其中一位將軍逃跑了,沒執行"進攻",但最後仍取得勝利,但對國家造成危害(其中一個節點失效對系統造成的危害),亦會得知哪位將軍有問題,而在 PBFT 的共識機制下,雖然出現有問題的節點,但這是容許的,不影響最終一致性的結果,這就是所謂 PBFT 算法的流程。

接下來我們可以來嘗試枚舉一下,按照 N ≥ 3F + 1 這條公式下,用不同的數據會得到怎樣的結果:

如此類推,也就知道為何PBFT 能夠保證至少有 3F+1 節點工作時,不管這些節點如何廣播有問題的信息,可信節點之間都一定能達到一致共識。

市場上的應用

在目前市場上,大部份聯盟鏈(許可鏈)及私有鏈都有使用 PBFT 作為系統的共識機制,比較有名的就是由IBM創建的Hyperledger Fabric。

安全性

PBFT中,只要有問題的節點不超過 1/3 時,不管這些節點如何廣播有問題的信息,可信節點之間都一定能達到一致共識;不過如果當有問題的節點超過 1/3 時,就無法保證達到一致共識。

所以一個能夠保證達到一致共識的拜占庭系統節點數至少為4個,容許出現1個壞的節點。亦即 N ≥ 3F + 1N為節點總數,F為有問題的節點總數)。

優缺點

優點

  1. 具備容錯性

能夠容納接近1/3的錯誤節點誤差,能夠在無效節點數量不超過 (N-1)/3 的情況下,保證安全性和活躍性。

2. 不用靠發幣維持系統運作

由於 PBFT 中各參與者都是已提前確認及相對可信的,所以系統出塊、安全性、穩定都共同保證。

3. 共識效率佳

可以滿足較高頻率的交易量,各節點達成共識的延時大約為25秒鐘,一般在商用上的實時處理基本適用。

缺點

  1. 封閉性

系統中的各節點數目需要提前確定並互相連接,並且不能動態加入,並且因為複雜的 View Change 算法所造成的開銷,將會令到節點數目有局限,連接上百個節點已經吃力,所以在公有鏈上使用PBFT的可能性基本為零。

2. 系統穩定性

當有 1/3 以上的節點停止工作後,系統將無法提供服務;

3. 高性能開銷

時間複雜度為 O(N^2)

總結

眾所周知,區塊鏈是一個分佈式賬本網絡,網絡內所有的節點都透過P2P的網絡連接,所有的交易數據都透過廣播的方式發送,而在這個網絡中,由於節點都是比較彈性及不可控的,比如可以隨時連接或斷開網絡,有惡意節點加入,所有在成功出塊前,所有的交易數據都會有機會出現延遲、被惡意修改、數據不完整、交易的順序不同等多個可能性。而為了解決這些問題,區塊鏈中共識機制的重要性就不言而喻,PBFT 則為其中一種,而區塊鏈中的三種類型:公有鏈、聯盟鏈(許可鏈)、私有鏈,亦因為各自性質不同,所採用的共識機制亦有所不同,又因 PBFT的特性,能夠在失效節點數量不超過 (N-1)/3 的情況下,保證安全性和活躍性,解決公有鏈上為了解決一致性問題從而降低交易效率的問題,所以都被認為較適用於聯盟鏈(許可鏈)及私有鏈,但正如早前在分析各種共識機制一樣,各個共識機制都有其各自的優缺點,PBFT並不是最優的共識機制。選擇共識機制應該根據實用應用的場景而定,私有鏈可以使用PaxosRaft,聯盟鏈(許可鏈)可以使用PBFT,公有鏈則可以使用PoWPoS等。

由於PBFT的特性,鏈內所有節點數目需要提前確定並互相連接,相互之間都是被認為是可信的節點,並且不能夠動態加入,所以既然如此,可以思考一下,是否用傳統的中心化系統就已經能夠解決業務上的要求,而不用為區塊鏈而區塊鏈?

根據系統內各參與方的可信任程度、實際應用場景選擇,才是真正最適合系統的"共識機制"

參考文章

拜占庭問題與算法

如何通俗的理解IBM區塊鏈技術HyperLedger/fabric中的共識算法PBFT(拜占庭容錯)

拜占庭將軍問題 - 維基百科

“區塊鏈 Blockchain – 共識機制之實用拜占庭容錯 PBFT” 有 2 則迴響

  1. Richard 說:

    很讚的文章。

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *