王旭東 符精晶 王 赟

（1.江蘇大學(xué)計算機科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）（2.沙洲職業(yè)工學(xué)院電子信息工程系 張家港 215600）

1 引言

比特幣［1］作為有史以來最成功的加密貨幣［2］，是一種突破和顛覆性的創(chuàng)新，其底層的區(qū)塊鏈技術(shù)在分布式共識領(lǐng)域備受技術(shù)人員和研究者的關(guān)注。區(qū)塊鏈（blockchain）是一種由對等網(wǎng)絡(luò)以分散的方式保存且無法篡改［3］的分布式賬本，其最初的目的是為了實現(xiàn)像比特幣這樣的數(shù)字資產(chǎn)而設(shè)計的，由于區(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)中當眾多節(jié)點試圖將一個區(qū)塊添加到主鏈中時，就需要一種達成一致性協(xié)議算法來確定哪個區(qū)塊才能被添加到主鏈中，這個算法被稱為共識算法，共識算法具有非常重要的意義，它決定了要添加的數(shù)據(jù)的正確性、試圖添加該區(qū)塊的節(jié)點的可信度以及確保了區(qū)塊鏈系統(tǒng)中分散的節(jié)點之間的一致性，高效的共識算法可實現(xiàn)更高的精度、更高的安全性、更好的性能和擴展性等，常見的共識算法有工作量證明（PoW）［1］，權(quán)益證明（PoS）［6］和實用拜占庭容錯（PBFT）［7］等。

目前區(qū)塊鏈的發(fā)展還處于最初階段，面臨著很多問題［8］，其中擴展性［9］問題亟待解決，分片技術(shù)是迄今為止被認為最能夠解決區(qū)塊鏈系統(tǒng)擴展性的最實用的解決方案，它通過將網(wǎng)絡(luò)劃分為不同的分片能夠使系統(tǒng)的處理、存儲和計算可以并行進行，從而減少通信、數(shù)據(jù)存儲和計算等資源開銷，同時保持去中心化和安全性，國內(nèi)外許多專家針對分片提出了諸多解決方案，下面將進行分別的介紹。

Elastico［10］是一種無許可的分片協(xié)議，在Elastico 中節(jié)點首先需要解決一個用于確定共識委員會PoW 謎題，確定共識委員會后，該委員會負責對分片的共識結(jié)果作出最終決定，在Elastico 中每達成一輪共識，委員會就會重組一次，這種頻繁的操作會降低交易執(zhí)行的效率；OmniLedger［11］是在Elastico的基礎(chǔ)上提出的一種分片協(xié)議，OmniLedger數(shù)據(jù)結(jié)構(gòu)塊采用了DAG，并使用了結(jié)合RndHound 和Algorand 的公共隨機協(xié)議來進行分片，但Omniledger的缺點是共識過程中牽扯到跨分片交易時通信開銷過大；RapidChain［12］是一種基于PBF 算法分片的公共區(qū)塊鏈協(xié)議，RapidChain 通過減少每筆交易的數(shù)據(jù)交換量，并使用快速的跨分片驗證技術(shù)，使交易不需要大范圍傳播，但是RapidChain 是采用PBF算法達成共識，依然沒能解決通信開銷大的問題；Monoxide［13］是一個橫向擴展的區(qū)塊鏈，它提出了異步共識區(qū)，線性擴展了區(qū)塊鏈系統(tǒng)，但依然沒能解決通信開銷的問題；Zilliqa［14］是以Pow 為共識算法的區(qū)塊鏈分片技術(shù)，Zilliqa 通過處理不同分片中的交易來改進吞吐量，但是Zilliqa中的節(jié)點需要存儲整個區(qū)塊鏈網(wǎng)絡(luò)中的數(shù)據(jù)，阻礙了系統(tǒng)的擴展；Harmony 是一個具有多個分片鏈結(jié)構(gòu)的方案，它可以同時處理交易和存儲數(shù)據(jù)，但該分片協(xié)議可擴展性較差，還有很大的研究空間。

2 準備知識

2.1 實用拜占庭容錯算法

PBFT 是一種經(jīng)過改進的BFT 算法，經(jīng)過改進，PBFT在異步環(huán)境下比BFT的響應(yīng)時間降低了一個數(shù)量級，并能夠容忍異步系統(tǒng)中故障節(jié)點引起的一致性問題。與PoW 相比，PBFT 的工作原理中沒有計算任務(wù)，因此，它將共識的復(fù)雜性降低到多項式水平，并且顯著降低了能耗。

