2021-02-23 11:44 來源：中國(guó)科學(xué)報(bào)如果是在中世紀(jì)，強(qiáng)大的拜占庭帝國(guó)如何讓自己的將軍們?cè)谝粋€(gè)有叛徒的非信任環(huán)境中建立戰(zhàn)斗計(jì)劃共識(shí)？現(xiàn)今，在區(qū)塊鏈網(wǎng)絡(luò)環(huán)境中，能在不同節(jié)點(diǎn)間達(dá)成共識(shí)的核心算法就是要解決這樣的“拜占庭將軍問題”。 近日，中國(guó)科學(xué)院軟件研究所張振峰團(tuán)隊(duì)與美國(guó)新澤西理工學(xué)院唐強(qiáng)團(tuán)隊(duì)在區(qū)塊鏈核心技術(shù)——拜占庭容錯(cuò)（BFT）共識(shí)研究中取得突破，提出了目前國(guó)際首個(gè)完全實(shí)用的異步共識(shí)算法——小飛象拜占庭容錯(cuò)（DumboBFT）算法，該成果發(fā)表于網(wǎng)絡(luò)安全旗艦會(huì)議ACM CCS（第27屆國(guó)際計(jì)算機(jī)與通信安全大會(huì)）。在異步BFT共識(shí)算法設(shè)計(jì)領(lǐng)域，我國(guó)此前未有重要研究成果在該會(huì)議上發(fā)表。 研究人員表示，這些成果可為我國(guó)區(qū)塊鏈基礎(chǔ)設(shè)施建設(shè)提供強(qiáng)安全、高性能、可擴(kuò)展的新一代核心技術(shù)。 持續(xù)數(shù)十年的異步共識(shí)難題 1982年，圖靈獎(jiǎng)得主Leslie Lamport以在有叛徒的情況下，忠誠(chéng)的拜占庭將軍們通過信使遠(yuǎn)程通信，就共同進(jìn)攻或后退的作戰(zhàn)目標(biāo)達(dá)成一致，來比喻如何解決區(qū)塊鏈節(jié)點(diǎn)之間的信任問題，這就是拜占庭容錯(cuò)（BFT）共識(shí)算法的來由。后來，為了進(jì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)有的各類隨機(jī)化算法解決異步共識(shí)，就好比一只健壯卻行動(dòng)遲緩的'大象’，不僅會(huì)拖垮運(yùn)行速度，還會(huì)讓系統(tǒng)背上沉重的通信代價(jià)。”張振峰告訴《中國(guó)科學(xué)報(bào)》，早在20年前，國(guó)際密碼學(xué)會(huì)前主席Christian Cachin等人就把“如何提升異步共識(shí)的關(guān)鍵性能指標(biāo)”列為了公開問題。 “小飛象”成區(qū)塊鏈新一代核心技術(shù) 為了設(shè)計(jì)完全實(shí)用的異步共識(shí)算法，中國(guó)科學(xué)院軟件研究所從2015年開始了小飛象拜占庭容錯(cuò)算法研究工作。研究團(tuán)隊(duì)在分析了唯一一個(gè)接近實(shí)用的異步共識(shí)算法HoneyBadgerBFT后發(fā)現(xiàn)，其性能受限的根源是大量隨機(jī)化子模塊調(diào)用導(dǎo)致的運(yùn)行時(shí)間增加。 “我們的新算法提出了全新的可證明可靠廣播原語（PRBC），并巧妙利用多值共識(shí)算法（MVBA）將隨機(jī)模塊的調(diào)用從線性減少到常數(shù)，大大降低了運(yùn)行時(shí)間，在容忍1/3的惡意節(jié)點(diǎn)的同時(shí)，突破了異步共識(shí)算法在性能上的設(shè)計(jì)挑戰(zhàn)?！睆堈穹逭f，它變成了一只既健壯又靈活快速的“小飛象”。 在遍布全球四大洲的100個(gè)共識(shí)節(jié)點(diǎn)的測(cè)試網(wǎng)絡(luò)中，小飛象拜占庭容錯(cuò)算法的確認(rèn)延遲時(shí)間為24秒，不到HoneyBadgerBFT算法的1/20；交易吞吐量為每秒近1.8萬筆，是HoneyBadgerBFT算法的9倍多。目前研究人員正計(jì)劃在國(guó)內(nèi)一些主流區(qū)塊鏈平臺(tái)部署該算法。 隨著深入研究，團(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í)的正確途徑，回答了“如何提升異步共識(shí)算法的關(guān)鍵性能指標(biāo)”這一長(zhǎng)達(dá)20年的公開問題。該成果發(fā)表于分布式計(jì)算理論的旗艦會(huì)議ACM PODC 2020上。 相關(guān)論文信息： https://dl./doi/10.1145/3372297.3417262 https://dl./doi/10.1145/3382734.3405707 |
|
|
