李寶瑩，李志淮，王成愛，楊鋒

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

0 引言

自從2008 年中本聰發(fā)布比特幣白皮書［1］以來，越來越多的研究者開始關(guān)注比特幣背后的區(qū)塊鏈技術(shù)。然而，隨著區(qū)塊鏈網(wǎng)絡(luò)中交易數(shù)量的增多與去中心化應(yīng)用的發(fā)展，區(qū)塊鏈出現(xiàn)了嚴(yán)重的性能瓶頸，已無法滿足實(shí)際應(yīng)用的需求。擴(kuò)容是區(qū)塊鏈的核心任務(wù)和前沿技術(shù)難題。研究者們提出了許多擴(kuò)容方案，例如，擴(kuò)塊［2］、有向無環(huán)圖（DAG）［3-5］、分片［6-7］、側(cè)鏈［8］、狀態(tài)通道［9］等，其中分片是目前最可能實(shí)現(xiàn)區(qū)塊鏈擴(kuò)容的技術(shù)之一，狀態(tài)分片能夠從本質(zhì)上解決公鏈的可擴(kuò)展性問題。在狀態(tài)分片的情況下，由于每個(gè)分片只保留了狀態(tài)的一部分，因此一旦一個(gè)新節(jié)點(diǎn)加入一個(gè)分片中，系統(tǒng)就必須確保該節(jié)點(diǎn)有足夠的時(shí)間進(jìn)行分片狀態(tài)的同步，否則新節(jié)點(diǎn)將無法參與交易的驗(yàn)證。

分片方案通常被視為安全地適應(yīng)開放網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)變化的可持續(xù)擴(kuò)展方案，但現(xiàn)有分片方案大多預(yù)先設(shè)定了分片規(guī)模。公鏈處于一個(gè)開放低門檻的分布式環(huán)境中，網(wǎng)絡(luò)中的節(jié)點(diǎn)狀態(tài)和規(guī)模隨時(shí)會(huì)發(fā)生變化，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量在短時(shí)間內(nèi)發(fā)生較大變化時(shí)，現(xiàn)有利用時(shí)間片在分片內(nèi)更新節(jié)點(diǎn)的方式將相對(duì)滯后，并且不適用于節(jié)點(diǎn)數(shù)量明顯波動(dòng)的情況。一方面，預(yù)先設(shè)定分片的規(guī)模只是為了暫時(shí)的方便，偏離了更多的節(jié)點(diǎn)提供更高性能的設(shè)計(jì)目的，同時(shí)也會(huì)使網(wǎng)絡(luò)在短時(shí)間內(nèi)面對(duì)更多節(jié)點(diǎn)時(shí)無法及時(shí)發(fā)揮節(jié)點(diǎn)性能，從而導(dǎo)致網(wǎng)絡(luò)無法充分利用節(jié)點(diǎn)資源。另一方面，在區(qū)塊鏈網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)在短時(shí)間內(nèi)大幅減少的情況下，預(yù)先設(shè)定分片規(guī)模也會(huì)增加分片內(nèi)的安全隱患。除此之外，預(yù)先設(shè)定分片規(guī)模的靜態(tài)分片方案未來即使需要擴(kuò)大分片規(guī)模，也只能采用時(shí)延較長、成本較高的硬分叉方式，這使得系統(tǒng)更新更困難、代價(jià)更大、速度更慢。

在分片后要面臨的是安全性降低的問題：分片后單個(gè)分片內(nèi)節(jié)點(diǎn)數(shù)量遠(yuǎn)低于分片前整個(gè)區(qū)塊鏈網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量，導(dǎo)致攻擊者對(duì)單個(gè)分片發(fā)起攻擊的成本極大降低。假設(shè)系統(tǒng)包含S個(gè)分片，在節(jié)點(diǎn)被均勻地分配到各個(gè)分片的情況下，每個(gè)分片的安全性變?yōu)樵日麠l鏈的1/S。若分片前后區(qū)塊鏈都采用工作量證明（POW）共識(shí)（假設(shè)各個(gè)節(jié)點(diǎn)的算力相當(dāng)），則分片前攻擊者需要控制超過50%的節(jié)點(diǎn)才能發(fā)動(dòng)51%攻擊，而分片后攻擊者若想攻擊單個(gè)分片，則只需要控制分片內(nèi)超過50%/S的節(jié)點(diǎn)。

在網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)一定的情況下，擴(kuò)展分片的數(shù)量意味著分片內(nèi)節(jié)點(diǎn)數(shù)的減少，也意味著攻擊者攻擊單個(gè)分片的代價(jià)更小，分片的安全性被削弱。因此，從安全方面而言，分片內(nèi)要有足夠的節(jié)點(diǎn)來保證安全性和去中心化，分片的節(jié)點(diǎn)數(shù)應(yīng)該有一個(gè)最小值，即下限閾值。當(dāng)分片的節(jié)點(diǎn)數(shù)低于下限閾值時(shí)，此時(shí)的分片不滿足基本安全要求，節(jié)點(diǎn)數(shù)量需要增加，給分片補(bǔ)充節(jié)點(diǎn)。但由于在狀態(tài)分片下，補(bǔ)充新的節(jié)點(diǎn)存在同步分片狀態(tài)的滯后問題，因此應(yīng)采取縮減分片規(guī)模的方式來確保分片的節(jié)點(diǎn)數(shù)不低于下限閾值。

在滿足基本的安全要求后，若分片的節(jié)點(diǎn)數(shù)過多，則會(huì)影響網(wǎng)絡(luò)的吞吐量。在網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)一定的情況下，增加分片內(nèi)的節(jié)點(diǎn)數(shù)而減少分片的數(shù)量會(huì)使整個(gè)網(wǎng)絡(luò)的并行度降低，進(jìn)而影響網(wǎng)絡(luò)的吞吐量。同時(shí)，若分片內(nèi)的節(jié)點(diǎn)過多，則會(huì)增加節(jié)點(diǎn)間的通信開銷，節(jié)點(diǎn)需要存儲(chǔ)和維護(hù)的區(qū)塊信息和狀態(tài)數(shù)據(jù)也會(huì)隨之增多，而通信量的增大也會(huì)對(duì)網(wǎng)絡(luò)帶寬造成影響。因此，分片的節(jié)點(diǎn)數(shù)也應(yīng)該有一個(gè)最大值，即上限閾值。當(dāng)分片節(jié)點(diǎn)數(shù)高于上限閾值時(shí)，此時(shí)的分片可以通過向外擴(kuò)展以提高吞吐能力。

本文建立基于狀態(tài)歸約的自適應(yīng)節(jié)點(diǎn)規(guī)模的動(dòng)態(tài)分片可擴(kuò)展模型（DSSM），旨在使分片規(guī)模能夠自適應(yīng)節(jié)點(diǎn)環(huán)境并且動(dòng)態(tài)可擴(kuò)展，同時(shí)不削弱去中心化程度和安全性。設(shè)計(jì)基于可驗(yàn)證延遲函數(shù)（VDF）+可驗(yàn)證隨機(jī)函數(shù)（VRF）的節(jié)點(diǎn)隨機(jī)數(shù)生成算法，可以對(duì)抗Sybil 攻擊以及避免可能存在的惡意節(jié)點(diǎn)相互串通、提前計(jì)算符合它們要求的隨機(jī)數(shù)的情況。

1 相關(guān)工作

1.1 符號(hào)與定義

本節(jié)簡要介紹了使用的相關(guān)符號(hào)及定義，如表1所示。

表1 符號(hào)及定義Table 1 Symbols and definitions

1.2 安全的去中心化隨機(jī)數(shù)生成器

1.2.1 可驗(yàn)證隨機(jī)函數(shù)

VRF 是一種將輸入映射為可驗(yàn)證的偽隨機(jī)輸出的加密函數(shù)［10］，已被廣泛應(yīng)用于Algorand［11］、本體的VBFT 算法等 加密場 景，一般由Keygen、Evaluate、Verify 算法組成。

對(duì)于相同的密鑰對(duì)以及輸入X，VRF 只會(huì)產(chǎn)生唯一的偽隨機(jī)字符串Y和證明ρ。因此，VRF 滿足以下性質(zhì)：1）偽隨機(jī)性，對(duì)于不知道證明ρ的第三方而言，它看起來輸出值是隨機(jī)的；2）可驗(yàn)證性，輸出結(jié)果能夠被驗(yàn)證；3）唯一性，輸出的隨機(jī)值是唯一的，具有不可偽造或抵賴性，不可能通過給定的密鑰對(duì)（VK，SK）和消息X產(chǎn)生不同的輸出Y和證明ρ。

1.2.2 可驗(yàn)證延遲函數(shù)

VDF 是一類數(shù)學(xué)函數(shù)［12］，即使在同時(shí)使用不同CPU 并行計(jì)算的情況下計(jì)算出結(jié)果也至少需要一段已知的時(shí)間，一般由Setup、Eval和Verify算法組成。

