摘 要：編碼區(qū)塊鏈利用糾錯碼技術(shù)，將區(qū)塊分為多個編碼片段并分布式存儲于節(jié)點(diǎn)中。其主要目的在于減少參與者或節(jié)點(diǎn)的存儲需求，實(shí)現(xiàn)高效的存儲和容錯能力。然而，節(jié)點(diǎn)隨機(jī)存儲任意數(shù)量的編碼片段，導(dǎo)致編碼片段分布不均勻，從而增加節(jié)點(diǎn)嘗試解碼區(qū)塊時的通信成本以及關(guān)鍵節(jié)點(diǎn)的存儲開銷。為此，提出一種基于強(qiáng)化學(xué)習(xí)的分布式協(xié)議，用來合理分配節(jié)點(diǎn)存儲的編碼片段以降低存儲開銷和通信成本。具體而言，節(jié)點(diǎn)在解碼任意區(qū)塊時計(jì)算存儲獎勵，該獎勵與編碼片段的存儲成本和節(jié)點(diǎn)嘗試解碼區(qū)塊時產(chǎn)生的通信成本呈反比關(guān)系。學(xué)習(xí)收斂后與現(xiàn)有的集中式和分布式區(qū)塊鏈編碼存儲方法進(jìn)行了比較，研究結(jié)果表明，節(jié)點(diǎn)的獎勵提高了7%，且節(jié)點(diǎn)的通信成本降低了55%。綜上，基于強(qiáng)化學(xué)習(xí)的分布式協(xié)議為編碼區(qū)塊鏈存儲和傳輸性能的提升提供了有效的解決方案。

關(guān)鍵詞：編碼；糾錯碼；分配；恢復(fù)；分布式

中圖分類號：TP311.1 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695（2024）10-006-2918-08

doi：10.19734/j.issn.1001-3695.2023.12.0631

Distributed learning protocol for storage assignment in coded blockchain

Yang Changlin1， 2， Niu Xingyu1

（1.School of Computer Science， Zhongyuan University of Technology， Zhengzhou 451191， China; 2. School of Software Engineering， Sun YatSen University， Zhuhai Guangdong 519082， China）

Abstract：Coded blockchain leverages error correction codes to create multiple coded fragments that are then stored in a distributed manner by nodes. Its primary objective is to reduce the storage requirements of participants or nodes， achieving efficient storage and fault tolerance. However， nodes randomly store arbitrary coded fragments， which leads to high communication cost when a node attempts to decode a block. To this end， this paper proposed a novel reinforcement learning inspired distributed protocol to efficiently assign coded fragments to nodes. Specifically， nodes learn to store coded fragments based on a feedback signal that related to the storage cost of coded fragments and the communication cost incurred during block decoding attempts. After convergence， it compared the proposed protocol with existing centralized and distributed blockchain encoding storage methods. The results show that nodes have 7% higher reward， and critically， their communication cost is lower by 55%. In summary， the proposed reinforcement learning-based distributed protocol provides an effective solution for enhancing the storage and transmission performance of encoded blockchains.

Key words：coding; error correction codes; assignment; recovery; distributed

0 引言

區(qū)塊鏈?zhǔn)且环N無須任何中間方即可促進(jìn)多方之間交易的技術(shù)。其關(guān)鍵特性包括分布式架構(gòu)、安全性、不可竄改性和透明性，已在金融、醫(yī)療保健、物聯(lián)網(wǎng)（IoT）和教育等不同領(lǐng)域得到了廣泛應(yīng)用［1］。然而，區(qū)塊鏈存在存儲可擴(kuò)展性問題［2］，因?yàn)槊總€參與者都存儲整個區(qū)塊鏈的副本，該副本的數(shù)量級為千兆字節(jié)，并隨時間不斷增長。因此，區(qū)塊鏈的運(yùn)行依賴于擁有充足資源的節(jié)點(diǎn)，進(jìn)而帶來了安全問題。該安全問題涉及到資源豐富節(jié)點(diǎn)的壟斷和操控，威脅了區(qū)塊鏈的去中心化和抗攻擊性能。

為了擴(kuò)大區(qū)塊鏈的規(guī)模，業(yè)界和學(xué)術(shù)界提出了許多存儲方法，包括輕節(jié)點(diǎn)、分片、側(cè)鏈和剪枝等［3］。然而，這些方法都有缺點(diǎn)。例如，輕節(jié)點(diǎn)和側(cè)鏈都缺乏驗(yàn)證所有交易的能力，這意味著它們?nèi)菀资艿綌?shù)據(jù)可用性攻擊［4］。至于分片方法，其安全級別隨著每個分片中惡意節(jié)點(diǎn)數(shù)量的增加而降低［5］。修剪會導(dǎo)致永久性數(shù)據(jù)丟失［3］。

與上述方法不同，編碼區(qū)塊鏈利用糾刪碼技術(shù)來提高傳統(tǒng)區(qū)塊鏈的存儲效率和容錯能力［3］。如圖1所示，每個節(jié)點(diǎn)獨(dú)立地將區(qū)塊編碼成編碼片段并根據(jù)存儲分配策略存儲。當(dāng)一個節(jié)點(diǎn)（如節(jié)點(diǎn)v1）需要恢復(fù)一個區(qū)塊時，它會從其他節(jié)點(diǎn)收集編碼片段。此示例使用一個［4，5］編碼，這意味著解碼需要四個唯一的編碼片段。在編碼區(qū)塊鏈系統(tǒng)中，一個區(qū)塊被分為k個片段，然后使用Reed-Solomon碼或噴泉碼等糾錯碼進(jìn)行編碼，生成m（m≥k）個編碼片段。編碼區(qū)塊鏈的另一個優(yōu)點(diǎn)是它能夠抵御節(jié)點(diǎn)故障［6］。

編碼區(qū)塊鏈面臨的一個關(guān)鍵問題涉及到如何合理分配編碼片段給節(jié)點(diǎn)，本文將其稱為編碼片段分配（CFA）問題。早期的編碼區(qū)塊鏈研究主要關(guān)注于區(qū)塊編碼策略，卻忽視了CFA問題。換言之，它們的策略是在節(jié)點(diǎn)上隨機(jī)存儲任意數(shù)量的編碼片段。這樣的做法導(dǎo)致編碼片段分布不均，從而增加了節(jié)點(diǎn)嘗試解碼區(qū)塊時的通信成本，因?yàn)楣?jié)點(diǎn)必須從遠(yuǎn)處的節(jié)點(diǎn)獲取編碼片段。圖2展示了在沒有考慮CFA的編碼區(qū)塊鏈中存在的另外兩個問題。第一個問題是存儲浪費(fèi)，靠近的節(jié)點(diǎn)存儲相同的編碼片段，這不利于解碼并增加了節(jié)點(diǎn)的存儲負(fù)擔(dān)，如案例1。第二個問題是無法保證區(qū)塊的完全恢復(fù)，因?yàn)楣?jié)點(diǎn)存儲的編碼片段數(shù)量不足以確保對區(qū)塊的解碼，如案例2。

現(xiàn)有的解決CFA問題的方法采用集中式或分布式分配方法。然而，這些方法有一個或多個缺點(diǎn)［3］。例如，中心化的分發(fā)方法與區(qū)塊鏈系統(tǒng)的去中心化性質(zhì)相矛盾［7］。另一方面，分布式分配方法未考慮參與者在重建區(qū)塊時產(chǎn)生的通信成本［8］。此外，先前的分布式CFA解決方案并未對從對等節(jié)點(diǎn)檢索的編碼片段進(jìn)行驗(yàn)證。

本文引入了一種分布式學(xué)習(xí)協(xié)議，用于將編碼片段合理地分配給節(jié)點(diǎn)。該協(xié)議充分考慮了區(qū)塊鏈系統(tǒng)的動態(tài)特性，其中節(jié)點(diǎn)獨(dú)立進(jìn)行存儲、編碼、解碼區(qū)塊以及加入/離開網(wǎng)絡(luò)的操作。通過使用該協(xié)議，節(jié)點(diǎn)在解碼區(qū)塊時能夠了解編碼片段的分配情況，特別是在分配時考慮了解碼成本以及來自其他節(jié)點(diǎn)發(fā)送的編碼片段的完整性。節(jié)點(diǎn)維護(hù)其存儲的編碼片段的“狀態(tài)”，并根據(jù)與存儲成本、通信成本以及當(dāng)前網(wǎng)絡(luò)拓?fù)湎嚓P(guān)的“獎勵”，采取“行動”來調(diào)整其編碼片段集。

