DAGGraph:適合移動自組網的區塊鏈

張文韜，黃建華，顧 彬，寧宇豪，宮在為

華東理工大學 信息科學與工程學院，上海 200237

移動自組網（mobile ad hoc networks，MANET）是一種具有自組織能力、可快速部署的特殊類型物聯網（Internet of things，IoT），它無需固定基礎設施的支持，在軍事戰場、緊急救援和環境勘探等特殊環境中應用前景廣闊。在執行任務的過程中，MANET 的節點之間需要通過無線信道傳輸數據和通過操作指令進行協同，這些數據和操作指令存在多種安全風險且容易受到攻擊。因此，維護MANET數據的機密性、完整性和真實性顯得非常重要。

區塊鏈是一種在計算機網絡節點之間共享信息的分布式數據庫，它以區塊的形式組織搜集的信息，通過密碼學將區塊之間鏈接在一起，以確保數據的不變性。作為一項新興的技術，區塊鏈為分布式系統提供了去中心化和防篡改的能力，確保了數據的真實性和完整性。一些學者嘗試利用區塊鏈來解決物聯網的安全問題。Islam 等人[1]提出使用基于區塊鏈的智能合約，實現了移動節點間機器學習模型的安全共享；Abishu[2]與Hassija[3]等學者提出將交易數據上鏈，實現移動節點間以及移動節點與固定節點間安全的能源交易。

然而，由于MANET 的移動性會引發網絡拓撲的動態變化，將區塊鏈與MANET 相結合面臨不少挑戰。Laube 等人[4]首次探討了移動性引發的網絡拓撲變化問題，提出了應對MANET分裂和合并問題的解決方案，從理論上證明了在MANET中應用區塊鏈技術的可行性。但該方案采用被動的方式檢測網絡拓撲的變化，存在效率較低下、網絡延遲等問題，并且未就檢測網絡分裂提出有效的解決方案。Block-Graph[5-6]將基于有向無環圖（directed acyclic graph，DAG）的區塊鏈模型應用于MANET，重新設計了區塊的數據結構和Raft共識算法，解決了傳統區塊鏈在MANET 分裂和合并下產生的問題，保證了數據的正確性與完整性。但是該模型的共識時延易受到節點數量的影響，在大規模的集群下共識效率不高。雖然以上工作取得一些進展，但是將區塊鏈應用于MANET 仍然存在以下問題需要解決。首先，不同類型的任務往往要求移動節點或分散或聚集地開展工作，需設計高效的分簇算法，使得節點快速分簇的同時有效控制簇內節點的數量；其次，受到環境和任務變化等因素的影響，網絡的結構將進行分裂和合并等動態調整，而網絡的分裂將引發區塊鏈的分叉，在網絡合并后需合理地處理這些分叉；最后，節點的通信信號易受到山體、樹木和建筑物等大型物體的干擾，在此環境下，節點間傳遞區塊所需的控制和驗證信息極易丟失。

針對以上問題，本文解決問題的思路是采用DAG結構來適配移動性引發的網絡拓撲的變化，以解決區塊鏈分叉問題；通過簇首控制簇節點密度，以限制入簇節點數量，確保簇的性能；簡化出塊和驗證流程，減小數據丟失對區塊上鏈所帶來的影響。提出一種基于DAG 結構的系統模型DAGGraph，以有效地控制每個簇的規模，提高分簇的速度，實現網絡合并后區塊鏈分支的安全恢復，通過簡化上鏈流程提高共識速度，增加系統的吞吐量和魯棒性。本文的貢獻如下：

（1）提出簇節點密度（數量）限制算法，有效地解決了一個簇的節點數量不受控增加所引發的性能下降問題。

（2）針對網絡分裂和合并引發的網絡拓撲的變化，提出基于簇首間數據同步的區塊恢復算法，在網絡合并后由原簇首交換并同步產生的區塊分支，實現對區塊分支的恢復，以保留所有節點產生的合法區塊。

（3）提出一種簡化的區塊上鏈算法，簡化了區塊的上鏈流程，節點僅需對收到的區塊進行本地驗證即可完成上鏈操作，增強了系統的健壯性。

1 相關工作

