周旺，胡紅鋼，俞能海

快速響應的高效多值拜占庭共識方案

周旺1,2，胡紅鋼1,2，俞能海1,2

（1.中國科學院電磁空間信息重點實驗室，安徽 合肥 230027；2. 中國科學技術大學網絡空間安全學院，安徽 合肥 230027）

由于網絡設備的增多和傳輸環(huán)境的不確定性，消息時延同樣具有不確定性，異步共識協議發(fā)揮出更多優(yōu)勢。Miller等于2016年提出第一個異步共識協議HoneyBadgerBFT，但其在實現高吞吐量的同時傳輸效率依然可以再優(yōu)化。針對HoneyBadgerBFT中的廣播協議進行改進，減少廣播過程中的消息復雜度，同時增加可選的消息請求過程，以達到快速響應和高效傳輸的效果。

快速響應；高傳輸效率；拜占庭協議；共識方案

1 引言

自2008年中本聰首次提出比特幣[1]的概念后，區(qū)塊鏈作為其底層技術也被廣泛關注。區(qū)塊鏈本質上是一個分布式數據庫，同時具有去中心化、開放性、自治性、信息不可篡改和匿名性這五大特性。區(qū)塊鏈系統(tǒng)與傳統(tǒng)數據庫系統(tǒng)的區(qū)別在于其能夠在不依賴第三方的情況下，在分布式環(huán)境中正確運行，其核心之一是共識機制，即如何在一組節(jié)點之間達成消息的一致。

對于共識機制的研究一直熱度不減，從20世紀70年代末開始，研究人員便對分布式系統(tǒng)中的容錯問題進行了深入研究。對于宕機容錯（CFT）問題，Lamport于1989年做出了開拓性的工作，提出了一個新的狀態(tài)機復制協議—— Paxos[2]，并在2001年進行了解釋[3]。1982年，Lamport等提出了一個新的問題——拜占庭將軍問題[4]，對于新的拜占庭容錯（BFT）問題，Castro和Liskov于1999提出了著名的PBFT[5]方案。2008年以后，隨著比特幣的關注度升高，同時由于其使用的工作量證明（PoW）機制的公平性，實現簡單，PoW受到追捧，以太坊[6]、萊特幣等部分主流“數字貨幣”使用的均是PoW機制。但鑒于其消耗大量計算資源與電力資源，相關社區(qū)一直在尋找PoW的替代機制。權益證明（PoS）依據系統(tǒng)中的稀缺資源，如資金，選取出塊者，抵抗女巫攻擊的同時不用消耗大量資源，并且近些年來有研究人員提出了可證明安全的PoS協議[7-9]，所以PoS機制正逐漸被區(qū)塊鏈系統(tǒng)設計者考慮使用。為了解決共識機制的可拓展性與低吞吐量問題，一系列新的方案與機制被提出[10-13]，所以對于共識的研究會根據應用場景、需求的變化一直持續(xù)下去。

上述協議為保證可用性大多需要弱同步甚至同步環(huán)境的假定，但當底層網絡由于某些原因導致消息轉發(fā)緩慢甚至停止時，同步協議的性能將明顯下降，異步共識協議在這種環(huán)境下展示出較大優(yōu)勢。HoneybadgerBFT[14]是由 Miller等于2016年提出的第一個異步拜占庭協議，但協議過程中傳輸效率可進一步優(yōu)化，文獻[15]直接將HoneybadgerBFT中的異步公共子集（ACS）協議作為一個單獨模塊，提出一種“先共識消息哈希，后請求缺失消息”的共識思路，單位傳輸代價優(yōu)于HoneybadgerBFT。但文獻[15]對消息先通過廣播哈希值，接收多個簽名的方式進行處理，增加了時間消耗，無法快速響應共識請求。本文則對ACS協議進行改進，替換其中的廣播子模塊，增加可選的消息請求模塊，避免對消息預處理的同時減小帶寬消耗，達到快速響應、高效傳輸的效果。

2 預備知識

