秦文慧，李志淮，馬洪程

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

區(qū)塊鏈本質(zhì)上是一個(gè)去中心化的賬本，是一種融合了密碼學(xué)技術(shù)、分布式數(shù)據(jù)庫、計(jì)算機(jī)網(wǎng)絡(luò)、共識(shí)算法等計(jì)算機(jī)技術(shù)的新型應(yīng)用模式[1]。2021年6月，工信部發(fā)布文件指出：區(qū)塊鏈成為建設(shè)制造強(qiáng)國和網(wǎng)絡(luò)強(qiáng)國，發(fā)展數(shù)字經(jīng)濟(jì)，實(shí)現(xiàn)國家治理體系和治理能力現(xiàn)代化的重要支撐。在各種政策和環(huán)境的激勵(lì)下，區(qū)塊鏈技術(shù)研究得到大力支持。然而，目前區(qū)塊鏈基礎(chǔ)設(shè)施無法滿足大規(guī)模應(yīng)用的需求，其中限制區(qū)塊鏈技術(shù)大規(guī)模落地的一個(gè)重要因素就是區(qū)塊鏈的性能問題。

為了使區(qū)塊鏈能夠更好地適應(yīng)實(shí)際需求，必須增強(qiáng)其可擴(kuò)展性[2]。區(qū)塊鏈擴(kuò)容[3]是區(qū)塊鏈亟待突破的核心技術(shù)之一，通過提升可擴(kuò)展性，從而提升交易吞吐量。目前已有的擴(kuò)容解決方案包括側(cè)鏈[4]、分片技術(shù)[5]、DAG（directed acyclic graph）技術(shù)等[6]。

分片是目前最有效的實(shí)現(xiàn)高性能而不降低去中心化程度的區(qū)塊鏈擴(kuò)容方案。分片的思想是“分而治之”，在區(qū)塊鏈系統(tǒng)中，分片是指將事務(wù)和存儲(chǔ)劃分為不同的分組，每個(gè)分組并行處理交易，從而提升區(qū)塊鏈的性能[7]。分片包括網(wǎng)絡(luò)分片、交易分片、狀態(tài)分片等，其中狀態(tài)分片難度最大，狀態(tài)分片在網(wǎng)絡(luò)分片和交易分片的基礎(chǔ)上，不僅將交易處理并行化，且因每個(gè)分片只存儲(chǔ)與本分片交易相關(guān)的狀態(tài)信息，能夠減少存儲(chǔ)冗余。狀態(tài)分片可以從本質(zhì)上突破區(qū)塊鏈的容量瓶頸[8]。

從理論上看，區(qū)塊鏈分片可以有效提高網(wǎng)絡(luò)的整體性能，但是由于交易根據(jù)一定規(guī)則隨機(jī)分配，難以被預(yù)先規(guī)劃，某個(gè)分片內(nèi)極有可能因?yàn)榻灰琢窟^大而發(fā)生交易擁堵。目前應(yīng)用狀態(tài)分片技術(shù)的區(qū)塊鏈項(xiàng)目，尚未專門討論狀態(tài)分片后可能帶來的交易過載的處理問題。此外，區(qū)塊鏈中的驗(yàn)證節(jié)點(diǎn)，即共識(shí)節(jié)點(diǎn)的性能實(shí)際上存在較大的差異，而在目前主流方案中的驗(yàn)證節(jié)點(diǎn)分配時(shí)，沒有考慮節(jié)點(diǎn)交易驗(yàn)證能力的差異。嚴(yán)重時(shí)，整個(gè)區(qū)塊鏈網(wǎng)絡(luò)的交易吞吐量也會(huì)因單個(gè)分片交易驗(yàn)證擁堵而受到影響[9-10]。

綜上所述，本文針對(duì)區(qū)塊鏈狀態(tài)分片交易過載問題進(jìn)行預(yù)研究，提出了一種狀態(tài)約束下分片內(nèi)交易過載處理的多輪驗(yàn)證節(jié)點(diǎn)競選方案。方案考慮到狀態(tài)分片約束下，節(jié)點(diǎn)不能隨意調(diào)度到其他分片，將分片內(nèi)的交易驗(yàn)證分為多輪，在不同輪次中優(yōu)化節(jié)點(diǎn)競選策略，進(jìn)行區(qū)塊鏈分片內(nèi)的交易過載優(yōu)化處理，當(dāng)分片內(nèi)交易過載時(shí)，分配性能高的節(jié)點(diǎn)進(jìn)行下一輪的驗(yàn)證。實(shí)驗(yàn)表明，本文方案可以有效提升交易過載分片的交易驗(yàn)證率，減少分片交易擁堵的現(xiàn)象，提升區(qū)塊鏈分片性能。

1 問題的提出與研究

1.1 分片模型中的過載

1.1.1 分片中的交易分配和分布特點(diǎn)

分片理論上能夠提升整個(gè)系統(tǒng)層面的性能，但是單個(gè)分片仍然可能存在單點(diǎn)過熱問題，即在具有分片的區(qū)塊鏈系統(tǒng)中，為了避免雙花攻擊[11]，交易往往按發(fā)送地址隨機(jī)分配到各個(gè)分片中，再次分配還是會(huì)分配到特定的分片，造成單個(gè)分片內(nèi)部交易量過載，從而使得分片發(fā)生擁堵并且產(chǎn)生大量的交易成本。分片技術(shù)只是通過并行的方式實(shí)現(xiàn)了整體性能提升，但各分片本質(zhì)上是小型的區(qū)塊鏈系統(tǒng)，其性能并沒有實(shí)質(zhì)的提升，因此若在單個(gè)分片內(nèi)存在過多交易，分片仍會(huì)發(fā)生擁堵，并且如果此分片內(nèi)長期擁堵，所產(chǎn)生的交易成本也會(huì)遠(yuǎn)高于其他分片。分片交易過載如圖1所示。

由圖1可以看到，區(qū)塊鏈網(wǎng)絡(luò)中的交易進(jìn)行隨機(jī)分配后，可能會(huì)出現(xiàn)分片2與其他分片未驗(yàn)證交易數(shù)差距過大的現(xiàn)象。如果3個(gè)分片中節(jié)點(diǎn)處理能力恰好與1號(hào)分片中的交易數(shù)對(duì)應(yīng)，此時(shí)2號(hào)分片可能會(huì)因?yàn)槲打?yàn)證交易數(shù)過多造成交易過載。

1.1.2 交易過載的概率

假設(shè)區(qū)塊鏈系統(tǒng)中有ks個(gè)分片，未驗(yàn)證交易集合Tx={T1,T2,…,Tn}。由于區(qū)塊鏈中的交易是根據(jù)交易發(fā)送方的地址隨機(jī)分配到分片中的，可以將交易分配的過程視為n次獨(dú)立重復(fù)的伯努利試驗(yàn)，每個(gè)未驗(yàn)證的交易被分配到某一特定分片的概率為1/k。用X表示n重伯努利試驗(yàn)中，新交易被分配到某一特定分片的次數(shù)，則X的取值可以是0,1,…,n，隨機(jī)變量X的離散概率服從二項(xiàng)分布。

假設(shè)單個(gè)分片中驗(yàn)證節(jié)點(diǎn)Nsv數(shù)目保持均勻恒定并且每一輪可驗(yàn)證交易的最大數(shù)量為Tmax，可以通過式（1）計(jì)算出單個(gè)分片分配的交易數(shù)為Tmax的概率，其中n為區(qū)塊鏈系統(tǒng)中的未驗(yàn)證交易數(shù)，x為分配到某一分片的未驗(yàn)證交易數(shù)。

如果單個(gè)分片中的未驗(yàn)證交易數(shù)超過該分片中當(dāng)前輪次節(jié)點(diǎn)可驗(yàn)證交易的最大數(shù)量Tmax，驗(yàn)證節(jié)點(diǎn)在短時(shí)間內(nèi)無法完成驗(yàn)證，該分片就會(huì)交易擁堵?？梢赃\(yùn)用式（2）計(jì)算出單個(gè)分片中交易數(shù)超出Tmax的概率。