分簇算法可以解決MANET 中節點資源開銷大、可擴展性不高等問題。分簇算法將平面網絡結構中鄰近的節點組成一個簇，一個簇包含一個簇首和若干個簇成員節點，簇首與簇成員協同執行任務。運行分簇算法的節點周期性地發送控制信息，這些控制信息用來進行簇首選舉、節點入簇和節點移動等操作。最小ID分簇算法[7]是較早提出的分簇算法，該算法要求每個節點擁有唯一的ID，在網絡初始化階段，節點周期性地向其他節點廣播自己的ID，節點通過比較收到的ID，選擇ID 最小的節點作為網絡的簇首。最小ID 分簇算法的一個顯著特點是算法的收斂性高，實現簡單。陳志軍等人[8]對最小ID分簇算法進行了改進，將剩余電量和節點相對移動速度作為簇首選舉的參考因素，使節點能耗更均衡，網絡拓撲更穩定。受到外部環境因素的影響，在實際應用中，節點的移動方向、速度等特性在一定程度上具有某種規律。通過設計合理的數學模型，可以預測節點在某一時間段內的移動特性，降低分簇算法的開銷。宋人杰等人[9]指出移動節點具有分組移動的特性，通過計算得出節點的移動特性并進行分簇，同時將節點性能作為簇首選舉的參考因素以提高系統性能。陳宇等人[10]基于衛星節點運行軌跡的可預測性，將簇的初始化階段交由可信的地面終端完成，簡化了分簇算法的復雜度，提高了網絡的穩定性。吳振華等人[11]根據車輛移動位置的可預測性，按路段將城市道路劃分成簇，通過車輛節點的實時位置預測移動趨勢，降低了分簇算法的路由發現及分簇的開銷。MANET 的節點基于無線方式通信，存在消息泄露風險，網絡拓撲易受到攻擊。崔朝陽等人[12]根據MANET 的特點，提出安全分簇算法。該算法通過證書交換，確?？尚殴濣c加入網絡，通過協商會話密鑰，完成對信息的加密，提高了分簇算法的安全性。

基于DAG 的區塊鏈可以實現區塊并發寫入，且能較好地解決由網絡分裂引起的區塊鏈分叉問題，受到研究人員的廣泛關注。使用DAG結構的區塊鏈項目主要有Nano（https://nano.org/en/whitepaper）、Byteball（https://byteball.org/Byteball.pdf）、IOTA（http://tanglereport.com/wp-content/uploads/2018/01/IOTA_Whitepaper.pdf）、DagCoin（https://dagcoin.org/whitepaper.pdf）等。DAG 賬本的每一個子單元可以引用驗證多個父單元，一個父單元也可以被多個子單元驗證，這種驗證關系在提高交易確認速度的基礎上確保了DAG賬本的安全性和可靠性。為了解決由多分支合并引起的交易沖突問題，GHOST[13]提出主鏈選擇協議，對于兩個沖突的交易，將位于主鏈上的交易視為有效。然而GHOST協議將丟棄主鏈以外的交易，造成對算力的浪費。Conflux[14]和Inclusive[15]基于GHOST主鏈選擇協議，將節點產生的所有交易都視為DAG賬本的一部分，并根據主鏈對交易進行排序，解決了交易沖突問題。安全性是移動自組網所面臨的又一個問題，針對節點的惡意攻擊會給MANET帶來不可預測的風險和損失。其攻擊類型主要包括物理攻擊、惡意竊聽、洪泛攻擊[16]、拒絕服務攻擊、雙花攻擊和女巫攻擊[17]等。區塊鏈具有分布式、防篡改等特點，但與移動自組網相結合的區塊鏈也容易受到來自外部和內部的攻擊。一些學者對于如何提高區塊鏈系統自身的安全性進行了研究。李忠誠等人[18]根據區塊鏈中誠實節點與惡意節點之間的博弈，提出了一種激勵和押金機制。規定每個參與驗證的節點都需要繳納押金，參與共識的誠實節點將按繳納的押金比例獲得獎勵，同時惡意節點會被扣除押金，以此激勵節點理性共識，限制惡意行為。季鈺翔等人[19]引入信任度評估機制，通過對鄰居節點行為的監督，以有效檢測惡意節點，同時引入工作量證明和押金機制來限制女巫攻擊，保證區塊鏈網絡的安全性。英特爾軟件保護擴展（Intel software guard extensions，SGX）[20]利用可信硬件提供安全容器，以確保安全容器中加載的代碼和數據不能被外界篡改，提高了區塊鏈的安全性。

在移動自組網環境中，節點的頻繁移動會引起網絡拓撲變化，當節點間的距離超出通信范圍時，網絡會分裂；節點連接恢復后，網絡將合并。分簇算法增加了MANET 組網的靈活性，提高了網絡的性能，然而節點間靈活的組網能力也為區塊鏈在MANET上的應用提出了不小的挑戰。傳統的單鏈式區塊鏈根據最長鏈原則，將丟棄由網絡分裂產生的分支，從而造成正常的數據丟失。區塊圖[5-6]將DAG結構應用于MANET，為區塊鏈應對網絡分裂和合并帶來的問題提供了解決方案。當網絡分裂成兩個子網后DAG分叉，各子網在自己的分叉上獨立地產生區塊并上鏈；當網絡合并后，啟動區塊恢復程序，恢復由其他子網產生的區塊。區塊圖基于每個子網中的領導者節點完成日志復制和區塊恢復等過程，然而區塊圖并未就網絡的分裂和合并等拓撲變化給出具體的檢測方案。Laube 等人[4]提出了一種被動檢測網絡拓撲變化的方案，指出網絡的出塊速度應根據節點的數量動態變化，并給出了優化的方向。然而基于被動的方式可能造成網絡延遲。

