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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



關(guān)注【深圳科普】微信公眾號(hào)，在對(duì)話(huà)框：
回復(fù)【最新活動(dòng)】，了解近期科普活動(dòng)
回復(fù)【科普行】，了解最新深圳科普行活動(dòng)
回復(fù)【研學(xué)營(yíng)】，了解最新科普研學(xué)營(yíng)
回復(fù)【科普課堂】，了解最新科普課堂
回復(fù)【科普書(shū)籍】，了解最新科普書(shū)籍
回復(fù)【團(tuán)體定制】，了解最新團(tuán)體定制活動(dòng)
回復(fù)【科普基地】，了解深圳科普基地詳情
回復(fù)【觀鳥(niǎo)知識(shí)】，學(xué)習(xí)觀鳥(niǎo)相關(guān)科普知識(shí)