2.1 時間假設

底層網絡可能因為擁堵或攻擊導致消息轉發(fā)緩慢，甚至由于惡意節(jié)點的操作使消息停止轉發(fā)，這使共識協議的設計、運行變得愈加困難。研究人員針對不同應用需求，根據消息延遲的界定義了不同的時間假設。

1) 同步：發(fā)送的每個消息最多在延遲一段時間后收到，即消息的延遲存在上界。

2) 部分同步[16]：有兩種不同的情形。第一種是網絡存在最大延遲，但對于參與者是未知的；第二種是在一個未知時間（被稱為全局標準時間，GTS）后，網絡變?yōu)橥耆健?/p>

3) 弱同步：延遲的界隨時間變化，但增長速度不會比時間的多項式函數級快。

4) 異步：消息的延遲沒有上界，但誠實用戶之間發(fā)送的消息最終會達到。

2.2 HoneyBagerBFT

HoneyBadgerBFT協議是Miller等在2016年提出的一種BFT協議。其作為第一個異步的BFT共識協議，完全不依賴于網絡中對時間條件的假設。與傳統(tǒng)的PBFT共識協議相比，當節(jié)點增加時，效率不會明顯下降。

HoneyBadgerBFT由兩個模塊組成：門限加密（TPKE）模塊和異步公共子集（ACS）模塊。ACS模塊負責最終交易集合的共識，TPKE模塊保證協議的公平性，防止有針對性的審查攻擊。ACS模塊也由兩個模塊組成：可靠廣播（RBC[17]）模塊和二元共識（ABA）模塊。RBC模塊將每個節(jié)點提出的建議值廣播給其他節(jié)點，ABA模塊對所有節(jié)點之間在個比特上達成共識，第個比特為1，代表節(jié)點提出的建議值被包含在最終交易集合中。本文關注ACS協議中的RBC模塊，ACS協議及RBC協議流程如下。

//系統(tǒng)維護個RBC實例，個ABA實例

輸入 每個節(jié)點的建議值

輸出 所有建議值的一個子集

3) 當已向?個ABA實例提供過輸入，則將0作為未提供輸入的ABA實例的輸入；

4) 當所有ABA實例均已完成，取輸出為1的ABA實例對應RBC輸出的并集作為最終共識的交易集合。

5)當收到+1個匹配的READY()，若還未發(fā)送過READY消息，則廣播READY()。

6) 當收到2+1個匹配的READY()，等待?2個ECHO消息，解碼恢復。

2.3 AVID-FP

AVID-FP[18]是Hendricks于2007年提出的用于優(yōu)化糾刪碼帶寬的方案，其使用同態(tài)指紋作為每次廣播的信息。同態(tài)指紋保持了糾刪碼的結構，允許每個編碼塊可以單獨驗證其是否對應特定的原信息，于是每個節(jié)點均可以利用首次收到的編碼塊以及對應的指紋信息驗證收到的編碼塊的正確性，同時僅需在之后的廣播消息中加入指紋信息即可確保所有誠實節(jié)點擁有的編碼塊對應于同一個原信息，由于其帶寬消耗最優(yōu)，文獻[19]中使用AVID-FP作為線性存儲的實現方案。AVID-FP協議流程如下。

AVID-FP協議流程

//客戶端分發(fā)消息

//客戶端恢復消息

1)向所有服務器發(fā)送消息恢復請求（RETRIEVED）；

3)當收到的對應的編碼塊數量為時，恢復消息。

//服務器端

2)當從其他服務器收到（ECHO，fpcc），若ECHO消息數為+，并且READY消息數少于+1，則向其他服務器廣播（READY，fpcc）。

3) 當從其他服務器收到（READY，fpcc），若READY消息數為+1，并且ECHO消息數小于+，則向其他服務器廣播（READY，fpcc）；

5) 當從客戶端收到消息恢復請求（RETRIEVED）時，向客戶端發(fā)送（VERIFIED，echoed）。

3 協議設計

