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

白 兵，李志淮，李 敏

大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116002

區(qū)塊鏈技術(shù)在中本聰?shù)恼撐腫1]中首次提出。在技術(shù)層面，區(qū)塊鏈?zhǔn)且环N使用了P2P網(wǎng)絡(luò)、分布式存儲、密碼學(xué)等計算機(jī)技術(shù)，具有去中心化、去信任化、難篡改特點的分布式數(shù)字賬本。區(qū)塊鏈因其技術(shù)特點，其應(yīng)用已經(jīng)延伸到銀行、物流、金融等多個領(lǐng)域，對它們的數(shù)據(jù)存儲和共享產(chǎn)生重大的影響[2-3]。同時，在2019年10月24日的中央政治局第十八次集體學(xué)習(xí)會議上，習(xí)近平總書記強(qiáng)調(diào)，要大力發(fā)展區(qū)塊鏈關(guān)鍵技術(shù)，加快推動區(qū)塊鏈技術(shù)和產(chǎn)業(yè)創(chuàng)新發(fā)展。

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

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

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

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

根據(jù)上述文獻(xiàn)可知，現(xiàn)有的分片方案中缺少“跨分片交易中因某個分片失效導(dǎo)致分片內(nèi)交易無法驗證，進(jìn)而造成跨分片交易回滾”的概率分析，以及對這種原因?qū)е碌目绶制灰谆貪L的進(jìn)一步處理方案。故本文針對以上問題進(jìn)行分析，提出了一種多輪共識驗證的改進(jìn)方案，較傳統(tǒng)的單輪次驗證其貢獻(xiàn)如下：（1）該方案可以及時地為失效分片更換驗證節(jié)點，讓失效分片中的交易可以在下一輪驗證中再次處理，降低有效的跨分片交易回滾的概率，減少了回滾的交易重新提交產(chǎn)生更大的延遲現(xiàn)象的發(fā)生；（2）該方案通過連續(xù)的多輪驗證，可以在降低跨分片交易回滾的概率的基礎(chǔ)上，增大分片規(guī)模，進(jìn)一步提升系統(tǒng)的TPS；（3）通過實驗表明，多輪驗證方案的表現(xiàn)更優(yōu)。

1 問題描述與分析

1.1 問題描述

UTXO模型[1]由于具有良好的并發(fā)性，被應(yīng)用于很多區(qū)塊鏈網(wǎng)絡(luò)中。在UTXO模型中，交易可以具有多個輸入和輸出。交易驗證時，驗證者需要驗證每筆交易的輸入尚未花費，并且確保在這筆交易完成后該交易的所有輸入都已不可再花費。在基于UTXO模型的分片區(qū)塊鏈系統(tǒng)中，交易的多個輸入輸出可能涉及到多個節(jié)點地址，根據(jù)分片協(xié)議，節(jié)點和交易按規(guī)則劃分到不同的分片，這就導(dǎo)致一些交易需要在多個分片進(jìn)行驗證，也就是跨分片交易。

在跨分片交易中，一般設(shè)定管理輸入對象所在的分片稱為輸入分片（input shard，IS），管理輸出對象所在分片稱為輸出分片（output shard，OS）。由于一筆跨分片交易涉及多個分片，為保證分片間的全局一致性需要多個分片之間協(xié)調(diào)處理?？绶制灰滋幚頃r，客戶端將跨分片交易發(fā)送到涉及的輸入分片中，每個分片獨立地對該分片內(nèi)的交易進(jìn)行共識驗證處理，只有所有的輸入分片驗證成功后才會提交跨分片交易到一個或多個輸出分片，并在輸出分片中進(jìn)行再次驗證。當(dāng)任何一個輸入分片驗證交易失敗或超出時間限制時，為保證區(qū)塊鏈系統(tǒng)的一致性，需要對部分處理的跨分片交易進(jìn)行回滾操作?？绶制灰椎奶幚砹鞒倘鐖D1所示。

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

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

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

對于有效的跨分片交易，因某個分片內(nèi)拜占庭節(jié)點比例f>1/3，而無法對片內(nèi)交易達(dá)成共識驗證，導(dǎo)致的跨分片交易回滾嚴(yán)重影響系統(tǒng)的性能，并且后續(xù)用戶重新發(fā)送這筆交易到網(wǎng)絡(luò)中謀求再次驗證，將會產(chǎn)生更大的交易延遲。因此本文針對分片內(nèi)拜占庭節(jié)過多導(dǎo)致分片失效，造成的跨分片交易回滾問題進(jìn)行分析處理。

1.2 跨分片交易概率分析

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

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

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

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

1.3 跨分片交易回滾的概率

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

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

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

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

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

根據(jù)表2可知，在L不變時，跨分片交易回滾的概率隨著w的增大而增大；當(dāng)跨分片交易的輸入分片個數(shù)w不變時，回滾的概率隨著分片內(nèi)節(jié)點個數(shù)L的增大而減小。但即使在L=600時，跨分片交易回滾的概率依舊無法忽視。

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

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

