DS-PBFT：一種基于距離的面向區(qū)塊鏈的共識算法

朱 海，金 瑜

1(武漢科技大學 計算機科學與技術(shù)學院，武漢 430065) 2(湖北省智能信息處理與實時工業(yè)系統(tǒng)重點實驗室，武漢 430065)

1 引 言

自中本聰提出了比特幣[1]后，區(qū)塊鏈的概念就誕生了.由于區(qū)塊鏈具有去中心化、防篡改和可追溯等特征[2]，近幾年區(qū)塊鏈的相關(guān)技術(shù)成為了研究熱點.在此基礎(chǔ)上，區(qū)塊鏈的應(yīng)用場景已經(jīng)從加密貨幣[3]、數(shù)字資產(chǎn)[4]擴展到能源[5]、醫(yī)療保健[6]、教育[7]、供應(yīng)鏈[8]等非金融行業(yè)的領(lǐng)域.

共識算法作為區(qū)塊鏈的核心技術(shù)，其功能就是保證系統(tǒng)的一致性、安全以及穩(wěn)定的運行[9].區(qū)塊鏈分為公有鏈、聯(lián)盟鏈和私有鏈[10].工作量證明(Proof of Work，PoW)、權(quán)益證明[11](Proof of Stake，PoS)以及授權(quán)股份證明[12](Delegated Proof of Stake，DPoS)是公有鏈主要的共識算法；實用拜占庭容錯協(xié)議[13](Practical Byzantine Fault Tolerance，PBFT)是私有鏈、聯(lián)盟鏈主要的共識算法.PBFT共識算法有效的解決了拜占庭將軍問題[14]，使其可以實際應(yīng)用于吞吐量較小的分布式系統(tǒng).但該算法為了追求完全的去中心化，讓系統(tǒng)中除客戶端節(jié)點以外的所有節(jié)點都參與到共識過程中，并且其算法的時間復(fù)雜度為O(N2)，故其只能應(yīng)用于節(jié)點數(shù)量較少的系統(tǒng).目前，有很多對PBFT算法進行改進的一類方案，它們通過各種措施(比如通過VRF、投票等等)對系統(tǒng)中的節(jié)點進行篩選，從而單純地通過減小共識節(jié)點的規(guī)模來提升PBFT算法的效率，但是其通信代價和共識時延仍然無法達到現(xiàn)實應(yīng)用場景的要求.

本文基于PBFT算法的思想，提出了一種基于距離的面向區(qū)塊鏈的共識算法.通過Grouping算法，將距離較近的節(jié)點分成一組進行共識，在減小共識節(jié)點規(guī)模的基礎(chǔ)上縮短共識節(jié)點間的通信距離，從而減少共識時延.同時結(jié)合speculation技術(shù)[15]，降低算法的時間復(fù)雜度，從而減少系統(tǒng)的通信代價，使得DS-PBFT算法能夠適用于更廣泛的應(yīng)用場景中.

2 相關(guān)工作

PBFT算法的共識過程是在所有共識節(jié)點的共同參與下完成的，使得系統(tǒng)中的共識節(jié)點數(shù)量增多時，算法的通信次數(shù)與共識時延成倍增加.因此，現(xiàn)階段有許多的方案都是通過減少共識節(jié)點的規(guī)模來提升PBFT算法的效率.

以上共識算法雖然從各個角度減少了參與共識節(jié)點的規(guī)模，與傳統(tǒng)的PBFT相比，確實在一定程度上提升了共識效率，但它們篩選共識節(jié)點都不是基于距離，并且不能從根本上克服傳統(tǒng)PBFT的缺點，因此共識時延和通信代價都還是比較大的.為了簡單，本文將這類算法統(tǒng)一稱為ND-PBFT，即在n>m的條件下，從n個節(jié)點里面篩選出m個節(jié)點進行PBFT共識的算法.

3 DS-PBFT共識算法

3.1 相關(guān)定義

為了更加方便的對DS-PBFT共識算法進行描述，對相關(guān)概念進行如下定義：

定義1.初始節(jié)點集合

初始時系統(tǒng)提供的節(jié)點集合，用字母U表示，包含的節(jié)點數(shù)量較少，方便以較小的代價求解節(jié)點間的距離矩陣.使用U={n1，n2，…，nt}來表示擁有t個節(jié)點的初始節(jié)點集合，其中ni表示第i個節(jié)點.另外，初始集合中的節(jié)點是在一個固定周期內(nèi)根據(jù)地理位置均勻地挑選出來的.

定義2.距離矩陣