與現(xiàn)有的解決CFA問題的方法相比，基于強(qiáng)化學(xué)習(xí)的分布式協(xié)議能夠更智能地解決CFA問題。這一協(xié)議允許每個節(jié)點(diǎn)根據(jù)其解碼經(jīng)驗(yàn)計(jì)算獎勵，從而實(shí)現(xiàn)更合理的編碼片段分配策略，并且根據(jù)網(wǎng)絡(luò)狀態(tài)變化實(shí)時調(diào)整存儲的編碼片段。同時，該協(xié)議無須節(jié)點(diǎn)間建立信任關(guān)系，每個節(jié)點(diǎn)都獨(dú)立執(zhí)行編碼、解碼和驗(yàn)證，并基于編碼片段的可解碼性定位誠實(shí)和惡意節(jié)點(diǎn)，因此，更適用于現(xiàn)有開放式的區(qū)塊鏈系統(tǒng)。在仿真實(shí)驗(yàn)中，本文協(xié)議與文獻(xiàn)［7］提出的CSA算法進(jìn)行了比較，這是由于目前僅有文獻(xiàn)［7］針對編碼片段分配問題進(jìn)行了討論，并提出了可行方法。

綜上，本文作出了以下貢獻(xiàn)：

a）本文首次提出解決CFA問題的分布式學(xué)習(xí)協(xié)議，使每個節(jié)點(diǎn)能夠?qū)W習(xí)如何合理地分配和重新分配編碼片段。具體而言，節(jié)點(diǎn)可以根據(jù)其解碼經(jīng)驗(yàn)計(jì)算獎勵，從而實(shí)現(xiàn)更智能的分配策略。此外，該協(xié)議適用于無信任的區(qū)塊鏈系統(tǒng)。因?yàn)槊總€節(jié)點(diǎn)都獨(dú)立執(zhí)行編碼、解碼和驗(yàn)證，不依賴其他節(jié)點(diǎn)。

b）本文首次對所提出的學(xué)習(xí)協(xié)議進(jìn)行研究，并與現(xiàn)有解決CFA問題的集中式和分布式啟發(fā)式算法進(jìn)行比較。結(jié)果表明，就總體獎勵而言，所提出的協(xié)議比現(xiàn)有算法高出7%。此外，當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化并需要重新分配編碼片段時，其重新分配編碼片段所產(chǎn)生的通信成本比現(xiàn)有算法低55%。

1 相關(guān)工作

之前的工作已經(jīng)設(shè)計(jì)了各種策略來編碼區(qū)塊鏈。例如，文獻(xiàn)［9］采用糾刪碼來對區(qū)塊文件進(jìn)行編碼分片存儲，并隨機(jī)分配給任意節(jié)點(diǎn)。Dai等人［10］采用網(wǎng)絡(luò)編碼，每個節(jié)點(diǎn)只存儲一個編碼片段。文獻(xiàn)［11，12］中的工作結(jié)合拜占庭容錯（BFT）共識算法和糾刪碼，每個節(jié)點(diǎn)存儲一部分編碼片段。文獻(xiàn)［13］利用密鑰共享、私鑰加密和分布式存儲來減少節(jié)點(diǎn)的存儲需求。在文獻(xiàn)［14］中，每個節(jié)點(diǎn)在{1，2，…，k}內(nèi)隨機(jī)生成一個數(shù)字d，節(jié)點(diǎn)從一組k個區(qū)塊中隨機(jī)選擇d個區(qū)塊，對這d個區(qū)塊執(zhí)行按位異或操作，生成所謂的液滴并進(jìn)行存儲。文獻(xiàn)［15］介紹了一種新型區(qū)塊鏈存儲優(yōu)化策略，利用糾刪碼技術(shù)對區(qū)塊數(shù)據(jù)進(jìn)行編碼，并通過引入節(jié)點(diǎn)分組存儲的方式，將編碼后的區(qū)塊數(shù)據(jù)以組為單位進(jìn)行存儲。這一策略旨在減少每個節(jié)點(diǎn)的存儲負(fù)擔(dān)，通過讓每個組內(nèi)的節(jié)點(diǎn)僅存儲部分區(qū)塊數(shù)據(jù)來實(shí)現(xiàn)存儲空間的降低。然而，這些工作都沒有明確說明如何在節(jié)點(diǎn)之間分配編碼片段。這意味著節(jié)點(diǎn)會存儲重復(fù)的片段，并且如果某些節(jié)點(diǎn)離開網(wǎng)絡(luò)，會導(dǎo)致解碼時編碼片段數(shù)量不足，從而引發(fā)解碼失敗。

一些工作提出了集中式的分配策略，其中選舉產(chǎn)生的節(jié)點(diǎn)或網(wǎng)絡(luò)運(yùn)營商決定每個節(jié)點(diǎn)的編碼片段分配。例如，在文獻(xiàn)［16］中，一組節(jié)點(diǎn)中的領(lǐng)導(dǎo)者負(fù)責(zé)對數(shù)據(jù)進(jìn)行編碼并將其分發(fā)給組內(nèi)的節(jié)點(diǎn)。在文獻(xiàn)［17］中，領(lǐng)導(dǎo)者（服務(wù)器）將一個區(qū)塊編碼成多個編碼片段，并將其分發(fā)到客戶端節(jié)點(diǎn)，其中每個客戶端節(jié)點(diǎn)存儲一個編碼片段。Yang等人［7］將CFA問題制定為整數(shù)線性規(guī)劃（ILP），他們還提出了一種由網(wǎng)絡(luò)運(yùn)營商負(fù)責(zé)運(yùn)行的集中式啟發(fā)算法，用來確定存儲分配。Yu等人［17］在實(shí)用拜占庭容錯（PBFT）系統(tǒng)中提出了一種編碼區(qū)塊鏈文件存儲系統(tǒng)。在每個區(qū)塊生成輪次中，礦工對挖掘的區(qū)塊進(jìn)行編碼，并將編碼片段分發(fā)到其他節(jié)點(diǎn)。Li等人［18］根據(jù)解碼失敗的整體概率確定每個節(jié)點(diǎn)存儲的編碼片段。

在分布式分配方法方面，每個節(jié)點(diǎn)根據(jù)自身對網(wǎng)絡(luò)的觀察來決定存儲的編碼片段，旨在減少存儲并確保區(qū)塊仍然可解碼。Perard等人［19］引入了一種僅存儲編碼片段的編碼節(jié)點(diǎn)，區(qū)塊編碼片段的數(shù)量隨著區(qū)塊的年齡增加而減少。Yang等人［7］概述了一種分布式協(xié)議，該協(xié)議在新節(jié)點(diǎn)加入或離開網(wǎng)絡(luò)時調(diào)整節(jié)點(diǎn)的存儲需求。如果節(jié)點(diǎn)無法使用附近鄰居的編碼片段解碼區(qū)塊，它會聯(lián)系更遠(yuǎn)的節(jié)點(diǎn)以獲取編碼片段。文獻(xiàn)［8］提出了一種分布式協(xié)商協(xié)議，節(jié)點(diǎn)使用該協(xié)議來交換編碼片段，它減少了重復(fù)片段的數(shù)量，并確保節(jié)點(diǎn)存儲足夠數(shù)量的編碼片段以解碼區(qū)塊。然而，該協(xié)議缺乏驗(yàn)證方案來檢查編碼片段的有效性。此外，文獻(xiàn)［20］采用基于糾刪碼和拜占庭容錯算法的編碼方法，每個節(jié)點(diǎn)根據(jù)共識節(jié)點(diǎn)公鑰列表分配存儲編碼區(qū)塊，以降低區(qū)塊鏈系統(tǒng)的存儲冗余度，提高可擴(kuò)展性。

