提升分片規(guī)模和有效性的多輪PBFT驗(yàn)證方案

王夫森，李志淮，田 娜

大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連116002

1 引言

區(qū)塊鏈技術(shù)作為比特幣[1]的底層協(xié)議，具有去中心化、難篡改、允許運(yùn)行在非許可環(huán)境下的特點(diǎn)。區(qū)塊鏈本質(zhì)是一個(gè)去中心化的賬本，有效解決了拜占庭將軍問(wèn)題[2]，實(shí)現(xiàn)了在點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)中互不信任的節(jié)點(diǎn)通過(guò)遵循預(yù)設(shè)的機(jī)制達(dá)成數(shù)據(jù)的最終一致性，從而降低了現(xiàn)實(shí)世界的信任成本。

但是，現(xiàn)階段的區(qū)塊鏈技術(shù)仍是不成熟的，面臨著擴(kuò)容困境[3-4]。現(xiàn)有的解決方案主要?dú)w納為L(zhǎng)ayer1 層擴(kuò)容和Layer2層擴(kuò)容方案，Layer1擴(kuò)容方案主要包括分片技術(shù)[5]、DAG[6]結(jié)構(gòu)、代理共識(shí)協(xié)議、增大區(qū)塊[7]等。Layer2擴(kuò)容方案主要包括側(cè)鏈[8]、狀態(tài)通道[9-10]等。

區(qū)塊鏈分片的概念最早是在文獻(xiàn)[5]中提出，本質(zhì)是一種將計(jì)算和存儲(chǔ)分散到對(duì)等網(wǎng)絡(luò)的分區(qū)方式，每個(gè)節(jié)點(diǎn)只維護(hù)與其分片相關(guān)的信息。分片方案通過(guò)切割網(wǎng)絡(luò)中的節(jié)點(diǎn)和交易，以實(shí)現(xiàn)每秒處理數(shù)千筆交易的區(qū)塊鏈網(wǎng)絡(luò)。

POW 類共識(shí)算法屬于概率性算法，采用最長(zhǎng)鏈競(jìng)爭(zhēng)原則[11]，不適合分片內(nèi)；POS 類共識(shí)算法的邏輯是從整體上假定少數(shù)利益不能違背多數(shù)利益，也不適合被分割的分片內(nèi)。目前分片內(nèi)多采用聚合簽名優(yōu)化后的PBFT[12-13]共識(shí)算法，是一種被證明的P2P網(wǎng)絡(luò)中實(shí)現(xiàn)數(shù)據(jù)最終一致性的確定型共識(shí)算法，它允許含有傳遞惡意消息或任意延遲消息的拜占庭節(jié)點(diǎn)，但其比例小于總節(jié)點(diǎn)數(shù)的1/3。

區(qū)塊鏈分片方案盡管提高了區(qū)塊鏈吞吐量，但在采用PBFT共識(shí)算法的分片方案中，即使總體拜占庭節(jié)點(diǎn)比例不超過(guò)三分之一，單個(gè)分片內(nèi)拜占庭節(jié)點(diǎn)比例也可能會(huì)超過(guò)三分之一，使得這些分片的驗(yàn)證有效性和可用性受到威脅。

針對(duì)分片后單個(gè)分片驗(yàn)證有效性降低的問(wèn)題，在文獻(xiàn)[5]中，ELASTICO采用增加單個(gè)分片中的節(jié)點(diǎn)數(shù)目來(lái)降低單個(gè)分片失效的概率，通過(guò)將單個(gè)分片中的節(jié)點(diǎn)數(shù)目增加至600 個(gè)來(lái)保證單個(gè)分片失效的概率低于百萬(wàn)分之一。在文獻(xiàn)[14-16]中，采用包括RandHound、VSS、VRF、Randao節(jié)點(diǎn)隨機(jī)分配方案提高單個(gè)分片的驗(yàn)證有效性[14-16]。在節(jié)點(diǎn)隨機(jī)分配方案中，節(jié)點(diǎn)不具有自主選擇分片的可能性，將節(jié)點(diǎn)地址、IP地址、公鑰等信息作為輸入進(jìn)行簽名與Hash 計(jì)算，將得到的哈希結(jié)果依據(jù)映射關(guān)系分配到既定分片中。在文獻(xiàn)[17]中，通過(guò)將礦工節(jié)點(diǎn)運(yùn)行在TEE環(huán)境中以及通過(guò)SGX產(chǎn)生的隨機(jī)數(shù)將節(jié)點(diǎn)分配到既定分片[17]，降低節(jié)點(diǎn)作惡的概率。在文獻(xiàn)[18]中，提出連弩挖礦的方案[18]，每個(gè)礦工節(jié)點(diǎn)可以連接多個(gè)共識(shí)組，通過(guò)提高礦工收益的經(jīng)濟(jì)模型來(lái)降低礦工節(jié)點(diǎn)作惡的機(jī)率。