在RBC廣播協議中，為了驗證每個收到的廣播消息的正確性，即是否對應于特定原消息，在廣播消息中需加入編碼塊、對應的默克爾樹根以及默克爾樹路徑信息，所以，對于大小不可忽略的輸入，RBC協議執(zhí)行時將占用大量帶寬。文獻[15]直接將ACS協議作為單獨的模塊，并依據本地節(jié)點的消息和最終建議值集合中的消息有交集的假定，對消息哈希先簽名后廣播，在收到多個簽名后組成建議值特定格式項，然后使用ACS先共識消息哈希，再請求缺失消息。其通過形成特殊格式的建議值，將該值作為ACS協議的輸入，在ACS協議的廣播模塊執(zhí)行時，廣播消息的大小大大降低。本文通過對ACS協議的廣播子模塊進行替換，使用AVID-FP進行消息的廣播，在不需要對輸入做特定預處理的情況下，廣播模塊執(zhí)行時，其廣播消息的大小與消息請求模塊請求內容的大小相比可忽略，而且由于使用了同態(tài)指紋技術，對每個收到的廣播消息均可驗證其正確性，于是在不需要更多預處理操作的同時達到高效傳輸的效果。

需要注意的是，使用AVID-FP替換廣播子模塊后的ACS協議在執(zhí)行完后，共識的結果依舊是大小可忽略的fpcc集合，為了獲得最終的共識消息，需要增加額外的消息請求模塊。但在AVID-FP算法流程中有消息恢復的部分，于是恢復消息模塊可由各節(jié)點以客戶端的角色運行消息恢復部分得到最終共識消息。

協議整體流程如下：系統(tǒng)中維護個AVID-FP實例，個ABA實例，每個節(jié)點均選取一定交易消息作為建議值，然后以客戶端的角色運行AVID-FP協議，分發(fā)選取的建議值，并以服務器端的角色共識fpcc；每當一個fpcc驗證，在向客戶端發(fā)送（STROED）消息時，向對應的ABA實例輸入1；若該節(jié)點已經向?個ABA實例提供過輸入，則向其他所有ABA實例輸入0；等待所有ABA實例完成，取輸出為1的ABA實例對應的AVID-FP輸出的fpcc的并集作為最終建議值指紋集合；若此時節(jié)點網絡環(huán)境不佳，則可以先進行下一輪共識，而不需要立即請求fpcc對應的建議值集合，否則節(jié)點依次廣播消息恢復請求（RETRIEVED），在最優(yōu)情況下只需從其他+1個節(jié)點收到每個建議值的編碼塊即可恢復相應的建議值，進而得出最終建議值集合。改進的ACS協議流程如下。

//系統(tǒng)維護個AVID-FP實例，N個ABA實例

輸入 每個節(jié)點的建議值

輸出 所有建議值指紋的一個子集或所有建議值的一個子集

3)當已向?個ABA實例提供過輸入，則將0作為未提供輸入的ABA實例的輸入。

4) 當所有ABA實例均已完成，取輸出為1的ABA實例對應的AVID-FP輸出的fpcc并集作為最終共識的建議值指紋集合。

5)由fpcc集合發(fā)送消息恢復請求，并根據收到的編碼塊恢復消息集合。

在文獻[15]中，為了使本地節(jié)點的消息和最終建議值集合中的消息交集最大化，在將消息輸入ACS協議之前，需要對消息做處理，形成如下格式的消息插入本地建議值集合中。

在本文的協議中，沒有處理用戶發(fā)來消息的時間消耗，而且消息恢復模塊不影響共識的進程，若只考慮共識的fpcc，則可對參與的節(jié)點進行快速的響應；即使考慮完全恢復最終建議值集合，也會比文獻[15]中的改進方案響應更快。改進前后流程如圖1所示，模塊對比如表1所示。

4 傳輸效率分析

4.1 本協議傳輸效率分析