根據(jù)式（2），設(shè)置n=1 000，ks=10，用Python模擬計(jì)算出當(dāng)交易數(shù)為1 000，分片個(gè)數(shù)為10時(shí)，單個(gè)分片交易過載的概率。表1列舉了分片內(nèi)的交易數(shù)Tmax=[120,130,140,150]與其對(duì)應(yīng)發(fā)生過載的概率。

表1 單個(gè)分片交易數(shù)分配過載的概率Table 1 Probability of single sharding transaction number distribution overload

根據(jù)表1可以發(fā)現(xiàn)，當(dāng)交易數(shù)為1 000，分片個(gè)數(shù)為10時(shí)，單個(gè)分片交易數(shù)超過120的概率約為0.22，此時(shí)該分片的交易數(shù)已經(jīng)比各分片平均分配交易多出20%。以以太坊為例，分析分片交易過載對(duì)區(qū)塊鏈系統(tǒng)的影響。根據(jù)以太坊瀏覽器提供的相關(guān)數(shù)據(jù)，統(tǒng)計(jì)以太坊2021年10月28日至11月9日的每日交易筆數(shù)，如圖2所示。

圖2 中，橫坐標(biāo)表示日期，縱坐標(biāo)表示相對(duì)應(yīng)的交易量。平均24小時(shí)鏈上交易數(shù)約為100萬筆。根據(jù)以太坊網(wǎng)絡(luò)中的分片個(gè)數(shù)為64個(gè)，平均分配交易到各個(gè)分片，每個(gè)分片分到的交易數(shù)約為15 600筆。如果其中一個(gè)分片中的交易數(shù)比平均分配多出20%，則該分片比其他分片多出3 120筆交易。分析可知，隨著網(wǎng)絡(luò)中交易數(shù)的增多，各分片所分配交易數(shù)之間的差距會(huì)越來越大。區(qū)塊鏈分片時(shí)無法保證各個(gè)分片內(nèi)節(jié)點(diǎn)處理能力均衡。隨機(jī)分配交易具有很大的概率，導(dǎo)致部分分片未驗(yàn)證交易過載。

1.2 相關(guān)解決方法與分析

目前的分片方案一般采用隨機(jī)方式分配節(jié)點(diǎn)和交易，然而區(qū)塊鏈網(wǎng)絡(luò)中的節(jié)點(diǎn)因設(shè)備、網(wǎng)絡(luò)環(huán)境等因素的不同，存在較大的性能差異。隨機(jī)分配節(jié)點(diǎn)會(huì)導(dǎo)致各個(gè)分片的整體性能差異較大，隨機(jī)分配交易又可能因性能較差的分片分得較多的交易負(fù)載而產(chǎn)生擁堵，導(dǎo)致整個(gè)區(qū)塊鏈系統(tǒng)交易處理能力下降。目前，區(qū)塊鏈分片交易過載的問題尚未在全球公有鏈中得到有效解決。

研究人員提出了OmniLedger[12]、NEAR[13]和以太坊[14-15]等狀態(tài)分片協(xié)議，利用分片技術(shù)將網(wǎng)絡(luò)中的節(jié)點(diǎn)和交易進(jìn)行劃分，各個(gè)分片并行處理交易，提高了區(qū)塊鏈系統(tǒng)的交易處理能力。OmniLedger分片方案根據(jù)隨機(jī)協(xié)議選擇驗(yàn)證者分組，利用RandHound協(xié)議保證分配過程的安全性。該分片方案實(shí)現(xiàn)了狀態(tài)分片，降低了節(jié)點(diǎn)的存儲(chǔ)和啟動(dòng)開銷，但是并沒有考慮節(jié)點(diǎn)交易驗(yàn)證能力差異，無法處理分片內(nèi)交易過載。與以太坊不同，NEAR協(xié)議是單條區(qū)塊鏈，而各個(gè)分片植根于其上。像傳統(tǒng)的區(qū)塊鏈一樣，每個(gè)區(qū)塊都包含所有分片的所有交易，但是此數(shù)據(jù)并不存在于單個(gè)物理區(qū)塊中。應(yīng)對(duì)過量的交易，該分片方案采用延遲的交易處理方式，如果交易重新分配時(shí)仍指向同一個(gè)分片，該分片方案無力處理。以太坊市值高達(dá)25 400億元，是規(guī)模僅次于比特幣的區(qū)塊鏈項(xiàng)目。以太坊2.0使用信標(biāo)鏈進(jìn)行節(jié)點(diǎn)分配，大大提高了區(qū)塊鏈網(wǎng)絡(luò)的性能，同時(shí)也面對(duì)著很多新的挑戰(zhàn)。以太坊2.0嘗試在信標(biāo)鏈上部署負(fù)載均衡合約，當(dāng)某個(gè)分片中出現(xiàn)交易擁堵時(shí)，通過調(diào)用合約將負(fù)載轉(zhuǎn)移到其他分片。該方案目前還未在項(xiàng)目中實(shí)際應(yīng)用，其穩(wěn)定性仍需進(jìn)一步研究。

1.3 無狀態(tài)驗(yàn)證的局限

針對(duì)區(qū)塊鏈分片隨機(jī)分配交易機(jī)制產(chǎn)生的難以預(yù)知的區(qū)塊鏈分片交易過載問題，文獻(xiàn)[16]提出了一種基于節(jié)點(diǎn)驗(yàn)證能力積分的區(qū)塊鏈分片負(fù)載的多輪驗(yàn)證方案。此方案根據(jù)各分片的剩余負(fù)載，將驗(yàn)證能力高的節(jié)點(diǎn)再分配到高負(fù)載的分片進(jìn)行后續(xù)的驗(yàn)證，減少單個(gè)分片交易擁堵的情況。但是此方案沒有考慮狀態(tài)分片約束下，節(jié)點(diǎn)不能隨意競選的問題。

狀態(tài)分片中每個(gè)分片只存儲(chǔ)所負(fù)責(zé)分片中的狀態(tài)，因此在下一次節(jié)點(diǎn)重新分配時(shí)，新節(jié)點(diǎn)加入分片之前必須等待同步完該分片中的狀態(tài)信息后才可以加入分片并提供算力，否則將無法保證數(shù)據(jù)的連貫性，從而影響交易驗(yàn)證的有效性。而狀態(tài)信息的同步需要消耗大量的時(shí)間，因此若頻繁地在分片之間進(jìn)行節(jié)點(diǎn)的輪換，會(huì)極大地增加系統(tǒng)的延遲，從而影響系統(tǒng)的活性。因此，僅考慮無狀態(tài)驗(yàn)證，節(jié)點(diǎn)隨意跨分片間調(diào)度是不可行的。

根據(jù)上述分析可知，在前期較少的關(guān)于交易過載處理的分片方案中存在無狀態(tài)驗(yàn)證的局限。故本文針對(duì)以上問題進(jìn)行分析及預(yù)研究，在跨分片節(jié)點(diǎn)調(diào)度外提出了一種狀態(tài)約束下交易過載處理的多輪節(jié)點(diǎn)競選方案。

2 分片多輪驗(yàn)證模型的交易過載處理

本文在現(xiàn)有區(qū)塊鏈分片基礎(chǔ)上，提出了狀態(tài)分片約束下交易過載處理的多輪節(jié)點(diǎn)競選方案。一輪驗(yàn)證后，通過節(jié)點(diǎn)綜合積分方法更準(zhǔn)確地評(píng)價(jià)節(jié)點(diǎn)，計(jì)算剩余的未確認(rèn)交易數(shù)量并判斷剩余負(fù)載，通過節(jié)點(diǎn)競選策略有效地組織節(jié)點(diǎn)進(jìn)行交易驗(yàn)證，以縮短區(qū)塊鏈交易確認(rèn)時(shí)間，使得節(jié)點(diǎn)篩選更快收斂，實(shí)施均衡化處理，提高區(qū)塊鏈交易處理能力。

2.1 分片的多輪驗(yàn)證模型

