自適應節點規模的區塊鏈分片可擴展模型

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

（大連海事大學信息科學技術學院，遼寧 大連 116026）

0 引言

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

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

在分片后要面臨的是安全性降低的問題：分片后單個分片內節點數量遠低于分片前整個區塊鏈網絡的節點數量，導致攻擊者對單個分片發起攻擊的成本極大降低。假設系統包含S個分片，在節點被均勻地分配到各個分片的情況下，每個分片的安全性變為原先整條鏈的1/S。若分片前后區塊鏈都采用工作量證明（POW）共識（假設各個節點的算力相當），則分片前攻擊者需要控制超過50%的節點才能發動51%攻擊，而分片后攻擊者若想攻擊單個分片，則只需要控制分片內超過50%/S的節點。

在網絡中節點數一定的情況下，擴展分片的數量意味著分片內節點數的減少，也意味著攻擊者攻擊單個分片的代價更小，分片的安全性被削弱。因此，從安全方面而言，分片內要有足夠的節點來保證安全性和去中心化，分片的節點數應該有一個最小值，即下限閾值。當分片的節點數低于下限閾值時，此時的分片不滿足基本安全要求，節點數量需要增加，給分片補充節點。但由于在狀態分片下，補充新的節點存在同步分片狀態的滯后問題，因此應采取縮減分片規模的方式來確保分片的節點數不低于下限閾值。

在滿足基本的安全要求后，若分片的節點數過多，則會影響網絡的吞吐量。在網絡中節點數一定的情況下，增加分片內的節點數而減少分片的數量會使整個網絡的并行度降低，進而影響網絡的吞吐量。同時，若分片內的節點過多，則會增加節點間的通信開銷，節點需要存儲和維護的區塊信息和狀態數據也會隨之增多，而通信量的增大也會對網絡帶寬造成影響。因此，分片的節點數也應該有一個最大值，即上限閾值。當分片節點數高于上限閾值時，此時的分片可以通過向外擴展以提高吞吐能力。

本文建立基于狀態歸約的自適應節點規模的動態分片可擴展模型（DSSM），旨在使分片規模能夠自適應節點環境并且動態可擴展，同時不削弱去中心化程度和安全性。設計基于可驗證延遲函數（VDF）+可驗證隨機函數（VRF）的節點隨機數生成算法，可以對抗Sybil 攻擊以及避免可能存在的惡意節點相互串通、提前計算符合它們要求的隨機數的情況。

1 相關工作

1.1 符號與定義

本節簡要介紹了使用的相關符號及定義，如表1所示。

表1 符號及定義Table 1 Symbols and definitions

1.2 安全的去中心化隨機數生成器

1.2.1 可驗證隨機函數

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

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

1.2.2 可驗證延遲函數

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

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

1.3 其他區塊鏈分片方案

1.3.1 以太坊

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

Danksharding 的主要特點包括：1）Blob 數據分片傳輸；2）數據可用性抽樣實現區塊驗證；3）區塊提議者與構建者分離（PBS）。

1.3.2 Monoxide

Monoxide［14］的主要思想是通過異步共識組來實現公鏈擴容，主要特點包括：1）將區塊鏈網絡劃分為多個獨立和并行的Zone；2）高效處理跨越不同Zone的交易；3）通過“連弩挖礦”的方式解決分組后挖礦算力稀釋的問題。

Monoxide 在完全去中心化的前提下實現了全方位的分片，保證了可以正確高效地完成其上的跨分片交易，并保證了攻擊單個共識組的代價與攻擊整個網絡的代價相當。

1.3.3 NEAR

NEAR［15］將系統建模成一個單獨的區塊鏈，其中每個塊邏輯上包含所有分片的全部交易以及改變所有分片的整個狀態。然而，在物理上任何參與者都不會下載完整的狀態或完整的邏輯區塊，網絡的每個參與者只是維護為之驗證交易的分片上對應的狀態，區塊中的所有交易的列表被分割成物理上的段，一個分片為一個段。

1.4 多輪驗證思想與狀態分片基礎上的共識組

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

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

