基于綜合選舉的DPoS 共識算法

王 兵，李輝靈，牛新征

（1.西南石油大學(xué) 計算機科學(xué)學(xué)院，成都 610500；2.電子科技大學(xué) 計算機科學(xué)與工程學(xué)院，成都 611731）

0 概述

區(qū)塊鏈的提出引起了學(xué)術(shù)界與業(yè)界的廣泛關(guān)注，其為集中式機構(gòu)的高成本、低效率和數(shù)據(jù)存儲［1］不安全性提供了解決方案［2］。區(qū)塊鏈底層是一系列技術(shù)集成的分布式賬本系統(tǒng)，系統(tǒng)中每一個區(qū)塊的架構(gòu)包含了交易數(shù)據(jù)［3］、父區(qū)塊Hash 值［4］、Merkle 樹［5］等信息。根據(jù)技術(shù)的不同從下到上分為數(shù)據(jù)層、網(wǎng)絡(luò)層、共識層、激勵層、合約層、應(yīng)用層［6］，且隨著技術(shù)的不斷發(fā)展，區(qū)塊鏈能夠與智能合約［7］相結(jié)合，并出現(xiàn)了許多的Dapp應(yīng)用［8-10］，為現(xiàn)實世界提供了從信息到價值的傳遞功能。

區(qū)塊鏈中各節(jié)點能自發(fā)、誠實地遵守協(xié)議中預(yù)先設(shè)定的規(guī)則并保持全局狀態(tài)一致，共識算法起著至關(guān)重要的作用。工作量證明（Proof of Work，PoW）［11-12］機制作為主流的共識算法之一，其依賴計算機算力競爭記賬權(quán)，一個新的區(qū)塊生成需要計算出符合條件的哈希值，但算力爭奪會消耗大量資源。為減緩資源的大量消耗，研究人員提出權(quán)益證明（Proof of Stake，PoS）［13］共識算法，根據(jù)持有數(shù)字貨幣數(shù)量和時間來分配相應(yīng)利息的制度。PoS 的進一步演變是股份授權(quán)證明（Delegate Proof of Stake，DPoS）［14］共識算法，其原理是讓每一個股份節(jié)點進行投票，由此產(chǎn)生權(quán)利對等的101位委托人節(jié)點。隨著聯(lián)盟鏈共識機制［15］的興起，實用拜占庭容錯（Practical Byzantine Fault Tolerance，PBFT）［16］共識算法被提出，按照少數(shù)服從多數(shù)原則，經(jīng)主節(jié)點提交提議至其他共識節(jié)點進行確認，當(dāng)超過2/3 的節(jié)點確認后則提議通過［17］。Raft［18］可作為一種典型的聯(lián)盟鏈共識算法，該算法包含3 種角色，分別是跟隨者、候選人和領(lǐng)導(dǎo)者，這3 種角色能隨著時間和條件的變化而互相轉(zhuǎn)換。

本文提出一種基于綜合選舉的DPoS（Comprehensive Election DPoS，CE-DPoS）共識算法。該算法摒棄原DPoS 按股份投票的方式，節(jié)點之間能夠根據(jù)自身意愿進行投票，在符合現(xiàn)實情況的同時，新節(jié)點的加入不受股份的影響，提升了節(jié)點之間的投票活躍度。DPoS 節(jié)點的通信代價主要受前置節(jié)點和后置節(jié)點的影響，而CE-DPoS 共識算法根據(jù)預(yù)設(shè)的網(wǎng)絡(luò)信息表選取節(jié)點，以降低網(wǎng)絡(luò)通信消耗。

1 DPoS 共識算法相關(guān)研究