VDF 滿足以下性質(zhì)：1）驗(yàn)證高效；2）唯一性，對(duì)于任意一個(gè)VDF 的輸入，應(yīng)有唯一的輸出結(jié)果能夠通過檢驗(yàn)；3）串行性，攻擊者即使擁有很多算力，能夠并行計(jì)算，但是其以少于某個(gè)固定時(shí)間計(jì)算出VDF 結(jié)果的概率小到可忽略不計(jì)。

1.3 其他區(qū)塊鏈分片方案

1.3.1 以太坊

2022 年9 月，以太坊進(jìn)行了合并，實(shí)現(xiàn)了從POW 到權(quán)益證明（POS）的過渡。同時(shí)，以太坊官方明確了擴(kuò)展以太坊性能的方向，即放棄最初的分片方案，啟動(dòng)以Rollup 為中心的擴(kuò)容方案，也就是Danksharding［13］。

Danksharding 的主要特點(diǎn)包括：1）Blob 數(shù)據(jù)分片傳輸；2）數(shù)據(jù)可用性抽樣實(shí)現(xiàn)區(qū)塊驗(yàn)證；3）區(qū)塊提議者與構(gòu)建者分離（PBS）。

1.3.2 Monoxide

Monoxide［14］的主要思想是通過異步共識(shí)組來實(shí)現(xiàn)公鏈擴(kuò)容，主要特點(diǎn)包括：1）將區(qū)塊鏈網(wǎng)絡(luò)劃分為多個(gè)獨(dú)立和并行的Zone；2）高效處理跨越不同Zone的交易；3）通過“連弩挖礦”的方式解決分組后挖礦算力稀釋的問題。

Monoxide 在完全去中心化的前提下實(shí)現(xiàn)了全方位的分片，保證了可以正確高效地完成其上的跨分片交易，并保證了攻擊單個(gè)共識(shí)組的代價(jià)與攻擊整個(gè)網(wǎng)絡(luò)的代價(jià)相當(dāng)。

1.3.3 NEAR

NEAR［15］將系統(tǒng)建模成一個(gè)單獨(dú)的區(qū)塊鏈，其中每個(gè)塊邏輯上包含所有分片的全部交易以及改變所有分片的整個(gè)狀態(tài)。然而，在物理上任何參與者都不會(huì)下載完整的狀態(tài)或完整的邏輯區(qū)塊，網(wǎng)絡(luò)的每個(gè)參與者只是維護(hù)為之驗(yàn)證交易的分片上對(duì)應(yīng)的狀態(tài)，區(qū)塊中的所有交易的列表被分割成物理上的段，一個(gè)分片為一個(gè)段。

1.4 多輪驗(yàn)證思想與狀態(tài)分片基礎(chǔ)上的共識(shí)組

實(shí)用拜占庭容錯(cuò)（PBFT）［16］算法具有“即時(shí)敲定”的特性，即被PBFT 共識(shí)驗(yàn)證通過并上鏈的交易會(huì)被永久確認(rèn)，沒有被篡改的可能性，這使得它天然具有避免分叉的特性。然而，PBFT 只有1/3 的拜占庭容錯(cuò)率，這就使得它的實(shí)際應(yīng)用會(huì)受到很多限制。

針對(duì)在分片內(nèi)使用PBFT 共識(shí)所面臨的因拜占庭節(jié)點(diǎn)比例超過1/3 而導(dǎo)致共識(shí)失敗的問題，研究者們提出了多輪驗(yàn)證的思想。多輪驗(yàn)證的主要思路為：若交易驗(yàn)證失敗，則不是立刻丟棄該交易，而是更新分片內(nèi)的節(jié)點(diǎn)，對(duì)交易進(jìn)行新一輪驗(yàn)證，以此類推，直到交易驗(yàn)證成功或者達(dá)到驗(yàn)證輪數(shù)上限而放棄該交易。

然而，普通的多輪驗(yàn)證方案對(duì)于交易驗(yàn)證采用的是分片內(nèi)的全部節(jié)點(diǎn)均參與的方式。這會(huì)帶來一些問題：PBFT 的通信復(fù)雜度是O（n2）級(jí)別，若是分片內(nèi)全部節(jié)點(diǎn)均參與PBFT 共識(shí)，則會(huì)引起通信量過大的問題。另外，每輪都更新分片內(nèi)的節(jié)點(diǎn)，會(huì)造成許多額外開銷。

針對(duì)以上問題，研究者們提出分片共識(shí)組［17］的概念，其主要思想是篩選分片內(nèi)的部分節(jié)點(diǎn)，構(gòu)建共識(shí)組對(duì)交易進(jìn)行驗(yàn)證，這能有效降低通信開銷，同時(shí)啟用積分機(jī)制對(duì)節(jié)點(diǎn)表現(xiàn)進(jìn)行評(píng)價(jià)，從而能夠高效甄別拜占庭節(jié)點(diǎn)，提高了系統(tǒng)安全性。

1.5 動(dòng)態(tài)分片

自適應(yīng)節(jié)點(diǎn)規(guī)模的區(qū)塊鏈分片可擴(kuò)展模型是動(dòng)態(tài)分片技術(shù)的優(yōu)化研究。針對(duì)傳統(tǒng)分片預(yù)先設(shè)定分片規(guī)模的靜態(tài)分片方式的局限性：文獻(xiàn)［18］提出一種在聯(lián)盟鏈中的基于隨機(jī)值的動(dòng)態(tài)分片協(xié)議，在聯(lián)盟鏈中降低了靜態(tài)分片的安全風(fēng)險(xiǎn)，但并未給出具體的應(yīng)用場景；文獻(xiàn)［19］提出一種基于深度強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)分片區(qū)塊鏈框架，采用深度強(qiáng)化學(xué)習(xí)來調(diào)整分片策略，以解決節(jié)點(diǎn)加入、退出、惡意攻擊等動(dòng)態(tài)環(huán)境下的問題；文獻(xiàn)［20］為了解決跨分片交易問題提出一種方案，首先在劃分分片時(shí)考慮其數(shù)據(jù)相關(guān)性以減少跨分片交易的概率，然后通過考慮分片的利用率進(jìn)行合并和分割，并通過選舉領(lǐng)導(dǎo)者來減少共識(shí)延遲；文獻(xiàn)［21］通過動(dòng)態(tài)分片減少各個(gè)節(jié)點(diǎn)存儲(chǔ)的舊區(qū)塊副本來減少存儲(chǔ)負(fù)載，但并未規(guī)定節(jié)點(diǎn)間或者分片間的通信規(guī)則，在驗(yàn)證交易時(shí)如果需要的數(shù)據(jù)不在本地，則需要從其他節(jié)點(diǎn)處獲取，這就存在數(shù)據(jù)一致性問題。

2 環(huán)境假設(shè)

2.1 網(wǎng)絡(luò)模型

對(duì)于底層網(wǎng)絡(luò)，假設(shè)與其他方案一致［22-24］，并假設(shè)：1）誠實(shí)節(jié)點(diǎn)的網(wǎng)絡(luò)是良好連接的；2）誠實(shí)節(jié)點(diǎn)的通信通道是同步的，即一個(gè)誠實(shí)節(jié)點(diǎn)廣播一個(gè)消息，那么所有節(jié)點(diǎn)都能在一個(gè)已知的最大延遲?［25］內(nèi)接收該消息。

2.2 威脅模型

網(wǎng)絡(luò)中存在誠實(shí)和拜占庭兩種節(jié)點(diǎn)。假設(shè)網(wǎng)絡(luò)中拜占庭節(jié)點(diǎn)的比例f≤1/3，也就是網(wǎng)絡(luò)中最多有1/3的驗(yàn)證者可能是惡意的。誠實(shí)節(jié)點(diǎn)遵守所有協(xié)議，惡意節(jié)點(diǎn)可以進(jìn)行任意操作，它們可以以任意方式違反協(xié)議，如拒絕發(fā)送、篡改和偽造消息等。它們之間還可能相互串通來共同作惡。假設(shè)拜占庭對(duì)手是慢適應(yīng)的，即拜占庭節(jié)點(diǎn)和誠實(shí)節(jié)點(diǎn)的集合在每個(gè)時(shí)隙內(nèi)都是固定的，只有在不同的時(shí)隙之間才能變化。

3 DSSM 模型

針對(duì)傳統(tǒng)分片方案預(yù)定分片規(guī)模的靜態(tài)分片方式產(chǎn)生的性能缺陷與安全隱患，本文力圖實(shí)現(xiàn)一種樹型分層的自適應(yīng)節(jié)點(diǎn)規(guī)模的分片可擴(kuò)展模型，以提高分片區(qū)塊鏈系統(tǒng)在向外擴(kuò)展時(shí)的魯棒性與自適應(yīng)性。

3.1 狀態(tài)歸約思想