然而，普通的多輪驗證方案對于交易驗證采用的是分片內的全部節點均參與的方式。這會帶來一些問題：PBFT 的通信復雜度是O（n2）級別，若是分片內全部節點均參與PBFT 共識，則會引起通信量過大的問題。另外，每輪都更新分片內的節點，會造成許多額外開銷。

針對以上問題，研究者們提出分片共識組［17］的概念，其主要思想是篩選分片內的部分節點，構建共識組對交易進行驗證，這能有效降低通信開銷，同時啟用積分機制對節點表現進行評價，從而能夠高效甄別拜占庭節點，提高了系統安全性。

1.5 動態分片

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

2 環境假設

2.1 網絡模型

對于底層網絡，假設與其他方案一致［22-24］，并假設：1）誠實節點的網絡是良好連接的；2）誠實節點的通信通道是同步的，即一個誠實節點廣播一個消息，那么所有節點都能在一個已知的最大延遲?［25］內接收該消息。

2.2 威脅模型

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

3 DSSM 模型

針對傳統分片方案預定分片規模的靜態分片方式產生的性能缺陷與安全隱患，本文力圖實現一種樹型分層的自適應節點規模的分片可擴展模型，以提高分片區塊鏈系統在向外擴展時的魯棒性與自適應性。

3.1 狀態歸約思想

傳統分片方案中分片內的節點只會維護本分片的狀態，而狀態歸約思想鼓勵高性能的節點同步其他分片的狀態。當某個節點具有兩個及以上的分片狀態時，它就成了歸約節點。狀態同步且具有相同分片（至少兩個）狀態的節點集合構成了新的分片，稱為歸約分片。歸約分片與被同步狀態的分片之間構成了樹結構，如圖1 所示。

圖1 分片間的邏輯關系Fig.1 Logical relationship between shards

根據狀態歸約思想，處于父節點位置的分片（父級分片）中的節點將會存儲處于其孩子節點位置的分片（子分片）的所有狀態信息。在圖1 中，分片A處于分片B 與分片C 的父節點的位置上，分片B 和C分別處于兩個孩子節點的位置上。分片B 和C 中的白色節點分別同步了其兄弟分片的狀態而成了歸約節點，這兩部分白色節點同時具有分片B 和C 的狀態，它們共同組成了歸約分片A。對于分片B 和C 中的白色節點，它們的邏輯級別屬于分片A 這一級別。

3.2 DSSM 模型構建

在DSSM 中分片可以分為兩種：一種是基礎分片，它們是物理上的實際分片，與其他方案中的分片相似，每個基礎分片獨立驗證分片的事務；另一種是邏輯分片，又稱為歸約分片，它們是邏輯上的分片，不是實際的分片。在歸約分片中的節點，要在分片的動態調整中發揮作用，例如為節點的狀態同步提供相應數據、在分片動態調整過程中傳遞相應的消息等。

DSSM 模型使用分片歸約樹這樣的邏輯結構來控制分片的動態擴展。分片歸約樹是一個二叉樹的結構，如圖2 所示（彩色效果見《計算機工程》官網HTML 版），其中每個葉子節點代表的是一個基礎分片，而處于非葉子節點位置上的節點是邏輯分片（歸約分片），它們維護孩子節點所對應分片的所有狀態，并在分片動態調整時保證分片狀態的平穩過渡。

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

DSSM 考慮到節點的性能存在差異，因此通過激勵機制，鼓勵高性能的節點盡可能地同步兄弟分片的狀態，成為上層歸約分片中的節點，從而使得在分片動態調整時，相應的狀態信息不會丟失，分片也不至于因為狀態信息的不一致而導致癱瘓。

在整個網絡中，性能較好的節點處于DSSM 模型較上層位置，性能較差的節點處于DSSM 模型較下層位置。DSSM 還有一個基本原則就是所有歸約分片中的節點即使邏輯級別和狀態存儲各有不同，但在物理上它們都處于各自的基礎分片中，它們仍然需要承擔所屬基礎分片的交易驗證任務，這符合性能越好需要承擔的任務越多的設計理念。這樣的設計能夠較為充分地發揮節點的性能，從而提高整個區塊鏈網絡的性能。

3.3 DSSM 消息傳遞規則