目前的編碼片段分配方法有幾個缺陷。它們會不合理地將編碼片段分配給節(jié)點(diǎn)，導(dǎo)致那些擁有更多片段的節(jié)點(diǎn)在解碼過程中具有更高的通信成本。也可以說，它們必須在解碼過程中提供更多編碼片段。此外，編碼片段會集中在某些節(jié)點(diǎn)上，因此當(dāng)節(jié)點(diǎn)發(fā)生故障或離開網(wǎng)絡(luò)時，存在數(shù)據(jù)丟失的風(fēng)險。集中式的分發(fā)方法不適用，因?yàn)閰^(qū)塊鏈系統(tǒng)需要分布式的解決方案。最后，分布式方法只考慮節(jié)點(diǎn)是否誠實(shí)，并不考慮區(qū)塊恢復(fù)期間的通信成本。因此，本文提出了一種具有以下特點(diǎn)的分布式協(xié)議：

a）確保節(jié)點(diǎn)或參與者具有較小的存儲和通信成本。

b）不需要領(lǐng)導(dǎo)節(jié)點(diǎn)。

c）從自身的解碼過程中學(xué)習(xí)存儲分配。

2 系統(tǒng)模型

本文旨在解決區(qū)塊鏈系統(tǒng)中的存儲可擴(kuò)展性問題以及編碼區(qū)塊鏈中的編碼片段分配（CFA）問題。在系統(tǒng)模型部分，本文詳細(xì)闡述了節(jié)點(diǎn)如何對區(qū)塊進(jìn)行編碼和解碼，并引入了網(wǎng)絡(luò)和節(jié)點(diǎn)模型。本文系統(tǒng)模型的設(shè)計(jì)目標(biāo)是通過提出一種基于強(qiáng)化學(xué)習(xí)的分布式協(xié)議，使節(jié)點(diǎn)能夠合理地調(diào)整編碼片段的分配策略，從而降低存儲和通信成本。

2.1 編碼區(qū)塊鏈模型

所有區(qū)塊都采用相同的編碼策略進(jìn)行編碼，該策略由以下三個基本功能組成。

a）編碼。每個節(jié)點(diǎn)將一個區(qū)塊（如X）劃分為k個片段，記為X={x1，x2，…，xk}。然后，它們使用Reed-Solomon糾錯碼對這k個片段進(jìn)行編碼。具體地，節(jié)點(diǎn)將所述編碼的生成矩陣G與k個片段組成的列向量相乘，得到編碼片段{f1，f2，…，fm}，每個編碼片段的大小均為λ位。為了獲得每個編碼片段fj，j∈{1，2，…，m}，其計(jì)算表達(dá)式如下：

fj=x1×G［j，1］+x2×G［j，2］+…+xk×G［j，k］（1）

實(shí)際上，矩陣G可以是一個擁有m行和k列的范德蒙矩陣。它由兩部分組成（圖3）：一部分是一個k×k對角矩陣，另一部分是一個具有m－k行和k列的奇偶校驗(yàn)矩陣，其中奇偶校驗(yàn)矩陣的每個元素都是一個偽隨機(jī)數(shù)，表示為{z1，1，z1，2，…，zm－k，k}。圖3顯示了一個編碼過程的示例，其中m=7且k=4。

b）存儲。編碼片段由節(jié)點(diǎn)負(fù)責(zé)分發(fā)和存儲。為了保存編碼片段的記錄，節(jié)點(diǎn)具有每個編碼片段的索引，索引的集合表示為J={1，2，…，m}。

c）解碼。為了解碼一個區(qū)塊，節(jié)點(diǎn)必須下載至少d個編碼片段。一般來說，d≥k，并且d的具體取值取決于所采用糾錯碼的類型。在本文中，假設(shè)d=k，即采用最大距離可分離（MDS）代碼。根據(jù)文獻(xiàn)［21］，節(jié)點(diǎn)使用Merkle樹來驗(yàn)證編碼片段的完整性。驗(yàn)證通過后，節(jié)點(diǎn)通過從矩陣G中選擇對應(yīng)于k個編碼片段的行來構(gòu)造可逆矩陣G^。節(jié)點(diǎn)通過將G^的逆乘以由這k個編碼片段組成的列向量，來恢復(fù)原始區(qū)塊X。具體計(jì)算如下：

X=G^－1×［f1，f2，…，fm］（2）

圖4顯示了解碼過程的示例，其中m=7且k=4。

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

本文將編碼區(qū)塊鏈網(wǎng)絡(luò)建模為一個具有n個節(jié)點(diǎn)的圖（V，L），其中V是節(jié)點(diǎn)集，L為鏈接集。該網(wǎng)絡(luò)應(yīng)用［7］中的h跳定位特性表示其中每個節(jié)點(diǎn)需要從距離不超過h跳的節(jié)點(diǎn)獲取足夠數(shù)量的編碼片段進(jìn)行解碼，并使用hv，u表示節(jié)點(diǎn)v和u之間的最小跳數(shù)。對于節(jié)點(diǎn)v，其h跳鄰居為

Hh（v）={u：u∈V，hv，u≤h}（3）

在解碼區(qū)塊時，節(jié)點(diǎn)v將從h跳內(nèi)的鄰居節(jié)點(diǎn)獲取編碼片段，并使用B^（v）存儲從這些鄰居節(jié)點(diǎn)下載的編碼片段的索引。此外，B（v）表示節(jié)點(diǎn)v存儲的編碼片段的集合。為了保證編碼片段的及時響應(yīng)，節(jié)點(diǎn)設(shè)有超時或最大等待時間，如果發(fā)生超時，節(jié)點(diǎn)將重新選擇一個新的鄰居節(jié)點(diǎn)來請求編碼片段。

2.3 節(jié)點(diǎn)模型

每個節(jié)點(diǎn)維護(hù)自身的狀態(tài)空間和動作空間，并接收獎勵。假設(shè)節(jié)點(diǎn)在每個時刻t執(zhí)行一個動作。

a）狀態(tài)。令sv（t）為時刻t時節(jié)點(diǎn)v存儲的編碼片段數(shù)量，其中sv（t）=|B（v）|。節(jié)點(diǎn)v的狀態(tài)空間Sv（t）包含sv（t）可以取值的所有數(shù)值。所有節(jié)點(diǎn)都設(shè)置其存儲上限k，以確保它們不會存儲不必要的編碼片段，節(jié)點(diǎn)v∈V的狀態(tài)空間Sv（t）為

Sv（t）={sv（t）|sv（t）∈{0，…，k}}（4）

b）動作。所有節(jié)點(diǎn)都獨(dú)立地從相同的動作空間中采取行動。在每個時刻t，處于狀態(tài)sv（t）的節(jié)點(diǎn)v根據(jù)Q（sv（t），av（t））的值來采取動作av（t），其中動作av（t）來自動作空間Av（t）。正式地，節(jié)點(diǎn)v的動作空間Av（t）為

Av（t）={av（t）|av（t）∈{－1，0，1}}（5）

其中每個動作av（t）都在集合{－1，0，1}中取一個值。如果節(jié)點(diǎn)v設(shè)置av（t）=1，則它在t時刻時從距離超過h跳的鄰居節(jié)點(diǎn)處獲得一個編碼片段，該編碼片段必須與其在B（v）中存儲的編碼片段不同。另一方面，如果av（t）=－1，則節(jié)點(diǎn)v從其存儲中隨機(jī)刪除一個編碼片段。最后，對于av（t）=0，節(jié)點(diǎn)v在時刻t時保持其編碼片段不變。

c）獎勵。獎勵考慮了存儲和通信成本。此外，為了權(quán)衡存儲和通信成本，獎勵引入權(quán)重參數(shù)ε∈（0，1］，其計(jì)算表達(dá)式如下：

Rv（t）=1λ×sv（t）+ε×D（v）（6）

其中：ε是平衡存儲和通信成本影響的權(quán)重因子；λ表示編碼片段的大?。ㄒ员忍貫閱挝唬?；D（v）表示節(jié)點(diǎn)v解碼區(qū)塊時的通信成本。

在此背景下，值得注意的是獎勵并不取決于節(jié)點(diǎn)的“動作”，而是取決于其“狀態(tài)”。換句話說，如果節(jié)點(diǎn)存儲少量編碼片段，并且產(chǎn)生較小的通信成本，例如當(dāng)節(jié)點(diǎn)在解碼期間嘗試檢索編碼片段時，所有編碼片段都可以從附近的節(jié)點(diǎn)獲得，那么該節(jié)點(diǎn)具有較高的“狀態(tài)獎勵”。

3 可驗(yàn)證的低成本解碼過程

