一種基于權(quán)益代表的可擴展共識協(xié)議

李忠誠，黃建華，唐瑞琮，胡慶春，夏 旭

1.華東理工大學(xué)信息科學(xué)與工程學(xué)院，上海200237

2.香港DAEX 區(qū)塊鏈有限公司，上海200120

區(qū)塊鏈是一種按時間順序存儲的鏈式數(shù)據(jù)結(jié)構(gòu)[1]，具有去中心化、去信任、防篡改和可追溯等特性，在金融、物流[2]、醫(yī)療保健[3]、物聯(lián)網(wǎng)[4]等領(lǐng)域均展現(xiàn)了廣闊的應(yīng)用前景.

區(qū)塊鏈網(wǎng)絡(luò)中所有參與交易驗證的節(jié)點都具有完全相同的賬本，這樣區(qū)塊鏈就可以通過共識協(xié)議來確保這些節(jié)點狀態(tài)的一致性.共識協(xié)議主要分為兩類：基于證明的共識協(xié)議和基于投票的共識協(xié)議.基于證明的共識協(xié)議要求加入網(wǎng)絡(luò)的節(jié)點能證明自己比其他節(jié)點更有資格添加一個區(qū)塊到鏈上，這類算法主要有工作量證明（proof of work, PoW）、權(quán)益證明（proof of stake, PoS）等.PoW 和PoS 主要應(yīng)用于金融價值轉(zhuǎn)移的公有鏈，它們的共同問題是交易處理性能低，且共識過程只能保證最終一致性而非強一致性，易導(dǎo)致區(qū)塊鏈出現(xiàn)分叉、交易確認延遲等問題.基于投票的共識要求網(wǎng)絡(luò)中的節(jié)點交換當(dāng)前新區(qū)塊或者交易的驗證結(jié)果，然后根據(jù)驗證結(jié)果決定該區(qū)塊是否可以上鏈，這類協(xié)議包括拜占庭容錯協(xié)議（Byzantine fault tolerance, BFT）及其變種，如實用拜占庭算法（practical Byzantine fault tolerance, PBFT）、授權(quán)拜占庭容錯算法[5]（delegated Byzantine fault tolerance, DBFT）和Tendermint[6]等.拜占庭算法需要知道節(jié)點身份，以便它們之間交換區(qū)塊或消息，其主要問題是容易受到DoS攻擊，節(jié)點擴展性差.針對證明類和投票類共識協(xié)議存在的問題，文獻[7]提出用PBFT 來增強PoW 區(qū)塊鏈，目的是通過PBFT 來確保PoW 區(qū)塊鏈中的共識終結(jié)性.文獻[8]提出了SCP算法，將網(wǎng)絡(luò)劃分成許多子委員會以并行產(chǎn)生子區(qū)塊，并通過最終委員會來聚合子區(qū)塊以提高網(wǎng)絡(luò)的吞吐量，其不足是基于PoW 算法的分區(qū)過程耗時較長，并且最終委員會成員選舉機制容易遭受攻擊，可能導(dǎo)致生成錯誤的最終共識區(qū)塊.文獻[9]提出了ISCP 算法，取消了最終委員會，而使所有委員會都參與最終區(qū)塊的共識過程來解決SCP 存在的安全問題，但還是以PoW 作為分區(qū)算法，同樣存在分區(qū)時間過長的問題.

針對共識協(xié)議在平衡性能、安全性和可拓展性方面存在的問題，本文提出一種基于權(quán)利代表的可擴展共識協(xié)議（delegate-based scalable consensus protocol, DSCP）.DSCP 將網(wǎng)絡(luò)節(jié)點分區(qū)以形成若干獨立的共識分區(qū)，所有分區(qū)并行處理網(wǎng)絡(luò)交易產(chǎn)生的子區(qū)塊，子區(qū)塊由聚合層進行整合，從而實現(xiàn)區(qū)塊鏈的交易處理性能隨節(jié)點規(guī)模而同步擴展的目標，基于VRF 算法的分區(qū)機制確保了分區(qū)的高效性和隨機性，基于簡單投票的分區(qū)內(nèi)共識機制VCP（voting-based consensus protocol, VCP）進一步提升了網(wǎng)絡(luò)的性能.DSCP設(shè)計了一種押金和激勵機制，這樣誠實節(jié)點可以獲取獎勵，作惡節(jié)點會受到懲罰，增強了系統(tǒng)的安全.

1 研究現(xiàn)狀