通過上述分析可以發(fā)現(xiàn)，區(qū)塊鏈狀態(tài)分片中，交易通常按照一定的規(guī)則被隨機(jī)分配到各個(gè)分片，且再次分配還是會(huì)被分配到特定分片，存在單個(gè)分片交易過載的問題。此外，區(qū)塊鏈系統(tǒng)的交易負(fù)載具有滯后性，即無法預(yù)先獲得各分片的交易負(fù)載對(duì)此進(jìn)行處理。目前一些主流的分片項(xiàng)目并沒有針對(duì)分片的交易過載問題提出切實(shí)可行的解決方案。

針對(duì)單個(gè)分片內(nèi)拜占庭節(jié)點(diǎn)比例過高導(dǎo)致單個(gè)分片失效概率增大的問題，多輪PBFT驗(yàn)證（multiple rounds of PBFT verification，MRPV）方案[17]被提出。連續(xù)多輪進(jìn)行交易驗(yàn)證，當(dāng)各個(gè)分片開始對(duì)分片內(nèi)的交易進(jìn)行驗(yàn)證時(shí)，即為第一輪驗(yàn)證，當(dāng)分片中產(chǎn)生一個(gè)區(qū)塊后，即為一輪結(jié)束。本文基于此方案提出狀態(tài)分片交易過載處理的多輪PBFT驗(yàn)證方案，利用多輪PBFT機(jī)制在每輪驗(yàn)證后獲取到分片內(nèi)的交易負(fù)載，通過調(diào)整分片內(nèi)輪次間不同性能的驗(yàn)證節(jié)點(diǎn)，來處理狀態(tài)分片內(nèi)交易過載的問題，提升區(qū)塊鏈系統(tǒng)的TPS（transaction per second）。

如圖3所示，第t時(shí)隙，分片的狀態(tài)為SS(t)，待驗(yàn)證的交易集合為Tx(t)，分片內(nèi)共識(shí)節(jié)點(diǎn)組表示為Vsv(Nsv=||Vsv)。在第t時(shí)隙，共識(shí)驗(yàn)證節(jié)點(diǎn)組Vsv利用當(dāng)前狀態(tài)SS(t)對(duì)當(dāng)前交易集合Tx(t)進(jìn)行第1輪共識(shí)驗(yàn)證，記為Vsv(t,1)[SS(t),Tx(t)]。

若交易在第t時(shí)隙被驗(yàn)證成功，則將交易打包上鏈，并更新狀態(tài)。第t時(shí)隙結(jié)束后，若Tx(t)中仍存在未經(jīng)驗(yàn)證的交易，則重新選取共識(shí)節(jié)點(diǎn)對(duì)此批交易，在第t+1時(shí)隙進(jìn)行第2輪的驗(yàn)證，如過程①所示，記為Vsv(t+1,2)[SS(t),Tx(t)]。若仍未驗(yàn)證成功，則繼續(xù)重新選取共識(shí)節(jié)點(diǎn)進(jìn)行第3輪驗(yàn)證，如過程②所示，記為Vsv(t+2,3)[SS(t),Tx(t)]，直至達(dá)到輪數(shù)上限放棄交易。

多輪方案中不同輪次可能對(duì)應(yīng)多個(gè)共識(shí)組，分別處理不同的交易。若交易集合Tx(t)在第t時(shí)隙被確認(rèn)，則將交易打包上鏈，并在第t+1時(shí)隙將分片狀態(tài)更新為SS(t+1)。第t+1時(shí)隙又將有新的交易集合Tx(t+1)等待被處理，選取新的共識(shí)節(jié)點(diǎn)組對(duì)此批交易進(jìn)行第一次驗(yàn)證，記為Vsv(t+1,1)[SS(t+1),Tx(t+1)]。隨著輪數(shù)增多，每一時(shí)隙的交易驗(yàn)證延遲會(huì)帶來更多的負(fù)載。

狀態(tài)分片交易過載處理的多輪驗(yàn)證方案的具體過程如下：

（1）將節(jié)點(diǎn)隨機(jī)分配到各個(gè)分片，再將交易根據(jù)映射規(guī)則隨機(jī)分配到各個(gè)分片，然后初始化交易處理的輪次。

（2）待同步節(jié)點(diǎn)首先進(jìn)行狀態(tài)同步，并根據(jù)節(jié)點(diǎn)狀態(tài)同步的快慢測評(píng)其通信能力。待同步節(jié)點(diǎn)完成狀態(tài)同步后可以進(jìn)入分片內(nèi)并獲得參與共識(shí)驗(yàn)證的資格，通過VRF隨機(jī)函數(shù)選出共識(shí)節(jié)點(diǎn)。

（3）由分片內(nèi)的共識(shí)節(jié)點(diǎn)集合Vsv對(duì)分配到該分片的全部交易進(jìn)行共識(shí)驗(yàn)證，超過2/3共識(shí)節(jié)點(diǎn)達(dá)成一致則驗(yàn)證成功，將該組交易打包到區(qū)塊。通過節(jié)點(diǎn)綜合積分機(jī)制更新共識(shí)節(jié)點(diǎn)的分值，并進(jìn)行交易負(fù)載的計(jì)算，判斷是否有未驗(yàn)證交易。若分片內(nèi)交易過載，則通過節(jié)點(diǎn)競選策略選取通信能力高的節(jié)點(diǎn)進(jìn)行下一輪的驗(yàn)證，更快地處理交易。

（4）若分片未達(dá)到共識(shí)，則扣除共識(shí)節(jié)點(diǎn)的分值，通過節(jié)點(diǎn)競選策略分配共識(shí)表現(xiàn)較好的驗(yàn)證節(jié)點(diǎn)進(jìn)行下一輪的驗(yàn)證。

（5）若連續(xù)T輪過后仍未達(dá)成有效共識(shí)，則選擇放棄該筆交易。通過犧牲交易的可用性，保全系統(tǒng)的總體性能。

需注意，在步驟（3）中，達(dá)成共識(shí)的分片同樣需要重新分配共識(shí)節(jié)點(diǎn)，一方面，如果分片內(nèi)交易過載，需分配綜合性能強(qiáng)的節(jié)點(diǎn)進(jìn)行驗(yàn)證，提高分片的處理能力。另一方面，如果不進(jìn)行節(jié)點(diǎn)重新分配，分片中的節(jié)點(diǎn)一直處于同一分片中，會(huì)導(dǎo)致如下兩個(gè)問題：一是分片中的拜占庭節(jié)點(diǎn)會(huì)因?yàn)橐淮闻既坏姆峙涠恢绷粼谡９ぷ鞯姆制?，其共識(shí)表現(xiàn)分值無法被扣除，拜占庭節(jié)點(diǎn)身份無法體現(xiàn)，不利于系統(tǒng)整體的穩(wěn)定。二是隨著驗(yàn)證輪數(shù)的增加，同一分片中的節(jié)點(diǎn)熟悉彼此后，可能會(huì)為謀求更大的利益，互相勾結(jié)攻擊分片，影響系統(tǒng)的安全性。

多輪驗(yàn)證的流程圖如圖4所示。

2.2 節(jié)點(diǎn)綜合積分機(jī)制

本文在現(xiàn)有區(qū)塊鏈分片的基礎(chǔ)上，提出了節(jié)點(diǎn)綜合積分機(jī)制。文獻(xiàn)[18]通過節(jié)點(diǎn)處理交易能力來進(jìn)行節(jié)點(diǎn)積分，本文考慮到實(shí)際網(wǎng)絡(luò)中的影響因素，根據(jù)節(jié)點(diǎn)的共識(shí)表現(xiàn)和節(jié)點(diǎn)的通信能力兩個(gè)指標(biāo)來評(píng)估節(jié)點(diǎn)性能，并且為每個(gè)指標(biāo)都設(shè)置一個(gè)指標(biāo)權(quán)重占比，然后再根據(jù)這些指標(biāo)數(shù)據(jù)，計(jì)算分?jǐn)?shù)，綜合權(quán)衡兩個(gè)指標(biāo)。在下一輪節(jié)點(diǎn)重新分配時(shí)，遵循基于節(jié)點(diǎn)積分的分配算法，選取綜合積分高的節(jié)點(diǎn)進(jìn)入下一輪共識(shí)，解決區(qū)塊鏈系統(tǒng)分片內(nèi)剩余負(fù)載不均衡的問題，提高系統(tǒng)的交易吞吐量。