傳統(tǒng)分片方案中分片內(nèi)的節(jié)點(diǎn)只會(huì)維護(hù)本分片的狀態(tài)，而狀態(tài)歸約思想鼓勵(lì)高性能的節(jié)點(diǎn)同步其他分片的狀態(tài)。當(dāng)某個(gè)節(jié)點(diǎn)具有兩個(gè)及以上的分片狀態(tài)時(shí)，它就成了歸約節(jié)點(diǎn)。狀態(tài)同步且具有相同分片（至少兩個(gè)）狀態(tài)的節(jié)點(diǎn)集合構(gòu)成了新的分片，稱為歸約分片。歸約分片與被同步狀態(tài)的分片之間構(gòu)成了樹結(jié)構(gòu)，如圖1 所示。

圖1 分片間的邏輯關(guān)系Fig.1 Logical relationship between shards

根據(jù)狀態(tài)歸約思想，處于父節(jié)點(diǎn)位置的分片（父級(jí)分片）中的節(jié)點(diǎn)將會(huì)存儲(chǔ)處于其孩子節(jié)點(diǎn)位置的分片（子分片）的所有狀態(tài)信息。在圖1 中，分片A處于分片B 與分片C 的父節(jié)點(diǎn)的位置上，分片B 和C分別處于兩個(gè)孩子節(jié)點(diǎn)的位置上。分片B 和C 中的白色節(jié)點(diǎn)分別同步了其兄弟分片的狀態(tài)而成了歸約節(jié)點(diǎn)，這兩部分白色節(jié)點(diǎn)同時(shí)具有分片B 和C 的狀態(tài)，它們共同組成了歸約分片A。對(duì)于分片B 和C 中的白色節(jié)點(diǎn)，它們的邏輯級(jí)別屬于分片A 這一級(jí)別。

3.2 DSSM 模型構(gòu)建

在DSSM 中分片可以分為兩種：一種是基礎(chǔ)分片，它們是物理上的實(shí)際分片，與其他方案中的分片相似，每個(gè)基礎(chǔ)分片獨(dú)立驗(yàn)證分片的事務(wù)；另一種是邏輯分片，又稱為歸約分片，它們是邏輯上的分片，不是實(shí)際的分片。在歸約分片中的節(jié)點(diǎn)，要在分片的動(dòng)態(tài)調(diào)整中發(fā)揮作用，例如為節(jié)點(diǎn)的狀態(tài)同步提供相應(yīng)數(shù)據(jù)、在分片動(dòng)態(tài)調(diào)整過程中傳遞相應(yīng)的消息等。

DSSM 模型使用分片歸約樹這樣的邏輯結(jié)構(gòu)來控制分片的動(dòng)態(tài)擴(kuò)展。分片歸約樹是一個(gè)二叉樹的結(jié)構(gòu)，如圖2 所示（彩色效果見《計(jì)算機(jī)工程》官網(wǎng)HTML 版），其中每個(gè)葉子節(jié)點(diǎn)代表的是一個(gè)基礎(chǔ)分片，而處于非葉子節(jié)點(diǎn)位置上的節(jié)點(diǎn)是邏輯分片（歸約分片），它們維護(hù)孩子節(jié)點(diǎn)所對(duì)應(yīng)分片的所有狀態(tài)，并在分片動(dòng)態(tài)調(diào)整時(shí)保證分片狀態(tài)的平穩(wěn)過渡。

圖2 DSSM 歸約模型Fig.2 Reduction model of DSSM

DSSM 考慮到節(jié)點(diǎn)的性能存在差異，因此通過激勵(lì)機(jī)制，鼓勵(lì)高性能的節(jié)點(diǎn)盡可能地同步兄弟分片的狀態(tài)，成為上層歸約分片中的節(jié)點(diǎn)，從而使得在分片動(dòng)態(tài)調(diào)整時(shí)，相應(yīng)的狀態(tài)信息不會(huì)丟失，分片也不至于因?yàn)闋顟B(tài)信息的不一致而導(dǎo)致癱瘓。

在整個(gè)網(wǎng)絡(luò)中，性能較好的節(jié)點(diǎn)處于DSSM 模型較上層位置，性能較差的節(jié)點(diǎn)處于DSSM 模型較下層位置。DSSM 還有一個(gè)基本原則就是所有歸約分片中的節(jié)點(diǎn)即使邏輯級(jí)別和狀態(tài)存儲(chǔ)各有不同，但在物理上它們都處于各自的基礎(chǔ)分片中，它們?nèi)匀恍枰袚?dān)所屬基礎(chǔ)分片的交易驗(yàn)證任務(wù)，這符合性能越好需要承擔(dān)的任務(wù)越多的設(shè)計(jì)理念。這樣的設(shè)計(jì)能夠較為充分地發(fā)揮節(jié)點(diǎn)的性能，從而提高整個(gè)區(qū)塊鏈網(wǎng)絡(luò)的性能。

3.3 DSSM 消息傳遞規(guī)則

由于DSSM 所有節(jié)點(diǎn)實(shí)際上都處于基礎(chǔ)分片中，節(jié)點(diǎn)同步更多的狀態(tài)只是為了在分片的動(dòng)態(tài)調(diào)整中發(fā)揮更多的作用。歸約分片并不是真分片，是邏輯上的分片，是虛分片。同時(shí)，為了動(dòng)態(tài)擴(kuò)展的需要，每個(gè)基礎(chǔ)分片中也必然存在這樣的節(jié)點(diǎn)，它們處于各級(jí)的祖先分片中。

在DSSM 中的消息傳遞規(guī)則是所有的消息都在本分片內(nèi)傳遞，這里的本分片既包括物理上的實(shí)際分片，也包括邏輯上的虛分片。

以圖3 為例，假設(shè)節(jié)點(diǎn)4 在分片C 中廣播消息，那么節(jié)點(diǎn)1、2 和3 就可以接收到消息，并分別將消息在分片Root、A 和B 中廣播。此時(shí)，消息在分片C 內(nèi)部廣播的同時(shí)，也將近乎并行地在分片Root、A 和B中廣播。同樣地，節(jié)點(diǎn)7、10 和13 也會(huì)因?yàn)榉制琑oot、A 和B 中的消息廣播而捕獲此消息，那么分片E、D 和F 也會(huì)接收到此消息。以此類推，父級(jí)分片的節(jié)點(diǎn)在廣播消息的同時(shí)，其子分片的節(jié)點(diǎn)也在近乎并行地廣播消息。因此，當(dāng)某一節(jié)點(diǎn)在自己的分片中廣播消息時(shí)，全網(wǎng)的所有分片（包括基礎(chǔ)分片和歸約分片）也在近乎并行地廣播消息，這大大提高了消息的傳遞效率。

圖3 消息傳遞規(guī)則Fig.3 Messaging rules

4 DSSM 分片自適應(yīng)擴(kuò)展設(shè)計(jì)

DSSM 實(shí)行狀態(tài)分片，并以存儲(chǔ)狀態(tài)為依據(jù)將節(jié)點(diǎn)進(jìn)行邏輯分層。

4.1 歸約樹邏輯結(jié)構(gòu)初始化

一般地，為了更好地兼容未實(shí)施分片的區(qū)塊鏈系統(tǒng)，DSSM 的分片初始化由單個(gè)分片（稱為根分片Root）開始。未分片的區(qū)塊鏈網(wǎng)絡(luò)可以視為網(wǎng)絡(luò)中只有單個(gè)分片。

1）當(dāng)Roo（t對(duì)于未實(shí)施分片的區(qū)塊鏈，Root 包括其所有節(jié)點(diǎn)）中的節(jié)點(diǎn)數(shù)超過上限閾值O時(shí)，便可以開始分片的分裂。

2）由于存在分片分裂之后產(chǎn)生的兩個(gè)子分片的節(jié)點(diǎn)數(shù)依然超過上限閾值O的情況，因此每次分裂后形成的子分片的節(jié)點(diǎn)繼續(xù)按照步驟1）中的標(biāo)準(zhǔn)判斷所在子分片是否滿足分片分裂條件，若滿足，則可以執(zhí)行相應(yīng)的分片分裂過程。

3）執(zhí)行步驟2）中的過程，直到節(jié)點(diǎn)檢測到所在子分片的節(jié)點(diǎn)數(shù)不超過O為止。

4.2 分片的全網(wǎng)分裂

4.2.1 分裂條件

1）節(jié)點(diǎn)發(fā)起分裂請(qǐng)求提案的條件

當(dāng)基礎(chǔ)分片內(nèi)任一節(jié)點(diǎn)發(fā)現(xiàn)分片的節(jié)點(diǎn)數(shù)已經(jīng)超過上限閾值O，并且它能夠提供其所處基礎(chǔ)分片滿足分片分裂條件的證明時(shí)，就可以發(fā)起分裂請(qǐng)求提案。

2）全網(wǎng)分片分裂條件

當(dāng)全網(wǎng)分片分裂后不會(huì)導(dǎo)致某些新分片的節(jié)點(diǎn)數(shù)低于T且超過1/2 的分片響應(yīng)分裂時(shí)，可以開始全網(wǎng)分片的分裂。

