利用狀態(tài)歸約處理跨分片交易的多輪驗證方案①

王冬雪, 李志淮, 陳玉華, 白 兵

(大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院, 大連 116026)

在過去的10 年里, 隨著數(shù)字加密貨幣的普及, 區(qū)塊鏈技術(shù)引起了學(xué)術(shù)界和工業(yè)界的極大關(guān)注. 此后, 區(qū)塊鏈技術(shù)的發(fā)展已經(jīng)超越了加密貨幣的范疇, 支持許多現(xiàn)有的商業(yè)和工業(yè)流程. 此外, 它還能夠創(chuàng)造新的商業(yè)模式, 影響各行各業(yè)如金融、醫(yī)療保健、制造業(yè)和物流[1,2].

區(qū)塊鏈的技術(shù)特點使其有著廣闊的應(yīng)用前景, 但也面臨可擴(kuò)展性不足的瓶頸, 存在擴(kuò)容需求[3,4]. 現(xiàn)有的擴(kuò)容技術(shù)主要包括分片方案[5]、DAG[6]、擴(kuò)塊[7,8]、側(cè)鏈技術(shù)[9]、狀態(tài)通道[10]等. 其中分片方案是目前擴(kuò)容技術(shù)中最為可行的方案, 它利用“分而治之”的思想, 將區(qū)塊鏈的存儲和負(fù)載分散到并行分片上. 目前分片分為網(wǎng)絡(luò)分片、交易分片和狀態(tài)分片, 網(wǎng)絡(luò)分片是將全網(wǎng)節(jié)點劃分到不同分片中, 是交易分片和狀態(tài)分片的基礎(chǔ)[11]; 交易分片是將全網(wǎng)交易劃分到不同的分片中進(jìn)行驗證和打包, 全網(wǎng)多個分片通過并行對交易進(jìn)行驗證和打包可以在一定程度上提升公鏈的性能, 但由于每個分片都存儲全部的賬本信息, 就會造成資源瓶頸等問題; 狀態(tài)分片是將系統(tǒng)的存儲區(qū)域分開, 每個分片只負(fù)責(zé)本分片的數(shù)據(jù), 不用存儲完整的區(qū)塊鏈狀態(tài),緩解了節(jié)點的存儲和處理壓力, 可以有效提升區(qū)塊鏈整體的性能, 可以從本質(zhì)上解決公鏈可擴(kuò)展性的問題,是目前最理想但是難度也最大的分片方案. 在分片方案中, 網(wǎng)絡(luò)中不可避免會存在跨分片交易[12]的問題, 而在狀態(tài)分片中, 又由于各分片只維護(hù)本分片的狀態(tài)信息, 這就使得狀態(tài)分片下的跨分片交易更加的復(fù)雜, 對于跨分片交易的處理是狀態(tài)分片下最大的難題之一.

針對在狀態(tài)分片下處理跨分片交易的難題, 文獻(xiàn)[13] ChainSpace 方案利用智能合約進(jìn)行分片, 通過“SMART’s PBFT”[14]協(xié)議來保證跨分片交易的安全性,但是該論文對交易的假設(shè)是基于樂觀并發(fā)控制, 對于回滾和悲觀并發(fā)并未作出討論. 文獻(xiàn)[15] Omniledger方案中提出利用客戶端驅(qū)動整個過程, 可以避免分片間通信, 避免分片間一致性開銷, 但是加入了客戶端便不能完全保證區(qū)塊鏈系統(tǒng)的安全性, 無法從本質(zhì)上解決狀態(tài)一致性帶來的問題. 文獻(xiàn)[16]提出MRPV 方案,利用多輪驗證的方式提高交易驗證效率, 文獻(xiàn)[17]在MRPV 此基礎(chǔ)上提出了一種解決跨分片交易回滾問題的方案, 但是此方案并未考慮分片狀態(tài), 并且由于輪數(shù)增加還帶來了較高時延問題. 故本文針對以上分析, 提出一種利用狀態(tài)歸約并結(jié)合分片內(nèi)多輪驗證機(jī)制, 來處理跨分片交易的方案SRMR (state reduction and multi-round).

本文貢獻(xiàn)如下: (1) 本文利用狀態(tài)歸約模型, 將跨分片交易轉(zhuǎn)化成一種不跨分片的處理方案, 通過這種轉(zhuǎn)化, 減少驗證跨分片交易的可能性. 但經(jīng)過分析, 推導(dǎo)出完全依賴歸約模型存在上層分片交易負(fù)載過大的問題; (2) 為了防止交易堆積, 提出激勵機(jī)制方案并將狀態(tài)歸約與多輪驗證相結(jié)合, 提出了一種合理平衡歸約與多輪驗證的策略以減輕上層交易負(fù)載量. 此外, 該方案綜合利用節(jié)點的能力, 并通過連續(xù)多輪的驗證, 力?？绶制灰椎捻樌瓿? 降低跨分片交易回滾率;(3)通過公式推導(dǎo)以及實驗驗證, 該方案具有可行性,并可以有效地降低跨分片交易產(chǎn)生的時延問題, 提升系統(tǒng)的性能.

1 問題描述與分析

1.1 問題描述