2 DAGGraph

2.1 系統模型

節點的移動性會引發網絡拓撲的動態變化，如何確保使用區塊鏈運行的任何應用在移動自組織網絡中保持一致是本文需要解決的關鍵問題。移動自組網的特點是移動節點間連接的穩定性通常不及固定節點，節點的無線通信范圍有限且易受環境因素的影響，節點因執行任務移動到不同位置或外部干擾會造成連接中斷，引發網絡分裂，形成幾個稱為簇的獨立分區，分區內的節點可以相互通信，但分區之間彼此不能直接通信。當任務發生變化后，分裂的簇又會逐漸靠近，合并成一個網絡。

區塊鏈通常假設網絡是穩定的并且具有良好的可用性。這些假設不適用于可能出現網絡分區的移動自組網，因為網絡的分裂和合并都會引發網絡拓撲變化，給區塊鏈網絡維持數據一致性帶來挑戰。在部署區塊鏈的移動自組網中，當網絡出現分區時，不同的簇之間不能直接通信，全網節點無法達成整體共識。要確保網絡分區后區塊鏈能繼續提供服務，不同的簇會獨立共識以延展區塊鏈，從而引發區塊鏈分叉。當網絡再次合并時，要確保數據保持可用和一致，傳統區塊鏈會將多余的分支進行修剪，僅保留最長鏈分支。刪除分支會刪除許多有用的數據，引起數據丟失，這是不接受的。

針對以上問題，本文采用DAG 結構來適配移動性引發的網絡拓撲的變化，以保留網絡分裂階段各簇獨立產生的區塊鏈分支，并通過簇首處理區塊的恢復和同步問題，提出一種基于DAG 結構的系統模型DAGGraph，如圖1所示。

圖1 DAGGraph系統模型Fig.1 DAGGraph system model

圖1 反映了網絡運行過程中網絡拓撲的動態變化，網絡分裂后形成多個簇（分區），由于通信距離有限，各簇間無法直接通信。每一個簇由一個簇首和多個成員節點組成，同一簇內的節點具有相同的出塊權，均可在屬于本簇的DAG 分支上產生區塊。如圖1所示，節點移動后網絡中產生A與B兩個簇，簇A的節點和簇B 的節點在各自的DAG 分支上產生區塊，兩個分支可在網絡合并后由舊簇首恢復給所有成員節點，同時由新簇首負責生成合并塊以收斂此前產生的DAG分支。

系統基于私有鏈運行，可信證書授權機構（certificate authority，CA）為每一個參與節點頒發證書。節點之間通過互換各自的證書，相互驗證，未被授予證書的節點將不被允許加入系統。節點間的消息傳輸采用會話密鑰加密傳輸，會話密鑰采用密鑰交換技術協商產生，以確保安全性。

本文將區塊鏈與移動自組網相結合需要解決的問題簡化為三個：分簇管理問題、共識問題和區塊恢復問題。分簇管理主要基于分簇算法形成簇結構，處理網絡初始化和維護簇結構，通過引入加密機制支持每個加入簇的節點與鄰居節點協商會話密鑰，確保數據安全傳輸。區塊管理模塊由共識模塊和區塊恢復模塊組成，其中共識模塊允許每個簇獨立地產生區塊，區塊恢復模塊負責網絡合并后恢復由不同簇產生的區塊。

2.2 分簇管理

MANET 被廣泛應用于搶險救災、地質勘探和水文觀測等領域，這些應用場景往往根據任務形式和物理環境的不同，要求節點分散地開展任務。然而受到通信距離的限制，MANET 節點的分布不宜過于松散，節點間的遠距離通信造成網絡的不穩定連接將頻繁引發數據丟包和數據包重傳，大大增加通信能耗。利用分簇算法，將松散分布的節點聚集成簇，可在一定程度上緩解此類問題。然而，現有的分簇算法大都基于地理位置對集群進行分簇，若某一位置的節點數量過多，極易造成一個簇內的節點密度過高，節點間的頻段干擾以及帶寬占用等問題將嚴重影響節點間的通信效率。因此，本文設計了一種高效的分簇管理機制，包括分簇和簇首選舉模塊、簇結構維護模塊、拓撲變更檢測模塊、會話密鑰協商模塊等。該機制以簇的形式組織MANET節點，以發揮MANET 節點的團隊協作優勢，提高工作效率，降低通信能耗。

如圖2所示，分簇管理機制中的節點包含五種節點狀態：未定狀態、游離狀態、成員狀態、簇首狀態、簇首隱藏狀態。其中未定狀態為每個節點啟動后的初始狀態；游離狀態表示節點未發現鄰居節點。簇首選舉基于加權分簇算法，該算法綜合考慮了節點性能、網絡帶寬、剩余電量等因素，選舉綜合素質最高的節點進入簇首狀態。簇內的節點狀態為成員狀態，處于簇首狀態和成員狀態的節點動態維護簇成員表。此外，為了減小網絡通信負擔，本文為簇首設計了控制簇內節點數量的機制，當簇內節點數量過多，簇首轉為隱藏狀態，此時簇首不再允許新節點加入簇。

