科學家提出完全實用的異步共識算法“小飛象拜占庭容錯算法”

近日，中國科學院軟件研究所研究員張振峰團隊與美國新澤西理工學院（現悉尼大學副教授）唐強團隊在區塊鏈核心技術——拜占庭容錯（BFT）共識研究中取得突破，提出首個完全實用的異步共識算法——小飛象拜占庭容錯（DumboBFT）算法，研究成果以Dumbo: Faster Asynchronous BFT Protocols爲題，發表於網絡安全旗艦會議ACM CCS（第27屆國際計算機與通信安全大會）。在異步BFT共識算法設計領域，我國此前未有重要研究成果在國際頂級會議上發表。

拜占庭容錯（BFT）共識算法是區塊鏈的核心技術，也是確保區塊鏈安全可靠運行、提升區塊鏈擴展能力和運行性能的核心算法。BFT共識算法具有運行性能高、資源消耗低、易於部署等特點，廣泛應用於國內外區塊鏈系統中。異步BFT算法能夠容忍網絡通信故障、抵抗拜占庭敵手惡意攻擊，是保障區塊鏈在互聯網環境下健壯運行的理想共識技術。

如何設計高效的異步BFT共識算法，是密碼學和分佈式計算領域的著名難題。自上世紀80年代起，國內外學者先後對這一難題進行了探索。第一個接近實用的異步共識算法是在2016年提出的HoneyBadgerBFT算法，已被應用於螞蟻鏈等區塊鏈平臺。爲設計完全實用的異步共識算法，軟件所於2015年開展小飛象拜占庭容錯算法研究工作。該算法以獨到視角對HoneyBadgerBFT算法進行分析，揭示其性能受限的根源是大量隨機化子模塊調用導致的運行時間增加，提出了全新的可證明可靠廣播（provable reliable broadcast）原語，並給出了基於門限數字簽名技術的高效構造方法，通過一種創新性的多值拜占庭共識應用，在容忍1/3的惡意節點的同時，突破了異步共識算法在性能上的設計挑戰。

在遍佈全球四大洲的100個共識節點的測試網絡中，小飛象拜占庭容錯算法DumboBFT的確認延遲時間爲24秒、不到HoneyBadgerBFT算法的1/20，交易吞吐量爲每秒近1.8萬筆、是HoneyBadgerBFT算法的9倍多。此外，軟件所特別研究助理路遠等人進一步提出了小飛象多值共識算法（Dubmo-MVBA），在消息數量、通信代價和運行時間等關鍵性能指標上均達到了漸進理論最優，回答了國際密碼界關於“如何提升異步共識算法的關鍵性能指標”這一問題。小飛象共識算法的創造性突破，解決了異步共識算法設計的理論難題，在性能上大幅提升並超越了當前工業界採用的HoneyBadgerBFT，成爲國際首個完全實用的異步共識算法，可爲我國區塊鏈基礎設施建設提供強安全、高性能、可擴展的新一代核心技術。

圖1.Dumbo BFT協議執行流程

圖2.Dumbo BFT和HoneyBadger BFT在全球互聯網中的實際性能對比

圖3.Dumbo-MVBA協議和HoneyBadger BFT協議的漸近複雜度對比

來源：中國科學院軟件研究所