由于DSSM 所有節點實際上都處于基礎分片中，節點同步更多的狀態只是為了在分片的動態調整中發揮更多的作用。歸約分片并不是真分片，是邏輯上的分片，是虛分片。同時，為了動態擴展的需要，每個基礎分片中也必然存在這樣的節點，它們處于各級的祖先分片中。

在DSSM 中的消息傳遞規則是所有的消息都在本分片內傳遞，這里的本分片既包括物理上的實際分片，也包括邏輯上的虛分片。

以圖3 為例，假設節點4 在分片C 中廣播消息，那么節點1、2 和3 就可以接收到消息，并分別將消息在分片Root、A 和B 中廣播。此時，消息在分片C 內部廣播的同時，也將近乎并行地在分片Root、A 和B中廣播。同樣地，節點7、10 和13 也會因為分片Root、A 和B 中的消息廣播而捕獲此消息，那么分片E、D 和F 也會接收到此消息。以此類推，父級分片的節點在廣播消息的同時，其子分片的節點也在近乎并行地廣播消息。因此，當某一節點在自己的分片中廣播消息時，全網的所有分片（包括基礎分片和歸約分片）也在近乎并行地廣播消息，這大大提高了消息的傳遞效率。

圖3 消息傳遞規則Fig.3 Messaging rules

4 DSSM 分片自適應擴展設計

DSSM 實行狀態分片，并以存儲狀態為依據將節點進行邏輯分層。

4.1 歸約樹邏輯結構初始化

一般地，為了更好地兼容未實施分片的區塊鏈系統，DSSM 的分片初始化由單個分片（稱為根分片Root）開始。未分片的區塊鏈網絡可以視為網絡中只有單個分片。

1）當Roo（t對于未實施分片的區塊鏈，Root 包括其所有節點）中的節點數超過上限閾值O時，便可以開始分片的分裂。

2）由于存在分片分裂之后產生的兩個子分片的節點數依然超過上限閾值O的情況，因此每次分裂后形成的子分片的節點繼續按照步驟1）中的標準判斷所在子分片是否滿足分片分裂條件，若滿足，則可以執行相應的分片分裂過程。

3）執行步驟2）中的過程，直到節點檢測到所在子分片的節點數不超過O為止。

4.2 分片的全網分裂

4.2.1 分裂條件

1）節點發起分裂請求提案的條件

當基礎分片內任一節點發現分片的節點數已經超過上限閾值O，并且它能夠提供其所處基礎分片滿足分片分裂條件的證明時，就可以發起分裂請求提案。

2）全網分片分裂條件

當全網分片分裂后不會導致某些新分片的節點數低于T且超過1/2 的分片響應分裂時，可以開始全網分片的分裂。

3）單個分片分裂條件

當基礎分片中的節點就是否響應分裂進行PBFT 共識時，每個節點除了需要在消息中注明是否響應，同時需要注明是否愿意留在當前分片內成為歸約節點，即是否愿意同步兩個基礎分片的狀態（在分裂完成后，當前分片處于歸約樹中非葉子節點的位置，它在邏輯上已經屬于歸約分片，分裂產生的新分片處于新的葉子節點位置上，它們是新的基礎分片）。在對響應分裂達成共識的情況下，只有愿意留在當前分片內的節點數大于等于T，基礎分片才可以將響應消息向上傳遞。

4.2.2 分片的分裂過程

4.2.2.1 請求階段

基礎分片內某一節點發現分片的節點數已經超過了O，它便發起分裂請求提案。該提案包括其所屬基礎分片滿足分裂條件的證明、請求編號以及它的數字簽名。

4.2.2.2 預準備階段

分裂請求提案一經提出，便會在發起提案的節點所屬的基礎分片內廣播，該基礎分片的祖先分片中的節點便可以捕獲這個提案，然后捕獲提案的節點作為當前其所在的歸約樹中最高級別分片PBFT共識的主節點，執行PBFT 共識，目的是就該提案是否可以執行達成一致。以圖3 為例，假設分片C 中的節點發起分裂請求提案，分片Root、A 和B 中的節點1、2 和3 若是捕獲到該提案，則其便作為主節點在相應分片內開始PBFT 共識。