距離矩陣是一個(t×t)的矩陣，用字母D表示，是由初始節(jié)點集合中任意兩節(jié)點之間的最短距離而形成的矩陣.其中元素dij表示在某一時刻節(jié)點i到節(jié)點j的最短距離.

定義3.距離平均值

距離平均值指的是一個節(jié)點到一個節(jié)點集合中所有節(jié)點的距離的平均值，用字母md表示.例如，md(i，U1)表示節(jié)點i到節(jié)點集合U1中所有節(jié)點的距離的平均值，用公式表示如下：

(1)

定義4.距離標準差

距離標準差指的是一個節(jié)點到一個節(jié)點集合中所有節(jié)點的距離的標準差，用字母sd表示.例如，sd(i，U1)表示節(jié)點i到節(jié)點集合U1中所有節(jié)點的距離的標準差.用公式表示如下：

(2)

定義5.節(jié)點

節(jié)點是區(qū)塊鏈網(wǎng)絡(luò)中的基本單元，其中包含index(序號)、sd(距離標準差)、md(距離平均值)、primary(該節(jié)點所在小組的主節(jié)點)、group(該節(jié)點所在小組序號)這些屬性.

定義6.初始分組

初始分組是由初始節(jié)點集合通過Grouping算法產(chǎn)生的若干個小組，用字母G表示.每個小組中各自包含著距離相對較近的節(jié)點.令G={g1，g2，…，gm}表示m個小組，其中g(shù)i表示第i個小組.

定義7.主節(jié)點集合

主節(jié)點集合是由各個小組中選出的主節(jié)點所構(gòu)成的節(jié)點集合，用pList表示.令pList={p1，p2，…，pm}表示由m個主節(jié)點構(gòu)成的主節(jié)點集合，其中pi為第i個小組的主節(jié)點.

定義8.主節(jié)點候補集合

主節(jié)點候補集合是由各個小組中的候補集合構(gòu)成的總的集合，用Alternate表示.當某個小組中的主節(jié)點發(fā)生故障時，該小組的候補集合中的節(jié)點會按照順序進行替換.令A(yù)lternate={a1，a2，…，am}表示m個小組的候補集合，其中ai表示第i個小組的候補集合.

定義9.speculation共識階段

當不存在拜占庭節(jié)點時，使用speculation技術(shù)進行共識的階段，并且在共識執(zhí)行的過程中首先進行.

定義10.group共識階段

當存在拜占庭節(jié)點時即speculation共識階段失敗后，請求節(jié)點所在小組進行第一次PBFT共識的階段.

定義11.primary共識階段

當group共識階段完成后，在主節(jié)點集合中進行第2次PBFT共識的階段.

3.2 系統(tǒng)框架

DS-PBFT共識算法的框架如圖1所示，系統(tǒng)中主要包含普通節(jié)點和共識節(jié)點兩個實體.普通節(jié)點不參與共識，共識節(jié)點才參與到具體的共識過程，比如圖1所示組1和所有主節(jié)點構(gòu)成了一輪共識中的共識節(jié)點.DS-PBFT中參與每一輪共識的共識節(jié)點都是動態(tài)變化的，是由某個小組集合加上主節(jié)點集合構(gòu)成的.共識節(jié)點變化的那部分是參與共識的小組集合，但是對于所有主節(jié)點來說，每一輪共識都需要參與，所以它們永遠都是共識節(jié)點.因此對于具體某一輪共識中是由哪個小組中的節(jié)點加上所有主節(jié)點構(gòu)成共識節(jié)點進行共識，可以按照輪詢的方式進行確定.具體為系統(tǒng)在分成的若干個小組中按照小組序號進行輪詢，若輪詢到某個小組時該小組內(nèi)存在請求，則該小組內(nèi)的節(jié)點加上所有主節(jié)點構(gòu)成共識節(jié)點進行共識，直到處理完從上次輪循完該小組開始到現(xiàn)在剛輪循到該小組時這段時間內(nèi)產(chǎn)生的所有請求后，自動跳過該小組，輪詢下一個小組；若輪詢到某個小組時該小組內(nèi)不存在請求，則直接跳過該小組輪詢下一個小組，直到找到存在請求的小組，再加上所有主節(jié)點構(gòu)成共識節(jié)點進行共識.下面通過圖1介紹一個周期內(nèi)DS-PBFT共識算法的大致步驟.

圖1 系統(tǒng)框架Fig.1 System framework

a)通過Grouping算法首先將系統(tǒng)提供的初始節(jié)點集合中的節(jié)點分成若干個小組.

