在講這個問題前，我們先回顧我們已經(jīng)有的容錯。我們可以使用RSM來容錯，在2F+1最多可以有F個節(jié)點(diǎn)掛掉。
參與PAXOS的協(xié)議的機(jī)子被攻擊了，或者代碼寫錯了。這樣這臺機(jī)器可能會違背協(xié)議。
拜占庭將軍問題：
https://zh.wikipedia.org/wiki/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98
拜占庭問題的目標(biāo)是，共識發(fā)生在好人里，少數(shù)的壞人不可以影響好人去接受一個壞計劃。
本身控制不了壞人，壞人可以不遵守好人的計劃，也可以發(fā)送不同的消息
如何讓好人達(dá)成一致呢？
關(guān)鍵是讓好人得到相同的正確的消息。
假設(shè)前面5個人，前面4個都是好的，最后一個是叛徒。如果進(jìn)行投票，2個好的進(jìn)攻，2個好的撤退。叛徒無論說進(jìn)攻還是撤退看上去都是叛徒?jīng)Q定。但這個不是拜占庭將軍要解決的問題。拜占庭將軍問題是要讓這4個好人步調(diào)不一致，有人進(jìn)攻有人撤退。當(dāng)好人2邊結(jié)果很接近，叛徒的決定是可以影響最終結(jié)果這個無法避免。實(shí)際情況，5個人是無法當(dāng)面投票的，所以他們只能互相發(fā)消息來代表自己的投票。如果都是好人，每個人都會收到別人的結(jié)果，最終他們能收到一致的結(jié)果。這個時候叛徒就出來了起作用。他可以向一部分發(fā)送進(jìn)攻，一部分發(fā)送撤退。造成4個好的分裂。使得共識被破壞。
上面2個條件。每個好人都會向其他人投一致的票（一個好人不會一半投進(jìn)攻，一半投撤退），并且他們投出去的票被別人看到的都是對的。同時要求通過一些交互可以把叛徒發(fā)現(xiàn)出來使得壞人不能發(fā)揮作用。他們可以把自己收到的票再轉(zhuǎn)發(fā)一次。這個時候他們4個好人一通氣發(fā)現(xiàn)叛徒有的說進(jìn)攻有的說撤退，就能把叛徒找出來。
這個問題被轉(zhuǎn)化另一個問題，
對一個人來說他是主將，其他人是副官。叛徒如果做了副官，可以在轉(zhuǎn)發(fā)的時候搗亂。如果叛徒做了主將可以給不同的副官發(fā)不同的消息。
所以在3個人的時候，有1個叛徒。是分辨不出來的，如下圖。
通信是基于可以篡改的環(huán)境3個人的時候，有1個叛徒。是分辨不出來的
那我們看4個人能不能容忍一個壞蛋。
我們看看如何做
消息在路中不會被篡改，知道誰發(fā)的，知道消息缺席的情況。
1和2,保證叛徒不能中途截獲信息。3保證壞蛋不發(fā)消息也沒事。
基本思想就是轉(zhuǎn)發(fā)，每個人收到消息就向剩下其他人轉(zhuǎn)發(fā)。副官會收到一系列的VALUE。
我們來看一個具體例子?，F(xiàn)在4個人，假設(shè)壞蛋是副官。
那么大多數(shù)的是好人發(fā)的。
如果壞蛋是CMD會如何，最優(yōu)策略是發(fā)3個不一樣（最可能達(dá)不成一致）
好人經(jīng)過轉(zhuǎn)發(fā)，發(fā)現(xiàn)3個消息不一致，那么他們就知道CMD是壞人，就可以不執(zhí)行了。
那么時間復(fù)雜度是多少呢？
復(fù)雜度會比較高。純ORAL的方式DETECT的代價非常大。
最簡單的方法是不讓他篡改MESSAGE。（這里如何解讀，也就是好比將軍都是用自己專屬的筆跡寫的指令，當(dāng)叛徒收到后，是無法篡改后轉(zhuǎn)發(fā)給別人。所以叛徒能做的只有當(dāng)自己做COMMANDER的時候，發(fā)送混亂的消息。）
在這是非對稱的簽名可以用上了，就達(dá)到了上述的效果。
這樣復(fù)雜度就降低了。當(dāng)不存在機(jī)器掛掉的時候，只需要有2F+1個機(jī)器就可以容忍F個壞蛋。
如果在DS里有些系統(tǒng)被攻擊，那么就可以用拜占庭問題來解決。
又有人會搗亂，又有人會不參加，怎么在一起WORK，也就是說結(jié)合PAXOS和BFT來實(shí)現(xiàn)一個RSM。RSM就是初始狀態(tài)一致，操作一致，結(jié)束狀態(tài)就會一致。
上述的分析就表示如果有壞蛋，那么PAXOS就不能用。如果消息是加密的，要解決這個問題，我們首先要限制住如果壞蛋是PRIMARY的情況，因?yàn)閴牡笆荁ACKUP時，由于消息是加密的，它不能做什么事情，最多只能讓自己掛掉。
那么整個問題就變成如何發(fā)現(xiàn)錯誤當(dāng)壞蛋是PRIMARY的時候，當(dāng)有機(jī)器掛了應(yīng)該怎么做？
我們首先來看下為什么PAXOS在拜占庭問題下會不WORK？
在這里既有機(jī)器會掛掉，又有機(jī)器是壞蛋，那么3f+1里需要有2F+1達(dá)成一致。
也就是說可以容忍F個壞蛋和F個機(jī)器掛掉。
輪流做PRIMARY ， 有F+1個人達(dá)成一致可以要求替換PRIMARY。（因?yàn)樽疃郌個壞蛋，壞蛋團(tuán)結(jié)不管用）
當(dāng)PRIMARY 是好人，壞蛋能不能阻止PRIMARY 繼續(xù)做下去？因?yàn)楹萌擞?F+1個，即使有F個掛了，還有F+1個，那么當(dāng)F個壞人都在搗亂。其他的REPLICA好人也知道有F+1的消息一致，所以知道PRIMARY是好人。
當(dāng)PRIMARY時壞人，好人能不能阻止？ 當(dāng)PRIMARY時壞人，有F+1個好人，會彼此交互PRIMARY給他們發(fā)的消息看是不是一致，而壞人一定不一致。而必定有至少F+1個混亂的消息。那么就知道PRIMARY是壞人。所以可以按順序繼續(xù)讓下一個人來做PRIMARY。