在介紹協(xié)議細(xì)節(jié)之前，本文首先概述節(jié)點(diǎn)執(zhí)行的解碼過程，將文獻(xiàn)［7， 21］中的解碼過程進(jìn)行結(jié)合。簡而言之，文獻(xiàn)［21］使用Merkle樹來驗(yàn)證編碼片段，相較于文獻(xiàn)［19］的方法在計(jì)算成本上更低。另一方面，文獻(xiàn)［7］從位于一跳或多跳之外的節(jié)點(diǎn)獲取編碼片段。

執(zhí)行解碼的節(jié)點(diǎn)（例如v）被稱為請求者。它還記錄通信成本D（v），用于計(jì)算第2章中的獎勵。向節(jié)點(diǎn)v發(fā)送編碼片段的其他節(jié)點(diǎn)被稱為響應(yīng)者。接下來，本文解釋請求者和響應(yīng)者。

a）請求者。算法1顯示了請求者v的操作步驟。其輸入是：（a） B（v）；（b） 其擁有的編碼片段的索引集合，即B^（v），最初設(shè)置為B^（v）=B（v）；（c） 從其他節(jié)點(diǎn)檢索的編碼片段數(shù)量，即z=k－|B^（v）|；（d） 用于查找節(jié)點(diǎn)以獲取編碼片段的跳數(shù)，即，最初設(shè)置為=0。

在解碼過程中，當(dāng)節(jié)點(diǎn)v的編碼片段不足時，即z>0，它將加1，旨在發(fā)現(xiàn)更多的鄰居。它構(gòu)造了一個集合U，其中包含距離它恰好跳的節(jié)點(diǎn)。節(jié)點(diǎn)v從U中隨機(jī)選擇一個節(jié)點(diǎn)u，并向其發(fā)送一個REQ_BLOCK消息，其中包括節(jié)點(diǎn)u的地址、B^（v）中的索引以及所需的編碼片段的數(shù)量z。如果節(jié)點(diǎn)v在給定的超時時間內(nèi)收到響應(yīng)，它會提取編碼片段fj及其相應(yīng)的Merkle樹路徑pj，見算法1第10行。然后，節(jié)點(diǎn)v通過驗(yàn)證功能確保接收到的編碼片段fj的完整性，這包括構(gòu)建一棵Merkle樹，將其葉子作為編碼片段，并使用節(jié)點(diǎn)存儲的Merkle樹根來進(jìn)行驗(yàn)證。

如果編碼片段有效，則節(jié)點(diǎn)v將其添加到B^（v）中，將z的值減1，并將λ添加到通信成本中。請注意，如果響應(yīng)節(jié)點(diǎn)的距離超過h跳，則節(jié)點(diǎn)v將獨(dú)立存儲該編碼片段，即保持h跳定位特性，請參見算法1第15～17行。另一方面，如果編碼片段無效或節(jié)點(diǎn)v尚未在超時時間內(nèi)收到節(jié)點(diǎn)u的答復(fù)，則將u從U中刪除，并向U中的另一個節(jié)點(diǎn)發(fā)送請求，直到U≠或z=0。

算法1 請求者

輸入：B（v），z，B^（v），。

輸出：D（v），B（v），B^（v）。

1 D（v）=0 // 解碼區(qū)塊時初始化節(jié)點(diǎn)v的通信成本

2 while z>0 do

3 =+1 // 增加跳數(shù)以發(fā)現(xiàn)更多鄰居節(jié)點(diǎn)

4 U=H（v）－H－1（v） /* 構(gòu)建包含距離節(jié)點(diǎn)v恰好跳的節(jié)點(diǎn)集合U */

5 while U= do

6 u=random.sample（U，1） /* 從集合U中隨機(jī)選擇一個節(jié)點(diǎn)u */

7 send（"REQ_BLOCK"，u，B^（v），z）

8 while not timeout do

9 if receive（"RPY_BLOCK"） then

10 ［fj，pj］=extract（"RPY_BLOCK"）

11 if verify（fj，pj） then

12 B^（v）=B^（v）∪{j} /*將接收到的編碼片段索引添加到B^（v）中*/

13 D（v）=D（v）+λ // 更新通信成本

14  z=z－1

15 if >h then /*檢查接收到的編碼片段是否在h跳范圍內(nèi)*/

16 B（v）=B（v）∪{fj} /* 節(jié)點(diǎn)v存儲編碼片段fj以保持h跳定位 */

17 end

18 end

19 end

20 end

21 if z≤0 then

22 break

23 end

24 U=U－{u} // 從集合U中刪除已處理的節(jié)點(diǎn)u

25 end

26 end

請求者算法（算法1）包含兩個嵌套的while循環(huán)。在第一個while循環(huán)中，節(jié)點(diǎn)需要嘗試構(gòu)建集合U，其最壞情況下的時間復(fù)雜度是O（kn），其中k是每個節(jié)點(diǎn)最多存儲的編碼片段數(shù)量，n是節(jié)點(diǎn)的數(shù)量。在第二個while循環(huán)中，節(jié)點(diǎn)需要遍歷集合U并執(zhí)行相應(yīng)的通信操作，其最壞情況下的復(fù)雜度是O（knlog n），其中l(wèi)og n是Merkle樹的高度。算法1的時間復(fù)雜度為O（kn+knlog n），但由于通常關(guān)注增長最快的項(xiàng)，整體空間復(fù)雜度可以表示為O（knlog n）。對于空間復(fù)雜度，算法1主要占用空間的是節(jié)點(diǎn)維護(hù)的數(shù)據(jù)結(jié)構(gòu)，包括B（v）、B^（v）和集合U。每個節(jié)點(diǎn)需要存儲的編碼片段數(shù)量最多為k，即|B（v）|≤k、|B^（v）|≤k。因此B（v）和B^（v）的空間復(fù)雜度都是O（k）。此外，在第一個while循環(huán)中，集合U涉及到存儲所有節(jié)點(diǎn)的編號，因此集合U的空間復(fù)雜度是O（n）。綜合考慮節(jié)點(diǎn)維護(hù)的數(shù)據(jù)結(jié)構(gòu)和集合U，整體空間復(fù)雜度可以表示為O（n）。

b）響應(yīng)者。響應(yīng)者的偽代碼如算法2所示。節(jié)點(diǎn)一旦收到REQ_BLOCK消息就成為響應(yīng)者。收到此消息后，響應(yīng)者節(jié)點(diǎn)（假設(shè)為u）提取索引集B^（v）和所需編碼片段的數(shù)量z。它首先檢查其存儲的編碼片段集合B（u）并構(gòu)建一個互補(bǔ)集。如果z≤||，這意味著節(jié)點(diǎn)u存儲的編碼片段多于所需的編碼片段數(shù)量。其次，它從中隨機(jī)選擇z個索引并重建集合^，請參見算法2第5行；否則，將^設(shè)置為整個互補(bǔ)集，請參見算法2第7行。接下來，對于每個編碼片段fj（其中j∈^），節(jié)點(diǎn)u使用Merkle_tree_path函數(shù)來計(jì)算Merkle樹路徑pj。最后，它向節(jié)點(diǎn)v發(fā)送RPY_BLOCK消息，其中包含節(jié)點(diǎn)v的地址、編碼片段fj以及對應(yīng)的Merkle樹路徑pj。

算法2 響應(yīng)者

輸入：REQ_BLOCK，u，B^（v），z。

輸出：RPY_BLOCK，v，fj，pj。

1 if receive（"REQ_BLOCK"） then

2 ［B^（v），z］=extract（"REQ_BLOCK"）

3 =B（u）－B^（v） // 計(jì)算互補(bǔ)集

4 if z≤|| then

5 ^=random.sample（，z） /* 從中隨機(jī)選擇z個索引來構(gòu)建集合^ */

6 else

7 ^= /* 如果需要的編碼片段數(shù)z超過可用編碼片段數(shù)||，則使用整個互補(bǔ)集來構(gòu)建集合^ */

8 end

9 for j∈^ do

10 pj=Merkle_tree_path（fj） /* 計(jì)算^中每個編碼片段fj的Merkle樹路徑 */

11 send（"RPY_BLOCK"，v，fj，pj）

12 end

13 end