圖2 節點狀態轉換圖Fig.2 Node state transition

基于節點靈活移動的特性，分簇管理的任務如下：網絡初始化、節點加入、節點退出、節點移動等。為了更加高效地檢測網絡拓撲變化，本文還定義了兩種拓撲狀態：拓撲變化狀態、拓撲穩定狀態。初始階段節點都處于拓撲變化狀態，待節點檢測到分簇完成后轉為拓撲穩定狀態。

2.2.1 網絡初始化

網絡初始化即簇結構的初始化：將網絡中物理距離接近的節點劃分成包含一個簇首和多個成員節點的簇，網絡初始化流程如圖3所示。

圖3 網絡初始化流程Fig.3 Network initialization process

為完成簇結構的初始化，節點需向全網廣播Hello消息，Hello消息包含節點ID、節點證書、節點權值、節點狀態、時間戳和消息驗證碼。其中節點權值W綜合考慮了節點的處理器性能A、網絡帶寬M和剩余電量E等因素，權值計算公式為：

當節點收到來自其他節點的Hello 消息后，根據消息驗證碼和節點證書來驗證節點的身份和消息的真實性。消息驗證通過后，根據節點發出的Hello 消息信號強度計算節點間的距離：

其中，λ為波長，PT為發送方功率大小，PR為接收方功率大小。節點i與節點j進行n次距離的測算，兩個節點間平均距離為：

若平均距離小于給定的閾值，將該節點信息加入自己的內存，若節點的內存中存在狀態為簇首的節點，則發送入簇申請。若節點的內存中存在多個可選的簇首，則計算簇首的優先級：

其中，wv表示簇首CHv的權值，N表示簇內節點數量，s表示節點i與簇首CHv的平均距離。節點可向優先級最大的簇首發送入簇申請。

若節點內存中不包含簇首，則選擇權值最大的節點作為簇首，其余節點以簇成員的身份加入。簇內節點主要采用廣播方式進行通信，若節點數量過多，將會造成網絡擁堵和延遲等問題。為控制簇的節點數量，本文提出簇首隱藏狀態的概念，當簇首檢測到簇內的節點數量超過給定閾值時，將自己的狀態轉為簇首隱藏狀態，不再處理入簇申請，其余節點也不會選擇隱藏狀態的簇首加入。

2.2.2 簇結構維護

簇結構維護即系統針對簇結構變化的一系列反應，節點的下列三種行為將引起簇結構的變化：節點加入、節點離簇和節點移動。在本文中節點可采用主動或被動的方式監測簇結構的變化。

節點收到簇首的Hello 消息后，進入節點加入流程。首先計算簇首的優先級，選擇向優先級最高的簇首發送入簇申請。簇首收到入簇申請后，驗證節點的身份信息，驗證通過后，同意節點入簇，廣播修改后的簇成員表。成員節點收到廣播后，同步修改簇成員表。

根據節點的狀態和節點退出簇的方式，可將節點退出分為四類：成員節點正常退出、成員節點非正常退出、簇首節點正常退出、簇首節點非正常退出。節點離簇前需要向簇內各節點廣播離簇消息，表示自己即將離簇，成員節點離簇后簇首需要修改并廣播簇成員表，對于簇首的離簇，需要指定或選舉出新的簇首。正確廣播離簇消息的節點被視為正常離簇。此外，本文采用被動方式檢測節點的非正常離簇，正常運行的節點需要在每個周期廣播Hello消息，若某節點連續三個周期未廣播Hello 消息，則其余節點可將其視為非正常離簇。

當節點受到環境變化或任務改變等因素的影響，需要移動較大的距離，其選擇退出當前簇加入另一簇的過程就完成了一次節點移動。節點移動是節點退出和節點加入的組合。若節點移動的距離過大，無法接收到任何簇首的Hello消息，則將自己的狀態改為游離狀態，等待接收簇首的Hello消息。

綜上所述，本文主動監測簇內網絡拓撲變化的方式為簇首接收到節點的入簇申請，以及簇內節點收到離簇節點的離簇消息；被動監測拓撲變化的方式為連續三個周期未收到節點的Hello消息。將主動與被動的形式相結合，可以更加有效地判斷簇結構是否發生變化，增強系統的穩定性。

2.2.3 拓撲狀態變更

對于簇首節點，若連續三次廣播的簇成員表都相同，則將自己的拓撲狀態從拓撲變化狀態改為拓撲穩定狀態。簇首修改簇成員表后，需要將自己的拓撲狀態改為拓撲變化狀態。對于簇成員節點，若連續三次收到相同的簇成員表，則將自己的拓撲狀態從拓撲變化狀態改為拓撲穩定狀態。當簇成員收到簇首更新的簇成員表或連續三個Hello消息周期未收到簇首的Hello 消息，需要將自己的拓撲狀態改為拓撲變化狀態。