b)在產(chǎn)生的各個小組中分別通過主節(jié)點選取、輪換算法獲得各個小組的主節(jié)點以及候補集合，接著再將各個主節(jié)點和候補集合分別構(gòu)成主節(jié)點集合pList和主節(jié)點候補集合Alternate.

c)當系統(tǒng)中存在請求需要處理時，共識節(jié)點首先進行speculation共識.若speculation共識成功，則整個共識過程成功結(jié)束；若speculation共識失敗，則進入到group共識階段.

d)若speculation共識失敗，請求節(jié)點所在小組以小組為單位進行第1次PBFT共識即group共識階段.共識成功過后進入到primary共識階段.

e)若group共識成功，主節(jié)點集合中進行第2次PBFT共識即primary共識階段，共識成功后整個共識過程成功結(jié)束.

其中上述a)、b)這兩個步驟屬于初始化階段，為后面的共識執(zhí)行階段做準備工作，c)、d)、e)3個步驟為共識執(zhí)行階段，進行實際的共識流程.另外在實際應(yīng)用中，由于DS-PBFT在存在拜占庭節(jié)點(宕機或發(fā)生其它故障導(dǎo)致不能正常工作的節(jié)點)時是基于PBFT的，因此各個小組以及主節(jié)點集合需要滿足n>3f的條件才能保證共識結(jié)果的正確性，其中n為小組或者主節(jié)點集合中節(jié)點的數(shù)量，f為小組或者主節(jié)點集合中能夠容忍的拜占庭節(jié)點的數(shù)量.

3.3 DS-PBFT關(guān)鍵算法

3.3.1 初始化階段

1)Grouping算法

在實際的網(wǎng)絡(luò)中，節(jié)點之間距離的遠近會影響節(jié)點間信息傳遞的時間，距離是影響數(shù)據(jù)傳輸延遲的關(guān)鍵因素.并且在實際生活中大部分節(jié)點的位置不會發(fā)生很大的變動，因此在某一個固定周期內(nèi)，可以近似的將某一時刻節(jié)點之間的距離看作一個固定周期內(nèi)節(jié)點之間的距離.基于此，本文設(shè)計一種Grouping算法，將系統(tǒng)中在某一固定周期內(nèi)距離較近的節(jié)點分為一組，并且允許節(jié)點進行細微的位置變動(細微的位置變動對共識時延帶來的影響可以忽略不記)，經(jīng)過主節(jié)點選取后最終形成多個主節(jié)點領(lǐng)導(dǎo)下的多個小組，從而使算法在距離因素上減少節(jié)點間的信息傳輸時延.

為了能夠以較低的計算代價將節(jié)點進行分組，系統(tǒng)初始時需要提供一個一定數(shù)量的初始節(jié)點集合U，并首先將初始集合中的節(jié)點進行分組.對于未分組或未來新加入?yún)^(qū)塊鏈網(wǎng)絡(luò)的節(jié)點，再根據(jù)初始分組G的信息判斷加入哪個小組，這是Grouping算法的基本思想.另外，之所以對節(jié)點進行分組之前需要系統(tǒng)提供一個節(jié)點數(shù)量較少的初始節(jié)點集合，那是因為計算大量節(jié)點的距離矩陣所需要的代價是巨大的，而初始集合中的節(jié)點數(shù)量并不多，計算初始集合中節(jié)點的距離矩陣的代價相對較小，因此首先通過對初始集合中的節(jié)點進行分組并在此基礎(chǔ)上對所有節(jié)點進行分組就成為了合理的選擇.

另外，由于后續(xù)新節(jié)點的分配依賴于初始分組的信息，所以初始分組的結(jié)果對后面的節(jié)點分配起著關(guān)鍵性的作用，影響著最終的分組結(jié)果.所以，對初始節(jié)點集合中節(jié)點的分組應(yīng)當足夠的準確，防止誤差的積累，導(dǎo)致誤差越來越大.以下是Grouping算法的偽代碼.

算法1.Grouping

Grouping algorithm

輸入：Initial node collectionU

Distance matrixD

Number of groupsm

輸出：Initial groupsG

1. initialize.G←{g1，g2，…，gm}

2. foriin range(1，m)

3.c←random(U)

4.gi.add(c)

5. avg←(∑j∈U，j≠cdcj)/(|U|-1)

6. forj∈U&&j≠c

7. ifdcj

8.gi.add(j)

9.U←U-{j}

10.U←U-{c}

11. whileU≠?&&n∈U

12. foriin range(1，m)&& !enough(i)

13.k，n←min(md(n，gi)，sd(n，gi))

14.gk.add(n)

15. returnG