響應(yīng)者算法（算法2）包括接收消息、提取消息信息、處理互補(bǔ)集和計(jì)算Merkle樹路徑等四個關(guān)鍵步驟。首先，接收和提取消息信息步驟的時間復(fù)雜度通常為常數(shù)時間，對整體復(fù)雜度的影響較小，因此被忽略。在處理互補(bǔ)集方面，響應(yīng)者節(jié)點(diǎn)需要構(gòu)建互補(bǔ)集和重建集合^，其中||≤k和|^|≤k，兩個集合的時間復(fù)雜度都為O（k）。在計(jì)算Merkle樹路徑方面，對于每個在互補(bǔ)集中的編碼片段，響應(yīng)者節(jié)點(diǎn)需要計(jì)算Merkle樹路徑，其中每個編碼片段計(jì)算的時間復(fù)雜度為O（log n）。因此，Merkle樹路徑計(jì)算的總時間復(fù)雜度為O（klog n）。對于空間復(fù)雜度，算法2主要占用空間的是節(jié)點(diǎn)維護(hù)的數(shù)據(jù)結(jié)構(gòu)，包括B（u）、B^（v）、和^，其中|B（u）|≤k、|B^（v）|≤k、||≤k和|^|≤k。綜上所述，算法2的總時間復(fù)雜度可以表示為O（klog n），而整體空間復(fù)雜度為O（k）。

在此背景下，值得注意的是響應(yīng)者節(jié)點(diǎn)可以不回復(fù)請求消息。為此，編碼區(qū)塊鏈可以利用智能合約［22，23］以代幣或硬幣的形式激勵響應(yīng)者。另外，可以實(shí)施懲罰機(jī)制來驅(qū)逐自私節(jié)點(diǎn)，即誠實(shí)節(jié)點(diǎn)認(rèn)為自私節(jié)點(diǎn)是惡意的并且不回復(fù)其請求。

4 CFA分布式學(xué)習(xí)協(xié)議

DLP-CFA可以分為初始化、學(xué)習(xí)兩個主要階段。DLP-CFA使節(jié)點(diǎn)能夠?qū)W習(xí)和調(diào)整其存儲的編碼片段，如圖5所示。本文采用狀態(tài)-動作-獎勵-狀態(tài)-動作（SARSA）算法［24］中的Q表更新規(guī)則。

4.1 初始化階段

節(jié)點(diǎn)的Q表跨越兩個連續(xù)的時刻。因此，在第一個時刻，節(jié)點(diǎn)執(zhí)行一個動作并且不更新其Q表。參考算法3，對于所有狀態(tài)sv（t）∈Sv（t）和所有動作av（t）∈Av（t），節(jié)點(diǎn)v將其Q值初始化為零。它還通過從m個編碼片段中隨機(jī)選擇k個編碼片段，即其初始狀態(tài)為sv（t）=k，來初始化編碼片段集合B（v）。接下來，節(jié)點(diǎn)v使用玻爾茲曼策略［25］在初始狀態(tài)sv（t）下選擇一個初始動作av（t），其中選擇動作av（t）的概率為

π（sv（t），av（t））=eφ（sv（t））Q（sv（t），av（t））∑b∈Av（t）eφ（sv（t））Q（sv（t），b）（7）

其中：

φ（sv（t））=ln c（sv（t））maxa，b∈Av（t）|Q（sv（t），b）－Q（sv（t），a）|（8）

這里，φ（sv（t））是時刻t時狀態(tài)sv（t）的探索率；c（sv（t））表示節(jié)點(diǎn)v在時刻t之前經(jīng)歷狀態(tài)sv（t）的次數(shù)。在開始學(xué)習(xí)時，玻爾茲曼策略會探索更多的狀態(tài)，隨后趨于收斂到具有較高Q值的狀態(tài)，即更頻繁地訪問該狀態(tài)。

最初，φ（sv（t））=0，節(jié)點(diǎn)v以相等的概率從Av（t）中選擇一個動作。在此階段，如果節(jié)點(diǎn)v恰好選擇動作av（t）=1，則將其修改為av（t）=0，因?yàn)樗恍枰鎯︻~外的編碼片段。換句話說，在初始階段，節(jié)點(diǎn)v只有在av（t）=－1時才執(zhí)行該動作。最后，當(dāng)av（t）=－1時，節(jié)點(diǎn)v隨機(jī)刪除其存儲中的編碼片段并進(jìn)入學(xué)習(xí)階段。

算法3 DLP-CFA初始化階段

輸入：h，m，k。

輸出：sv（t），v，av（t），B（v），Q。

1 初始化Q（sv（t），av（t））=0，sv（t）∈Sv（t），av（t）∈Av（t）

2 B（v）=random.sample（{1，…，m}，k） /* 通過從m個編碼片段中隨機(jī)選擇k個編碼片段來初始化B（v） */

3 sv（t）=|B（v）| // 獲取當(dāng)前狀態(tài)

4 使用式（7）來選擇av（t）

5 if av（t）==1 then

6 av（t）=0

7 end

8 if av（t）==－1 then

9 B（v）=random.remove（B（v），1） /* 從B（v）中隨機(jī)刪除一個編碼片段 */

10 end

算法3的時間復(fù)雜度主要涉及Q表和B（v）的初始化以及動作的執(zhí)行。Q表初始化的時間復(fù)雜度為O（|Sv（t）|×|Av（t）|），其中|Sv（t）|=1和|Av（t）|=3。隨機(jī)選擇編碼片段操作的時間復(fù)雜度為O（mk），而當(dāng)動作av（t）=－1時執(zhí)行動作的時間復(fù)雜度為O（m）。在最壞情況下，整體初始化階段的時間復(fù)雜度可以表示為O（mk）。在空間復(fù)雜度方面，算法3的空間復(fù)雜度主要受節(jié)點(diǎn)的Q表和編碼片段集合B（v）的影響。Q表的空間復(fù)雜度為O（|Sv（t）|×|Av（t）|），而編碼片段集合B（v）的空間復(fù)雜度為O（|B（v）|），其中|B（v）|≤k。因此，整體空間復(fù)雜度為O（k）。

4.2 學(xué)習(xí)階段

在學(xué)習(xí)階段，每個時刻，節(jié)點(diǎn)會更新其存儲的編碼片段，即B（v），還更新其Q表。參考算法4，在將狀態(tài)sv（t）初始化為當(dāng)前存儲的編碼片段的數(shù)量|B（v）|之后，節(jié)點(diǎn)v使用玻爾茲曼策略選擇一個動作。如果滿足以下任一個條件：a） sv（t）=k且av（t）=1；b） sv（t）=0且av（t）=－1。節(jié)點(diǎn)將動作修改為零，即av（t）=0。這是因?yàn)樵谌魏我环N情況下，該節(jié)點(diǎn)都無法執(zhí)行所需的操作。

如果選擇的動作av（t）=1，則節(jié)點(diǎn)v需要獲取一個編碼片段來存儲。具體來說，它需要獲取一個編碼片段進(jìn)行存儲，該編碼片段在h跳內(nèi)沒有被任何節(jié)點(diǎn)存儲，即Hh（v）中沒有節(jié)點(diǎn)具有所請求的編碼片段。為此，它以B（v）、z、B^（v）和作為輸入運(yùn)行算法1，其中B^（v）是通過上一個時刻的解碼獲得的，請參見算法4第15行。算法1從距離至少h+1跳的節(jié)點(diǎn)返回一個不在B^（v）中的編碼片段。另一方面，如果av（t）=－1，則節(jié)點(diǎn)v只是刪除一個其存儲的編碼片段。在此階段，節(jié)點(diǎn)v的狀態(tài)更改為sv（t+1），并更新|B（v）|。

在執(zhí)行動作av（t）后，節(jié)點(diǎn)v解碼一個區(qū)塊。解碼過程遵循第4章中的步驟，其中輸入為z=k－|B（v）|、h=0和B^（v）=B（v）。解碼后，節(jié)點(diǎn)v存儲的編碼片段數(shù)量會增加，這是因?yàn)楣?jié)點(diǎn)v存儲從距離超過h跳的節(jié)點(diǎn)檢索到的編碼片段。正如在4.2節(jié)中闡明的那樣，節(jié)點(diǎn)v在執(zhí)行一個動作和計(jì)算獎勵時運(yùn)行算法1。因此，節(jié)點(diǎn)的狀態(tài)變化是由其“動作”和獎勵計(jì)算引起的。

算法4 DLP-CFA學(xué)習(xí)階段