2.2.1 節(jié)點(diǎn)共識(shí)表現(xiàn)評(píng)估

節(jié)點(diǎn)在共識(shí)過程中的表現(xiàn)是降低選中拜占庭節(jié)點(diǎn)參與共識(shí)的重要指標(biāo)，同時(shí)也是區(qū)塊鏈中節(jié)點(diǎn)提供資源和服務(wù)可靠性的評(píng)價(jià)因素。通過對(duì)區(qū)塊鏈網(wǎng)絡(luò)中節(jié)點(diǎn)行為信息的收集、評(píng)價(jià)、量化、更新，從而達(dá)到利用節(jié)點(diǎn)的可靠性評(píng)估對(duì)其行為進(jìn)行規(guī)范和限制的目的。在區(qū)塊鏈網(wǎng)絡(luò)通信中，選擇共識(shí)表現(xiàn)好的節(jié)點(diǎn)參與驗(yàn)證，在一定程度上可以保證區(qū)塊鏈網(wǎng)絡(luò)的可靠性。因此，節(jié)點(diǎn)共識(shí)表現(xiàn)評(píng)價(jià)機(jī)制須體現(xiàn)多粒度、動(dòng)態(tài)更新的特點(diǎn)，同時(shí)符合人類社會(huì)信任評(píng)價(jià)中“信任積累緩慢，信任迅速消減”的特性，即信任的增加是緩慢的，信任的衰減是迅速的。如果只是根據(jù)節(jié)點(diǎn)每次的共識(shí)結(jié)果對(duì)其積分進(jìn)行累加，會(huì)太過于片面，可能會(huì)導(dǎo)致一些惡意節(jié)點(diǎn)故意通過節(jié)點(diǎn)通信能力來累積分值，從而得到參與驗(yàn)證的機(jī)會(huì)，這樣會(huì)對(duì)系統(tǒng)的性能造成比較大的負(fù)面影響。

基于此，本文引入了基于時(shí)間的信任衰減函數(shù)以及節(jié)點(diǎn)信任積分的動(dòng)態(tài)更新策略，來提升區(qū)塊鏈網(wǎng)絡(luò)的可靠性和安全性。隨著時(shí)間的推移，節(jié)點(diǎn)成功參與兩次共識(shí)之間相差的時(shí)間越長，共識(shí)積分的占比會(huì)越小。共識(shí)積分的衰減函數(shù)如式（3）所示：

式（3）中，Ti表示隨著時(shí)間的推移，節(jié)點(diǎn)的共識(shí)表現(xiàn)分值的衰減程度；tnew表示節(jié)點(diǎn)當(dāng)前共識(shí)發(fā)生的時(shí)間；tpre表示節(jié)點(diǎn)上次共識(shí)發(fā)生的時(shí)間。|tnew-tpre|值越大，Ti就越小。當(dāng)節(jié)點(diǎn)長時(shí)間不在線，或者出現(xiàn)網(wǎng)絡(luò)故障，導(dǎo)致節(jié)點(diǎn)參加兩次共識(shí)時(shí)間的間隔比較長，則衰減程度就會(huì)相應(yīng)增大。根據(jù)節(jié)點(diǎn)的投票信息與最終的共識(shí)結(jié)果是否一致來判斷節(jié)點(diǎn)是否成功參與共識(shí)。

節(jié)點(diǎn)共識(shí)分值Ri(x)的具體計(jì)算方式如式（4）所示。如果投票信息與最終的共識(shí)結(jié)果一致，則節(jié)點(diǎn)的可靠值是結(jié)合時(shí)間衰減函數(shù)進(jìn)行累加。若共識(shí)成功則加1分。若不一致或者檢測到驗(yàn)證節(jié)點(diǎn)作惡，則表明此節(jié)點(diǎn)為惡意，共識(shí)分值減10分。如果節(jié)點(diǎn)超時(shí)沒有進(jìn)行響應(yīng)，表明此節(jié)點(diǎn)可能是因?yàn)榫W(wǎng)絡(luò)故障造成超時(shí)，但是也有可能節(jié)點(diǎn)是惡意不回應(yīng)，此時(shí)的積分不會(huì)直接降為初始值，而是將積分值減5分。

式（4）中，x表示節(jié)點(diǎn)i參與共識(shí)的次數(shù)，Ri(x)表示節(jié)點(diǎn)i參與x次共識(shí)后的積分，Ri(x)的初始值Ri(0)設(shè)為0，Ti表示節(jié)點(diǎn)i的共識(shí)表現(xiàn)隨時(shí)間的衰減程度。

2.2.2 節(jié)點(diǎn)通信能力評(píng)估

在區(qū)塊鏈真實(shí)網(wǎng)絡(luò)中，區(qū)塊鏈節(jié)點(diǎn)具有異構(gòu)性，主要表現(xiàn)在節(jié)點(diǎn)的驗(yàn)證能力、存儲(chǔ)能力、通信能力的差異[19]。一筆交易信息要快速可靠地傳輸給網(wǎng)絡(luò)中的其他節(jié)點(diǎn)，需要重點(diǎn)考慮節(jié)點(diǎn)通信能力，本文中節(jié)點(diǎn)的通信能力評(píng)測是在狀態(tài)同步過程中進(jìn)行的。本文對(duì)節(jié)點(diǎn)的通信時(shí)間和通信效率進(jìn)行研究，將節(jié)點(diǎn)的硬件性能作為通信影響因子來量化節(jié)點(diǎn)的通信能力。

節(jié)點(diǎn)由于硬件配置的異構(gòu)性導(dǎo)致其在區(qū)塊鏈通信過程中的傳輸能力存在差異。文獻(xiàn)[2]通過CPU內(nèi)核數(shù)n、CPU頻率C、內(nèi)存容量M、磁盤I/O速率D、網(wǎng)絡(luò)帶寬T等指標(biāo)來計(jì)算一個(gè)節(jié)點(diǎn)的硬件性能。本文的積分重點(diǎn)在節(jié)點(diǎn)對(duì)共識(shí)的貢獻(xiàn)力度，因此主要考慮節(jié)點(diǎn)的CPU處理頻率、內(nèi)存大小以及CPU利用率和內(nèi)存利用率。通信能力Pi的量化公式如下：

其中，Ci代表節(jié)點(diǎn)i的CPU處理頻率，n表示CPU內(nèi)核數(shù)，Mi表示節(jié)點(diǎn)i的內(nèi)存大小，Uc表示節(jié)點(diǎn)的CPU利用率，Um表示節(jié)點(diǎn)的內(nèi)存利用率。

2.2.3 節(jié)點(diǎn)綜合性能評(píng)估

節(jié)點(diǎn)的綜合性能MergeScore評(píng)估計(jì)算方式如式（6）所示：

其中，Ri(x)表示節(jié)點(diǎn)i的共識(shí)表現(xiàn)積分，Pi表示節(jié)點(diǎn)的通信能力積分，β是指標(biāo)的權(quán)重參數(shù)，可根據(jù)具體情況設(shè)定合理的值。考慮到?jīng)]有可靠傳輸?shù)谋Ｕ?，?fù)載的優(yōu)化是無意義的。因此要嚴(yán)格杜絕通信能力強(qiáng)，但是共識(shí)表現(xiàn)差的節(jié)點(diǎn)作為驗(yàn)證節(jié)點(diǎn)，可適當(dāng)調(diào)整β的值。

2.3 交易負(fù)載計(jì)算模型

區(qū)塊鏈系統(tǒng)中的交易根據(jù)交易發(fā)送方的地址隨機(jī)分配到各個(gè)分片，因此無法保證交易數(shù)量均勻分配。本文方案引入多輪驗(yàn)證的思想，分片中的節(jié)點(diǎn)在每一輪達(dá)成共識(shí)打包交易出塊后，計(jì)算本輪分片內(nèi)剩余交易負(fù)載，剩余負(fù)載進(jìn)入下一輪與新交易一起打包處理，根據(jù)分片內(nèi)的剩余負(fù)載來選取已有節(jié)點(diǎn)在不同輪次之間均衡使用。本文的每一輪待處理的交易負(fù)載包括上一輪次分片內(nèi)的剩余負(fù)載和當(dāng)前輪次的交易負(fù)載兩部分，由式（7）計(jì)算：