DPoS 共識算法憑借低延時、出塊時間短、高吞吐量、幾乎不分叉的特點及優(yōu)勢，得到了研究人員的廣泛使用［19］，區(qū)塊鏈架構(gòu)如圖1 所示。DPoS 相較于PoW 有更低的能源消耗，減少了硬件資源的消耗，且繼承了PoS的股份思想，具有比PoS 更快的效率和更高的性能。DPoS 共識算法在選舉委托人節(jié)點過程中，由持有股份的節(jié)點相互投票（投票權(quán)重與股份成正比），即每個股東節(jié)點可以將其持有的股份作為選票授予一個代理人，最終選定的節(jié)點為票數(shù)靠前的n個節(jié)點，選定的n個節(jié)點輪流進行打包交易和出塊。但持有股份越多的節(jié)點當(dāng)選委托人節(jié)點的概率極大，造成了弱中心化，并容易導(dǎo)致Dos 攻擊［20］。

圖1 區(qū)塊鏈結(jié)構(gòu)Fig.1 Structure of blockchain

由此，許多學(xué)者對DPoS 共識算法做了進一步優(yōu)化。文獻［21］提出了節(jié)點的升降機制，從對惡意節(jié)點的識別角度出發(fā)，對良好節(jié)點和惡意節(jié)點通過降級的方式加以區(qū)分。文獻［22］在節(jié)點升降的基礎(chǔ)上引入了誠實節(jié)點的動態(tài)選舉，有效降低選取惡意節(jié)點的概率，但對節(jié)點投票活躍度沒有明顯提升。文獻［23］引入了信用值，為每一個節(jié)點設(shè)定一個信用值，信用值作為當(dāng)選委托人節(jié)點的一個重要參考指標(biāo)，每輪共識結(jié)束后信用值發(fā)生改變，但信用值的積累可能導(dǎo)致信用值高者越高的情況。文獻［24］將DPoS 中的節(jié)點分為不同的信譽狀態(tài)，同樣可能導(dǎo)致信譽值高的節(jié)點一直處于高信譽的問題。從優(yōu)化投票的角度出發(fā)，文獻［25］提出細化投票的思想，其中包括支持票、棄權(quán)票、反對票，通過3 種方式度量節(jié)點的意愿投票傾向，文獻［26］根據(jù)細化的投票方式又做了進一步優(yōu)化，增加10 分支持票、10 分反對票的投票方式，改善了單一投票的方式，但不能完全滿足現(xiàn)實狀況的實際投票人的意愿權(quán)重。

2 CE-DPoS 共識算法方案

由于經(jīng)典DPoS 共識算法選舉節(jié)點固定單一，且始終是股份占比較大的節(jié)點，導(dǎo)致股份占比少的節(jié)點活躍度急劇下降。同時選舉出委托人節(jié)點后，出塊順序未考慮節(jié)點之間的通信消耗，加大了出塊時間。針對上述問題，本文提出一種CE-DPoS 共識算法。每個節(jié)點根據(jù)自身的意愿相互投票，在一輪共識投票結(jié)束后，模型網(wǎng)絡(luò)會計算出每個節(jié)點的最終加權(quán)票數(shù)，并進行降序排列。每個節(jié)點在加入?yún)^(qū)塊鏈網(wǎng)絡(luò)前，會和網(wǎng)絡(luò)中的其他節(jié)點進行通信，隨后根據(jù)通信的代價建立自身節(jié)點的網(wǎng)絡(luò)信息表，網(wǎng)絡(luò)信息表中存儲的是與自身通信開銷最小的某些節(jié)點。最終依據(jù)網(wǎng)絡(luò)的連接情況，依次動態(tài)選擇通信量少并且分值最大的節(jié)點。

2.1 CE-DPoS 投票模型計算方式

在公有鏈網(wǎng)絡(luò)中，節(jié)點參與活躍度與網(wǎng)絡(luò)的安全性息息相關(guān)，在經(jīng)典DPoS 共識算法中，節(jié)點投票有失公平性，節(jié)點出現(xiàn)投票政治冷漠性。為極大程度地滿足節(jié)點的投票意愿傾向和公平性，對投票意愿設(shè)置等級。CE-DPoS 投票模型中的符號說明如表1 所示。

表1 符號說明Table 1 Symbol description