輸入：h，k，t，α，β，γ，σ，B（v），B^（v），Q。

輸出：sv（t），av（t），B（v），Q，α。

1 sv（t）=|B（v）| // 獲取當(dāng)前狀態(tài)

2 使用式（7）來選擇av（t）

3 if （sv（t）==k and av（t）==1） or （sv（t）==0 and av（t）==－1）

4 av（t）==0 // 如果條件滿足，則將動作av（t）修改為0

5 end

6 if av（t）==1 then

7 B（v）=Requester（B（v），1，B^（v），h） /* 如果條件滿足，節(jié)點(diǎn)執(zhí)行Requester函數(shù)獲取一個編碼片段 */

8 end

9 if av（t）==－1 then

10 B（v）=random.remove（B（v），1） /* 從B（v）中隨機(jī)刪除一個編碼片段 */

11 end

12 z=k－|B（v）| // 計(jì)算解碼所需編碼片段個數(shù)z

13 =0

14 B^（v）=B（v）

15 D（v），B^（v），B（v）=Requester（B（v），z，B^（v），） /* 運(yùn)行算法1獲取編碼片段并計(jì)算出節(jié)點(diǎn)v的通信開銷 */

16 sv（t+1）=|B（v）| // 獲取當(dāng)前狀態(tài)

17 計(jì)算獎勵Rv（t）=1λ×sv（t+1）+ε×D（v）

18 使用式（9）來更新Q表

19 使用式（10）來計(jì)算αt－1

接下來，更新節(jié)點(diǎn)v的狀態(tài)sv（t+1）。它使用式（6）計(jì)算獎勵Rv（t），將sv（t）替換為sv（t+1）。最后，節(jié)點(diǎn)v將狀態(tài)-動作對（sv（t－1），av（t－1））的Q值更新為

Q（sv（t－1），av（t－1））=Q（sv（t－1），av（t－1））+αt－1（Rv（t）+

γQ（sv（t+1），av（t+1））－Q（sv（t－1），av（t－1）））（9）

其中：γ是貼現(xiàn)率，而αt－1表示學(xué)習(xí)率。在每個時刻結(jié)束后，學(xué)習(xí)率都會降低，以確保收斂，具體如下［26］：

αt=α×βtσ（10）

其中：α是初始學(xué)習(xí)率；0<β<1是衰減率；σ是恒定步長。

算法4的時間復(fù)雜度主要受到動作執(zhí)行和計(jì)算通信開銷的影響。對于執(zhí)行動作av（t）=1的情況，節(jié)點(diǎn)v執(zhí)行Requester函數(shù)來獲取一個編碼片段。該函數(shù)的時間復(fù)雜度主要包括算法1的執(zhí)行。由于只需要獲取一個編碼片段，該函數(shù)的時間復(fù)雜度為O（n+nlog n）。對于執(zhí)行動作av（t）=－1的情況，節(jié)點(diǎn)執(zhí)行刪除操作的時間復(fù)雜度為O（k）。同時，計(jì)算通信開銷的時間復(fù)雜度為O（kn+knlog n）。在最差情況下，總的時間復(fù)雜度可以表示為O（knlog n）。在空間復(fù)雜度方面，算法4主要占用空間的是節(jié)點(diǎn)維護(hù)的數(shù)據(jù)結(jié)構(gòu)，包括B（v）、B^（v）和Q表，其中|B（v）|≤k、|B^（v）|≤k，而Q表的空間復(fù)雜度為O（|Sv（t）|×|Av（t）|）。因此，整體空間復(fù)雜度可以表示為O（k）。

5 仿真實(shí)驗(yàn)

本實(shí)驗(yàn)在一臺搭載Intel Core i5-5287U處理器的筆記本電腦上進(jìn)行，該處理器具有四個核心和八個線程，運(yùn)行頻率為29 GHz，內(nèi)存為8 GB，硬盤容量為1 TB。本實(shí)驗(yàn)使用Python 3.9版本。網(wǎng)絡(luò)拓?fù)涫窃谝粋€面積為100 m2的區(qū)域內(nèi)隨機(jī)生成的，包含100個節(jié)點(diǎn)。如果兩個節(jié)點(diǎn)的距離小于20 m，則它們是一跳鄰居。本文將DLP-CFA中式（10）的學(xué)習(xí)率步長σ設(shè)置為50。假設(shè)所有區(qū)塊的大小恒定為1 MB。本實(shí)驗(yàn)定義一個稱為歸一化獎勵的度量，用R^（t）表示，它是所有節(jié)點(diǎn)的總體獎勵。正式地，歸一化獎勵為

R^（t）=1n∑v∈VRv（t）（11）

該實(shí)驗(yàn)只考慮一個區(qū)塊，因?yàn)樗袎K都使用相同的策略進(jìn)行編碼。該實(shí)驗(yàn)省略任何關(guān)于區(qū)塊挖礦的討論，有興趣的讀者可以參考文獻(xiàn)［6］。仿真實(shí)驗(yàn)中，本文將DLP-CFA與現(xiàn)有的解決CFA問題的方法進(jìn)行對比，即文獻(xiàn)［7］中提出的集中式編碼片段分配（CSA）算法和分布式動態(tài)調(diào)整（DA）算法。簡而言之，在CSA算法中，一個中央控制器分配編碼片段給所有節(jié)點(diǎn)，其目的是最大限度地降低總體存儲和通信成本。使用DA算法，每個節(jié)點(diǎn)發(fā)現(xiàn)其h跳鄰居處存儲的編碼片段，并動態(tài)調(diào)整其存儲的編碼片段。

5.1 k的影響

該實(shí)驗(yàn)首先研究DLP-CFA在不同k值下的收斂速度。該實(shí)驗(yàn)設(shè)置以下參數(shù)值：n=100、ε=0.9、h=2、m=200、α=0.1、γ=0.9和β=0.95。圖6的結(jié)果表明，隨著k的增加，DLP-CFA的收斂速度減少，并且歸一化獎勵收斂到比k較小時更高的值。這是因?yàn)檩^高的k值意味著較大的狀態(tài)空間，從而減慢收斂速度。另一方面，歸一化獎勵隨著k的增加而增加。因?yàn)榫幋a片段的數(shù)量增加，每個編碼片段的大小減小，從而降低節(jié)點(diǎn)存儲相同編碼片段集的概率。因此，DLP-CFA具有更高的歸一化獎勵或更高的收斂性和學(xué)習(xí)效率。本文注意到，當(dāng)k=100時，DLP-CFA的歸一化獎勵在1 000個時間周期內(nèi)收斂到0.010 7。在k=100時，與k的其他值相比，DLP-CFA收斂到更高的歸一化獎勵。

5.2 超參數(shù)α、β、γ、σ

為了研究上述超參數(shù)對DLP-CFA收斂性的影響，本文使用以下參數(shù)值：n=100、ε=0.9、h=2、m=200和k=100。

本實(shí)驗(yàn)首先考慮初始學(xué)習(xí)率α，將其設(shè)置為{1，0.5，0.1，0.05}中的一個值，其他三個參數(shù)固定為β=0.65、γ=0.6和σ=50。圖7表明，當(dāng)α減小時，DLP-CFA的收斂速度也增加。這是因?yàn)檩^小的α值意味著每個時期對Q的更新較小，這反過來又減慢了學(xué)習(xí)和收斂速度。結(jié)果表明，α=0.1導(dǎo)致DLP-CFA收斂到更高的歸一化獎勵。

接下來，本實(shí)驗(yàn)研究衰減率β，其取值為{095，065，035，005}。本實(shí)驗(yàn)使用α=0.1，γ=0.6和σ=50。根據(jù)圖8，隨著β的增加，DLP-CFA的收斂速度降低。這是因?yàn)閷W(xué)習(xí)率α是衰減率β的函數(shù)，參見式（10）。因此，較大的β意味著較大的學(xué)習(xí)率，即學(xué)習(xí)率會隨著時刻的增加而降低得更慢。結(jié)果表明，β=0.95使DLP-CFA能夠收斂到更高的歸一化獎勵。