2.2.4 會話密鑰協商

完成分簇的網絡初始化操作后，節點處于拓撲穩定狀態，進入密鑰協商階段。本文的密鑰協商過程基于棣弗-赫爾曼（Diffie-Hellman，DH）密鑰交換，如圖4所示，簇內的節點兩兩協商一個共同的會話密鑰Ki。圖5 展示了節點i與節點j協商密鑰時所發送的消息，密鑰協商涉及的相關符號如表1所示。后續階段如有新節點入簇，新節點需要向簇內的所有節點協商會話密鑰，密鑰協商結束后，節點運行區塊管理模塊。

圖5 會話密鑰協商流程Fig.5 Session key negotiation process

2.3 區塊管理模塊

區塊管理模塊由共識模塊和區塊恢復模塊組成。系統完成密鑰協商后，每一個簇開始運行共識模塊，獨立地進行共識，簇中的每個節點（包括簇首和簇成員）都有相同的概率和地位產生區塊，區塊由會話密鑰加密后在簇內廣播。受到任務和環境變化等因素的影響，網絡可能經歷分裂和合并等拓撲變化，區塊恢復模塊負責網絡拓撲改變后對區塊鏈分支進行恢復。如圖6 所示，系統基于DAG 結構構建區塊鏈，網絡分裂成多個簇時，由于網絡隔離，區塊鏈會產生分支，每個簇在各自的分支上產生區塊，每一條分支也基于DAG 結構，提高了系統的吞吐量。當多個簇合并成一個簇后，節點運行區塊恢復模塊，恢復由其他簇產生的區塊。

圖6 DAGGraph賬本Fig.6 DAGGraph ledger

如圖6 所示，本系統將區塊分為四種類型：創世區塊（Genesis Block）、配置更改塊（ConfChange Block）、合并塊（Merge Block）以及普通塊（Normal Block）。創世區塊由簇首產生，是系統產生的第一個區塊，隨后簇中的每一個節點都有相同的概率產生普通塊，普通塊可包含交易在內的任何類型的事務信息。為簡化出塊流程，減小網絡通信負載，每個普通塊只包含一條事務信息，即節點直接將自己的事務打包成區塊，交由共識模塊共識。網絡發生分裂后，將形成多個簇，每個簇的簇首都會在本簇的賬本上生成一個相同的配置更改塊，用于收斂之前生成的區塊。網絡發生合并后由新簇首產生合并塊，合并塊將引用區塊鏈各分支上所有未被引用的區塊，用于合并各簇產生的分支。

本系統定義的區塊結構如圖7所示，主要包含區塊類型、區塊標記、父哈希列表和隨機數Nonce 等字段。區塊標記包含該區塊的創建者信息：若區塊類型為普通塊，則區塊標記為簇ID，同一簇內的節點產生的普通塊包含相同的簇ID，簇ID 由簇首在拓撲穩定后生成，并廣播給簇成員節點。簇ID的計算公式為：

圖7 區塊結構Fig.7 Block structure

簇ID=Hash(∑簇內節點ID)（6）

若區塊類型為簇首產生的創世區塊、配置更改塊或合并塊，則區塊標記為簇首ID。為確保系統穩定出塊，保證區塊鏈系統的安全性，防止女巫攻擊等惡意行為，節點在產生區塊前需運行一次工作量證明（proof of work，PoW）算法。隨機數Nonce 在節點運行PoW 算法后產生，父哈希列表包含區塊引用的所有父區塊的哈希值。

2.3.1 共識模塊

共識模塊負責區塊的生成上鏈。在DAGGraph中，每個節點均可進行出塊，在網絡質量良好、信道占用率低的情況下，簇內的節點越多，簇的出塊速度越大。然而隨著簇內節點數量的增加，節點間因出塊進行的通信可能會占用大量的信道資源，對系統的整體性能造成影響。因此，本文除第2.2.1 小節所提出的簇首隱藏狀態的概念用于限制簇節點密度外，還將通過共識模塊，根據簇內節點數量的變化動態調整PoW 算法的難度以調整簇的出塊速度。出塊速度可簡化為：

其中，N表示簇內節點數量，p表示節點出塊的概率，A表示節點性能，D表示共識算法的難度。因此，出塊速度與簇內節點的數量、節點出塊的概率以及節點的性能成正比，與共識算法的難度成反比。共識模塊隨節點數量的增加而適當提高共識算法的難度，可在一定程度上限制出塊速度，以確保簇內信道占用率處于可接受的水平，保證系統的平穩運行，所選取的PoW 難度適中，對系統的整體能耗影響較小。此外，在節點出塊前引入PoW 算法還可以增加惡意節點作惡成本，提高系統安全性。

