降低跨分片交易回滾概率的多輪驗證方案

白 兵，李志淮，李 敏

大連海事大學 信息科學技術學院，遼寧 大連 116002

區塊鏈技術在中本聰的論文[1]中首次提出。在技術層面，區塊鏈是一種使用了P2P網絡、分布式存儲、密碼學等計算機技術，具有去中心化、去信任化、難篡改特點的分布式數字賬本。區塊鏈因其技術特點，其應用已經延伸到銀行、物流、金融等多個領域，對它們的數據存儲和共享產生重大的影響[2-3]。同時，在2019年10月24日的中央政治局第十八次集體學習會議上，習近平總書記強調，要大力發展區塊鏈關鍵技術，加快推動區塊鏈技術和產業創新發展。

區塊鏈的技術特點使其有著廣闊的應用前景，但也同時面臨可擴展性不足的瓶頸，存在擴容需求[4-5]。現有的擴容技術主要包括分片方案[6]、DAG[7]、擴塊[8-9]、側鏈技術[10]、狀態通道[11]等。其中分片方案是目前擴容方案中最具可行性的方案，受到廣大學者和社區人員的關注和重視。區塊鏈分片的核心思想是將區塊鏈網絡節點劃分為若干個集合，每個集合獨立運行共識協議，對交易進行共識驗證，并且每個集合可以并行地處理不同的交易集合甚至只存儲部分網絡狀態，從而達到提高交易吞吐量的效果。

分片技術雖然可以提升區塊鏈系統的性能，但同時也帶來了新的挑戰。分片后網絡中必然存在跨分片交易，而跨分片交易的正確處理對系統的性能至關重要。在UTXO（unspent transaction outputs，未花費的交易輸出）模型下，處理跨分片交易時，客戶端將跨分片交易發送到涉及的輸入分片中獨立地驗證處理，當全部輸入分片成功驗證跨分片交易后，會提交給輸出分片進行驗證處理。出現任一個輸入分片驗證交易失敗或超時后，為保證區塊鏈網絡數據的一致性和完整性，需要對部分處理的跨分片交易進行回滾操作。

跨分片交易回滾的原因如下：（1）交易是無效的，部分輸入分片驗證無誤且提交，而某輸入分片驗證交易失效，拒絕這筆交易，跨分片交易必須回滾以此釋放其他分片已鎖定的資源，保證后續交易對該對象的正常使用；（2）對于大多數分片項目采用的PBFT[12-14]類共識算法的分片方案中，存在總拜占庭節點比例不超過1/3，分片后單個分片拜占庭節點比例大于1/3的情況，使分片驗證有效性受到威脅[15]，分配到某分片的跨分片交易遲遲無法達成共識，致使跨分片交易進行回滾。

針對因分片失效導致跨分片交易回滾的問題，文獻[16]通過采用Rand Hound節點隨機分配算法降低分片內拜占庭節點聚集的概率，提高分片的驗證有效性，可以在一定程度上保證跨分片交易的正確處理。文獻[17]通過將節點的通訊方式設為同步，以此來增加單個分片對拜占庭節點的容忍度，提高分片的驗證有效性，從而減少跨分片交易回滾的發生，但同步的通訊方式應用具有局限性。文獻[18]通過智能合約進行分片，使用了假設分片內安全的“SMART’s PBFT”協議來保證跨分片交易的處理。文獻[19]提出了連弩挖礦的激勵方案，在提高礦工收益的經濟模型下，確保分片的有效性，可以一定程度上減少跨分片交易回滾的發生。

根據上述文獻可知，現有的分片方案中缺少“跨分片交易中因某個分片失效導致分片內交易無法驗證，進而造成跨分片交易回滾”的概率分析，以及對這種原因導致的跨分片交易回滾的進一步處理方案。故本文針對以上問題進行分析，提出了一種多輪共識驗證的改進方案，較傳統的單輪次驗證其貢獻如下：（1）該方案可以及時地為失效分片更換驗證節點，讓失效分片中的交易可以在下一輪驗證中再次處理，降低有效的跨分片交易回滾的概率，減少了回滾的交易重新提交產生更大的延遲現象的發生；（2）該方案通過連續的多輪驗證，可以在降低跨分片交易回滾的概率的基礎上，增大分片規模，進一步提升系統的TPS；（3）通過實驗表明，多輪驗證方案的表現更優。

