資訊專欄INFORMATION COLUMN
摘要：拜占庭故障是最嚴重最難處理的。在飛機發動機系統核電站和幾乎所有行為取決于大量傳感器結果的系統都需要拜占庭容錯。前面提到的算法，只要叛徒的數量不超過將軍的三分之一，就是拜占庭容錯。
區塊鏈本質上是去中心化的系統，由不同的成員計算機組成，這些成員的行為取決于它們的動機和它們可以獲得的信息。
每當一個新的交易被廣播到網絡中時，節點就可以選擇將該交易包含在它們的帳簿副本中，或者忽略它。當組成網絡的大多數成員統一意見時，達到了共識。
分布式計算和多代理系統中的一個基本問題是，在存在許多出錯的進程的情況下，實現整個系統的可靠性。這通常需要進程來在計算過程中需要的一些數據值上保持一致性。
這些進程被描述為共識。
當成員決定不遵守規則和篡改他的帳簿狀態時會發生什么？
當這些成員是網絡的一大部分但不是多數時會發生什么？
為了創建一個安全的共識協議，它必須是容錯的。
首先，我們會簡單討論一下不可解的兩個將軍問題（Two Generals Problem）。然后，我們會引申到拜占庭將軍問題和討論在分布式的去中心化系統中的拜占庭容錯。最后，我們會討論這些與區塊鏈空間如何相關。
這個問題（1975首次發行，1978年被命名）描述了兩個將軍在攻擊同一個敵人的場景。將軍1號被認為是領導，而另一個被認為是跟隨者。每個將軍的軍隊都無法僅靠自己的力量成功打敗敵軍，所以他們需要合作并同一時間發起攻擊。這看起來是一個簡單的情況，但有一點要注意：
為了兩軍的溝通和決定作戰時間，將軍1號必須要派遣一個信使穿過敵人的營地去把攻擊時間告訴將軍2號。但是，信使可能會被敵人抓住因而信息無法傳到友軍。那會導致將軍1號發起攻擊時，將軍2號和他的軍隊還呆在原地。
即使第一條信息傳到了，將軍2號也需要確認（ACK，注意和TCP三次握手的相似之處）他收到了信息，所以他要派遣一個信使回去，因此重復上一個信使可能被抓的情況。這會延伸到無限的ACK，兩位將軍將無法達成一致。
沒有任何辦法可以保證第二個要求，那就是每個將軍都要確保對方同意了攻擊計劃。兩個將軍都總會懷疑他們最后的信使是否能到達。
(因為信使無法到達的可能性總是大于0，所以將軍們永遠無法以100%的自信達成共識。)
兩個將軍問題已被證實無解。
于1982年由Lamport、Shostak和Pease著名描述，是一個帶反轉的廣義版本的兩個將軍問題。它描繪了同一個場景，但兩個以上的將軍需要對攻打他們共同敵人的時間作出同意。增加的一層復雜性就是，其中一個或幾個將軍有可能是叛徒，意味著他們可以對他們的選擇撒謊（比如他們同意在0900發起攻擊但實際上他們不）。
兩個將軍問題中領導者－跟隨者的關系變成了指揮官－中尉的組合。為了在這里達成共識，指揮官和每個中尉必須就同一個決定達成一致（為了簡單，只有攻擊或撤退）。
除了IC2.之外，有趣的事，如果指揮官是叛徒，還是必須達成共識。結果，所有的中尉成為了多數票。
在這種情況下達成共識的算法是基于一個中尉所觀察到的大多數決策的價值。
定理：對于任意m，如果有多于3m的將軍和至多m個叛徒，算法OM(m)達到共識。
這說明只要2/3的成員是誠實的，算法就能達到共識。如果叛徒多于1/3，無法達到共識，這些軍隊無法協調他們的攻擊，敵軍勝利。
(m = 0 -> 沒有叛徒，每個中尉都服從｜m > 0 -> 每個中尉的最終選擇來自于大多數中尉的選擇)
一個從中尉2號角度來看的示意圖應該看得更清楚?—?— C是指揮官，L{i}是中尉i號：
(OM(1)：中尉3號是叛徒－從L2角度來看)
步驟：
指揮官派v去找所有中尉
L1派v去找L2｜L3派x去找L2
L2 <- 大多數(v,v,x) == v
最后的決定是來自L1、L2、L3的大多數票，因此達成了共識。
要記得，重要的是大多數中尉要選同一個決策，哪一個并不重要。
讓我們來檢驗指揮官是叛徒的情況：
(OM(1): 指揮官是叛徒)
步驟：
指揮官派x、y、z去分別找L1、L2、L3
L1派x去找L2、L3｜L2派y去找L1、L3｜L3派z去找L1、L2
L1 <- 大多數(x,y,z)｜L2 <- 大多數(x,y,z)｜L3 <- 大多數(x,y,z)
他們的數值都一樣所以達成了共識。這里花點時間來想一下，即使x,y,z各不相同，所有三個中尉的大多數(x,y,z)的值是相同的。在x,y,z全部不一樣的情況時，我們可以假設他們采取默認選項撤退。
要是想了解一個更實用的方法和一個更復雜的7個將軍和2個叛徒的例子，我建議你讀這篇文章。
拜占庭容錯是一個定義容許屬于拜占庭將軍問題失敗類別的系統的特性。拜占庭故障(Byzantine Failure)是失效模式中最困難級別的。這意味著沒有任何限制，也不會假設節點可以具有的行為類型（例如，一個節點可以生成任何類型的任意數據時假裝成一個誠實的成員）。
拜占庭故障是最嚴重最難處理的。在飛機發動機系統、核電站和幾乎所有行為取決于大量傳感器結果的系統都需要拜占庭容錯。就連SpaceX都曾考慮過它為系統的潛在需求。
前面提到的算法，只要叛徒的數量不超過將軍的三分之一，就是拜占庭容錯。其他變形的存在使得解決問題更容易，包括使用數字簽名或通過在網絡中的對等體之間施加通信限制。
區塊鏈是不受中央權威管制的去中心化帳簿們。由于存儲在這些帳簿中的價值，不良成員有巨大的經濟動機去嘗試造成故障。所以，拜占庭容錯，也就是拜占庭將軍問題的解決方案是區塊鏈非常需要的。
在沒有BFT的情況下，同行可以傳輸和發布虛假交易，從而有效地消除了區塊鏈的可靠性。更糟糕的是，沒有中央權威來接管和修復損害。
發明比特幣時的一個重大突破就是利用“工作量證明”(Proof-of-Work)作為拜占庭將軍問題的概率解決方案。想了解更多，請參考Satoshi Nakamoto在這封電子郵件中的深入描述。
在這篇文章中，我們討論了在分布式系統中共識的一些基本概念。
在下一篇文章中，我們將討論并比較一些在區塊鏈中用于實現拜占庭容錯的算法。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/24009.html
摘要：課程概述本課程適合希望開發自己的專有區塊鏈的語言工程師，課程內容如下第一章課程簡介簡單介紹的定位特點以及對于開發者而言與以太坊的區別。課程地址區塊鏈開發詳解 簡介 tendermint是一個開源的完整的區塊鏈實現，可以用于公鏈或聯盟鏈，其官方定位 是面向開發者的區塊鏈共識引擎： showImg(https://segmentfault.com/img/remote/1460000016...
摘要：在這種狀態下，拜占庭將軍們才能保證有多于支軍隊在同一時間一起發起進攻，從而贏取戰斗拜占庭將軍問題中并不去考慮通信兵是否會被截獲或無法傳達信息等問題，即消息傳遞的信道絕無問題。共識算法的核心就是解決拜占庭將軍問題分布式網絡一致性問題。 本文首發于深入淺出區塊鏈社區原文鏈接:什么是拜占庭將軍問題原文已更新，請讀者前往原文閱讀 接觸區塊鏈的同學，多少都聽說過拜占庭將軍問題，經常看到或聽到某某...
摘要：區塊鏈系統首先是一個分布式系統，分布式系統的核心問題包括一致性共識一致性問題一致性問題是分布式領域最為基礎也是最重要的問題。算法與算法問題是指分布式系統中存在故障，但不存在惡意節點的場景即可能消息丟失或重復，但無錯誤消息下的共識達成問題。 區塊鏈系統首先是一個分布式系統，分布式系統的核心問題包括一致性、共識 一致性問題 一致性問題是分布式領域最為基礎也是最重要的問題。如果分布式系統能實...
閱讀 664·2021-11-23 09:51
閱讀 3305·2021-10-11 10:58
閱讀 15465·2021-09-29 09:47
閱讀 3563·2021-09-01 11:42
閱讀 1293·2019-08-29 16:43
閱讀 1839·2019-08-29 15:37
閱讀 2112·2019-08-29 12:56
閱讀 1729·2019-08-28 18:21