由上述文獻(xiàn)可知，目前國(guó)內(nèi)外關(guān)于分片方案的研究很多，各從不同方面對(duì)單個(gè)分片的驗(yàn)證有效性進(jìn)行了分析。但是，目前關(guān)于分片驗(yàn)證有效性的研究側(cè)重點(diǎn)集中在對(duì)分片驗(yàn)證有效性的定性分析，缺乏對(duì)分片失效概率與拜占庭節(jié)點(diǎn)比例、分片內(nèi)節(jié)點(diǎn)數(shù)目之間量化關(guān)系的分析，以及對(duì)分片驗(yàn)證失效后的進(jìn)一步處理。本文量化了影響分片驗(yàn)證有效性的各變量之間的關(guān)系，計(jì)算出單個(gè)分片失效的概率以及全部分片都不失效的概率。本文提出的多輪驗(yàn)證方案，通過(guò)連續(xù)多輪PBFT驗(yàn)證，確保分片內(nèi)的交易得到更高概率的確認(rèn)。通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以表明，多輪驗(yàn)證方案在提升分片規(guī)模的同時(shí)，確保單個(gè)分片的驗(yàn)證有效性，實(shí)現(xiàn)分片方案下區(qū)塊鏈整體TPS（Transaction Per Second）的顯著提高。

2 問(wèn)題描述與分析

2.1 問(wèn)題描述

分片方案力圖通過(guò)并行處理提高區(qū)塊鏈TPS，但也可能因?yàn)榉制瑑?nèi)驗(yàn)證有效性明顯降低，達(dá)不到預(yù)期吞吐量，產(chǎn)生分片規(guī)模與分片內(nèi)驗(yàn)證有效性的矛盾。

針對(duì)分片中采用PBFT 共識(shí)的方案，假設(shè)在未分片之前，總節(jié)點(diǎn)數(shù)目為n，拜占庭節(jié)點(diǎn)數(shù)為b，拜占庭節(jié)點(diǎn)數(shù)所占比例為f，則f=b n(0 ≤f＜1/3)?，F(xiàn)假定將n個(gè)節(jié)點(diǎn)均勻分配到k個(gè)分片中，假設(shè)每個(gè)分片內(nèi)的節(jié)點(diǎn)數(shù)是L，則L=n k；每個(gè)分片中的拜占庭節(jié)點(diǎn)比例為，其中i(1 ≤i≤k)表示分片編號(hào)。將節(jié)點(diǎn)分配到k個(gè)分片中后，自然存在拜占庭節(jié)點(diǎn)分配不均，可能出現(xiàn)≥1/3 的問(wèn)題，如圖1所示。

圖1 分片可能導(dǎo)致拜占庭節(jié)點(diǎn)在片內(nèi)聚集

圖1 描述了經(jīng)過(guò)分片后存在一定概率使得片內(nèi)拜占庭節(jié)點(diǎn)比例超過(guò)1/3。在圖1中，經(jīng)過(guò)節(jié)點(diǎn)分配后1號(hào)分片和3號(hào)分片中拜占庭節(jié)點(diǎn)數(shù)超過(guò)1/3，導(dǎo)致分片內(nèi)無(wú)法達(dá)成共識(shí)。

2.2 節(jié)將對(duì)單個(gè)分片失效的概率P與f、L的關(guān)系進(jìn)行量化，2.3節(jié)中將對(duì)所有分片都正常工作的概率Pr與f、L、k之間的關(guān)系進(jìn)行量化。

2.2 單個(gè)分片失效概率的分析

假設(shè)在未進(jìn)行分片之前，區(qū)塊鏈中的拜占庭節(jié)點(diǎn)比例為f(0 ≤f＜1/3)，L表示一個(gè)分片中節(jié)點(diǎn)的數(shù)量。對(duì)于L中的每一個(gè)節(jié)點(diǎn)在進(jìn)行共識(shí)的時(shí)候都會(huì)依據(jù)自己的身份進(jìn)行驗(yàn)證，拜占庭或者非拜占庭身份。

令X=，其中Xi表示第i個(gè)節(jié)點(diǎn)表現(xiàn)出了拜占庭身份，X表示當(dāng)前片中拜占庭節(jié)點(diǎn)總個(gè)數(shù)。由于Xi只能表現(xiàn)出拜占庭節(jié)點(diǎn)身份或者非拜占庭節(jié)點(diǎn)身份，且這兩個(gè)身份之間相互獨(dú)立，所以X服從Binomial(L,X,f)的二項(xiàng)分布，當(dāng)X≥L/3時(shí)，分片失效。如公式（1）所示：

