联合分布算法对区块链分片的稳定性分析优化研究

刘 云， 朱鹏俊， 陈路遥， 宋 凯

(昆明理工大学信息工程与自动化学院， 昆明 650500)

1 引 言

基于Hyperledger Fabric架构的区块链网络可以通过分片实现吞吐量的提高，但分片会降低区块链的稳定性，因此需要在分片前针对各个委员会失败概率进行预评估，得到具有较高稳定性的分片方案[1-6].

Hafid等提出的使用Hoeffding边界算法分析区块链协议的稳定性，计算单个委员会的失败概率并乘以委员会数量得到分片失败概率的精确边界，适用于二项分布和超几何分布的随机变量[7].Zamani等提出了一种RapidChain方案，其中的稳定性分析算法使用超几何分布对分片节点进行建模采样，能准确地计算单个分片失败概率，但在计算整体分片失败概率时存在一定局限性[8].

为了能够更好地分析区块链分片的稳定性，提出了一种基于Hyperledger Fabric架构下区块链分片的联合分布(Joint Distribution,JD)算法.首先，针对预分片的节点，按预分片方案的委员会数量进行不放回的随机抽样，从而获得每个委员会中节点的超几何分布；其次，根据节点的超几何分布计算每个委员会中含有恶意节点的概率 ，并构建所有委员会的联合分布函数；最后，根据所有委员会的联合分布函数计算整个分片方案的失败概率和失败年限，从而提高区块链分片稳定性分析的精准度.

2 分片模型与稳定性评估

2.1 分片模型

图1 分片模型Fig.1 Sharding model

在分片模型中，将评估分片的稳定性量化为测量分片失败概率和分片失败年限等参数[10]，分片的失败概率越低、失败年限越长，分片的稳定性越好；反之稳定性越差.

2.2 稳定性参数测量模型

在基于分片的区块链协议中，分片中若存在至少一个委员会被破坏，则整个区块链网络就会被破坏，即单分片接管攻击[11].因此完成一次分片的失败概率fp是指在一次分片中至少有一个委员会失败的概率，平均失败年限Yf则是根据失败概率和每年的分片次数进行计算的平均年限.

图2 稳定性参数测量的主要流程Fig.2 The main flow of the stability parameter measurement

稳定性参数通常是按图2模型的顺序进行计算，模型的输入为预分片方案的参数N,M,n.首先，根据输入的参数对节点进行建模抽样，获得单个委员会的分布模型Xi；其次，通过单个委员会的分布计算出所有委员会的整体失败概率P，并根据委员会弹性r以及区块链整体弹性R获得委员会中恶意节点数的所有情况；最后，可以计算出完成一次分片的失败概率fp和平均失败年限Yf.在得出这两个参数后，分析失败概率fp和失败年限Yf是否满足分片稳定性要求，若分片失败概率过高、失败年限过短会导致分片的稳定性不高，容易被恶意节点攻击，需要改变委员会节点数n以提高分片的稳定性.

除前文中定义的参数，另外还定义了一些名词属性，如下.

定义1委员会弹性r:委员会在安全情况下能够包含的恶意节点的最大百分比.多数区块链分片协议中这个弹性为33%[12，13]，在RapidChain区块链分片协议中这个弹性为50%[8].

定义2区块链整体弹性R：区块链在安全情况下能够包含的恶意节点的最大百分比.多数区块链分片协议中这个弹性为25%[12，13]，在RapidChain区块链分片协议中这个弹性为33%[8].

3 联合分布(JD)算法

3.1 JD算法

在区块链网络中，分配节点到委员会的过程可以建模成不放回的随机抽样.目前常用的分片规范是基于二项分布的，无法正确建模采样.当样本不放回时，分片中的采样与超几何分布相匹配，相比二项分布具有更好的逼近性[14].因此，本文提出的联合分布(JD)算法是基于超几何分布来分配节点至各个委员会中.

根据图1中的分片模型以及参数，按图3的流程计算分片失败概率和失败年限.