采用分片技術(shù)解決性能問題, 從宏觀上來講, 并未降低原來的工作量, 而是將原來的工作量分配到了各個分片當(dāng)中, 通過增加原來系統(tǒng)的并行能力來提升整體的性能. 此外, 分片的引入從總工作量上來講, 在原來的基礎(chǔ)上還增加了跨分片交易驗證的工作量. 尤其對于狀態(tài)分片來講, 其最具有挑戰(zhàn)性的問題是跨分片交易的問題, 因特定分片只存儲部分狀態(tài), 而不是完整的區(qū)塊鏈狀態(tài), 這就導(dǎo)致了跨分片交易驗證的復(fù)雜性.為了提高系統(tǒng)運行效率, 不同分片間維護(hù)各自的賬本,分片內(nèi)可以高效地處理交易, 但是對于不同分片之間如何低成本且高效地處理交易, 是目前亟需解決的問題. 甚至考慮一種極端情況: 在系統(tǒng)內(nèi)的交易全部都是跨分片交易的情況下, 分片系統(tǒng)的性能是遠(yuǎn)遠(yuǎn)低于未分片前系統(tǒng)的性能. 現(xiàn)有的解決方案有同步和異步方案, 同步方案存在著難以應(yīng)付連續(xù)狀態(tài)改變的問題, 異步方案存在著自身原子性故障的問題. 因此, 在設(shè)計分片系統(tǒng)的過程中, 一種可行且高效的跨分片驗證和交易處理策略至關(guān)重要.

區(qū)塊鏈中應(yīng)用最廣泛的兩種模型分別是基于賬戶的模型與UTXO (unspent transaction outputs, 未花費的交易輸出) 模型. 基于賬戶的模型雖然具有易用的優(yōu)點, 但是該模型安全性差, 在一個分布式環(huán)境下只有一個地址存儲數(shù)據(jù), 有強(qiáng)一致性的要求, 這就會導(dǎo)致維護(hù)困難, 并且它還存在讀寫臟數(shù)據(jù)的問題, 對于同一個數(shù)據(jù), 同一時刻不同用戶分別在讀和寫, 還會帶來數(shù)據(jù)失效性的問題. 相比較而言, UTXO 模型以交易記錄為中心, 記錄每筆交易以及交易的流通地址, 其并發(fā)度好、安全性高、可溯源, 不存在讀寫臟數(shù)據(jù)的問題, 另外,UTXO 的防攻擊性也比賬戶模型更好. 因此綜合考慮,本文選擇UTXO 模型處理跨分片交易.

在UTXO 模型中, 一筆交易的輸入地址可能來自于不同分片, 在交易驗證時, 驗證者需要驗證每筆輸入尚未被消費, 并確保完成這筆交易后, 所有的輸入都已不可再花費. 對所有交易的輸入均驗證成功后, 可以通過智能合約運算, 輸出到其他分片中, 這就是跨分片交易, 其結(jié)構(gòu)如圖1 所示. 假設(shè)一筆交易Tx有4 個輸入,其中A1 和A2 的輸入地址均映射到分片1,A3 的輸入地址映射到分片2,A4 的輸入地址映射到分片3, 該筆交易向分片n輸出, 在交易驗證時, 需要驗證這3 筆輸入地址映射的分片, 3 個分片驗證成功后, 根據(jù)輸出地址An將交易發(fā)送到分片n中, 處理完成一筆跨分片交易.

1.2 跨分片交易概率分析

在基于UTXO 的模型中, 假設(shè)區(qū)塊鏈系統(tǒng)中分片規(guī)模為n, 一筆交易的輸入數(shù)為m, 根據(jù)分片的隨機(jī)分配算法, 每筆交易的輸入賬戶都是等概率分配在不同分片中, 那么可以得出單個分片間跨分片的概率P如式(1)所示.

根據(jù)公式可以計算在交易輸入數(shù)為m的情況下,跨分片交易P的概率如表1 所示.

由表1 可以看出, 跨分片交易概率隨著分片規(guī)模n和分片個數(shù)m增加而增加, 當(dāng)分片規(guī)模n為4 時, 輸入個數(shù)m大于8, 跨分片概率無限接近1; 當(dāng)分片規(guī)模n為16 時, 輸入個數(shù)m為2 時, 跨分片交易概率已經(jīng)超過93%, 輸入個數(shù)m為16 時, 跨分片交易的概率為1, 必然存在跨分片交易. 由此可見, 在分片系統(tǒng)中, 出現(xiàn)跨分片交易的概率會非常高. 因此如何降低分片間跨分片交易、保證跨分片交易高效處理, 對區(qū)塊鏈系統(tǒng)性能的至關(guān)重要.

表1 輸入數(shù)量對跨分片交易概率的影響

2 利用狀態(tài)歸約處理跨分片交易方案

2.1 狀態(tài)歸約模型與節(jié)點劃分策略

2.1.1 狀態(tài)歸約模型

根據(jù)表1 得出的數(shù)據(jù), 在分片環(huán)境下, 存在跨分片交易的概率非常大, 為了降低跨分片交易的概率, 根據(jù)滿二叉樹結(jié)構(gòu), 本文提出了狀態(tài)歸約模型. 利用狀態(tài)歸約模型解決狀態(tài)分片下跨分片交易驗證的思想是利用狀態(tài)歸約模型將跨分片交易轉(zhuǎn)變成不跨分片交易, 并完成狀態(tài)同步, 狀態(tài)歸約模型如圖2 所示.

圖2 狀態(tài)歸約模型

將分片按照滿二叉樹形式劃分, 滿二叉樹的葉子結(jié)點代表真實存在的分片, 稱為單分片; 非葉子結(jié)點為歸約模型構(gòu)造出的分片, 將其稱為合成分片. 系統(tǒng)中有Si個單分片, 本文Si設(shè)置為16, 分別標(biāo)注為Si1 至Si16.樹的高度是logSi+1, 即高度為5, 那么按照高度由下至上將分片分為0 至4 五個等級.

分片模型構(gòu)造完成后, 將節(jié)點分配到各個單分片中. 節(jié)點根據(jù)自身性能選擇是否同步其兄弟結(jié)點狀態(tài)向上歸約, 節(jié)點向上歸約策略在第2.2.2 節(jié)敘述.