若是達成一致性共識，則先向另一個非提案來源的子分片廣播一致性結果和提案，再由該子分片向它的所有子分片傳遞一致性結果和提案。以此類推，直到傳遞至基礎分片。以圖3 為例，對于分片A中的節點，它們接收的提案來自分片C，也就是分片B 這一分支，則在分片A 達成一致性共識的情況下，分片A 中的節點要主動將一致性結果和提案傳遞給另一分支即分片D，再由分片D 繼續向下層擴散傳遞。同樣地，對應圖4 中的分片Root 和分片B，它們要分別傳遞一致性結果和提案給分片F 和分片E，再由F 和E 繼續向下傳遞，其中箭頭上的標注代表傳遞過程中一致性結果的來源。

圖4 預準備階段的消息傳遞路線Fig.4 Messaging routes of pre-prepare phase

若是在某一級分片達不成一致性共識，則該分片的主節點要向其子分片傳遞拒絕請求消息。拒絕請求消息傳遞路線如圖5 所示。

圖5 拒絕請求消息傳遞路線Fig.5 Reject request messaging routes

仍以圖3 為例，若是分片Root 沒有達成一致性共識，則主節點會向來源分片（分片A）傳遞拒絕請求消息，消息的傳遞路線如圖5（a）所示。若分片A沒有達成一致性共識，則拒絕請求消息的傳遞路線如圖5（b）所示。對于分片B，拒絕請求消息的傳遞路線如圖5（c）所示。對于來源分片，例如圖5（a）中的分片A，則需要向其所有子分片傳遞拒絕請求消息，以此類推，直到基礎分片。這是因為拒絕請求的分片在發現請求需要被否決時，來源分片可能已經達成一致性共識并將結果傳遞給下級分片。

4.2.2.3 準備階段

預準備階段通過消息的并行傳遞可以使一致性結果和分裂請求提案傳遞到各個基礎分片。此時，若是某基礎分片中不屬于歸約分片的節點捕獲到傳遞來的一致性結果，它便作為該基礎分片中PBFT 共識的主節點執行PBFT 共識，其目的是就是否響應分片分裂達成一致性共識。在基礎分片達成共識后，將結果向上傳遞給根分片Root。

與此同時，Root 在預準備階段達成一致性共識后，便開始使用VRF 來確定分裂的啟動者。在啟動者確定后，設置超時時間，等待并收集基礎分片的響應消息。若收集到超過1/2 的來自基礎分片的同意響應的消息，則開始分裂的執行階段。

4.2.2.4 執行階段

1）分裂過程相關參數的確定

分裂啟動者一旦收集到超過1/2 的來自基礎分片的同意響應的消息，并且全網分片分裂后不會導致某些新分片的節點數低于分片節點數的下限閾值T，它就作為分裂決策共識（共識節點集合是Root 中的全部節點）的主節點發起分裂提案，提案中包括分裂過程中相關參數的一些設定，包含VDF 所需的時間參數t、安全參數λ和啟動者產生提案的當前時隙C以及參數z（將C時隙之后第z個區塊的哈希值作為VDF 的隨機性輸入x）。

若根分片Root 沒有對分裂提案達成共識，則依據多輪驗證的思想，重新通過VRF 算法選擇新的啟動者進行新一輪的分裂決策共識，直到達到共識輪數上限仍未達成共識才放棄此次分裂過程。

若在分裂決策共識中分裂提案被同意，則分片Root 中的節點便將一致性結果向下傳遞，直至傳遞到所有基礎分片。

2）節點隨機數的生成

在基礎分片中的節點接收到分裂決策共識的一致性結果后，便可以按照相關參數生成隨機數。DSSM為了對抗Sybil攻擊以及避免可能存在的惡意節點相互串通而提前計算符合它們要求的隨機數的情況，采用VDF+VRF的方式來生成各個節點的隨機數。

算法1節點隨機數生成算法

3）節點分配

每個節點以產生的隨機數與分裂后的子分片數量（這里取2）為參數，通過跳躍一致性Hash 算法得到其分裂之后所在的子分片編號。

4.2.3 分裂過程中的特殊情況

在分片的分裂過程中，有可能會出現單個分片因為某種因素不再滿足分裂條件的情況，即分片分裂后新分片的節點數低于T或分裂前分片中的節點數就已經小于T，這兩種情況都對分片的安全性造成了威脅。對此，提出復用和降級兩種相應的處理策略。