2.2.1 分片內(nèi)節(jié)點(diǎn)數(shù)與分片驗(yàn)證有效性的關(guān)系

根據(jù)公式（1），設(shè)置f=[0.1,0.2,0.3]，改變L的值，用Python模擬研究L對(duì)P的影響情況。如表1所示。

表1 分片內(nèi)節(jié)點(diǎn)數(shù)L 對(duì)單分片失效概率P 的影響

根據(jù)表1，在拜占庭節(jié)點(diǎn)比例f不變時(shí)，單個(gè)分片失效的概率隨著分片中節(jié)點(diǎn)數(shù)目的增大而減??；當(dāng)f=0.3，L=60 時(shí)，單個(gè)分片失效的概率超過(guò)0.3；即使L=600，單個(gè)分片失效的概率在f=0.3 時(shí)仍大于0.04，這仍是一個(gè)不可接受的值，并且分片內(nèi)節(jié)點(diǎn)數(shù)目過(guò)多限制了分片規(guī)模。當(dāng)分片內(nèi)節(jié)點(diǎn)數(shù)目L不變時(shí)，在f=0.3的較高拜占庭比例下，單個(gè)分片的驗(yàn)證有效性迅速降低。

2.2.2 拜占庭節(jié)點(diǎn)比例與單個(gè)分片驗(yàn)證有效性的關(guān)系

根據(jù)公式（1），設(shè)定L=600 的情況下，研究不同數(shù)值的拜占庭節(jié)點(diǎn)比例f對(duì)于單個(gè)分片失效概率P的影響。如表2所示。

表2 拜占庭節(jié)點(diǎn)比例f 對(duì)單分片失效概率P 的影響

根據(jù)表2，當(dāng)L=600，f≤0.25 時(shí)，單個(gè)分片失效的概率很小。隨著f不斷接近1/3，單分片失效的概率出現(xiàn)指數(shù)類型增長(zhǎng)，這將使得該分片幾乎失去了驗(yàn)證有效性，難以達(dá)成驗(yàn)證共識(shí)。單個(gè)分片的驗(yàn)證有效性成為了影響整個(gè)區(qū)塊鏈TPS的瓶頸。

2.3 所有分片都正常工作的概率的分析

在進(jìn)行分片的區(qū)塊鏈中，區(qū)塊鏈的整體TPS受限于單個(gè)分片的驗(yàn)證有效性。在分片后，若想提升區(qū)塊鏈的并行驗(yàn)證能力，需要保證每個(gè)分片內(nèi)的驗(yàn)證有效性。

下面計(jì)算分析分片之后所有分片都能正常工作的概率。假設(shè)：

區(qū)塊鏈中總節(jié)點(diǎn)數(shù)目為n；拜占庭節(jié)點(diǎn)比例為f(0 ≤f＜1/3)；每個(gè)分片中的節(jié)點(diǎn)數(shù)目為L(zhǎng)；分片規(guī)模為k；分片后第i個(gè)分片中的拜占庭節(jié)點(diǎn)比例為fi′，節(jié)點(diǎn)進(jìn)入到任意分片概率相同。若想保證所有分片不失效，需要保證每個(gè)分片內(nèi)的拜占庭節(jié)點(diǎn)的比例fi′＜1/3，為了追求結(jié)果的準(zhǔn)確性，采用窮舉遍歷的方法，列舉出所有滿足分片都不失效的情況，如公式（2）所示。其中對(duì)于公式（2）有兩個(gè)限定條件，分別為公式（3）、（4）。

在公式（3）中，i1表示第1 個(gè)分片內(nèi)可能的拜占庭節(jié)點(diǎn)數(shù)目；i2表示第2 個(gè)分片內(nèi)可能的拜占庭節(jié)點(diǎn)數(shù)目；ij表示第j(1 ≤j≤k)個(gè)分片內(nèi)可能的拜占庭節(jié)點(diǎn)數(shù)目；所有滿足公式（3）的序列均被放入到集合B中。

對(duì)于公式（4），借鑒貪心算法思想，若保證每個(gè)分片都能正常運(yùn)行，每個(gè)分片中保持分片驗(yàn)證有效性的同時(shí)盡可能多地容納拜占庭節(jié)點(diǎn)。假設(shè)前k-1 個(gè)分片中在保證不失效的情況下盡可能多地存儲(chǔ)了拜占庭節(jié)點(diǎn)數(shù)，則第k個(gè)分片中可能的拜占庭節(jié)點(diǎn)數(shù)目分為兩種情況：一種是拜占庭節(jié)點(diǎn)數(shù)目已經(jīng)都分配到前k-1 個(gè)分片中，那么第k個(gè)分片中的拜占庭節(jié)點(diǎn)數(shù)目為0。另一種情況是前面k-1 個(gè)分片盡管盡可能多地分配了拜占庭節(jié)點(diǎn)，但仍有剩余，則剩下的拜占庭節(jié)點(diǎn)全部分配到第k個(gè)分片中。故第k個(gè)分片中的拜占庭節(jié)點(diǎn)的取值為0之間的較大值。