Grouping算法在計算每一個分組時，首先會從初始節(jié)點集合U中隨機地抽取一個節(jié)點，并將此節(jié)點作為當前的中心節(jié)點，使分布在中心節(jié)點一定閾值半徑內(nèi)的若干節(jié)點成為一個小組，包括中心節(jié)點.然后從初始集合U中移除已經(jīng)分配好的節(jié)點，重復(fù)以上過程直到完成m個小組的分配.閾值半徑avg是當前中心節(jié)點到U中其他所有節(jié)點距離的平均值.將節(jié)點映射到一個二維平面上，Grouping算法相當于用m個圓去覆蓋一個平面節(jié)點集，并且這m個圓互不相交.由于這些圓之間互不相交，因此在初始集合中可能還會存在少量節(jié)點沒有被包含.對于這些沒有被包含即沒有成功分組的節(jié)點，需要逐一地計算其到m個小組集合的距離平均值，然后根據(jù)計算出的最小的距離平均值將節(jié)點加入到對應(yīng)的小組中，如果存在該節(jié)點到若干小組的最小距離平均值有多個的情況，就接著計算該節(jié)點到這些小組集合的距離標準差，最后根據(jù)最小的距離標準差將節(jié)點分配到對應(yīng)的小組中.其中enough(i)函數(shù)的作用是當?shù)趇組的人數(shù)已經(jīng)充分足夠了返回true，否則返回false，確保每個小組中的節(jié)點數(shù)量滿足n>3f的條件.

在生成初始分組后，為了提高系統(tǒng)的動態(tài)性，DS-PBFT共識算法允許節(jié)點動態(tài)的加入或退出小組.由于參與到一輪共識中的共識節(jié)點是請求節(jié)點所在小組加上主節(jié)點集合中的節(jié)點，其它小組處于空閑期.因此為了防止組內(nèi)成員節(jié)點的變化而影響共識，小組內(nèi)節(jié)點的動態(tài)加入或退出是在當前小組處于空閑時期時進行的，即在當前小組沒有參與到某輪共識期間.對于新加入到區(qū)塊鏈中的節(jié)點，通過Grouping算法分配到某個具體小組后，系統(tǒng)會將該節(jié)點信息在該小組處于空閑時期記錄到該小組集合中.對于想要退出當前小組的節(jié)點(非主節(jié)點)，首先需要向系統(tǒng)提出申請，申請通過后，系統(tǒng)會將該節(jié)點信息在當前小組處于空閑時期時從相關(guān)節(jié)點集合中刪除.另外如果該節(jié)點是候補節(jié)點，系統(tǒng)會重新按照生成候補集合的算法補充候補節(jié)點的數(shù)量.退出的節(jié)點如果想要再次加入某個小組時，需要重新根據(jù)其距離信息以及Grouping算法對其進行分配.最后對于小組中的主節(jié)點想要退出當前小組，必須首先向系統(tǒng)申請降級為非主節(jié)點，由系統(tǒng)根據(jù)候補集合中獲得有資格的候補節(jié)點替換當前主節(jié)點后，再在該節(jié)點處于空閑時期時將其有關(guān)信息在相關(guān)集合中進行刪除，最后更新其它小組的候補集合.

另外，DS-PBFT每隔一定周期需要對節(jié)點重新進行分組，具體周期時長可以根據(jù)實際適當?shù)倪M行設(shè)置.之所以要每隔一定周期對節(jié)點重新進行分組，是因為在實際過程中，經(jīng)過較長的一段時間后，各個小組內(nèi)小部分節(jié)點的位置可能會發(fā)生很大的變動，導(dǎo)致組內(nèi)節(jié)點之間的距離會發(fā)生很大的改變，從而較大地影響共識時延.在重新分組時，系統(tǒng)會根據(jù)地理位置均勻地挑選出適量節(jié)點重構(gòu)初始節(jié)點集合和距離矩陣.最后通過Grouping算法對所有節(jié)點重新進行分組，重新構(gòu)建小組集合、主節(jié)點集合以及候補集合.而對于在具體的某個周期內(nèi)，系統(tǒng)生成的小組集合、主節(jié)點集合以及候補節(jié)點集合就是固定的，只會由于主節(jié)點替換、節(jié)點動態(tài)加入、退出這些操作才會帶來細微變化.

2)主節(jié)點選取算法

主節(jié)點選取算法的目的同樣是為了在各個小組中選出若干個距離較近的主節(jié)點，從而減少primary共識階段的消息傳輸時延.下面詳細描述主節(jié)點選取算法的步驟.