圖1 PBFT算法的共識過程

在PBFT的每個視圖中，當主節(jié)點收到請求時，它會根據(jù)一個三階段的協(xié)議向前移動：預(yù)準備、準備和提交。在預(yù)準備階段，當主節(jié)點收到請求序列時，主節(jié)點按順序?qū)⒄埱笮蛄邪l(fā)送給其他副本節(jié)點，副本節(jié)點在收到請求序列后，檢查其有效性，并將其添加到其本地日志中，并向其副本節(jié)點發(fā)送一條消息，以顯示它已經(jīng)收到了提議并識別了它。然后，副本節(jié)點進入準備階段，副本節(jié)點成功收集2f+1反饋消息（f表示故障節(jié)點數(shù)量）時，將啟動提交階段。最后，主節(jié)點收集到2f+1 條提交消息后，就可以確保提案已經(jīng)由足夠的副本節(jié)點完成記錄，可以執(zhí)行反饋操作，并向客戶端發(fā)送回復(fù)。

為了確保主節(jié)點不出現(xiàn)故障，PBFT 設(shè)計了一種稱為視圖更換的協(xié)議，如果備份節(jié)點發(fā)現(xiàn)主節(jié)點有惡意行為或停止工作，那么它會獨立地宣布要將主節(jié)點更改為下一個節(jié)點的提議，如果2f+1副本發(fā)現(xiàn)主節(jié)點的異常，將確認更改視圖，由下一個主節(jié)點接管。

2.2 聚合簽名

聚合簽名［15］是一種用于消息身份驗證和數(shù)據(jù)完整性驗證的安全技術(shù)，通過將一組數(shù)字簽名組合成一個單一的數(shù)字簽名，可用作大量數(shù)據(jù)的完整性證明。聚合簽名通過把多個簽名進行聚合，節(jié)省了通信和存儲空間，在聚合簽名驗證過程中只有當整個簽名集都有效時，聚合簽名的驗證才會輸出肯定的結(jié)果，如果在集合中有一個錯誤的簽名，則表示所涉及數(shù)據(jù)的完整性無效。下面對聚合簽名做簡單驗證，對于橢圓曲線上的兩個點X，Y 和x，y 以及原點G：

聚合簽名有諸多優(yōu)點，對于驗證者來講，聚合簽名可以提升交易的驗證速度并節(jié)省了通信和存儲空間，且無法通過聚合簽名推導(dǎo)出參與方的公鑰和簽名的信息，可用于提高鏈上數(shù)據(jù)的隱私性。

3 分片失效概率分析

本章通過對節(jié)點數(shù)對分片失效概率的分析、分片節(jié)點數(shù)對分片均不失效的分析來驗證導(dǎo)致分片有效性降低的原因。

3.1 節(jié)點數(shù)對分片失效概率的分析

根據(jù)式（4），設(shè)置初始參數(shù)值f=[0.1,0.2,0.3]，通過改變M 的值模擬研究M 對P的影響情況，如表1所示。

表1 分片內(nèi)節(jié)點數(shù)M對單個分片失效概率P的影響

根據(jù)表1，在f 不變時，隨著分片中節(jié)點數(shù)目的增多，分片失效的概率顯著降低，在M不變時，隨著f 增大分片失效概率越高，對于整個區(qū)塊鏈系統(tǒng)而言，單個分片失效概率大于0.03已經(jīng)是一個較高的數(shù)值了。

3.2 分片節(jié)點數(shù)對分片均不失效的分析

假設(shè)拜占庭節(jié)點比例為f(0 ≤f≤1/3) ，每個分片中節(jié)點數(shù)為M，分片個數(shù)為k，若想保證所有分片不失效，需要保證每個分片內(nèi)的拜占庭節(jié)點的比例f<1/3，為了追求結(jié)果的準確性，采用窮舉遍歷的方法，如式（5）所示，式（6）和式（7）是式（5）的兩個限定條件。

在探究M 與Pr 的關(guān)系時，為了研究高拜占庭節(jié)點比例下分片的失效概率，選取f=0.3，分片個數(shù)k=4，固定這兩個值可準確地研究有效分片規(guī)模與高拜占庭比例下，分片內(nèi)節(jié)點數(shù)M對所有分片都不失效的概率值Pr 影響，圖2 是基于式（5），M 對P 的影響圖。

圖2 M對P的影響

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

4 分片內(nèi)共識方案實現(xiàn)