3）單個(gè)分片分裂條件

當(dāng)基礎(chǔ)分片中的節(jié)點(diǎn)就是否響應(yīng)分裂進(jìn)行PBFT 共識(shí)時(shí)，每個(gè)節(jié)點(diǎn)除了需要在消息中注明是否響應(yīng)，同時(shí)需要注明是否愿意留在當(dāng)前分片內(nèi)成為歸約節(jié)點(diǎn)，即是否愿意同步兩個(gè)基礎(chǔ)分片的狀態(tài)（在分裂完成后，當(dāng)前分片處于歸約樹中非葉子節(jié)點(diǎn)的位置，它在邏輯上已經(jīng)屬于歸約分片，分裂產(chǎn)生的新分片處于新的葉子節(jié)點(diǎn)位置上，它們是新的基礎(chǔ)分片）。在對(duì)響應(yīng)分裂達(dá)成共識(shí)的情況下，只有愿意留在當(dāng)前分片內(nèi)的節(jié)點(diǎn)數(shù)大于等于T，基礎(chǔ)分片才可以將響應(yīng)消息向上傳遞。

4.2.2 分片的分裂過程

4.2.2.1 請(qǐng)求階段

基礎(chǔ)分片內(nèi)某一節(jié)點(diǎn)發(fā)現(xiàn)分片的節(jié)點(diǎn)數(shù)已經(jīng)超過了O，它便發(fā)起分裂請(qǐng)求提案。該提案包括其所屬基礎(chǔ)分片滿足分裂條件的證明、請(qǐng)求編號(hào)以及它的數(shù)字簽名。

4.2.2.2 預(yù)準(zhǔn)備階段

分裂請(qǐng)求提案一經(jīng)提出，便會(huì)在發(fā)起提案的節(jié)點(diǎn)所屬的基礎(chǔ)分片內(nèi)廣播，該基礎(chǔ)分片的祖先分片中的節(jié)點(diǎn)便可以捕獲這個(gè)提案，然后捕獲提案的節(jié)點(diǎn)作為當(dāng)前其所在的歸約樹中最高級(jí)別分片PBFT共識(shí)的主節(jié)點(diǎn)，執(zhí)行PBFT 共識(shí)，目的是就該提案是否可以執(zhí)行達(dá)成一致。以圖3 為例，假設(shè)分片C 中的節(jié)點(diǎn)發(fā)起分裂請(qǐng)求提案，分片Root、A 和B 中的節(jié)點(diǎn)1、2 和3 若是捕獲到該提案，則其便作為主節(jié)點(diǎn)在相應(yīng)分片內(nèi)開始PBFT 共識(shí)。

若是達(dá)成一致性共識(shí)，則先向另一個(gè)非提案來源的子分片廣播一致性結(jié)果和提案，再由該子分片向它的所有子分片傳遞一致性結(jié)果和提案。以此類推，直到傳遞至基礎(chǔ)分片。以圖3 為例，對(duì)于分片A中的節(jié)點(diǎn)，它們接收的提案來自分片C，也就是分片B 這一分支，則在分片A 達(dá)成一致性共識(shí)的情況下，分片A 中的節(jié)點(diǎn)要主動(dòng)將一致性結(jié)果和提案傳遞給另一分支即分片D，再由分片D 繼續(xù)向下層擴(kuò)散傳遞。同樣地，對(duì)應(yīng)圖4 中的分片Root 和分片B，它們要分別傳遞一致性結(jié)果和提案給分片F(xiàn) 和分片E，再由F 和E 繼續(xù)向下傳遞，其中箭頭上的標(biāo)注代表傳遞過程中一致性結(jié)果的來源。

圖4 預(yù)準(zhǔn)備階段的消息傳遞路線Fig.4 Messaging routes of pre-prepare phase

若是在某一級(jí)分片達(dá)不成一致性共識(shí)，則該分片的主節(jié)點(diǎn)要向其子分片傳遞拒絕請(qǐng)求消息。拒絕請(qǐng)求消息傳遞路線如圖5 所示。

圖5 拒絕請(qǐng)求消息傳遞路線Fig.5 Reject request messaging routes

仍以圖3 為例，若是分片Root 沒有達(dá)成一致性共識(shí)，則主節(jié)點(diǎn)會(huì)向來源分片（分片A）傳遞拒絕請(qǐng)求消息，消息的傳遞路線如圖5（a）所示。若分片A沒有達(dá)成一致性共識(shí)，則拒絕請(qǐng)求消息的傳遞路線如圖5（b）所示。對(duì)于分片B，拒絕請(qǐng)求消息的傳遞路線如圖5（c）所示。對(duì)于來源分片，例如圖5（a）中的分片A，則需要向其所有子分片傳遞拒絕請(qǐng)求消息，以此類推，直到基礎(chǔ)分片。這是因?yàn)榫芙^請(qǐng)求的分片在發(fā)現(xiàn)請(qǐng)求需要被否決時(shí)，來源分片可能已經(jīng)達(dá)成一致性共識(shí)并將結(jié)果傳遞給下級(jí)分片。

4.2.2.3 準(zhǔn)備階段

預(yù)準(zhǔn)備階段通過消息的并行傳遞可以使一致性結(jié)果和分裂請(qǐng)求提案傳遞到各個(gè)基礎(chǔ)分片。此時(shí)，若是某基礎(chǔ)分片中不屬于歸約分片的節(jié)點(diǎn)捕獲到傳遞來的一致性結(jié)果，它便作為該基礎(chǔ)分片中PBFT 共識(shí)的主節(jié)點(diǎn)執(zhí)行PBFT 共識(shí)，其目的是就是否響應(yīng)分片分裂達(dá)成一致性共識(shí)。在基礎(chǔ)分片達(dá)成共識(shí)后，將結(jié)果向上傳遞給根分片Root。

與此同時(shí)，Root 在預(yù)準(zhǔn)備階段達(dá)成一致性共識(shí)后，便開始使用VRF 來確定分裂的啟動(dòng)者。在啟動(dòng)者確定后，設(shè)置超時(shí)時(shí)間，等待并收集基礎(chǔ)分片的響應(yīng)消息。若收集到超過1/2 的來自基礎(chǔ)分片的同意響應(yīng)的消息，則開始分裂的執(zhí)行階段。

4.2.2.4 執(zhí)行階段

1）分裂過程相關(guān)參數(shù)的確定

分裂啟動(dòng)者一旦收集到超過1/2 的來自基礎(chǔ)分片的同意響應(yīng)的消息，并且全網(wǎng)分片分裂后不會(huì)導(dǎo)致某些新分片的節(jié)點(diǎn)數(shù)低于分片節(jié)點(diǎn)數(shù)的下限閾值T，它就作為分裂決策共識(shí)（共識(shí)節(jié)點(diǎn)集合是Root 中的全部節(jié)點(diǎn)）的主節(jié)點(diǎn)發(fā)起分裂提案，提案中包括分裂過程中相關(guān)參數(shù)的一些設(shè)定，包含VDF 所需的時(shí)間參數(shù)t、安全參數(shù)λ和啟動(dòng)者產(chǎn)生提案的當(dāng)前時(shí)隙C以及參數(shù)z（將C時(shí)隙之后第z個(gè)區(qū)塊的哈希值作為VDF 的隨機(jī)性輸入x）。

若根分片Root 沒有對(duì)分裂提案達(dá)成共識(shí)，則依據(jù)多輪驗(yàn)證的思想，重新通過VRF 算法選擇新的啟動(dòng)者進(jìn)行新一輪的分裂決策共識(shí)，直到達(dá)到共識(shí)輪數(shù)上限仍未達(dá)成共識(shí)才放棄此次分裂過程。

若在分裂決策共識(shí)中分裂提案被同意，則分片Root 中的節(jié)點(diǎn)便將一致性結(jié)果向下傳遞，直至傳遞到所有基礎(chǔ)分片。

2）節(jié)點(diǎn)隨機(jī)數(shù)的生成

在基礎(chǔ)分片中的節(jié)點(diǎn)接收到分裂決策共識(shí)的一致性結(jié)果后，便可以按照相關(guān)參數(shù)生成隨機(jī)數(shù)。DSSM為了對(duì)抗Sybil攻擊以及避免可能存在的惡意節(jié)點(diǎn)相互串通而提前計(jì)算符合它們要求的隨機(jī)數(shù)的情況，采用VDF+VRF的方式來生成各個(gè)節(jié)點(diǎn)的隨機(jī)數(shù)。

算法1節(jié)點(diǎn)隨機(jī)數(shù)生成算法

3）節(jié)點(diǎn)分配

每個(gè)節(jié)點(diǎn)以產(chǎn)生的隨機(jī)數(shù)與分裂后的子分片數(shù)量（這里取2）為參數(shù)，通過跳躍一致性Hash 算法得到其分裂之后所在的子分片編號(hào)。

4.2.3 分裂過程中的特殊情況