1）復用

針對分片分裂后新分片的節點數低于T的情況，選擇在分片內復用節點的策略。當出現上述情況時，如果有歸約節點愿意同時作為兩個新的子分片的節點存在并且同時負責處理兩個子分片的事務，則該節點被定義為復用歸約節點，如圖6（a）中的節點1 和2 所示。

圖6 節點復用與分片降級Fig.6 Node reuse and sharding degradation

節點復用的條件如式（1）所示：

當分片內的節點發現上述情況時，開始在分片內廣播復用詢問消息，此時該節點成為分片中的源節點。當分片內的其他節點接收到此消息時，若是同意作為復用歸約節點而存在，則廣播發送復用確認消息。

在源節點發送復用詢問消息后，開始準備收集確認消息。在源節點收集到足夠多的確認消息后，便在本分片（分裂前的分片）內廣播復用消息，此消息內包含已確認的復用節點名單的信息。

普通節點繼續執行分片分裂過程，復用歸約節點不必繼續執行此過程，屬于它們的分裂過程已經結束，生成的隨機數也隨之作廢。

2）降級

節點降級的條件如式（2）所示，待分裂的分片中的節點數量已低于T：

此時，即使該分片中所有的節點都成了復用歸約節點，也無法滿足兩個子分片中基本節點數的要求。在這種情況下，采取此分片分裂中止并降級的策略。當分片中的節點發現上述情況時，便按照消息的傳遞規則將降級證明消息傳遞給全網分片，此消息包含本分片滿足降級條件的證明。同時，接收到該消息的本分片節點停止分裂過程，整個分片整體降級。

如圖6（b）所示，分片A 中的節點數量小于T，那么在分裂過程中采取的策略是分片A 中的節點在物理上整體下移至分片B 中，具體下移至左子分片還是右子分片，可根據實際情況而制定相應的規則。分片B 作為新的基礎分片，與其他分裂后產生的新分片同處于歸約樹葉子節點的位置。分片B 的兄弟節點的位置原本也應該有一個基礎分片C，只是因為分片降級的問題導致該分片是空分片。此時，分片A 與分片B 實際上是一個分片，它們的節點集合是一樣的，但是它們在歸約樹中占據兩個節點的位置。

4.3 分片的全網合并

分片在正常情況下可能會因為某些原因而導致大批節點宕機，造成分片內節點數過少，從而使得分片的安全性和去中心化程度大大降低。為此，采用分片合并策略。

4.3.1 合并條件

1）節點發起合并請求提案的條件

當基礎分片內任一節點發現分片的節點數已經低于下限閾值T并且能夠提供所處基礎分片滿足分片合并條件的證明時，便可以發起合并請求提案。

2）全網分片合并條件

當超過半數的分片響應合并時，開始全網分片的合并。

4.3.2 分片的合并過程

4.3.2.1 請求階段

類似于分片分裂的請求階段，在滿足相應條件后，節點可以發起合并請求提案。與分裂請求提案不同的是，該提案中要含有該節點所屬的基礎分片滿足合并條件的證明以及合并請求編號。

4.3.2.2 預準備階段

合并請求提案一經提出便在發起提案的節點所屬的基礎分片內廣播，該基礎分片的祖先分片中的節點便可以捕獲這個提案。與分裂過程類似，捕獲提案的節點作為當前其所在的分片歸約樹中最高級別分片PBFT 共識的主節點，執行PBFT 共識。

若是達成一致性共識，則向另一個非提案來源的子分片廣播一致性結果和合并請求提案，消息的傳遞規則與分裂時的預準備階段一致，傳遞路徑如圖4 所示。

若是某一級分片達不成一致性共識，則由該分片的主節點向其子分片傳遞拒絕請求消息。消息的傳遞路徑與分裂時的預準備階段一致，傳遞路徑如圖5 所示。

4.3.2.3 準備階段

類似于分裂的準備階段，若是基礎分片中不屬于歸約分片的節點捕獲到父級分片傳遞的一致性結果和合并請求提案，它便作為該基礎分片中PBFT 共識的主節點執行PBFT 共識，就是否響應分片合并進行共識。在基礎分片達成共識后，將結果向上傳遞給根分片Root。

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