通過以上的分析可以看出，分片后不僅會存在跨分片交易，且跨分片交易在網(wǎng)絡(luò)的所有交易中，占了很大的比例，因此跨片交易的正確處理對系統(tǒng)性能是至關(guān)重要的。處理跨分片交易時，即使僅存在一個輸入分片未完成驗證交易，都需要對其他已處理的跨分片交易進(jìn)行回滾。通過1.3節(jié)的模擬計算，對分片后拜占庭節(jié)點分布不均而使某些分片失效，進(jìn)而導(dǎo)致的跨分片交易回滾的概率進(jìn)行分析，發(fā)現(xiàn)跨分片交易的回滾概率很高，不可忽視?？绶制灰谆貪L將嚴(yán)重影響系統(tǒng)性能，為了保證系統(tǒng)的性能，應(yīng)盡量減小跨分片交易的回滾概率。故提出多輪共識的驗證方案，通過多輪驗證，可以提升跨分片交易的驗證率，從而保障系統(tǒng)總體的TPS。

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

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

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

2.2 多輪驗證方案輪數(shù)選擇

2.2.1拜占庭合謀攻擊的概率

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

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

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

根據(jù)表3可知，單個分片內(nèi)節(jié)點數(shù)量越多時，分片發(fā)生合謀攻擊的概率越低?？梢钥闯霎?dāng)f=0.333時，只要分片內(nèi)節(jié)點數(shù)L超過60時，合謀攻擊概率低于10-8，合謀概率足夠低，近似認(rèn)定分片內(nèi)節(jié)點達(dá)成的決定為集體誠實，不考慮合謀攻擊的發(fā)生。

2.2.2 多輪輪數(shù)對回滾概率的影響

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

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

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

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

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

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

2.2.3 多輪輪數(shù)的上限

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

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

當(dāng)一筆交易連續(xù)經(jīng)過Tmax輪共識驗證后，仍無法對同一筆交易達(dá)成共識，則放棄該筆交易，保全系統(tǒng)的總體性能。

2.3 節(jié)點隨機(jī)分配算法

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

VRF包含3個函數(shù)：VRFG、VRFF、VRFV。

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

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

（3）VRFV：驗證函數(shù)，調(diào)用節(jié)點根據(jù)廣播的輸入x和零知識證明proof，結(jié)合生成隨機(jī)數(shù)的公鑰Pk，對隨機(jī)數(shù)value進(jìn)行驗證，驗證通過則表明隨機(jī)數(shù)有效，反之則無效。

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

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

其中，h為第h個區(qū)塊，Bh-1為當(dāng)前區(qū)塊高度的上一個區(qū)塊的哈希值，{Nk}為每個參與節(jié)點與網(wǎng)絡(luò)中的相鄰節(jié)點互換一個數(shù)字所獲得的數(shù)字集合，可以得出x每一輪都將做出改變，具有很好的不可預(yù)測性。

3 實驗設(shè)置及結(jié)果分析

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

3.1 實驗環(huán)境及參數(shù)設(shè)置

本實驗以實驗室局域網(wǎng)搭建的P2P測試網(wǎng)絡(luò)作為實驗所需的網(wǎng)絡(luò)環(huán)境，通過實驗室10臺服務(wù)器構(gòu)建10個分片，用不同服務(wù)器的不同端口號模擬創(chuàng)建不同的共識節(jié)點，以普通PC機(jī)模擬網(wǎng)絡(luò)中發(fā)起交易請求的客戶端，其中具體硬件環(huán)境和軟件環(huán)境如下。

（1）硬件環(huán)境

局域網(wǎng)內(nèi)8臺服務(wù)器：CPU i5四核，RAM 16 GB，Disk 500 GB；另2臺服務(wù)器：CPU i5八核，RAM 16 GB，Disk 1 TB。

（2）軟件環(huán)境

操作系統(tǒng)：Linux，開發(fā)環(huán)境：Goland。

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

（1）節(jié)點的屬性是可變的，即在本輪誠實的節(jié)點，下一輪可變?yōu)榘菡纪ス?jié)點。

（2）設(shè)定總節(jié)點數(shù)目N=600,分片內(nèi)節(jié)點數(shù)L=60,節(jié)點可以動態(tài)加入或退出，分片期間節(jié)點數(shù)量保持不變。

3.2 實驗設(shè)計和結(jié)果分析

3.2.1 交易驗證率測試

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

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

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

3.2.2 交易吞吐量測試

交易吞吐量含義為系統(tǒng)服務(wù)器在單位時間內(nèi)處理事務(wù)的數(shù)量，一般表示為TPS（transaction per second，每秒的交易數(shù)），如公式（7）所示：

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

圖5 兩種方案的TPS表現(xiàn)情況Fig.5 TPS performance of two solutions

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

兩實驗綜合表明，減小分片內(nèi)節(jié)點數(shù)，增大分片規(guī)模的多輪共識的驗證方案，較分片內(nèi)節(jié)點數(shù)較多，分片數(shù)量較小的單輪次驗證方案相比，有效地降低了跨分片交易回滾的概率，提升了交易的驗證率，提升了系統(tǒng)總體的TPS。

4 總結(jié)

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

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