對于系統(tǒng)中通過Grouping算法形成的m個初始分組{g1，g2，…，gm}，首先在g1組中計算出各個節(jié)點到{g2，g3，…，gm}集合中的距離平均值，將距離平均值最小的節(jié)點作為主節(jié)點加入到主節(jié)點集合pList中，接著在g2內(nèi)計算各個節(jié)點到pList集合中的距離平均值，將距離平均值最小的節(jié)點加入到pList中.對于后續(xù)其它小組中選取主節(jié)點的步驟和在g2內(nèi)一樣，直到主節(jié)點集合中存在m個主節(jié)點才結(jié)束選舉過程.當以上選舉過程中存在多個最小平均值的情況時，同樣是接著比較距離標準差，從而獲得唯一的主節(jié)點加入到主節(jié)點集合中.主節(jié)點選取算法的偽代碼如下.

算法2.Primary nodes selection

Primary nodes selection algorithm

輸入：Initial groupsG

Distance matrixD

輸出：Collection of primary nodespList

1.pList←null

2.node←getMin(g1，G-g1，D)

3.pList.add(node)

4. foriin range(2，G.size())

5.node←getMin(gi，pList，D)

6.pList.add(node)

7. returnpList

3)主節(jié)點輪換算法

主節(jié)點輪換算法分成兩部分，一個是生成主節(jié)點候補集合，另一個是輪換拜占庭主節(jié)點.用于當小組中的主節(jié)點發(fā)生故障或者宕機時進行輪換，從而保持系統(tǒng)的正常工作.下面詳細地描述主節(jié)點輪換算法的步驟.

a)生成主節(jié)點候補集合

對于系統(tǒng)中通過Grouping算法在初始節(jié)點集合中形成的m個初始分組{g1，g2，…，gm}，假設(shè)在g1中有q個節(jié)點，在g1中計算各個節(jié)點到pList中的距離平均值(不包括g1中的當前主節(jié)點)，按照從小到大的順序?qū)⒐?jié)點排列為{n1，n2，…，nq-1}.如果存在距離平均值相同的情況，則將節(jié)點按照距離標準差從小到大的順序進行排列，最終獲得的由(q-1)個節(jié)點構(gòu)成的序列即為該小組的候補集合.其它小組按照g1中同樣的方式進行，最終系統(tǒng)會獲得m個候補集合.最后，系統(tǒng)會將各個小組中產(chǎn)生的候補集合整合成主節(jié)點候補集合.另外，各個小組中候補集合的節(jié)點數(shù)是固定的并且可能各不相同，依賴于初始分組時的節(jié)點數(shù)量，等于初始分組時的節(jié)點數(shù)量減1.

b)輪換拜占庭主節(jié)點

假設(shè)在g1內(nèi)檢測到主節(jié)點是拜占庭節(jié)點時，會按照該小組候補集合中的順序選擇第一個候補節(jié)點(距離平均值最小并且距離標準差最小)輪換當前主節(jié)點，但前提是這個候補節(jié)點不是宕機節(jié)點，如果是宕機節(jié)點就接著按照順序往下找候補節(jié)點.被輪換的主節(jié)點將從主節(jié)點集合及其所屬的小組集合中移除.成為了主節(jié)點的候補節(jié)點將從候補集合中移除并將其加入到主節(jié)點集合中，使其他的候補節(jié)點能夠擁有機會成為主節(jié)點，否則會導(dǎo)致壟斷的問題.另外在該小組內(nèi)，為了保證候補集合中始終有(q-1)個候補節(jié)點，當后續(xù)新加入到該小組的節(jié)點達到一定數(shù)量時，系統(tǒng)會對新加入的節(jié)點同樣通過計算距離平均值以及距離標準差的方式按照從小到大的順序?qū)⑿鹿?jié)點插入到當前小組的候補集合中.最后由于各個小組的候補節(jié)點是依賴于其它小組的主節(jié)點，當某個小組的主節(jié)點發(fā)生替換時，應(yīng)當及時更新其它各個小組的候補節(jié)點集合即重新按照生成候補集合的算法重構(gòu)候補集合，保證從當前候補集合中挑選出的主節(jié)點總是距離其它主節(jié)點是較近的.

算法3.Rotation of primary node

Rotation of primary node algorithm

輸入：Initial groupsG

Distance matrixD

Collection of new nodesnewNodes

輸出：Primary nodepri，Alternate set of primary nodesAlternate

Alternate collection of primary nodeAlternate

1. initialize.Alternate←{a1，a2，…，am}

2. foriin range(1，G.size())

3. forningi&&nnot inpList

4.n.sd←sd(n，pList-n.primary)

5.n.md←md(n，pList-n.primary)

6.ai.add(n)

7.ai←sorted(ai)