本實(shí)驗(yàn)現(xiàn)在研究范圍內(nèi)的貼現(xiàn)率γ。本實(shí)驗(yàn)設(shè)置α=0.1、β=0.95和σ=50。圖9顯示，具有較大折扣率的DLP-CFA需要更多的時間才能收斂。因?yàn)檩^小的γ表示更新在時刻t－1選擇的狀態(tài)-動作對的Q值，對于時刻t的Q值的影響較小，參見式（9）。此外，圖9顯示γ=0.9時具有最高的收斂歸一化獎勵。因?yàn)槿绻锰?，DLP-CFA就會優(yōu)先考慮即時獎勵而不是長期收益。相反，如果γ太大，DLP-CFA會根據(jù)在時刻t下動作積極更新Q值。

本實(shí)驗(yàn)還研究學(xué)習(xí)率步長σ，將其設(shè)置為集合{10，50，100，150}中的一個值，并設(shè)置α=0.1、β=0.95和γ=0.9。圖10顯示，DLP-CFA需要更多的時間周期才能以更大的步長收斂。原因與圖8相同，因?yàn)棣烈彩遣介Lσ的函數(shù)。結(jié)果表明，σ=50時收斂到更高的歸一化獎勵。

圖11展示了上述結(jié)果中具有最大歸一化獎勵的參數(shù)，它表明α=0.1、β=0.95、σ=50和γ=0.9是很好的超參數(shù)選擇。

5.3 與CSA和DA的比較

本實(shí)驗(yàn)研究了DLP-CFA的參數(shù)，并對其性能與CSA和DA進(jìn)行了比較評估。本實(shí)驗(yàn)設(shè)置參數(shù)n=100、ε=0.9、h=2、k=100和m=200。DLP-CFA的超參數(shù)按照5.2節(jié)進(jìn)行設(shè)置。從圖12可以看出，DLP-CFA的歸一化獎勵分別比DA和CSA高6%和7%。

5.4 平均存儲和通信成本

本實(shí)驗(yàn)現(xiàn)在研究使用DLP-CFA時的節(jié)點(diǎn)存儲和通信成本，設(shè)置n=100、ε=0.9、h=2、k=100和m=200。圖13顯示，16％的節(jié)點(diǎn)存儲少于10％的編碼片段，即少于10個片段。另一方面，80%的節(jié)點(diǎn)存儲10%～20%的編碼片段，只有不到5%的節(jié)點(diǎn)存儲超過50%的編碼片段。從圖14中可以看出，76%的節(jié)點(diǎn)從距離為一跳的節(jié)點(diǎn)獲取編碼片段。大約12%的節(jié)點(diǎn)從距離超過一跳的節(jié)點(diǎn)獲取編碼片段。

5.5 五個節(jié)點(diǎn)示例

為了展示每個節(jié)點(diǎn)的實(shí)際存儲演變，本實(shí)驗(yàn)研究了一個具有五個節(jié)點(diǎn)的示例網(wǎng)絡(luò)。本實(shí)驗(yàn)展示了每個節(jié)點(diǎn){v1，…，v5}在每個時期的歸一化獎勵、存儲和通信成本。本實(shí)驗(yàn)設(shè)置ε=0.9、h=1、k=100和m=200。

在圖15～17中，本實(shí)驗(yàn)看到節(jié)點(diǎn)的存儲量越高，通信成本就越低，反之亦然。如圖16所示，節(jié)點(diǎn)存儲水平在前300個時刻內(nèi)迅速下降，這是因?yàn)樽畛跛泄?jié)點(diǎn)都存儲k個編碼片段，這超出解碼一個區(qū)塊所需的編碼片段的數(shù)量。在300～1 000個時間周期之間，節(jié)點(diǎn)v1、v3和v5的存儲水平在收斂到最終值28之前波動，而節(jié)點(diǎn)v2和v4的存儲水平在收斂到最終值71之前波動。

5.6 節(jié)點(diǎn)離開和加入

現(xiàn)在討論一個動態(tài)場景，其中節(jié)點(diǎn)會隨機(jī)離開并且新節(jié)點(diǎn)加入網(wǎng)絡(luò)。本實(shí)驗(yàn)用c表示離開網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量和加入網(wǎng)絡(luò)的新節(jié)點(diǎn)數(shù)。參數(shù)設(shè)置為n=100、ε=0.9、h=2、k=100、m=200和c={10，15，20，25}。在這個實(shí)驗(yàn)中，有c個隨機(jī)節(jié)點(diǎn)在時刻t=3 000時離開網(wǎng)絡(luò)，這標(biāo)志著DLP-CFA達(dá)到穩(wěn)定的編碼片段分配狀態(tài)。同時，c個新節(jié)點(diǎn)加入網(wǎng)絡(luò)，但不存儲任何編碼片段，即需要從現(xiàn)有節(jié)點(diǎn)獲取編碼片段。

參考圖18，隨著更多的節(jié)點(diǎn)離開和加入，即較高的c值，DLP-CFA需要更多的時間才能收斂。這是因?yàn)楦嗟墓?jié)點(diǎn)需要學(xué)習(xí)分配編碼片段，并且節(jié)點(diǎn)之間存在更多的交互。此外，當(dāng)c=10時，收斂后的歸一化獎勵增加，而當(dāng)c=25時，收斂后的歸一化獎勵減少。這是因?yàn)楫?dāng)大量節(jié)點(diǎn)離開網(wǎng)絡(luò)時，現(xiàn)有節(jié)點(diǎn)和新節(jié)點(diǎn)都需要存儲新的編碼片段以滿足h跳定位屬性。

現(xiàn)在本實(shí)驗(yàn)研究在c個節(jié)點(diǎn)離開和加入網(wǎng)絡(luò)后，導(dǎo)致編碼片段重新分配的通信成本。圖19顯示DLP-CFA和DA的通信成本都隨著c的增加而增加。這種增長可以歸因于新節(jié)點(diǎn)數(shù)量的增加，這需要更多的編碼片段重新分配給新加入的節(jié)點(diǎn)。此外，圖19顯示DLP-CFA的通信成本比DA低45%。

5.7 節(jié)點(diǎn)故障

最后，本實(shí)驗(yàn)研究當(dāng)μ個節(jié)點(diǎn)發(fā)生故障或受到攻擊時的情況。在這種情況下，當(dāng)一個節(jié)點(diǎn)發(fā)生故障或受到攻擊時，可以通過其回復(fù)無效的編碼片段來進(jìn)行檢測。實(shí)驗(yàn)中參數(shù)值設(shè)置為n=100、ε=0.9、h=2、k=100和m=200，μ從{10，15，20，25}中選擇一個值。

從圖20中可以看出，隨著μ值增加，DLP-CFA收斂速度變慢，這是因?yàn)楫?dāng)具有所需編碼片段的節(jié)點(diǎn)發(fā)生故障時，更多的編碼片段變得不可使用。此外，歸一化獎勵隨著μ值的增加而減少，這是因?yàn)榇罅抗?jié)點(diǎn)故障意味著誠實(shí)節(jié)點(diǎn)需要存儲更多的編碼片段，以確保區(qū)塊能夠成功解碼。然而，當(dāng)有25個節(jié)點(diǎn)發(fā)生故障時，歸一化獎勵最多僅減少3%。

區(qū)塊鏈編碼存儲方法已經(jīng)在前期研究中［27］利用實(shí)際的比特幣區(qū)塊鏈數(shù)據(jù)進(jìn)行了驗(yàn)證，其編碼方法與本文方法相似，能夠支撐本文方法在實(shí)際的區(qū)塊鏈中應(yīng)用的實(shí)用性，有效降低區(qū)塊鏈節(jié)點(diǎn)存儲開銷。此外，本文方法在文獻(xiàn)［27］的基礎(chǔ)上進(jìn)一步優(yōu)化了節(jié)點(diǎn)存儲編碼數(shù)據(jù)的分配方法，降低傳輸成本并確保編碼區(qū)塊鏈的可解碼性。

6 結(jié)束語

本文考慮了區(qū)塊鏈系統(tǒng)中的分布式編碼片段分配問題，為了解決此問題，提出了一種稱為DLP-CFA的新穎協(xié)議，節(jié)點(diǎn)使用該協(xié)議以降低存儲和通信成本的方式放置編碼片段。所進(jìn)行的模擬研究比較了現(xiàn)有的分布式和集中式算法。結(jié)果顯示，DLP-CFA在總體獎勵方面比這些算法高出7%。本文的研究還考慮節(jié)點(diǎn)離開/加入網(wǎng)絡(luò)和節(jié)點(diǎn)故障的場景。結(jié)果表明，與之前的算法相比，DLP-CFA 降低了55%的通信成本。總體而言，本文提出的分布式學(xué)習(xí)協(xié)議在解決編碼片段分配問題上取得了顯著的進(jìn)展。未來的研究將聚焦于區(qū)塊鏈智能合約的數(shù)據(jù)編碼存儲問題，通過對智能合約進(jìn)行編碼，并考慮合約的調(diào)用頻率，以進(jìn)一步降低區(qū)塊鏈存儲成本和傳輸開銷。

