白 兵，李志淮，李 敏

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

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

區(qū)塊鏈的技術(shù)特點(diǎn)使其有著廣闊的應(yīng)用前景，但也同時(shí)面臨可擴(kuò)展性不足的瓶頸，存在擴(kuò)容需求[4-5]。現(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é)點(diǎn)劃分為若干個(gè)集合，每個(gè)集合獨(dú)立運(yùn)行共識(shí)協(xié)議，對(duì)交易進(jìn)行共識(shí)驗(yàn)證，并且每個(gè)集合可以并行地處理不同的交易集合甚至只存儲(chǔ)部分網(wǎng)絡(luò)狀態(tài)，從而達(dá)到提高交易吞吐量的效果。

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

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

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

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

1 問(wèn)題描述與分析

1.1 問(wèn)題描述

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

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

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

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

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

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

1.2 跨分片交易概率分析

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

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

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

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

1.3 跨分片交易回滾的概率

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

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

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

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

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

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

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

2 多輪共識(shí)處理跨片交易驗(yàn)證方案

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

2.1 多輪驗(yàn)證方案處理交易的流程

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

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

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

2.2.1拜占庭合謀攻擊的概率

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

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

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

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

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

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

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

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

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

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

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

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

為限定延遲上限，防止對(duì)一筆交易無(wú)限循環(huán)共識(shí)影響系統(tǒng)的總體性能，對(duì)輪數(shù)的上限進(jìn)行設(shè)定。輪數(shù)T的上限即共識(shí)的最多輪數(shù)，取值為跨分片交易回滾概率小于10-8時(shí)的輪數(shù)。根據(jù)表4，當(dāng)分片節(jié)點(diǎn)數(shù)和拜占庭比例固定時(shí)，w的增大對(duì)使交易的回滾概率小于10-8的輪數(shù)幾乎沒(méi)有影響。故表6分析計(jì)算了在輸入分片個(gè)數(shù)w=4時(shí)（可以粗略代表不同的輸入分片個(gè)數(shù)w），在不同的分片內(nèi)節(jié)點(diǎn)個(gè)數(shù)L和拜占庭節(jié)點(diǎn)比例f下，跨分片交易回滾的概率小于10-8時(shí)的輪數(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)過(guò)Tmax輪共識(shí)驗(yàn)證后，仍無(wú)法對(duì)同一筆交易達(dá)成共識(shí)，則放棄該筆交易，保全系統(tǒng)的總體性能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析

3.2.1 交易驗(yàn)證率測(cè)試

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

圖4 交易驗(yàn)證率Fig.4 Transaction verification rate

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

3.2.2 交易吞吐量測(cè)試

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

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

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

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

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

4 總結(jié)

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

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