百萬級交易速度何以達成？淺談EOS中的BFT-DPOS共識算法

由於POW在比特幣的共識算法中極大地消耗了算法的資源。而且會有算法集中的問題，所以在2014年的時候Dan Larimer提出了一個相較於POW來說更加高效，輕便的共識機制即DPOS。該共識機制一邊能讓網絡成本小型化，另一方面有回覆語每個持股人一定的投票權。

這些超級節點呢能夠：供相關計算資源和網絡資源，保證節點的正常運行;當輪到某超級節點擁有出塊權時，超級節點收集該時段內的所有交易，並對交易驗證後打包成區塊廣播至其他超級節點，其他節點驗證後把區塊添加到自己的數據庫中。這種共識機制採用隨機的見證人出塊順序，出塊速度為 3 秒，交易不可逆需要45秒。為什麼需要 45 秒呢？因為 DPoS 下，見證人生產一個新區塊，才表示他對之前的整條區塊鏈進行了確認，表明這個見證人認可目前的整條鏈。而一個交易要達到不可逆狀態，需要 三分之二以上的見證人確認，在 EOS 裡就是 14 個見證人。DPoS共識算法也有極強的抗分叉能力，因為區塊添加到一條區塊鏈分叉的速率與擁有該共識的超級節點比例是相關的。當一個超級節點設法在兩條分叉上同時生產區塊時，EOS的持有者會在下一輪投票中將該超級節點刪掉，並且EOS社區會給予相關惡意節點一定的懲罰。因此，在一般情況下，使用DPoS的EOS都是很難經歷分叉的。

其次，我們還要明白BFT所代表的的意義。

拜占庭容錯技術（Byzantine Fault Tolerance，BFT）是一類分佈式計算領域的容錯技術。拜占庭假設是對現實世界的模型化，由於硬件錯誤、網絡擁塞或中斷以及遭到惡意攻擊等原因，計算機和網絡可能出現不可預料的行為。拜占庭容錯技術被設計用來處理這些異常行為，並滿足所要解決的問題的規範要求。

拜占庭容錯技術來源於拜占庭將軍問題。拜占庭將軍問題是Leslie Lamport在20世紀80年代提出的一個假象問題。拜占庭是東羅馬帝國的首都，由於時拜占庭羅馬帝國國土遼闊，每支軍隊的駐地分隔很遠，將軍們只能靠信使傳遞消息發生戰爭時，將軍們必須制訂統一的行動計劃。然而，這些將軍中有叛徒，叛徒希望通過影響統一行動計劃的制定與傳播，破壞忠誠的將軍們一致的行動計劃。因此，將軍們必須有一個預定的方法協議，使所有忠誠的將軍能夠達成一致，而且少數幾個叛徒不能使忠誠的將軍做出錯誤的計劃。也就是說，拜占庭將軍問題的實質就是要尋找一個方法，使得將軍們能在一個有叛徒的非信任環境中建立對戰鬥計劃的共識。在分佈式系統中，特別是在區塊鏈網絡環境中，也和拜占庭將軍的環境類似，有運行正常的服務器（類似忠誠的拜占庭將軍），有故障的服務器還有破壞者的服務器（類似叛變的拜占庭將軍）。共識算法的核心是在正常的節點間形成對網絡狀態的共識。

簡單形容就是：通過在一群數量有限的節點中，使用輪換或者其他算法來篩選出某個節點作為主節點。並且賦予該節點出塊的權利。在主節點是將該時段的交易打包成區塊後用自己的私鑰對該區塊簽名，並將其廣播到所有節點。當主節點收到至少三分之二的不同節點的簽名區塊後，則該區塊完成了所有節點的驗證成為不可逆區塊串聯到區塊鏈中。

BFT與DPOS二者相結合就誕生了BFT—DPOS共識算法。

、為了挖掘 EOS 系統的性能，Daniel Larimer 在以上基礎上又進行了修改。首先，他將出塊速度由 3 秒 縮短至 0.5 秒，理論上這樣可以極大提升系統性能，但帶來了網絡延遲問題：0.5 秒的確認時間會導致下一個出塊者還沒有收到上一個出塊者的區塊，就該生產下一個區塊了，那麼下一個出塊者會忽略上一個區塊，導致區塊鏈分叉（相同區塊高度有兩個區塊）。比如：中國見證人後面可能就是美國見證人，中美網絡延遲有時高達 300ms，很有可能到時美國見證人沒有收到中國見證人的區塊時，就該出塊了，那麼中國見證人的區塊就會被略過。

為解決這個問題，Daniel Larimer 將原先的隨機出塊順序改為由見證人商議後確定的出塊順序，這樣網絡連接延遲較低的見證人之間就可以相鄰出塊。比如：日本的見證人後面是中國的見證人，再後面是俄羅斯的見證人，再後面是英國的見證人，再後面是美國的見證人。這樣可以大大降低見證人之間的網絡延遲。使得 0.5 秒的出塊速度有了理論上的可能。

為了保證萬無一失，不讓任何一個見證人因為網絡延遲的意外而被跳過，Daniel Larimer 讓每個見證人連續生產 6 個區塊，也就是每個見證人還是負責 3 秒的區塊生產，但是由最初的只生產 1 個變成生產 6 個。最惡劣的情況下，6 個區塊中，最後一個或兩個有可能因為網絡延遲或其他意外被下一個見證人略過，但 6 個區塊中的前幾個會有足夠的時間傳遞給下一個見證人。

再來討論 BFT-DPoS 的交易確認時間問題：每個區塊生產後立即進行全網廣播，區塊生產者一邊等待 0.5 秒生產下一個區塊，同時會接收其他見證人對於上一個區塊的確認結果。新區塊的生產和舊區塊確認的接收同時進行。大部分的情況下，交易會在 1 秒之內確認（不可逆）。這其中包括了 0.5 秒的區塊生產，和要求其他見證人確認的時間。

使用上述BFT-DPoS協議就可以使得EOS的出塊間隔從原來的3秒降低到500毫秒，這也使得跨鏈通信的時延大大縮短，單位時間內可確認的交易數量大大提升。筆者相信如果這樣的機制在EOSIO1.0的正式版本中成功實現，那無疑是區塊鏈技術向支持百萬級別用戶的目標邁出的巨大一步。