8.pNode←System.supervise()

9.index←pNode.group

10.pri←getFirst(aindex)

11.pList.add(pri)

12.aindex，pList←remove(aindex，pList，pri，pNode)

13.Alternate←update(Alternate-aindex)

14. if(aindex).size()<(aindex).size()-1

15. (aindex).add(newNodes)

16. returnpri，Alternate

3.3.2 共識執(zhí)行階段

在共識執(zhí)行階段，共識算法的運行步驟存在兩種情況.下面根據(jù)系統(tǒng)中是否存在拜占庭節(jié)點對共識過程進行詳細描述，DS-PBFT共識算法的共識流程如圖2所示.

圖2 GS-PBFT共識流程Fig.2 DS-PBFT consensus process

1.若共識節(jié)點中不存在拜占庭節(jié)點

1)節(jié)點發(fā)送請求消息給其所在小組的主節(jié)點.

2)主節(jié)點收到節(jié)點請求后首先校驗請求，驗證通過后為請求分配序號，然后將排序好的請求消息廣播給其它所有共識節(jié)點.

3)節(jié)點在收到排序好的請求消息后，執(zhí)行該請求，最后向發(fā)出請求的節(jié)點反饋結(jié)果.如果該節(jié)點收到其他所有節(jié)點反饋的消息并且全部相同，則共識成功.如果該節(jié)點沒有收到來自其它所有節(jié)點的反饋消息，或者反饋消息存在不同的情況，則speculation共識失敗.說明共識節(jié)點中存在拜占庭節(jié)點，轉(zhuǎn)到下面的共識流程.

2.若共識節(jié)點中存在拜占庭節(jié)點

1)節(jié)點將請求消息發(fā)送給其所在小組的主節(jié)點.

2)主節(jié)點收到請求后，首先校驗其正確性，校驗成功后為請求分配序號，接著生成預(yù)準備消息廣播給其所在小組內(nèi)的其他節(jié)點開始進行g(shù)roup共識即第1次PBFT共識.

3)group共識成功后，該小組的主節(jié)點會將生成的預(yù)準備消息廣播給其它主節(jié)點.主節(jié)點們在收到消息后會進行primary共識即第2次PBFT共識，在primary共識過程中各個主節(jié)點會將各自的數(shù)字簽名廣播給其他主節(jié)點并收集來自其他主節(jié)點的數(shù)字簽名.

4)primary共識成功后，各個主節(jié)點將收集到的數(shù)字簽名集合附帶請求生成打包消息廣播給其所在小組的其他節(jié)點，通知組內(nèi)其他節(jié)點共識成功.打包消息的數(shù)據(jù)結(jié)構(gòu)如圖3所示，其中Signaturei表示主節(jié)點i的數(shù)字簽名.

圖3 打包消息的數(shù)據(jù)結(jié)構(gòu)Fig.3 Data structure of packaged message

5)各個小組的節(jié)點在收到來自其主節(jié)點的打包消息后，為了保證請求通過了primary共識，會驗證數(shù)字簽名集合.驗證通過后執(zhí)行該請求內(nèi)容，然后各節(jié)點更新本地區(qū)塊鏈賬本，保證數(shù)據(jù)的一致性.

DS-PBFT共識算法偽代碼如下：

算法4.Consensus

Consensus algorithm

輸入：Initial node collectionU

Requestnodeclient

Initial groupsG

Collection of primary nodespList

輸出：Consensus resultsres

1.sendReq(client，client.primary，req)

2.res←false

3.res←startSC(gclient.group+pList)

4. ifresis false

5.res←startGC(gclient.group)&&startPC(pList)

6. ifresis true

7.pm←package(req)

8. forpinpList

9.broadcast(pNode，gpNode.group，pm)

10. fornodeingpNode.group&&verify(pm)

11.execute(req)

12. returnres

4 分 析

本文針對DS-PBFT算法、PBFT算法以及ND-PBFT算法，進行了理論分析以及實驗分析，理論上分析了兩個指標：節(jié)點間的平均延遲、通信次數(shù)，它們是影響共識時延和通信代價的因素.接下來從實驗的角度分析了單次共識的共識時延.

4.1 理論分析

4.1.1 節(jié)點間的平均延遲

對于DS-PBFT共識算法，在某個小組內(nèi)，假設(shè)已知節(jié)點A、B到另一個節(jié)點C的距離，那么根據(jù)三角不等式關(guān)系可以說明節(jié)點A、B之間的距離要小于節(jié)點A、B到節(jié)點C的距離之和.換句話說，如果節(jié)點A、B都是節(jié)點C的相鄰節(jié)點，那么肯定存在一個值，A、B之間的距離小于它.用數(shù)學公式表示如下：