在分片的分裂過程中，有可能會(huì)出現(xiàn)單個(gè)分片因?yàn)槟撤N因素不再滿足分裂條件的情況，即分片分裂后新分片的節(jié)點(diǎn)數(shù)低于T或分裂前分片中的節(jié)點(diǎn)數(shù)就已經(jīng)小于T，這兩種情況都對(duì)分片的安全性造成了威脅。對(duì)此，提出復(fù)用和降級(jí)兩種相應(yīng)的處理策略。

1）復(fù)用

針對(duì)分片分裂后新分片的節(jié)點(diǎn)數(shù)低于T的情況，選擇在分片內(nèi)復(fù)用節(jié)點(diǎn)的策略。當(dāng)出現(xiàn)上述情況時(shí)，如果有歸約節(jié)點(diǎn)愿意同時(shí)作為兩個(gè)新的子分片的節(jié)點(diǎn)存在并且同時(shí)負(fù)責(zé)處理兩個(gè)子分片的事務(wù)，則該節(jié)點(diǎn)被定義為復(fù)用歸約節(jié)點(diǎn)，如圖6（a）中的節(jié)點(diǎn)1 和2 所示。

圖6 節(jié)點(diǎn)復(fù)用與分片降級(jí)Fig.6 Node reuse and sharding degradation

節(jié)點(diǎn)復(fù)用的條件如式（1）所示：

當(dāng)分片內(nèi)的節(jié)點(diǎn)發(fā)現(xiàn)上述情況時(shí)，開始在分片內(nèi)廣播復(fù)用詢問消息，此時(shí)該節(jié)點(diǎn)成為分片中的源節(jié)點(diǎn)。當(dāng)分片內(nèi)的其他節(jié)點(diǎn)接收到此消息時(shí)，若是同意作為復(fù)用歸約節(jié)點(diǎn)而存在，則廣播發(fā)送復(fù)用確認(rèn)消息。

在源節(jié)點(diǎn)發(fā)送復(fù)用詢問消息后，開始準(zhǔn)備收集確認(rèn)消息。在源節(jié)點(diǎn)收集到足夠多的確認(rèn)消息后，便在本分片（分裂前的分片）內(nèi)廣播復(fù)用消息，此消息內(nèi)包含已確認(rèn)的復(fù)用節(jié)點(diǎn)名單的信息。

普通節(jié)點(diǎn)繼續(xù)執(zhí)行分片分裂過程，復(fù)用歸約節(jié)點(diǎn)不必繼續(xù)執(zhí)行此過程，屬于它們的分裂過程已經(jīng)結(jié)束，生成的隨機(jī)數(shù)也隨之作廢。

2）降級(jí)

節(jié)點(diǎn)降級(jí)的條件如式（2）所示，待分裂的分片中的節(jié)點(diǎn)數(shù)量已低于T：

此時(shí)，即使該分片中所有的節(jié)點(diǎn)都成了復(fù)用歸約節(jié)點(diǎn)，也無法滿足兩個(gè)子分片中基本節(jié)點(diǎn)數(shù)的要求。在這種情況下，采取此分片分裂中止并降級(jí)的策略。當(dāng)分片中的節(jié)點(diǎn)發(fā)現(xiàn)上述情況時(shí)，便按照消息的傳遞規(guī)則將降級(jí)證明消息傳遞給全網(wǎng)分片，此消息包含本分片滿足降級(jí)條件的證明。同時(shí)，接收到該消息的本分片節(jié)點(diǎn)停止分裂過程，整個(gè)分片整體降級(jí)。

如圖6（b）所示，分片A 中的節(jié)點(diǎn)數(shù)量小于T，那么在分裂過程中采取的策略是分片A 中的節(jié)點(diǎn)在物理上整體下移至分片B 中，具體下移至左子分片還是右子分片，可根據(jù)實(shí)際情況而制定相應(yīng)的規(guī)則。分片B 作為新的基礎(chǔ)分片，與其他分裂后產(chǎn)生的新分片同處于歸約樹葉子節(jié)點(diǎn)的位置。分片B 的兄弟節(jié)點(diǎn)的位置原本也應(yīng)該有一個(gè)基礎(chǔ)分片C，只是因?yàn)榉制导?jí)的問題導(dǎo)致該分片是空分片。此時(shí)，分片A 與分片B 實(shí)際上是一個(gè)分片，它們的節(jié)點(diǎn)集合是一樣的，但是它們?cè)跉w約樹中占據(jù)兩個(gè)節(jié)點(diǎn)的位置。

4.3 分片的全網(wǎng)合并

分片在正常情況下可能會(huì)因?yàn)槟承┰蚨鴮?dǎo)致大批節(jié)點(diǎn)宕機(jī)，造成分片內(nèi)節(jié)點(diǎn)數(shù)過少，從而使得分片的安全性和去中心化程度大大降低。為此，采用分片合并策略。

4.3.1 合并條件

1）節(jié)點(diǎn)發(fā)起合并請(qǐng)求提案的條件

當(dāng)基礎(chǔ)分片內(nèi)任一節(jié)點(diǎn)發(fā)現(xiàn)分片的節(jié)點(diǎn)數(shù)已經(jīng)低于下限閾值T并且能夠提供所處基礎(chǔ)分片滿足分片合并條件的證明時(shí)，便可以發(fā)起合并請(qǐng)求提案。

2）全網(wǎng)分片合并條件

當(dāng)超過半數(shù)的分片響應(yīng)合并時(shí)，開始全網(wǎng)分片的合并。

4.3.2 分片的合并過程

4.3.2.1 請(qǐng)求階段

類似于分片分裂的請(qǐng)求階段，在滿足相應(yīng)條件后，節(jié)點(diǎn)可以發(fā)起合并請(qǐng)求提案。與分裂請(qǐng)求提案不同的是，該提案中要含有該節(jié)點(diǎn)所屬的基礎(chǔ)分片滿足合并條件的證明以及合并請(qǐng)求編號(hào)。

4.3.2.2 預(yù)準(zhǔn)備階段

合并請(qǐng)求提案一經(jīng)提出便在發(fā)起提案的節(jié)點(diǎn)所屬的基礎(chǔ)分片內(nèi)廣播，該基礎(chǔ)分片的祖先分片中的節(jié)點(diǎn)便可以捕獲這個(gè)提案。與分裂過程類似，捕獲提案的節(jié)點(diǎn)作為當(dāng)前其所在的分片歸約樹中最高級(jí)別分片PBFT 共識(shí)的主節(jié)點(diǎn)，執(zhí)行PBFT 共識(shí)。

若是達(dá)成一致性共識(shí)，則向另一個(gè)非提案來源的子分片廣播一致性結(jié)果和合并請(qǐng)求提案，消息的傳遞規(guī)則與分裂時(shí)的預(yù)準(zhǔn)備階段一致，傳遞路徑如圖4 所示。

若是某一級(jí)分片達(dá)不成一致性共識(shí)，則由該分片的主節(jié)點(diǎn)向其子分片傳遞拒絕請(qǐng)求消息。消息的傳遞路徑與分裂時(shí)的預(yù)準(zhǔn)備階段一致，傳遞路徑如圖5 所示。

4.3.2.3 準(zhǔn)備階段

類似于分裂的準(zhǔn)備階段，若是基礎(chǔ)分片中不屬于歸約分片的節(jié)點(diǎn)捕獲到父級(jí)分片傳遞的一致性結(jié)果和合并請(qǐng)求提案，它便作為該基礎(chǔ)分片中PBFT 共識(shí)的主節(jié)點(diǎn)執(zhí)行PBFT 共識(shí)，就是否響應(yīng)分片合并進(jìn)行共識(shí)。在基礎(chǔ)分片達(dá)成共識(shí)后，將結(jié)果向上傳遞給根分片Root。

根分片Root 在預(yù)準(zhǔn)備階段達(dá)成一致性共識(shí)后，便開始使用VRF 來確定合并過程的啟動(dòng)者。在啟動(dòng)者確定后，設(shè)置超時(shí)時(shí)間，等待并收集基礎(chǔ)分片的響應(yīng)消息。若是啟動(dòng)者收集到超過1/2 的來自基礎(chǔ)分片的同意響應(yīng)的消息，則開始合并的執(zhí)行階段。

4.3.2.4 執(zhí)行階段

1）合并決策共識(shí)

合并啟動(dòng)者一旦收集到超過1/2 的來自基礎(chǔ)分片的同意響應(yīng)的消息，就作為合并決策共識(shí)（共識(shí)節(jié)點(diǎn)集合是分片Root 中的全部節(jié)點(diǎn)）的主節(jié)點(diǎn)發(fā)起合并提案，就是否進(jìn)行全網(wǎng)合并進(jìn)行共識(shí)。合并啟動(dòng)者發(fā)起的提案中必須包含其所收集的超過1/2 的來自基礎(chǔ)分片的同意響應(yīng)的消息。

