大家好，我是EKT周迅鸦泳。

今天為大家簡單解釋一下银锻，EKT系統(tǒng)中如何解決“拜占庭將軍問題”

#EKT

第一，何謂“拜占庭將軍問題”做鹰？

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

拜占庭帝國想要進(jìn)攻一個(gè)強(qiáng)大的敵國钾麸，為此帝國派出了10支軍隊(duì)去包圍這個(gè)帝國更振。這個(gè)敵人雖然不如拜占庭帝國強(qiáng)大，但也足以抵御5支常規(guī)拜占庭軍隊(duì)的同時(shí)襲擊饭尝。由于某些原因肯腕，這10支軍隊(duì)無法聚合在一起進(jìn)行攻擊，必須分散然后根據(jù)統(tǒng)一的指令一起進(jìn)攻或者撤退钥平。他們?nèi)我恢к婈?duì)單獨(dú)進(jìn)攻都毫無勝算实撒，除非有至少6支軍隊(duì)同時(shí)襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵相互通信來協(xié)商進(jìn)攻意向及進(jìn)攻時(shí)間知态。

軍中可能有叛徒捷兰，可能向其他的將軍發(fā)送錯(cuò)誤的指令。在這種情況下如何保持戰(zhàn)爭指令的統(tǒng)一性進(jìn)而獲取勝利便成為了一個(gè)問題负敏。

進(jìn)一步講贡茅，拜占庭將軍的問題可以描述為：

一個(gè)發(fā)送命令的將軍要發(fā)送一個(gè)命令給其余n-1個(gè)將軍，使得所有忠誠的接收命令的將軍遵守相同的命令如果發(fā)送命令的將軍是忠誠的其做，那么所有忠誠的接收命令的將軍遵守所接收的命令這個(gè)問題發(fā)展到計(jì)算機(jī)領(lǐng)域顶考，就是拜占庭容錯(cuò)問題。區(qū)塊鏈需要解決的一個(gè)核心問題就是如何保證在分布式環(huán)境下庶柿，各個(gè)節(jié)點(diǎn)（即使存在惡意節(jié)點(diǎn)）的數(shù)據(jù)能夠達(dá)成最終的一致性和正確性村怪。

EKT的共識(shí)算法是DPoS，在DPoS的共識(shí)基礎(chǔ)上浮庐，我們也引入了基于路由策略進(jìn)行拜占庭容錯(cuò)的方案甚负。

第二，“拜占庭容錯(cuò)”方案如何實(shí)現(xiàn)审残？

在EKT中梭域，我們使用公私鑰加密和路由策略的機(jī)制實(shí)現(xiàn)拜占庭容錯(cuò)。這個(gè)是怎么實(shí)現(xiàn)的呢搅轿？

EKT主鏈上每個(gè)DPoS節(jié)點(diǎn)的公鑰都是公開的病涨，具體路由策略為：

1. 區(qū)塊廣播

當(dāng)一個(gè)節(jié)點(diǎn)完成打包之后，會(huì)對(duì)區(qū)塊進(jìn)行簽名璧坟。簽名完以后節(jié)點(diǎn)會(huì)把區(qū)塊和簽名廣播給網(wǎng)絡(luò)中的其他節(jié)點(diǎn)既穆。當(dāng)另外一個(gè)節(jié)點(diǎn)收到區(qū)塊和簽名之后會(huì)對(duì)簽名信息進(jìn)行校驗(yàn)，以此來確認(rèn)這個(gè)區(qū)塊是從打包節(jié)點(diǎn)廣播出去的雀鹃。其他節(jié)點(diǎn)確認(rèn)完成后幻工，會(huì)判斷自己節(jié)點(diǎn)與打包節(jié)點(diǎn)在當(dāng)前輪的距離，如果滿足條件 (currentIndex - miningIndex + len(DPoSNodes)) % len(DPoSNodes) <len(DPoSNodes) / 2黎茎，則將自己收到的區(qū)塊和簽名繼續(xù)廣播給其他節(jié)點(diǎn)囊颅。 當(dāng)一個(gè)節(jié)點(diǎn)收到兩個(gè)不同的打包節(jié)點(diǎn)的區(qū)塊和簽名之后，會(huì)將兩個(gè)不同的區(qū)塊和簽名發(fā)送給所有其他節(jié)點(diǎn)傅瞻。而所有節(jié)點(diǎn)則放棄當(dāng)前區(qū)塊踢代，進(jìn)入下一個(gè)區(qū)塊的打包并對(duì)當(dāng)前打包節(jié)點(diǎn)的作惡行為進(jìn)行記錄。

