基于HoneyBadgerBFT算法的流程解析
1)算法流程
整體的算法分為三個(gè)步驟:1)每個(gè)節(jié)點(diǎn)交易隨機(jī)選擇一些交易,所有節(jié)點(diǎn)的總交易個(gè)數(shù)是B。 每個(gè)節(jié)點(diǎn)的交易進(jìn)行加密生成x。2)通過ACS協(xié)議將每個(gè)節(jié)點(diǎn)加密的交易進(jìn)行廣播,以及形成統(tǒng)一交易序列。 3)解密交易生成區(qū)塊。整體的算法流程如下:
2)TPKE加解密算法
TPKE,threshold public key encryption,加解密算法,一個(gè)公鑰,多份私鑰。通過TPKE加密后的數(shù)據(jù)需要多份子秘鑰才能解密。
TPKE.Setup創(chuàng)建公鑰PK和若干個(gè)子秘鑰SKi。TPKE.Enc用PK對m進(jìn)行加密,加密結(jié)果是C。TPKE.DecShare用單個(gè)子秘鑰解密得到中間結(jié)果。TPKE.Dec用若干個(gè)中間結(jié)果解密得到m。
3)ACS協(xié)議
ACS - Asynchronous Common Subset。ACS協(xié)議又由兩個(gè)協(xié)議組成:RBC協(xié)議和BA協(xié)議。ACS協(xié)議的主要功能是通過RBC協(xié)議廣播交易,再通過BA協(xié)議形成一致的列表。網(wǎng)絡(luò)節(jié)點(diǎn)間的數(shù)據(jù)共識的基礎(chǔ)是RBC協(xié)議。
4)RBC協(xié)議
RBC,reliable broadcast協(xié)議。RBC協(xié)議通過糾刪碼算法降低節(jié)點(diǎn)間的數(shù)據(jù)傳輸。兩次廣播(ECHO以及READY消息)后,網(wǎng)絡(luò)節(jié)點(diǎn)間可以形成共識。RBC的算法如下:
RBC算法的精髓是充分利用所有節(jié)點(diǎn)間的網(wǎng)絡(luò)帶寬。廣播發(fā)起者P,將需要廣播的數(shù)據(jù)(區(qū)塊),通過糾刪碼算法分割成N份(其中有2f份是冗余),分發(fā)給N個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)之間利用它們自己的網(wǎng)絡(luò)帶寬,廣播這些分割后數(shù)據(jù)。這樣做的好處是降低了廣播發(fā)起者P的網(wǎng)絡(luò)帶寬,充分利用所有節(jié)點(diǎn)的網(wǎng)絡(luò)帶寬,示意如下圖:
上圖中,廣播發(fā)起者先向三個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)A,B和C廣播糾刪碼算法生成的分割后的小區(qū)塊。網(wǎng)絡(luò)節(jié)點(diǎn)A,B和C在接收到小區(qū)塊數(shù)據(jù)后,廣播給其他節(jié)點(diǎn)。任何節(jié)點(diǎn)只要收到超過一定數(shù)量的小區(qū)塊就可以恢復(fù)出原始區(qū)塊。
5)復(fù)雜度以及實(shí)驗(yàn)數(shù)據(jù)
論文指出HoneyBadgerBFT算法的總的數(shù)據(jù)傳輸?shù)膹?fù)雜度:
其中,v是單節(jié)點(diǎn)上最大數(shù)據(jù)大小。推導(dǎo)方法如下圖所示:
因?yàn)橐淮蝹鬏攲?shí)現(xiàn)B個(gè)交易(N^N*LogN),一個(gè)交易的傳輸量的復(fù)雜度可以近似為O(N)。
論文在Amazon集群上模擬節(jié)點(diǎn),對比了HoneyBadgerBFT和PBFT的性能,如下圖:
簡單的說,在網(wǎng)絡(luò)節(jié)點(diǎn)少的情況下(比如,8節(jié)點(diǎn)),HoneyBadgerBFT性能稍遜PBFT算法。但是在網(wǎng)絡(luò)節(jié)點(diǎn)變多的情況下,HoneyBadgerBFT算法的性能幾乎不變,而PBFT算法的性能顯著下降。
總結(jié):HoneyBadgerBFT是針對異步網(wǎng)絡(luò)設(shè)計(jì)的共識算法。HoneyBadgerBFT算法,讓網(wǎng)絡(luò)節(jié)點(diǎn)同時(shí)廣播交易,其核心是RBC廣播協(xié)議。RBC廣播協(xié)議的主要思想是,使用糾刪碼算法降低節(jié)點(diǎn)間的數(shù)據(jù)傳輸量,并通過BA算法形成一致的交易列表。論文指出HoneyBadgerBFT算法的復(fù)雜度是O(N),在網(wǎng)絡(luò)節(jié)點(diǎn)少的情況下(比如,8節(jié)點(diǎn)),HoneyBadgerBFT性能稍遜PBFT算法。但是在網(wǎng)絡(luò)節(jié)點(diǎn)變多的情況下,HoneyBadgerBFT算法的性能幾乎不變,而PBFT算法的性能顯著下降。