區(qū)塊鏈系統(tǒng)的性能、安全和可擴展性與采用的共識協(xié)議有很大的關(guān)系，因此共識協(xié)議的研究一直是人們關(guān)注的熱點.最著名的共識協(xié)議就是比特幣系統(tǒng)采用的PoW 算法.PoW的問題是需要消耗大量算力去解決一個在算力上存在難度的謎題，以贏得區(qū)塊記賬權(quán)，且共識過程過于漫長，系統(tǒng)吞吐量低.基于消逝時間量的共識機制（proof of elapsed time, PoET）[10]是一種基于可信執(zhí)行環(huán)境的共識算法，用來抵御挖礦對于能源的消耗，但具體執(zhí)行時依賴于支持SGX 的Intel CPU，違背了區(qū)塊鏈的去中心化思想.文獻[11]提出了Bitcoin-NG 協(xié)議，該協(xié)議使用直接添加微區(qū)塊來規(guī)避工作量證明，以增加網(wǎng)絡(luò)吞吐量，減少網(wǎng)絡(luò)延時，但基于PoW 機制的主節(jié)點選舉可能導(dǎo)致主節(jié)點的不確定性，最終無法保證一致性.文獻[12]提出的閃電網(wǎng)絡(luò)則是通過專用快速通道增加區(qū)塊鏈網(wǎng)絡(luò)的交易吞吐量，但閃電網(wǎng)絡(luò)的鏈下交易環(huán)境的安全性難以保證.針對PoW類算法存在的能耗問題[13]，文獻[14]提出了PoS 算法，利用每個人的權(quán)益（代幣）并通過一個幸運因子來選擇有權(quán)添加區(qū)塊到鏈的礦工，降低了挖礦過程的能源消耗.PoS 中區(qū)塊的創(chuàng)建是通過消耗幣齡（coin age）來完成的，其問題是即使節(jié)點沒有連接到網(wǎng)絡(luò)幣齡也會增加，攻擊者依然可以對區(qū)塊鏈進行分叉并達成雙花.權(quán)益證明有很多不同的變種，如DPoS[15]、PoSV[16]和PoA[17]，都嘗試去解決上述問題，但是引入了新的安全性問題[18].以太坊中的PoS 算法還存在與PoW 算法類似的策略選擇困境[19]：權(quán)益較大者忠實于礦池能否獲得較高收益，權(quán)益較小者忠實于礦池是否能維持自己的收益并獲得相應(yīng)收益.

傳統(tǒng)的拜占庭算法（Byzantine fault tolerance, BFT）是一種性能高且具有強一致性的共識算法.最典型的是Hyperledger[20]區(qū)塊鏈平臺所采用的實用拜占庭算法PBFT.PBFT 交易處理能力可以達到每秒數(shù)千筆交易（transactions per second, TPS），且共識過程是確定性的.PBFT 算法交換區(qū)塊或消息時需要知道節(jié)點身份，通常只能用于安全性較高的聯(lián)盟鏈；此外，PBFT 還存在著節(jié)點擴展性差的問題，驗證節(jié)點數(shù)量的增加會使節(jié)點之間交換的消息量急劇增加（通信復(fù)雜度是O(N2)）.除了PBFT，相繼出現(xiàn)了進一步提升性能或魯棒性的BFT算法，如DBFT、HoneyBadger-BFT[21]、Tendermint 等.Tendermint 是一種基于DLS[22]協(xié)議改進的共識協(xié)議，憑借押金機制防止惡意攻擊者可能發(fā)起的女巫攻擊.與PBFT 不同的是，投票時節(jié)點之間廣播消息是通過Gossip 協(xié)議，這在一定程度上減少了共識過程的消息復(fù)雜度.然而，在節(jié)點數(shù)較多情況下，該系統(tǒng)的消息通信量依然很大.

混合型共識也是一種解決區(qū)塊鏈性能和拓展性問題的方法.SCP 就是一種混合型共識機制，它將網(wǎng)絡(luò)劃分成多個分區(qū)而并行產(chǎn)生區(qū)塊，使得區(qū)塊鏈網(wǎng)絡(luò)的吞吐量近似與分區(qū)數(shù)量成正比，大大提高了吞吐量.但是SCP 使用基于PoW 的分區(qū)機制，無法在安全性和性能上保持平衡.為了保證分區(qū)過程的安全性，需要設(shè)置較高的PoW 難度值以避免擁有高算力的惡意攻擊者的分區(qū)優(yōu)勢，但是較高的難度值會導(dǎo)致分區(qū)過程過長，影響網(wǎng)絡(luò)性能.此外，還有其他種類的混合型共識機制，如將PoW 和PoS 結(jié)合的Casper[23]協(xié)議等.

2 DSCP 共識協(xié)議

2.1 DSCP 網(wǎng)絡(luò)結(jié)構(gòu)

本文結(jié)合權(quán)益代表和層次化分區(qū)共識的思想，提出了基于權(quán)益代表的可擴展共識協(xié)議DSCP.如圖1所示，DSCP 是一種層次化的分區(qū)并行共識模型，網(wǎng)絡(luò)在邏輯上被劃分為上層的代理層和下層的分區(qū)層.

在每一輪共識過程中，通過分區(qū)機制將節(jié)點組織成多個獨立的分區(qū)，形成分區(qū)層.每個分區(qū)各自運行分區(qū)內(nèi)共識協(xié)議來并行處理一組獨立的交易，并將交易打包成共識子區(qū)塊，發(fā)送到代理層進行合并處理.多個分區(qū)并行處理網(wǎng)絡(luò)交易將大大提高網(wǎng)絡(luò)吞吐量，同時網(wǎng)絡(luò)節(jié)點數(shù)量的增加可以形成更多的分區(qū)，進一步提升了網(wǎng)絡(luò)的并行處理能力，實現(xiàn)了性能隨節(jié)點數(shù)量的增加而同步擴展的目標.為了防止節(jié)點作惡，分區(qū)層節(jié)點需要繳納押金才能參與共識.在共識過程中，一旦發(fā)現(xiàn)節(jié)點作惡，其他節(jié)點就可以發(fā)送節(jié)點作惡的證據(jù)，使作惡節(jié)點受到懲罰，其繳納的押金被沒收.