其中，shardLi(t)為分片i在第t輪的交易負(fù)載值，Counti(T(t-1))為該分片上一輪交易驗(yàn)證后的剩余負(fù)載，即未確認(rèn)交易數(shù)，Counti(T(t))表示該分片第t輪新提交的交易數(shù)。分片的交易負(fù)載與輪次的關(guān)系如圖5所示。

需注意，不同輪次對(duì)應(yīng)不同的共識(shí)組，且每一輪次可能對(duì)應(yīng)多個(gè)共識(shí)組。第i輪的剩余負(fù)載作延后處理，后續(xù)輪次的驗(yàn)證一定是對(duì)未確認(rèn)交易的重復(fù)驗(yàn)證。

2.4 節(jié)點(diǎn)競選策略

2.4.1 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移機(jī)制

狀態(tài)分片中活躍節(jié)點(diǎn)的角色是動(dòng)態(tài)轉(zhuǎn)變的，本文根據(jù)網(wǎng)絡(luò)中的節(jié)點(diǎn)不同的狀態(tài)，將節(jié)點(diǎn)劃分為全局候選節(jié)點(diǎn)、待同步狀態(tài)節(jié)點(diǎn)、分片內(nèi)就緒節(jié)點(diǎn)、分片內(nèi)共識(shí)節(jié)點(diǎn)和局外節(jié)點(diǎn)。處于不同狀態(tài)的節(jié)點(diǎn)對(duì)應(yīng)不同的行為。

待同步狀態(tài)節(jié)點(diǎn)由于沒有存儲(chǔ)當(dāng)前分片的狀態(tài)信息，需要先進(jìn)行狀態(tài)同步，即同步節(jié)點(diǎn)所在分片的賬本信息后才有資格參與交易的驗(yàn)證。此外，通過節(jié)點(diǎn)狀態(tài)同步的快慢來測定節(jié)點(diǎn)的通信能力。以下三種情況的節(jié)點(diǎn)統(tǒng)稱為待同步狀態(tài)節(jié)點(diǎn)：

（1）狀態(tài)分片后被分配到指定分片并等待加入分片進(jìn)行工作的節(jié)點(diǎn)。

（2）后續(xù)新加入系統(tǒng)的節(jié)點(diǎn)。

（3）部分節(jié)點(diǎn)因?yàn)榫W(wǎng)絡(luò)問題掉線重連，可能會(huì)丟失部分狀態(tài)，同樣需要先同步信息后再參與共識(shí)流程。

狀態(tài)同步后的節(jié)點(diǎn)會(huì)進(jìn)入分片內(nèi)，獲取參與交易驗(yàn)證的資格，轉(zhuǎn)換為分片內(nèi)就緒節(jié)點(diǎn)。每一輪通過節(jié)點(diǎn)競選策略選出共識(shí)節(jié)點(diǎn)集合進(jìn)行交易的驗(yàn)證。

在完成一輪驗(yàn)證并進(jìn)行積分核算后，共識(shí)節(jié)點(diǎn)集合按照分值進(jìn)行排序，并將排名末位的節(jié)點(diǎn)淘汰轉(zhuǎn)入全局候選節(jié)點(diǎn)隊(duì)列，進(jìn)入靜默期靜默一段時(shí)間等待進(jìn)入待同步狀態(tài)節(jié)點(diǎn)。

全局候選節(jié)點(diǎn)隊(duì)列依據(jù)分值按序排列，等待加入分片進(jìn)行工作，后續(xù)可依據(jù)輪次通過隨機(jī)算法選中進(jìn)入到分片內(nèi)的待同步節(jié)點(diǎn)集合。

分片內(nèi)的就緒節(jié)點(diǎn)需要監(jiān)督共識(shí)節(jié)點(diǎn)進(jìn)行共識(shí)驗(yàn)證，若通過欺詐性證明檢測出共識(shí)節(jié)點(diǎn)作惡，例如節(jié)點(diǎn)隨意篡改轉(zhuǎn)發(fā)信息、丟棄信息、破壞網(wǎng)絡(luò)資源等，則進(jìn)行舉報(bào)，將作惡節(jié)點(diǎn)轉(zhuǎn)入分片外的局外節(jié)點(diǎn)集合，剝奪其進(jìn)入分片內(nèi)參與驗(yàn)證的資格，并對(duì)提交了欺詐性證明的就緒節(jié)點(diǎn)進(jìn)行獎(jiǎng)勵(lì)。節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換流程如圖6所示。

2.4.2 可驗(yàn)證的隨機(jī)分配算法

VRF（verifiable random function）是可驗(yàn)證的隨機(jī)函數(shù)，是結(jié)合了哈希函數(shù)與非對(duì)稱加密的應(yīng)用算法。通過隨機(jī)輸入一個(gè)數(shù)值，得到一個(gè)任意的輸出，且該輸出的結(jié)果，可以通過零知識(shí)證明來驗(yàn)證其正確性。

本文基于以下三種情況采用可驗(yàn)證的隨機(jī)分配算法VRF進(jìn)行節(jié)點(diǎn)的分配：

（1）狀態(tài)分片交易依據(jù)相應(yīng)規(guī)則被分配到分片中，通過VRF算法隨機(jī)分配節(jié)點(diǎn)到各個(gè)分片。

（2）每一輪次通過VRF算法從就緒節(jié)點(diǎn)中重新選取驗(yàn)證節(jié)點(diǎn)，以此來保證節(jié)點(diǎn)分配時(shí)較高的隨機(jī)性、不可預(yù)測性和可驗(yàn)證性。

（3）全局待分配同步節(jié)點(diǎn)需要通過VRF算法，依據(jù)當(dāng)前輪次隨機(jī)選中進(jìn)入分片內(nèi)待同步狀態(tài)節(jié)點(diǎn)集合，以此保證其在不同時(shí)刻進(jìn)入不同的分片。

由于VRF的不可預(yù)測性、可驗(yàn)證和無偏倚的特性優(yōu)勢，節(jié)點(diǎn)的分配無法預(yù)測，可以高效、安全且隨機(jī)地分配節(jié)點(diǎn)，保證了分片的驗(yàn)證有效性和系統(tǒng)安全性。

2.4.3 狀態(tài)分片約束下的節(jié)點(diǎn)競選策略

針對(duì)第1章的分析，本文提出了一種適應(yīng)于狀態(tài)分片約束下的多輪PBFT驗(yàn)證的節(jié)點(diǎn)競選方案。利用分片內(nèi)節(jié)點(diǎn)能力的差異，每一輪驗(yàn)證結(jié)束后通過更新共識(shí)節(jié)點(diǎn)組，對(duì)交易過載的分片進(jìn)行快速調(diào)整處理，同時(shí)可以降低分片內(nèi)的拜占庭節(jié)點(diǎn)比例，有效提高驗(yàn)證效率。

方案進(jìn)行節(jié)點(diǎn)競選的具體步驟如下：

（1）每輪交易驗(yàn)證完成后，根據(jù)節(jié)點(diǎn)綜合積分機(jī)制進(jìn)行節(jié)點(diǎn)積分核算。

（2）打包交易成功出塊后，計(jì)算本輪剩余交易負(fù)載，下一輪次再結(jié)合新分配的交易根據(jù)交易負(fù)載計(jì)算模型計(jì)算出本輪的交易負(fù)載。

（3）節(jié)點(diǎn)競選首先借助VRF隨機(jī)算法，從分片內(nèi)的節(jié)點(diǎn)Ns中隨機(jī)選出一半節(jié)點(diǎn)，以此保證一定的隨機(jī)性和公平性。再選取前端分值最高的Nsv個(gè)共識(shí)節(jié)點(diǎn)進(jìn)入下一輪驗(yàn)證。

（4）每輪驗(yàn)證結(jié)束后，根據(jù)節(jié)點(diǎn)的共識(shí)表現(xiàn)更新節(jié)點(diǎn)分值，共識(shí)節(jié)點(diǎn)組按照分值進(jìn)行排序，分值最低的節(jié)點(diǎn)進(jìn)行末位淘汰，作為本輪轉(zhuǎn)出當(dāng)前分片的節(jié)點(diǎn)，按照最新分值轉(zhuǎn)入全局候選節(jié)點(diǎn)序列的相應(yīng)位置。

