基于PBFT 算法的分片技術(shù)的研究?

王旭東 符精晶 王 赟

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

1 引言

比特幣［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ò)展性較差，還有很大的研究空間。

2 準(zhǔn)備知識(shí)

2.1 實(shí)用拜占庭容錯(cuò)算法

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)接管。

2.2 聚合簽名

聚合簽名［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ù)的隱私性。

3 分片失效概率分析

本章通過(guò)對(duì)節(jié)點(diǎn)數(shù)對(duì)分片失效概率的分析、分片節(jié)點(diǎn)數(shù)對(duì)分片均不失效的分析來(lái)驗(yàn)證導(dǎo)致分片有效性降低的原因。

3.1 節(jié)點(diǎn)數(shù)對(duì)分片失效概率的分析

根據(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ù)值了。

3.2 分片節(jié)點(diǎn)數(shù)對(duì)分片均不失效的分析

假設(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)題。

4 分片內(nèi)共識(shí)方案實(shí)現(xià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）。

4.1 節(jié)點(diǎn)隨機(jī)性分配

在對(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ī)分配，跳躍查找算法如下所示：

4.2 PBFT共識(shí)算法改進(jìn)

選擇生成元定義為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ā)送σi>給副本節(jié)點(diǎn)；

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

5 實(shí)驗(yàn)測(cè)試結(jié)果與分析

本文將分別從系統(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)的行為。

5.1 系統(tǒng)容錯(cuò)性測(cè)試

在系統(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í)間影響

5.2 交易吞吐量測(cè)試

交易吞吐量測(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)。

5.3 交易延遲測(cè)試

在系統(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)景。

6 結(jié)語(yǔ)

擴(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ò)性、交易吞吐量并降低了交易延遲。