代理層的功能是檢查并整合子區(qū)塊中的交易，也就是將所有共識子區(qū)塊中正確的交易打包，形成最終的共識區(qū)塊向網(wǎng)絡(luò)廣播，接著開始下一輪的共識過程.代理層運行PBFT 共識協(xié)議并限定21 個節(jié)點以保證共識效率，但未使用分區(qū)層基于PBFT 改進的VCP 協(xié)議.代理層和分區(qū)層的最大區(qū)別就是節(jié)點數(shù)量的不同，為了盡可能增強分區(qū)的安全性，分區(qū)層的節(jié)點數(shù)量遠大于代理層，可見在節(jié)點數(shù)比較多（相對于代理層）的分區(qū)層分區(qū)中，使用VCP 可以大大提高共識速度.VCP 基于分區(qū)設(shè)計，其安全性的保證一部分來源于代理層的正確性，因此這種協(xié)議并不適用于代理層.代理層節(jié)點有限，在保證整個分層共識協(xié)議的強一致性和安全性下，使用PBFT同樣可以實現(xiàn)代理層的高性能共識.

圖1 分層共識模型Figure 1 Hierarchical consensus model

代理層節(jié)點由全網(wǎng)節(jié)點選舉產(chǎn)生，網(wǎng)絡(luò)中的節(jié)點采用類似DPoS 算法的方式選舉自己信任的節(jié)點作為代理層的成員.網(wǎng)絡(luò)節(jié)點通過投票從申請者中選舉出票數(shù)最多的前21 個節(jié)點作為候選代理層節(jié)點，這些節(jié)點必須繳納一定押金才能被確定為代理層節(jié)點.如圖2所示，在共識過程中，每產(chǎn)生21 個區(qū)塊作為一個周期epoch，每個epoch 中又分為21 個時隙slot，在每個slot 中，網(wǎng)絡(luò)都將完成一輪共識.不同于分區(qū)層中的分區(qū)，代理層的21 個節(jié)點輪流擔(dān)任每輪共識的leader 節(jié)點以完成子區(qū)塊的整合工作.當(dāng)一個epoch 結(jié)束時，網(wǎng)絡(luò)將重新選舉代理層節(jié)點，新選舉的代理層首先向網(wǎng)絡(luò)廣播一個隨機數(shù)種子seed，用在新的epoch 中，再將分區(qū)層節(jié)點重新隨機劃分到不同的分區(qū).

圖2 共識周期與時隙Figure 2 Consensus epoch and slot

2.2 基于VRF 的分區(qū)算法

分區(qū)算法將網(wǎng)絡(luò)節(jié)點劃分到不同分區(qū)，以實現(xiàn)各分區(qū)通過獨立并行共識同時處理交易的目的.為了提高分區(qū)的效率并保證分區(qū)的隨機性，本文提出了一種基于可驗證隨機函數(shù)VRF的分區(qū)算法，設(shè)計了基于押金的分區(qū)leader 節(jié)點選取機制以增強分區(qū)共識的安全性.在分區(qū)過程中，每個節(jié)點用可驗證隨機函數(shù)VRF 來計算一個隨機數(shù)ε，以決定節(jié)點自身所屬分區(qū).此外，節(jié)點還需計算隨機數(shù)證明p，以便向其他節(jié)點證明該隨機數(shù)并非節(jié)點惡意偽造.ε和p的計算公式分別為

式中，VRFVAL是產(chǎn)生隨機值的可驗證函數(shù)，VRFPROVE是可驗證隨機值的證明函數(shù)，Sk是節(jié)點私鑰，seed 是代理層每個階段公開的隨機數(shù)種子.隨機值的計算公式為

隨機值驗證函數(shù)為

節(jié)點在計算隨機值之后，需要發(fā)送一筆押金交易Participate?ε,p,Pk,deposit?給代理層（聚合層）的節(jié)點，聚合層的節(jié)點會記錄一段時間內(nèi)收到的所有Participate 交易，并根據(jù)這些交易信息決定節(jié)點所屬分區(qū)和每個分區(qū)的leader 節(jié)點.一段時間之后，聚合層會將這些押金退還給行為正確的節(jié)點.交納押金是為增強分區(qū)共識的安全性和利益分配的公平性，節(jié)點也只有在繳納一定的押金后才能參與共識.押金交易中包含節(jié)點計算出的隨機數(shù)ε和隨機數(shù)證明p，繳納押金的多少由參與共識的節(jié)點決定.代理層收到這些交易后，首先驗證隨機數(shù)證明和隨機數(shù)的相互匹配性，只要簡單地對證明p進行Hash 運算，并驗證是否與ε相等即可；隨后驗證隨機數(shù)證明的正確性，其計算公式分別為

式中，Pk是節(jié)點公鑰，p是隨機數(shù)證明.Dec 函數(shù)使用節(jié)點公鑰對證明進行解密，并驗證結(jié)果x是否與這一階段的隨機數(shù)種子seed 相同，若相同則表示隨機數(shù)驗證通過.代理層根據(jù)參與共識的節(jié)點數(shù)量確定分區(qū)數(shù)目為2n，并將分區(qū)層節(jié)點計算的隨機數(shù)的最后n位作為分區(qū)的標識ID，式（6）中的ID 值就是將節(jié)點計算的隨機數(shù)的最后4 位的數(shù)值作為分區(qū)ID 的例子.分區(qū)中節(jié)點的數(shù)量必須滿足一定閾值，因為節(jié)點數(shù)量過少可能導(dǎo)致分區(qū)內(nèi)惡意節(jié)點數(shù)量比例過高，甚至分區(qū)內(nèi)共識失敗.最后，聚合層選取各個分區(qū)當(dāng)中押金額最高的節(jié)點作為分區(qū)的leader節(jié)點，并將每個分區(qū)成員和leader 節(jié)點廣播到網(wǎng)絡(luò)中.