由于Pr的值受分片個(gè)數(shù)k、拜占庭比例f、分片內(nèi)節(jié)點(diǎn)數(shù)L的影響，采用控制變量的方法，分別研究f、L、k對(duì)Pr的影響。

2.3.1 分片內(nèi)節(jié)點(diǎn)數(shù)與所有分片都不失效的關(guān)系

根據(jù)上述2.2.1小節(jié)的分析，總結(jié)出分片內(nèi)節(jié)點(diǎn)數(shù)L會(huì)對(duì)分片的驗(yàn)證有效性造成影響。探究L與Pr的關(guān)系，需要控制分片個(gè)數(shù)和拜占庭節(jié)點(diǎn)比例不變。本文主要研究高拜占庭節(jié)點(diǎn)比例下分片的失效概率，故選取f=0.3；分片個(gè)數(shù)k=4 是保證分片規(guī)模有效的合理有效值，固定這兩個(gè)值可準(zhǔn)確地研究有效分片規(guī)模與高拜占庭比例下分片內(nèi)節(jié)點(diǎn)數(shù)L對(duì)所有分片都不失效的概率值Pr影響。圖2 是基于公式（2）～（4）模擬k=4，f=0.3，分片中節(jié)點(diǎn)數(shù)目L對(duì)所有分片都不失效的概率影響圖。

圖2 L 對(duì)于Pr 的影響

圖2顯示，增加分片內(nèi)的節(jié)點(diǎn)數(shù)在一定程度上能提高分片不失效的概率，但所有分片不失效的概率依然很低，且隨著不斷增加分片內(nèi)節(jié)點(diǎn)數(shù)，Pr增大的幅度也在減小，僅增大分片中的節(jié)點(diǎn)數(shù)目在f=0.3 的較高拜占庭比例下仍無(wú)法解決分片失效率高的問(wèn)題。

2.3.2 拜占庭比例與所有分片都不失效的關(guān)系

根據(jù)2.2.2小節(jié)分析，得出拜占庭節(jié)點(diǎn)比例對(duì)于分片驗(yàn)證有效性的影響很大，參考文獻(xiàn)[14]，單個(gè)分片內(nèi)節(jié)點(diǎn)數(shù)適中為宜，故單個(gè)分片內(nèi)的節(jié)點(diǎn)數(shù)設(shè)定為L(zhǎng)=180，根據(jù)公式（2）～（4），計(jì)算在n=720,L=180,k=4 時(shí)，不同的拜占庭節(jié)點(diǎn)比例f與所有分片都正常工作的概率Pr的關(guān)系，如圖3所示。

圖3 f 對(duì)Pr 的影響

依據(jù)圖3，當(dāng)每個(gè)分片中的節(jié)點(diǎn)數(shù)目固定時(shí)，所有分片正常工作的概率隨著拜占庭節(jié)點(diǎn)比例的增大而減小。當(dāng)拜占庭節(jié)點(diǎn)比例f=0.25 時(shí)，所有分片正常工作的概率為0.034；當(dāng)拜占庭節(jié)點(diǎn)比例f=0.3 時(shí)，所有分片正常工作的概率為0.015。較高拜占庭節(jié)點(diǎn)比例對(duì)分片驗(yàn)證有效性影響較大。

2.3.3 分片規(guī)模與所有分片都不失效的關(guān)系

根據(jù)公式，計(jì)算在L=180，f=0.3 時(shí)，不同的分片規(guī)模k對(duì)所有分片都不失效的概率的影響。結(jié)果如圖4所示。

圖4 k 對(duì)Pr 的影響

在區(qū)塊鏈分片中，增加分片規(guī)模會(huì)使得系統(tǒng)的吞吐量線性增加，但分片規(guī)模的增加會(huì)使得分片的驗(yàn)證有效性降低。當(dāng)k=3 時(shí)，所有分片正常工作的概率為0.022 3，而當(dāng)分片規(guī)模k=10 時(shí)，所有分片全部正常工作的概率低于0.005，此時(shí)分片已基本失去了驗(yàn)證有效性。

3 多輪共識(shí)方案設(shè)計(jì)