為了解決以上問題，本文通過動態(tài)權(quán)值分配方法優(yōu)化一致性hash 算法，解決節(jié)點分配的不均衡性，在此基礎(chǔ)上實現(xiàn)基于PBFT 共識算法利用聚合簽名技術(shù)改進動態(tài)實用拜占庭算法（DPBFT）。

4.1 節(jié)點隨機性分配

在對節(jié)點進行隨機劃分時，采用一致性哈希算法［16］進行劃分，但是在系統(tǒng)中每一個節(jié)點都存在差異，故本文通過動態(tài)權(quán)值分配的方法對一致性hash算法進行優(yōu)化以支持動態(tài)權(quán)重，首先對權(quán)值進行計算，步驟如下：

1）節(jié)點負載

假設(shè)有n 個節(jié)點，分片數(shù)目為m，對于每個節(jié)點i，CPU 利用率是內(nèi)核模式和空閑模式下CPU（t）時間之和的比值，采用以下公式計算：

節(jié) 點 閑 置 內(nèi) 存 為METfree（t），節(jié) 點 總 內(nèi) 存 為METtotal（t），主機內(nèi)存利用率（MEM（t））為

網(wǎng)絡(luò)利用率（NET（t））是節(jié)點在時間間隔t 內(nèi)接收和發(fā)送的字節(jié)之和與網(wǎng)絡(luò)帶寬NETband（t）的比值，當一個節(jié)點加入集群時，可以使用以下公式計算網(wǎng)絡(luò)利用率：

通過上面的計算，我們使用以下公式計算系統(tǒng)中節(jié)點i的負載Load：

其中λ1=0.3，λ2=0.3，λ3=0.4。

2）節(jié)點誠信值

共識完成率反映了節(jié)點在區(qū)塊鏈中總體的完成程度，其可通過共識完成率γ表示，如式（12）計算：

式（12）中，s 為節(jié)點成功完成的共識次數(shù)，a 為調(diào)節(jié)常數(shù)，n為節(jié)點參與共識次數(shù)。

交易影響率用于表示交易對節(jié)點的影響程度，交易影響率可用交易影響函數(shù)f（x）計算，如式（13）：

節(jié)點交互程度是指節(jié)點在區(qū)塊鏈系統(tǒng)中的參與共識的程度，節(jié)點交互程度用交互影響函數(shù)表示，交互影響函數(shù)可采用式（14）計算：

其中，η?( ]0.5,1 用來控制活躍度比重，a為次數(shù)調(diào)節(jié)因子，n為共識次數(shù)。

則節(jié)點信用可采用式（15）計算：

其中Cinit為節(jié)點信任值初值，E 為行為評價影響因子。

3）節(jié)點完成速率可用式（16）計算：

其中，V0表示原始數(shù)值，Vmin和Vmax分別為節(jié)點完成速率的最大和最小值。

那么節(jié)點s的當前權(quán)重Ws為

經(jīng)過多次實驗驗證，當ω1=0.3，ω2=0.3，ω3=0.4時最為合適。

經(jīng)過上述對分片權(quán)重的計算，我們使用一致性哈希算法來獲取系統(tǒng)中所有節(jié)點的動態(tài)權(quán)值Ws，并將節(jié)點的動態(tài)權(quán)重值作為哈希值，映射到哈希空間中，然后利用一致性哈希算法來確保節(jié)點與哈?？臻g動態(tài)權(quán)值之間的對應(yīng)關(guān)系，并用哈希表進行記錄，最后通過跳躍查找算法對節(jié)點的所有權(quán)重進行索引查找然后隨機分配，跳躍查找算法如下所示：

4.2 PBFT共識算法改進

選擇生成元定義為P∈G1，Q∈G2，定義雙線性映射為e：G1×G1→G2，散列函數(shù)為H0、H1、H2、HDV。

1）利用當下的視圖計算Pv=vP，得到系統(tǒng)參數(shù)Params=｛G1，G2，e，q，P，Q，Pv，H0，H1，H2，HDV｝。

2）用戶ui選擇隨機值xi∈Zq*計算Pi=xiP，Qi=H1（IDi||Pi），Di=vQi生成用戶的私鑰Si=（Di，xi）。

3）用戶ui執(zhí)行以下過程：ri∈Zq，計算Ri=riP，hi=H0（IDi||mi||Pi||Ri），T=H2（Pv）。