（5）若檢測出節(jié)點(diǎn)作惡，則將節(jié)點(diǎn)轉(zhuǎn)入局外節(jié)點(diǎn)，使其失去加入分片內(nèi)參與驗(yàn)證工作的資格。

節(jié)點(diǎn)競選的詳細(xì)流程如圖7所示。

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

3.1 實(shí)驗(yàn)基本設(shè)置

為驗(yàn)證本文提出的狀態(tài)分片內(nèi)的交易過載多輪節(jié)點(diǎn)競選方案的可用性和有效性，對(duì)本方案進(jìn)行分片規(guī)模與有效性分析和交易驗(yàn)證輪數(shù)的研究，并將本方案與未進(jìn)行交易過載處理的MRPV方案進(jìn)行對(duì)比實(shí)驗(yàn)，觀察兩種方案在交易驗(yàn)證率、系統(tǒng)吞吐量方面的性能。實(shí)驗(yàn)設(shè)置總節(jié)點(diǎn)數(shù)為1 000，每100個(gè)節(jié)點(diǎn)為1個(gè)分片，設(shè)置共識(shí)節(jié)點(diǎn)數(shù)為10。節(jié)點(diǎn)的共識(shí)表現(xiàn)初始分值為100分，節(jié)點(diǎn)通信能力初始分值為60～100分。

本文設(shè)計(jì)的狀態(tài)分片內(nèi)的交易過載多輪節(jié)點(diǎn)競選方案在實(shí)驗(yàn)室環(huán)境下進(jìn)行，需要設(shè)置以下假設(shè)條件：

（1）分片期間總節(jié)點(diǎn)數(shù)目保持均勻恒定。

（2）本實(shí)驗(yàn)所設(shè)置的交易均不屬于跨分片交易。

（3）本實(shí)驗(yàn)的節(jié)點(diǎn)屬性可變，即本輪誠實(shí)的節(jié)點(diǎn)，下一輪可變成拜占庭節(jié)點(diǎn)。

3.2 分片規(guī)模及有效性分析

在本文的多輪PBFT驗(yàn)證方案中，由于每一輪共識(shí)時(shí)間較短，且狀態(tài)分片中的待同步節(jié)點(diǎn)還需同步每一輪共識(shí)后產(chǎn)生的區(qū)塊，增加了分片內(nèi)的通信量，本節(jié)將分析共識(shí)節(jié)點(diǎn)的數(shù)目，在降低分片內(nèi)通信開銷的同時(shí)，保證每個(gè)分片內(nèi)的驗(yàn)證有效性。

3.2.1 通信量與分片內(nèi)共識(shí)節(jié)點(diǎn)數(shù)目的關(guān)系分析

在真實(shí)區(qū)塊鏈網(wǎng)絡(luò)中，考慮到每個(gè)節(jié)點(diǎn)的實(shí)際網(wǎng)絡(luò)的帶寬可能并不一致，因此網(wǎng)絡(luò)中的通信量會(huì)有一定的限制。由于PBFT共識(shí)機(jī)制中驗(yàn)證節(jié)點(diǎn)增多，分片內(nèi)的通信復(fù)雜度也會(huì)顯著增加。本文將選取盡量少的驗(yàn)證節(jié)點(diǎn)進(jìn)行共識(shí)，降低通信開銷成本。為了滿足系統(tǒng)的活性，節(jié)點(diǎn)的網(wǎng)絡(luò)帶寬必須足以讓整個(gè)網(wǎng)絡(luò)能同時(shí)進(jìn)行上一區(qū)塊的廣播驗(yàn)證，客戶端發(fā)布待驗(yàn)證交易、主節(jié)點(diǎn)共識(shí)以及普通節(jié)點(diǎn)投票幾項(xiàng)工作。本文將滿足網(wǎng)絡(luò)主節(jié)點(diǎn)所需的最低網(wǎng)絡(luò)帶寬抽象為式（8）：

其中，B為網(wǎng)絡(luò)帶寬的最小值，Nsv為分片內(nèi)共識(shí)節(jié)點(diǎn)的數(shù)目，HashSize為轉(zhuǎn)發(fā)哈希的大小（固定32 Byte），a為普通節(jié)點(diǎn)投票產(chǎn)生主節(jié)點(diǎn)所產(chǎn)生的通信量。BlockSize為打包的一個(gè)區(qū)塊的大小，其計(jì)算公式如下所示：

式（9）中，HeaderSize為區(qū)塊頭的大小，txSize為一條交易信息的大小。

式（10）中，TxCount為一個(gè)區(qū)塊打包的交易數(shù)量，TPS為每秒可打包的交易數(shù)量，TD為上一區(qū)塊進(jìn)入主節(jié)點(diǎn)共識(shí)的時(shí)刻與本輪進(jìn)入主節(jié)點(diǎn)共識(shí)階段的時(shí)間差。

式（11）中，CP為一致性協(xié)議產(chǎn)生的通信量，p為prepare階段節(jié)點(diǎn)廣播的確認(rèn)消息的大小，c為commit階段各節(jié)點(diǎn)廣播的確認(rèn)消息的大小。

通過式（11）可以看出，網(wǎng)絡(luò)中最小帶寬取決于分片內(nèi)共識(shí)節(jié)點(diǎn)的數(shù)量Nsv。若僅僅將Nsv設(shè)置過小，雖然通信量較低，但是這將導(dǎo)致嚴(yán)重的中心化以及安全性問題，這與本文分片規(guī)模設(shè)置的初衷不符。分片內(nèi)共識(shí)節(jié)點(diǎn)的數(shù)量Nsv如果設(shè)置過大，將會(huì)使得網(wǎng)絡(luò)中的通信量過大，從而造成網(wǎng)絡(luò)擁堵。其中節(jié)點(diǎn)數(shù)量帶來的通信量占網(wǎng)絡(luò)帶寬比如圖8所示。

本文為了控制整個(gè)過程中所產(chǎn)生的通信量占用百分比為網(wǎng)絡(luò)帶寬的30%到40%，通過仿真計(jì)算得出共識(shí)節(jié)點(diǎn)應(yīng)該控制在10到19個(gè)的范圍內(nèi)。

3.2.2 單個(gè)分片內(nèi)不同拜占庭節(jié)點(diǎn)比例的概率分析

設(shè)置系統(tǒng)總節(jié)點(diǎn)數(shù)N為1 000，單個(gè)分片內(nèi)節(jié)點(diǎn)數(shù)Ns為100，系統(tǒng)內(nèi)拜占庭節(jié)點(diǎn)比例為1/3。X1表示單個(gè)分片內(nèi)節(jié)點(diǎn)數(shù)Ns中拜占庭節(jié)點(diǎn)的數(shù)量，X1服從超幾何分布，記為X1～H(Ns,N×Pn,N)，系統(tǒng)中總的拜占庭節(jié)點(diǎn)比例Pn為1/3。系統(tǒng)進(jìn)行節(jié)點(diǎn)分配時(shí)，可看作從系統(tǒng)N個(gè)節(jié)點(diǎn)中為每個(gè)分片選取Ns個(gè)節(jié)點(diǎn)，則在分片內(nèi)拜占庭節(jié)點(diǎn)數(shù)量為K1時(shí)，分片內(nèi)拜占庭節(jié)點(diǎn)比例Ps在不同點(diǎn)的取值概率P1如式（12）所示：

根據(jù)公式運(yùn)用Python模擬計(jì)算出單個(gè)分片內(nèi)不同拜占庭節(jié)點(diǎn)比例的概率如圖9所示。

由圖9可知，當(dāng)系統(tǒng)內(nèi)總拜占庭節(jié)點(diǎn)比例Pn為1/3時(shí)，單個(gè)分片內(nèi)拜占庭節(jié)點(diǎn)比例Ps在[0，0.2]范圍內(nèi)的概率之和為1.50E-3；在[0.2，0.45]范圍內(nèi)的概率為0.99，其中，當(dāng)Ps等于0.33時(shí)的概率最大；在[0.45，1]范圍內(nèi)的概率之和為7.02E-3。可以發(fā)現(xiàn)單個(gè)分片拜占庭節(jié)點(diǎn)比例在[0.2，0.45]范圍內(nèi)的概率較大。經(jīng)驗(yàn)算，P1的概率總和近似為1。