若分片Root 沒有對(duì)合并提案達(dá)成共識(shí)，則與分裂時(shí)一致，采用多輪驗(yàn)證思想繼續(xù)選擇啟動(dòng)者進(jìn)行流程。

若在合并決策共識(shí)中提案被通過，則分片Root中的節(jié)點(diǎn)便將達(dá)成的一致性結(jié)果向下傳遞，直至傳遞到所有基礎(chǔ)分片。

2）合并執(zhí)行

當(dāng)處于歸約樹倒數(shù)第2 層的分片中的節(jié)點(diǎn)收到分片Root 傳遞的一致性結(jié)果時(shí)便開始狀態(tài)同步過程，將自己目前所保存的兩個(gè)基礎(chǔ)分片的狀態(tài)同步給自己所處的基礎(chǔ)分片的非歸約節(jié)點(diǎn)（也就是未同步其他分片狀態(tài)的節(jié)點(diǎn)）。此時(shí)，原來的只在基礎(chǔ)分片中的節(jié)點(diǎn)便成為其父級(jí)分片中的待同步節(jié)點(diǎn)。原來的歸約樹倒數(shù)第2 層的分片變成了新的基礎(chǔ)分片。

4.4 節(jié)點(diǎn)分配算法

在父級(jí)分片分裂為兩個(gè)子分片的過程中，對(duì)于其中的節(jié)點(diǎn)，采用跳躍一致性Hash 算法［26］來決定其將進(jìn)入哪個(gè)子分片。跳躍一致性Hash 算法具有均勻性與一致性兩個(gè)特點(diǎn)。

節(jié)點(diǎn)分配算法具體如下：

在DSSM 中，由于只需要將父級(jí)分片分裂為兩個(gè)子分片，對(duì)應(yīng)于節(jié)點(diǎn)分配算法，則相當(dāng)于只需要增加一個(gè)新的槽位，因此n的取值為2 即可。當(dāng)節(jié)點(diǎn)提供的隨機(jī)數(shù)為參數(shù)k、分片數(shù)目為參數(shù)n時(shí)，ch（k，n）的返回值為節(jié)點(diǎn)所劃分到的子分片。本文規(guī)定：返回值為0 的節(jié)點(diǎn)屬于左子分片，返回值為1 的節(jié)點(diǎn)屬于右子分片（當(dāng)n為2 時(shí)，只有0 和1 兩個(gè)返回值）。

4.5 激勵(lì)機(jī)制

DSSM 鼓勵(lì)性能較高的節(jié)點(diǎn)同步其所在分片的兄弟分片的狀態(tài)，從而使高性能的節(jié)點(diǎn)成為更高級(jí)別的歸約節(jié)點(diǎn)。若想促使節(jié)點(diǎn)積極地參與狀態(tài)歸約，則需要激勵(lì)機(jī)制驅(qū)動(dòng)。

適應(yīng)DSSM 激勵(lì)機(jī)制的原則為：1）對(duì)于歸約樹的不同層級(jí)上的分片，在其上執(zhí)行事務(wù)所獲得的激勵(lì)必不相同，處理上層分片的事務(wù)所獲得的激勵(lì)應(yīng)該比下層高，只有這樣才能使節(jié)點(diǎn)積極地參與到歸約過程中；2）分片的合并和分裂過程中承擔(dān)著相應(yīng)角色（例如分裂和合并的啟動(dòng)者）的節(jié)點(diǎn)也應(yīng)獲得相應(yīng)的激勵(lì)；3）對(duì)于惡意行為的檢舉及證明也會(huì)有相應(yīng)的激勵(lì)。

具體的激勵(lì)機(jī)制需要匹配具體的網(wǎng)絡(luò)環(huán)境和相應(yīng)的項(xiàng)目，在此不再贅述。

5 安全性分析與參數(shù)設(shè)置

5.1 安全性分析

由于DSSM 結(jié)合多輪共識(shí)模型進(jìn)行驗(yàn)證，因此需要結(jié)合多輪共識(shí)模型進(jìn)行分析。

5.1.1 共識(shí)的安全性分析

對(duì)于采用PBFT 算法作為共識(shí)機(jī)制的區(qū)塊鏈網(wǎng)絡(luò)而言，一旦拜占庭節(jié)點(diǎn)的比例超過2/3，根據(jù)威脅模型：若拜占庭對(duì)手沒有獲得發(fā)布區(qū)塊的主節(jié)點(diǎn)的身份，則它會(huì)選擇遵守協(xié)議不作惡；若拜占庭對(duì)手獲得了發(fā)布區(qū)塊的主節(jié)點(diǎn)的身份，則它就可以輕易地發(fā)起雙花攻擊或發(fā)布錯(cuò)誤的鑄幣交易，最終導(dǎo)致數(shù)據(jù)的不一致?？紤]最壞的情況，即一旦拜占庭對(duì)手控制了共識(shí)節(jié)點(diǎn)中超過2/3 的節(jié)點(diǎn)，那么它就可以發(fā)起合謀攻擊，在區(qū)塊中發(fā)布錯(cuò)誤事務(wù)。

為了最大化共識(shí)的安全性，從分片的節(jié)點(diǎn)數(shù)入手降低合謀攻擊的概率。在多輪共識(shí)模型的基礎(chǔ)上，按照最低輪數(shù)下限的要求，計(jì)算在不同分片節(jié)點(diǎn)數(shù)的情況下，攻擊者若想使合謀攻擊的概率高于百萬分之一，則需要付出的代價(jià)如圖7 所示，其中代價(jià)用攻擊者需要控制的最少節(jié)點(diǎn)數(shù)量表示。

圖7 合謀攻擊代價(jià)Fig.7 Cost of collusion attack

由圖7 可以看出，隨著分片內(nèi)節(jié)點(diǎn)數(shù)的增多，攻擊者要想使其發(fā)動(dòng)合謀攻擊的概率超過百萬分之一，需要控制的節(jié)點(diǎn)數(shù)也會(huì)隨之增加，并且近似于線性增加。分片內(nèi)節(jié)點(diǎn)數(shù)越多，攻擊者發(fā)動(dòng)合謀攻擊所付出的代價(jià)越大，分片也越安全。

由數(shù)據(jù)計(jì)算而得，若合謀攻擊的概率超過百萬分之一，則需要攻擊者至少控制分片的將近1/2 的驗(yàn)證節(jié)點(diǎn)。這也意味著：若分片內(nèi)節(jié)點(diǎn)數(shù)翻倍，則攻擊者進(jìn)行攻擊的代價(jià)至少也要翻倍。

5.1.2 節(jié)點(diǎn)隨機(jī)數(shù)的可靠性分析

在節(jié)點(diǎn)隨機(jī)數(shù)生成算法中，由于參數(shù)t和λ是根據(jù)分裂決策共識(shí)的一致性結(jié)果獲得的，x是由一致性結(jié)果中的信息求得的，那么同一分片的驗(yàn)證節(jié)點(diǎn)生成的VDF 結(jié)果必然是一樣的，因此獲得了可靠的公共隨機(jī)數(shù)。

所有驗(yàn)證節(jié)點(diǎn)以VDF 的結(jié)果作為VRF 的Evaluate（SK，X）函數(shù)的隨機(jī)性輸入X，再使用自己的私鑰作為輸入SK，那么通過計(jì)算便可獲得屬于節(jié)點(diǎn)自己的可驗(yàn)證的可靠的隨機(jī)數(shù)。

5.1.3 分片的安全性分析

根據(jù)節(jié)點(diǎn)隨機(jī)數(shù)的可靠性以及節(jié)點(diǎn)分配過程的隨機(jī)性和不可預(yù)測性，拜占庭對(duì)手很難再主動(dòng)地將拜占庭節(jié)點(diǎn)聚集到某些固定分片內(nèi)。

對(duì)于單個(gè)分片，考慮最壞情況，某個(gè)基礎(chǔ)分片超過50%的節(jié)點(diǎn)被拜占庭對(duì)手控制，并且這些惡意節(jié)點(diǎn)全部向上歸約。由均勻性可得，該分片的父級(jí)分片會(huì)有將近1/2 的節(jié)點(diǎn)被拜占庭對(duì)手控制，而再上一級(jí)的歸約分片只有1/4 的節(jié)點(diǎn)被控制。以此類推，越往上層，拜占庭節(jié)點(diǎn)的比例被稀釋得越低。

本文規(guī)定：DSSM 歸約模型的最底層，也就是基礎(chǔ)分片（由葉子節(jié)點(diǎn)代表的分片）所在的那層稱為歸約模型的第0 層，往上1 層也就是歸約模型的倒數(shù)第2 層，被稱為歸約模型的第1 層，以此類推。那么，隨著層數(shù)的遞增，某層分片中拜占庭節(jié)點(diǎn)的最高比例如式（3）所示：

由式（3）可以得出，在分片歸約樹的第2 層分片中的拜占庭節(jié)點(diǎn)比例只有1/4，已經(jīng)可以滿足大多數(shù)分片協(xié)議的容錯(cuò)率，越往上層，比例越低。另外，由于多輪共識(shí)模型中多輪驗(yàn)證與欺詐證明的存在，因此拜占庭對(duì)手在第0 和1 層分片作惡成功的概率極低。