|AC|<ε，|BC|<ε?|AB|<|AC|+|BC|<2ε

(3)

其中ε為小組內(nèi)兩個節(jié)點之間距離的上限值也就是前面說的閾值半徑.對于在以節(jié)點O為中心節(jié)點的小組里，用集合{An}表示在小組內(nèi)除O以外的節(jié)點，根據(jù)距離矩陣可以計算出各個節(jié)點之間距離的總和Distances，這里的距離指的是兩個節(jié)點之間的最短距離，最短距離可以通過Dijkstra算法求得.根據(jù)公式(3)可以推導(dǎo)出以下關(guān)系：

(4)

結(jié)合公式(3)和公式(4)，便可以推導(dǎo)出各個小組(包括主節(jié)點集合)內(nèi)任意兩節(jié)點之間的平均距離滿足公式(5).

(5)

對于PBFT共識算法，可以將所有共識節(jié)點當成一個小組，即可以看成所有節(jié)點分布在一個圓內(nèi)，取閾值半徑等于任意兩節(jié)點之間距離的最大值的一半.用同樣的方式也可以推導(dǎo)出系統(tǒng)中任意兩節(jié)點之間的平均距離，唯一的不同在于PBFT算法的閾值半徑以及節(jié)點數(shù)肯定大于DS-PBFT算法的，將它們反映到平面上也就是一個大圓包含若干個小圓，大圓的半徑肯定是大于包含其中的小圓的半徑.因此，DS-PBFT共識算法任意兩節(jié)點之間的平均距離肯定是小于傳統(tǒng)PBFT共識算法的.

對于ND-PBFT共識算法，假設(shè)DS-PBFT算法和ND-PBFT算法兩者參與到共識過程中的節(jié)點數(shù)是相同的.按照對PBFT算法同樣的分析方式也可以推導(dǎo)出DS-PBFT共識算法任意兩節(jié)點之間的平均距離是小于ND-PBFT共識算法的.

由此可知，在DS-PBFT中任意兩節(jié)點之間的平均距離都小于PBFT和ND-PBFT的情況下，DS-PBFT算法中任意兩節(jié)點的平均延遲肯定更小.由小及大，在消息傳輸速率相同的情況下，DS-PBFT共識算法的總的通信時延會更低.

4.1.2 通信次數(shù)

1)PBFT共識算法的通信次數(shù)

假設(shè)系統(tǒng)中有n(n>=16)個節(jié)點，下面按照PBFT共識算法的流程計算單次共識所需要的通信次數(shù).

預(yù)準備階段，主節(jié)點將預(yù)準備消息發(fā)送給其他所有節(jié)點，需要進行(n-1)次通信；準備階段，各個節(jié)點需要發(fā)送準備消息給其他節(jié)點，需要進行(n-1)(n-1)次通信；確認階段，各個節(jié)點生成確認消息并廣播給其他節(jié)點，又需要n(n-1)次通信.因此完成一次PBFT共識，總共需要的通信次數(shù)如下：

N1=n-1+(n-1)(n-1)+n(n-1)=2n(n-1))

(6)

2)DS-PBFT共識算法的通信次數(shù)

(7)

(8)

3)ND-PBFT共識算法的通信次數(shù)

(9)

顯然，ND-PBFT共識算法的通信次數(shù)要比PBFT少，因為ND-PBFT只是在PBFT的基礎(chǔ)上減少了參與共識的節(jié)點數(shù)量.下面比較ND-PBFT算法和DS-PBFT算法的通信次數(shù).

根據(jù)公式(7)、公式(8)可知，DS-PBFT算法當系統(tǒng)中不存在拜占庭節(jié)點時的通信次數(shù)要遠遠少于當系統(tǒng)中存在拜占庭節(jié)點時的.因此ND-PBFT算法只需要和當存在拜占庭節(jié)點時的DS-PBFT算法比較即可.于是可以推導(dǎo)出N4-N3滿足以下關(guān)系：

(10)

由式(10)可知，即使在存在拜占庭節(jié)點的情況下，DS-PBFT共識算法的通信次數(shù)也是遠遠少于ND-PBFT共識算法的.并且隨著系統(tǒng)中節(jié)點數(shù)的增加，DS-PBFT和ND-PBFT之間通信次數(shù)的差距還會越來越大.綜上所述，DS-PBFT在3者之間，單次共識所需要的通信次數(shù)是最少的，即總的通信代價是最低的.

4.2 實驗分析

4.2.1 實驗環(huán)境

