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

王 兵，李輝靈，牛新征

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

0 概述

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

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

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

1 DPoS 共識算法相關研究

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

圖1 區塊鏈結構Fig.1 Structure of blockchain

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

2 CE-DPoS 共識算法方案

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

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

在公有鏈網絡中，節點參與活躍度與網絡的安全性息息相關，在經典DPoS 共識算法中，節點投票有失公平性，節點出現投票政治冷漠性。為極大程度地滿足節點的投票意愿傾向和公平性，對投票意愿設置等級。CE-DPoS 投票模型中的符號說明如表1 所示。

表1 符號說明Table 1 Symbol description

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

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

表2 列舉了3 個節點的得票情況，節點之間對其他節點進行權重投票。

表2 節點得票數Table 2 Number of votes by the node

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

不失一般性，設當前有11 個節點參與投票，則對于11 個候選節點出現的得票權可能性p如式（2）所示：

其中：mi表示票權為i的票數總和。

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

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

2.2 CE-DPoS 委托人節點選取

在網絡信息表的基礎上，選定所有節點中分數排名最高的節點A，從節點A網絡信息表中選出除節點A外分數排名最高的節點B，再從節點B網絡信息表中選出除B外分數排名最高的節點C，直至選定n個委托人節點，整體過程如圖2 所示。

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

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

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

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

將式（4）變形得到：

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

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

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

3 實驗結果與分析

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

3.1 CE-DPoS 投票結果

本文設定從11 個節點中選擇4 個節點作為委托人節點，此外，各節點相互之間能夠對其他節點進行權重為0～5 的對等投票，其中0 表示未進行投票打分，圖3 展示了11 個節點相互投票的結果。

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

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

表3 節點得分票權占比和最終分值Table 3 Proportion of node’s scoring votes and final score

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

圖4 節點網絡信息表連接情況Fig.4 Connection status of node network information table

通過圖4 中各個節點之間的關系，采用局部最優的思想，最終選取的委托人節點如表4 所示。

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

3.2 CE-DPoS 動態選舉節點百分占比

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

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

圖5 選舉委托人節點分數占比1Fig.5 Election delegate node score percentage 1

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

圖6 選舉委托人節點分數占比2Fig.6 Election delegate node score percentage 2

3.3 CE-DPoS 出塊時間

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

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

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

3.4 CE-DPoS 節點活躍度

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

圖8 節點活躍度對比Fig.8 Node activity comparison

4 結束語

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