聯(lián)合分布算法對(duì)區(qū)塊鏈分片的穩(wěn)定性分析優(yōu)化研究

劉 云， 朱鵬俊， 陳路遙， 宋 凱

(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院， 昆明 650500)

1 引 言

基于Hyperledger Fabric架構(gòu)的區(qū)塊鏈網(wǎng)絡(luò)可以通過(guò)分片實(shí)現(xiàn)吞吐量的提高，但分片會(huì)降低區(qū)塊鏈的穩(wěn)定性，因此需要在分片前針對(duì)各個(gè)委員會(huì)失敗概率進(jìn)行預(yù)評(píng)估，得到具有較高穩(wěn)定性的分片方案[1-6].

Hafid等提出的使用Hoeffding邊界算法分析區(qū)塊鏈協(xié)議的穩(wěn)定性，計(jì)算單個(gè)委員會(huì)的失敗概率并乘以委員會(huì)數(shù)量得到分片失敗概率的精確邊界，適用于二項(xiàng)分布和超幾何分布的隨機(jī)變量[7].Zamani等提出了一種RapidChain方案，其中的穩(wěn)定性分析算法使用超幾何分布對(duì)分片節(jié)點(diǎn)進(jìn)行建模采樣，能準(zhǔn)確地計(jì)算單個(gè)分片失敗概率，但在計(jì)算整體分片失敗概率時(shí)存在一定局限性[8].

為了能夠更好地分析區(qū)塊鏈分片的穩(wěn)定性，提出了一種基于Hyperledger Fabric架構(gòu)下區(qū)塊鏈分片的聯(lián)合分布(Joint Distribution,JD)算法.首先，針對(duì)預(yù)分片的節(jié)點(diǎn)，按預(yù)分片方案的委員會(huì)數(shù)量進(jìn)行不放回的隨機(jī)抽樣，從而獲得每個(gè)委員會(huì)中節(jié)點(diǎn)的超幾何分布；其次，根據(jù)節(jié)點(diǎn)的超幾何分布計(jì)算每個(gè)委員會(huì)中含有惡意節(jié)點(diǎn)的概率 ，并構(gòu)建所有委員會(huì)的聯(lián)合分布函數(shù)；最后，根據(jù)所有委員會(huì)的聯(lián)合分布函數(shù)計(jì)算整個(gè)分片方案的失敗概率和失敗年限，從而提高區(qū)塊鏈分片穩(wěn)定性分析的精準(zhǔn)度.

2 分片模型與穩(wěn)定性評(píng)估

2.1 分片模型

圖1 分片模型Fig.1 Sharding model

在分片模型中，將評(píng)估分片的穩(wěn)定性量化為測(cè)量分片失敗概率和分片失敗年限等參數(shù)[10]，分片的失敗概率越低、失敗年限越長(zhǎng)，分片的穩(wěn)定性越好；反之穩(wěn)定性越差.

2.2 穩(wěn)定性參數(shù)測(cè)量模型

在基于分片的區(qū)塊鏈協(xié)議中，分片中若存在至少一個(gè)委員會(huì)被破壞，則整個(gè)區(qū)塊鏈網(wǎng)絡(luò)就會(huì)被破壞，即單分片接管攻擊[11].因此完成一次分片的失敗概率fp是指在一次分片中至少有一個(gè)委員會(huì)失敗的概率，平均失敗年限Yf則是根據(jù)失敗概率和每年的分片次數(shù)進(jìn)行計(jì)算的平均年限.

圖2 穩(wěn)定性參數(shù)測(cè)量的主要流程Fig.2 The main flow of the stability parameter measurement