共識模塊負責產生區塊和區塊上鏈。區塊的共識不同于Raft算法需要超過半數節點返回確認消息，本系統的節點出塊流程如下：首先節點打包自己產生的事務，接著運行一次簡單的PoW 算法，并廣播自己的區塊。其他節點收到區塊后，需要驗證區塊是否滿足共識模塊規定的共識算法難度，如滿足則進入區塊上鏈階段，如不滿足則丟棄。采用工作量證明實現對區塊的驗證，可減少集群中的通信量，提高共識速度。如圖8 所示，節點拓撲狀態穩定后，由簇首向簇成員節點廣播開始共識消息，簇成員收到消息后運行共識模塊。共識模塊將節點拓撲穩定后的時間劃分為多個時間片（Epoch），節點可在每個Epoch產生區塊，每個新上鏈的區塊需要引用前一個Epoch產生的所有區塊。如果拓撲狀態發生改變，如節點退出或入簇，則簇內的節點停止出塊，待拓撲狀態穩定后重新運行共識模塊。退出簇的節點重新組成另一個新的簇后，網絡分裂成兩個簇，區塊鏈也將分裂為獨立的分支，待拓撲穩定后兩個簇在各自的分支上繼續進行共識。

圖8 DAGGraph共識機制Fig.8 DAGGraph consensus mechanism

2.3.2 區塊恢復模塊

區塊恢復模塊用于在簇間和簇內，對新加入的節點恢復區塊鏈分支。當網絡發生合并時，合并的簇之間需要恢復其他簇產生的分支；節點加入某一簇后，也需要從該簇節點恢復自己所缺失的所有區塊。如圖9 所示，簇A 和簇B 合并為一個新的簇，以簇A為例，它需要恢復簇B產生的區塊。簇A的簇首向簇B 的簇首發送請求消息，請求簇B 的完整分支，簇A的簇首收到完整分支后在本地進行恢復，然后向自己的簇成員廣播來自簇B的分支，實現簇A的所有節點對簇B 分支的恢復。簇B 也以相同的方式恢復簇A產生的分支。待區塊恢復完成后，合并后的簇選舉新的簇首，然后由新簇首生成合并塊，收斂之前的區塊鏈分支。

圖9 簇間區塊恢復Fig.9 Inter-cluster block recovery

如圖10所示，簇A的節點1因某種原因離開本簇后加入簇B，節點1 需要恢復簇B 產生的區塊，節點1的區塊恢復任務由簇B 的簇首負責完成。簇B 的簇首檢測到節點1的加入后，判定簇內網絡拓撲發生變化，立即停止共識，并生成配置更改塊，運行區塊恢復流程。節點1 向簇B 的簇首發送請求消息，請求簇B的區塊分支，節點1收到簇B分支后進行恢復，并刪除由簇A產生的分支。待網絡拓撲穩定后，簇B的簇首產生配置更改塊，表示節點1 的區塊恢復成功，簇B的節點可繼續進行共識。

圖10 簇內區塊恢復Fig.10 Intra-cluster block recovery

2.4 節點注冊

CA具有授權DAGGraph節點的權限。在實際應用中，一批運行DAGGraph 系統的節點可以先后向CA 提出注冊申請。CA 完成對節點的驗證后，向節點頒發證書?？紤]到運行DAGGraph 系統的節點通常不具備較高的算力，因此需要一個安全高效的對稱加密方案完成證書的傳遞。每個節點開始注冊前，先通過橢圓曲線數字簽名算法（elliptic curve digital signature algorithm，ECDSA）生成自己的公鑰Pub和私鑰Priv。如圖11 所示，CA 通過節點的公鑰向節點傳輸對稱密鑰，并最終使用對稱密鑰構建的安全信道向節點傳遞證書，完成節點注冊，節點注冊所涉及的相關符號如表2所示。

表2 節點注冊相關符號Table 2 Relevant notation of node registration

圖11 節點注冊Fig.11 Node registration

2.5 網絡合并檢測

本文將網絡合并定義為當前系統只存在一個簇，所有節點都已加入該簇，采用對比簇成員信息的方式檢測是否發生網絡合并。本系統基于私有鏈，當一批節點完成向CA 的注冊后，表示節點成功加入DAGGraph 系統。所有節點完成注冊后，CA 將它們寫入節點信息表。節點信息表包含所有加入系統的節點的身份信息。其他簇的節點入簇后，原有簇的節點比較簇成員表和節點信息表，如果兩表內包含的簇成員節點信息相同，則表示發生了網絡合并，節點需要運行區塊恢復模塊，完成對分支的恢復。

3 安全性與通信復雜度分析

3.1 安全性分析

本節討論系統的分簇管理模塊和共識模塊易受到的安全攻擊，并分析系統應如何防范。

