? ? ? ? ? 古老的“拜占庭將軍問題” 02
接上篇
拜占庭將軍問題”并非如傳說中那樣颅眶，源于公元5世紀(jì)的東羅馬戰(zhàn)場寥院，而是產(chǎn)生于1982年一位美國計算機(jī)科學(xué)家的頭腦當(dāng)中掰盘。
因此欠橘，我們不會使用任何1982年之前的案例來描述這個問題在古老年代的意義矩肩，因?yàn)樵偻白匪荩⑽凑嬲嘈?yán)肅地被提出并加以審視黍檩。 在原始的戰(zhàn)爭年代，將軍與將軍始锚、將軍與下屬間只能采用原始的方式——“出行靠走刽酱，通訊靠吼”的口頭傳輸。這對應(yīng)蘭伯特論文提出算法中的第一部分的口頭消息算法瞧捌，簡稱OM（m）算法棵里。
這種情形，真?zhèn)魏茈y辨別姐呐，只有當(dāng)叛徒的總數(shù)不超過將軍總數(shù)的1/3殿怜，成為一個特殊的“拜占庭容錯系統(tǒng)”時，才能在很大的消息驗(yàn)證代價后曙砂，實(shí)現(xiàn)最終的一致行動头谜。這個結(jié)果非常令人驚訝，如果將軍們只能發(fā)送口頭消息麦轰，除非超過2/3的將軍是忠誠的乔夯，否則該問題無解砖织。尤其是款侵，如果只有三個將軍，其中一個是叛變者侧纯，那么此時無解新锈。但這樣的錯誤，這樣的有意眶熬、無意的“叛徒”卻可能經(jīng)常出現(xiàn)妹笆。無論是我們把“叛變的將軍”替換成以下哪種，該問題都成立娜氏。
? 一個出故障的拳缠，向其他計算機(jī)不停發(fā)出不同錯誤信息的服務(wù)器；
? 一份為獲取暴利而做出來的金融票據(jù)贸弥；
? 一份失效的醫(yī)療糾紛合同窟坐；
? 一份含混不清的保單；
? 一個可以發(fā)出消息，做出行動的錯誤信息節(jié)點(diǎn)哲鸳。
而這里臣疑，每一個錯誤節(jié)點(diǎn)可以做任意事情：不響應(yīng)；發(fā)送錯誤信息徙菠；對不同節(jié)點(diǎn)發(fā)送不同決定讯沈；不同錯誤節(jié)點(diǎn)聯(lián)合起來攻擊其他節(jié)點(diǎn)等。沒準(zhǔn)會出現(xiàn)比這更嚴(yán)重婿奔、更荒謬的錯誤缺狠。
如果說“叛變的拜占庭將軍”是我們社會中各種類型的信息節(jié)點(diǎn)的隱喻，那么“拜占庭將軍問題”所描述的情景萍摊，這樣一個進(jìn)攻／撤退命令極難驗(yàn)證真?zhèn)蔚闹惺兰o(jì)戰(zhàn)場儒老，則無疑是我們當(dāng)今越發(fā)缺乏中心化的、難以判別信息與產(chǎn)生信任的社會的極度悲觀的隱喻记餐。
構(gòu)造出一個完美的驮樊、可以解決問題的“拜占庭容錯系統(tǒng)”是一個不小的挑戰(zhàn)。而且構(gòu)造出來以后片酝，其是否真的有效囚衔，能否經(jīng)得起時間的考驗(yàn)與各方的質(zhì)疑，這些都關(guān)乎著這個系統(tǒng)未來的命運(yùn)與其創(chuàng)造群體的聲譽(yù)雕沿。 2008年冬季练湿，美國MIT（麻省理工學(xué)院）的密碼學(xué)及密碼學(xué)政策戰(zhàn)略的郵件討論組中，一位澳大利亞的企業(yè)家James A Donald（詹姆斯·A. 唐納德）就對一位聲稱構(gòu)造出了一個點(diǎn)對點(diǎn)的审轮、不需要第三方權(quán)威認(rèn)證的e-cash（電子現(xiàn)金）支付系統(tǒng)提出了質(zhì)疑肥哎。
而他的理由就是：對方設(shè)計的P2P系統(tǒng)不能夠解決“拜占庭將軍問題”。 在郵件中他挑剔地說道：“我們的確真的非常非常需要這個系統(tǒng)疾渣，但我所擔(dān)憂的并不是信任的問題篡诽，而是如何獲取一個全局共享的圖景，借由此點(diǎn)而獲取一致性的問題榴捡。每個人都知道X杈女，這并不足夠。
我們需要讓每個人都知道‘每個人都知道X’吊圾。而每個人都知道‘每個人都知道X’就是‘拜占庭將軍問題’中达椰，分布式的數(shù)據(jù)處理最難解決的問題。尤其是當(dāng)X是非常龐大的數(shù)據(jù)時……”言下之意项乒，他并不清楚或不確信這個去中心化的系統(tǒng)啰劲，如何解決拜占庭將軍的難題。 僅僅在一天之后檀何，他就收到了原作者的回復(fù)蝇裤，一封簡潔趁尼、優(yōu)雅的郵件解釋了在這個系統(tǒng)中，破解“拜占庭將軍問題”的算法猖辫。
? ? 一群拜占庭將軍酥泞，人手一臺電腦想用字符串模式匹配的方法，暴力破解國王的Wi-Fi密碼啃憎，當(dāng)然他們已經(jīng)事先獲取了組成密碼的字符串的長度芝囤。一旦他們開始模擬網(wǎng)絡(luò)發(fā)送數(shù)據(jù)包，他們必須在一個限定的時間內(nèi)完成破解工作辛萍，并清除服務(wù)器和電腦上的記錄悯姊，否則他們就會被發(fā)現(xiàn)，那就麻煩了贩毕。
只有當(dāng)絕大多數(shù)將軍在同一時間發(fā)起攻擊和破解悯许，這樣才能有足夠的CPU（中央處理器）和計算能力在短時間內(nèi)完成破解工作。 他們并不特別在乎什么時候開始攻擊辉阶，只要他們?nèi)客饩秃谩?/p>
一開始的時候先壕，大家決定這樣搞：任何人覺得時機(jī)到了都可以宣布一個攻擊時刻。而且谆甜，不論是什么時候垃僚，只要是第一個被聽到的攻擊時刻，就將被確定為官方的攻擊時刻规辱。這樣的話問題又來了谆棺，因?yàn)榫W(wǎng)絡(luò)傳達(dá)有延遲和干擾，如果有兩個將軍差不多同一時間公布了兩個不同的攻擊時刻罕袋，那么有的人會最先聽到其中一個將軍發(fā)布的攻擊時刻改淑，而又有些人則會最先聽到另外一個將軍發(fā)布的攻擊時刻。
他們使用一個“工作量證明鏈”來解決這個問題浴讯。當(dāng)每個將軍接收到任何表達(dá)形式的第一個攻擊時刻時朵夏，他都會設(shè)置他的計算機(jī)來求解一個極其困難的“工作量證明”問題，對這個問題的解答是一個哈希（Hash）散列兰珍，里面也將包含著這次的攻擊時刻侍郭。
由于這個“工作量證明”問題询吴，非常難解掠河，一般而言，就算所有人收到這個問題后同時求解猛计，也至少需要10分鐘才能產(chǎn)生解答唠摹。
一旦一個將軍解出了“工作量證明”，他將會把這個算出來的“工作量證明”向整個網(wǎng)絡(luò)進(jìn)行傳播奉瘤，每一個接收到的人勾拉，將在他們當(dāng)前正在做的“工作量證明”計算的散列中附加上剛剛被求解出來的那個工作量證明煮甥。如果任何人正在計算他收到的其他的一個不同的攻擊時刻，他們將會轉(zhuǎn)向新的更新后的“工作量證明”計算當(dāng)中藕赞，因?yàn)樗F(xiàn)在的“工作量證明鏈”更長了成肘。
兩個小時后，將有一個攻擊時刻被散列在一個有12個“工作量證明”的鏈中斧蜕。每個將軍只要通過驗(yàn)證（這條工作鏈的）計算難度双霍，就能估算出平均每小時有多少CPU算力耗費(fèi)在這上面，也就會知道：這一定是在分配的時間段內(nèi)批销，絕大多數(shù)將軍的計算機(jī)共同協(xié)作才能生成的結(jié)果洒闸。
如果“工作量證明鏈”中展示出來的算力足夠強(qiáng)大，可以破解國王的Wi-Fi密碼均芽，那么他們就可以在一致同意的時間內(nèi)安全地展開攻擊丘逸。 同步、分布式數(shù)據(jù)庫和一個一致的掀宋、全局性的視野的問題如何解決深纲？“工作量證明鏈”就是答案。
我們可以看到這封郵件解決了下面幾個問題：
（1）引入一個困難的劲妙、需要10分鐘求解的工作量計算囤萤，限制了網(wǎng)絡(luò)中每個時刻中被提出的進(jìn)攻時刻數(shù)目。
（2）將所有求解出的“工作量證明”都逐一加入是趴，形成一個越來越長的鏈條涛舍，一個記錄著所有“參與著攻擊時刻哈希計算的將軍、計算的‘工作量證明’唆途、關(guān)于‘工作量證明’的計算的總體名錄”富雅。
（3）基于這條長鏈得出安全的進(jìn)攻時刻的答案。