1 問題描述與分析

1.1 問題描述

UTXO模型[1]由于具有良好的并發性，被應用于很多區塊鏈網絡中。在UTXO模型中，交易可以具有多個輸入和輸出。交易驗證時，驗證者需要驗證每筆交易的輸入尚未花費，并且確保在這筆交易完成后該交易的所有輸入都已不可再花費。在基于UTXO模型的分片區塊鏈系統中，交易的多個輸入輸出可能涉及到多個節點地址，根據分片協議，節點和交易按規則劃分到不同的分片，這就導致一些交易需要在多個分片進行驗證，也就是跨分片交易。

在跨分片交易中，一般設定管理輸入對象所在的分片稱為輸入分片（input shard，IS），管理輸出對象所在分片稱為輸出分片（output shard，OS）。由于一筆跨分片交易涉及多個分片，為保證分片間的全局一致性需要多個分片之間協調處理。跨分片交易處理時，客戶端將跨分片交易發送到涉及的輸入分片中，每個分片獨立地對該分片內的交易進行共識驗證處理，只有所有的輸入分片驗證成功后才會提交跨分片交易到一個或多個輸出分片，并在輸出分片中進行再次驗證。當任何一個輸入分片驗證交易失敗或超出時間限制時，為保證區塊鏈系統的一致性，需要對部分處理的跨分片交易進行回滾操作。跨分片交易的處理流程如圖1所示。

圖1 跨分片交易的處理Fig.1 Processing of cross-shard transactions

采用PBFT類共識算法的分片方案可以保證數據的最終一致性，但在這類分片方案中，分片中存在由于拜占庭節點分配不均，導致分片驗證有效性遭到破壞的問題，從而影響某個分片內交易的處理。一旦某個分片失效則導致涉及該分片內的跨分片交易無法得到驗證，那么跨分片交易涉及的其他分片提交的跨分片事務就需要開始回滾操作，而回滾對于性能的負面影響是巨大的。設總節點個數為N，總體拜占庭比例為f<1/3，設將N個節點隨機均勻地分到k個分片中，分片內節點數為L，分片后可能會存在單個分片拜占庭比例fi>1/3(1≤i≤k)致分片失效，如圖2所示。

圖2 拜占庭節點分配不均致分片失效Fig.2 Uneven distribution of Byzantine nodes making shards invalid

對于有效的跨分片交易，因某個分片內拜占庭節點比例f>1/3，而無法對片內交易達成共識驗證，導致的跨分片交易回滾嚴重影響系統的性能，并且后續用戶重新發送這筆交易到網絡中謀求再次驗證，將會產生更大的交易延遲。因此本文針對分片內拜占庭節過多導致分片失效，造成的跨分片交易回滾問題進行分析處理。

1.2 跨分片交易概率分析

在區塊鏈UTXO模型的分片系統，交易的多個輸入可能涉及到多個節點地址，節點會按照分片協議中的隨機分配算法，隨機分配到各個分片中。設分片規模為k，交易的輸入數量為m，根據分片的隨機分配算法，每個輸入節點都等概率地隨機分配到k個分片中。則在UTXO模型下的分片系統中，具有m個輸入的交易，為跨分片交易的概率P(cross-shard)如公式（1）所示：

根據公式（1），模擬研究交易的輸入個數m對跨分片交易概率P()cross-shard的影響情況。如表1所示。

表1 對跨分片交易概率P（cross-shard）的影響Table 1 Impact of m on probability P（cross-shard）

由表1可知，一筆多個輸入的交易為跨分片交易的概率隨著分片規模k和輸入個數m的增大而增大。當分片規模k為16時，具有多個輸入的交易為跨分片交易的概率已超過93%；若k、m繼續增大，跨分片交易的概率將無限接近于1。綜上所述，在分片系統中，處理具有多個輸入的交易時，出現跨分片交易的概率很大。故保證涉及多個輸入的跨分片交易的正確處理、減小跨分片交易發生回滾的概率對區塊鏈系統的性能至關重要。

