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