通過(guò)第2 章量化影響分片驗(yàn)證有效性的各變量之間的關(guān)系，數(shù)據(jù)表明當(dāng)拜占庭節(jié)點(diǎn)比例f較高時(shí)，擴(kuò)大分片規(guī)模k，分片內(nèi)驗(yàn)證有效性P降低。當(dāng)拜占庭節(jié)點(diǎn)比例f越接近于1/3，單個(gè)分片失效的概率P越高，所有分片都不失效的概率Pr也就越小，單個(gè)分片的驗(yàn)證有效性將成為提高區(qū)塊鏈TPS的關(guān)鍵，擴(kuò)大分片規(guī)模則又是解決當(dāng)前區(qū)塊鏈擴(kuò)容瓶頸的重要方法。在這樣一個(gè)難兩全的環(huán)境下，本文提出多輪PBFT共識(shí)驗(yàn)證的方案，通過(guò)擴(kuò)大分片規(guī)模，并降低分片驗(yàn)證失效率，力圖使區(qū)塊鏈整體TPS顯著提高。

多輪驗(yàn)證方案的主要思想為當(dāng)一筆交易根據(jù)映射規(guī)則被分配到一個(gè)既定的分片后，由此分片中的所有節(jié)點(diǎn)對(duì)分片中的交易進(jìn)行共識(shí)驗(yàn)證。如果共識(shí)驗(yàn)證成功，則將交易打包進(jìn)區(qū)塊。如果交易驗(yàn)證超時(shí)未得到有效共識(shí)，可依據(jù)節(jié)點(diǎn)的隨機(jī)分配算法重新分配一組新的節(jié)點(diǎn)到該分片，對(duì)此交易進(jìn)行新一輪共識(shí)驗(yàn)證。

在拜占庭節(jié)點(diǎn)比例較高的情況下，如果連續(xù)經(jīng)過(guò)T次都沒有達(dá)成共識(shí)，將選擇放棄該筆交易，犧牲交易的可用性，同時(shí)要求放棄一筆交易的概率ε＜10-7。

對(duì)于輪數(shù)T的上限，在3.1節(jié)中給出。對(duì)于節(jié)點(diǎn)隨機(jī)分配算法，在3.2節(jié)中描述。

3.1 多輪輪數(shù)的選擇

3.1.1 拜占庭節(jié)點(diǎn)合謀的概率

在拜占庭節(jié)點(diǎn)比例比較高的情況下，可能在某個(gè)分片內(nèi)拜占庭節(jié)點(diǎn)占據(jù)大多數(shù)，且相互串通，進(jìn)行合謀攻擊。此時(shí)，盡管主節(jié)點(diǎn)收集到足夠多的消息，但是這些確認(rèn)消息是拜占庭節(jié)點(diǎn)之間串通合謀發(fā)送給主節(jié)點(diǎn)的，使得最終達(dá)成錯(cuò)誤的共識(shí)。

若想在某個(gè)分片內(nèi)進(jìn)行合謀攻擊，則要求此分片中至少含有(2×L)/3+1 個(gè)拜占庭節(jié)點(diǎn)且進(jìn)行合謀，但這是比較困難的。假設(shè)當(dāng)該分片中的拜占庭節(jié)點(diǎn)數(shù)目大于(2×L)/3，則串通在一起進(jìn)行合謀。X表示分配到該分片中的節(jié)點(diǎn)總數(shù)，L表示分片內(nèi)節(jié)點(diǎn)數(shù)。X符合Binomial(L,X,f)的二項(xiàng)分布。如公式（5）所示：

根據(jù)公式（5）運(yùn)用python模擬計(jì)算出在不同的拜占庭比例f和單個(gè)分片內(nèi)不同的節(jié)點(diǎn)數(shù)目L下，該分片中的拜占庭節(jié)點(diǎn)發(fā)生合謀的概率，見表3。

表3 單個(gè)分片中拜占庭節(jié)點(diǎn)間合謀的概率

根據(jù)表3 發(fā)現(xiàn)，即使當(dāng)f=0.333，若保證單個(gè)分片中的節(jié)點(diǎn)數(shù)目超過(guò)60 個(gè)，該分片中的拜占庭節(jié)點(diǎn)達(dá)成合謀的概率β也會(huì)低于4×10-8。

3.1.2 拜占庭節(jié)點(diǎn)比例和分片內(nèi)節(jié)點(diǎn)數(shù)對(duì)輪數(shù)的影響