穩(wěn)定性參數(shù)通常是按圖2模型的順序進(jìn)行計(jì)算，模型的輸入為預(yù)分片方案的參數(shù)N,M,n.首先，根據(jù)輸入的參數(shù)對(duì)節(jié)點(diǎn)進(jìn)行建模抽樣，獲得單個(gè)委員會(huì)的分布模型Xi；其次，通過(guò)單個(gè)委員會(huì)的分布計(jì)算出所有委員會(huì)的整體失敗概率P，并根據(jù)委員會(huì)彈性r以及區(qū)塊鏈整體彈性R獲得委員會(huì)中惡意節(jié)點(diǎn)數(shù)的所有情況；最后，可以計(jì)算出完成一次分片的失敗概率fp和平均失敗年限Yf.在得出這兩個(gè)參數(shù)后，分析失敗概率fp和失敗年限Yf是否滿足分片穩(wěn)定性要求，若分片失敗概率過(guò)高、失敗年限過(guò)短會(huì)導(dǎo)致分片的穩(wěn)定性不高，容易被惡意節(jié)點(diǎn)攻擊，需要改變委員會(huì)節(jié)點(diǎn)數(shù)n以提高分片的穩(wěn)定性.

除前文中定義的參數(shù)，另外還定義了一些名詞屬性，如下.

定義1委員會(huì)彈性r:委員會(huì)在安全情況下能夠包含的惡意節(jié)點(diǎn)的最大百分比.多數(shù)區(qū)塊鏈分片協(xié)議中這個(gè)彈性為33%[12，13]，在RapidChain區(qū)塊鏈分片協(xié)議中這個(gè)彈性為50%[8].

定義2區(qū)塊鏈整體彈性R：區(qū)塊鏈在安全情況下能夠包含的惡意節(jié)點(diǎn)的最大百分比.多數(shù)區(qū)塊鏈分片協(xié)議中這個(gè)彈性為25%[12，13]，在RapidChain區(qū)塊鏈分片協(xié)議中這個(gè)彈性為33%[8].

3 聯(lián)合分布(JD)算法

3.1 JD算法

在區(qū)塊鏈網(wǎng)絡(luò)中，分配節(jié)點(diǎn)到委員會(huì)的過(guò)程可以建模成不放回的隨機(jī)抽樣.目前常用的分片規(guī)范是基于二項(xiàng)分布的，無(wú)法正確建模采樣.當(dāng)樣本不放回時(shí)，分片中的采樣與超幾何分布相匹配，相比二項(xiàng)分布具有更好的逼近性[14].因此，本文提出的聯(lián)合分布(JD)算法是基于超幾何分布來(lái)分配節(jié)點(diǎn)至各個(gè)委員會(huì)中.

根據(jù)圖1中的分片模型以及參數(shù)，按圖3的流程計(jì)算分片失敗概率和失敗年限.

圖3 聯(lián)合分布穩(wěn)定性評(píng)估模型Fig.3 Joint distribution stability evaluation model

每個(gè)委員會(huì)的分布可以通過(guò)參數(shù)N，M和n的超幾何分布建模，超幾何分布的表達(dá)式如式(1).

X～H(N,M,n)

(1)

因此，根據(jù)式(1)，可以依次確切的構(gòu)建每個(gè)委員會(huì)的分布模型，如式(2)為第一個(gè)委員會(huì)的分布.

X1～H(N,M,n)

(2)

同樣可以寫出第二個(gè),第三個(gè)委員會(huì)以及第λ個(gè)委員會(huì)的分布，如式(3)～(5).

X2～H(N-n,M-m1,n)

(3)

X3～H(N-2n,M-(m1+m2),n)

(4)

(5)

根據(jù)每個(gè)委員會(huì)的分布，可以計(jì)算第一個(gè)至第λ個(gè)委員會(huì)中抽到mi(i=1,2,…,λ)個(gè)惡意節(jié)點(diǎn)的概率.則第一個(gè)委員會(huì)的概率和第λ個(gè)委員會(huì)的概率函數(shù)[15]分別為式(6)和式(7).

P(X1=m1)=h(N,M,n,m1)=

(6)

P(Xλ=mλ)=

(7)

聯(lián)合各委員會(huì)的概率函數(shù)P(X=mi)，可推出X=(X1,X2,…,Xλ)，即λ個(gè)委員會(huì)的聯(lián)合分布函數(shù)如式(8)所示.

P(X)=P(X1=m1,X2=m2,…,Xλ=mλ)=

