人們常說的“拜占庭將軍”問題究竟是啥？

何謂“拜占庭將軍問題”？

拜占庭將軍問題首先是由Leslie Lamport等人在1982年提出，被稱為The Byzantine Generals Problem或者Byzantine Failure。這個問題是這樣描述的：

拜占庭帝國想要進攻一個強大的敵國，為此帝國派出了10支軍隊去包圍這個帝國。這個敵人雖然不如拜占庭帝國強大，但也足以抵禦5支常規拜占庭軍隊的同時襲擊。由於某些原因，這10支軍隊無法聚合在一起進行攻擊，必須分散然後根據統一的指令一起進攻或者撤退。他們任一支軍隊單獨進攻都毫無勝算，除非有至少6支軍隊同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵相互通信來協商進攻意向及進攻時間。

軍中可能有叛徒，可能向其他的將軍發送錯誤的指令。在這種情況下如何保持戰爭指令的統一性進而獲取勝利便成為了一個問題。

進一步講，拜占庭將軍的問題可以描述為：

一個發送命令的將軍要發送一個命令給其餘n-1個將軍，使得所有忠誠的接收命令的將軍遵守相同的命令如果發送命令的將軍是忠誠的，那麼所有忠誠的接收命令的將軍遵守所接收的命令這個問題發展到計算機領域，就是拜占庭容錯問題。區塊鏈需要解決的一個核心問題就是如何保證在分佈式環境下，各個節點（即使存在惡意節點）的數據能夠達成最終的一致性和正確性。

EKT的共識算法是DPoS，在DPoS的共識基礎上，我們也引入了基於路由策略進行拜占庭容錯的方案。

“拜占庭容錯”方案如何實現？

在EKT中，我們使用公私鑰加密和路由策略的機制實現拜占庭容錯。這個是怎麼實現的呢？

EKT主鏈上每個DPoS節點的公鑰都是公開的，具體路由策略為：

1. 區塊廣播

當一個節點完成打包之後，會對區塊進行簽名。簽名完以後節點會把區塊和簽名廣播給網絡中的其他節點。當另外一個節點收到區塊和簽名之後會對簽名信息進行校驗，以此來確認這個區塊是從打包節點廣播出去的。其他節點確認完成後，會判斷自己節點與打包節點在當前輪的距離，如果滿足條件(currentIndex - miningIndex + len(DPoSNodes)) % len(DPoSNodes)

2. 區塊的校驗與投票

在每個區塊頭上，都會有區塊body的Hash校驗值。節點可以向其他節點獲取區塊body，對body進行處理之後，對當前打包的區塊進行投票，所有節點都會把區塊的校驗結果進行簽名，發送給滿足(currentIndex - miningIndex + len(DPoSNodes) ) % len(DPoSNodes)

3. 節點宕機

當一個節點超過一定時間沒有出塊，當前輪的下一個節點會在3*interval/2 的時間點開始打包下一個區塊，進入下一個區塊的打包流程。同理，如果節點連續宕機，判斷當前節點是否需要打包的條件是currentTime - lastBlockTime > (2*(currentIndex -LastIndex)+1)*interval/2，一旦滿足當前條件，則當前節點開始打包。如果是最後n個區塊連續宕機，則按照當前輪的最後一個區塊的hash值判斷下一輪的順序，按照遞增每個區塊加一個出塊interval的算法進行計算，判斷當前打包的節點並進行打包。當超過n/2的節點宕機的時候，所有節點會自動停止出塊，直到超過1/2的節點存活。

這種方案的複雜度在最好情況下是：消息複雜度O(n^2), 時間複雜度O(1)。在最差情況也可以達到：消息複雜度O(n^2), 時間複雜度O(n)。基於這種路由策略的拜占庭容錯機制，系統可以保證在少於n/2的節點宕機或者叛變的情況下，系統不會出現分叉，是一種用計算資源換容錯性的方案。