3.2.3 不同共識(shí)節(jié)點(diǎn)數(shù)目導(dǎo)致共識(shí)失效的概率分析

假設(shè)分片內(nèi)共識(shí)節(jié)點(diǎn)數(shù)量為Nsv，分片內(nèi)共識(shí)節(jié)點(diǎn)組中拜占庭節(jié)點(diǎn)比例為Psv,X2表示選取的Nsv個(gè)共識(shí)節(jié)點(diǎn)中拜占庭節(jié)點(diǎn)的數(shù)量，則X2服從超幾何分布，X2～H(Nsv,Ns×Ps,Ns)。Psv在不同共識(shí)節(jié)點(diǎn)數(shù)取值的概率P2如式（13）所示：

單個(gè)分片內(nèi)節(jié)點(diǎn)數(shù)Ns中拜占庭節(jié)點(diǎn)的數(shù)量X1和共識(shí)組中拜占庭節(jié)點(diǎn)的數(shù)量X2所有情況下分片失效的概率取值之和Psum如式（14）所示。經(jīng)驗(yàn)算，Psum的總和近似為1。當(dāng)共識(shí)節(jié)點(diǎn)組中拜占庭節(jié)點(diǎn)比例超過1/3時(shí)，共識(shí)節(jié)點(diǎn)組會(huì)無法達(dá)成共識(shí)，導(dǎo)致共識(shí)失效。當(dāng)分片內(nèi)共識(shí)節(jié)點(diǎn)數(shù)量Nsv不同時(shí)，共識(shí)節(jié)點(diǎn)中拜占庭節(jié)點(diǎn)所占的比例Psv也不同，從而導(dǎo)致節(jié)點(diǎn)共識(shí)失效的概率不同。共識(shí)失效的概率Pfailure如式（15）所示。

根據(jù)式（15）運(yùn)用Python進(jìn)行模擬計(jì)算，當(dāng)分片內(nèi)拜占庭節(jié)點(diǎn)比例Ps在[0.2，0.45]范圍內(nèi)，共識(shí)節(jié)點(diǎn)的數(shù)目在[10，19]范圍內(nèi)，不同共識(shí)節(jié)點(diǎn)數(shù)目導(dǎo)致共識(shí)失效的概率如圖10所示。

根據(jù)圖10可知，共識(shí)失效的概率隨著分片內(nèi)拜占庭節(jié)點(diǎn)比例Ps的增大而增大。而共識(shí)節(jié)點(diǎn)數(shù)量和共識(shí)失效概率存在振蕩的情況。

選取分片內(nèi)拜占庭節(jié)點(diǎn)比例Ps出現(xiàn)概率最高的值0.33，共識(shí)節(jié)點(diǎn)的數(shù)目在{10，19}范圍內(nèi)，不同共識(shí)節(jié)點(diǎn)數(shù)目導(dǎo)致共識(shí)失效的概率如圖11所示。

根據(jù)圖11可得知，隨著共識(shí)節(jié)點(diǎn)數(shù)量的增加，共識(shí)失效的概率呈現(xiàn)總體上升的趨勢，并產(chǎn)生周期長度為3的振蕩，因此Nsv的節(jié)點(diǎn)數(shù)量可按3i+C來選定范圍。其中，C是常數(shù)0、1、2，i取正整數(shù)。

綜上分析，本文將分片內(nèi)共識(shí)節(jié)點(diǎn)數(shù)Nsv取值定為[10，13，16]，在降低通信開銷的同時(shí)，保證了分片內(nèi)PBFT共識(shí)的驗(yàn)證有效性。

3.3 交易驗(yàn)證輪數(shù)的研究

3.3.1 多輪輪數(shù)與驗(yàn)證成功概率的關(guān)系

本方案中設(shè)置一筆交易被驗(yàn)證失敗的次數(shù)高于某一限定值后就放棄該筆交易。對(duì)輪數(shù)上限的設(shè)置關(guān)系到系統(tǒng)整體的性能，若輪數(shù)上限設(shè)置過低，會(huì)導(dǎo)致大量交易被放棄，系統(tǒng)的交易驗(yàn)證率降低。若輪數(shù)上限設(shè)置過高，又會(huì)影響到交易的處理延遲，導(dǎo)致過多交易擁堵，對(duì)系統(tǒng)的負(fù)荷帶來壓力。下面將詳細(xì)分析對(duì)于驗(yàn)證輪數(shù)的設(shè)置。

根據(jù)以上分析，當(dāng)分片內(nèi)拜占庭節(jié)點(diǎn)比例較高時(shí)，共識(shí)失效概率依舊不可忽視，威脅系統(tǒng)的安全性。因此本文通過多輪驗(yàn)證以有限地犧牲交易的可用性，保全系統(tǒng)的性能。多輪驗(yàn)證中，一筆交易進(jìn)行x輪驗(yàn)證直到被驗(yàn)證成功才被打包到區(qū)塊上，用X表示多輪的驗(yàn)證次數(shù)，假設(shè)交易在第x輪被成功驗(yàn)證，則前x-1輪次均驗(yàn)證失敗，那么X近似服從幾何分布，記為X～GE(p)，其中p為驗(yàn)證成功的概率，pfailure表示交易驗(yàn)證失敗的概率，則p=1-pfailure。交易驗(yàn)證成功的概率P如式（16）所示：

根據(jù)公式模擬出分片內(nèi)不同共識(shí)節(jié)點(diǎn)數(shù)下，輪數(shù)x對(duì)交易驗(yàn)證成功率P的影響，如圖12所示。

根據(jù)圖12可以看出，隨著輪數(shù)的加大，一筆交易在k輪內(nèi)被驗(yàn)證成功的概率也在增大。而隨著共識(shí)節(jié)點(diǎn)數(shù)目的增加，交易成功率會(huì)隨之降低，需要更多的輪數(shù)來保證其可用性。

此外，根據(jù)公式模擬出分片內(nèi)不同拜占庭節(jié)點(diǎn)比例，輪數(shù)x對(duì)交易驗(yàn)證成功率P的影響，如圖13所示。

根據(jù)圖13可知，當(dāng)分片內(nèi)拜占庭節(jié)點(diǎn)比例Ps不變時(shí)，隨著交易驗(yàn)證輪數(shù)的增加，交易共識(shí)成功率會(huì)逐漸增大。當(dāng)分片內(nèi)拜占庭節(jié)點(diǎn)比例低于0.3時(shí)，大多數(shù)交易在1到4輪有很大的概率共識(shí)成功。當(dāng)分片內(nèi)拜占庭節(jié)點(diǎn)比例為0.3時(shí)，經(jīng)過4輪驗(yàn)證，交易驗(yàn)證成功的概率就可以達(dá)到99%。當(dāng)分片內(nèi)拜占庭節(jié)點(diǎn)比例為出現(xiàn)概率最高的值0.33時(shí)，在交易驗(yàn)證輪數(shù)為8時(shí)，交易驗(yàn)證成功的概率達(dá)到了99%。當(dāng)交易輪數(shù)達(dá)到14時(shí)，即使在分片內(nèi)拜占庭節(jié)點(diǎn)比例為0.45的情況下，交易驗(yàn)證成功率也達(dá)到了99%。

綜上所述，多輪驗(yàn)證方案相較于傳統(tǒng)的單輪驗(yàn)證方法，交易驗(yàn)證成功率大幅提高，證明多輪方法達(dá)到了以犧牲交易的可用性提升系統(tǒng)性能的目的。