P(X1=m1)×P(X2=m2)×…×P(Xλ=mλ)=

h(N,M,n,m1)×h(N-n,M-m1,n,m2)×

(8)

(9)

根據(jù)定理3.1，可以將式(8)中的復(fù)雜分布計(jì)算簡(jiǎn)化為式(10)，

P(X1=m1,X2=m2,…,Xλ=mλ)=

(10)

第一個(gè)委員會(huì)中的m1個(gè)惡意節(jié)點(diǎn)可以假設(shè)以下值中的任意一個(gè):n,n-1,…,1,0.同樣，第二個(gè)委員會(huì)中的m2惡意節(jié)點(diǎn)可以假設(shè)以下任意值:n,n-1,…,1,0，以此類推，直到最后一個(gè)委員會(huì).因此，式(8)和式(10)中的分布只表示一種特定的結(jié)果.為了計(jì)算所有可能的結(jié)果，即滿足每個(gè)委員會(huì)中惡意節(jié)點(diǎn)數(shù)不超過(guò)委員會(huì)彈性限度，需要計(jì)算這些情況的聯(lián)合超幾何分布，表達(dá)式如下式(11).

P(X1≤nr,X2≤nr,…,Xλ≤nr)=

(11)

最后，分片失敗概率(至少一個(gè)委員會(huì)失敗的概率)可以表示為式(12).

fp=1-P(X1≤nr,X2≤nr,…,Xλ≤nr)

(12)

在聯(lián)合分布的計(jì)算過(guò)程中，計(jì)算出每個(gè)委員會(huì)的分布函數(shù)，消除了每個(gè)委員會(huì)失敗概率不獨(dú)立的問(wèn)題，可以更加精準(zhǔn)的估計(jì)出切片失敗的概率.但即使式(8)到式(10)的計(jì)算得到簡(jiǎn)化，式(12)中的概率仍然復(fù)雜難以計(jì)算，尤其是在考慮到大量的節(jié)點(diǎn)時(shí)，因此只能估計(jì)該概率，而不是精準(zhǔn)計(jì)算.

(13)

因此可以通過(guò)估計(jì)的失敗概率來(lái)較精準(zhǔn)的得到準(zhǔn)確失敗概率，并能降低計(jì)算復(fù)雜度.

另外根據(jù)完成一次分片的失敗概率fp，可以計(jì)算分片的失敗年限.平均失敗年數(shù)的計(jì)算如式(14).

(14)

3.2 算法估計(jì)性能分析

為了確定估計(jì)失敗概率的準(zhǔn)確性，選擇計(jì)算最準(zhǔn)確、最可靠的Wilson置信區(qū)間[17，18]，如式(15).

n=u+v，p=u/n，

(15)

其中，S為Wilson置信區(qū)間算法公式；n為樣本總數(shù)；u為誠(chéng)實(shí)節(jié)點(diǎn)數(shù)；v為惡意節(jié)點(diǎn)數(shù)；Zα表示對(duì)應(yīng)某個(gè)置信水平的統(tǒng)計(jì)量，如在95%的置信水平下，Zα=1.96.使用Wilson置信區(qū)間計(jì)算上下邊界以更好地限制和估計(jì)失敗概率.

Hafid等[7]在分析和比較Hoeffding，Chebyshev和 Chvátal邊界計(jì)算區(qū)塊鏈分片的失敗概率時(shí)，使用Hoeffding邊界計(jì)算的失敗概率會(huì)較另兩種更低，取Hoeffding邊界為更好的分片失敗概率近似值，可以更好的分析區(qū)塊鏈分片協(xié)議的穩(wěn)定性.據(jù)此在本文中算法計(jì)算分片失敗概率越小，失敗年限越大越能說(shuō)明算法能夠提供更好的穩(wěn)定性估計(jì).

4 仿真分析

4.1 仿真環(huán)境

