想象一下中世紀的西方世界，強大的拜占庭帝國如何才能做到，讓自己的將軍們在一個有叛徒的非信任環(huán)境中建立對戰(zhàn)斗計劃的共識？現(xiàn)今的區(qū)塊鏈網(wǎng)絡(luò)環(huán)境中，在不同節(jié)點間達成共識的核心算法就是要解決這樣的“拜占庭將軍問題”。

近日，中國科學院軟件研究所張振峰團隊與新澤西理工學院唐強團隊在區(qū)塊鏈核心技術(shù)——拜占庭容錯（BFT）共識研究中取得突破，提出了首個完全實用的異步共識算法——小飛象拜占庭容錯（DumboBFT）算法，該成果發(fā)表于網(wǎng)絡(luò)安全旗艦會議ACM CCS（第27屆國際計算機與通信安全大會）。據(jù)悉，在異步BFT共識算法設(shè)計領(lǐng)域，我國此前未有重要研究成果在該會議上發(fā)表。

持續(xù)數(shù)十年的異步共識難題

1982年，圖靈獎得主Leslie Lamport把存在叛變成員的情況下，忠誠的拜占庭將軍們通過信使遠程通信，就共同進攻或共同后退的作戰(zhàn)目標達成一致，用來比喻如何解決區(qū)塊鏈中節(jié)點之間的信任問題，這就是拜占庭容錯（BFT）共識算法的來由。后來，為了進一步解決信使被敵方俘獲而造成的通信中斷或延遲問題，另一位圖靈獎得主Michael Rabin等又提出了異步BFT算法。

張振峰介紹，BFT共識算法是區(qū)塊鏈的關(guān)鍵核心技術(shù)，它可以確保區(qū)塊鏈安全可靠運行、提升區(qū)塊鏈擴展能力和運行性能的核心算法，具有運行性能高、資源消耗低、易于部署等特點，因此得到了工業(yè)界的青睞，已經(jīng)廣泛應(yīng)用于國內(nèi)外區(qū)塊鏈系統(tǒng)中。

相較而言，異步BFT可以容忍網(wǎng)絡(luò)通信故障、抵抗惡意網(wǎng)絡(luò)節(jié)點的任意破環(huán)，是保障區(qū)塊鏈在互聯(lián)網(wǎng)環(huán)境下健壯運行更為理想的共識技術(shù)。但如何設(shè)計高效的異步BFT共識算法，卻是密碼學和分布式計算領(lǐng)域的著名難題。

“用現(xiàn)有的各類隨機化算法來解決異步共識，就好比一只健壯卻行動遲緩的‘大象’，不僅會拖垮運行速度，還會讓系統(tǒng)背上沉重的通信代價?！睆堈穹甯嬖V《中國科學報》，早在20年前國際密碼學會前主席Christian Cachin等人就把“如何提升異步共識的關(guān)鍵性能指標”列為了公開問題。

“小飛象”成區(qū)塊鏈新一代核心技術(shù)

為了設(shè)計完全實用的異步共識算法，中科院軟件所從2015年開始了小飛象拜占庭容錯算法（DumboBFT）研究工作。研究團隊在對唯一一個接近實用的異步共識算法HoneyBadgerBFT進行分析后發(fā)現(xiàn)，它性能受限的根源是大量隨機化子模塊調(diào)用導致的運行時間增加。

“我們的新算法提出了全新的可證明可靠廣播原語（PRBC），并巧妙利用多值共識算法（MVBA）將隨機模塊的調(diào)用從線性減少到常數(shù)、大大降低了運行時間，在容忍1/3的惡意節(jié)點的同時，突破了異步共識算法在性能上的設(shè)計挑戰(zhàn)?！睆堈穹逭f，它變成了一只既健壯又靈活快速的“小飛象”。

“小飛象”采用PRBC保證交易被正確廣播到全網(wǎng)，進而應(yīng)用MVBA將對交易的共識轉(zhuǎn)換為對證明的共識。（研究團隊供圖）

在遍布全球四大洲的100個共識節(jié)點的測試網(wǎng)絡(luò)中，“小飛象”的確認延遲時間為24秒，不到HoneyBadgerBFT算法的1/20；交易吞吐量為每秒近1.8萬筆、是HoneyBadgerBFT算法的9倍多。目前，“小飛象”正在計劃在國內(nèi)一些主流區(qū)塊鏈平臺上進行部署。

除此之外，張振峰介紹，團隊成員路遠、盧振亮等人還進一步提出了小飛象多值共識算法（Dumbo-MVBA），在消息數(shù)量、通信代價和運行時間等關(guān)鍵性能指標上達到了漸進理論最優(yōu)，確認了MVBA才是實現(xiàn)異步共識的正確途徑，圓滿回答了“如何提升異步共識算法的關(guān)鍵性能指標”這一20年的公開問題。這一成果發(fā)表于分布式計算理論的旗艦會議ACM PODC 2020上。

據(jù)悉，小飛象共識算法是目前國際首個完全實用的異步共識算法，可為我國區(qū)塊鏈基礎(chǔ)設(shè)施建設(shè)提供強安全、高性能、可擴展的新一代核心技術(shù)。

相關(guān)論文鏈接：

https://dl.acm.org/doi/10.1145/3372297.3417262

https://dl.acm.org/doi/10.1145/3382734.3405707



關(guān)注【深圳科普】微信公眾號，在對話框：
回復(fù)【最新活動】，了解近期科普活動
回復(fù)【科普行】，了解最新深圳科普行活動
回復(fù)【研學營】，了解最新科普研學營
回復(fù)【科普課堂】，了解最新科普課堂
回復(fù)【科普書籍】，了解最新科普書籍
回復(fù)【團體定制】，了解最新團體定制活動
回復(fù)【科普基地】，了解深圳科普基地詳情
回復(fù)【觀鳥知識】，學習觀鳥相關(guān)科普知識