節(jié)點劃分結(jié)束后, 再進(jìn)行交易劃分. 針對跨分片交易輸入地址映射的分片, 將交易向上歸約, 讓上級分片對交易進(jìn)行處理, 如: 輸入地址映射到Si7、Si8 分片,那么將交易最終歸約到C4 分片中驗證; 輸入地址映射到Si1、Si3、Si7 分片, 那么將交易最終歸約到A1 分片中驗證. 除此之外, 更高級別分片內(nèi)的節(jié)點, 除了可以驗證僅在本級別驗證的交易外, 還可以驗證更低級別分片內(nèi)的交易, 例如: 4 級分片內(nèi)的節(jié)點除了擁有驗證該級分片中交易的權(quán)力, 還具有驗證下一級(3 級分片)甚至是單分片(0 級分片)間交易的權(quán)力. 通過這種模型, 就將跨分片交易轉(zhuǎn)換為一種不跨分片交易, 驗證跨分片交易就轉(zhuǎn)換為驗證單個分片內(nèi)交易.

2.1.2 節(jié)點劃分策略

為了在狀態(tài)分片下, 充分利用各個節(jié)點能力, 本文將節(jié)點進(jìn)行劃分. 將節(jié)點集合分成全局待選擇節(jié)點序列、片內(nèi)待同步節(jié)點隊列, 分片內(nèi)已同步節(jié)點隊列和分片內(nèi)驗證節(jié)點集. 節(jié)點劃分如圖3 所示.

圖3 狀態(tài)同步節(jié)點劃分

(1)根據(jù)網(wǎng)絡(luò)中的節(jié)點隨機(jī)分配算法, 將全局待選擇節(jié)點分配到每一個單分片中, 此時, 新加入的節(jié)點處于待同步狀態(tài), 具有網(wǎng)絡(luò)中最小的狀態(tài).

(2)當(dāng)分片內(nèi)待同步節(jié)點隊列中的節(jié)點完成狀態(tài)同步后, 待同步節(jié)點進(jìn)入已同步節(jié)點隊列, 此時, 已同步節(jié)點集具有單分片內(nèi)全部狀態(tài)信息, 并且已同步節(jié)點可以根據(jù)自身性能等因素選擇是否要同步其相鄰的兄弟節(jié)點狀態(tài), 若選擇不同步, 便通過隨機(jī)算法選取部分已同步狀態(tài)節(jié)點作為當(dāng)前分片內(nèi)的驗證節(jié)點, 若選擇同步, 便開始同步其兄弟分片中節(jié)點狀態(tài), 這樣就同時具有該分片及其兄弟節(jié)點的全部節(jié)點狀態(tài), 這種節(jié)點就進(jìn)入下一級別, 即其父結(jié)點之中, 具有更高的狀態(tài)能力, 同理, 在這些更高級別的節(jié)點中, 同樣根據(jù)隨機(jī)算法選取部分節(jié)點作為這一級別的驗證節(jié)點.

(3)當(dāng)驗證節(jié)點完成交易驗證之后, 可以對其利用評分機(jī)制進(jìn)行評分, 得分高的進(jìn)入分片內(nèi)同步節(jié)點隊列中, 得分低的進(jìn)行淘汰, 若得分低的原因并不是有惡意行為, 并且節(jié)點仍愿意繼續(xù)參與驗證, 那么節(jié)點進(jìn)入全局待選擇節(jié)點序列, 若末尾節(jié)點淘汰的原因不是有惡意行為, 但是不愿意繼續(xù)參加驗證, 則將其加入到局外節(jié)點集合, 之后還有機(jī)會繼續(xù)加入全局待選擇節(jié)點序列進(jìn)行驗證, 若淘汰的原因是因為節(jié)點作惡, 那么將節(jié)點加入黑名單, 之后不再參與共識驗證. 通過這樣設(shè)定流程可以避免因長時間不更新驗證節(jié)點, 從而導(dǎo)致部分驗證節(jié)點有機(jī)會作惡, 進(jìn)而驗證失效的問題.

由此可確定, 越上層分片內(nèi)的節(jié)點, 具有越高的狀態(tài)能力, 具有更詳細(xì)的賬本信息, 其中二叉樹根節(jié)點具有網(wǎng)絡(luò)中全部的賬本信息, 也因此將最上層合成分片內(nèi)的節(jié)點稱為全狀態(tài)節(jié)點.

2.2 基于狀態(tài)歸約模型的跨分片概率

首先, 將跨分片交易輸入地址映射的分片進(jìn)行分類,K1={{Si1,Si2}, {Si3,Si4}, {Si5,Si6}, {Si7,Si8},{Si9,Si10}, {Si11,Si12}, {Si13,Si14}, {Si15,Si16}};K2={{C1,C2}, {C3,C4}, {C5,C6}, {C7,C8}};K3={{B1,B2}, {B3,B4}};K4={{A1,A2}}.

根據(jù)狀態(tài)歸約模型, 來計算利用狀態(tài)歸約模型解決跨分片交易問題時, 需要每一層節(jié)點驗證交易的概率. 當(dāng)一筆交易輸入個數(shù)為m(m≥2, 當(dāng)m=1 時不存在跨分片交易), 分片規(guī)模為k, 準(zhǔn)備歸約到l 級分片上, 計算當(dāng)跨分片交易輸入地址映射到K1 集合, 即兩個異或結(jié)果為0x0001 的分片, 交易可歸約到一級分片內(nèi)節(jié)點驗證的概率P(merge-one)如式(2)所示.

當(dāng)跨分片交易輸入地址映射到K2 集合中元素對應(yīng)的分片集, 以A1 狀態(tài)下的分片集合為例, 輸入來自的分片集合為{{Si1,Si3}, {Si1,Si4}, {Si2,Si3}, {Si2,Si4}, {Si1,Si2,Si3}, {Si1,Si2,Si4}, {Si1,Si3,Si4}, {Si2,Si3,Si4}, {Si1,Si2,Si3,Si4}}, 計算交易可歸約到二級節(jié)點驗證的概率P(merge-two) (排除在1 級節(jié)點中可驗證的交易)如式(3)所示.

