iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 6
0
Blockchain

匚口口口土甶儿厶金連,這技術拼圖你了解了嗎?系列 第 6

DAY06 區塊鏈的起源-拜占庭容錯

今天一樣繼續來說區塊鏈的起源,探討「拜占庭容錯」 PBFT(Practical Byzantine Fault Tolerance)。拜占庭容錯是一種基於嚴格數據證明的算法,至少需要經過三個階段的信息交換和通過局部共識達至最終的一致性結果。
簡單來說,系統中有可信節點超過三分之二,有問題的節點不超過三分之一時,不管這些節點如何散播與傳達有問題的信息時,可信節點之間都一定能達到一致共識;

其實就是每一個收到訊息的節點不斷的重複與彼此雙雙交換訊息,互相驗證,讓其中可信的節點之間能確認出正確的訊息,找出少數那些有問題的節點。以拜占庭帝國的例子來說,就是將軍們不斷重複彼此確認訊息,來找出間諜,以及直到確認接受到正確的命令。

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

只看滿滿的文字,實在還是很難理解拜占庭容錯的運篹方法,我們就來用圖表一段段解釋,<區塊鏈 Block chain – 共識機制之實用拜占庭容錯 PBFT>這篇文章對「拜占庭容錯」的步驟猜拆解非常詳細。
對於拜占庭將軍問題,PBFT 算法至少通過三個階段達成一致性的協議:<請求 Request、預準備 Pre-Prepare、回覆 Reply >,根據不同的協議設計,亦可能同時包含<準備 Prepare、確認 Commit>

A. 首先背景套用上面拜占庭將軍的故事,同時 PBFT算法最少要求有4個參與者
B. C:元帥、0:司令、1:將軍1號、2:將軍2號、3:將軍3號。
C. 勝利條件:2/3以上的軍隊都共同發起"進攻"。

拜占庭容錯運作過程分解
拜占庭容錯運作過程分解 圖片來源:https://www.samsonhoi.com/570/blockchain-pbft

五大程序:

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

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

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

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

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

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

參考資料:
。 區塊鏈 Blockchain 共識機制之實用拜占庭容錯PBFT / https://www.samsonhoi.com/570/blockchain-pbft / 2018年07月30日
。 Blockchain / https://en.wikipedia.org/wiki/Blockchain
。 如何通俗的理解IBM區塊鏈技術HyperLedger/fabric中的共識演算法PBFT(拜占庭容錯)? / https://www.zhihu.com/question/52254063/answer/148246972 / 2017年02月24日
。 Byzantine fault / https://en.wikipedia.org/wiki/Byzantinefault
。 區塊聯革命/中介消失的未來,改寫商業規則,興起社會變革,經濟大洗牌。(劉勇著) / 2017年01月出版


上一篇
DAY05 區塊鏈的起源-拜占庭將軍問題
下一篇
DAY07 區塊鏈的起源-拜占庭將軍問題-在通信領域的意義
系列文
匚口口口土甶儿厶金連,這技術拼圖你了解了嗎?30

尚未有邦友留言

立即登入留言