TMT观察网_独特视角观察TMT行业

WF曲速區：近日，在加密貨幣經歷“混亂時期”后，區塊鏈再次火爆起來，受到了各方的極大關注與重視，成為資本市場和各領域關注的焦點，就連朋友圈中的探討和分享也讓人目不暇接。

區塊鏈核心算法一：拜占庭協定

超級賬本PBFT是Practical Byzantine Fault Tolerance的縮寫，意為實用拜占庭容錯算法。該算法是Miguel Castro (卡斯特羅)和Barbara Liskov（利斯科夫）在1999年提出來的，解決了原始拜占庭容錯算法效率不高的問題，將算法復雜度由指數級降低到多項式級，使得拜占庭容錯算法在實際系統應用中變得可行。該論文發表在1999年的操作系統設計與實現國際會議上（OSDI99）。沒錯，這個Loskov就是提出著名的里氏替換原則（LSP）的人，2008年圖靈獎得主。

拜占庭的故事大概是這么說的：拜占庭帝國擁有巨大的財富，周圍10個鄰邦垂誕已久，但拜占庭高墻聳立，固若金湯，沒有一個單獨的鄰邦能夠成功入侵。任何單個鄰邦入侵的都會失敗，同時也有可能自身被其他9個鄰邦入侵。拜占庭帝國防御能力如此之強，至少要有十個鄰邦中的一半以上同時進攻，才有可能攻破。然而，如果其中的一個或者幾個鄰邦本身答應好一起進攻，但實際過程出現背叛，那么入侵者可能都會被殲滅。于是每一方都小心行事，不敢輕易相信鄰國。這就是拜占庭將軍問題。

就上面的問題：拜占庭的n個將軍圍攻一個敵人，n個將軍包圍著這個敵人，所以他們是在不同的地方。忠誠的將軍希望通過某種協議達成某個命令的一致（比如約定某個時間一起進攻）。但其中一些背叛的將軍會通過發送錯誤的消息阻撓忠誠的將軍達成命令上的一致。如果同時發起進攻的將軍數量少于m個，那么不足以殲滅敵人反而容易被敵人全部殲滅。怎樣做才能保證有多于m個將軍在同一時間一起發起進攻？

“拜占庭將軍問題”模型中，對于將軍們（節點）有兩個默認的假設： 

1.所有忠誠的將軍收到相同的命令后，執行這條命令得到的結果一定是相同的；

2.如果命令是正確的，那么所有忠誠的將軍必須執行這條命令。

假設2的含義是：忠誠的將軍需要判斷接收到的命令是不是正確的。這個判斷命令的方法是整個拜占庭容錯技術的核心。

對于將軍們的通信過程，在“拜占庭將軍問題”中也是有默認假設的：點對點通信是沒問題的。也就是說，在這里，我們假設A將軍要給B將軍一條命令X，那么派出去的傳令兵一定會準確的把命令X傳遞給B將軍。

在這個分布式網絡里：每個將軍都有一份實時與其他將軍同步的消息賬本。賬本里有每個將軍的簽名都是可以驗證身份的。如果有哪些消息不一致，可以知道消息不一致的是哪些將軍。盡管有消息不一致的，只要超過半數同意進攻，少數服從多數，共識達成。

有了上述假設，我們來看看將軍們面臨的核心問題是什么。

拜占庭帝國的幾支軍隊攻打到了敵人的城市外面，然后分開駐扎。每一支軍隊由一位拜占庭將軍(Byzantine general)率領。為了制定出一個統一的作戰計劃，每一位將軍需要通過信差(messenger)與其它將軍互通消息。但是，在拜占庭將軍之間可能出現了叛徒(traitor)。這些叛徒將軍的目的是阻撓其他忠誠的將軍(loyal generals)達成一致的作戰計劃。為了這一目的，他們可能做任何事，比如串通起來，故意傳出虛假消息，或者不傳出任何消息。

我們考慮4個將軍的情況，同時假設4個將軍中最多只有1個背叛者。當4個將軍A、B、C、D把敵人包圍了之后，必須協商一個統一的時間去發起進攻。這時，A將軍派出了3個傳令兵，分別告訴B、C、D將軍，下午1點準時發起進攻。到了下午1點，A、C、D三個將軍發起了進攻，殲滅了敵人，同時他們三個發現B是背叛的。雖然B背叛了，但是對最終任務沒有影響。

但如果A是背叛的，會發生什么情況？A派出3個傳令兵，分別告訴B、C、D將軍在下午1點、2點、3點發起進攻。于是，到了下午1點，B將軍去攻擊敵人，由于寡不敵眾，全軍覆沒；2點，C將軍全軍覆沒；3點，D將軍全軍覆沒。

因為對于忠誠的將軍來說，他不知道誰是背叛者，所以，他不能完全相信接收到的命令，他必須對命令做出判斷。在1999年，著名的PBFT算法出現了。這個算法說起來也不難理解，他的核心思想是：對于每一個收到命令的將軍，都要去詢問其他人，他們收到的命令是什么。

回到剛才的第二種情況（A是背叛者），A派出3個傳令兵，分別告訴B、C、D將軍在下午1點、2點、3點發起進攻。B將軍派出傳令兵去告訴C和D兩位將軍，B收到的命令是下午1點進攻。C也同樣派出了傳令兵分別告訴B和D兩位將軍，C收到的命令是下午2點進攻。D也同樣告訴B和C兩位將軍，D收到的命令是下午3點進攻。于是，B得到了3條指令：A命令B下午1點進攻，A命令C下午2點進攻，A命令D下午3點進攻。B很容易判斷出來，A是背叛者（因為B知道最多只有一個背叛者）。C和D也能做出同樣的判斷。因此這次進攻時間的協商是無效的。

采用了這種辦法以后，另一種情況又會怎樣？當B是背叛者，A將軍派出了3個傳令兵，分別告訴B、C、D將軍，下午1點準時發起進攻。B告訴C說B收到的命令是下午2點，B告訴D說收到的命令是下午2點，C和D分別告訴另外2個將軍，A告訴他們的命令是下午1點。

于是，C、D收到的消息都是兩個1點，一個2點。對于C、D而言，不需要判斷是A和B誰是背叛者——他們只需要執行收到多的那個命令就可以了。

如果A是忠誠的，那么B是背叛的，這種情況下對于A來說，他知道自己是忠誠的，他發出的命令，至少有2個將軍會執行，所以下午1點，A、C、D三個將軍一起去進攻，有3個將軍一起發起攻擊，敵人被殲滅了。如果B是忠誠的，那么B會收到兩個1點一個2點，B也會執行收到多的命令，于是B、C、D三個將軍一起去進攻，有3個將軍一起發起攻擊，敵人被殲滅了。不管怎樣，按照這種方式執行，結果是沒問題的。

據區塊鏈安全社區WF曲速區 表示：由此，在一個分布式的系統中，盡管有壞人，壞人可以做任意事情（不受protocol限制），比如不響應、發送錯誤信息、對不同節點發送不同決定、不同錯誤節點聯合起來干壞事等等。但是，只要大多數人是好人，就完全有可能去中心化地實現共識。

注： 本文內容由區塊鏈安全公司WF曲速未來(WarpFuture.com)  編譯，轉載請注明來自WF曲速區。WF是交易所與超級節點的安全技術提供商，為區塊鏈交易所提供媲美某貓雙十一級別的賬戶安全與交易安全對抗云引擎，現交易所每日安全攻防調用量達億級。