以此類推, 求跨分片交易歸約的某一級節(jié)點驗證的概率, 便可依次減去上一級歸約的概率. 根據(jù)上述公式計算當(dāng)分片規(guī)模為16, 在不同輸入m情況下, 歸約到1 到4 級合成分片驗證交易的概率P如表2 所示.

表2 在輸入m 不同時, 歸約到各級合成分片驗證的概率

根據(jù)表2 分析可知, 當(dāng)輸入個數(shù)大于等于6 時, 歸約到1、2 級合成分片驗證的概率小于0.1%; 當(dāng)輸入個數(shù)大于等于8, 只能歸約到3 級合成分片驗證的概率小于1%; 當(dāng)輸入個數(shù)大于12, 只能歸約到3 級合成分片驗證的概率小于0.1%; 當(dāng)輸入個數(shù)等于6 時, 只能歸約到4 級合成分片驗證的概率超過96%, 并且隨著m增加, 輸入個數(shù)越多, 只能歸約到3 級節(jié)點驗證的概率越高, 無限趨近于1.

雖然狀態(tài)歸約可以解決跨分片交易的難題, 但是存在一個明顯的缺點是分片級數(shù)越高, 處理交易的量級越大, 便會出現(xiàn)父級分片處理壓力匯集的問題. 通過對表2 的分析, 對跨分片交易的處理大概率都匯集到全狀態(tài)節(jié)點來處理, 對系統(tǒng)來講, 分片的作用變低, 并行度也就變低, 這與分片的“分而治之”背道而馳.

2.3 利用激勵機(jī)制對狀態(tài)歸約模型優(yōu)化方案

為了減輕上級合約分片處理跨分片交易的負(fù)載壓力, 本文提出一種激勵機(jī)制模型, 如圖4 所示.

(1) 我們可以鼓勵用戶不進(jìn)行跨分片交易, 對跨分片的交易收取更高的gas 費用, 這樣用戶就可以盡可能多地進(jìn)行分片內(nèi)交易, 以獲得快速確認(rèn)并支付更少的交易費用.

(2) 對歸約模型的每一級設(shè)置不同的gas 費用. 級別越高, gas 費用越高, 驗證等待時間越低. 用戶可以在歸約模型中選擇在哪一層級的分片上提交交易進(jìn)行驗證.

由于歸約過程中會存在性能方面的損耗, 可以確定, 葉子結(jié)點歸約到上一級父親結(jié)點后, 假設(shè)每個葉子結(jié)點處理事務(wù)的能力為d, 那么其父親結(jié)點處理事務(wù)的能力D將遠(yuǎn)遠(yuǎn)小于2d(D＜＜2d), 令向上歸約結(jié)點損耗集合Q={q,u,v,z}, 則D=(2×每一個葉子結(jié)點能力-Q集合中的元素). 因此可以推導(dǎo)出除0 級結(jié)點外, 每一級父結(jié)點處理事務(wù)的能力D={Q,U,V,Z}={2d-q,2×(2d-q)-u, 4×(2d-q)-2u-v, 8×(2d-q)-4u-2v-z}. 而對于gas 費用的設(shè)置, 根據(jù)級別l, 設(shè)置在每一級分片用戶的價格Price按照Price=2l+1-1 進(jìn)行規(guī)定. 讓用戶支付的每一級別的價格大于上一級價格的2 倍, 但結(jié)點處理事務(wù)的能力卻無法達(dá)到下一級結(jié)點的2 倍. 級別高的分片驗證時延短, 但是用戶提交交易驗證價格高;級別低的分片驗證時延長, 但交易驗證價格低. 通過上述模式, 設(shè)計如圖4 所示的激勵機(jī)制模型, 可以緩解交易在上層分片堆積的問題, 又可以確保每一級分片都有交易驗證處理.

圖4 激勵機(jī)制模型

3 SRMR 方案設(shè)計

通過第2.3 節(jié)激勵機(jī)制模型, 可以讓用戶對于交易提交具有自主選擇權(quán), 可以避免交易都堆積到上層分片處理, 導(dǎo)致上層合成分片交易超過負(fù)載的問題. 如若用戶提交交易所在的分片仍存在跨分片交易, 于是對系統(tǒng)進(jìn)行平衡處理, 從系統(tǒng)負(fù)載能力、共識驗證效率等角度分析這筆交易是否繼續(xù)向上歸約, 如果不繼續(xù)歸約且仍存在跨分片交易, 那么便提出將狀態(tài)歸約結(jié)合多輪共識方案, 通過對跨分片交易進(jìn)行多輪次的驗證, 來提升跨分片交易驗證通過的概率.

3.1 SRMR 方案驗證流程

多輪驗證方案MRPV (multi-round PBFT verification)[16]根據(jù)“分而治之”的原理提出. 多輪驗證方案的主要思想為當(dāng)一筆交易根據(jù)映射規(guī)則被分配到一個既定的分片后, 由此分片中的所有節(jié)點對分片中的交易進(jìn)行PBFT 共識驗證. 如果共識驗證成功, 則將交易打包進(jìn)區(qū)塊. 若出現(xiàn)交易在分片內(nèi)因拜占庭節(jié)點過多使交易驗證超時未能有效驗證交易, 那么對此交易進(jìn)行新一輪共識驗證[16].

多輪共識方案驗證跨分片交易的中心思想是當(dāng)一筆跨分片交易被發(fā)送到多個輸入分片后, 由每個分片獨立進(jìn)行驗證處理, 每個分片內(nèi)交易驗證成功后, 通過智能合約來傳遞信息, 確認(rèn)無誤后打包交易到區(qū)塊.

