關(guān)于拜占庭問題及其分析
故事起源
拜占庭問題是容錯(cuò)計(jì)算中的一個(gè)老問題程梦，有萊斯特蘭伯特等人在1982年提出罩息。拜占廷帝國(guó)為5-15世紀(jì)的東羅馬帝國(guó)荞胡，拜占庭城邦擁有巨大的財(cái)富拼缝，令他的十個(gè)鄰邦垂涎已久，但是拜占庭高墻聳立彰亥，固若金湯咧七，沒有任何一個(gè)單獨(dú)的鄰邦能夠成功入侵，任何單個(gè)城邦的入侵行動(dòng)都會(huì)失敗任斋，而入侵者的軍隊(duì)也會(huì)被殲滅继阻，使得其自身反而容易遭到其它九個(gè)城邦的入侵。這十個(gè)城邦之間也互相覬覦對(duì)方的財(cái)富并經(jīng)常爆發(fā)戰(zhàn)爭(zhēng)废酷。
拜占庭的防御能力如此之強(qiáng)瘟檩，非大多數(shù)人一起不能攻破。而且只要其中一個(gè)城邦背叛盟軍澈蟆，那么所有進(jìn)攻軍隊(duì)都會(huì)被殲滅墨辛，并隨后被其他鄰邦所劫掠。因此這是一個(gè)互不信任的各個(gè)鄰邦構(gòu)成的分布式網(wǎng)絡(luò)趴俘。每一方都小心行事睹簇，因?yàn)樯杂胁簧骶蜁?huì)給自己帶來(lái)災(zāi)難。為了獲取拜占庭的巨額財(cái)富寥闪，這些鄰邦分散在拜占庭的周圍太惠，依靠士兵傳遞消息來(lái)協(xié)商進(jìn)攻目的及進(jìn)攻時(shí)間，這些鄰邦將軍想要攻克拜占庭疲憋，但面臨的一個(gè)困擾凿渊，鄰邦將軍不確定他們之中是否有叛徒，叛徒是否擅自變更進(jìn)攻意向或者進(jìn)攻時(shí)間缚柳？在這種狀態(tài)下埃脏，將軍們能否找到一種分布式協(xié)議來(lái)進(jìn)行遠(yuǎn)程協(xié)商達(dá)成他們的共識(shí)，進(jìn)而贏取拜占庭城邦的財(cái)富呢秋忙？
假設(shè)前提
在拜占庭將軍問題模型中剂癌，對(duì)于將軍們有兩個(gè)公認(rèn)的假設(shè)：
假設(shè)一、所有忠誠(chéng)的將軍受到相同的命令后翰绊，執(zhí)行這條命令佩谷，得到的結(jié)果一定是相同的旁壮，它的含義是所有節(jié)點(diǎn)對(duì)命令的解析和執(zhí)行是一樣的，這個(gè)命令必須是一個(gè)確定性的命令谐檀，不能存在隨機(jī)性抡谐，也不能依賴節(jié)點(diǎn)自身的狀態(tài)，也就是說(shuō)這個(gè)秘密不能是心情好桐猬，就攻擊敵人麦撵，心情不好就原地休息；
假設(shè)二溃肪、如果命令是正確的免胃，那么所有忠誠(chéng)的將軍必須執(zhí)行這條命令，換句話說(shuō)惫撰，忠誠(chéng)的將軍需要判斷羔沙，接收到的命令是不是正確的。
對(duì)于將軍們的通訊過(guò)程厨钻，在“拜占庭將軍問題”中也是有默認(rèn)假設(shè)的：點(diǎn)對(duì)點(diǎn)通信是沒有問題的扼雏，也就是說(shuō)在這里，我們假設(shè)A將軍要給B將軍一條命令X夯膀，那么派出去的傳令兵一定會(huì)準(zhǔn)確的把命令X傳給B將軍诗充。
問題
但問題在于，如果每個(gè)城邦向其他九個(gè)城邦派出一名信使诱建，那么就是這十個(gè)城邦蝴蜓，每一個(gè)都派出了九名信使，也就是在任何一個(gè)時(shí)間有總計(jì)90次的信息傳輸俺猿，并且每個(gè)城市分別收到九條信息励翼，可能每一條都寫著不同的進(jìn)攻時(shí)間，除此以外辜荠，信息傳輸過(guò)程中汽抚，如果叛徒想要破壞原有的約定時(shí)間，就會(huì)自己修改相關(guān)信息伯病，然后發(fā)給其他城邦以混淆試聽造烁，這樣的結(jié)果是，部分城邦收到錯(cuò)誤信息后午笛，會(huì)遵循一個(gè)或者多個(gè)城邦已經(jīng)修改過(guò)的攻擊時(shí)間相關(guān)信息惭蟋，從而背叛發(fā)起人的本意。這樣一來(lái)药磺，遵循錯(cuò)誤信息的城邦（包含叛徒）告组，將重新廣播超過(guò)一條信息的信息鏈，整個(gè)信息鏈會(huì)隨著他們所發(fā)送的錯(cuò)誤信息癌佩，迅速變成不可信的信息和攻擊時(shí)間木缝，變成一個(gè)相互矛盾的糾結(jié)體便锨。
解決辦法
針對(duì)這個(gè)問題，人們主要提出了兩種解決方法我碟，一個(gè)是口頭協(xié)議算法放案；另一個(gè)是書面協(xié)議算法。
口頭協(xié)議算法的核心思想：要求每一個(gè)被發(fā)送的消息都能被正確投遞矫俺，信息接收者明確知道消息發(fā)送者的身份吱殉，并且信息接收者知道信息中是否缺少信息。采用口頭協(xié)議算法厘托，若叛徒數(shù)少于1/3時(shí)友雳，則拜占庭將軍問題可以很容易解決。但是口頭協(xié)議算法存在著明顯的缺點(diǎn)铅匹，那就是消息不能溯源押赊。
為解決該問題，提出了書面協(xié)議算法伊群。該算法要求簽名，不可偽造策精，一旦被篡改即可發(fā)現(xiàn)舰始，同時(shí)任何人都可以驗(yàn)證簽名的可靠性。
就算是書面協(xié)議算法咽袜，也不能完全解決拜占庭將軍問題丸卷，因?yàn)樵撍惴]有考慮信息傳輸延遲、簽名體系難以實(shí)現(xiàn)的問題询刹。且簽名消息記錄的保存谜嫉，也難以擺脫中心化機(jī)構(gòu)。
PBFT(拜占庭容錯(cuò)算法)
PBFT是一種狀態(tài)機(jī)副本復(fù)制算法凹联，即服務(wù)作為狀態(tài)機(jī)進(jìn)行建模沐兰，狀態(tài)機(jī)在分布式系統(tǒng)的不同節(jié)點(diǎn)進(jìn)行副本復(fù)制。每個(gè)狀態(tài)機(jī)的副本都保存了服務(wù)的狀態(tài)蔽挠，同時(shí)也實(shí)現(xiàn)了服務(wù)的操作住闯。將所有的副本組成的集合使用大寫字母R表示，使用0到|R|-1的整數(shù)表示每一個(gè)副本澳淑。
為了描述方便比原，假設(shè)|R|=3f+1，這里f是有可能失效的副本的最大個(gè)數(shù)杠巡。盡管可以存在多于3f+1個(gè)副本量窘，但是額外的副本除了降低性能之外不能提高可靠性。
首先介紹view氢拥、replica 蚌铜、primary锨侯、backups
所有的副本在一個(gè)被稱為視圖（View）的輪換過(guò)程（succession of configuration）中運(yùn)作。在某個(gè)視圖中厘线，一個(gè)副本作為主節(jié)點(diǎn)（primary）识腿，其他的副本作為備份（backups）。視圖是連續(xù)編號(hào)的整數(shù)造壮。
主節(jié)點(diǎn)由公式p = v mod |R|
計(jì)算得到渡讼，這里v是視圖編號(hào)，p是副本編號(hào)耳璧，|R|是副本集合的個(gè)數(shù)成箫。當(dāng)主節(jié)點(diǎn)失效的時(shí)候就需要啟動(dòng)視圖更換（view change）過(guò)程旨枯。
Viewstamped Replication算法和Paxos算法就是使用類似方法解決良性容錯(cuò)的。
同所有的狀態(tài)機(jī)副本復(fù)制技術(shù)一樣攀隔，PBFT對(duì)每個(gè)副本節(jié)點(diǎn)提出了兩個(gè)限定條件：
（1）所有節(jié)點(diǎn)必須是確定性的。也就是說(shuō)昆汹，在給定狀態(tài)和參數(shù)相同的情況下，操作執(zhí)行的結(jié)果必須相同满粗；
（2）所有節(jié)點(diǎn)必須從相同的狀態(tài)開始執(zhí)行。在這兩個(gè)限定條件下映皆，即使失效的副本節(jié)點(diǎn)存在挤聘，PBFT算法對(duì)所有非失效副本節(jié)點(diǎn)的請(qǐng)求執(zhí)行總順序達(dá)成一致，從而保證安全性捅彻。
接下去描述簡(jiǎn)化版本的PBFT算法组去，忽略磁盤空間不足和消息重傳等細(xì)節(jié)內(nèi)容。并且步淹，本文假設(shè)消息驗(yàn)證過(guò)程是通過(guò)數(shù)字簽名方法實(shí)現(xiàn)的添怔，而不是更加高效的基于消息驗(yàn)證編碼（MAC）的方法。
客戶端
客戶端c向主節(jié)點(diǎn)發(fā)送<REQUEST,o,t,c>請(qǐng)求執(zhí)行狀態(tài)機(jī)操作o贤旷，這里時(shí)間戳t用來(lái)保證客戶端請(qǐng)求只會(huì)執(zhí)行一次广料。客戶端c發(fā)出請(qǐng)求的時(shí)間戳是全序排列的幼驶，后續(xù)發(fā)出的請(qǐng)求比早先發(fā)出的請(qǐng)求擁有更高的時(shí)間戳艾杏。例如，請(qǐng)求發(fā)起時(shí)的本地時(shí)鐘值可以作為時(shí)間戳盅藻。
每個(gè)由副本節(jié)點(diǎn)發(fā)給客戶端的消息都包含了當(dāng)前的視圖編號(hào)购桑，使得客戶端能夠跟蹤視圖編號(hào)畅铭，從而進(jìn)一步推算出當(dāng)前主節(jié)點(diǎn)的編號(hào)〔客戶端通過(guò)點(diǎn)對(duì)點(diǎn)消息向它自己認(rèn)為的主節(jié)點(diǎn)發(fā)送請(qǐng)求硕噩，然后主節(jié)點(diǎn)自動(dòng)將該請(qǐng)求向所有備份節(jié)點(diǎn)進(jìn)行廣播。
副本發(fā)給客戶端的響應(yīng)為<REPLY,v,t,c,i,r>缭贡，v是視圖編號(hào)炉擅，t是時(shí)間戳，i是副本的編號(hào)阳惹，r是請(qǐng)求執(zhí)行的結(jié)果谍失。
客戶端等待f+1個(gè)從不同副本得到的同樣響應(yīng)，同樣響應(yīng)需要保證簽名正確莹汤，并且具有同樣的時(shí)間戳t和執(zhí)行結(jié)果r快鱼。這樣客戶端才能把r作為正確的執(zhí)行結(jié)果，因?yàn)槭У母北竟?jié)點(diǎn)不超過(guò)f個(gè)纲岭，所以f+1個(gè)副本的一致響應(yīng)必定能夠保證結(jié)果是正確有效的抹竹。
如果客戶端沒有在有限時(shí)間內(nèi)收到回復(fù)，請(qǐng)求將向所有副本節(jié)點(diǎn)進(jìn)行廣播止潮。如果請(qǐng)求已經(jīng)在副本節(jié)點(diǎn)處理過(guò)了窃判，副本就向客戶端重發(fā)一遍執(zhí)行結(jié)果。如果請(qǐng)求沒有在副本節(jié)點(diǎn)處理過(guò)兢孝，該副本節(jié)點(diǎn)將把請(qǐng)求轉(zhuǎn)發(fā)給主節(jié)點(diǎn)仅偎。如果主節(jié)點(diǎn)沒有將該請(qǐng)求進(jìn)行廣播橘沥，那么就有認(rèn)為主節(jié)點(diǎn)失效夯秃，如果有足夠多的副本節(jié)點(diǎn)認(rèn)為主節(jié)點(diǎn)失效仓洼，則會(huì)觸發(fā)一次視圖變更。
本文假設(shè)客戶端會(huì)等待上一個(gè)請(qǐng)求完成才會(huì)發(fā)起下一個(gè)請(qǐng)求哺呜，但是只要能夠保證請(qǐng)求順序某残，可以允許請(qǐng)求是異步的。
PBFT要系統(tǒng)共同維護(hù)一個(gè)狀態(tài)介牙，所有節(jié)點(diǎn)采取的行動(dòng)一致环础。為此赏酥，需要運(yùn)行三類基本協(xié)議，包括：一致性協(xié)議框都、檢查點(diǎn)協(xié)議和視圖更換協(xié)議魏保。同時(shí)谓罗，一致性協(xié)議要求來(lái)自客戶端的請(qǐng)求在每一個(gè)服務(wù)節(jié)點(diǎn)上都按照一個(gè)確定的順序執(zhí)行季二，這個(gè)協(xié)議把節(jié)點(diǎn)分為兩類：主節(jié)點(diǎn)和從節(jié)點(diǎn)胯舷，主節(jié)點(diǎn)僅有一個(gè)并負(fù)責(zé)請(qǐng)求排序，從節(jié)點(diǎn)按照主節(jié)點(diǎn)排序處理請(qǐng)求炊汹。
1）主節(jié)點(diǎn)的“選舉”
PBFT的主節(jié)點(diǎn)“選舉”和Raft算法的選舉不一樣讨便，只是通過(guò)一個(gè)模運(yùn)算進(jìn)行或者選擇當(dāng)前存活的節(jié)點(diǎn)編號(hào)最小的節(jié)點(diǎn)成為新的主節(jié)點(diǎn)霸褒。
p = v mod |R
v 是view的編號(hào)盈蛮，從0開始一直連續(xù)下去，這樣可以理解為從replica 0 到 replica |R-1 依次當(dāng)primary節(jié)點(diǎn)穆役，當(dāng)每一次view change發(fā)生時(shí)耿币。
p = v mod |R|韧拒，其中p為節(jié)點(diǎn)編號(hào)叛溢、v為視圖編號(hào)，|R|為節(jié)點(diǎn)數(shù)量厢蒜。當(dāng)主節(jié)點(diǎn)失效后就需要啟動(dòng)視圖更換斑鸦。
2）PBFT算法基本流程：
1）從全網(wǎng)節(jié)點(diǎn)選舉出一個(gè)主節(jié)點(diǎn)（Leader）巷屿，新區(qū)塊由主節(jié)點(diǎn)負(fù)責(zé)生成墩虹。
（2）每個(gè)節(jié)點(diǎn)把客戶端發(fā)來(lái)的交易向全網(wǎng)廣播诫钓，主節(jié)點(diǎn)將從網(wǎng)絡(luò)收集到需放在新區(qū)塊內(nèi)的多個(gè)交易排序后存入列表，并將該列表向全網(wǎng)廣播稳懒。
（3）每個(gè)節(jié)點(diǎn)接收到交易列表后慢味，根據(jù)排序模擬執(zhí)行這些交易纯路。所有交易執(zhí)行完后驰唬，基于交易結(jié)果計(jì)算新區(qū)塊的哈希摘要叫编，并向全網(wǎng)廣播。
（4）如果一個(gè)節(jié)點(diǎn)收到的2f（f為可容忍的拜占庭節(jié)點(diǎn)數(shù)）個(gè)其它節(jié)點(diǎn)發(fā)來(lái)的摘要都和自己相等卷谈，就向全網(wǎng)廣播一條commit消息世蔗。
（5）如果一個(gè)節(jié)點(diǎn)收到2f+1條commit消息污淋，即可提交新區(qū)塊及其交易到本地的區(qū)塊鏈和狀態(tài)數(shù)據(jù)庫(kù)余掖。
3）算法核心三階段流程
三階段流程如下圖所示盐欺，核心三階段分別為pre-preare階段（預(yù)準(zhǔn)備階段）、prepare階段（準(zhǔn)備階段）和commit階段（提交階段）歌憨，圖中的C代表客戶端务嫡，0心铃、1挫剑、2樊破、3代表節(jié)點(diǎn)的編號(hào)，打叉的3代表可能是一個(gè)故障節(jié)點(diǎn)或者問題節(jié)點(diǎn)奔滑，0為主節(jié)點(diǎn)朋其。
首先，客戶端向主節(jié)點(diǎn)發(fā)起請(qǐng)求氓辣，主節(jié)點(diǎn)0收到客戶端請(qǐng)求筛婉，會(huì)向其它節(jié)點(diǎn)發(fā)送pre-prepare消息爽撒，其它節(jié)點(diǎn)就收到了pre-prepare消息响蓉，就開始了這個(gè)核心三階段共識(shí)過(guò)程了枫甲。
我們采用三階段協(xié)議來(lái)廣播請(qǐng)求給replicas：pre-prepare, prepare, commit想幻。
（1）pre-prepare階段：
主節(jié)點(diǎn)收到客戶端請(qǐng)求，給請(qǐng)求編號(hào)闹究，并發(fā)送pre-pre類型信息給其他從節(jié)點(diǎn)渣淤。
從1節(jié)點(diǎn)收到pre-pre類型信息价认，如果同意這個(gè)請(qǐng)求的編號(hào)用踩，如果同意就進(jìn)入prepare階段
（2）Prepare階段：
從1節(jié)點(diǎn)同意主節(jié)點(diǎn)請(qǐng)求的編號(hào)忙迁，將發(fā)送prepare類型消息給主節(jié)點(diǎn)和其他兩個(gè)從節(jié)點(diǎn)动漾。如果不發(fā)荠锭，表示不同意。
圖：從1節(jié)點(diǎn)發(fā)prepare信息給其他節(jié)點(diǎn)
從1節(jié)點(diǎn)如果收到另外兩個(gè)從節(jié)點(diǎn)都發(fā)出的同意主節(jié)點(diǎn)分配的編號(hào)的prepare類型的消息共虑，則表示從1節(jié)點(diǎn)的狀態(tài)為prepared,該節(jié)點(diǎn)會(huì)擁有一個(gè)prepared認(rèn)證證書呀页。
為了防止viewchange導(dǎo)致主節(jié)點(diǎn)給請(qǐng)求分配的編號(hào)失效蓬蝶，引入commit階段。
（3）commit階段
從1節(jié)點(diǎn)進(jìn)入prepared狀態(tài)后培愁，將發(fā)送一條COMMIT類型信息給其它所有節(jié)點(diǎn)告訴他們它有一個(gè)prepared認(rèn)證證書了缓窜。
圖：從1節(jié)點(diǎn)發(fā)commit類型信息給其他節(jié)點(diǎn)
如果從1節(jié)點(diǎn)收到2f+1條commit信息禾锤，證明從1節(jié)點(diǎn)已經(jīng)進(jìn)入commited狀態(tài)恩掷。
只通過(guò)這一個(gè)節(jié)點(diǎn)，我們就能認(rèn)為客戶端的請(qǐng)求在需要的節(jié)點(diǎn)中都到達(dá)了prepared狀態(tài)旦签，每一個(gè)需要的節(jié)點(diǎn)都同意了主節(jié)點(diǎn)分配的編號(hào)宁炫。當(dāng)一個(gè)請(qǐng)求在某個(gè)節(jié)點(diǎn)中到達(dá)commited狀態(tài)后氮凝，該請(qǐng)求就會(huì)被該節(jié)點(diǎn)執(zhí)行。
整個(gè)流程：
DBFT：小蟻區(qū)塊鏈（delegated BFT竿秆，授權(quán)拜占庭容錯(cuò)機(jī)制）
用權(quán)益來(lái)選出記賬人幽钢，然后記賬人之間通過(guò)拜占庭容錯(cuò)算法 達(dá)成共識(shí)匪燕。
優(yōu)點(diǎn)：專業(yè)化的記賬人可以容忍任何類型的錯(cuò)誤記賬由多人協(xié)同完成，每一個(gè)區(qū)塊都有最終性帽驯，不會(huì)分叉算法的可靠性有 嚴(yán)格的數(shù)學(xué)證明缺點(diǎn)：當(dāng)三分之一或以上記賬人停止工作后尼变，系統(tǒng)將無(wú)法提供服務(wù)當(dāng)三分之一或以上記賬人聯(lián)合作惡嫌术，且其他所有的記賬人恰好分割為兩個(gè)網(wǎng)絡(luò)孤島時(shí)，惡意記賬人可以使系統(tǒng)出現(xiàn)分叉日丹，但是會(huì)留下密碼學(xué)證據(jù)