拒絕服務（denial of service，DoS）攻擊：在分簇階段，惡意節點將大量無效的Hello 消息廣播給鄰居節點，使節點無法處理正常的分簇請求。本系統采用CA 頒發證書的形式，確保每個節點都可被驗證身份，對于未被驗證的節點，系統將直接忽略其發送的消息。

雙花攻擊：在傳統鏈式結構的區塊鏈中，雙花攻擊指惡意節點在區塊鏈上發起一筆交易，當交易被打包成區塊后，在該區塊之前重新發布一個包含沖突交易的區塊，造成區塊鏈的分叉。若分叉鏈能夠取代主鏈，則惡意節點的雙花攻擊成功。在基于DAG 結構的區塊鏈上，雙花攻擊指的是惡意節點在區塊鏈的分支上發布兩個包含沖突交易的區塊，DAG 結構雖然能夠容忍分叉的產生，但沖突的交易也將影響區塊鏈系統的正常運行。本系統根據時間片對區塊進行排序，同一個時間片內的區塊按哈希值進行排序，通過這種方式確定DAG 賬本內區塊的總順序，對于沖突的交易，將排序靠前的交易視為有效交易。

女巫攻擊：女巫攻擊指惡意節點冒充多個身份，爭奪網絡控制權，影響共識結果以及干擾節點正常工作等。進行女巫攻擊的節點需要將自己的計算資源分配給多個身份，每個身份分配到的資源有限。本系統規定節點出塊前需要運行一次PoW 算法，有效地限制了女巫攻擊。此外，CA 負責為每個節點頒發證書，同一節點無法向CA 申請多個證書，不被CA驗證的節點將無法運行本系統，從根源上杜絕了女巫攻擊的發生。

3.2 共識階段的通信復雜度分析

BlockGraph 采用Raft 算法，假設節點總數為n，則區塊由leader發送后至少需要n2條確認消息才能上鏈，BlockGraph 在共識階段的通信復雜度為O(n)。DAGGraph簇中的簇首和簇成員均可產生區塊，且節點采用PoW 算法驗證區塊的正確性，通過驗證的區塊即可上鏈，而節點無需向簇首或其他任意節點返回確認消息。因此DAGGraph 的共識時延僅由區塊的打包和傳播時間以及節點運行PoW 算法驗證區塊的時間構成，而區塊的傳播時間可忽略不計。區塊的打包和驗證僅需節點在本地計算和驗證PoW 算法，因此共識時延與節點個數無關，DAGGraph 在共識階段的通信復雜度為O(1)，其通信效率要明顯高于BlockGraph。

4 相關工作實驗結果與分析

4.1 實驗環境

實驗采用Docker 虛擬化技術模擬節點和節點運行所需的網絡環境，Docker運行的軟硬件環境如表3所示。本實驗所采用的代碼庫均由論文作者編寫，代碼運行環境由python:3.5.4-jessie提供支持，實驗所需的Docker 鏡像基于Python3 編寫生成。實驗開始前先在Docker 中創建一個網絡以供節點通信使用，并使用Docker 鏡像在網絡中批量生成模擬節點行為的Docker 容器，容器可模擬BlockGraph 和DAGGraph的共識行為，容器間使用用戶數據報協議（user datagram protocol，UDP）進行通信。為便于仿真實驗，本文假設一個區塊內僅包含一筆由節點產生的交易，并將區塊大小設置為8 KB。實驗主要模擬BlockGraph和DAGGraph的出塊和上鏈過程，通過對比二者在不同節點數量以及不同簇數量下的共識時延與吞吐量，來評估方案的性能。

表3 實驗軟硬件環境Table 3 Software and hardware environments of experiment

4.2 共識時延測試

共識時延指的是簇內完成一次共識所需的時間，共識時延的大小將在一定程度上影響區塊鏈系統的性能。本文對比的區塊鏈系統為BlockGraph。BlockGraph的共識機制基于Raft算法，核心是在每個分區內選舉出領導者節點，由領導者節點向追隨者節點復制區塊，實現賬本的一致性。Raft算法要求領導者節點收集超過半數的確認消息，才能確保區塊復制成功，因此等待確認消息的時間將影響共識時延的大小。本文提出的DAGGraph 將每一個簇內的節點分為一個簇首節點和多個簇成員節點，且每個節點均可以產生區塊。為加強系統的安全性，節點產生區塊前將運行一次簡單的PoW算法，節點收到區塊后僅需要驗證必要的身份信息和區塊的正確性，簡化了區塊的確認過程。圖12 為一個分區內BlockGraph 和DAGGraph 的共識時延隨節點個數的變化關系。從實驗結果可以看出，DAGGraph的共識時延明顯優于BlockGraph。DAGGraph 的共識時延隨節點數量的變化緩慢波動，基本維持穩定的值。而BlockGraph的共識時延隨節點數量的增加呈近似線性增長，原因是BlockGraph 共識的通信復雜度為O(n)，隨著分區內節點數量的增加，領導者節點所需等待的確認消息越多，共識時延越長。如第3.2 節所述，DAGGraph在共識階段的通信復雜度取決于解決PoW 難題和驗證PoW所花費的時間，因此DAGGraph在共識階段的通信復雜度為O(1)，共識所需的時間僅取決于PoW算法的難度，與節點個數無關。