利用狀態(tài)歸約處理跨分片交易多輪驗證方案SRMR (state reduction and multi-round)思想是當(dāng)用戶提交交易到某一級后, 若仍存在跨分片交易, 這筆跨分片交易會被發(fā)送到對應(yīng)的輸入分片, 在每個分片內(nèi)單獨進(jìn)行多輪驗證. 如圖5 所示, 假設(shè)用戶提交的一筆跨分片交易被發(fā)送到Si1、Si2、Si3 分片中, 通過狀態(tài)歸約模型, 用戶根據(jù)自身選擇將交易提交到1 級合成分片C1 中,C1 分片中有Si1 與Si2 全部的賬本信息, 而C1 與Si3 還處于兩個單獨的分片, 利用多輪共識方案對C1 和Si3 開始獨立進(jìn)行驗證處理.

圖5 用戶提交跨分片交易模型

SRMR 方案具體流程如圖6 所示.

圖6 SRMR 方案流程圖

(1) 分配節(jié)點到網(wǎng)絡(luò). 將網(wǎng)絡(luò)中全局待選擇節(jié)點序列根據(jù)VRF 隨機(jī)分配算法, 隨機(jī)分配到各個分片中,讓每個分片節(jié)點進(jìn)入待同步節(jié)點隊列.

(2) 將節(jié)點進(jìn)行狀態(tài)同步. 在分片內(nèi)的待同步節(jié)點隊列進(jìn)行狀態(tài)同步, 同步完成的節(jié)點再判斷是否繼續(xù)同步兄弟結(jié)點, 最高同步到Lmax級別(Lmax為滿二叉樹的高度). 此時, 整棵二叉樹中, 葉子結(jié)點(單分片)中有待同步節(jié)點和同步節(jié)點, 非葉子結(jié)點(合成分片)中有同步其子結(jié)點狀態(tài)的同步節(jié)點. 以此遞歸, 完成在二叉樹各級分片中節(jié)點的分配.

(3) 分配交易到分片中. 用戶根據(jù)激勵機(jī)制選擇要提交到哪一級分片處理交易, 若提交到那一級別的交易仍存在跨分片交易, 根據(jù)輸入地址映射的分片, 將交易Tx[i]繼續(xù)分配到對應(yīng)的0 級單分片中. 系統(tǒng)根據(jù)整體性能的平衡判斷, 是否進(jìn)行歸約到上一級處理驗證交易, 在二叉樹各級分片中完成交易分配.

(4)多輪共識驗證交易. 各個分片內(nèi)共識節(jié)點對交易集合中的交易進(jìn)行PBFT 共識, 共識成功則將交易打包到區(qū)塊, 若因分片內(nèi)共識節(jié)點中拜占庭節(jié)點比例較高導(dǎo)致共識失效, 那么將驗證交易輪數(shù)round加1, 每進(jìn)行一輪驗證, 需要利用評分機(jī)制對共識節(jié)點進(jìn)行評分, 評分高的節(jié)點可以進(jìn)入該級別的同步節(jié)點隊列, 評分低的根據(jù)末位淘汰的原則分配到全局待選擇節(jié)點中進(jìn)行重新輪換選擇. 若交易驗證次數(shù)超過輪數(shù)上限Rmax還未達(dá)成共識, 那么便放棄這筆交易.

3.2 參與共識節(jié)點驗證概率

在狀態(tài)分片下, 對于驗證跨分片交易需要確定參與共識驗證節(jié)點的個數(shù). 將網(wǎng)絡(luò)中的節(jié)點利用VRF 算法隨機(jī)選取分配到各個分片內(nèi), 設(shè)置網(wǎng)絡(luò)中節(jié)點總數(shù)為N, 網(wǎng)絡(luò)節(jié)點中拜占庭節(jié)點比例為Pn, 選取單一分片內(nèi)節(jié)點數(shù)為Ns, 分片內(nèi)參與共識驗證的節(jié)點數(shù)為Nsv, 令Xi表示分片內(nèi)拜占庭節(jié)點數(shù),Xj表示參與共識驗證節(jié)點中拜占庭節(jié)點的數(shù)量, 分片內(nèi)的節(jié)點分配可認(rèn)為是從網(wǎng)絡(luò)中N個總節(jié)點中選擇Ns個節(jié)點, 令Xi表示選擇的Ns個節(jié)點中拜占庭節(jié)點的數(shù)量, 則Xi服從超幾何分布, 記為Xi～Hi(Ns, N×Pn, N); 共識組內(nèi)的節(jié)點分配可認(rèn)為是從分片內(nèi)Ns個節(jié)點中選擇Nsv個共識節(jié)點, 令Xj表示選擇的Nsv個節(jié)點中拜占庭節(jié)點的數(shù)量, 則Xj同樣服從超幾何分布, 記為Xj～Hj(Nsv, Ns×Ps, Ns). 并且可知, 共識組中拜占庭節(jié)點數(shù)量與分片內(nèi)拜占庭節(jié)點數(shù)量存在依賴條件, 利用二重求和可推導(dǎo)出式(5).

假設(shè)當(dāng)網(wǎng)絡(luò)中節(jié)點總數(shù)N為4 000, 網(wǎng)絡(luò)節(jié)點中拜占庭節(jié)點比例Pn為1/3 時, 分片內(nèi)同步節(jié)點與驗證總數(shù)Nk為2 000, 設(shè)置分片數(shù)Ks為16, 單個分片內(nèi)節(jié)點數(shù)Ns=Nk/Ks, 即Ns選取為125, 根據(jù)式(5), 計算分片內(nèi)參與共識驗證節(jié)點數(shù)Nsv在不同拜占庭比例Ps的情況下導(dǎo)致分片內(nèi)共識失效的概率P(Failure of consensus). 計算結(jié)果如圖7 所示. 可以看出隨著Nsv增加,共識失效概率以3 為周期震蕩型降低,Nsv的節(jié)點數(shù)量可按3i+1 來固定范圍(i取正整數(shù)), 使得共識失效概率最低. 其中由于網(wǎng)絡(luò)中最小帶寬取決于系統(tǒng)中驗證節(jié)點數(shù)量Nsv, 若Nsv設(shè)置過大, 會使網(wǎng)絡(luò)中通信量過大從而造成網(wǎng)絡(luò)負(fù)擔(dān)加重, 若Nsv設(shè)置過小, 雖然通信量較低, 但是容易產(chǎn)生合謀攻擊, 并導(dǎo)致嚴(yán)重的中心化以及安全性問題. 因此, 從通信量和網(wǎng)絡(luò)帶寬的角度考慮,將Nsv設(shè)置在10 到20 之間進(jìn)行計算.Nsv可取值為10、13、16、19, 分片內(nèi)共識失效的概率為0.441、0.448、0.453、0.457.