在拜占庭節(jié)點(diǎn)比例低的情況下，共識(shí)可以在較少的輪數(shù)t(1 ≤t＜T)內(nèi)結(jié)束。在4.1節(jié)實(shí)驗(yàn)中會(huì)得出在不同拜占庭比例下達(dá)成一輪共識(shí)的最少次數(shù)、最多次數(shù)和平均次數(shù)。最大共識(shí)次數(shù)T的取值范圍需要根據(jù)拜占庭節(jié)點(diǎn)不合作的概率和合謀的概率確定。T的下限是當(dāng)拜占庭節(jié)點(diǎn)合謀的概率小于10-7時(shí)的取值，T的上限是拜占庭節(jié)點(diǎn)不合作的概率低于10-7時(shí)的取值。保證最終共識(shí)超時(shí)的概率低于10-7時(shí)，計(jì)算出在不同的拜占庭比例f和分片中不同的節(jié)點(diǎn)數(shù)目L下，輪數(shù)T的取值范圍，如表4 所示。表5 分析了在L=60，不同輪數(shù)下，不同拜占庭節(jié)點(diǎn)比例與共識(shí)超時(shí)概率的關(guān)系。

表4 輪數(shù)T 在不同f 和L 下的取值范圍

表5 共識(shí)超時(shí)概率

通過(guò)表4 發(fā)現(xiàn)，隨著分片內(nèi)節(jié)點(diǎn)數(shù)的增多，對(duì)輪數(shù)影響不大。表5表明f=0.3 時(shí)，需要更多的輪數(shù)來(lái)保證可用性。

3.2 節(jié)點(diǎn)隨機(jī)分配算法

當(dāng)出現(xiàn)共識(shí)過(guò)程超時(shí)的情況時(shí)，需要對(duì)分片中的節(jié)點(diǎn)進(jìn)行新一輪的分配，節(jié)點(diǎn)隨機(jī)分配算法需要盡可能滿足具有比較高的隨機(jī)性和不可預(yù)測(cè)的特點(diǎn)?；诖耍x用VRF（Verifiable Random Function）作為節(jié)點(diǎn)隨機(jī)分配算法的隨機(jī)函數(shù)。VRF 隨機(jī)函數(shù)具有很好的隨機(jī)性和不可預(yù)測(cè)的特性。

在區(qū)塊鏈中，每個(gè)節(jié)點(diǎn)都具有節(jié)點(diǎn)地址和一對(duì)公私鑰。在需要進(jìn)行重新分配節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)i將輸入m通過(guò)數(shù)字簽名和哈希函數(shù)映射為固定長(zhǎng)度的輸出H[SIGi(m)]，即m→H[SIGi(m)]，其中m可以是節(jié)點(diǎn)的IP 地址或者是節(jié)點(diǎn)公鑰。對(duì)于任何輸入m，不同的調(diào)用節(jié)點(diǎn)i生成的數(shù)字簽名SIGi(m)是確定且唯一的；而對(duì)于不同輸入，哈希函數(shù)H的輸出具有隨機(jī)性，符合隨機(jī)性的特點(diǎn)。

為保證不可預(yù)測(cè)性，需要為VRF 隨機(jī)函數(shù)提供一個(gè)隨機(jī)的且不斷變化的種子。在本文的VRF 函數(shù)中，引入一個(gè)隨機(jī)的、不斷更新的種子參數(shù)G(h)，G(h)=H(Bh-1,Sk)，其中h為第h個(gè)區(qū)塊，Bh-1為上一區(qū)塊的哈希值。要求每個(gè)參與節(jié)點(diǎn)都需要和網(wǎng)絡(luò)中的兩個(gè)鄰居節(jié)點(diǎn)互換一個(gè)數(shù)字，Sk為每個(gè)參與的節(jié)點(diǎn)從鄰居節(jié)點(diǎn)獲得的數(shù)字集合?？梢钥闯觯珿(h)在每一輪都會(huì)發(fā)生變化，且與交易本身無(wú)關(guān)。當(dāng)G(h-1)是隨機(jī)的，則G(h)也是隨機(jī)的。因此惡意節(jié)點(diǎn)無(wú)法通過(guò)改變交易集去影響下一個(gè)種子的生成。符合所要求的不可預(yù)測(cè)性。

4 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

為驗(yàn)證本文方法確實(shí)能夠降低單個(gè)分片失效的概率，且多輪對(duì)交易的延遲確認(rèn)不會(huì)使得總體TPS 降低。實(shí)驗(yàn)以ELASTICO為基礎(chǔ)進(jìn)行，增加了多輪方案和節(jié)點(diǎn)的隨機(jī)分配方法，選用Linux 作為實(shí)驗(yàn)平臺(tái)，以Go 語(yǔ)言作為開發(fā)語(yǔ)言，以Docker和Goland作為開發(fā)工具，在每臺(tái)服務(wù)器的不同端口模擬不同的節(jié)點(diǎn)，實(shí)驗(yàn)數(shù)據(jù)用MATLAB進(jìn)行繪制。

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 實(shí)驗(yàn)環(huán)境設(shè)定

本文所設(shè)計(jì)的多輪方案，在使用之前需要設(shè)定下列條件：

