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