圖7 在不同共識驗證的節(jié)點數(shù)Nsv 下導(dǎo)致分片共識失效的概率P

3.3 多輪共識方案輪數(shù)選擇

對于一筆跨分片交易, 為了避免合謀攻擊的情況以及在某一時刻單個分片內(nèi)輸入交易不足, 下一時刻輸入交易滿足條件的情況, 在此規(guī)定, 一筆交易驗證通過至少需要2 輪驗證才可通過, 因此將輪數(shù)下限選擇為2.

3.3.1 多輪輪數(shù)上限

對于需要多輪驗證的跨分片交易, 即如圖5 所示的跨分片交易模型, 為了防止對某一分片中的交易連續(xù)進(jìn)行多輪次的驗證仍未通過導(dǎo)致性能損耗, 需要確定輪數(shù)上限Rmax, 即最大共識次數(shù). 根據(jù)第3.2 節(jié)對驗證節(jié)點的選取可知,Nsv的值可為10、13、16、19, 并可計算出對應(yīng)的失效概率P(Failure of consensus). 假定交易在r輪驗證成功, 即r-1 輪驗證失敗, 可以推導(dǎo)交易驗證成功概率P(Success of consensus), 如式(6)所示.

根據(jù)式(6)可計算出在不同拜占庭比例Pn和不同共識驗證節(jié)點Nsv的條件下, 跨分片交易驗證成功的概率大于1-10-8時輪數(shù)上限Rmax. 計算結(jié)果如表3 所示.

表3 在不同Pn 和Nsv 的條件下, 輪數(shù)上限Rmax 的選擇

當(dāng)一筆交易連續(xù)經(jīng)過Rmax輪共識后仍無法驗證成功, 為保證系統(tǒng)整體性能便放棄這筆交易.

3.3.2 歸約輪數(shù)選取

本節(jié)針對于圖6 中判斷是否歸約策略進(jìn)行細(xì)化,計算向上歸約的輪數(shù)下限Rmin.

當(dāng)一筆需要多輪驗證的跨分片交易輸入地址發(fā)送到來自同一父級下相鄰的結(jié)點, 記該集合為Q, 并且在Q集合下這兩個分片下進(jìn)行多輪驗證均經(jīng)過Rmin輪仍未驗證成功, 那么這兩個分片下的交易被判定為有向上一級歸約的能力. 規(guī)定當(dāng)跨分片驗證成功概率大于99%時,Q集合中的分片均未共識成功, 那么Q集合中的分片具有向上歸約的能力. 根據(jù)式(6)計算出在不同拜占庭比例Pn和不同共識驗證節(jié)點Nsv的條件下, 跨分片交易驗證成功的概率大于99.9%時, 符合歸約條件的輪數(shù)下限Rmin. 計算結(jié)果如表4 所示.

表4 在不同Pn 和Nsv 的條件下, 符合歸約條件的輪數(shù)下限

3.4 平衡多輪共識與歸約策略

針對空閑分片中的共識節(jié)點閑置太久, 浪費資源,長時間得不到交易的進(jìn)行驗證, 或者單個分片驗證跨分片交易過多, 導(dǎo)致單個分片負(fù)載過多, 或者單個分片共識節(jié)點不夠, 無法進(jìn)行交易驗證, 導(dǎo)致交易長時間無法驗證, 交易處理時延過長的問題. 根據(jù)狀態(tài)歸約模型處理跨分片交易的多輪共識方案, 提出了判斷該筆驗證的交易是否需要向上繼續(xù)歸約的這個解決方案. 該方案的處理流程圖如圖8 所示.

圖8 歸約處理流程圖

當(dāng)一筆跨分片交易輸入地址被發(fā)送到多個分片后,設(shè)置這筆交易的輸入地址發(fā)送到各個單分片集合TotalSet中, 用戶將這筆跨分片交易提交到某一Grade級分片之后, 若Grade＞0, 則設(shè)置Grade級別下的單分片集合為SingleSet, 若Grade=0, 即用戶提交到單分片中, 那么SingleSet集合為空. 這筆跨分片交易的輸入地址映射到SingleSet集合的分片外的其他單分片, 設(shè)置這個集合為OtherSet,OtherSet=TotalSet-SingleSet. 這樣, 當(dāng)一筆交易Tx[i]被發(fā)送到Grade級分片后, 這筆交易需要滿足以下條件才可進(jìn)行歸約.

(1) 系統(tǒng)開始判斷是否提交到最高等級Lmax, 并且這筆交易驗證的輪次是否大于Rmin, 若不是Lmax級并且該分片內(nèi)驗證的輪數(shù)大于Rmin, 則符合條件. 其中輪數(shù)Rmin的選取規(guī)則如第3.3.2 節(jié)所述, 根據(jù)共識成功概率高于99%計算Rmin值作為可以向上歸約的輪數(shù)下限, 只有驗證輪數(shù)達(dá)到Rmin的取值, 才滿足向上歸約的條件之一.

(2) 判斷OtherSet集合中的是否存在驗證這筆交易的分片的兄弟結(jié)點元素. 判斷這個條件的原因在于,當(dāng)OtherSet集合中的兩個元素是來自同一父級下的兄弟結(jié)點, 才有向上一父級分片歸約判斷的條件, 否則某一父級的分片下, 只有一個孩子結(jié)點, 便無需向上歸約搶占資源, 只需要在單個分片內(nèi)多輪驗證即可.