為了估算由JD算法計(jì)算的分片失敗概率，使用了NumPy Python庫(kù)進(jìn)行實(shí)驗(yàn)，該庫(kù)提供了數(shù)學(xué)函數(shù)和隨機(jī)數(shù)生成器等.另外，還使用numpy.array()來(lái)建立一個(gè)包含M個(gè)惡意節(jié)點(diǎn)和N-M個(gè)誠(chéng)實(shí)節(jié)點(diǎn)的數(shù)組.還使用了numpy.random.choice()將節(jié)點(diǎn)進(jìn)行隨機(jī)分布，而無(wú)需在分片上替換這些節(jié)點(diǎn).在配備i7-2677M CPU 1.80 GHz和6 GB RAM的PC上運(yùn)行實(shí)驗(yàn).

4.2 置信區(qū)間

在N=1000，M=250的區(qū)塊鏈網(wǎng)絡(luò)模型中，計(jì)算了在改變單個(gè)委員會(huì)中節(jié)點(diǎn)數(shù)n分別為125,200,250和實(shí)驗(yàn)次數(shù)Nt為104,105,106時(shí)使用JD算法的估計(jì)失敗概率.為了更好地限定和估計(jì)失敗概率，也計(jì)算了在置信水平為95%時(shí)的Wilson置信區(qū)間的上下限，這意味著，有95%的正確率確定估計(jì)的失敗概率能在Wilson的上下限之間.表1數(shù)據(jù)顯示計(jì)算的失敗概率落在置信區(qū)間的上下限之間，驗(yàn)證了JD算法計(jì)算的分片失敗概率是準(zhǔn)確可靠的.

表1 不同實(shí)驗(yàn)次數(shù)和委員會(huì)節(jié)點(diǎn)數(shù)的估計(jì)失敗概率及Wilson置信區(qū)間

4.3 失敗概率分析

為了評(píng)估算法計(jì)算的分片失敗概率，我們?cè)趦煞N參數(shù)的場(chǎng)景下進(jìn)行了實(shí)驗(yàn)：(a)N=1000，M=250，Nt=106；(b)N=4000，M=1333，Nt=106.兩種場(chǎng)景分別為兩種主流區(qū)塊鏈分片協(xié)議下能容忍的最大惡意節(jié)點(diǎn)數(shù)，若惡意節(jié)點(diǎn)占比更低，穩(wěn)定性的分析效果會(huì)更好.在場(chǎng)景(a)中改變單個(gè)委員會(huì)節(jié)點(diǎn)數(shù)量n=100～250，在場(chǎng)景(b)中改變單個(gè)委員會(huì)節(jié)點(diǎn)數(shù)量n=30～500時(shí)的分片估計(jì)失敗概率，并與Hoeffding邊界算法和 RapidChain的分片穩(wěn)定性分析算法進(jìn)行了比較.

圖4(a)和(b)中總體顯示，分片的失敗概率會(huì)隨單個(gè)委員會(huì)中的節(jié)點(diǎn)數(shù)n的增加而降低，這是因?yàn)槲瘑T會(huì)中節(jié)點(diǎn)數(shù)量的增加，惡意節(jié)點(diǎn)的占比容易降低，惡意節(jié)點(diǎn)接管分片的難度會(huì)增大，從而降低分片失敗概率.在場(chǎng)景(a)和(b)中當(dāng)n較小時(shí)，Hoeffding邊界算法的走勢(shì)較為陡峭，說(shuō)明Hoeffding邊界算法在委員會(huì)節(jié)點(diǎn)數(shù)較少時(shí)的準(zhǔn)確性差. 在圖4(a)和(b)中能觀察到Hoeffding和RapidChain都有失敗概率超過(guò)1的時(shí)候，這是因?yàn)檫@兩種算法都只計(jì)算了第一個(gè)委員會(huì)的失敗概率并將其乘以委員會(huì)的數(shù)量，從而導(dǎo)致計(jì)算概率的不準(zhǔn)確.另外在場(chǎng)景(a)和(b)中，JD算法計(jì)算的分片失敗概率都較另外兩種算法更低，且不會(huì)超過(guò)1，這是因?yàn)镴D算法采用了適當(dāng)?shù)母怕史植紒?lái)計(jì)算，相比之下JD算法提供了更好的分片失敗概率估計(jì).

