王旭東 符精晶 王 赟
(1.江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013)(2.沙洲職業(yè)工學(xué)院電子信息工程系 張家港 215600)
比特幣[1]作為有史以來(lái)最成功的加密貨幣[2],是一種突破和顛覆性的創(chuàng)新,其底層的區(qū)塊鏈技術(shù)在分布式共識(shí)領(lǐng)域備受技術(shù)人員和研究者的關(guān)注。區(qū)塊鏈(blockchain)是一種由對(duì)等網(wǎng)絡(luò)以分散的方式保存且無(wú)法篡改[3]的分布式賬本,其最初的目的是為了實(shí)現(xiàn)像比特幣這樣的數(shù)字資產(chǎn)而設(shè)計(jì)的,由于區(qū)塊鏈技術(shù)擁有的巨大的潛力為現(xiàn)有業(yè)務(wù)能力的突破提供了新的可能性,故區(qū)塊鏈技術(shù)在能源貿(mào)易,農(nóng)業(yè)[4],物聯(lián)網(wǎng)(IoT)[5]等領(lǐng)域被廣泛應(yīng)用。
在區(qū)塊鏈系統(tǒng)中當(dāng)眾多節(jié)點(diǎn)試圖將一個(gè)區(qū)塊添加到主鏈中時(shí),就需要一種達(dá)成一致性協(xié)議算法來(lái)確定哪個(gè)區(qū)塊才能被添加到主鏈中,這個(gè)算法被稱(chēng)為共識(shí)算法,共識(shí)算法具有非常重要的意義,它決定了要添加的數(shù)據(jù)的正確性、試圖添加該區(qū)塊的節(jié)點(diǎn)的可信度以及確保了區(qū)塊鏈系統(tǒng)中分散的節(jié)點(diǎn)之間的一致性,高效的共識(shí)算法可實(shí)現(xiàn)更高的精度、更高的安全性、更好的性能和擴(kuò)展性等,常見(jiàn)的共識(shí)算法有工作量證明(PoW)[1],權(quán)益證明(PoS)[6]和實(shí)用拜占庭容錯(cuò)(PBFT)[7]等。
目前區(qū)塊鏈的發(fā)展還處于最初階段,面臨著很多問(wèn)題[8],其中擴(kuò)展性[9]問(wèn)題亟待解決,分片技術(shù)是迄今為止被認(rèn)為最能夠解決區(qū)塊鏈系統(tǒng)擴(kuò)展性的最實(shí)用的解決方案,它通過(guò)將網(wǎng)絡(luò)劃分為不同的分片能夠使系統(tǒng)的處理、存儲(chǔ)和計(jì)算可以并行進(jìn)行,從而減少通信、數(shù)據(jù)存儲(chǔ)和計(jì)算等資源開(kāi)銷(xiāo),同時(shí)保持去中心化和安全性,國(guó)內(nèi)外許多專(zhuān)家針對(duì)分片提出了諸多解決方案,下面將進(jìn)行分別的介紹。
Elastico[10]是一種無(wú)許可的分片協(xié)議,在Elastico 中節(jié)點(diǎn)首先需要解決一個(gè)用于確定共識(shí)委員會(huì)PoW 謎題,確定共識(shí)委員會(huì)后,該委員會(huì)負(fù)責(zé)對(duì)分片的共識(shí)結(jié)果作出最終決定,在Elastico 中每達(dá)成一輪共識(shí),委員會(huì)就會(huì)重組一次,這種頻繁的操作會(huì)降低交易執(zhí)行的效率;OmniLedger[11]是在Elastico的基礎(chǔ)上提出的一種分片協(xié)議,OmniLedger數(shù)據(jù)結(jié)構(gòu)塊采用了DAG,并使用了結(jié)合RndHound 和Algorand 的公共隨機(jī)協(xié)議來(lái)進(jìn)行分片,但Omniledger的缺點(diǎn)是共識(shí)過(guò)程中牽扯到跨分片交易時(shí)通信開(kāi)銷(xiāo)過(guò)大;RapidChain[12]是一種基于PBF 算法分片的公共區(qū)塊鏈協(xié)議,RapidChain 通過(guò)減少每筆交易的數(shù)據(jù)交換量,并使用快速的跨分片驗(yàn)證技術(shù),使交易不需要大范圍傳播,但是RapidChain 是采用PBF算法達(dá)成共識(shí),依然沒(méi)能解決通信開(kāi)銷(xiāo)大的問(wèn)題;Monoxide[13]是一個(gè)橫向擴(kuò)展的區(qū)塊鏈,它提出了異步共識(shí)區(qū),線性擴(kuò)展了區(qū)塊鏈系統(tǒng),但依然沒(méi)能解決通信開(kāi)銷(xiāo)的問(wèn)題;Zilliqa[14]是以Pow 為共識(shí)算法的區(qū)塊鏈分片技術(shù),Zilliqa 通過(guò)處理不同分片中的交易來(lái)改進(jìn)吞吐量,但是Zilliqa中的節(jié)點(diǎn)需要存儲(chǔ)整個(gè)區(qū)塊鏈網(wǎng)絡(luò)中的數(shù)據(jù),阻礙了系統(tǒng)的擴(kuò)展;Harmony 是一個(gè)具有多個(gè)分片鏈結(jié)構(gòu)的方案,它可以同時(shí)處理交易和存儲(chǔ)數(shù)據(jù),但該分片協(xié)議可擴(kuò)展性較差,還有很大的研究空間。
PBFT 是一種經(jīng)過(guò)改進(jìn)的BFT 算法,經(jīng)過(guò)改進(jìn),PBFT在異步環(huán)境下比BFT的響應(yīng)時(shí)間降低了一個(gè)數(shù)量級(jí),并能夠容忍異步系統(tǒng)中故障節(jié)點(diǎn)引起的一致性問(wèn)題。與PoW 相比,PBFT 的工作原理中沒(méi)有計(jì)算任務(wù),因此,它將共識(shí)的復(fù)雜性降低到多項(xiàng)式水平,并且顯著降低了能耗。
圖1 PBFT算法的共識(shí)過(guò)程
在PBFT的每個(gè)視圖中,當(dāng)主節(jié)點(diǎn)收到請(qǐng)求時(shí),它會(huì)根據(jù)一個(gè)三階段的協(xié)議向前移動(dòng):預(yù)準(zhǔn)備、準(zhǔn)備和提交。在預(yù)準(zhǔn)備階段,當(dāng)主節(jié)點(diǎn)收到請(qǐng)求序列時(shí),主節(jié)點(diǎn)按順序?qū)⒄?qǐng)求序列發(fā)送給其他副本節(jié)點(diǎn),副本節(jié)點(diǎn)在收到請(qǐng)求序列后,檢查其有效性,并將其添加到其本地日志中,并向其副本節(jié)點(diǎn)發(fā)送一條消息,以顯示它已經(jīng)收到了提議并識(shí)別了它。然后,副本節(jié)點(diǎn)進(jìn)入準(zhǔn)備階段,副本節(jié)點(diǎn)成功收集2f+1反饋消息(f表示故障節(jié)點(diǎn)數(shù)量)時(shí),將啟動(dòng)提交階段。最后,主節(jié)點(diǎn)收集到2f+1 條提交消息后,就可以確保提案已經(jīng)由足夠的副本節(jié)點(diǎn)完成記錄,可以執(zhí)行反饋操作,并向客戶(hù)端發(fā)送回復(fù)。
為了確保主節(jié)點(diǎn)不出現(xiàn)故障,PBFT 設(shè)計(jì)了一種稱(chēng)為視圖更換的協(xié)議,如果備份節(jié)點(diǎn)發(fā)現(xiàn)主節(jié)點(diǎn)有惡意行為或停止工作,那么它會(huì)獨(dú)立地宣布要將主節(jié)點(diǎn)更改為下一個(gè)節(jié)點(diǎn)的提議,如果2f+1副本發(fā)現(xiàn)主節(jié)點(diǎn)的異常,將確認(rèn)更改視圖,由下一個(gè)主節(jié)點(diǎn)接管。
聚合簽名[15]是一種用于消息身份驗(yàn)證和數(shù)據(jù)完整性驗(yàn)證的安全技術(shù),通過(guò)將一組數(shù)字簽名組合成一個(gè)單一的數(shù)字簽名,可用作大量數(shù)據(jù)的完整性證明。聚合簽名通過(guò)把多個(gè)簽名進(jìn)行聚合,節(jié)省了通信和存儲(chǔ)空間,在聚合簽名驗(yàn)證過(guò)程中只有當(dāng)整個(gè)簽名集都有效時(shí),聚合簽名的驗(yàn)證才會(huì)輸出肯定的結(jié)果,如果在集合中有一個(gè)錯(cuò)誤的簽名,則表示所涉及數(shù)據(jù)的完整性無(wú)效。下面對(duì)聚合簽名做簡(jiǎn)單驗(yàn)證,對(duì)于橢圓曲線上的兩個(gè)點(diǎn)X,Y 和x,y 以及原點(diǎn)G:
聚合簽名有諸多優(yōu)點(diǎn),對(duì)于驗(yàn)證者來(lái)講,聚合簽名可以提升交易的驗(yàn)證速度并節(jié)省了通信和存儲(chǔ)空間,且無(wú)法通過(guò)聚合簽名推導(dǎo)出參與方的公鑰和簽名的信息,可用于提高鏈上數(shù)據(jù)的隱私性。
本章通過(guò)對(duì)節(jié)點(diǎn)數(shù)對(duì)分片失效概率的分析、分片節(jié)點(diǎn)數(shù)對(duì)分片均不失效的分析來(lái)驗(yàn)證導(dǎo)致分片有效性降低的原因。
根據(jù)式(4),設(shè)置初始參數(shù)值f=[0.1,0.2,0.3],通過(guò)改變M 的值模擬研究M 對(duì)P的影響情況,如表1所示。
表1 分片內(nèi)節(jié)點(diǎn)數(shù)M對(duì)單個(gè)分片失效概率P的影響
根據(jù)表1,在f 不變時(shí),隨著分片中節(jié)點(diǎn)數(shù)目的增多,分片失效的概率顯著降低,在M不變時(shí),隨著f 增大分片失效概率越高,對(duì)于整個(gè)區(qū)塊鏈系統(tǒng)而言,單個(gè)分片失效概率大于0.03已經(jīng)是一個(gè)較高的數(shù)值了。
假設(shè)拜占庭節(jié)點(diǎn)比例為f(0 ≤f≤1/3) ,每個(gè)分片中節(jié)點(diǎn)數(shù)為M,分片個(gè)數(shù)為k,若想保證所有分片不失效,需要保證每個(gè)分片內(nèi)的拜占庭節(jié)點(diǎn)的比例f<1/3,為了追求結(jié)果的準(zhǔn)確性,采用窮舉遍歷的方法,如式(5)所示,式(6)和式(7)是式(5)的兩個(gè)限定條件。
在探究M 與Pr 的關(guān)系時(shí),為了研究高拜占庭節(jié)點(diǎn)比例下分片的失效概率,選取f=0.3,分片個(gè)數(shù)k=4,固定這兩個(gè)值可準(zhǔn)確地研究有效分片規(guī)模與高拜占庭比例下,分片內(nèi)節(jié)點(diǎn)數(shù)M對(duì)所有分片都不失效的概率值Pr 影響,圖2 是基于式(5),M 對(duì)P 的影響圖。
圖2 M對(duì)P的影響
圖2 顯示,增加分片內(nèi)的節(jié)點(diǎn)數(shù)在一定程度上能提高分片不失效的概率,但所有分片不失效的概率依然很低,且隨著不斷增加分片內(nèi)節(jié)點(diǎn)數(shù),P 增大的幅度在減小,而且在f=0.3 的情況下,僅增大分片中的節(jié)點(diǎn)數(shù)目仍無(wú)法解決分片失效率高的問(wèn)題。
為了解決以上問(wèn)題,本文通過(guò)動(dòng)態(tài)權(quán)值分配方法優(yōu)化一致性hash 算法,解決節(jié)點(diǎn)分配的不均衡性,在此基礎(chǔ)上實(shí)現(xiàn)基于PBFT 共識(shí)算法利用聚合簽名技術(shù)改進(jìn)動(dòng)態(tài)實(shí)用拜占庭算法(DPBFT)。
在對(duì)節(jié)點(diǎn)進(jìn)行隨機(jī)劃分時(shí),采用一致性哈希算法[16]進(jìn)行劃分,但是在系統(tǒng)中每一個(gè)節(jié)點(diǎn)都存在差異,故本文通過(guò)動(dòng)態(tài)權(quán)值分配的方法對(duì)一致性hash算法進(jìn)行優(yōu)化以支持動(dòng)態(tài)權(quán)重,首先對(duì)權(quán)值進(jìn)行計(jì)算,步驟如下:
1)節(jié)點(diǎn)負(fù)載
假設(shè)有n 個(gè)節(jié)點(diǎn),分片數(shù)目為m,對(duì)于每個(gè)節(jié)點(diǎn)i,CPU 利用率是內(nèi)核模式和空閑模式下CPU(t)時(shí)間之和的比值,采用以下公式計(jì)算:
節(jié) 點(diǎn) 閑 置 內(nèi) 存 為METfree(t),節(jié) 點(diǎn) 總 內(nèi) 存 為METtotal(t),主機(jī)內(nèi)存利用率(MEM(t))為
網(wǎng)絡(luò)利用率(NET(t))是節(jié)點(diǎn)在時(shí)間間隔t 內(nèi)接收和發(fā)送的字節(jié)之和與網(wǎng)絡(luò)帶寬NETband(t)的比值,當(dāng)一個(gè)節(jié)點(diǎn)加入集群時(shí),可以使用以下公式計(jì)算網(wǎng)絡(luò)利用率:
通過(guò)上面的計(jì)算,我們使用以下公式計(jì)算系統(tǒng)中節(jié)點(diǎn)i的負(fù)載Load:
其中λ1=0.3,λ2=0.3,λ3=0.4。
2)節(jié)點(diǎn)誠(chéng)信值
共識(shí)完成率反映了節(jié)點(diǎn)在區(qū)塊鏈中總體的完成程度,其可通過(guò)共識(shí)完成率γ表示,如式(12)計(jì)算:
式(12)中,s 為節(jié)點(diǎn)成功完成的共識(shí)次數(shù),a 為調(diào)節(jié)常數(shù),n為節(jié)點(diǎn)參與共識(shí)次數(shù)。
交易影響率用于表示交易對(duì)節(jié)點(diǎn)的影響程度,交易影響率可用交易影響函數(shù)f(x)計(jì)算,如式(13):
節(jié)點(diǎn)交互程度是指節(jié)點(diǎn)在區(qū)塊鏈系統(tǒng)中的參與共識(shí)的程度,節(jié)點(diǎn)交互程度用交互影響函數(shù)表示,交互影響函數(shù)可采用式(14)計(jì)算:
其中,η?( ]0.5,1 用來(lái)控制活躍度比重,a為次數(shù)調(diào)節(jié)因子,n為共識(shí)次數(shù)。
則節(jié)點(diǎn)信用可采用式(15)計(jì)算:
其中Cinit為節(jié)點(diǎn)信任值初值,E 為行為評(píng)價(jià)影響因子。
3)節(jié)點(diǎn)完成速率可用式(16)計(jì)算:
其中,V0表示原始數(shù)值,Vmin和Vmax分別為節(jié)點(diǎn)完成速率的最大和最小值。
那么節(jié)點(diǎn)s的當(dāng)前權(quán)重Ws為
經(jīng)過(guò)多次實(shí)驗(yàn)驗(yàn)證,當(dāng)ω1=0.3,ω2=0.3,ω3=0.4時(shí)最為合適。
經(jīng)過(guò)上述對(duì)分片權(quán)重的計(jì)算,我們使用一致性哈希算法來(lái)獲取系統(tǒng)中所有節(jié)點(diǎn)的動(dòng)態(tài)權(quán)值Ws,并將節(jié)點(diǎn)的動(dòng)態(tài)權(quán)重值作為哈希值,映射到哈??臻g中,然后利用一致性哈希算法來(lái)確保節(jié)點(diǎn)與哈??臻g動(dòng)態(tài)權(quán)值之間的對(duì)應(yīng)關(guān)系,并用哈希表進(jìn)行記錄,最后通過(guò)跳躍查找算法對(duì)節(jié)點(diǎn)的所有權(quán)重進(jìn)行索引查找然后隨機(jī)分配,跳躍查找算法如下所示:
選擇生成元定義為P∈G1,Q∈G2,定義雙線性映射為e:G1×G1→G2,散列函數(shù)為H0、H1、H2、HDV。
1)利用當(dāng)下的視圖計(jì)算Pv=vP,得到系統(tǒng)參數(shù)Params={G1,G2,e,q,P,Q,Pv,H0,H1,H2,HDV}。
2)用戶(hù)ui選擇隨機(jī)值xi∈Zq*計(jì)算Pi=xiP,Qi=H1(IDi||Pi),Di=vQi生成用戶(hù)的私鑰Si=(Di,xi)。
3)用戶(hù)ui執(zhí)行以下過(guò)程:ri∈Zq,計(jì)算Ri=riP,hi=H0(IDi||mi||Pi||Ri),T=H2(Pv)。
4)若要驗(yàn)證u對(duì)m的簽名σi=(Vi,Ri)的有效性,計(jì)算hi=H0(IDi||mi||Pi||Ri),Qi=H1(IDi||Pi),T=H2(Pv),并驗(yàn)證下列等式是否成立:
為了說(shuō)明上述論述是正確的,下面給出了單個(gè)簽名驗(yàn)證過(guò)程和聚合簽名驗(yàn)證過(guò)程的正確性的證明過(guò)程。
u 對(duì)m 的簽名σi=(Vi,Rn)證明單個(gè)簽名驗(yàn)證過(guò)程是正確的過(guò)程如下:
對(duì)上述問(wèn)題進(jìn)行正確性驗(yàn)證之后,改進(jìn)的共識(shí)算法DPBFT的共識(shí)過(guò)程如下。
1)令H:{0,1}*→G1是一個(gè)哈希函數(shù),T/B 是一個(gè)交易。 發(fā)送者使用私鑰sk 計(jì)算哈希值h=H((T/B)||v),計(jì)算的簽名為σ=hsk,節(jié)點(diǎn)附上發(fā)送者簽名的數(shù)據(jù)向全網(wǎng)廣播;
2)聚合簽名者通過(guò)給定的公鑰pk,交易T/B,簽名σ=hsk,計(jì)算哈希函數(shù)值h=H((T/B)||v),驗(yàn)證為真,則接受,反之放棄。聚合簽名者通過(guò)聚合簽名算法得到的聚合集表示為U={u1,u2,…,un},收集到的簽名為σ,消息集為T(mén)/B={(T/B)1,(T/B)2,…,(T/B)n},則聚合簽名為
3)主節(jié)點(diǎn)在經(jīng)過(guò)時(shí)間t 后,發(fā)送
4)副本節(jié)點(diǎn)i在收到消息后,檢查其有效性,并添加到本地日志中,并發(fā)送
本文將分別從系統(tǒng)容錯(cuò)性、交易吞吐量,交易延遲三個(gè)方面對(duì)改進(jìn)后的DPBFT 與Omniledger 兩個(gè)方案進(jìn)行對(duì)比,實(shí)驗(yàn)平臺(tái)為Hyperledger Fabric,實(shí)驗(yàn)中通過(guò)對(duì)節(jié)點(diǎn)收到消息后延遲處理與發(fā)送模擬拜占庭節(jié)點(diǎn)的行為。
在系統(tǒng)容錯(cuò)性實(shí)驗(yàn)中,主要統(tǒng)計(jì)Omniledger和DPBFT 兩種方案在不同的拜占庭節(jié)點(diǎn)數(shù)目下的出塊時(shí)間,在實(shí)驗(yàn)室中我們將拜占庭節(jié)點(diǎn)個(gè)數(shù)逐次增加至超過(guò)節(jié)點(diǎn)總數(shù)的1/3。
由圖3 可以看出,隨著拜占庭節(jié)點(diǎn)數(shù)目的增多Omniledger 和DPBFT 兩種方案的出塊時(shí)間都在增加,但DPBFT 方案的增加幅度比較小,相比而言DPBFT方案更優(yōu)。
圖3 分片內(nèi)拜占庭節(jié)點(diǎn)數(shù)目對(duì)出塊時(shí)間影響
交易吞吐量測(cè)試過(guò)程中,只改變拜占庭節(jié)點(diǎn)比例,其他參數(shù)均保持保持不變,對(duì)比DPBFT 和Omniledger兩種方案的交易吞吐量,結(jié)果如圖4所示。
圖4 不同拜占庭節(jié)點(diǎn)比例對(duì)TPS的影響
根據(jù)圖4 所示,隨著拜占庭節(jié)點(diǎn)比例的增大,兩種方案的TPS均在降低,但是DPBFT方案下降幅度稍緩,DPBFT方案較優(yōu)。
在系統(tǒng)對(duì)拜占庭節(jié)點(diǎn)比例容忍范圍內(nèi),通過(guò)改變分片個(gè)數(shù),對(duì)DPBFT 和Omnildger 兩種方案的交易延遲進(jìn)行測(cè)試,結(jié)果如圖5所示。
圖5 分片數(shù)量對(duì)交易延遲的影響
根據(jù)圖5 所示,隨著區(qū)塊鏈系統(tǒng)中分片數(shù)量不斷增加,DPBFT方案和Omniledger方案交易延遲都在增加,但DPBFT 方案具有更低的交易延遲,DPBFT方案更優(yōu)。
經(jīng)過(guò)上述實(shí)驗(yàn)分析可知,DPBFT共識(shí)算法提高了系統(tǒng)容錯(cuò)性和交易吞吐量并降低了交易延遲,保證區(qū)塊鏈系統(tǒng)分片后的系統(tǒng)效率,使該改進(jìn)后的共識(shí)算法能夠應(yīng)用于更多去中心化場(chǎng)景。
擴(kuò)展性是區(qū)塊鏈系統(tǒng)面臨的一大問(wèn)題,受到越來(lái)越多的專(zhuān)家的關(guān)注,本文針對(duì)區(qū)塊鏈分片以及分片內(nèi)達(dá)成一致性的的問(wèn)題進(jìn)行研究,提出了DPBFT共識(shí)算法,在保證分片數(shù)據(jù)的可信性前提下有效地提升了系統(tǒng)容錯(cuò)性、交易吞吐量并降低了交易延遲。