2. 區(qū)塊的校驗(yàn)與投票

在每個(gè)區(qū)塊頭上嗅骄，都會(huì)有區(qū)塊body的Hash校驗(yàn)值胳挎。節(jié)點(diǎn)可以向其他節(jié)點(diǎn)獲取區(qū)塊body，對(duì)body進(jìn)行處理之后掸读，對(duì)當(dāng)前打包的區(qū)塊進(jìn)行投票串远，所有節(jié)點(diǎn)都會(huì)把區(qū)塊的校驗(yàn)結(jié)果進(jìn)行簽名宏多，發(fā)送給滿足 (currentIndex - miningIndex + len(DPoSNodes)) % len(DPoSNodes) <len(DPoSNodes) / 2條件的節(jié)點(diǎn)進(jìn)行唱票。 當(dāng)任何一個(gè)節(jié)點(diǎn)收到超過半數(shù)對(duì)同一個(gè)區(qū)塊的投票之后即可認(rèn)為當(dāng)前的區(qū)塊可寫入?yún)^(qū)塊鏈中澡罚，并將區(qū)塊和投票結(jié)果發(fā)送給所有的節(jié)點(diǎn)伸但，所有節(jié)點(diǎn)對(duì)區(qū)塊進(jìn)行記錄。如果投票的數(shù)量不足半數(shù)則在一定時(shí)間內(nèi)停止唱票留搔，節(jié)點(diǎn)將自己的唱票結(jié)果發(fā)送給其他節(jié)點(diǎn)更胖，所有節(jié)點(diǎn)在收到其他節(jié)點(diǎn)的投票結(jié)果之后對(duì)結(jié)果進(jìn)行合并，判斷最后的投票結(jié)果并執(zhí)行響應(yīng)的操作隔显。?

3. 節(jié)點(diǎn)宕機(jī)

當(dāng)一個(gè)節(jié)點(diǎn)超過一定時(shí)間沒有出塊却妨，當(dāng)前輪的下一個(gè)節(jié)點(diǎn)會(huì)在 3*interval/2 的時(shí)間點(diǎn)開始打包下一個(gè)區(qū)塊，進(jìn)入下一個(gè)區(qū)塊的打包流程括眠。同理彪标，如果節(jié)點(diǎn)連續(xù)宕機(jī)，判斷當(dāng)前節(jié)點(diǎn)是否需要打包的條件是 currentTime - lastBlockTime > (2*(currentIndex -LastIndex)+1)*interval/2掷豺，一旦滿足當(dāng)前條件捞烟，則當(dāng)前節(jié)點(diǎn)開始打包。如果是最后n個(gè)區(qū)塊連續(xù)宕機(jī)当船，則按照當(dāng)前輪的最后一個(gè)區(qū)塊的hash值判斷下一輪的順序题画，按照遞增每個(gè)區(qū)塊加一個(gè)出塊interval的算法進(jìn)行計(jì)算，判斷當(dāng)前打包的節(jié)點(diǎn)并進(jìn)行打包德频。當(dāng)超過n/2的節(jié)點(diǎn)宕機(jī)的時(shí)候苍息，所有節(jié)點(diǎn)會(huì)自動(dòng)停止出塊，直到超過1/2的節(jié)點(diǎn)存活壹置。

這種方案的復(fù)雜度在最好情況下是：消息復(fù)雜度O(n^2), 時(shí)間復(fù)雜度O(1)竞思。在最差情況也可以達(dá)到：消息復(fù)雜度O(n^2), 時(shí)間復(fù)雜度O(n)〕ぃ基于這種路由策略的拜占庭容錯(cuò)機(jī)制衙四，系統(tǒng)可以保證在少于n/2的節(jié)點(diǎn)宕機(jī)或者叛變的情況下，系統(tǒng)不會(huì)出現(xiàn)分叉患亿，是一種用計(jì)算資源換容錯(cuò)性的方案。

Ending

好了押逼，今天關(guān)于“拜占庭將軍”的文章就到這里了步藕。

如果大家有任何關(guān)于技術(shù)上的問題想與我討論，

歡迎加入我的公鏈開發(fā)QQ群：699726921

項(xiàng)目交流可進(jìn)項(xiàng)目QQ群：173806202

如想關(guān)注EKT的項(xiàng)目進(jìn)展挑格，歡迎關(guān)注微信公眾號(hào)：EKT通用積分

官方網(wǎng)址

https：//ekt8.io

Telegram

中文群：http://0.plus/ektcoin

國際群：?https://0.plus/ektofficial

Twitter：@EKTcoin

https://twitter.com/EKTcoin

GITHUB

https://github.com/EducationEKT/EKT