分區(qū)層節(jié)點接收到代理層廣播的分區(qū)信息之后，根據(jù)自己計算出的隨機值確定自己的分區(qū)ID，并連接到對應(yīng)分區(qū)的leader 節(jié)點.形成分區(qū)后，leader 節(jié)點將分區(qū)內(nèi)節(jié)點信息發(fā)送到分區(qū)的各個節(jié)點，之后分區(qū)開始處理網(wǎng)絡(luò)交易.與基于PoW 的分區(qū)機制相比，基于VRF 的分區(qū)算法幾乎不消耗任何算力，故速度更快.此外，基于VRF的分區(qū)算法輸出結(jié)果與基于PoW算法的輸出結(jié)果不但相同，而且完全隨機.這個隨機值還具有可驗證的特性，是節(jié)點無法惡意偽造的.

2.3 代理層

代理層負責(zé)接收分區(qū)層提交的子區(qū)塊，并將子區(qū)塊中的交易進行整合后打包成最終的共識區(qū)塊.當(dāng)每一個階段結(jié)束時，代理層還會產(chǎn)生一個隨機數(shù)種子，用于下一階段的分區(qū)層分區(qū)過程.

代理層對子區(qū)塊進行檢查時，首先檢查子區(qū)塊中是否含有非法的交易，驗證交易是否正確，并驗證子區(qū)塊對應(yīng)的簽名數(shù)量是否足夠.如果子區(qū)塊驗證通過，代理層就按照分區(qū)ID 的大小順序?qū)⒆訁^(qū)塊整合到一起；如果不同的子區(qū)塊出現(xiàn)交易沖突，也就是出現(xiàn)雙花交易，則將分區(qū)ID 靠后的子區(qū)塊中的交易刪除.

當(dāng)代理層檢測到子區(qū)塊中包含錯誤交易并且分區(qū)內(nèi)節(jié)點簽名數(shù)量超過2/3 時，就會向網(wǎng)絡(luò)發(fā)送子區(qū)塊錯誤證明，扣除相應(yīng)分區(qū)當(dāng)中所有簽名節(jié)點的押金.當(dāng)代理層檢測到子區(qū)塊并未包含足夠的節(jié)點簽名時，就會向網(wǎng)絡(luò)廣播該分區(qū)leader 節(jié)點作惡的證明，扣除該leader 節(jié)點的押金，并向該分區(qū)的所有節(jié)點發(fā)送更換leader 節(jié)點的消息，便于該分區(qū)重新提交區(qū)塊.

2.4 激勵機制

區(qū)塊鏈系統(tǒng)中時刻存在著誠實節(jié)點和惡意節(jié)點的博弈，而激勵機制是保證區(qū)塊鏈系統(tǒng)安全的重要一環(huán).DSCP 引入了獎懲機制，要求參與驗證的節(jié)點交納一定的押金，這樣誠實執(zhí)行協(xié)議的節(jié)點會獲得獎勵.因為作惡會被扣除押金，所以理性的節(jié)點會選擇誠實地執(zhí)行協(xié)議，并獲得獎勵.DSCP 的每一個共識slot 結(jié)束之后，新的區(qū)塊被添加到區(qū)塊鏈上.與此同時，系統(tǒng)會給予參與共識的誠實節(jié)點token 激勵，代理層和分區(qū)層節(jié)點則按比例分配獎勵（如代理層占10%，分區(qū)層占90%）.在分區(qū)層中，分區(qū)內(nèi)節(jié)點同樣也按繳納的押金比例分配獎勵，節(jié)點繳納的押金越多，獲得的共識激勵就越高；在代理層中，21 個節(jié)點則采取均分代理層獎勵的模式.

2.5 分區(qū)機制安全性分析

本文假設(shè)網(wǎng)絡(luò)當(dāng)中的惡意節(jié)點數(shù)量是有限的，不超過節(jié)點總數(shù)的1/3，網(wǎng)絡(luò)中節(jié)點間的通信是半同步的，即節(jié)點間通信存在不可忽略的延遲，但在有限長的時間內(nèi)消息一定會送達.本文將在以上的假設(shè)條件下證明協(xié)議的安全性.

DSCP 基于分區(qū)并行處理交易提高網(wǎng)絡(luò)吞吐量，網(wǎng)絡(luò)中的節(jié)點通過VRF 生成的分區(qū)隨機數(shù)來保證節(jié)點分布的隨機性和不可欺騙性.當(dāng)每一個共識階段結(jié)束時，代理層都會產(chǎn)生一個隨機數(shù)種子seed，能使每個共識階段的分區(qū)層節(jié)點都無法預(yù)知網(wǎng)絡(luò)的分區(qū)情況.節(jié)點根據(jù)VRF 計算出自己所在的分區(qū)都是隨機的，每個共識階段使用的隨機數(shù)種子都是不同的，保證了每個共識階段網(wǎng)絡(luò)的分區(qū)結(jié)果都截然不同.惡意攻擊者無法預(yù)知網(wǎng)絡(luò)中節(jié)點的分區(qū)結(jié)果，也無法使惡意節(jié)點聚集到相同的分區(qū)當(dāng)中.除此之外，VRF 的引入消除了惡意節(jié)點合謀的可能.節(jié)點在公布自己計算的分區(qū)隨機數(shù)之外，還需要提供隨機數(shù)證明P，其計算公式為