图3 联合分布稳定性评估模型Fig.3 Joint distribution stability evaluation model

每个委员会的分布可以通过参数N，M和n的超几何分布建模，超几何分布的表达式如式(1).

X～H(N,M,n)

(1)

因此，根据式(1)，可以依次确切的构建每个委员会的分布模型，如式(2)为第一个委员会的分布.

X1～H(N,M,n)

(2)

同样可以写出第二个,第三个委员会以及第λ个委员会的分布，如式(3)～(5).

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

(3)

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

(4)

(5)

根据每个委员会的分布，可以计算第一个至第λ个委员会中抽到mi(i=1,2,…,λ)个恶意节点的概率.则第一个委员会的概率和第λ个委员会的概率函数[15]分别为式(6)和式(7).

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

(6)

P(Xλ=mλ)=

(7)

联合各委员会的概率函数P(X=mi)，可推出X=(X1,X2,…,Xλ)，即λ个委员会的联合分布函数如式(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)

根据定理3.1，可以将式(8)中的复杂分布计算简化为式(10)，

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

(10)

第一个委员会中的m1个恶意节点可以假设以下值中的任意一个:n,n-1,…,1,0.同样，第二个委员会中的m2恶意节点可以假设以下任意值:n,n-1,…,1,0，以此类推，直到最后一个委员会.因此，式(8)和式(10)中的分布只表示一种特定的结果.为了计算所有可能的结果，即满足每个委员会中恶意节点数不超过委员会弹性限度，需要计算这些情况的联合超几何分布，表达式如下式(11).

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

(11)

最后，分片失败概率(至少一个委员会失败的概率)可以表示为式(12).

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

(12)

在联合分布的计算过程中，计算出每个委员会的分布函数，消除了每个委员会失败概率不独立的问题，可以更加精准的估计出切片失败的概率.但即使式(8)到式(10)的计算得到简化，式(12)中的概率仍然复杂难以计算，尤其是在考虑到大量的节点时，因此只能估计该概率，而不是精准计算.

(13)

因此可以通过估计的失败概率来较精准的得到准确失败概率，并能降低计算复杂度.

另外根据完成一次分片的失败概率fp，可以计算分片的失败年限.平均失败年数的计算如式(14).

(14)

3.2 算法估计性能分析

为了确定估计失败概率的准确性，选择计算最准确、最可靠的Wilson置信区间[17，18]，如式(15).

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

(15)

其中，S为Wilson置信区间算法公式；n为样本总数；u为诚实节点数；v为恶意节点数；Zα表示对应某个置信水平的统计量，如在95%的置信水平下，Zα=1.96.使用Wilson置信区间计算上下边界以更好地限制和估计失败概率.

Hafid等[7]在分析和比较Hoeffding，Chebyshev和 Chvátal边界计算区块链分片的失败概率时，使用Hoeffding边界计算的失败概率会较另两种更低，取Hoeffding边界为更好的分片失败概率近似值，可以更好的分析区块链分片协议的稳定性.据此在本文中算法计算分片失败概率越小，失败年限越大越能说明算法能够提供更好的稳定性估计.

4 仿真分析

4.1 仿真环境

为了估算由JD算法计算的分片失败概率，使用了NumPy Python库进行实验，该库提供了数学函数和随机数生成器等.另外，还使用numpy.array()来建立一个包含M个恶意节点和N-M个诚实节点的数组.还使用了numpy.random.choice()将节点进行随机分布，而无需在分片上替换这些节点.在配备i7-2677M CPU 1.80 GHz和6 GB RAM的PC上运行实验.

4.2 置信区间

在N=1000，M=250的区块链网络模型中，计算了在改变单个委员会中节点数n分别为125,200,250和实验次数Nt为104,105,106时使用JD算法的估计失败概率.为了更好地限定和估计失败概率，也计算了在置信水平为95%时的Wilson置信区间的上下限，这意味着，有95%的正确率确定估计的失败概率能在Wilson的上下限之间.表1数据显示计算的失败概率落在置信区间的上下限之间，验证了JD算法计算的分片失败概率是准确可靠的.