4.3.2.4 執行階段

1）合并決策共識

合并啟動者一旦收集到超過1/2 的來自基礎分片的同意響應的消息，就作為合并決策共識（共識節點集合是分片Root 中的全部節點）的主節點發起合并提案，就是否進行全網合并進行共識。合并啟動者發起的提案中必須包含其所收集的超過1/2 的來自基礎分片的同意響應的消息。

若分片Root 沒有對合并提案達成共識，則與分裂時一致，采用多輪驗證思想繼續選擇啟動者進行流程。

若在合并決策共識中提案被通過，則分片Root中的節點便將達成的一致性結果向下傳遞，直至傳遞到所有基礎分片。

2）合并執行

當處于歸約樹倒數第2 層的分片中的節點收到分片Root 傳遞的一致性結果時便開始狀態同步過程，將自己目前所保存的兩個基礎分片的狀態同步給自己所處的基礎分片的非歸約節點（也就是未同步其他分片狀態的節點）。此時，原來的只在基礎分片中的節點便成為其父級分片中的待同步節點。原來的歸約樹倒數第2 層的分片變成了新的基礎分片。

4.4 節點分配算法

在父級分片分裂為兩個子分片的過程中，對于其中的節點，采用跳躍一致性Hash 算法［26］來決定其將進入哪個子分片。跳躍一致性Hash 算法具有均勻性與一致性兩個特點。

節點分配算法具體如下：

在DSSM 中，由于只需要將父級分片分裂為兩個子分片，對應于節點分配算法，則相當于只需要增加一個新的槽位，因此n的取值為2 即可。當節點提供的隨機數為參數k、分片數目為參數n時，ch（k，n）的返回值為節點所劃分到的子分片。本文規定：返回值為0 的節點屬于左子分片，返回值為1 的節點屬于右子分片（當n為2 時，只有0 和1 兩個返回值）。

4.5 激勵機制

DSSM 鼓勵性能較高的節點同步其所在分片的兄弟分片的狀態，從而使高性能的節點成為更高級別的歸約節點。若想促使節點積極地參與狀態歸約，則需要激勵機制驅動。

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

具體的激勵機制需要匹配具體的網絡環境和相應的項目，在此不再贅述。

5 安全性分析與參數設置

5.1 安全性分析

由于DSSM 結合多輪共識模型進行驗證，因此需要結合多輪共識模型進行分析。

5.1.1 共識的安全性分析

對于采用PBFT 算法作為共識機制的區塊鏈網絡而言，一旦拜占庭節點的比例超過2/3，根據威脅模型：若拜占庭對手沒有獲得發布區塊的主節點的身份，則它會選擇遵守協議不作惡；若拜占庭對手獲得了發布區塊的主節點的身份，則它就可以輕易地發起雙花攻擊或發布錯誤的鑄幣交易，最終導致數據的不一致?？紤]最壞的情況，即一旦拜占庭對手控制了共識節點中超過2/3 的節點，那么它就可以發起合謀攻擊，在區塊中發布錯誤事務。

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

圖7 合謀攻擊代價Fig.7 Cost of collusion attack

由圖7 可以看出，隨著分片內節點數的增多，攻擊者要想使其發動合謀攻擊的概率超過百萬分之一，需要控制的節點數也會隨之增加，并且近似于線性增加。分片內節點數越多，攻擊者發動合謀攻擊所付出的代價越大，分片也越安全。

由數據計算而得，若合謀攻擊的概率超過百萬分之一，則需要攻擊者至少控制分片的將近1/2 的驗證節點。這也意味著：若分片內節點數翻倍，則攻擊者進行攻擊的代價至少也要翻倍。

5.1.2 節點隨機數的可靠性分析

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

所有驗證節點以VDF 的結果作為VRF 的Evaluate（SK，X）函數的隨機性輸入X，再使用自己的私鑰作為輸入SK，那么通過計算便可獲得屬于節點自己的可驗證的可靠的隨機數。

5.1.3 分片的安全性分析

根據節點隨機數的可靠性以及節點分配過程的隨機性和不可預測性，拜占庭對手很難再主動地將拜占庭節點聚集到某些固定分片內。

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

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