設(shè)定投票權(quán)重為Si，其中Si={i|i=1，2，3，4，5}，權(quán)重依次遞增為：S1≤S2≤S3≤S4≤S5，投票意愿分別對應(yīng)于［0～19%］、［20%～39%］、［40%～59%］、［60%～79%］、［80%～100%］。CE-DPoS 和DPoS 共識算法中最大投票數(shù)相同，每個節(jié)點至多對其他30 個節(jié)點投票。本文通過實驗仿真進行模擬投票，統(tǒng)計投票信息的權(quán)重占比，若曲線出現(xiàn)近似正態(tài)分布，權(quán)重S1、S2與權(quán)重S5投票數(shù)大致相同，且均低于投票權(quán)重S3、S4，便于系統(tǒng)票數(shù)的計算，采用3 個集合Γ1、Γ2、Γ3進行票數(shù)的統(tǒng)計：Γ1代表投票意向為（0，39%］，集合中投票評分對應(yīng)S1、S2；Γ2代表投票意向為［40%，79%］，集合中投票評分對應(yīng)S3、S4；Γ3代表投票意向為［80%，100%］，集合中投票評分對應(yīng)S5。

設(shè)節(jié)點收到其他節(jié)點的投票數(shù)為m（m值不涉及投票分值，一個節(jié)點參與投票即一票），節(jié)點對另一個節(jié)點評分值用Φ表示，其中Φi表示第i個節(jié)點的評分值。所有投票分值的中位數(shù)為，平均值為，節(jié)點最終分值如式（1）所示：

表2 列舉了3 個節(jié)點的得票情況，節(jié)點之間對其他節(jié)點進行權(quán)重投票。

表2 節(jié)點得票數(shù)Table 2 Number of votes by the node

按照式（1）計算得到節(jié)點的最終分值：

不失一般性，設(shè)當(dāng)前有11 個節(jié)點參與投票，則對于11 個候選節(jié)點出現(xiàn)的得票權(quán)可能性p如式（2）所示：

其中：mi表示票權(quán)為i的票數(shù)總和。

節(jié)點投票出現(xiàn)的所有可能結(jié)果以概率的形式表示，所有結(jié)果的概率之和為1，如下式所示：

通過計算，將節(jié)點得分按降序排列：

2.2 CE-DPoS 委托人節(jié)點選取

在網(wǎng)絡(luò)信息表的基礎(chǔ)上，選定所有節(jié)點中分數(shù)排名最高的節(jié)點A，從節(jié)點A網(wǎng)絡(luò)信息表中選出除節(jié)點A外分數(shù)排名最高的節(jié)點B，再從節(jié)點B網(wǎng)絡(luò)信息表中選出除B外分數(shù)排名最高的節(jié)點C，直至選定n個委托人節(jié)點，整體過程如圖2 所示。

圖2 CE-DPoS 委托人節(jié)點選舉流程Fig.2 Procedure of CE-DPoS delegate node election

區(qū)塊鏈網(wǎng)絡(luò)中的交互主要通過節(jié)點之間的通信，通信快慢直接或間接影響著整個區(qū)塊鏈的性能。文獻［27］定義了節(jié)點發(fā)生沖突塊的概率Pr(F=0)，如式（3）所示：

其中：T為區(qū)塊最大傳播時延；G（t）代表多個區(qū)塊傳播給節(jié)點的概率積累值；P為挖礦難度。

區(qū)塊傳播時間定義如式（4）所示：

將式（4）變形得到：

其中：G(t)=，最終得出Pr(F≥1)≈P×ns×D。結(jié)果表明出塊概率與區(qū)塊傳播時間成正相關(guān)。

在DPoS 共識算法中，委托人節(jié)點之間的傳播主要是與后面一個節(jié)點通信，因此節(jié)點之間依靠通信代價最小的連接是提高性能的一種方式。