對于之后的消息恢復模塊，因為僅需個編碼塊便可恢復出原消息，對于某個建議值最優(yōu)情況下僅需發(fā)送個消息恢復請求，收到個誠實節(jié)點發(fā)送的建議值編碼塊即可恢復出此建議值。所以，最優(yōu)情況下的單位傳輸代價為

最壞情況下系統(tǒng)中有個敵手，在消息恢復模塊需要請求至少+個編碼塊以恢復原建議值。于是，最壞情況下單位傳輸代價為

4.2 HoneyBadgerBFT傳輸效率分析

圖1 改進前后ACS協議流程

Figure 1 ACS protocol flow charts before and after improvement

表1 改進前后模塊對比

在最優(yōu)情況下，即

1) 系統(tǒng)中個節(jié)點均為誠實節(jié)點；

2) 各個建議值之間沒有重復消息；

3) 一輪中建議值均被共識。

HoneyBadgerBFT的單位傳輸代價為

在最壞情況下，即

1) 系統(tǒng)中有個惡意節(jié)點；

2) 每輪只有2+1個建議值被共識，且其中的個來自惡意節(jié)點，+1個來自誠實節(jié)點。

4.3 文獻[15]中共識方案傳輸效率分析

文獻[15]直接將ACS協議作為單獨模塊，使用了“共識消息哈希，后請求缺失消息”的共識思路，并預先對用戶發(fā)來的消息進行了處理，形成特定格式的建議值，廣播消息的大小與消息請求模塊請求內容的大小相比可忽略不計，于是在最優(yōu)情況下，即

1) 所有節(jié)點均是誠實節(jié)點；

2) 所有節(jié)點均有了建議值中的原消息。

所有節(jié)點不會對最終共識的哈希列表中的項發(fā)起原消息傳輸請求，此時協議的單位傳輸代價為

通過表2對比可知，本文協議的傳輸效率在最優(yōu)、最壞情況下均優(yōu)于HoneyBadgerBFT，最優(yōu)情況下與文獻[15]相同，最壞情況下比文獻[15]略差，響應速度由第3節(jié)分析可知，本文協議比文獻[15]響應速度更快。

表2 單位傳輸代價比較

5 結束語

在異步共識協議中不僅要考慮傳輸效率的高低，同時需要關注對于請求的響應速度。本文在HoneyBadgerBFT的基礎上，使用修改的AVID-FP協議改進其RBC協議，使在某些特定場景下不需要恢復最終建議值集合也能快速響應共識請求，即使在請求完整建議值集合時也比文獻[8]響應更快速，同時傳輸代價比HoneyBadgerBFT在最優(yōu)、最差情況下都有所改善。

值得關注的是，在ACS與ABA協議中有多次廣播操作，消耗大部分帶寬資源，所以，如何在減少廣播操作的同時達到相同的功能是接下來的研究重點。

[1] NAKAMOTO S. Bitcoin: a peer-to-peer electronic cash system[R]. 2008.

[2] LAMPORT L. The part-time parliament[J]. ACM Transactions on Computer Systems (TOCS), 1998, 16(2): 133-169.

[3] LAMPORT L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.

[4] LAMPORT L, SHOSTAK R, PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401.

[5] CASTRO M, LISKOV B. Practical Byzantine fault tolerance[C]//OSDI. 1999: 173-186.

[6] WOOD G. Ethereum: a secure decentralised generalised transaction ledger[J]. Ethereum Project Yellow Paper, 2014, 151: 1-32.

[7] KIAYIAS A, RUSSELL A, DAVID B, et al. Ouroboros: a provably secure proof-of-stake blockchain protocol[C]//Annual International Cryptology Conference. 2017: 357-388.

[8] DAVID B, GA?I P, KIAYIAS A, et al. Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2018: 66-98.

[9] BENTOV I, PASS R, SHI E. Snow white: provably secure proofs of stake[J]. IACR Cryptology ePrint Archive, 2016: 919.

[10] EYAL I, GENCER A E, SIRER E G, et al. Bitcoin-ng: a scalable blockchain protocol[C]//13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16). 2016: 45-59.