3.3.2 輪數(shù)實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境設(shè)置分片內(nèi)節(jié)點(diǎn)數(shù)Ns為100，每個(gè)節(jié)點(diǎn)完成同步后隨機(jī)對(duì)應(yīng)60～100的通信分值，并給其設(shè)置100分的共識(shí)表現(xiàn)初始值。取分片內(nèi)拜占庭節(jié)點(diǎn)比例Ps出現(xiàn)概率最高的值0.33，共投放10萬筆交易。根據(jù)第3.2節(jié)分析，共識(shí)節(jié)點(diǎn)數(shù)目Nsv取值范圍[10，13，16]。每輪根據(jù)共識(shí)節(jié)點(diǎn)的表現(xiàn)更新其共識(shí)表現(xiàn)分值。通過實(shí)驗(yàn)計(jì)算本文方案中每輪的交易成功率，如表2所示。

表2每輪的共識(shí)成功率Table 2 Success rate of each round

由表2可見，隨著共識(shí)節(jié)點(diǎn)數(shù)的增加，交易驗(yàn)證率減少。當(dāng)Nsv=10時(shí)，第4輪交易驗(yàn)證率就已接近99%。隨著輪數(shù)的加大，交易在k輪內(nèi)被驗(yàn)證成功的概率也在增大。當(dāng)輪數(shù)為6時(shí)，對(duì)一筆交易驗(yàn)證成功的概率達(dá)到了99%，表明系統(tǒng)能以較低的處理延遲確保更高的驗(yàn)證成功率且更快收斂。

此外，在保證最終共識(shí)超時(shí)的概率低于10-7時(shí)，計(jì)算出分片中不同的共識(shí)節(jié)點(diǎn)數(shù)目Nsv下，輪數(shù)T與共識(shí)超時(shí)概率的關(guān)系，如表3所示。

表3共識(shí)超時(shí)Table 3 Consensus timeout

由表3可見，當(dāng)分片失效概率小于10-7時(shí)，此時(shí)的多輪輪數(shù)Tmax=8。本文方案將多輪輪數(shù)上限定為8輪，即對(duì)同一筆交易進(jìn)行8輪共識(shí)驗(yàn)證仍沒得到統(tǒng)一驗(yàn)證結(jié)果，就放棄這筆交易。

3.4 交易驗(yàn)證率對(duì)比實(shí)驗(yàn)

區(qū)塊鏈系統(tǒng)的交易驗(yàn)證率指的是在一段時(shí)間內(nèi)被成功驗(yàn)證交易數(shù)目占總交易數(shù)目的比重，在相同時(shí)間內(nèi)，系統(tǒng)內(nèi)節(jié)點(diǎn)驗(yàn)證的交易數(shù)目越多，則該系統(tǒng)的交易驗(yàn)證率越高，其性能越高。本實(shí)驗(yàn)?zāi)康氖球?yàn)證本文方案可以有效提高系統(tǒng)的交易驗(yàn)證率。

本實(shí)驗(yàn)的研究目標(biāo)是證明本文方案能夠有效地提升系統(tǒng)的交易驗(yàn)證率。設(shè)定總節(jié)點(diǎn)數(shù)目為1 000，分片數(shù)目為10。初始時(shí)將節(jié)點(diǎn)隨機(jī)分配到各分片，統(tǒng)計(jì)各分片的交易驗(yàn)證情況，分別計(jì)算本文方案和MRPV分片方案以及OmniLedger方案中每輪驗(yàn)證完成后各分片的交易驗(yàn)證率。交易驗(yàn)證率對(duì)比結(jié)果如圖14所示。

實(shí)驗(yàn)結(jié)果如圖14，隨著時(shí)隙的增加，三種方案的交易驗(yàn)證率均不斷提升。本文方案與MRPV方案由于采用了多輪驗(yàn)證，通過連續(xù)多輪次的交易驗(yàn)證，對(duì)之前未確認(rèn)的交易重新驗(yàn)證，保證了交易的最終確認(rèn)，最終的交易驗(yàn)證率均趨近100%。而OmniLedger方案由于設(shè)定一筆交易在一次驗(yàn)證失敗后將直接丟棄該筆交易，交易驗(yàn)證率僅可達(dá)到90%。通過對(duì)比分析本文方案和MRPV方案兩種多輪模擬系統(tǒng)，可以看出本文方案在第8輪交易驗(yàn)證率就已達(dá)到99.99%，而MRPV方案的交易驗(yàn)證成功率在第15輪才達(dá)到99.99%。

3.5 交易吞吐量對(duì)比實(shí)驗(yàn)

交易吞吐量代表系統(tǒng)單位時(shí)間內(nèi)處理事務(wù)或交易的能力，是衡量系統(tǒng)性能的重要指標(biāo)，一般用TPS表示系統(tǒng)吞吐量，計(jì)算公式如式（17）所示：

其中，Δt表示一筆交易從發(fā)起到寫入?yún)^(qū)塊的時(shí)間間隔，Transactions表示在Δt時(shí)間內(nèi)寫入?yún)^(qū)塊的交易總數(shù)。為了驗(yàn)證本文方案可以提高算法的吞吐量，在實(shí)驗(yàn)室環(huán)境中，根據(jù)公式計(jì)算本文方案、MRPV分片方案以及OmniLedger三種方案在不同共識(shí)節(jié)點(diǎn)規(guī)模下的TPS。

由圖15可以看出，本文方案的平均TPS優(yōu)于沒有進(jìn)行交易過載處理的MRPV和OmniLedger方案，且在任意拜占庭節(jié)點(diǎn)比例下，這種優(yōu)勢都比較明顯。主要原因有三點(diǎn)：一是本文方案根據(jù)剩余負(fù)載在輪次間競選性能高的節(jié)點(diǎn)進(jìn)行交易過載處理；二是減少單個(gè)分片內(nèi)參與驗(yàn)證的節(jié)點(diǎn)數(shù)量，提高了共識(shí)達(dá)成的速度；三是本文方案能夠通過節(jié)點(diǎn)綜合積分機(jī)制，將拜占庭節(jié)點(diǎn)淘汰，使得拜占庭節(jié)點(diǎn)參與交易驗(yàn)證的機(jī)會(huì)降低，提高系統(tǒng)的穩(wěn)定性以及交易處理的效率。綜上所述，本文方案體現(xiàn)出了更高的平均TPS，能夠滿足更大規(guī)模的系統(tǒng)實(shí)現(xiàn)。

4 總結(jié)

本文針對(duì)區(qū)塊鏈狀態(tài)分片內(nèi)的交易過載問題，提出了一種狀態(tài)分片約束下的多輪節(jié)點(diǎn)競選驗(yàn)證方案。本文方案將分片內(nèi)的交易驗(yàn)證分為多輪，在每輪驗(yàn)證完成后根據(jù)節(jié)點(diǎn)的通信能力和節(jié)點(diǎn)共識(shí)表現(xiàn)進(jìn)行綜合積分核算，并計(jì)算分片內(nèi)的交易負(fù)載，確認(rèn)分片的交易過載情況，進(jìn)而在下一輪驗(yàn)證中增強(qiáng)分片的處理能力；通過利用節(jié)點(diǎn)競選策略對(duì)分片內(nèi)的節(jié)點(diǎn)在不同輪次之間均衡使用，實(shí)現(xiàn)狀態(tài)分片內(nèi)交易過載處理，在犧牲延遲來保證安全性的前提下，提高系統(tǒng)的性能。

通過實(shí)驗(yàn)驗(yàn)證，本文方案提出的狀態(tài)分片多輪節(jié)點(diǎn)任務(wù)競選方案可以有效處理分片內(nèi)交易過載，提升分片內(nèi)的交易驗(yàn)證率，提升整體TPS。但是本文方案存在一定局限性，由于考慮到狀態(tài)分片的約束，節(jié)點(diǎn)不能在分片間隨意調(diào)度。目前實(shí)現(xiàn)了分片內(nèi)部的已有節(jié)點(diǎn)在不同輪次間均衡使用，對(duì)狀態(tài)分片約束下分片間的負(fù)載均衡和信標(biāo)鏈上負(fù)載均衡的實(shí)現(xiàn)還在探索中，可在后續(xù)的研究中改進(jìn)和優(yōu)化。

此外，本文基于大連海事大學(xué)區(qū)塊鏈實(shí)驗(yàn)室團(tuán)隊(duì)成員陳靜、段培培、高冬雪、厚香瑩、王冬雪、馬洪程等同學(xué)的共同基礎(chǔ)研究。