(3) 判斷向上歸約的上級合成分片中節(jié)點狀態(tài)是否可用. 上級節(jié)點狀態(tài)是否可用的前提在于, 上層同步節(jié)點數(shù)量是否足夠. 在狀態(tài)同步下每個分片可用節(jié)點數(shù)是不一樣的, 因為歸約模型上層節(jié)點不屬于分配型的, 屬于激勵型的, 底層分片中的節(jié)點是否向上歸約是個不確定的情況, 因此可能存在上層分片在某個時刻沒有足夠的有效節(jié)點導(dǎo)致無法工作. 設(shè)合成分片中同步節(jié)點數(shù)量閾值為Nt, 某一合成分片內(nèi)同步節(jié)點數(shù)量可查, 針對閾值Nt的選定, 考慮兩種情況. 首先, 分片內(nèi)共識節(jié)點完成一輪驗證后, 需要進(jìn)行節(jié)點輪換, 通過評分機(jī)制將完成一輪驗證的節(jié)點進(jìn)行打分, 分?jǐn)?shù)低的淘汰, 由于多輪驗證方案要求每一輪都需要輪換掉一個分值低的共識節(jié)點, 那么便需要一個同步節(jié)點被選取為共識節(jié)點, 總共進(jìn)行R輪驗證, 取輪數(shù)上限Rmax(第3.3.1 節(jié)所求), 即首先確?？梢赃_(dá)到Rmax個同步節(jié)點;其次, 最壞的一種情況是, 分片內(nèi)一筆交易共識失敗,那么選取共識節(jié)點Nsv中達(dá)到1/3 評分低的節(jié)點, 將1/3×Nsv個驗證節(jié)點替換掉, 同時需要1/3×Nsv個同步節(jié)點通過隨機(jī)算法選取進(jìn)入分片內(nèi)驗證節(jié)點集, 那么便需要分片內(nèi)同步節(jié)點數(shù)大于1/3×Nsv+C(C＞0, 且C為正整數(shù)). 通過上述策略分析可推導(dǎo)出閾值Nt的公式如式(7)所示. 那么系統(tǒng)判斷, 當(dāng)上層同步節(jié)點數(shù)大于Nt的值后, 并可以向上歸約, 否則拒絕歸約.

(4) 判斷上級分片內(nèi)交易是否到達(dá)分片的負(fù)載. 在以上條件均滿足的情況下, 確定上層的分片的負(fù)載情況, 可通過這一時隙交易完成后, 要向上歸約到分片m中未驗證的交易數(shù)Count(unTxm)來確定該分片負(fù)載情況. 本文假設(shè)每筆交易的大小大致相同, 根據(jù)每一層分片數(shù)Kp, 可以計算出每一層未驗證交易總數(shù)為Count(unTxKp), 從而可推導(dǎo)出在每一層中各個分片負(fù)載均衡時, 單個分片平均未驗證交易數(shù)Avg(unTx), 如式(8)所示. 這樣, 利用這一時隙交易驗證完成后, 各個分片Count(unTxm)與單個分片平均未驗證的交易數(shù)為Avg(unTx) 的比值, 可以計算出分片m的負(fù)載值Shardm. 若Shardm≤1, 說明分片m中的未確認(rèn)交易數(shù)小于等于該層各分片未確認(rèn)交易數(shù)平均值, 那么可以將交易歸約到上層m分片中驗證; 若Shardm＞1, 說明分片m中的未確認(rèn)交易數(shù)大于該層各分片未確認(rèn)交易數(shù)平均值, 那么不可以將交易歸約到上層m分片中驗證, 這筆交易在這一時隙下不具有向上歸約的條件.

4 實驗結(jié)果和分析

為驗證本文提出的利用狀態(tài)歸約模型的多輪驗證方案的可行性, 首先通過對方案本身進(jìn)行時延的計算,按層遞進(jìn), 對比本方案中各個步驟所消耗的時延; 其次,對比MRPV 方案與SRMR 方案對降低跨分片交易回滾概率的影響.

4.1 實驗設(shè)置

為了可以更加高效的對本方案的可行性進(jìn)行分析,首先實驗之前需要對參數(shù)進(jìn)行如下設(shè)置.

(1) 設(shè)置系統(tǒng)中總節(jié)點數(shù)N=4000, 單分片內(nèi)Ns=125,分片數(shù)K=16, 分片內(nèi)參與共識節(jié)點Nsv=19. 根據(jù)第

3.3.1 節(jié)關(guān)于輪數(shù)上限Rmax的分析, 選取跨分片交易驗證成功概率高于1-10-8的輪數(shù)上限Rmax, 以及根據(jù)第

3.3.2 節(jié)關(guān)于符合歸約條件下限Rmin, 選取跨分片交易驗證成功的概率大于99.9%時, 符合歸約條件的輪數(shù)下限Rmin.

(2) 構(gòu)造狀態(tài)歸約模型, 讓1 級合成分片中任意構(gòu)造一個分片同步節(jié)點數(shù)目少于Nt, 另選一個分片讓其負(fù)載值Shardm＞1, 即通過這兩種情況的設(shè)置讓一個分片狀態(tài)不可用, 讓一個分片驗證交易超過負(fù)載, 這兩個分片將不會被系統(tǒng)設(shè)置為可向上歸約的分片. 設(shè)置其他分片均為正?？捎梅制? 同級分片間性能相當(dāng), 越往上級性能越好, 負(fù)載越高, 但負(fù)載差異在分片可控范圍內(nèi).

(3) 對P2P 測試網(wǎng)絡(luò)中的節(jié)點要求通信狀況良好,在有限的延遲內(nèi)接收消息.