[11] KOKORIS-KOGIAS E, JOVANOVIC P, GASSER L, et al. Omniledger: a secure, scale-out, decentralized ledger via sharding[C]// 2018 IEEE Symposium on Security and Privacy (SP). 2018: 583-598.

[12] ZAMANI M, MOVAHEDI M, RAYKOVA M. Rapidchain: scaling blockchain via full sharding[C]//2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 931-948.

[13] WANG J, WANG H. Monoxide: scale out blockchains with asynchronous consensus zones[C]//16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). 2019: 95-112.

[14] MILLER A, XIA Y, CROMAN K, et al. The honey badger of BFT protocols[C]//2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 31-42

[15] 郭兵勇, 李新宇. 一個高傳輸效率的多值拜占庭共識方案[J]. 密碼學報, 2018, 5(5): 516–528. GUO B Y, LI X Y. Multi-valued Byzantine consensus scheme with high transmission efficiency[J]. Journal of Cryptologic Research, 2018, 5(5): 516–528.

[16] DWORK C, LYNCH N, STOCKMEYER L. Consensus in the presence of partial synchrony[J]. Journal of the ACM (JACM), 1988, 35(2): 288-323.

[17] BRACHA G. Asynchronous Byzantine agreement protocols[J]. Information and Computation, 1987, 75(2): 130-143.

[18] HENDRICKS J, GANGER G R, REITER M K. Verifying distributed erasure-coded data[C]//The 26th Annual ACM Symposium on Principles of Distributed Computing. 2007: 139-146.

[19] DUAN S, REITER M K, ZHANG H. BEAT: asynchronous BFT made practical[C]//2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 2028-2041.

[20] CACHIN C, TESSARO S. Asynchronous verifiable information dispersal[C]//24th IEEE Symposium on Reliable Distributed Systems (SRDS'05). 2005: 191-201.

[21] REED I S, SOLOMON G. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics, 1960, 8(2): 300-304.

Rapid responsive and efficient multi-valued Byzantine consensus scheme

ZHOU Wang1,2, HU Honggang1,2, YU Nenghai1,2

1. Key Laboratory of Electromagnetic Space Information, Chinese Academy of Sciences, Hefei 230027, China 2. School of CyberScience, University of Science and Technology of China, Hefei 230027, China

Due to the increase of network equipments and the uncertainty of the transmission environment, the message delay is also uncertain, and the asynchronous consensus protocol possesses more advantages. Miller et al proposed the first asynchronous consensus protocol HoneyBadgerBFT in 2016, but its transmission efficiency can be optimized furthermore while achieving high throughput. The broadcast protocol in HoneyBadgerBFT was improved by reducing the message complexity in the broadcast process, and adding optional message request process to achieve rapid response and efficient transmission.

rapid response,efficient transmission, Byzantine protocol, consensus scheme

TP309.3

A

10.11959/j.issn.2096?109x.20201006

2020?01?14；

2020?03?02

胡紅鋼，hghu2005@uste.edu.cn

國家自然科學基金（61632013，61972370）

The National Natural Science Foundation of China (61632013, 61972370)

周旺, 胡紅鋼, 俞能海. 快速響應的高效多值拜占庭共識方案[J]. 網絡與信息安全學報, 2021, 7(1): 57-64.

ZHOU W, HU H G, YU N H. Rapid responsive and efficient multi-valued Byzantine consensus scheme[J]. Chinese Journal of Network and Information Security, 2021, 7(1): 57-64.

周旺（1995? ），男，安徽淮南人，中國科學技術大學碩士生，主要研究方向為共識協議、區(qū)塊鏈應用。

胡紅鋼（1978? ），男，四川彭州人，博士，中國科學技術大學教授、博士生導師，主要研究方向為密碼學、網絡安全。

俞能海（1964? ），男，安徽無為人，博士，中國科學技術大學教授、博士生導師，主要研究方向為多媒體數據處理分析與檢索、互聯網信息檢索、數字內容安全。