4）若要驗證u對m的簽名σi=（Vi，Ri）的有效性，計算hi=H0（IDi||mi||Pi||Ri），Qi=H1（IDi||Pi），T=H2（Pv），并驗證下列等式是否成立：

為了說明上述論述是正確的，下面給出了單個簽名驗證過程和聚合簽名驗證過程的正確性的證明過程。

u 對m 的簽名σi=（Vi，Rn）證明單個簽名驗證過程是正確的過程如下：

對上述問題進行正確性驗證之后，改進的共識算法DPBFT的共識過程如下。

1）令H：{0,1}*→G1是一個哈希函數(shù)，T/B 是一個交易。 發(fā)送者使用私鑰sk 計算哈希值h=H((T/B)||v)，計算的簽名為σ=hsk，節(jié)點附上發(fā)送者簽名的數(shù)據(jù)向全網(wǎng)廣播；

2）聚合簽名者通過給定的公鑰pk，交易T/B，簽名σ=hsk，計算哈希函數(shù)值h=H((T/B)||v)，驗證為真，則接受，反之放棄。聚合簽名者通過聚合簽名算法得到的聚合集表示為U={u1,u2,…,un}，收集到的簽名為σ，消息集為T/B={(T/B)1,(T/B)2,…,(T/B)n}，則聚合簽名為

3）主節(jié)點在經(jīng)過時間t 后，發(fā)送σi>給副本節(jié)點；

4）副本節(jié)點i在收到消息后，檢查其有效性，并添加到本地日志中，并發(fā)送σi>給其他副本節(jié)點，以顯示已經(jīng)收到了提議；

5 實驗測試結(jié)果與分析

本文將分別從系統(tǒng)容錯性、交易吞吐量，交易延遲三個方面對改進后的DPBFT 與Omniledger 兩個方案進行對比，實驗平臺為Hyperledger Fabric，實驗中通過對節(jié)點收到消息后延遲處理與發(fā)送模擬拜占庭節(jié)點的行為。

5.1 系統(tǒng)容錯性測試

在系統(tǒng)容錯性實驗中，主要統(tǒng)計Omniledger和DPBFT 兩種方案在不同的拜占庭節(jié)點數(shù)目下的出塊時間，在實驗室中我們將拜占庭節(jié)點個數(shù)逐次增加至超過節(jié)點總數(shù)的1/3。

由圖3 可以看出，隨著拜占庭節(jié)點數(shù)目的增多Omniledger 和DPBFT 兩種方案的出塊時間都在增加，但DPBFT 方案的增加幅度比較小，相比而言DPBFT方案更優(yōu)。

圖3 分片內(nèi)拜占庭節(jié)點數(shù)目對出塊時間影響

5.2 交易吞吐量測試

交易吞吐量測試過程中，只改變拜占庭節(jié)點比例，其他參數(shù)均保持保持不變，對比DPBFT 和Omniledger兩種方案的交易吞吐量，結(jié)果如圖4所示。

圖4 不同拜占庭節(jié)點比例對TPS的影響

根據(jù)圖4 所示，隨著拜占庭節(jié)點比例的增大，兩種方案的TPS均在降低，但是DPBFT方案下降幅度稍緩，DPBFT方案較優(yōu)。

5.3 交易延遲測試

在系統(tǒng)對拜占庭節(jié)點比例容忍范圍內(nèi)，通過改變分片個數(shù)，對DPBFT 和Omnildger 兩種方案的交易延遲進行測試，結(jié)果如圖5所示。

圖5 分片數(shù)量對交易延遲的影響

根據(jù)圖5 所示，隨著區(qū)塊鏈系統(tǒng)中分片數(shù)量不斷增加，DPBFT方案和Omniledger方案交易延遲都在增加，但DPBFT 方案具有更低的交易延遲，DPBFT方案更優(yōu)。

經(jīng)過上述實驗分析可知，DPBFT共識算法提高了系統(tǒng)容錯性和交易吞吐量并降低了交易延遲，保證區(qū)塊鏈系統(tǒng)分片后的系統(tǒng)效率，使該改進后的共識算法能夠應(yīng)用于更多去中心化場景。

6 結(jié)語

擴展性是區(qū)塊鏈系統(tǒng)面臨的一大問題，受到越來越多的專家的關(guān)注，本文針對區(qū)塊鏈分片以及分片內(nèi)達成一致性的的問題進行研究，提出了DPBFT共識算法，在保證分片數(shù)據(jù)的可信性前提下有效地提升了系統(tǒng)容錯性、交易吞吐量并降低了交易延遲。