（1）節(jié)點(diǎn)可以動(dòng)態(tài)加入和退出，假設(shè)在分片期間總節(jié)點(diǎn)數(shù)目保持均勻恒定。

（2）區(qū)塊鏈中節(jié)點(diǎn)的位置和網(wǎng)絡(luò)情況會(huì)影響達(dá)成共識(shí)的效率，實(shí)驗(yàn)在局域網(wǎng)內(nèi)進(jìn)行，P2P 網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)之間通信良好，延遲在可控范圍內(nèi)。

（3）在每一輪共識(shí)中，節(jié)點(diǎn)是否誠(chéng)實(shí)是可變的，即非拜占庭節(jié)點(diǎn)有可能在下一輪中變?yōu)榘菡纪ス?jié)點(diǎn)。

4.1.2 實(shí)驗(yàn)參數(shù)設(shè)置與實(shí)驗(yàn)流程

本文設(shè)計(jì)兩個(gè)對(duì)比實(shí)驗(yàn)，隨著拜占庭比例的變化，觀察對(duì)比首個(gè)區(qū)塊鏈分片方案ELASTICO、采用節(jié)點(diǎn)隨機(jī)分配算法并取得較好效果的Omniledger方案、多輪方案的單個(gè)分片的失效概率和平均TPS 的表現(xiàn)情況。在實(shí)驗(yàn)時(shí)，為了更能體現(xiàn)單一變量對(duì)結(jié)果的影響，需要對(duì)一些實(shí)驗(yàn)參數(shù)進(jìn)行設(shè)定，如下：

（1）總節(jié)點(diǎn)數(shù)目n=600；

（2）每個(gè)分片中的節(jié)點(diǎn)數(shù)L=60；

（3）拜占庭比例的取值為f=[0.1，0.15，0.2，0.25，0.28，0.3]；

（4）輪數(shù)T的值取為在f=0.3,L=60,ε＜10-7條件下的最多輪數(shù)。如圖5所示。

圖5 共識(shí)次數(shù)與拜占庭節(jié)點(diǎn)比例的關(guān)系

在圖5中，分別統(tǒng)計(jì)了在多輪方案中上述條件下輪數(shù)的最多、最少和平均情況。當(dāng)0 ≤f＜0.15 時(shí)，最多輪數(shù)、最少輪數(shù)、平均輪數(shù)均可在一輪內(nèi)結(jié)束；當(dāng)0.15 ≤f＜0.25 時(shí)，最多輪數(shù)的值在增大，但平均輪數(shù)和最少輪數(shù)仍可在一輪內(nèi)結(jié)束。當(dāng)0.25 ≤f≤0.3 時(shí)，最多輪數(shù)出現(xiàn)指數(shù)增長(zhǎng)的趨勢(shì)，平均輪數(shù)穩(wěn)定在兩輪，最少輪數(shù)仍可在一輪內(nèi)結(jié)束。

實(shí)驗(yàn)樣本：實(shí)驗(yàn)以局域網(wǎng)內(nèi)10 臺(tái)服務(wù)器的不同端口號(hào)模擬600個(gè)節(jié)點(diǎn)；在3.1.1小節(jié)的計(jì)算中，保證L＞60時(shí)合謀的概率即女巫攻擊成功的概率β＜4×10-8，故設(shè)定每個(gè)分片中的節(jié)點(diǎn)數(shù)為60。

實(shí)驗(yàn)中采用對(duì)收到消息不進(jìn)行轉(zhuǎn)發(fā)，來(lái)模擬拜占庭節(jié)點(diǎn)的行為：即拜占庭節(jié)點(diǎn)雖然收到了消息，但是不向主節(jié)點(diǎn)以及其他共識(shí)節(jié)點(diǎn)進(jìn)行反饋?；緦?shí)驗(yàn)流程如圖6所示。

圖6 多輪方案處理一筆交易流程

4.2 實(shí)驗(yàn)結(jié)果與分析

單個(gè)分片失效的概率受分片規(guī)模和區(qū)塊鏈中拜占庭節(jié)點(diǎn)比例的影響。實(shí)驗(yàn)1 模擬以n=600,L=60,T=7 為條件，隨著f的不斷變化，觀察ELASTICO 方案、Omniledger 方案、多輪方案與單個(gè)分片驗(yàn)證有效性的關(guān)系。實(shí)驗(yàn)結(jié)果分別如圖7所示。

圖7 不同拜占庭比例下兩種方案中單個(gè)分片失效概率