1.3 跨分片交易回滾的概率

設分片規模為k，在UTXO模型中，一筆交易包含的輸入個數m是有可能大于分片個數k的，那么含有m個輸入的交易Tx的跨片分布w，取值在1到min(m,k)個分片。為專注于跨片交易回滾的分析比較，一筆含有m個輸入的交易Tx在分片系統中，跨分片交易回滾的概率歸約為與跨片分布w和分片的驗證有效性相關。設分片規模為k，單個分片驗證失效的概率用Ps表示，m個輸入分布在w個分片的交易Tx，它的回滾概率用P(rollback)表示，如公式（2）所示：

在文獻[16]中，Omniledger方案對分片的有效性進行了具體的分析。其中，Xi表示第i個節點表現出了拜占庭屬性，X表示單個分片中拜占庭節點的數量，L表示為分片內節點數，f為總體拜占庭節點比例。X符合Binomial(L,f,X)的二項分布，X≥1/3時，分片失效。分片失效概率Ps如公式（3）所示：

故P(rollback)可以展開如公式（4）所示：

在許多分片項目中設定總體拜占庭比例f=0.25[6，16-18]，被認為是一個合理的取值。故設定f=0.25時，計算不同w對跨分片交易回滾概率的影響，如表2所示。

表2 輸入分片個數w對回滾概率P（rollback）的影響Table 2 Influence of w on P（rollback）

根據表2可知，在L不變時，跨分片交易回滾的概率隨著w的增大而增大；當跨分片交易的輸入分片個數w不變時，回滾的概率隨著分片內節點個數L的增大而減小。但即使在L=600時，跨分片交易回滾的概率依舊無法忽視。

由表2可知，通過增大L可以使同樣一筆跨分片交易回滾概率減小，但分片技術的目的是通過擴大分片規模提升吞吐量，分片內節點數過多不利于分片規模的擴大，從而達不到分片的最終目的。故本文提出了多輪驗證的共識算法，可以在降低跨分片交易回滾的概率的基礎上，擴大分片規模，提升系統的總體性能。

2 多輪共識處理跨片交易驗證方案

通過以上的分析可以看出，分片后不僅會存在跨分片交易，且跨分片交易在網絡的所有交易中，占了很大的比例，因此跨片交易的正確處理對系統性能是至關重要的。處理跨分片交易時，即使僅存在一個輸入分片未完成驗證交易，都需要對其他已處理的跨分片交易進行回滾。通過1.3節的模擬計算，對分片后拜占庭節點分布不均而使某些分片失效，進而導致的跨分片交易回滾的概率進行分析，發現跨分片交易的回滾概率很高，不可忽視。跨分片交易回滾將嚴重影響系統性能，為了保證系統的性能，應盡量減小跨分片交易的回滾概率。故提出多輪共識的驗證方案，通過多輪驗證，可以提升跨分片交易的驗證率，從而保障系統總體的TPS。

2.1 多輪驗證方案處理交易的流程

多輪共識的驗證方案驗證跨分片交易中心思想為當跨分片交易被發送到多個輸入分片，由各分片獨立地進行驗證處理，驗證成功則打包出塊。若出現交易在分片內因拜占節點過多使交易驗證超時，則重新分配節點到該分片，再次對該筆交易進行共識驗證，使其在有限的輪數內可以驗證成功，盡量避免跨分片交易因單個輸入分片失效而無法完成有效驗證。這減少了跨分片交易回滾情況的發生，也可避免重新發送已回滾的交易產生更大的延遲。

交易驗證的具體過程為：（1）將交易根據映射規則分配到既定分片，并初始化交易的輪次；（2）由分片內的全部節點對分配到該分片全部交易進行共識驗證，驗證成功則將該組交易打包交易到區塊；（3）若分片驗證超時后還未得到有效共識，則通過隨機分配算法重新分配一組節點到失效分片中（此時其他分片正常運行），對上一輪驗證超時的那組交易進行新一輪共識驗證；（4）若連續T輪過后仍未達成有效共識，則選擇放棄該筆交易。通過有限犧牲交易的可用性，保全系統的總體性能；本文設定放棄一筆交易的概率為β<10-8。多輪共識驗證的具體流程如圖3所示。

