資訊專欄INFORMATION COLUMN
摘要：在這種狀態(tài)下，拜占庭將軍們才能保證有多于支軍隊(duì)在同一時(shí)間一起發(fā)起進(jìn)攻，從而贏取戰(zhàn)斗拜占庭將軍問題中并不去考慮通信兵是否會(huì)被截獲或無法傳達(dá)信息等問題，即消息傳遞的信道絕無問題。共識(shí)算法的核心就是解決拜占庭將軍問題分布式網(wǎng)絡(luò)一致性問題。
本文首發(fā)于深入淺出區(qū)塊鏈社區(qū)
原文鏈接:什么是拜占庭將軍問題原文已更新，請(qǐng)讀者前往原文閱讀
接觸區(qū)塊鏈的同學(xué)，多少都聽說過拜占庭將軍問題，經(jīng)?？吹交蚵牭侥衬硡^(qū)塊鏈?zhǔn)褂媚衬乘惴ń鉀Q了拜占庭將軍問題，那么究竟什么是拜占庭將軍問題呢?
什么是拜占庭將軍問題也被稱為“拜占庭容錯(cuò)”、“拜占庭將軍問題”。
拜占庭將軍問題是Leslie Lamport（2013年的圖靈講得?。┯脕頌槊枋?strong>分布式系統(tǒng)一致性問題（Distributed Consensus）在論文中抽象出來一個(gè)著名的例子。
這個(gè)例子大意是這樣的：
拜占庭帝國(guó)想要進(jìn)攻一個(gè)強(qiáng)大的敵人，為此派出了10支軍隊(duì)去包圍這個(gè)敵人。這個(gè)敵人雖不比拜占庭帝國(guó)，但也足以抵御5支常規(guī)拜占庭軍隊(duì)的同時(shí)襲擊。這10支軍隊(duì)在分開的包圍狀態(tài)下同時(shí)攻擊。他們?nèi)我恢к婈?duì)多帶帶進(jìn)攻都毫無勝算，除非有至少6支軍隊(duì)（一半以上）同時(shí)襲擊才能攻下敵國(guó)。他們分散在敵國(guó)的四周，依靠通信兵騎馬相互通信來協(xié)商進(jìn)攻意向及進(jìn)攻時(shí)間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進(jìn)攻意向或者進(jìn)攻時(shí)間。在這種狀態(tài)下，拜占庭將軍們才能保證有多于6支軍隊(duì)在同一時(shí)間一起發(fā)起進(jìn)攻，從而贏取戰(zhàn)斗？
拜占庭將軍問題中并不去考慮通信兵是否會(huì)被截獲或無法傳達(dá)信息等問題，即消息傳遞的信道絕無問題。Lamport已經(jīng)證明了在消息可能丟失的不可靠信道上試圖通過消息傳遞的方式達(dá)到一致性是不可能的。所以，在研究拜占庭將軍問題的時(shí)候，已經(jīng)假定了信道是沒有問題的.問題分析
單從上面的說明可能無法理解這個(gè)問題的復(fù)雜性，我們來簡(jiǎn)單分析一下：
先看在沒有叛徒情況下，假如一個(gè)將軍A提一個(gè)進(jìn)攻提議（如：明日下午1點(diǎn)進(jìn)攻，你愿意加入嗎？）由通信兵通信分別告訴其他的將軍，如果幸運(yùn)中的幸運(yùn)，他收到了其他6位將軍以上的同意，發(fā)起進(jìn)攻。如果不幸，其他的將軍也在此時(shí)發(fā)出不同的進(jìn)攻提議（如：明日下午2點(diǎn)、3點(diǎn)進(jìn)攻，你愿意加入嗎？），由于時(shí)間上的差異，不同的將軍收到（并認(rèn)可）的進(jìn)攻提議可能是不一樣的，這是可能出現(xiàn)A提議有3個(gè)支持者，B提議有4個(gè)支持者，C提議有2個(gè)支持者等等。
再加一點(diǎn)復(fù)雜性，在有叛徒情況下，一個(gè)叛徒會(huì)向不同的將軍發(fā)出不同的進(jìn)攻提議（通知A明日下午1點(diǎn)進(jìn)攻， 通知B明日下午2點(diǎn)進(jìn)攻等等），一個(gè)叛徒也會(huì)可能同意多個(gè)進(jìn)攻提議（即同意下午1點(diǎn)進(jìn)攻又同意下午2點(diǎn)進(jìn)攻）。
叛徒發(fā)送前后不一致的進(jìn)攻提議，被稱為“拜占庭錯(cuò)誤”，而能夠處理拜占庭錯(cuò)誤的這種容錯(cuò)性稱為「Byzantine fault tolerance」，簡(jiǎn)稱為BFT。
相信大家已經(jīng)可以明白這個(gè)問題的復(fù)雜性了。
中本聰?shù)慕鉀Q方案在出現(xiàn)比特幣之前，解決分布式系統(tǒng)一致性問題主要是Lamport提出的Paxos算法或其衍生算法。Paxos類算法僅適用于中心化的分布式系統(tǒng)，這樣的系統(tǒng)的沒有不誠(chéng)實(shí)的節(jié)點(diǎn)（不會(huì)發(fā)送虛假錯(cuò)誤消息，但允許出現(xiàn)網(wǎng)絡(luò)不通或宕機(jī)出現(xiàn)的消息延遲）。
中本聰在比特幣中創(chuàng)造性的引入了“工作量證明（POW : Proof of Work）”來解決這個(gè)問題，有興趣可進(jìn)一步閱讀工作量證明。
通過工作量證明就增加了發(fā)送信息的成本，降低節(jié)點(diǎn)發(fā)送消息速率，這樣就以保證在一個(gè)時(shí)間只有一個(gè)節(jié)點(diǎn)(或是很少)在進(jìn)行廣播，同時(shí)在廣播時(shí)會(huì)附上自己的簽名。
這個(gè)過程就像一位將軍A在向其他的將軍（B、C、D...）發(fā)起一個(gè)進(jìn)攻提議一樣，將軍B、C、D...看到將軍A簽過名的進(jìn)攻提議書，如果是誠(chéng)實(shí)的將軍就會(huì)立刻同意進(jìn)攻提議，而不會(huì)發(fā)起自己新的進(jìn)攻提議。
以上就是比特幣網(wǎng)絡(luò)中是單個(gè)區(qū)塊（賬本）達(dá)成共識(shí)的方法（取得一致性）。
理解了單個(gè)區(qū)塊取得一致性的方法，那么整個(gè)區(qū)塊鏈（總賬本）如果達(dá)成一致也好理解。
我們稍微把將軍問題改一下：假設(shè)攻下一個(gè)城堡需要多次的進(jìn)攻，每次進(jìn)攻的提議必須基于之前最多次數(shù)的勝利進(jìn)攻下提出的（只有這樣敵方已有損失最大，我方進(jìn)攻勝利的可能性就更大），這樣約定之后，將軍A在收到進(jìn)攻提議時(shí)，就會(huì)檢查一下這個(gè)提議是不是基于最多的勝利提出的，如果不是（基于最多的勝利）將軍A就不會(huì)同意這樣的提議，如果是的，將軍A就會(huì)把這次提議記下來。
這就是比特幣網(wǎng)絡(luò)最長(zhǎng)鏈選擇。
經(jīng)濟(jì)學(xué)分析工作量證明其實(shí)相當(dāng)于提高了做叛徒（發(fā)布虛假區(qū)塊）的成本，在工作量證明下，只有第一個(gè)完成證明的節(jié)點(diǎn)才能廣播區(qū)塊，競(jìng)爭(zhēng)難度非常大，需要很高的算力，如果不成功其算力就白白的耗費(fèi)了（算力是需要成本的），如果有這樣的算力作為誠(chéng)實(shí)的節(jié)點(diǎn)，同樣也可以獲得很大的收益（這就是礦工所作的工作），這也實(shí)際就不會(huì)有做叛徒的動(dòng)機(jī)，整個(gè)系統(tǒng)也因此而更穩(wěn)定。
很多人批評(píng)工作量證明造成巨大的電力浪費(fèi)，促使人們?nèi)ヌ剿餍碌慕鉀Q一致性（共識(shí)）問題的機(jī)制：權(quán)益證明機(jī)制（POS: Proof of Stake）是一個(gè)代表。在拜占庭將軍問題的角度來看，它同樣提高了做叛徒的成本，因?yàn)橘~戶需要首先持有大量余額才能有更多的幾率廣播區(qū)塊，POS不是本文重點(diǎn)，以后在講。
共識(shí)算法的核心就是解決拜占庭將軍問題（分布式網(wǎng)絡(luò)一致性問題）。擴(kuò)展閱讀
The Byzantine Generals Problem
深入淺出區(qū)塊鏈 - 系統(tǒng)學(xué)習(xí)區(qū)塊鏈，打造最好的區(qū)塊鏈技術(shù)博客。
如果想與我有更密切的交流可以選擇加入我的知識(shí)星球（星球成員可加入微信技術(shù)交流群）
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/23966.html
摘要：拜占庭故障是最嚴(yán)重最難處理的。在飛機(jī)發(fā)動(dòng)機(jī)系統(tǒng)核電站和幾乎所有行為取決于大量傳感器結(jié)果的系統(tǒng)都需要拜占庭容錯(cuò)。前面提到的算法，只要叛徒的數(shù)量不超過將軍的三分之一，就是拜占庭容錯(cuò)。 showImg(https://segmentfault.com/img/bV6WtE?w=1080&h=870);區(qū)塊鏈本質(zhì)上是去中心化的系統(tǒng)，由不同的成員計(jì)算機(jī)組成，這些成員的行為取決于它們的動(dòng)機(jī)和它們可...
摘要：劉宇昆，英文名，是一名美籍華裔科幻作家。他最令國(guó)人熟知的成就，就是成功翻譯了劉慈欣的三體系列小說的英文版，讓大劉在國(guó)際科幻文學(xué)領(lǐng)域聲名鵲起。最近，月出版的科幻選集就收錄了他的新作，以及由他翻譯的劉慈欣作品黃金原野。 劉宇昆，英文名Ken Liu，是一名美籍華裔科幻作家。他最令國(guó)人熟知的成就，就是成功翻譯了劉慈欣的「三體」系列小說的英文版，讓大劉在國(guó)際科幻文學(xué)領(lǐng)域聲名鵲起。 這次他帶著新...
摘要：劉宇昆，英文名，是一名美籍華裔科幻作家。他最令國(guó)人熟知的成就，就是成功翻譯了劉慈欣的三體系列小說的英文版，讓大劉在國(guó)際科幻文學(xué)領(lǐng)域聲名鵲起。最近，月出版的科幻選集就收錄了他的新作，以及由他翻譯的劉慈欣作品黃金原野。 劉宇昆，英文名Ken Liu，是一名美籍華裔科幻作家。他最令國(guó)人熟知的成就，就是成功翻譯了劉慈欣的「三體」系列小說的英文版，讓大劉在國(guó)際科幻文學(xué)領(lǐng)域聲名鵲起。 這次他帶著新...
摘要：同時(shí)利用工作量證明等共識(shí)機(jī)制解決了雙重花費(fèi)和拜占庭將軍問題。比如拜占庭將軍問題就是一個(gè)典型的協(xié)作問題。拜占庭帝國(guó)想要進(jìn)攻一個(gè)強(qiáng)大的敵人，為此派出了支軍隊(duì)去包圍這個(gè)敵人。這個(gè)敵人雖不比拜占庭帝國(guó)，但也足以抵御支常規(guī)拜占庭軍隊(duì)的同時(shí)襲擊。 隨著比特幣的起起伏伏，區(qū)塊鏈技術(shù)也越來越受到關(guān)注，成為當(dāng)下和人工智能一樣風(fēng)靡的領(lǐng)域，也有了除了比特幣之外的應(yīng)用嘗試。不過明白區(qū)塊鏈技術(shù)底層原理的同學(xué)應(yīng)該...
摘要：區(qū)塊鏈系統(tǒng)首先是一個(gè)分布式系統(tǒng)，分布式系統(tǒng)的核心問題包括一致性共識(shí)一致性問題一致性問題是分布式領(lǐng)域最為基礎(chǔ)也是最重要的問題。算法與算法問題是指分布式系統(tǒng)中存在故障，但不存在惡意節(jié)點(diǎn)的場(chǎng)景即可能消息丟失或重復(fù)，但無錯(cuò)誤消息下的共識(shí)達(dá)成問題。 區(qū)塊鏈系統(tǒng)首先是一個(gè)分布式系統(tǒng)，分布式系統(tǒng)的核心問題包括一致性、共識(shí) 一致性問題 一致性問題是分布式領(lǐng)域最為基礎(chǔ)也是最重要的問題。如果分布式系統(tǒng)能實(shí)...
閱讀 2332·2023-04-26 01:50
閱讀 765·2021-09-22 15:20
閱讀 2669·2019-08-30 15:53
閱讀 1661·2019-08-30 12:49
閱讀 1766·2019-08-26 14:05
閱讀 2783·2019-08-26 11:42
閱讀 2397·2019-08-26 10:40
閱讀 2668·2019-08-26 10:38