在實(shí)驗(yàn)1中，當(dāng)f＜0.15 時(shí)，三種方案在單個(gè)分片失效的概率上都很低；當(dāng)0.15 ≤f＜0.25 時(shí)，ELASTICO 方案出現(xiàn)了失效概率增大的情況，Omniledger 方案和多輪方案表現(xiàn)仍然良好；當(dāng)0.25 ≤f≤0.3 時(shí)，ELASTICO方案的單分片失效的概率值出現(xiàn)了指數(shù)型增長(zhǎng)，Omniledger方案的單分片失效概率值出現(xiàn)了小幅增長(zhǎng)，這是由于在Omniledger 中節(jié)點(diǎn)隨機(jī)分配算法盡管在一定程度上可降低分片失效的概率，但是無(wú)法根本解決較高拜占庭比例下拜占庭節(jié)點(diǎn)聚集的問(wèn)題；多輪中單個(gè)分片失效的概率值盡管也出現(xiàn)了增長(zhǎng)，但在f=0.3 情況下值依然較小，這是因?yàn)樵谀硞€(gè)分片中連續(xù)多輪拜占庭節(jié)點(diǎn)發(fā)生累次聚集的概率極小，因此更能保證單個(gè)分片的驗(yàn)證有效性。

本文的目的是保證分片驗(yàn)證有效性的同時(shí)，顯著提高分片規(guī)模，確保整體區(qū)塊鏈TPS 提升，故實(shí)驗(yàn)2 模擬以n=600,L=60,T=7 為條件，隨著f的不斷變化，調(diào)整拜占庭節(jié)點(diǎn)數(shù)目，觀察ELASTICO 方案、Omniledger方案和多輪方案TPS的表現(xiàn)情況。結(jié)果如圖8所示。

圖8 不同拜占庭節(jié)點(diǎn)比例下兩種方案TPS表現(xiàn)情況

在實(shí)驗(yàn)2中，隨著拜占庭節(jié)點(diǎn)比例的不斷增大，三種方案的TPS值均在降低。當(dāng)0.1 ≤f≤0.15 時(shí)，ELASTICO方案和Omniledger方案的平均TPS比多輪方案稍高；當(dāng)0.15 ＜f≤0.2 時(shí)，三種方案TPS 值差距很?。划?dāng)0.2 ＜f≤0.3，ELASTICO 的TPS 急劇下降，Omniledger 方案的TPS 也在迅速下降，但整體TPS 較ELASTICO 稍優(yōu)，多輪方案盡管也出現(xiàn)了下降，但下降幅度稍緩，且整體TPS均優(yōu)于前兩種方案。

在多輪PBFT 共識(shí)驗(yàn)證算法中，在吞吐量方面，T輪共識(shí)驗(yàn)證雖然使得單個(gè)分片的交易確認(rèn)得到延遲，但保證了單個(gè)分片具有更高的驗(yàn)證有效性；同時(shí)，因分片的個(gè)數(shù)已增至M(M?k)，平均共識(shí)驗(yàn)證輪數(shù)為t，總體區(qū)塊鏈TPS提高M(jìn)/t倍。在保證單個(gè)分片中的節(jié)點(diǎn)數(shù)目不低于60 時(shí)，可使得單個(gè)分片中的拜占庭節(jié)點(diǎn)達(dá)成合謀攻擊的概率低至4×10-8。兩個(gè)實(shí)驗(yàn)綜合表明：減少分片內(nèi)節(jié)點(diǎn)數(shù)、擴(kuò)大分片規(guī)模、增加輪數(shù)驗(yàn)證，比分片規(guī)模較小、分片內(nèi)節(jié)點(diǎn)數(shù)較多的單輪驗(yàn)證方案，總體驗(yàn)證有效性更好、區(qū)塊鏈TPS更高。

5 總結(jié)

本文針對(duì)分片規(guī)模與分片內(nèi)驗(yàn)證有效性的矛盾：“在分片內(nèi)采用PBFT共識(shí)算法時(shí)，因擴(kuò)大分片規(guī)模，使分片內(nèi)驗(yàn)證有效性降低”提出多輪PBFT共識(shí)驗(yàn)證方案，找到輪數(shù)的一個(gè)合理取值，并通過(guò)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對(duì)比分析，確認(rèn)了多輪方案能夠在保持分片驗(yàn)證有效性的同時(shí)，提高區(qū)塊鏈總體TPS。

分片技術(shù)作為解決區(qū)塊鏈擴(kuò)容問(wèn)題的關(guān)鍵技術(shù)，受到越來(lái)越多項(xiàng)目和學(xué)者的關(guān)注，因此本文對(duì)于區(qū)塊鏈分片的多輪驗(yàn)證研究很有后續(xù)參考價(jià)值。進(jìn)一步，分片內(nèi)的多輪共識(shí)驗(yàn)證方法，還可以改進(jìn)，以抵抗分片內(nèi)的合謀攻擊。