由式（3）可以得出，在分片歸約樹的第2 層分片中的拜占庭節點比例只有1/4，已經可以滿足大多數分片協議的容錯率，越往上層，比例越低。另外，由于多輪共識模型中多輪驗證與欺詐證明的存在，因此拜占庭對手在第0 和1 層分片作惡成功的概率極低。

在DSSM 中，每個基礎分片的祖先分片中的節點都會存儲該基礎分片的狀態，并能對該基礎分片中的區塊信息進行驗證。同時，基礎分片的各級祖先分片中幾乎包含所有基礎分片的節點，因此拜占庭對手想要發起攻擊而不被發現無異于要控制整個系統。

狀態歸約與冗余可以使拜占庭對手攻擊單個分片，作惡成功的代價無異于攻擊整個區塊鏈網絡。同時，由于各級歸約節點的存在，拜占庭對手在分片動態調整過程中的惡意行為也很容易被檢舉，因此分片的安全性得到了保障。

5.1.4 數據的一致性分析

狀態歸約的存在使得上層分片的節點需要存儲其孩子分片的狀態。一個分片的狀態不僅被本分片內的節點存儲，而且還會被其所有的祖先分片的節點存儲。一個分片的狀態會有多個備份。

當有新的節點加入分片時（下層節點通過狀態歸約加入歸約分片或者新加入網絡的節點進入基礎分片），原分片中的節點與該分片的祖先分片中的節點都可以向新節點同步狀態，并且由于在該分片或其祖先分片中存在多個該分片的狀態備份，新節點可以快速同步到該分片的最新狀態。

參與共識的驗證節點必須同步到最新的分片狀態，這樣才能保證共識正常進行，確保一致性。若因為性能或網絡原因，導致節點總是無法及時同步到最新狀態，該節點可以選擇自行降級，在下一級分片中工作，這也符合DSSM 的設計理念。

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

本節結合多輪共識模型探討DSSM 中參數T和O的取值。

5.2.1 分片節點數下限閾值T的確定

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

根據上文分析，若拜占庭對手想對有150 個節點的分片發動合謀攻擊，要使合謀攻擊的概率超過百萬分之一，則至少需要控制約1/2 的節點，但其收益遠遠低于其所付出的代價（即使控制了1/2 的節點也有很大概率攻擊失?。Ｒ虼?，考慮設定下限閾值T為150。

5.2.2 分片節點數上限閾值O的確定

由于分裂時子分片是由父級分片一分為二得到的，則父級分片節點數的上限閾值O需要滿足：父級分片分裂之后，其子分片內的節點數仍需滿足最低運行標準，即子分片內的節點數仍然大于等于T，那么O至少要滿足的條件是O≥2T。

在多輪共識模型下，即使分片內節點數達到了600，共識仍然可用。另外，考慮到多分片并行可以提高吞吐量。為兼顧網絡的整體性能，分片內的節點數不宜過多。因此，在多輪共識模型下設定上限閾值O為600。

6 模擬驗證

模擬實驗將驗證DSSM 可以隨著節點數量的大幅增多實現分片規模的動態擴充，以提供更好的性能，同時在節點顯著減少時，DSSM 可以為了分片的安全，動態地收縮分片的規模。選用Linux 系統作為開發平臺，以Go 語言作為開發語言，以VS Code 和Docker 作為開發工具，進行模擬實驗。

6.1 實驗假設

1）測試網絡中節點間的通信狀況良好，延遲在可容忍范圍內。

2）不考慮由于交易分片導致的分片負載不均衡的問題，即每個基礎分片在同一個時間段內需要處理的交易是相對均勻的。

3）系統的拜占庭節點比例為0.33。

4）隨著模擬時間的推移，節點的表現可以發生變化，即原本的正常節點可以表現為拜占庭行為，但是系統中表現拜占庭行為的節點的比例不變。

5）節點可以動態加入或退出系統。

6）拜占庭節點秉承對自己最為有利的方式執行操作。

6.2 DSSM 可行性測試

從測試系統的一個初始狀態開始，隨著時間的推移，逐步往系統中添加或減少節點來模擬節點加入或退出系統的情況，同時逐步往系統中注入交易，觀察系統的吞吐能力隨著時間的變化情況。在其他外部條件不變的情況下，網絡中分片規模的變化可以通過吞吐量的變化體現出來。通過吞吐能力的變化來驗證DSSM 能夠根據節點環境自適應地調整分片的規模。