隨機數(shù)的驗證過程如下：

步驟1對節(jié)點提供的隨機數(shù)證明P進行Hash 運算，并驗證R=Hash(P)是否成立，若成立如式（8）所示，則繼續(xù)下一步的驗證，否則該證明是無效的；

步驟2使用節(jié)點公鑰解密證明P，得到結(jié)果seed′，驗證seed′=seed 是否成立，如果成立，則驗證過成功，證明有效，否則證明無效.

只有將節(jié)點的私鑰作為輸入?yún)?shù)才能生成該隨機數(shù)的正確的隨機數(shù)證明，并且在隨機數(shù)的生成函數(shù)中，seed 是全局變量，是已知的，因此惡意攻擊者無法偽造隨機數(shù)證明，自然也就無法偽裝成某個分區(qū)的成員節(jié)點，從而保證網(wǎng)絡(luò)中的節(jié)點被完全隨機分配到各個分區(qū)當(dāng)中.除此之外，節(jié)點必須繳納押金才能加入分區(qū)參與共識，并且分區(qū)層節(jié)點獲取到的獎勵和繳納的押金成正比.在經(jīng)濟學(xué)的理性模型中，節(jié)點為了獲取更多的共識激勵，愿意繳納更多的押金，以競爭分區(qū)內(nèi)的leader 節(jié)點，而惡意節(jié)點想要成為leader 節(jié)點則必須繳納比分區(qū)內(nèi)任何其他節(jié)點更多的押金.但從上面分析可知：惡意節(jié)點在形成分區(qū)之前是無法獲知分區(qū)內(nèi)其他節(jié)點的信息的，也就無法確定成為leader 節(jié)點需要繳納多少押金.如果惡意節(jié)點盡可能繳納更多的押金，那么其作惡行為一旦被發(fā)現(xiàn)，就會被扣除所有押金，承受巨大經(jīng)濟損失.

3 分區(qū)內(nèi)共識協(xié)議

在DSCP 中，每個分區(qū)是一個獨立的共識組.各分區(qū)并行處理網(wǎng)絡(luò)交易，生成自己的共識子區(qū)塊.為了提高分區(qū)的共識效率，減少節(jié)點間的通信復(fù)雜度，本文提出了基于投票的共識協(xié)議（voting-based consensus protocol, VCP），用于分區(qū)的共識過程.

3.1 VCP 協(xié)議過程

DSCP 的每個分區(qū)都有一個leader 節(jié)點，負責(zé)對當(dāng)前分區(qū)處理的交易進行驗證并打包成子區(qū)塊，完成分區(qū)內(nèi)的共識過程后將共識子區(qū)塊發(fā)送到代理層.leader 節(jié)點是分區(qū)節(jié)點中押金繳納最多的節(jié)點，這也意味著：一旦leader 節(jié)點作惡，所承受的懲罰也就越大.

VCP 共識過程包括6 個階段，如圖3所示：

圖3 VCP 協(xié)議時序圖Figure 3 VCP protocol sequence diagram

VCP 協(xié)議的運行過程如下：

1）Trans_collect 階段

客戶端首先將交易的Hash 廣播到網(wǎng)絡(luò)，分區(qū)節(jié)點根據(jù)收到交易的Hash 判斷該交易是否由本分區(qū)處理.如是，則leader 節(jié)點給本分區(qū)的其他節(jié)點發(fā)送消息TRANSORDER?seqnum,transhash?，其中seqnum 是由leader 分配給交易的一個唯一序列號，序列號是自然遞增的，不同交易的序列號不同.transhash 是交易Hash，其他節(jié)點在收到交易的Hash 后，發(fā)送響應(yīng)RESP?seqnum,transhash,signature?給leader 節(jié)點，leader 節(jié)點將交易的序列號和分區(qū)內(nèi)其他節(jié)點的RESP 消息都發(fā)送給交易發(fā)起者，隨后交易發(fā)起者將交易的詳細信息發(fā)送給leader 節(jié)點.在Trans_collect 階段結(jié)束時，leader 節(jié)點將接收到的所有交易打包，進入下一個階段.

2）Prepare 階段

leader節(jié)點向分區(qū)內(nèi)的其他節(jié)點發(fā)送消息prepare?BlockHash, Timestamp, Block, TransExclude, Signature?，其中，BlockHash 是子區(qū)塊的SHA256 Hash 值，Block 是打包好的子區(qū)塊，包含分區(qū)按順序處理的正確交易信息.交易在分配序列號的時候無法得知交易詳情，因此交易中可能含有與已有的區(qū)塊鏈數(shù)據(jù)沖突的非法交易.非法交易都包含在TransExclude中，Timestamp 是區(qū)塊生成的時間戳，Signature 是leader 節(jié)點對區(qū)塊Hash 的簽名信息.