本文設(shè)置節(jié)點網(wǎng)絡(luò)信息表用于保存每個節(jié)點與自己一定距離范圍內(nèi)（通信代價）其他節(jié)點的連接信息。為防止節(jié)點選舉發(fā)生網(wǎng)絡(luò)風(fēng)暴，進而導(dǎo)致無法選取出委托人節(jié)點，設(shè)定每個節(jié)點與其他節(jié)點連接數(shù)為k，k≥n-1，其中k為固定值，n為選取的委托人節(jié)點總數(shù)。在節(jié)點加入網(wǎng)絡(luò)時，向其他節(jié)點進行通信，當(dāng)節(jié)點N1每收到一個返回消息時，發(fā)送者N2的IP 地址就被用來更新對應(yīng)的網(wǎng)絡(luò)信息表。如果N2的IP 地址沒有記錄在該信息表中，則N1節(jié)點的記錄項小于k個，記錄N2至自身信息表中；如果節(jié)點N1的記錄項大于k個，則對該節(jié)點信息表中的節(jié)點進行檢測操作。出現(xiàn)節(jié)點沒有響應(yīng)，從表中刪除無響應(yīng)的節(jié)點，并插入N2節(jié)點。如果所有節(jié)點都有響應(yīng)，則忽略N2。網(wǎng)絡(luò)信息表的建立具體流程如算法1～算法3 所示。

3 實驗結(jié)果與分析

為測試模型的有效性，仿真實驗設(shè)備配置為AMD Ryzen 5 3550H 處理器，16 GB 運行內(nèi)存，Windows10 操作系統(tǒng)，采用Docker 容器技術(shù)，運用編程語言通過多端口模擬多節(jié)點來實現(xiàn)節(jié)點的投票行為。共識協(xié)議假定節(jié)點之間是誠信可靠的，并且網(wǎng)絡(luò)與最終交付確保是異步通信的，每個節(jié)點能通過可靠的通信鏈路連接。

3.1 CE-DPoS 投票結(jié)果

本文設(shè)定從11 個節(jié)點中選擇4 個節(jié)點作為委托人節(jié)點，此外，各節(jié)點相互之間能夠?qū)ζ渌?jié)點進行權(quán)重為0～5 的對等投票，其中0 表示未進行投票打分，圖3 展示了11 個節(jié)點相互投票的結(jié)果。

圖3 11 個節(jié)點互相投票結(jié)果Fig.3 Result of 11 nodes voting with each other

表3 所示為對圖3 結(jié)果的分析，將各個節(jié)點得分進行統(tǒng)計，計算出票權(quán)數(shù)總和Total 值，但會出現(xiàn)多個Total 值相等的情況，并不滿足實際的投票意愿，因此使用式（1）計算它們的偏差度，得出最終的分數(shù)V#。

表3 節(jié)點得分票權(quán)占比和最終分值Table 3 Proportion of node’s scoring votes and final score

圖4 為本文預(yù)先設(shè)定的節(jié)點之間路由表的連接，連接數(shù)k設(shè)定為3（單向箭頭指向代表該節(jié)點網(wǎng)絡(luò)信息表中包含箭頭指向的節(jié)點），各個節(jié)點通過與其他節(jié)點的交互行為形成各自的網(wǎng)絡(luò)信息表，最終所有的節(jié)點共同維護全局網(wǎng)絡(luò)信息表，矩陣R表示路由連接信息，1 表示連接，0 表示未連接。

圖4 節(jié)點網(wǎng)絡(luò)信息表連接情況Fig.4 Connection status of node network information table

通過圖4 中各個節(jié)點之間的關(guān)系，采用局部最優(yōu)的思想，最終選取的委托人節(jié)點如表4 所示。

表4 委托人節(jié)點選取的最終結(jié)果Table 4 Final result selected by delegate node

3.2 CE-DPoS 動態(tài)選舉節(jié)點百分占比

本文模型中委托人節(jié)點的選取是動態(tài)的，并且兼顧了各節(jié)點的票數(shù)，選出的節(jié)點既滿足通信量小且得分較高。在一輪共識結(jié)束后，計算選出的4 個節(jié)點的分數(shù)平均值，從剩下的7 個節(jié)點中隨機選取另外4 個節(jié)點并計算出平均值。最終分別計算出與一輪共識中最高分的比值，如式（5）所示：