在DSSM 中，每個(gè)基礎(chǔ)分片的祖先分片中的節(jié)點(diǎn)都會(huì)存儲(chǔ)該基礎(chǔ)分片的狀態(tài)，并能對(duì)該基礎(chǔ)分片中的區(qū)塊信息進(jìn)行驗(yàn)證。同時(shí)，基礎(chǔ)分片的各級(jí)祖先分片中幾乎包含所有基礎(chǔ)分片的節(jié)點(diǎn)，因此拜占庭對(duì)手想要發(fā)起攻擊而不被發(fā)現(xiàn)無異于要控制整個(gè)系統(tǒng)。

狀態(tài)歸約與冗余可以使拜占庭對(duì)手攻擊單個(gè)分片，作惡成功的代價(jià)無異于攻擊整個(gè)區(qū)塊鏈網(wǎng)絡(luò)。同時(shí)，由于各級(jí)歸約節(jié)點(diǎn)的存在，拜占庭對(duì)手在分片動(dòng)態(tài)調(diào)整過程中的惡意行為也很容易被檢舉，因此分片的安全性得到了保障。

5.1.4 數(shù)據(jù)的一致性分析

狀態(tài)歸約的存在使得上層分片的節(jié)點(diǎn)需要存儲(chǔ)其孩子分片的狀態(tài)。一個(gè)分片的狀態(tài)不僅被本分片內(nèi)的節(jié)點(diǎn)存儲(chǔ)，而且還會(huì)被其所有的祖先分片的節(jié)點(diǎn)存儲(chǔ)。一個(gè)分片的狀態(tài)會(huì)有多個(gè)備份。

當(dāng)有新的節(jié)點(diǎn)加入分片時(shí)（下層節(jié)點(diǎn)通過狀態(tài)歸約加入歸約分片或者新加入網(wǎng)絡(luò)的節(jié)點(diǎn)進(jìn)入基礎(chǔ)分片），原分片中的節(jié)點(diǎn)與該分片的祖先分片中的節(jié)點(diǎn)都可以向新節(jié)點(diǎn)同步狀態(tài)，并且由于在該分片或其祖先分片中存在多個(gè)該分片的狀態(tài)備份，新節(jié)點(diǎn)可以快速同步到該分片的最新狀態(tài)。

參與共識(shí)的驗(yàn)證節(jié)點(diǎn)必須同步到最新的分片狀態(tài)，這樣才能保證共識(shí)正常進(jìn)行，確保一致性。若因?yàn)樾阅芑蚓W(wǎng)絡(luò)原因，導(dǎo)致節(jié)點(diǎn)總是無法及時(shí)同步到最新狀態(tài)，該節(jié)點(diǎn)可以選擇自行降級(jí)，在下一級(jí)分片中工作，這也符合DSSM 的設(shè)計(jì)理念。

5.2 多輪共識(shí)模型下閾值T和O 的確定

本節(jié)結(jié)合多輪共識(shí)模型探討DSSM 中參數(shù)T和O的取值。

5.2.1 分片節(jié)點(diǎn)數(shù)下限閾值T的確定

在多輪共識(shí)模型下，考慮一種極端情況，每輪選擇的共識(shí)組的節(jié)點(diǎn)與前面輪次的共識(shí)組的節(jié)點(diǎn)均不同，即每輪共識(shí)組內(nèi)的節(jié)點(diǎn)相較于之前都是新的節(jié)點(diǎn)。那么，根據(jù)多輪共識(shí)模型所確定的輪數(shù)上限，估算得到分片內(nèi)至少需要150 個(gè)節(jié)點(diǎn)才能滿足需求。

根據(jù)上文分析，若拜占庭對(duì)手想對(duì)有150 個(gè)節(jié)點(diǎn)的分片發(fā)動(dòng)合謀攻擊，要使合謀攻擊的概率超過百萬分之一，則至少需要控制約1/2 的節(jié)點(diǎn)，但其收益遠(yuǎn)遠(yuǎn)低于其所付出的代價(jià)（即使控制了1/2 的節(jié)點(diǎn)也有很大概率攻擊失?。?。因此，考慮設(shè)定下限閾值T為150。

5.2.2 分片節(jié)點(diǎn)數(shù)上限閾值O的確定

由于分裂時(shí)子分片是由父級(jí)分片一分為二得到的，則父級(jí)分片節(jié)點(diǎn)數(shù)的上限閾值O需要滿足：父級(jí)分片分裂之后，其子分片內(nèi)的節(jié)點(diǎn)數(shù)仍需滿足最低運(yùn)行標(biāo)準(zhǔn)，即子分片內(nèi)的節(jié)點(diǎn)數(shù)仍然大于等于T，那么O至少要滿足的條件是O≥2T。

在多輪共識(shí)模型下，即使分片內(nèi)節(jié)點(diǎn)數(shù)達(dá)到了600，共識(shí)仍然可用。另外，考慮到多分片并行可以提高吞吐量。為兼顧網(wǎng)絡(luò)的整體性能，分片內(nèi)的節(jié)點(diǎn)數(shù)不宜過多。因此，在多輪共識(shí)模型下設(shè)定上限閾值O為600。

6 模擬驗(yàn)證

模擬實(shí)驗(yàn)將驗(yàn)證DSSM 可以隨著節(jié)點(diǎn)數(shù)量的大幅增多實(shí)現(xiàn)分片規(guī)模的動(dòng)態(tài)擴(kuò)充，以提供更好的性能，同時(shí)在節(jié)點(diǎn)顯著減少時(shí)，DSSM 可以為了分片的安全，動(dòng)態(tài)地收縮分片的規(guī)模。選用Linux 系統(tǒng)作為開發(fā)平臺(tái)，以Go 語言作為開發(fā)語言，以VS Code 和Docker 作為開發(fā)工具，進(jìn)行模擬實(shí)驗(yàn)。

6.1 實(shí)驗(yàn)假設(shè)

1）測試網(wǎng)絡(luò)中節(jié)點(diǎn)間的通信狀況良好，延遲在可容忍范圍內(nèi)。

2）不考慮由于交易分片導(dǎo)致的分片負(fù)載不均衡的問題，即每個(gè)基礎(chǔ)分片在同一個(gè)時(shí)間段內(nèi)需要處理的交易是相對(duì)均勻的。

3）系統(tǒng)的拜占庭節(jié)點(diǎn)比例為0.33。

4）隨著模擬時(shí)間的推移，節(jié)點(diǎn)的表現(xiàn)可以發(fā)生變化，即原本的正常節(jié)點(diǎn)可以表現(xiàn)為拜占庭行為，但是系統(tǒng)中表現(xiàn)拜占庭行為的節(jié)點(diǎn)的比例不變。

5）節(jié)點(diǎn)可以動(dòng)態(tài)加入或退出系統(tǒng)。

6）拜占庭節(jié)點(diǎn)秉承對(duì)自己最為有利的方式執(zhí)行操作。

6.2 DSSM 可行性測試

從測試系統(tǒng)的一個(gè)初始狀態(tài)開始，隨著時(shí)間的推移，逐步往系統(tǒng)中添加或減少節(jié)點(diǎn)來模擬節(jié)點(diǎn)加入或退出系統(tǒng)的情況，同時(shí)逐步往系統(tǒng)中注入交易，觀察系統(tǒng)的吞吐能力隨著時(shí)間的變化情況。在其他外部條件不變的情況下，網(wǎng)絡(luò)中分片規(guī)模的變化可以通過吞吐量的變化體現(xiàn)出來。通過吞吐能力的變化來驗(yàn)證DSSM 能夠根據(jù)節(jié)點(diǎn)環(huán)境自適應(yīng)地調(diào)整分片的規(guī)模。

為能夠模擬DSSM 中分片分裂過程的各種情況，進(jìn)行了如下設(shè)置：

1）初始狀態(tài)的系統(tǒng)內(nèi)有600 個(gè)節(jié)點(diǎn)，正好是分片的上限閾值O的值。

2）在第10 個(gè)時(shí)隙時(shí)，在系統(tǒng)中加入400 個(gè)節(jié)點(diǎn)，滿足分片分裂條件，觀察系統(tǒng)正常分裂情況下的吞吐能力的變化。

3）在第45 個(gè)時(shí)隙時(shí)，在系統(tǒng)中再加入400 個(gè)節(jié)點(diǎn)，每個(gè)分片內(nèi)有700個(gè)節(jié)點(diǎn)。然后，在第57個(gè)時(shí)隙時(shí)減少某個(gè)分片的節(jié)點(diǎn)數(shù)至200來模擬節(jié)點(diǎn)復(fù)用情況。