3）Endorsement 階段

除leader 外，分區(qū)的其他節(jié)點檢查prepare 消息中的區(qū)塊是否正確，包括檢查交易的順序是否正確，檢查每筆交易的詳情和交易的Hash 值是否匹配，并對交易的正確性進行驗證.如果區(qū)塊驗證成功，則向leader 節(jié)點發(fā)送endorsement?BlockHash, Signature?消息，否則向分區(qū)內(nèi)其他節(jié)點發(fā)送LEADER-REPLACE?BlockHash, Block, Signature?消息，消息中包含leader 節(jié)點發(fā)送到該節(jié)點的區(qū)塊Hash 值、區(qū)塊詳情和leader 節(jié)點的簽名信息.其他節(jié)點接收到LEADER-REPLACE 消息后對該消息進行驗證，如果確認leader 節(jié)點作惡，則分區(qū)內(nèi)所有正確節(jié)點將向代理層發(fā)送leader 節(jié)點作惡的簽名證據(jù)、代理層需要收到至少2/3 的節(jié)點對leader 節(jié)點作惡證據(jù)的簽名才會認為leader 作惡屬實.

4）Commit 階段

當(dāng)leader 節(jié)點收集到分區(qū)內(nèi)至少2/3 節(jié)點對leader 節(jié)點發(fā)送的區(qū)塊Hash 的簽名時，leader 節(jié)點將該分區(qū)生成的子區(qū)塊和至少2/3 節(jié)點簽名發(fā)送到代理層節(jié)點.

5）Confirm 階段

代理層對分區(qū)提交的子區(qū)塊進行驗證，然后給分區(qū)的leader 節(jié)點返回驗證結(jié)果和代理層節(jié)點的簽名；

6）Response 階段

分區(qū)leader 節(jié)點向分區(qū)內(nèi)其他節(jié)點發(fā)送代理層的響應(yīng)消息.

為了保證網(wǎng)絡(luò)中每個分區(qū)交易處理負載的均衡性，DSCP 為每筆交易都指定了處理的分區(qū).交易內(nèi)容的Hash 決定了該筆交易由哪個分區(qū)處理.在Trans_collect 階段，客戶端首先向分區(qū)層某個節(jié)點提交交易的Hash 值、公鑰和簽名，分區(qū)層節(jié)點在接收到交易的Hash 等相關(guān)信息后判斷當(dāng)前分區(qū)是否有權(quán)處理該交易.如果交易Hash 值的最后n位與該分區(qū)的分區(qū)ID 相同，則處理該交易；否則，收到該交易的節(jié)點會將交易發(fā)送給應(yīng)當(dāng)處理該交易的分區(qū)的leader 節(jié)點，并將leader 節(jié)點的網(wǎng)絡(luò)地址發(fā)送給客戶端.客戶端只有在分區(qū)的leader 節(jié)點給交易分配序列號之后才向該分區(qū)leader 節(jié)點發(fā)送交易的詳細信息.DSCP 每個分區(qū)在處理交易時不僅要保證交易的正確性，還要保證交易的順序.在交易分配序列號時，leader 節(jié)點無法提前獲知交易的詳細信息，自然也就無法差別對待交易.在序列號分配之后，leader 節(jié)點將無法改變交易的順序.

3.2 VCP 協(xié)議復(fù)雜度分析

與傳統(tǒng)的PBFT 協(xié)議相比，VCP 協(xié)議能夠在保證共識過程安全的同時實現(xiàn)更高的性能.圖4給出了正常情況下PBFT 協(xié)議的共識過程，該過程需要經(jīng)過3 個階段：Preprepare、Prepare、Commit.為了保證分區(qū)內(nèi)各個節(jié)點數(shù)據(jù)的一致性，在Prepare 和Commit階段，分區(qū)內(nèi)節(jié)點之間要相互發(fā)送消息.在基于分層的網(wǎng)絡(luò)結(jié)構(gòu)中，分區(qū)內(nèi)節(jié)點在最后的reply階段將共識子區(qū)塊發(fā)送到代理層節(jié)點.假設(shè)分區(qū)內(nèi)節(jié)點數(shù)量為c，則完成一輪共識過程所需要的通信次數(shù)為SUMmsg=2c2?c，則通信復(fù)雜度為O(c2).

圖4 PBFT三階段協(xié)議Figure 4 PBFT three-phase protocol

圖5給出了本文提出的基于投票的分區(qū)內(nèi)共識協(xié)議VCP 在正常情況下的協(xié)議過程，包括Proposal、Endorsement、Submit、Confirm、Response 階段.在Endorsement 階段，分區(qū)內(nèi)節(jié)點只將自己的投票區(qū)塊信息發(fā)送給leader 節(jié)點，而不向分區(qū)內(nèi)其他節(jié)點發(fā)送自己的投票信息.假設(shè)分區(qū)內(nèi)節(jié)點數(shù)量為c，則完成一輪共識過程所需要的通信次數(shù)為SUMmsg=N+c+c+c ?3=3c ?3+N，則通信復(fù)雜度為O(c).

由以上對比分析可知：VCP 協(xié)議過程可以大大減少節(jié)點間的通信次數(shù)，提高了共識效率，尤其是在半同步和異步網(wǎng)絡(luò)環(huán)境下?lián)碛懈用黠@的性能優(yōu)勢.