重復(fù)共識選舉20 次，實驗結(jié)果如圖5 所示。由圖5 可知，pa和pβ值呈現(xiàn)相似的波動。隨著共識次數(shù)從0～20 的增長，使用CE-DPoS 共識算法選舉模型比隨機選取算法在滿足現(xiàn)實情況投票方面的優(yōu)勢更加突出。當(dāng)共識次數(shù)增加到15 次時，CE-DPoS 共識的委托人選舉百分占比為97.23%，而同等條件下隨機選取委托人百分占比僅有91.05%。

圖5 選舉委托人節(jié)點分數(shù)占比1Fig.5 Election delegate node score percentage 1

增加共識次數(shù)至100 次，結(jié)果如圖6 所示，隨著共識次數(shù)的增加，CE-DPoS 共識算法選取委托人百分占比整體波動相對穩(wěn)定，而隨機選取波動幅度較大。

圖6 選舉委托人節(jié)點分數(shù)占比2Fig.6 Election delegate node score percentage 2

3.3 CE-DPoS 出塊時間

傳統(tǒng)DPoS 共識算法在選出節(jié)點后，委托人節(jié)點之間的先后通信方式?jīng)]有明確的規(guī)定，采用隨機的見證人出塊順序，出塊速度大致為3 s 左右。BFT-DPoS 共識算法選取委托人后互相協(xié)商出一個出塊的順序，見證人出塊時進行全網(wǎng)廣播，其他見證人收到新區(qū)塊后，立即對此區(qū)塊進行驗證，不需等待其他見證人自己出塊時再確認。CE-DPoS 共識算法通過設(shè)定網(wǎng)絡(luò)信息表記錄節(jié)點之間通信代價，在信息表中依次選取委托人節(jié)點，降低了隨機選取委托人節(jié)點之間不必要的通信消耗。

實驗仿真3 種共識算法的出塊時間進行對比，結(jié)果如圖7 所示。隨著區(qū)塊個數(shù)從0～1 000 的增長，使用CE-DPoS 共識算法比DPoS、BFT-DPoS 共識算法在降低出塊時間方面的優(yōu)勢更加突出。當(dāng)區(qū)塊個數(shù)增加到1 000 個時，CE-DPoS 共識算法的出塊時間降至0.4 s，比同等條件下DPoS 共識算法節(jié)約了80%的時間，能更好地應(yīng)對日益增長的交易量。

圖7 出塊時間對比Fig.7 Block time comparison

3.4 CE-DPoS 節(jié)點活躍度

DPoS 共識算法由于存在去中心化程度低下、節(jié)點投票不積極等問題而被業(yè)界與學(xué)術(shù)界所詬病。本文實驗仿真3 種共識算法，計算節(jié)點投票占比并將其進行對比，結(jié)果如圖8 所示。隨著共識次數(shù)的不斷增加，使用CE-DPoS 共識算法比DPoS、BFT-DPoS共識算法在提升節(jié)點投票活躍度方面優(yōu)勢更加突出。由于DPoS 和BFT-DPoS 都采用股份的投票方式，股份較少的節(jié)點失去了投票的積極性，全局投票活躍度僅為34%左右，同程度的CE-DPoS 共識算法節(jié)點活躍度提升至85%。

圖8 節(jié)點活躍度對比Fig.8 Node activity comparison

4 結(jié)束語

DPoS 共識算法作為主流公有鏈共識算法，存在選擇委托人節(jié)點單一固定、委托人節(jié)點之間出塊順序采用隨機方式以及通信消耗成本較高的問題。本文提出一種意愿評分的模型方案，該方案節(jié)點相互評分，計算出每個節(jié)點的綜合分值，然后通過排序選取出當(dāng)前分數(shù)最高的節(jié)點，再按照網(wǎng)絡(luò)信息表的連接情況依次選擇出后續(xù)的委托人節(jié)點。實驗結(jié)果表明，本文方案選擇的委托人節(jié)點之間的出塊順序與節(jié)點之間的通信密切相關(guān)，能夠加快節(jié)點的出塊時間，滿足日益增大的交易量，并提升節(jié)點的投票活躍度。后續(xù)工作將進一步優(yōu)化CE-DPoS 投票模型的時間復(fù)雜度，并應(yīng)用到實際場景中。