操作系統(tǒng)：64位Windows10；編程語言：go；編程工具：GoLand，NS2[20]，GT-ITM[21]，go1.13.4.

實驗基于Transit-Stub模型[22]，通過NS2以及GT-ITM網(wǎng)絡(luò)拓撲生成器獲得一個帶有權(quán)值的網(wǎng)絡(luò)拓撲作為初始的節(jié)點集合，通過Dijkstra最短路徑算法計算節(jié)點之間的距離矩陣，使用Grouping算法將節(jié)點分成了若干組.基于go語言實現(xiàn)了PBFT共識算法、ND-PBFT共識算法以及DS-PBFT共識算法.最后在共識時延這個方面對這3種算法進行實驗分析.

4.2.2 共識時延

共識時延是指從節(jié)點發(fā)送請求到整個共識過程完成所需要的時間，公式如下所示：

Delay=Tfinish-Treq

(11)

實驗1.設(shè)置自變量為節(jié)點數(shù)量，將節(jié)點固定分成4組.實驗設(shè)置節(jié)點數(shù)量為16，20，24，28，32，36，40，通過增加節(jié)點數(shù)量來對比兩種算法的單次共識時延.在調(diào)整節(jié)點數(shù)的同時，始終保證DS-PBFT與ND-PBFT中共識節(jié)點數(shù)量一致.最終實驗結(jié)果如圖4所示，其中DS-PBFT(1)和DS-PBFT(2)分別指的是DS-PBFT算法在存在拜占庭節(jié)點和不存在拜占庭節(jié)點時的兩種情況.

圖4 固定分組數(shù)的共識時延對比Fig.4 Consensus delay comparison of fixed number of groups

由圖4可知，在分組數(shù)固定的情況下，DS-PBFT算法在兩種情況下的共識時延都要遠遠低于另外兩種算法的共識時延.隨著節(jié)點數(shù)量的增加，相比另外兩種算法，DS-PBFT算法的共識時延增長相對緩慢.說明DS-PBFT共識算法相對比較穩(wěn)定.同樣在兩種情況下的DS-PBFT算法，在不存在拜占庭節(jié)點時的共識時延更低，并且更穩(wěn)定.

實驗2.設(shè)置自變量為小組的數(shù)量，具體設(shè)置為4，5，6，7，8，9，10，將總的節(jié)點數(shù)固定為40個并始終保證DS-PBFT與ND-PBFT中共識節(jié)點的數(shù)量一致.通過增加小組數(shù)將存在拜占庭節(jié)點時的DS-PBFT算法與另外兩種算法進行對比，由于小組數(shù)量對當不存在拜占庭節(jié)點時的DS-PBFT算法沒有影響，因此不需要比較.最終實驗結(jié)果如圖5所示.

圖5 固定節(jié)點數(shù)的共識時延對比Fig.5 Consensus delay comparison of fixed number of nodes

由圖5可知，在總的節(jié)點數(shù)量一定時，分組數(shù)對DS-PBFT共識算法的共識時延有一定影響，但是始終還是要遠遠低于另外兩種算法的共識時延.并且當分組數(shù)為6的時候，DS-PBFT共識算法的共識時延相對是最低的；因此可以得出結(jié)論，當節(jié)點數(shù)量一定時，適當?shù)姆纸M數(shù)會使DS-PBFT算法有一個理想的共識時延.

5 總結(jié)與展望

5.1 總 結(jié)

本文為了解決PBFT算法和ND-PBFT這一類算法效率低下的問題，提出了DS-PBFT共識算法.基于Grouping算法的思想，將系統(tǒng)中距離較近的節(jié)點分成一組，選出各個小組中的主節(jié)點并且生成主節(jié)點候補集合，降低節(jié)點間的通信時延.同時結(jié)合speculation技術(shù)，減少算法的通信次數(shù)，從而降低算法的通信代價.最后通過理論以及實驗對比分析，本文提出的DS-PBFT共識算法相對傳統(tǒng)的PBFT以及ND-PBFT這一類算法，在共識時延、通信代價等方面有著很大的提升，提高了系統(tǒng)效率，更加適應(yīng)于當前的區(qū)塊鏈系統(tǒng).

5.2 展 望

雖然本文提出的DS-PBFT共識算法的運行效率相比傳統(tǒng)PBFT共識算法提升了許多，但還是存在著一些缺陷.比如，在未來的工作中可以完善獎懲機制，對系統(tǒng)中的拜占庭節(jié)點進行懲罰，減少系統(tǒng)中出現(xiàn)拜占庭節(jié)點的概率，從而提高系統(tǒng)的運行效率、穩(wěn)定性以及安全性.