參考文獻(xiàn)：

［1］Xie Junfeng， Yu F R， Huang Tao，et al. A survey on the scalability of blockchain systems ［J］. IEEE Network， 2019， 33（5）： 166-173.

［2］Si Honghao， Niu Baoning. Research on blockchain data availability and storage scalability ［J］. Future Internet， 2023， 15（6）： 212.

［3］Yang Changlin， Chin K W， Wang Jiguang，et al. Scaling blockchains with error correction codes： a survey on coded blockchains ［J］. ACM Computing Surveys， 2024，56（6）： 1-33.

［4］Yu Mingchao， Sahraei S， Li Songze，et al. Coded Merkle tree： solving data availability attacks in blockchains ［C］// Proc of International Conference on Financial Cryptography and Data Security. Cham： Springer， 2020： 114-134.

［5］Das S， Kolluri A， Saxena P，et al. On the security of blockchain consensus protocols ［C］// Proc of the 14th International Conference on Information Systems Security. Cham：Springer， 2018： 465-480.

［6］Wu Huihui， Ashikhmin A， Wang Xiaodong，et al. Distributed error correction coding scheme for low storage blockchain systems ［J］. IEEE Internet of Things Journal， 2020， 7（8）： 7054-7071.

［7］Yang Changlin， Wang Xiaodong， Ashikhmin A. Storage and communication tradeoff for wireless coded blockchains ［J］. IEEE Systems Journal， 2021， 16（2）： 2911-2922.

［8］Yang Changlin， Wang Xiaodong， Jiang Zigui，et al. On min-max sto-rage for resource—restricted clients in coded blockchain systems ［J］. IEEE Internet of Things Journal， 2023，10（20）： 17988-17999.

［9］趙國鋒， 張明聰， 周繼華， 等. 基于糾刪碼的區(qū)塊鏈系統(tǒng)區(qū)塊文件存儲模型的研究與應(yīng)用 ［J］. 信息網(wǎng)絡(luò)安全， 2019 （2）： 28-35. （Zhao Guofeng， Zhang Mingcong， Zhou Jihua，et al. Research and application of block file storage model based on blockchain system of erasure code ［J］. Netinfo Security， 2019（2）： 28-35.）

［10］Dai Mingjun， Zhang Shengli， Wang Hui，et al. A low storage room requirement framework for distributed ledger in blockchain ［J］. IEEE Access， 2018， 6： 22970-22975.

［11］Qi Xiaodong， Zhang Zhao， Jin Cheqing，et al. BFT-Store： storage partition for permissioned blockchain via erasure coding ［C］// Proc of the 36th International Conference on Data Engineering. Pisca-taway， NJ： IEEE Press， 2020： 1926-1929.

［12］Qi Xiaodong， Zhang Zhao， Jin Cheqing，et al. A reliable storage partition for permissioned blockchain ［J］. IEEE Trans on Knowledge and Data Engineering， 2020， 33（1）： 14-27.

［13］Raman R K， Varshney L R. Coding for scalable blockchains via dynamic distributed storage ［J］. IEEE/ACM Trans on Networking， 2021， 29（6）： 2588-2601.

［14］Kadhe S， Chung J， Ramchandran K. SeF： a secure fountain architecture for slashing storage costs in blockchains ［EB/OL］. （2019-06-28） ［2023-12-16］. http：//arxiv.org/abs/1906.12140.

［15］張玉書， 何曉彤， 肖祥立， 等. 一種基于糾刪碼的區(qū)塊鏈賬本分組存儲優(yōu)化方法 ［J］. 計(jì)算機(jī)科學(xué)， 2023， 50（10）： 350-361. （Zhang Yushu， He Xiaotong， Xiao Xiangli，et al.

Grouping storage opimization method for blockchain ledger based on erasure code ［J］. Computer Science， 2023， 50（10）： 350-361.）

［16］Qu Bin， Wang L E， Liu Peng，et al. GCBlock： a grouping and co-ding based storage scheme for blockchain system ［J］. IEEE Access， 2020， 8： 48325-48336.

［17］Yu Ruize， Yang Changlin， Liu Ying. FSC： file storage in coded blockchain with C-PBFT consensus protocol ［C］// Proc of International Conference on Service Science. Piscataway， NJ： IEEE Press， 2022： 289-296.

［18］Li Chunlin， Zhang Jing， Yang Xianmin，et al. Lightweight blockchain consensus mechanism and storage optimization for resource-constrained IoT devices ［J］. Information Processing & Management， 2021， 58（4）： 102602.

［19］Perard D， Lacan J， Bachy Y，et al. Erasure code-based low storage blockchain node ［C］// Proc of IEEE International Conference on Internet of Things and IEEE Green Computing and Communications and IEEE Cyber， Physical and Social Computing and IEEE Smart Data. Piscataway， NJ： IEEE Press， 2018： 1622-1627.

［20］尹芙蓉， 朱承宇， 趙斌， 等. 基于CITA區(qū)塊鏈的糾刪碼分片存儲實(shí)現(xiàn) ［J］. 華東師范大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2021，2021（5）： 48-59. （Yin Furong， Zhu Chengyu， Zhao Bin，et al. Erasure code partition storage based on the CITA blockchain ［J］. Journal of East China Normal University： Natural Science， 2021，2021（5）： 48-59.）

［21］Miller A， Xia Yu， Croman K，et al. The honey badger of BFT protocols ［C］// Proc of the 26th ACM SIGSAC Conference on Computer and Communications Security. New York：ACM Press， 2016： 31-42.

［22］Zheng Zibin， Xie Shaoan， Dai Hongning，et al. An overview on smart contracts： challenges， advances and platforms ［J］. Future Generation Computer Systems， 2020， 105： 475-491.

［23］陳偉利， 鄭子彬. 區(qū)塊鏈數(shù)據(jù)分析： 現(xiàn)狀、趨勢與挑戰(zhàn) ［J］. 計(jì)算機(jī)研究與發(fā)展， 2018， 55（9）： 1853-1870. （Chen Weili， Zheng Zibin. Blockchain data analysis： a review of status， trends and challenges ［J］. Journal of Computer Research and Development， 2018， 55（9）： 1853-1870.）

［24］Wang Qiang， Zhan Zhongli. Reinforcement learning model， algorithms and its application ［C］// Proc of International Conference on Mechatronic Science， Electric Engineering and Computer. Pisca-taway， NJ： IEEE Press， 2011： 1143-1146.

［25］Singh S， Jaakkola T， Littman M L，et al. Convergence results for single-step on-policy reinforcement-learning algorithms ［J］. Machine Learning， 2000， 38： 287-308.

［26］She Daoming， Jia Minping. Wear indicator construction of rolling bearings based on multi-channel deep convolutional neural network with exponentially decaying learning rate ［J］. Measurement， 2019， 135： 368-375.

［27］Yang Changlin， Ashikhmin A， Wang Xiaodong，et al. Rateless coded blockchain for dynamic IoT networks ［EB/OL］. （2023-05-06）. https：//arxiv.org/abs/2305.03895.

［28］王鋒， 張強(qiáng)， 劉揚(yáng)， 等. 從擴(kuò)展性角度看區(qū)塊鏈 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（10）： 2896-2907. （Wang Feng， Zhang Qiang， Liu Yang，et al. Research progress of blockchain from perspective of scalability ［J］. Application Research of Computers， 2023， 40（10）： 2896-2907.）

［29］胡寧玉， 郝耀軍， 常建龍， 等. 基于變色龍hash的區(qū)塊鏈可擴(kuò)展存儲方案 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（12）： 3539-3544， 3550. （Hu Ningyu， Hao Yaojun， Chang Jianlong，et al. Scalable sto-rage scheme based on chameleon hash for blockchain ［J］. Application Research of Computers， 2023， 40（12）： 3539-3544， 3550.）