圖4 場(chǎng)景(a)和(b)中三種算法的失敗概率

4.4 失敗年限分析

評(píng)估算法計(jì)算的區(qū)塊鏈分片的平均失敗年限，在兩種參數(shù)的場(chǎng)景下進(jìn)行了實(shí)驗(yàn)：(a)N=1000，M=250，Nt=106；(b)N=4000，M=1333，Nt=106.固定每年的分片次數(shù)，Nsy=365，計(jì)算在場(chǎng)景(a)中改變單個(gè)委員會(huì)節(jié)點(diǎn)數(shù)量n=100～250，在場(chǎng)景(b)中改變單個(gè)委員會(huì)節(jié)點(diǎn)數(shù)量n=30～500時(shí)的平均失敗年限，并與Hoeffding邊界算法和 RapidChain的分片穩(wěn)定性分析算法進(jìn)行了比較.

圖5(a)和(b)中總體顯示，隨著委員會(huì)中節(jié)點(diǎn)數(shù)的增多，失敗年限會(huì)升高，這是因?yàn)閱蝹€(gè)委員會(huì)的節(jié)點(diǎn)數(shù)增多，惡意節(jié)點(diǎn)在委員會(huì)中的占比就容易降低，分片越難以被攻擊，使失敗前的預(yù)期分片次數(shù)Es增加，從而導(dǎo)致失敗年限減少.圖5(a)和(b)中Hoeffding邊界算法計(jì)算的平均失敗年限在隨著委員會(huì)數(shù)量的增加時(shí)，并沒(méi)有什么明顯變化，說(shuō)明Hoeffding邊界算法在計(jì)算失敗年限時(shí)的不準(zhǔn)確；當(dāng)n較小時(shí)，RapidChain方法和JD算法計(jì)算的平均失敗年限相差不大，但n逐漸變大時(shí)，JD算法與RapidChain開始拉開差距，失敗年限也開始遠(yuǎn)多于另外兩種方案.相比之下，JD算法能夠更好地確定分片的失敗年限.

圖5 場(chǎng)景(a)和(b)中三種算法的平均失敗年限

5 結(jié) 論

區(qū)塊鏈分片會(huì)降低區(qū)塊鏈的穩(wěn)定性，需要對(duì)分片進(jìn)行穩(wěn)定性預(yù)評(píng)估，得到具有較高穩(wěn)定性的分片方案.JD算法在計(jì)算分片失敗概率和失敗年限時(shí)能提供更好的估計(jì)，從而更好地分析區(qū)塊鏈分片的穩(wěn)定性.算法首先針對(duì)預(yù)分片的節(jié)點(diǎn)，按預(yù)定委員會(huì)數(shù)量進(jìn)行不放回的隨機(jī)抽樣，從而獲得每個(gè)委員會(huì)中節(jié)點(diǎn)的超幾何分布，其次根據(jù)節(jié)點(diǎn)的超幾何分布計(jì)算每個(gè)委員會(huì)中含有惡意節(jié)點(diǎn)的概率，并構(gòu)建所有委員會(huì)的聯(lián)合分布函數(shù)，最后根據(jù)所有委員會(huì)的聯(lián)合分布函數(shù)計(jì)算整個(gè)分片方案的失敗概率和失敗年限.通過(guò)計(jì)算Wilson置信區(qū)間確定JD算法計(jì)算結(jié)果是正確的，另外仿真結(jié)果表明，JD算法在計(jì)算分片失敗概率和分片失敗年限時(shí)有更好的估計(jì)，從而實(shí)現(xiàn)對(duì)分片穩(wěn)定性的精準(zhǔn)分析.區(qū)塊鏈分片是一個(gè)非常有挑戰(zhàn)性的方向，在研究分片的穩(wěn)定性問(wèn)題之后，將著手進(jìn)行區(qū)塊鏈分片方案的研究，在保證區(qū)塊鏈穩(wěn)定性的同時(shí)盡可能提高其吞吐量.