2.2 多輪驗證方案輪數選擇

2.2.1拜占庭合謀攻擊的概率

即使總體拜占庭節點比例小于1/3，節點在隨機分配到各個分片后，也會存在分片內拜占庭節點占據大多數且相互串通的情況。串通作惡的節點目的是進行合謀攻擊，讓分片內達成一致且錯誤的共識。若在分片內達成合謀，聯合作惡拜占庭節點在分片中占比需要大于2/3，但這具有較大的復雜性。假設只要分片內拜占庭節點大于(2L)/3+1，拜占庭節點就會互相串通達成合謀攻擊。在文獻[6]中，提出了Elastico方案并對分片的合謀概率進行了分析。其中令，Xi表示第i個節點表現出了拜占庭屬性，X表示單個分片中拜占庭節點數量，其中L為分片內節點數，f表示拜占庭節點總數所占比例。X符合Binomial(L,f,X)的二項分布，分片內合謀攻擊發生的概率如公式（5）所示：

根據公式（5）模擬計算了不同L以及不同f下的合謀概率，如表3所示。

表3 節點數L及拜占庭比例f對合謀概率P的影響Table 3 Impact of L and f on probability P

根據表3可知，單個分片內節點數量越多時，分片發生合謀攻擊的概率越低。可以看出當f=0.333時，只要分片內節點數L超過60時，合謀攻擊概率低于10-8，合謀概率足夠低，近似認定分片內節點達成的決定為集體誠實，不考慮合謀攻擊的發生。

2.2.2 多輪輪數對回滾概率的影響

根據表3，在L不小于60時，合謀攻擊概率足夠小，可以假定分片內節點達成的決定為集體誠實。故表4分析了在分片節點數L=60時，跨分片交易在不同的輪數T和不同的輸入分片個數w下的回滾概率。

表4 輪數T對跨分片交易回滾概率P（rollback）的影響Table 4 Impact of rounds T on P（rollback）

由表4可以看出，使用多輪共識的驗證方案與傳統的單輪次驗證方案（第一輪的回滾的概率）相比，跨分片交易的回滾的概率大幅度降低。隨著輪數T的增大，跨分片交易回滾的概率將越來越低，逐漸降低至一個相當微小的數值。雖然跨分片交易回滾的概率隨著w的增大而增大，但使用多輪的驗證方案僅當T=2,w=16時，比傳統單輪驗證方案w=2時的跨分片交易回滾概率還小很多。由此證明，使用了多輪共識的驗證方案處理跨分片交易對減少跨分片交易回滾的概率效果顯著，也利于實現更大規模的分片。

輸入分片個數w=4，據統計是跨分片交易中占比最大的數值。表5分析了在輸入分片個數w=4，在分片內節點數L不斷增長的情況下，使用了多輪驗證方案和未使用多輪驗證方案，跨分片交易回滾概率的差別。