圖5 VCP 多階段協(xié)議Figure 5 VCP multi-stage protocol

3.3 VCP 協(xié)議安全性分析

VCP 是一種基于投票的共識協(xié)議，leader 節(jié)點負責(zé)對交易進行排序并將正確的交易打包成子區(qū)塊提交給分區(qū)內(nèi)其他節(jié)點進行共識，最后將子區(qū)塊提交到代理層.分區(qū)內(nèi)其他節(jié)點只需對leader 節(jié)點提議的區(qū)塊進行驗證，并對其認為正確的區(qū)塊進行簽名背書即可，這保證了VCP 共識協(xié)議的簡單高效.如果leader 節(jié)點作惡，向分區(qū)內(nèi)節(jié)點發(fā)送不同的區(qū)塊，當(dāng)且僅當(dāng)分區(qū)內(nèi)2/3 節(jié)點都是作惡節(jié)點時，分區(qū)才會向代理層提交錯誤區(qū)塊，否則leader 節(jié)點無法提交含有足夠簽名的子區(qū)塊，也就無法收到代理層的正確響應(yīng).leader 節(jié)點作惡會被扣除押金，由于leader 節(jié)點是其分區(qū)繳納押金數(shù)最多的節(jié)點，作惡的leader 節(jié)點將會遭受極大的經(jīng)濟損失.如果leader 節(jié)點是誠實節(jié)點，按照繳納押金比例分配交易費的機制就會使leader節(jié)點獲得最高的經(jīng)濟收益.繳納押金越多，誠實節(jié)點獲得的收益也越多.有了押金和激勵機制作為保障，繳納更多押金的節(jié)點一旦作惡，將受到更嚴厲的經(jīng)濟懲罰.

在VCP 當(dāng)中，分區(qū)內(nèi)節(jié)點一旦發(fā)現(xiàn)leader 節(jié)點作惡，則可以請求更換leader 節(jié)點.leader節(jié)點的更換依照節(jié)點的押金高低次序進行，新的leader 節(jié)點必須是剩余節(jié)點中繳納押金數(shù)量最多的節(jié)點.

4 實驗分析

4.1 實驗環(huán)境

實驗采用Docker 容器虛擬化技術(shù)模擬網(wǎng)絡(luò)節(jié)點，軟件版本為Docker Community Edition Version 17.09.0-ce-win33(13620)，協(xié)議代碼基于Python3 實現(xiàn)，節(jié)點間通信使用UDP 協(xié)議，使用官方python:3.5.4-jessie Docker 鏡像作為協(xié)議代碼運行環(huán)境，宿主機操作系統(tǒng)為Windows 10 專業(yè)版Version 14393.1770，運行內(nèi)存8 GB，操作系統(tǒng)分配給Docker 的內(nèi)存為2 GB.

4.2 DSCP 分區(qū)速度測試

本文首先測試了DSCP進行分區(qū)的耗時.分區(qū)速度實驗測試了不同節(jié)點數(shù)量下基于VRF的分區(qū)過程耗時，并與PoW 的分區(qū)耗時進行對比，所得結(jié)果如圖6所示.可以看出，隨著節(jié)點數(shù)量的增加，基于VRF 的分區(qū)耗時幾乎不變，且明顯低于基于PoW 的分區(qū)耗時，原因是為了保證網(wǎng)絡(luò)的安全性，抵抗女巫攻擊，基于PoW 進行分區(qū)時需要每個節(jié)點花費一定的時間去尋找滿足條件的nonce 值.本實驗的難度值設(shè)置得非常低，只要花費很少的算力即可得到滿足條件的nonce 值，但過低的難度值也意味著網(wǎng)絡(luò)受到女巫攻擊的可能性增大.由圖6可以看出：隨著節(jié)點數(shù)量的增多，PoW 分區(qū)耗時逐步增大，這是因為實驗環(huán)境服務(wù)器的計算性能有限.當(dāng)越來越多的節(jié)點消耗算力時，每個節(jié)點擁有的平均算力會減少，節(jié)點越多，這種算力減少帶來的影響也就越明顯.基于VRF 的分區(qū)耗時基本保持不變，因為在VRF 機制中，計算分區(qū)隨機數(shù)所消耗的時間只與正向Hash 運算的速度有關(guān)，而與PoW 相比，正向Hash 運算時幾乎不消耗算力，這充分驗證了基于VRF分區(qū)機制在性能上的優(yōu)勢.

4.3 VCP 性能測試

VCP 協(xié)議的性能實驗分別對協(xié)議的一致性時延和吞吐量進行了測試.一致性時延實驗分別測試了VCP 和PBFT 在同一分區(qū)完成一次共識過程所用的時間，不斷增加分區(qū)內(nèi)的節(jié)點數(shù)量，就可以得到兩個協(xié)議在相同條件下的共識時延增長趨勢，其中每個數(shù)據(jù)都是在相同條件下進行20 次實驗的平均結(jié)果.如圖7所示，PBFT 協(xié)議的共識時延隨區(qū)內(nèi)節(jié)點數(shù)量的增加近似呈二次方增長，而VCP 協(xié)議的共識時延則只是隨節(jié)點數(shù)量呈緩慢的近似線性增長，這是因為PBFT的消息復(fù)雜度為O(c2)，而VCP 的消息復(fù)雜度為O(c).VCP 簡化了共識過程的步驟，減少了消息通信量，完成一次共識需要交換的消息量明顯少于PBFT，大大降低了共識時延.