圖12 不同節點個數下的共識時延對比Fig.12 Comparison of consensus delay under different number of nodes

在實際應用中，整個網絡內的節點數量往往是固定的，因此隨著網絡分區數量的增加，每個分區內的節點數量會相應地減少。在本實驗中，將系統中的節點總數固定為200 個，分區的初始數量為20 個，假設節點均勻地分布在各分區中，此時每個分區內的節點數量為10個；之后逐漸減少分區的數量，最終分區的數量減少為1個，分區內的節點數量為200個。圖13顯示了節點總數不變的前提下，分區數量與共識時延的關系。由實驗結果可以得出，DAGGraph的共識時延在分區數量不同的情況下，仍能保持穩定。這是因為DAGGraph 的共識時延僅取決于節點本地運行PoW 算法的時間，與分區內節點個數無關，分區數量變化所引發的分區內節點數量的變化不會對DAGGraph 的共識時延造成影響。而BlockGraph 的共識時延隨分區數量的減少而增加，受分區數量變化的影響較大。這是由于BlockGraph 采用的Raft 算法的性能隨節點數的增加而下降。在節點數量不變的前提下，分區數量越少，分區內的節點數量越多，BlockGraph 共識所需等待的確認消息越多，共識時延越大。

圖13 不同分區數量下的共識時延對比Fig.13 Comparison of consensus delay under different number of partitions

4.3 吞吐量測試

吞吐量指的是單位時間內區塊鏈系統處理的交易數量，與分區數量、節點數量和區塊內包含的交易數量成正比，與平均共識時延成反比。為便于仿真模擬，本實驗假設每個區塊包含一個交易，測試BlockGraph 和DAGGraph 的吞吐量與節點數量和分區數量的關系。

圖14 為吞吐量與節點數量的關系，可以看出DAGGraph 的吞吐量整體高于BlockGraph，且隨著節點數量的增加整體呈波動上升的趨勢，具有一定的可擴展性。這是因為在DAGGraph 中，簇首與簇成員是對等節點，均有出塊權，網絡中節點數量越多，則表示出塊節點的數量越多，吞吐量越高。而BlockGraph基于Raft算法，在一個簇內只有一個領導者節點可以產生區塊，因此吞吐量基本不隨節點數量變化，可擴展性較差。

圖14 不同節點個數下的吞吐量對比Fig.14 Comparison of throughput under different number of nodes

在分區數量與吞吐量的實驗中，同樣保持節點總數為200 個不變，且節點均勻分布在各分區中，則分區內的節點數量將隨著分區數量的增加而減少，在此前提下測試吞吐量與分區數量的關系。如圖15所示，隨著分區數量的增加，兩種方案的吞吐量均有一定程度的增長。DAGGraph 比BlockGraph 表現出更好的吞吐量性能，吞吐量的增長速度也更快。這是因為BlockGraph基于Raft算法，采用鏈式結構維護區塊鏈賬本，并由領導者節點復制區塊；而DAGGraph的每個節點均可產生區塊，且以DAG 的形式維護賬本，在分區數量更多的情況下，DAGGraph 的吞吐量性能優勢會更明顯。

圖15 不同分區數量下的吞吐量對比Fig.15 Comparison of throughput under different number of partitions

5 結束語

移動自組網允許節點自發地形成網絡拓撲，具有組網速度快、拓撲變化靈活等特點。區塊鏈以安全和不可篡改等特性著稱，將區塊鏈與移動自組網相結合是一種新穎的嘗試。移動自組網節點的移動性會引發節點隨時離開或加入，這種網絡拓撲的動態變化給區塊鏈的運行帶來巨大挑戰。本文提出區塊鏈與移動自組網的結合需要解決的三個問題：分簇問題、共識問題和區塊恢復問題。針對這三個問題提出了DAGGraph，一種基于DAG 結構的系統模型。通過引入一種高效的分簇算法，使得節點通過主動發現方式完成網絡拓撲變化（分裂）后的高效成簇并快速開始共識。在共識階段，DAGGraph規定一個區塊只包含一筆交易，簡化了出塊流程，節點只需驗證區塊的正確性和身份信息即可完成區塊上鏈。在網絡合并階段，通過簇首節點進行分叉交換和區塊同步，實現了對缺失區塊的快速恢復。網絡中傳輸的所有區塊信息均進行加密，確保了區塊傳輸的安全性。此外，DAGGraph以頒發證書的形式對節點進行驗證，可以有效抵御DoS 攻擊、雙花攻擊、女巫攻擊等惡意攻擊。實驗結果表明，DAGGraph在共識時延和吞吐量方面的性能較BlockGraph 均有明顯的優勢。