表1 不同实验次数和委员会节点数的估计失败概率及Wilson置信区间

4.3 失败概率分析

为了评估算法计算的分片失败概率，我们在两种参数的场景下进行了实验：(a)N=1000，M=250，Nt=106；(b)N=4000，M=1333，Nt=106.两种场景分别为两种主流区块链分片协议下能容忍的最大恶意节点数，若恶意节点占比更低，稳定性的分析效果会更好.在场景(a)中改变单个委员会节点数量n=100～250，在场景(b)中改变单个委员会节点数量n=30～500时的分片估计失败概率，并与Hoeffding边界算法和 RapidChain的分片稳定性分析算法进行了比较.

图4(a)和(b)中总体显示，分片的失败概率会随单个委员会中的节点数n的增加而降低，这是因为委员会中节点数量的增加，恶意节点的占比容易降低，恶意节点接管分片的难度会增大，从而降低分片失败概率.在场景(a)和(b)中当n较小时，Hoeffding边界算法的走势较为陡峭，说明Hoeffding边界算法在委员会节点数较少时的准确性差. 在图4(a)和(b)中能观察到Hoeffding和RapidChain都有失败概率超过1的时候，这是因为这两种算法都只计算了第一个委员会的失败概率并将其乘以委员会的数量，从而导致计算概率的不准确.另外在场景(a)和(b)中，JD算法计算的分片失败概率都较另外两种算法更低，且不会超过1，这是因为JD算法采用了适当的概率分布来计算，相比之下JD算法提供了更好的分片失败概率估计.

图4 场景(a)和(b)中三种算法的失败概率

4.4 失败年限分析

评估算法计算的区块链分片的平均失败年限，在两种参数的场景下进行了实验：(a)N=1000，M=250，Nt=106；(b)N=4000，M=1333，Nt=106.固定每年的分片次数，Nsy=365，计算在场景(a)中改变单个委员会节点数量n=100～250，在场景(b)中改变单个委员会节点数量n=30～500时的平均失败年限，并与Hoeffding边界算法和 RapidChain的分片稳定性分析算法进行了比较.

图5(a)和(b)中总体显示，随着委员会中节点数的增多，失败年限会升高，这是因为单个委员会的节点数增多，恶意节点在委员会中的占比就容易降低，分片越难以被攻击，使失败前的预期分片次数Es增加，从而导致失败年限减少.图5(a)和(b)中Hoeffding边界算法计算的平均失败年限在随着委员会数量的增加时，并没有什么明显变化，说明Hoeffding边界算法在计算失败年限时的不准确；当n较小时，RapidChain方法和JD算法计算的平均失败年限相差不大，但n逐渐变大时，JD算法与RapidChain开始拉开差距，失败年限也开始远多于另外两种方案.相比之下，JD算法能够更好地确定分片的失败年限.

图5 场景(a)和(b)中三种算法的平均失败年限

5 结 论

区块链分片会降低区块链的稳定性，需要对分片进行稳定性预评估，得到具有较高稳定性的分片方案.JD算法在计算分片失败概率和失败年限时能提供更好的估计，从而更好地分析区块链分片的稳定性.算法首先针对预分片的节点，按预定委员会数量进行不放回的随机抽样，从而获得每个委员会中节点的超几何分布，其次根据节点的超几何分布计算每个委员会中含有恶意节点的概率，并构建所有委员会的联合分布函数，最后根据所有委员会的联合分布函数计算整个分片方案的失败概率和失败年限.通过计算Wilson置信区间确定JD算法计算结果是正确的，另外仿真结果表明，JD算法在计算分片失败概率和分片失败年限时有更好的估计，从而实现对分片稳定性的精准分析.区块链分片是一个非常有挑战性的方向，在研究分片的稳定性问题之后，将着手进行区块链分片方案的研究，在保证区块链稳定性的同时尽可能提高其吞吐量.