實驗選用Linux 作為開發(fā)平臺, 以Go 語言作為開發(fā)語言, 以Goland 和Docker 作為研發(fā)工具, 實驗數(shù)據(jù)利用Python 進(jìn)行繪制.

4.2 時延測試

交易時延是指一筆交易從發(fā)送到區(qū)塊鏈網(wǎng)絡(luò), 到被系統(tǒng)中共識節(jié)點確認(rèn)的時間. 處理交易的時延是確定區(qū)塊鏈系統(tǒng)性能好壞的一個重要指標(biāo), 較低的時延可以讓交易得到更快的確認(rèn). 設(shè)置一筆跨分片交易, 讓其根據(jù)輸入地址映射到各個分片中.

本次實驗通過設(shè)置3 個方案進(jìn)行對比, 分別是方案1: 只在單分片內(nèi)多輪驗證、方案2: 結(jié)合歸約模型進(jìn)行多輪驗證(未結(jié)合平衡多輪共識與歸約策略)、方案3: SRMR (結(jié)合平衡多輪共識與歸約策略). 實驗測試了在拜占庭比例Pn=1/4 的情況下, 跨分片交易涉及2、4、6、8、10、12、14、16 個輸入對象映射的分片數(shù)目下的8 組對照實驗. 實驗結(jié)果如圖9 所示, 根據(jù)運行結(jié)果分析, 隨著映射的分片數(shù)目越多, 這3 種驗證情況的時延都會增加, 但是結(jié)合歸約模型多輪驗證方案的時延明顯低于單分片多輪驗證方案, 并且SRMR 方案比僅結(jié)合歸約模型多輪驗證方案還低一些.

圖9 不同方案下跨分片交易時延對比

分析方案一增長速度逐漸加快的原因在于, 當(dāng)交易只在單分片內(nèi)進(jìn)行多輪驗證, 很大程度存在著某一個分片驗證輪次較高, 其他分片內(nèi)交易等待導(dǎo)致時延突增; 在分片數(shù)目為2-8 之間, 方案2、3 差距不大的原因在于, 分片數(shù)目小于8 的情況下, 系統(tǒng)判定向上歸約的可能性不大, 不符合向上歸約的要求; 分片數(shù)為16 時, 方案2、3 差距不大的原因在于, 默認(rèn)用戶對于這筆交易提交到了最高等級, 即系統(tǒng)判定不需要向上歸約, 產(chǎn)生時延的主要原因在于對交易進(jìn)行多輪驗證以及最高層分片負(fù)載較大, 交易驗證需要等待較長時間導(dǎo)致的.

4.3 跨分片交易回滾概率測試

跨分片交易回滾是指, 某一輸入對象映射的分片內(nèi)的交易被驗證為無效, 那么該筆交易其他分片已鎖定的資源也必須回滾, 保證后續(xù)交易可正常使用.

本實驗設(shè)置兩個方案對比, 分別是MRPV 方案與SRMR 方案. MRPV 方案未區(qū)分節(jié)點能力, 即MRPV方案中分片內(nèi)節(jié)點數(shù)均為驗證節(jié)點數(shù), 因此根據(jù)本文SRMR 設(shè)置對比實驗時, 設(shè)置MRPV 方案中節(jié)點數(shù)為125 (即與SRMR 方案中分片內(nèi)節(jié)點數(shù)Ns相同), 對比在拜占庭比例Pn=1/4 的情況下, 當(dāng)不同輸入對象映射到不同分片數(shù)時, 交易到達(dá)驗證最高輪數(shù)Rmax后仍存在回滾概率的情況. 實驗結(jié)果如圖10 所示. 根據(jù)結(jié)果顯示, MRPV 隨著輸入分片數(shù)目增多, 跨分片概率逐漸增加, SRMR 方案隨著輸入分片數(shù)量增加跨分片回滾概率明顯低于MRPV 分案, 甚至跨分片回滾概率逐漸趨于平穩(wěn).

圖10 不同方案下跨分片交易回滾概率對比

對上述運行結(jié)果進(jìn)行分析, 由于SRMR 方案相較于MRPV 方案, 在同一輸入分片數(shù)目的情況下, 在一定程度上通過歸約模型減少了實際驗證跨分片交易輸入分片數(shù)量, 并且越向上層歸約的節(jié)點性能越好, 驗證通過的概率甚至更大.

兩種實驗方案表明, SRMR 方案利用歸約模型, 綜合利用節(jié)點能力進(jìn)行多輪驗證, 不但可以有效降低時延, 還對多輪進(jìn)行優(yōu)化, 進(jìn)一步降低了跨分片交易的回滾概率, 保證了系統(tǒng)可行性, 改善了系統(tǒng)的性能.

5 總結(jié)與展望

本文針對狀態(tài)分片下處理跨分片交易的難題, 提出了一種利用狀態(tài)歸約處理跨分片交易的多輪驗證方案SRMR, 本方案通過歸約模型, 利用滿二叉樹的結(jié)構(gòu),將分片內(nèi)的節(jié)點根據(jù)自身性能選擇是否向上歸約, 并分析在此模型下各層處理跨分片交易的概率; 隨后, 本文分析出僅用歸約模型的方案所產(chǎn)生的弊端, 并提出一種結(jié)合了激勵機(jī)制和多輪驗證的歸約模型方案, 均衡了上層交易負(fù)載的問題, 最后推算出輪數(shù)的合理取值, 并提出了一種合理平衡歸約與多輪驗證的策略. 在該模型中, 我們綜合利用節(jié)點的能力, 在降低了時延的同時, 進(jìn)一步降低了跨分片交易回滾率. 本文對于后續(xù)針對跨分片交易的研究有一定的參考價值, 接下來的工作是利用SRMR 方案, 可以繼續(xù)針對狀態(tài)分片下抗合謀攻擊問題作出進(jìn)一步研究, 此外, 本文未探索交易打包上鏈的方式, 可以后續(xù)對SRMR 方案的打包上鏈方式進(jìn)行探究.