由表5看出，隨著分片內節點數增加，兩種方案跨分片交易回滾的概率都大幅降低，但使用多輪的驗證方案在節點數較小時依然比單輪次多節點的跨分片交易回滾概率低許多；且分片內節點數減小，分片規模增大，此時分片規模已增加至M(M>>k)；而達到與分片內節點較大時相同的回滾概率，所需的輪數T(T<

表5 輪數T對跨分片交易回滾概率P（rollback）的影響Table 5 Impact of rounds T on P（rollback）

2.2.3 多輪輪數的上限

為限定延遲上限，防止對一筆交易無限循環共識影響系統的總體性能，對輪數的上限進行設定。輪數T的上限即共識的最多輪數，取值為跨分片交易回滾概率小于10-8時的輪數。根據表4，當分片節點數和拜占庭比例固定時，w的增大對使交易的回滾概率小于10-8的輪數幾乎沒有影響。故表6分析計算了在輸入分片個數w=4時（可以粗略代表不同的輸入分片個數w），在不同的分片內節點個數L和拜占庭節點比例f下，跨分片交易回滾的概率小于10-8時的輪數上限Tmax。

表6 輪數上限Tmax在不同L和f下的取值Table 6 Value of upper limit of Tmax under different L and f

當一筆交易連續經過Tmax輪共識驗證后，仍無法對同一筆交易達成共識，則放棄該筆交易，保全系統的總體性能。

2.3 節點隨機分配算法

當分片拜占庭節點過多致分片失效驗證超時時，需通過節點隨機分配算法重新為失效分片重新分配一組節點，該算法需保證節點分配時較高的隨機性和不可預測性的特點，VRF（verifiable random function，可驗證隨機函數）[20]具有上述特點，因此本方案選用VRF函數作為節點隨機分配算法的隨機函數。

VRF包含3個函數：VRFG、VRFF、VRFV。

（1）VRFG：公私鑰生成函數，根據橢圓曲線函數隨機生成一對非對稱加密的密鑰，即一對公私鑰(Pk,Sk)。

（2）VRFF：隨機數和證明生成函數，根據輸入（Sk和一個輸入x），輸出兩個字符串，隨機數value=F1(Sk,x)和零知識證明函數proof=F2(Sk,x)，其中對于任何輸入x，不同的調用節點生成的value值確定且唯一。

（3）VRFV：驗證函數，調用節點根據廣播的輸入x和零知識證明proof，結合生成隨機數的公鑰Pk，對隨機數value進行驗證，驗證通過則表明隨機數有效，反之則無效。

在需要重新分配節點時，根據驗證有效的且唯一的隨機數value，通過哈希函數將value映射為固定長度的輸出，讓驗證節點根據結果進入相應的分片中。

VRF中的輸入x為生成隨機數的種子參數，為函數的不可預測性提供了保障。x需具有公開、隨機且不斷更新的特點。據此，對VRF輸入x進行設置，如公式（6）所示：

其中，h為第h個區塊，Bh-1為當前區塊高度的上一個區塊的哈希值，{Nk}為每個參與節點與網絡中的相鄰節點互換一個數字所獲得的數字集合，可以得出x每一輪都將做出改變，具有很好的不可預測性。

3 實驗設置及結果分析

現有的采用PBFT類共識跨分片方案，都存在分片的驗證有效性對跨分片交易的回滾產生影響的現象。為驗證本文方案確實可以降低跨分片交易回滾的概率，且多輪驗證犧牲的延遲不會降低系統總體的交易吞吐量TPS，分別選用分片方案中效果較好的方案，以文獻[12]提出的支持跨分片交易且分片內采用了PBFT類共識算法（即ByzCoinX）的Omniledger分片方案為基礎，增加了多輪共識的驗證方案，與Omniledger分片方案進行對比實驗，對比兩種方案的交易驗證率、吞吐量，在使用多輪驗證后的差異。

3.1 實驗環境及參數設置

本實驗以實驗室局域網搭建的P2P測試網絡作為實驗所需的網絡環境，通過實驗室10臺服務器構建10個分片，用不同服務器的不同端口號模擬創建不同的共識節點，以普通PC機模擬網絡中發起交易請求的客戶端，其中具體硬件環境和軟件環境如下。

（1）硬件環境

局域網內8臺服務器：CPU i5四核，RAM 16 GB，Disk 500 GB；另2臺服務器：CPU i5八核，RAM 16 GB，Disk 1 TB。

（2）軟件環境

操作系統：Linux，開發環境：Goland。

在2.2.1小節的計算中，當分片內節點數L超過60時，合謀攻擊的概率低于3.2×10-8，故實驗中設定L為60。對有著較優跨分片交易處理能力的Omniledger方案和使用多輪驗證的方案進行實驗對比，觀察它們在交易驗證率、吞吐量的差異，實驗數據用MATLAB進行繪制。在本文的設計方案中，實驗前需要對一些參數條件進行設定，如下：

（1）節點的屬性是可變的，即在本輪誠實的節點，下一輪可變為拜占庭節點。

（2）設定總節點數目N=600,分片內節點數L=60,節點可以動態加入或退出，分片期間節點數量保持不變。

3.2 實驗設計和結果分析

3.2.1 交易驗證率測試

設定總節點個數N=600，分片內節點數L=60的區塊鏈網絡下，驗證在兩種方案下的交易驗證率，向兩種方案分別投放相同50 000筆交易，設定每筆交易的輸入分片數量w分別為1、2、4、6、8幾種情況，觀察兩種方案的跨分片交易驗證率變化。如圖4所示。

圖4 交易驗證率Fig.4 Transaction verification rate

根據圖4可以看出，兩種方案的交易的驗證率隨著交易涉及的輸入分片數量的增加而減少。使用了多輪共識的驗證的方案，交易的驗證率明顯比單輪的Omniledger方案的驗證率高，這是因為使用多輪的驗證方案可以通過有限的延遲避免因分片失效導致的跨分片交易回滾的問題，可以讓某個失效分片的跨分片交易在下一輪繼續驗證，不用回滾交易并等待重新提交。而Omniledger方案若出現單個分片失效，則分片內交易無法在有限的時間得到及時的驗證處理，跨分片交易需要進行回滾，降低了交易驗證率。本實驗可以表明，多輪共識的驗證方案可以增加交易驗證率即降低交易回滾概率。

3.2.2 交易吞吐量測試

交易吞吐量含義為系統服務器在單位時間內處理事務的數量，一般表示為TPS（transaction per second，每秒的交易數），如公式（7）所示：

公式（7）中Δt表示為交易發送到網絡后直到交易上鏈的時間間隔，SumTransactionΔt表示在該時間間隔中打包進區塊上鏈的交易總數。設定總節點個數N=600，分片內節點數L=60的區塊鏈網絡下，驗證在兩種方案下的交易吞吐量，在系統分別運行5，10，30，60，120，300 min對交易處理情況進行統計，計算該時間段的平均TPS。觀察兩種方案隨著時間的變化，TPS的變化情況，根據公式（7）計算平均TPS，如圖5所示。

圖5 兩種方案的TPS表現情況Fig.5 TPS performance of two solutions

在實驗2可以看出，采用了多輪共識的驗證方案的TPS略高于原始單輪的Omniledger方案。系統在運行時，拜占庭節點會聯合作惡，影響單個分片的交易驗證有效性，加入多輪的方案可以快速恢復，重新分配節點在下一輪繼續對交易謀求驗證，故TPS表現略優。而單輪驗證交易的Omniledger方案，失效分片無法在短時內快速恢復，跨分片交易發生了回滾，影響了跨分片交易的有效驗證，所以平均TPS較低。多輪共識的驗證方案在系統運行過程中，對失效的分片重新分配節點，會產生短暫的延遲，可能會略微降低交易的吞吐量，但增大了分片規模的同時也能提高交易驗證率，使總體性能還是略高于未使用多輪的方案，達到了提升系統交易吞吐量的效果。

兩實驗綜合表明，減小分片內節點數，增大分片規模的多輪共識的驗證方案，較分片內節點數較多，分片數量較小的單輪次驗證方案相比，有效地降低了跨分片交易回滾的概率，提升了交易的驗證率，提升了系統總體的TPS。

4 總結

針對采用PBFT類共識算法的分片方案，因分片后拜占庭節點分配不均致分片失效所導致跨分片交易回滾的問題，提出了一種對交易進行多輪共識驗證的方案。選取分片方案中綜合效果最好，應用范圍最為廣泛的Omniledger方案進行模擬對比實驗，通過對交易驗證率、交易吞吐量的實驗結果進行分析，比較兩種方案的區別。實驗表明，采用了多輪驗證的分片方案可以在支持更大分片規模的同時，提高交易的驗證率，降低跨分片交易的回滾概率和重新提交的概率。這保證了數據一致性的同時，并提升了分片系統總體的TPS。

分片技術是解決擴容難題的方案中最具前景的方案，而跨分片交易的有效處理是保證分片系統性能的重要前提。因此，本文對許多區塊鏈分片項目降低跨片交易的回滾概率的研究都具有一定的參考價值。本方案還有需要改進之處，進一步考慮分片間負載均衡的問題，動態調整分片間性能差異，避免出現單個分片單點過熱問題，繼續增強系統的性能。