4）在第75 個(gè)時(shí)隙時(shí)，在系統(tǒng)中加入1 100 個(gè)節(jié)點(diǎn)，使得每個(gè)分片的節(jié)點(diǎn)數(shù)都達(dá)到500 個(gè)。在第90 個(gè)時(shí)隙時(shí)，在系統(tǒng)中加入1 200 個(gè)節(jié)點(diǎn)，此時(shí)每個(gè)分片的節(jié)點(diǎn)數(shù)都達(dá)到了800。在第103 個(gè)時(shí)隙時(shí)，減少某個(gè)分片的節(jié)點(diǎn)數(shù)至100 來模擬分片降級(jí)情況。在第120 個(gè)時(shí)隙時(shí)，將系統(tǒng)恢復(fù)至3 200 個(gè)節(jié)點(diǎn)的狀態(tài)。

經(jīng)過以上的模擬步驟，得到系統(tǒng)吞吐能力在分片分裂過程中隨著時(shí)間變化的情況如圖8 所示。

為了能夠模擬DSSM 中分片合并過程的情況，進(jìn)行如下設(shè)置：初始狀態(tài)的測試系統(tǒng)內(nèi)有2 400 個(gè)節(jié)點(diǎn)，分為8 個(gè)分片，每個(gè)分片有300 個(gè)節(jié)點(diǎn)；在第20 個(gè)時(shí)隙時(shí)，系統(tǒng)中每個(gè)分片都減少100 個(gè)節(jié)點(diǎn)，此時(shí)每個(gè)分片有200 個(gè)節(jié)點(diǎn)；在第40 個(gè)時(shí)隙時(shí)，系統(tǒng)減少600 個(gè)節(jié)點(diǎn)，此時(shí)每個(gè)分片內(nèi)有125 個(gè)節(jié)點(diǎn)，滿足合并條件。經(jīng)過以上的模擬步驟，得到系統(tǒng)吞吐能力在分片合并過程中隨著時(shí)間變化的情況如圖9所示。

圖9 吞吐能力在合并過程中的變化Fig.9 Changes of throughput capacity during merging process

由圖8 可以看出，系統(tǒng)吞吐能力隨著節(jié)點(diǎn)數(shù)量的增多得到了增強(qiáng)，而且是近乎翻倍的增強(qiáng)。由圖9可以看出，當(dāng)節(jié)點(diǎn)數(shù)量大幅減少時(shí)，系統(tǒng)吞吐能力有所下降。結(jié)合圖8 與圖9 驗(yàn)證了DSSM 可以根據(jù)不同的節(jié)點(diǎn)環(huán)境，動(dòng)態(tài)快速地調(diào)整網(wǎng)絡(luò)中分片的規(guī)模，從而實(shí)現(xiàn)了在保證基本安全要求的情況下，自適應(yīng)快速地進(jìn)行分片規(guī)模的調(diào)整，滿足系統(tǒng)性能更好的目標(biāo)。

6.3 可擴(kuò)展性對(duì)比實(shí)驗(yàn)

設(shè)置結(jié)合DSSM 的多輪共識(shí)模型與未結(jié)合DSSM 的多輪共識(shí)模型的吞吐量對(duì)比實(shí)驗(yàn)，以驗(yàn)證DSSM 能夠在節(jié)點(diǎn)數(shù)量滿足條件時(shí)具有更好的可擴(kuò)展性。

在初始狀態(tài)下，兩種模型各有兩個(gè)分片，每個(gè)分片的節(jié)點(diǎn)數(shù)均為500。然后在第5 個(gè)時(shí)隙時(shí)向環(huán)境中加入節(jié)點(diǎn)，使得每個(gè)分片的節(jié)點(diǎn)數(shù)達(dá)到700，觀察系統(tǒng)的吞吐能力隨時(shí)間變化的情況，如圖10 所示。

圖10 可擴(kuò)展性對(duì)比Fig.10 Scalability comparison

由圖10 可以看出，隨著節(jié)點(diǎn)數(shù)量的增多，在一段時(shí)間后，采用DSSM 的系統(tǒng)吞吐量有明顯的提升，而未采用DSSM 并沿用傳統(tǒng)靜態(tài)分片方式的系統(tǒng)吞吐量卻并未隨著節(jié)點(diǎn)數(shù)量的增多而得到較大改善。

因此，在區(qū)塊鏈運(yùn)行過程中，DSSM 可以隨著節(jié)點(diǎn)數(shù)量的增多，動(dòng)態(tài)自適應(yīng)地?cái)U(kuò)展分片的規(guī)模，以提高網(wǎng)絡(luò)的性能和可擴(kuò)展性。

6.4 時(shí)延對(duì)比實(shí)驗(yàn)

設(shè)置結(jié)合DSSM 的多輪共識(shí)模型與未結(jié)合DSSM 的多輪共識(shí)模型的交易時(shí)延對(duì)比實(shí)驗(yàn)，以驗(yàn)證DSSM 能夠在節(jié)點(diǎn)數(shù)量大幅減少時(shí)，通過自適應(yīng)地收縮分片的規(guī)模來保證網(wǎng)絡(luò)的活性與安全性。

在初始狀態(tài)下兩種模型各有兩個(gè)分片，每個(gè)分片的節(jié)點(diǎn)數(shù)是150，然后在第5 個(gè)時(shí)隙時(shí)在環(huán)境中減少節(jié)點(diǎn)，使得每個(gè)分片的節(jié)點(diǎn)數(shù)達(dá)到80，觀察系統(tǒng)的交易時(shí)延隨時(shí)間變化的情況，如圖11 所示。

圖11 交易時(shí)延對(duì)比Fig.11 Transaction latency comparison

由圖11 可以看出，當(dāng)節(jié)點(diǎn)數(shù)量大幅減少時(shí)，采用DSSM 的系統(tǒng)和未采用DSSM 的系統(tǒng)都出現(xiàn)了時(shí)延增加且不穩(wěn)定的情況。這是因?yàn)榉制瑑?nèi)的節(jié)點(diǎn)數(shù)量變少，拜占庭節(jié)點(diǎn)進(jìn)入共識(shí)組的概率會(huì)大大增加，導(dǎo)致交易的驗(yàn)證需要更多輪次的共識(shí)，所以時(shí)延也就升高了。采用DSSM 的系統(tǒng)在一段時(shí)間后，時(shí)延會(huì)慢慢降低，逐步恢復(fù)到節(jié)點(diǎn)減少之前的狀態(tài)并穩(wěn)定下來，而未采用DSSM 并沿用傳統(tǒng)靜態(tài)分片方式的系統(tǒng)交易時(shí)延依舊偏高且很不穩(wěn)定。

因此，在區(qū)塊鏈運(yùn)行過程中，當(dāng)節(jié)點(diǎn)數(shù)量大幅減少時(shí)，DSSM 可以通過動(dòng)態(tài)自適應(yīng)地收縮分片的規(guī)模來保障網(wǎng)絡(luò)的活性與安全性。

7 結(jié)束語

針對(duì)現(xiàn)有分片方案不能及時(shí)調(diào)整分片規(guī)模以適應(yīng)公鏈環(huán)境下分片內(nèi)節(jié)點(diǎn)數(shù)量在短時(shí)間內(nèi)的大幅變化以及由此導(dǎo)致的安全隱患和性能提升困難問題，本文提出一種基于狀態(tài)歸約的自適應(yīng)節(jié)點(diǎn)規(guī)模的動(dòng)態(tài)分片可擴(kuò)展模型?？紤]到驗(yàn)證節(jié)點(diǎn)的性能和表現(xiàn)差異，在基礎(chǔ)和邏輯分片的組合下，通過支持狀態(tài)歸約與狀態(tài)冗余允許節(jié)點(diǎn)在不同層級(jí)的分片上進(jìn)行狀態(tài)同步，同時(shí)分片的動(dòng)態(tài)分裂能夠充分利用節(jié)點(diǎn)資源以實(shí)現(xiàn)更高的性能，分片的動(dòng)態(tài)合并可以更好地保障分片安全，由此使得整個(gè)系統(tǒng)具有較好的規(guī)模彈性。模擬實(shí)驗(yàn)結(jié)果證明，該模型能夠快速、低成本、自適應(yīng)地針對(duì)節(jié)點(diǎn)環(huán)境做出相應(yīng)變化，從而實(shí)現(xiàn)分片系統(tǒng)的動(dòng)態(tài)自適應(yīng)調(diào)整。

本文提出的基于狀態(tài)歸約的自適應(yīng)節(jié)點(diǎn)規(guī)模的動(dòng)態(tài)分片可擴(kuò)展模型還有一些地方需要進(jìn)一步完善。例如，模型中的參數(shù)在面對(duì)不同的環(huán)境和不同的共識(shí)機(jī)制是不一樣的，這與系統(tǒng)的安全要求有關(guān)。另外，本文考慮的是一個(gè)整體系統(tǒng)的擴(kuò)展與收縮，尚未針對(duì)單個(gè)分片的突發(fā)情況進(jìn)行詳盡討論。這些都將是下一步研究的重點(diǎn)內(nèi)容。