圖6 基于PoW 和VRF 的分區(qū)時延對比Figure 6 Partition delay in consensus under PoW and VRF

圖7 VCP 和PBFT 的共識時延Figure 7 Delay in consensus under VCP and PBFT

吞吐量實驗測試了同一個分區(qū)分別運行VCP 協(xié)議和PBFT 協(xié)議時的性能.在測試中以固定的速率發(fā)送一定數(shù)量的請求（本實驗為200），并不斷增大請求的發(fā)送速率.當(dāng)分區(qū)無法處理完所有請求而開始出現(xiàn)請求丟失時，我們就把這種情況作為臨界條件.吞吐量實驗比較了兩個協(xié)議在不同的請求發(fā)送速率下的失敗率，如圖8所示.當(dāng)速率增大到每秒185 個請求時，運行PBFT 協(xié)議的分區(qū)出現(xiàn)了請求處理失敗的情況，而在運行VCP 協(xié)議的分區(qū)中，速率達到每秒333 個請求時才會出現(xiàn)請求處理失敗的情況.這是因為運行VCP 協(xié)議的分區(qū)的性能更高，能夠處理更多的并發(fā)請求，所以在相同的請求發(fā)送速率下，VCP 分區(qū)的失敗率遠遠低于PBFT分區(qū)的失敗率，這與共識時延測的結(jié)果相符.運行VCP 協(xié)議的分區(qū)完成一次共識過程的時間更短，因此相對于PBFT 算法，相同時間內(nèi)運行VCP 協(xié)議的分區(qū)能夠處理的交易請求數(shù)量更多，顯然性能更好.

4.4 DSCP 性能測試

性能實驗分別測試了DSCP 和PoW 協(xié)議的吞吐量，所得結(jié)果如圖9所示.由實驗結(jié)果可以看出：DSCP 的吞吐量明顯高于PoW 的吞吐量，且隨節(jié)點數(shù)量的增長呈近線性的增加；而節(jié)點數(shù)量的增長對PoW 的吞吐量影響不大.造成這種現(xiàn)象的原因是：隨著網(wǎng)絡(luò)中共識節(jié)點數(shù)量的增加，DSCP 中的共識分區(qū)數(shù)量也隨之不斷增加，因為每個分區(qū)并行處理交易，所以分區(qū)數(shù)越多，能同時處理的交易請求量越大，系統(tǒng)的吞吐量也在不斷提高.請求越多，分區(qū)越多，迫使代理層消耗更長的時間來整合來自下層的更多子區(qū)塊，因此網(wǎng)絡(luò)吞吐量無法隨分區(qū)數(shù)的增加呈完全線性增長.與網(wǎng)絡(luò)中消息通信的時延相比，代理層對子區(qū)塊驗證和整合所需要的時間對系統(tǒng)吞吐量的影響可以忽略不計，并且提高代理層節(jié)點的計算性能、存儲能力，可以大大縮短代理層驗證與整合子區(qū)塊的時間.與之相對應(yīng)的是，基于PoW 的共識機制無論網(wǎng)絡(luò)中的節(jié)點數(shù)量有多少，每個共識周期只能生成一個共識區(qū)塊，且每個共識周期所消耗的時間也基本保持不變，即使網(wǎng)絡(luò)中的節(jié)點數(shù)量增加，也不會對系統(tǒng)的吞吐量有任何的貢獻，反而節(jié)點數(shù)量越多，所消耗的算力越大，造成能源浪費更多.

圖8 VCP和PBFT協(xié)議吞吐量Figure 8 Throughput in consensus under VCP and PBFT

圖9 基于DSCP和PoW的系統(tǒng)吞吐量對比Figure 9 System throughput under DSCP and PoW

5 結(jié) 語

基于分區(qū)并行的區(qū)塊鏈共識協(xié)議相較于單個共識過程只生成一個區(qū)塊的協(xié)議具有明顯的性能優(yōu)勢，本文提出的高性能共識算法DSCP 彌補了目前分區(qū)共識機制存在的不足，提出的基于VRF 的分區(qū)機制不需要任何算力證明也可以在很短的時間內(nèi)完成大量共識節(jié)點的分區(qū)過程，且能保證分區(qū)的隨機性和安全性.為了進一步提高共識協(xié)議的性能，還設(shè)計了基于投票的分區(qū)內(nèi)共識協(xié)議VCP，可以在較低的消息復(fù)雜度下實現(xiàn)分區(qū)內(nèi)的共識.設(shè)計的押金與激勵機制大大提高了惡意節(jié)點作惡難度，保證了網(wǎng)絡(luò)的安全性，同時也使誠實節(jié)點可以獲得較高的收益.實驗結(jié)果表明：基于VRF 的分區(qū)機制能夠?qū)崿F(xiàn)更加快速的分區(qū)，相較于PBFT 協(xié)議，所提出的VCP 共識協(xié)議明顯降低了消息復(fù)雜度，有效提升了共識性能，DSCP 協(xié)議處理交易的吞吐量能夠隨著網(wǎng)絡(luò)節(jié)點數(shù)量增加而實現(xiàn)近線性增長，使區(qū)塊鏈的性能和安全性都得到明顯的改善.