為能夠模擬DSSM 中分片分裂過程的各種情況，進行了如下設置：

1）初始狀態的系統內有600 個節點，正好是分片的上限閾值O的值。

2）在第10 個時隙時，在系統中加入400 個節點，滿足分片分裂條件，觀察系統正常分裂情況下的吞吐能力的變化。

3）在第45 個時隙時，在系統中再加入400 個節點，每個分片內有700個節點。然后，在第57個時隙時減少某個分片的節點數至200來模擬節點復用情況。

4）在第75 個時隙時，在系統中加入1 100 個節點，使得每個分片的節點數都達到500 個。在第90 個時隙時，在系統中加入1 200 個節點，此時每個分片的節點數都達到了800。在第103 個時隙時，減少某個分片的節點數至100 來模擬分片降級情況。在第120 個時隙時，將系統恢復至3 200 個節點的狀態。

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

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

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

由圖8 可以看出，系統吞吐能力隨著節點數量的增多得到了增強，而且是近乎翻倍的增強。由圖9可以看出，當節點數量大幅減少時，系統吞吐能力有所下降。結合圖8 與圖9 驗證了DSSM 可以根據不同的節點環境，動態快速地調整網絡中分片的規模，從而實現了在保證基本安全要求的情況下，自適應快速地進行分片規模的調整，滿足系統性能更好的目標。

6.3 可擴展性對比實驗

設置結合DSSM 的多輪共識模型與未結合DSSM 的多輪共識模型的吞吐量對比實驗，以驗證DSSM 能夠在節點數量滿足條件時具有更好的可擴展性。

在初始狀態下，兩種模型各有兩個分片，每個分片的節點數均為500。然后在第5 個時隙時向環境中加入節點，使得每個分片的節點數達到700，觀察系統的吞吐能力隨時間變化的情況，如圖10 所示。

圖10 可擴展性對比Fig.10 Scalability comparison

由圖10 可以看出，隨著節點數量的增多，在一段時間后，采用DSSM 的系統吞吐量有明顯的提升，而未采用DSSM 并沿用傳統靜態分片方式的系統吞吐量卻并未隨著節點數量的增多而得到較大改善。

因此，在區塊鏈運行過程中，DSSM 可以隨著節點數量的增多，動態自適應地擴展分片的規模，以提高網絡的性能和可擴展性。

6.4 時延對比實驗

設置結合DSSM 的多輪共識模型與未結合DSSM 的多輪共識模型的交易時延對比實驗，以驗證DSSM 能夠在節點數量大幅減少時，通過自適應地收縮分片的規模來保證網絡的活性與安全性。

在初始狀態下兩種模型各有兩個分片，每個分片的節點數是150，然后在第5 個時隙時在環境中減少節點，使得每個分片的節點數達到80，觀察系統的交易時延隨時間變化的情況，如圖11 所示。

圖11 交易時延對比Fig.11 Transaction latency comparison

由圖11 可以看出，當節點數量大幅減少時，采用DSSM 的系統和未采用DSSM 的系統都出現了時延增加且不穩定的情況。這是因為分片內的節點數量變少，拜占庭節點進入共識組的概率會大大增加，導致交易的驗證需要更多輪次的共識，所以時延也就升高了。采用DSSM 的系統在一段時間后，時延會慢慢降低，逐步恢復到節點減少之前的狀態并穩定下來，而未采用DSSM 并沿用傳統靜態分片方式的系統交易時延依舊偏高且很不穩定。

因此，在區塊鏈運行過程中，當節點數量大幅減少時，DSSM 可以通過動態自適應地收縮分片的規模來保障網絡的活性與安全性。

7 結束語

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

本文提出的基于狀態歸約的自適應節點規模的動態分片可擴展模型還有一些地方需要進一步完善。例如，模型中的參數在面對不同的環境和不同的共識機制是不一樣的，這與系統的安全要求有關。另外，本文考慮的是一個整體系統的擴展與收縮，尚未針對單個分片的突發情況進行詳盡討論。這些都將是下一步研究的重點內容。