尹笑蓉 朱承宇 趙斌 張召

摘要：區(qū)塊鏈系統(tǒng)采用全復(fù)制的數(shù)據(jù)存儲機(jī)制，為每個節(jié)點(diǎn)保留整個區(qū)塊鏈的完整副本，系統(tǒng)擴(kuò)展性差. 同時由于區(qū)塊鏈系統(tǒng)中拜占庭節(jié)點(diǎn)的存在，導(dǎo)致傳統(tǒng)分布式系統(tǒng)中使用的分片方案不能被直接應(yīng)用于區(qū) 塊鏈系統(tǒng)中.本文結(jié)合糾刪碼和拜占庭容錯算法，使每個區(qū)塊的存儲消耗由O（n）降到0（1），增強(qiáng)了系統(tǒng)的 可擴(kuò)展性.本文還提出了對區(qū)塊數(shù)據(jù)進(jìn)行劃分的方法，在降低存儲冗余的同時減小對查詢效率的影響.提 出了無需網(wǎng)絡(luò)通信的編碼塊存儲方法，降低了系統(tǒng)存儲和通信開銷.還提出了區(qū)塊鏈節(jié)點(diǎn)加入和退出的動 態(tài)重編碼方法，既保證系統(tǒng)的穩(wěn)定性，又降低了系統(tǒng)重編碼開銷.最后，在開源區(qū)塊鏈系統(tǒng)CITA上實(shí)現(xiàn)， 并通過充分的實(shí)驗(yàn)，證明系統(tǒng)可擴(kuò)展性、可用性和存儲效率提升.

關(guān)鍵詞：區(qū)塊鏈;糾刪碼;拜占庭容錯;存儲可擴(kuò)展性

中圖分類號：TP302?????? 文獻(xiàn)標(biāo)志碼：A DOI： 10.3969/j.issn.1000-5641.2021.05.005

Erasure code partition storage based on the CITA blockchain

YIN Furong1， ZHU Chengyu1， ZHAO Bin2， ZHANG Zhao1

（X. School of Data Science and Engineering， East China Normal University， Shanghai 200062， China;

2. School of Computer and Electronic Information/School of Artificial Intelligence，

Nanjing Normal University， Nanjing 210023， China）

Abstract： Blockchain system adopts full replication data storage mechanism， which retains a complete copy of the whole block chain for each node. The scalability of the system is poor. Due to the existence of Byzantine nodes in the blockchain system， the shard scheme used in the traditional distributed system cannot be directly applied in the blockchain system. In this paper， the storage consumption of each block is reduced from O（n） to O（1） by combining erasure code and Byzantine fault-tolerant algorithm， and the scalability of the system is enhanced. This paper proposes a method to partition block data， which can reduce the storage redundancy and affect the query efficiency less. A coding block storage method without network communication is proposed to reduce the system storage and communication overhead. In addition， a dynamic recoding method for entry and exit of blockchain nodes is proposed， which not only ensures the reliability of the system， but also reduces the system recoding overhead. Finally， the system is implemented on the open source blockchain system CITA， and through sufficient experiments， it is proved that the system has improved scalability， availability and storage efficiency.

Keywords： blockchain; erasure code; Byzantine fault tolerance; storage scalability

收稿日期：2021-08-07

基金項(xiàng)目：國家自然科學(xué)基金（U1811264，U1911203， 6197215（2）

通信作者：張召，女，教授，博士生導(dǎo)師，研究方向?yàn)閰^(qū)塊鏈系統(tǒng)研發(fā)、海量數(shù)據(jù)管理與分析

E-mail： zhzhang@dase.ecnu.edu.cn

0引 言

區(qū)塊鏈?zhǔn)且环N分布式、去中心化、無需信任的數(shù)據(jù)庫系統(tǒng)，正在被越來越廣泛地應(yīng)用于金融管 理、銀行、保險等領(lǐng)域.在區(qū)塊鏈網(wǎng)絡(luò)中，每個節(jié)點(diǎn)都需要遵守基于密碼學(xué)的規(guī)則，每筆交易都需要與 網(wǎng)絡(luò)中的其他節(jié)點(diǎn)達(dá)成共識，不需要任何第三方機(jī)構(gòu)背書，降低了運(yùn)行成本.

隨著區(qū)塊鏈系統(tǒng)規(guī)模的不斷擴(kuò)大，全復(fù)制的方法已經(jīng)不能適應(yīng)海量數(shù)據(jù)的增長需求.全復(fù)制存儲 機(jī)制中數(shù)據(jù)量隨節(jié)點(diǎn)數(shù)量增加線性增長，整個系統(tǒng)需要投入巨大的存儲空間來保存區(qū)塊，在有N個參與者的情況下，每個塊的總體存儲消耗為O（N）.目前，逐步提高的交易吞吐率導(dǎo)致存儲成為了整個區(qū) 塊鏈擴(kuò)展的瓶頸.研究者一直在尋找一種高效的區(qū)塊鏈擴(kuò)容方案.

為了緩解區(qū)塊鏈系統(tǒng)的存儲擴(kuò)展性問題，業(yè)界提出了許多方案.如只在客戶端保留區(qū)塊頭部，在 全節(jié)點(diǎn)保留著完整區(qū)塊的輕量級客戶端[1-21.其雖然減輕了客戶端的存儲壓力，但每個全節(jié)點(diǎn)仍保留所 有區(qū)塊數(shù)據(jù)的完整副本.閃電網(wǎng)絡(luò)收集多個微支付，最終僅將余額信息上傳到區(qū)塊鏈網(wǎng)絡(luò)上，其雖 然減輕了每個節(jié)點(diǎn)的存儲壓力，但沒有從根本上解決區(qū)塊數(shù)據(jù)全復(fù)制的問題.分片技術(shù)[4-5]將區(qū)塊鏈網(wǎng) 絡(luò)分成多個組，每個組存儲系統(tǒng)中的部分?jǐn)?shù)據(jù)，但在同一組內(nèi)，仍采取了全復(fù)制的存儲方式.

糾刪碼是一種數(shù)據(jù)保護(hù)方法，最初被用于解決網(wǎng)絡(luò)傳輸中的丟包問題，后被推廣到存儲領(lǐng)域，可 提高存儲的可靠性.本文繼承BFT （Byzantine Fault Tolerance，拜占庭容錯）協(xié)議的假設(shè)，實(shí)現(xiàn)了一 種基于糾刪碼的區(qū)塊鏈系統(tǒng)，即在有n個節(jié)點(diǎn)的系統(tǒng)中，最多有/=「?]個節(jié)點(diǎn)是能夠入侵甚至破 壞整個網(wǎng)絡(luò)的拜占庭節(jié)點(diǎn).為了保證基于糾刪碼的系統(tǒng)在有/個節(jié)點(diǎn)發(fā)生故障時仍能正常運(yùn)行，須保 證糾刪碼編碼后的冗余塊個數(shù)不小于/，同時為降低冗余度，令冗余塊個數(shù)為/.與全復(fù)制的存儲方式 相比，本文實(shí)現(xiàn)的方法可以降低數(shù)據(jù)存儲的冗余度，且不降低數(shù)據(jù)的可靠性.

本文的主要貢獻(xiàn)如下：

（1）設(shè)計(jì)了糾刪碼編碼前原始區(qū)塊數(shù)據(jù)劃分的方法.采用區(qū)塊區(qū)間劃分的方法對一個區(qū)塊區(qū)間內(nèi) 的區(qū)塊進(jìn)行劃分，使得進(jìn)行編碼塊存儲時，一個區(qū)塊的信息只存在于一個節(jié)點(diǎn)中;

（2）設(shè)計(jì)了無需節(jié)點(diǎn)間通信的編碼塊存儲方法.利用區(qū)塊頭部的共識節(jié)點(diǎn)公鑰地址列表全局一致 的特性，在不需要節(jié)點(diǎn)通信的情況下，每個節(jié)點(diǎn)只保留一個對應(yīng)的編碼塊，全網(wǎng)擁有所有編碼塊的完 整信息;

（3）設(shè)計(jì)了依據(jù)節(jié)點(diǎn)的加入和退出動態(tài)同步編碼的方法.通過動態(tài)同步編碼，解決節(jié)點(diǎn)加入和退 出引起的系統(tǒng)存儲消耗和容錯能力下降的問題;

（4）在開源區(qū)塊鏈系統(tǒng)CITA （https：//citahub.com/）上實(shí)現(xiàn)了以上設(shè)計(jì).

1 相關(guān)工作

糾刪碼（Erasure Code）[6-7]是一種可以在存儲系統(tǒng)和通信系統(tǒng)中實(shí)現(xiàn)高可用性和高可靠性的前向 錯誤糾正技術(shù).在網(wǎng)絡(luò)傳輸中，其主要用于丟包恢復(fù);在存儲系統(tǒng)中，其主要應(yīng)用于提高存儲的可靠 性.與多副本的冗余復(fù)制方式相比，糾刪碼技術(shù)能夠在保證數(shù)據(jù)可靠性的基礎(chǔ)上降低數(shù)據(jù)存儲的冗 余度.

CITA是一個開源的企業(yè)級聯(lián)盟區(qū)塊鏈.CITA采用BFT共識算法，當(dāng)系統(tǒng)中有1/3的節(jié)點(diǎn)作惡 的情況下，仍能正常工作.其采用全復(fù)制的冗余存儲方式，每個節(jié)點(diǎn)存儲整個區(qū)塊鏈的完整副本.CITA 對自身的共識機(jī)制和底層邏輯進(jìn)行了深度優(yōu)化.

隨著區(qū)塊鏈系統(tǒng)應(yīng)用的領(lǐng)域越來越廣泛，區(qū)塊鏈系統(tǒng)存儲帶來的存儲擴(kuò)展性差，對服務(wù)器節(jié)點(diǎn)存 儲性能要求高的問題漸漸地顯露出來，這造成了區(qū)塊鏈技術(shù)落地困難和存儲成本高的問題.國內(nèi)外針

對區(qū)塊鏈的存儲問題做了許多研究.總體而言，雖然眾多的模型各有特色，但它們都有許多不足之處， 如賈大宇等[8]的模型對數(shù)據(jù)進(jìn)行不平均存儲，導(dǎo)致系統(tǒng)的去中心化水平降低，Dai等[9]只是提出了一 個框架，并沒有形成完整的編碼方案，而Xu等[10]設(shè)計(jì)的方法不適用于交易吞吐量較高的應(yīng)用.

目前，糾刪碼在分布式系統(tǒng)中的應(yīng)用已比較成熟，但由于區(qū)塊鏈系統(tǒng)中拜占庭節(jié)點(diǎn)的存在，不能 將其移植到區(qū)塊鏈中.將糾刪碼技術(shù)應(yīng)用于區(qū)塊鏈存儲系統(tǒng)優(yōu)化的研究較少，Perard等[11]在區(qū)塊鏈系 統(tǒng)中存儲能力較弱的節(jié)點(diǎn)上使用糾刪碼，雖在一定程度上降低了區(qū)塊鏈的存儲消耗，但導(dǎo)致系統(tǒng)去中 心化水平降低.同時，其并未處理拜占庭節(jié)點(diǎn)的錯誤信息，系統(tǒng)的穩(wěn)定性較差. Qi等[12]的研究將糾刪 碼和拜占庭容錯算法相結(jié)合，不僅降低了區(qū)塊鏈系統(tǒng)的存儲消耗，更使系統(tǒng)數(shù)據(jù)可靠性得到保障，但 其編碼、查詢效率較低，在實(shí)際應(yīng)用中延遲較高.

2?????? 基于糾刪碼的區(qū)塊鏈分片存儲方法設(shè)計(jì)

2.1系統(tǒng)架構(gòu)

本系統(tǒng)是一個基于糾刪碼分片存儲的區(qū)塊鏈系統(tǒng).每個用戶通過客戶端將交易發(fā)送到系統(tǒng)，并暫 存在交易池中.每隔一段時間，交易池中的交易被打包成一個區(qū)塊，在節(jié)點(diǎn)之間對其進(jìn)行共識，然后緩 存在系統(tǒng)中，最后經(jīng)過糾刪碼編碼，分布存儲在系統(tǒng)的節(jié)點(diǎn)上.系統(tǒng)框架如圖1所示，3個主要組成部 分為：糾刪碼模塊、查詢模塊和動態(tài)重編碼模塊.

2.1.1糾刪碼模塊

糾刪碼模塊包括編碼器和解碼器兩個子模塊.區(qū)塊緩存中的區(qū)塊序列，經(jīng)過區(qū)塊區(qū)間劃分，形成 原始數(shù)據(jù)塊，通過編碼器編碼，形成糾刪碼編碼塊.每個節(jié)點(diǎn)根據(jù)自身在共識列表中的位置，存儲對應(yīng) 的編碼塊，丟棄其余塊.系統(tǒng)并不是在一個節(jié)點(diǎn)上將區(qū)塊編碼成數(shù)據(jù)塊，然后將它們分派給其他節(jié)點(diǎn)， 而是在每個節(jié)點(diǎn)上獨(dú)立編碼，無需節(jié)點(diǎn)間網(wǎng)絡(luò)通信.所有的節(jié)點(diǎn)都遵循相同的編碼規(guī)則，每個塊的可 用性得到了保證.解碼器可以通過底層網(wǎng)絡(luò)從其他節(jié)點(diǎn)獲取編碼塊，利用糾刪碼解碼對原始數(shù)據(jù)塊進(jìn) 行恢復(fù).

2.1.2 查詢模塊

查詢模塊接收來自客戶端的查詢請求，并進(jìn)行響應(yīng).當(dāng)查詢模塊處理查詢區(qū)塊B的請求時，有三

種不同的情況：

（1）如果區(qū)塊B存儲在本地，查詢模塊在沒有任何網(wǎng)絡(luò)通信的情況下將它返回客戶端;

（2）如果目標(biāo)節(jié)點(diǎn)^⑶是正確的，則查詢模塊可以從^⑶中獲取區(qū)塊B ;

（3）如果目標(biāo)節(jié)點(diǎn)M （B）是拜占庭節(jié)點(diǎn)，則查詢模塊必須通過糾刪碼模塊中的解碼器恢復(fù)區(qū)塊B . 最終，查詢模塊將驗(yàn)證來自其他節(jié)點(diǎn)的所有數(shù)據(jù)，避免通過解碼恢復(fù)不正確的塊數(shù)據(jù).

2.1.3???????? 動態(tài)重編碼模塊

當(dāng)節(jié)點(diǎn)加入或退出系統(tǒng)時，動態(tài)重編碼模塊開始工作.為了在確保數(shù)據(jù)可用性的同時減少冗余， 歷史數(shù)據(jù)可能需要被重新編碼.在進(jìn)行重編碼時，需要通過糾刪碼模塊中的解碼器，從其他節(jié)點(diǎn)獲取 數(shù)據(jù).為了減少重編碼開銷，采用動態(tài)重編碼策略，當(dāng)冗余度達(dá)到閾值時，對歷史數(shù)據(jù)進(jìn)行重新編碼. 此外，在刪除舊編碼塊之前，每個節(jié)點(diǎn)都要確保其余的塊已經(jīng)完成了重新編碼，以保證塊的可用性.

2.2區(qū)塊區(qū)間劃分方法

本文提出對區(qū)塊區(qū)間進(jìn)行劃分形成糾刪碼數(shù)據(jù)塊的方法，區(qū)塊區(qū)間是區(qū)塊鏈中一段連續(xù)的區(qū)塊 序列，將區(qū)塊區(qū)間作為糾刪碼編碼的基本單位具有兩個優(yōu)點(diǎn)：首先，在生成多個區(qū)塊后對區(qū)塊區(qū)間進(jìn) 行編碼，而非每產(chǎn)生一個區(qū)塊進(jìn)行一次編碼，可降低糾刪碼編碼開銷;其次，避免了請求區(qū)塊信息時， 向多個節(jié)點(diǎn)請求數(shù)據(jù)的問題，可降低網(wǎng)絡(luò)資源的消耗.該方法中區(qū)塊區(qū)間的大小用連續(xù)區(qū)塊的數(shù)量來 表示，如圖2所示區(qū)塊區(qū)間，其大小為10.

為了保證每個區(qū)塊或交易的查詢最多只涉及一次網(wǎng)絡(luò)通信或糾刪碼解碼，需要使每個區(qū)塊僅存 于一個糾刪碼數(shù)據(jù)塊中.同時，糾刪碼編碼算法要求輸入的&個數(shù)據(jù)塊的長度相等.所以，在對區(qū)塊區(qū) 間進(jìn)行劃分時，需保證：（1）每個區(qū)塊只能被分配到一個數(shù)據(jù)塊中;（2） —個區(qū)塊區(qū)間內(nèi)的區(qū)塊需盡可能 平均地分配到各個數(shù)據(jù)塊中.由以上兩個條件，可以將每個數(shù)據(jù)塊中區(qū)塊數(shù)量s的計(jì)算公式總結(jié)為下 式（1）：

其中n為區(qū)塊區(qū)間的大小，k為糾刪碼編碼所需的數(shù)據(jù)塊數(shù)量，n%k為n對k求余.

通過以上劃分方法得到數(shù)據(jù)塊，在長度較短的數(shù)據(jù)塊后補(bǔ)充冗余數(shù)據(jù)，使得k個數(shù)據(jù)塊的長度相 等.經(jīng)過糾刪碼編碼，生成m個糾刪碼冗余塊，與數(shù)據(jù)塊一起組成k + rn個編碼塊.

以上區(qū)塊劃分及糾刪碼編碼過程采用的算法詳見算法1.算法1的時間復(fù)雜度為O （n）.算法1通 過循環(huán)檢查新生區(qū)塊的數(shù)量判斷是否達(dá)到輸入的區(qū)間大小標(biāo)準(zhǔn)（第1行），滿足條件后根據(jù)式（1）處理 得到數(shù)據(jù)塊（第2-5行），經(jīng)過數(shù)據(jù)預(yù)處理使得數(shù)據(jù)塊達(dá)到編碼要求（第6、7行），通過編碼得到編碼塊 結(jié)果（第8、9行）.該算法實(shí)時監(jiān)測區(qū)塊數(shù)量變化，滿足條件后對一個區(qū)間中的區(qū)塊進(jìn)行編碼，不需要 每個區(qū)塊編碼一次，采用批處理的思想，可以提高編碼的效率.數(shù)據(jù)預(yù)處理階段可以通過開辟新線程， 增加系統(tǒng)并行性，進(jìn)一步提高編碼效率.

算法1區(qū)塊區(qū)間劃分編碼算法

輸入：包含^個區(qū)塊的區(qū)塊區(qū)間，數(shù)據(jù)塊數(shù)量^ ，冗余塊數(shù)量m 輸出：fc + m個編碼塊

1：????? While新生成的區(qū)塊數(shù)量大于等于n

2：????? If n%k == 0

3：????? 將n個區(qū)塊平均分配到個數(shù)據(jù)塊中

4：????? Else

5：????? 前n%fc個數(shù)據(jù)塊每個存n/fc+ 1個區(qū)塊，其他每個數(shù)據(jù)塊存n/fc個區(qū)塊

6：????? End if

7：????? 獲得長度最長的數(shù)據(jù)塊長度maxl

8：????? 在其余數(shù)據(jù)塊后補(bǔ)“ 0”，使數(shù)據(jù)塊長度達(dá)到一致maxl

9：????? 將fc個數(shù)據(jù)塊作為糾刪碼的輸人進(jìn)行編碼

10：?? 得到fc + m個編碼塊

11：?? End while

采用以上算法，當(dāng)區(qū)塊區(qū)間大小n = 10 ，數(shù)據(jù)塊數(shù)量fc = 3 ，冗余塊數(shù)量m = 1時，區(qū)塊劃分及糾 刪碼編碼結(jié)果如圖3所示.

2.3無需網(wǎng)絡(luò)通信的編碼塊存儲方法

為降低系統(tǒng)的冗余度，經(jīng)過糾刪碼編碼后，每個節(jié)點(diǎn)僅保存一個編碼塊，可將其他編碼塊刪除.這 需要與其他節(jié)點(diǎn)達(dá)成共識，才能保證每個節(jié)點(diǎn)保存的區(qū)塊不同，同時保證系統(tǒng)中保存著所有的編碼塊 信息.然而，區(qū)塊鏈系統(tǒng)運(yùn)行在一個不可靠的環(huán)境中，網(wǎng)絡(luò)通信會增加系統(tǒng)的不穩(wěn)定性，還會導(dǎo)致系統(tǒng) 的吞吐率降低.為了解決上述問題，本文利用每個節(jié)點(diǎn)上相同區(qū)塊的共識節(jié)點(diǎn)公鑰列表具有一致性的 特性，設(shè)計(jì)了一種無需網(wǎng)絡(luò)通信的編碼塊存儲方法.如圖4所示，對原始數(shù)據(jù)進(jìn)行劃分并編碼之后，根 據(jù)本節(jié)點(diǎn)公鑰地址在所有節(jié)點(diǎn)公鑰地址序列中的位置，保存對應(yīng)于本節(jié)點(diǎn)的編碼塊，并刪除其余編碼 塊.由于公鑰地址有序序列在所有節(jié)點(diǎn)上都是一致的，所以節(jié)點(diǎn)間不需要網(wǎng)絡(luò)通信就可以僅保存自己 所對應(yīng)的編碼塊，同時保證系統(tǒng)中包含所有編碼塊的信息.

CITA采用鍵值數(shù)據(jù)庫存儲數(shù)據(jù)，在存儲編碼塊時，為能夠在請求區(qū)塊時從數(shù)據(jù)庫中查詢到其所 在的編碼塊，需增加一個表來存儲區(qū)塊高度與編碼塊編號的映射關(guān)系.該方式會增大系統(tǒng)的存儲消耗， 并增加查詢的響應(yīng)延遲.為了在查詢時快速利用區(qū)塊高度得到其所在的編碼塊，本文根據(jù)計(jì)算每個數(shù) 據(jù)塊中區(qū)塊數(shù)量的式（1），對編碼塊的編號進(jìn)行定義.將編碼塊編號以文本形式表示，它由兩部分組 成，第一部分標(biāo)識該編碼塊所處的區(qū)塊區(qū)間&第二部分標(biāo)識該編碼塊處于該區(qū)塊區(qū)間的第D個數(shù)據(jù) 塊，兩部分用下劃線連接，表示為^_乃.如圖4所示，高度為4的區(qū)塊位于區(qū)塊0?9所對應(yīng)的區(qū)塊區(qū) 間，其區(qū)塊區(qū)間^ = 0，又因其在該區(qū)間的第D = 1個數(shù)據(jù)塊，故高度為4的區(qū)塊所對應(yīng)的編碼塊編號 為 0—1.0_2 0_3

當(dāng)用戶向系統(tǒng)查詢區(qū)塊時，可以通過區(qū)塊高度計(jì)算得到其所處的區(qū)塊區(qū)間和數(shù)據(jù)塊號，進(jìn)而得到 其所對應(yīng)編碼塊的編號.由區(qū)塊高度計(jì)算編碼塊編號的算法詳見算法2.算法2的時間復(fù)雜度為O （1）.

算法2編碼塊編號計(jì)算算法

輸入：區(qū)塊高度＼區(qū)塊區(qū)間大小^，數(shù)據(jù)塊個數(shù)&，冗余塊個數(shù)爪 輸出：編碼塊編號S_D

1：????? S = h/n

2：????? If n%k == 0

3：????? D = （h°%n） /（n/k）

4：????? Else if h°%n < （n/k +（1） * （n%k）

5：????? D = （h%n） /（n/k + （1）

6：????? Else

7：????? D = n%k + （h%n — （n/k + 1 ）*（ n%k）） /（n/k）

8：????? End if

9：????? Return S_D

假設(shè)系統(tǒng)對前10個區(qū)塊的編碼結(jié)果如圖5所示，節(jié)點(diǎn)0接收到客戶端對于區(qū)塊3的請求，即區(qū)塊 高度為3，由上述計(jì)算方法，得到S = 0（3/10 = 0），D = 0（3%10）/4 = 0），即S_D = 0_0.節(jié)點(diǎn)0讀取 共識節(jié)點(diǎn)公鑰地址有序序列，比對本地公鑰地址在有序序列中的位置，若節(jié)點(diǎn)0上不存儲0_0編碼塊， 則向公鑰地址有序序列中的第D個節(jié)點(diǎn)（節(jié)點(diǎn)（3）發(fā)出對編碼塊0_0的請求.節(jié)點(diǎn)0將從節(jié)點(diǎn)3得到的 區(qū)塊數(shù)據(jù)返回給客戶端.

2.4動態(tài)重編碼方法

區(qū)塊鏈?zhǔn)且环N分布式賬本，賬本數(shù)據(jù)的一致性依賴多個節(jié)點(diǎn)的共同維護(hù).新機(jī)構(gòu)加入時，需為其 搭建一個新的節(jié)點(diǎn)，并將其加入?yún)^(qū)塊鏈系統(tǒng);原有機(jī)構(gòu)退出時，需將該節(jié)點(diǎn)從系統(tǒng)中刪除.為了應(yīng)對區(qū) 塊鏈系統(tǒng)中節(jié)點(diǎn)加入或退出造成的重編碼時間消耗過大的問題，本文提出了動態(tài)重編碼的方法.

CITA區(qū)塊鏈系統(tǒng)中存在不參與區(qū)塊共識的普通節(jié)點(diǎn).普通節(jié)點(diǎn)的加入或退出不會影響區(qū)塊的共 識進(jìn)程.普通節(jié)點(diǎn)加入后只需要提供查詢功能即可，不需要保存編碼塊.為了在不保存編碼塊的情況 下保證普通節(jié)點(diǎn)的查詢功能，普通節(jié)點(diǎn)需要同步共識節(jié)點(diǎn)的編碼塊索引.當(dāng)用戶向普通節(jié)點(diǎn)發(fā)起查詢 請求時，普通節(jié)點(diǎn)根據(jù)從共識節(jié)點(diǎn)處同步的索引，向?qū)?yīng)的共識節(jié)點(diǎn)發(fā)起請求，實(shí)現(xiàn)查詢功能.

共識節(jié)點(diǎn)的加入與區(qū)塊的共識同步進(jìn)行，如圖6所示.在生成一個區(qū)塊區(qū)間時，新的共識節(jié)點(diǎn)加 入會導(dǎo)致共識節(jié)點(diǎn)列表的變化，該區(qū)塊區(qū)間的前6個區(qū)塊的共識節(jié)點(diǎn)為{N0， N1， N2， N3}，而后4個區(qū) 塊的共識節(jié)點(diǎn)為{N0， N1， N2， N3， N4}.這導(dǎo)致對該區(qū)塊區(qū)間中的區(qū)塊進(jìn)行糾刪碼編碼后，存儲編碼塊的共識節(jié)點(diǎn)列表可以是{N0， N1， N2， N3}，也可以是{N0， N1， N2， N3， N4}.為了統(tǒng)一存儲該區(qū)塊區(qū)間的共識節(jié)點(diǎn)列表，對區(qū)塊區(qū)間共識節(jié)點(diǎn)列表做如下定義：區(qū)塊區(qū)間最后一個區(qū)塊的共識節(jié)點(diǎn)列表為此 區(qū)塊區(qū)間的共識節(jié)點(diǎn)列表.由此可得存儲10?19區(qū)塊區(qū)間編碼塊的共識節(jié)點(diǎn)列表為{N0， N1， N2， N3， N4}.

共識節(jié)點(diǎn)加入后，系統(tǒng)中共識節(jié)點(diǎn)的數(shù)量會發(fā)生變化.CITA區(qū)塊鏈系統(tǒng)保證系統(tǒng)中共識節(jié)點(diǎn)數(shù) #和拜占庭節(jié)點(diǎn)數(shù)P的數(shù)量關(guān)系為：N>3F+ 1，即（N-（1）/3.當(dāng)系統(tǒng)中共識節(jié)點(diǎn)數(shù)量變?yōu)?N + 1時，系統(tǒng)所能容忍的拜占庭節(jié)點(diǎn)的數(shù)量變?yōu)镕'，F(xiàn)'滿足F'>F.若保持原來的編碼參數(shù)不變， 系統(tǒng)只能在F個節(jié)點(diǎn)作惡時恢復(fù)丟失的數(shù)據(jù).此時若系統(tǒng)中有F'個節(jié)點(diǎn)作惡，且F' > F，則不能保證 可以通過糾刪碼解碼將原始數(shù)據(jù)恢復(fù)出來，從而不能保證系統(tǒng)的數(shù)據(jù)可用性.共識節(jié)點(diǎn)從系統(tǒng)中退出 時也面臨相同的情況.為了解決上述問題，需要在新的共識節(jié)點(diǎn)加入時，對歷史數(shù)據(jù)進(jìn)行重新編碼.

本文提出了動態(tài)糾刪碼重編碼算法，即在保證系統(tǒng)中所有區(qū)塊可恢復(fù)的情況下，不在節(jié)點(diǎn)加入或 退出時立刻對歷史數(shù)據(jù)進(jìn)行重新編碼，而是根據(jù)節(jié)點(diǎn)加入或退出后，系統(tǒng)所容忍拜占庭節(jié)點(diǎn)數(shù)量是否 增多或減少，來動態(tài)地對歷史數(shù)據(jù)進(jìn)行重新編碼.采用此方法可以降低重編碼帶來的系統(tǒng)開銷，提高 系統(tǒng)的效率.動態(tài)重編碼算法詳見算法3.算法3的時間復(fù)雜度為0（1）.算法3的第4-7行和第 9-12行分別對節(jié)點(diǎn)增加和刪除的情況進(jìn)行處理，由公式F=「（N-（1）/3]可得拜占庭節(jié)點(diǎn)數(shù)量，如果 節(jié)點(diǎn)數(shù)量的增加沒有使拜占庭節(jié)點(diǎn)數(shù)量發(fā)生變化，或節(jié)點(diǎn)數(shù)量的減少恰好可以使拜占庭節(jié)點(diǎn)數(shù)量減 少相同的個數(shù)，則原來的編碼模式可以保證系統(tǒng)的穩(wěn)定性.由于并不是每次節(jié)點(diǎn)增刪都會導(dǎo)致拜占庭 節(jié)點(diǎn)數(shù)量的變化，采用動態(tài)重編碼的方法可以減少重編碼的開銷.

算法3動態(tài)重編碼算法

輸入：歷史共識節(jié)點(diǎn)數(shù)量I ，新共識節(jié)點(diǎn)數(shù)量新區(qū)塊區(qū)間，歷史編碼塊數(shù)據(jù) 輸出：編碼結(jié)果

1：????? F'=「（，—（1）/3LF=「（N — （1）/3]

2：對新的區(qū)塊區(qū)間，采用^共識節(jié)點(diǎn)列表進(jìn)行糾刪碼編碼 3：? If N; >N

4：????? If F' == F

5：????? 新節(jié)點(diǎn)保存歷史編碼塊索引

6：????? Else

7：????? 采用N'共識節(jié)點(diǎn)列表，對歷史編碼塊數(shù)據(jù)進(jìn)行重編碼

8：????? End? if

9：????? Else if??????? N?????

10：?? If F' =???????? F — 1

11：?? 不處理歷史數(shù)據(jù)

12：?? Else

13：?? 采用N'共識節(jié)點(diǎn)列表，對歷史編碼塊數(shù)據(jù)進(jìn)行重編碼

14：?? End if

15：?? End if

16：保存編碼結(jié)果

3實(shí)驗(yàn)與評價

3.1實(shí)驗(yàn)環(huán)境和配置

（1）實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)在以下實(shí)驗(yàn)環(huán)境中進(jìn)行，其中操作系統(tǒng)為Ubuntu18.04，配置AMD Ryzen 5 3550H （4核8線程，主頻2.1 GHz，加速頻率3.7 GHz）處理器，內(nèi)存大小為16 GB，硬盤大小為512 G.本文 設(shè)計(jì)的算法使用Rust程序設(shè)計(jì)語言在0.25.2版本的CITA上實(shí)現(xiàn).

（2）參數(shù)配置

實(shí)驗(yàn)測試的節(jié)點(diǎn)數(shù)量為4，糾刪碼編碼的數(shù)據(jù)塊數(shù)量為3，冗余塊數(shù)量為1.

3.2實(shí)驗(yàn)結(jié)果與分析

本文的實(shí)驗(yàn)評價主要參考4個指標(biāo)：存儲消耗、編碼性能、響應(yīng)延遲和穩(wěn)定性.

3.2.1存儲消耗

存儲消耗的評估分為兩部分，首先，為了證明糾刪碼編碼的存儲方式能降低系統(tǒng)的存儲消耗，將 糾刪碼編碼存儲與全復(fù)制存儲相比，評價糾刪碼編碼存儲在空間占用方面的優(yōu)化效果，其中全復(fù)制的 存儲系統(tǒng)中存儲消耗與節(jié)點(diǎn)數(shù)成正比;其次，調(diào)整編碼區(qū)間的大小，評估糾刪碼編碼區(qū)塊區(qū)間大小對 每個區(qū)塊存儲消耗的影響，由此結(jié)論可根據(jù)需求調(diào)整區(qū)塊區(qū)間的大小，降低存儲消耗.

（1）全復(fù)制的存儲方式與糾刪碼的存儲方式的存儲消耗對比

區(qū)塊區(qū)間的大小固定為10，區(qū)塊大小固定為80 kB，節(jié)點(diǎn)數(shù)量從4到15變化.如圖7所示，展示了 在不同節(jié)點(diǎn)設(shè)置下存儲每個塊的平均存儲消耗.對于全復(fù)制的存儲方式（all），由于每個節(jié)點(diǎn)都需要保存區(qū)塊鏈的完整副本，每個區(qū)塊的平均存儲容量隨著節(jié)點(diǎn)數(shù)量的增加而線性增加.對于糾刪碼的存儲 方式（ec），隨著節(jié)點(diǎn)的增加，每個區(qū)塊的平均存儲容量產(chǎn)生輕微的波動，且總是小于所有區(qū)塊大小的 2倍.全復(fù)制存儲每個區(qū)塊的存儲消耗與糾刪碼存儲每個區(qū)塊的存儲消耗的比值（%）隨著節(jié)點(diǎn)的數(shù)量 增加而線性增加.

由以上實(shí)驗(yàn)分析得出，隨著節(jié)點(diǎn)數(shù)量的增加，糾刪碼存儲方式與全復(fù)制方式相比表現(xiàn)出更加明顯 的存儲性能優(yōu)勢，糾刪碼的存儲方式在有多個節(jié)點(diǎn)的區(qū)塊鏈系統(tǒng)中具有更高的應(yīng)用價值.同時，采用 糾刪碼的存儲方式，系統(tǒng)的存儲壓力不會因?yàn)楣?jié)點(diǎn)數(shù)量的變化而發(fā)生大幅度的變化，無須因?yàn)楣?jié)點(diǎn)的 增加調(diào)整系統(tǒng)存儲配置，降低了系統(tǒng)維護(hù)工作量.

（2）糾刪碼編碼區(qū)塊區(qū)間大小對每個區(qū)塊存儲消耗的影響

糾刪碼區(qū)塊區(qū)間的大小會在一定程度上影響每個區(qū)塊的平均存儲容量，固定系統(tǒng)中的節(jié)點(diǎn)數(shù)為4， 固定區(qū)塊的大小為80 kB，區(qū)塊區(qū)間在10?21間變化.圖8所顯示的是每個區(qū)塊的平均存儲消耗與 區(qū)塊區(qū)間大小的關(guān)系.

如圖8實(shí)線所示，每個區(qū)塊的存儲消耗會隨區(qū)塊區(qū)間的變化產(chǎn)生周期性波動，這與本文設(shè)計(jì)的數(shù) 據(jù)塊劃分策略有關(guān).當(dāng)區(qū)塊區(qū)間大小s= 10時，數(shù)據(jù)塊的劃分模式為（4，3，（3），其中4個區(qū)塊形成一個 編碼塊，剩余的6個區(qū)塊，每3個生成一個編碼塊，最終在較短的編碼塊后補(bǔ)0，然后進(jìn)行糾刪碼編碼 運(yùn)算，得到冗余塊的大小應(yīng)約等于4個區(qū)塊形成的編碼塊的大小，最終編碼塊的模式可表示為 （4， 3， 3， （4）.每個區(qū)塊的平均存儲消耗為（4 +3+ 3 +（4）/10 = 1.4 .同理可以得到其他區(qū)塊區(qū)間大小所對 應(yīng)的每個區(qū)塊的存儲消耗.在一個區(qū)塊區(qū)間變化周期中，當(dāng)編碼塊的模式為沁，，，…，O0時（a為每個 糾刪碼編碼塊中區(qū)塊數(shù)量的近似值），每個區(qū)塊的平均存儲消耗最低;當(dāng)編碼塊的模式為（a+1，a， a，…，a + （1）時，每個區(qū)塊的平均存儲消耗最高.

如圖8趨勢線所示，在保持節(jié)點(diǎn)數(shù)量為4不變的情況下，雖然隨著區(qū)塊區(qū)間的增大，每個區(qū)塊的 平均存儲消耗總體呈下降的趨勢，但實(shí)線所示折線具有周期性，適當(dāng)調(diào)整區(qū)塊區(qū)間大小可使糾刪碼的存儲方式的優(yōu)勢達(dá)到最大值，并不需要盲目增大區(qū)塊區(qū)間來提高存儲效率.

3.2.2編碼性能

全復(fù)制的存儲系統(tǒng)存儲一個區(qū)塊的延遲約為2 ms，糾刪碼存儲的編碼操作會造成編碼延遲，本小 節(jié)首先對編碼延遲做了測試.其次，對于降低編碼延遲的區(qū)塊區(qū)間劃分編碼算法，對比區(qū)塊區(qū)間劃分 與單個區(qū)塊劃分編碼方法所需編碼時間，評估其優(yōu)化效果.最后，綜合評價區(qū)塊區(qū)間劃分編碼算法中 的參數(shù)區(qū)塊區(qū)間大小對整體編碼延遲的影響和對單個區(qū)塊編碼延遲的影響.在實(shí)際應(yīng)用中可通過調(diào) 整區(qū)塊區(qū)間大小，降低編碼延遲.

（1）編碼延遲

在進(jìn)行區(qū)塊存儲時，與全復(fù)制的存儲方式相比，糾刪碼的存儲方式需要時間進(jìn)行糾刪碼的編碼. CITA系統(tǒng)中，保存一個區(qū)塊需要約2 ms，當(dāng)糾刪碼區(qū)塊區(qū)間為12時，一次糾刪碼編碼需要約20 ms， 平均到每個區(qū)塊上為1.6 ms.由以上數(shù)據(jù)，可以總結(jié)得出，使用基于糾刪碼的存儲方式，在存儲時消耗 的時間約為全復(fù)制存儲方式的1.8倍.相對于糾刪碼編碼存儲方式帶來的從O （n）到O （1）的存儲空間 優(yōu)化而言，糾刪碼編碼造成的時間開銷是可以接受的.

（2）區(qū)塊區(qū)間劃分與單個區(qū)塊劃分編碼方法所需編碼時間對比

確定區(qū)塊大小為80 kB，節(jié)點(diǎn)數(shù)量為4，區(qū)塊區(qū)間的大小為12?30，對比使用兩種方法編碼一個 區(qū)塊區(qū)間內(nèi)的區(qū)塊所消耗的時間.實(shí)驗(yàn)結(jié)果如圖9所示，采用區(qū)塊區(qū)間劃分的方法進(jìn)行編碼能夠節(jié)省 編碼的時間，且隨著區(qū)塊區(qū)間的增大，采用區(qū)塊區(qū)間編碼的優(yōu)勢也隨之增大，在區(qū)塊區(qū)間大小為30時， 采用區(qū)塊區(qū)間編碼的方法節(jié)省了近45%的編碼時間.獲得編碼性能提升的主要原因?yàn)閰^(qū)塊區(qū)間劃分 的方法采用了批處理思想，減小了每次編碼預(yù)處理及編碼器啟動時間在總編碼時間中的占比.

（3）區(qū)塊區(qū)間大小對編碼延遲的影響

如圖10所示，隨著區(qū)塊區(qū)間的增大，每個區(qū)間的編碼時間也隨之增大.

但將該區(qū)間的編碼時間平均到區(qū)塊區(qū)間內(nèi)的每個區(qū)塊上，得到每個區(qū)塊的平均編碼時間與區(qū)塊區(qū)間大小關(guān)系如圖ii所示，隨著區(qū)塊區(qū)間的增大，區(qū)塊的平均編碼時間呈下降趨勢.增大區(qū)塊區(qū)間的 大小，可以降低每個區(qū)塊的平均編碼時間，但區(qū)塊區(qū)間的增大會使得一次編碼的時間增長，在具體使 用過程中，可以根據(jù)需求調(diào)整糾刪碼編碼區(qū)塊區(qū)間大小.

3.2.3響應(yīng)延遲

在采用糾刪碼存儲方式的系統(tǒng)中，每個節(jié)點(diǎn)上只保存部分區(qū)塊的信息，當(dāng)所需區(qū)塊不存在所請求 的節(jié)點(diǎn)上或系統(tǒng)中的節(jié)點(diǎn)發(fā)生故障時，需要利用網(wǎng)絡(luò)傳輸和糾刪碼的解碼功能將原始數(shù)據(jù)恢復(fù)出來， 數(shù)據(jù)的恢復(fù)操作會造成響應(yīng)延遲.采用全復(fù)制存儲方式的CITA系統(tǒng)，由于沒有節(jié)點(diǎn)間通信，用戶查 詢請求的響應(yīng)延遲約為1.35 ms.

采用糾刪碼存儲方式后，查詢存在本地節(jié)點(diǎn)的區(qū)塊，響應(yīng)延遲約為9.5 ms，查詢存在其他節(jié)點(diǎn)的區(qū)塊，響應(yīng)延遲約為44.05 ms.雖然與全復(fù)制的存儲方式相比，由于區(qū)塊數(shù)據(jù)的提取和節(jié)點(diǎn)間的通信， 響應(yīng)延遲有所增加，但44 ms的延遲時間不會影響用戶的使用體驗(yàn).若不采用算法1而是采用對每個 區(qū)塊進(jìn)行編碼存儲的方法，則向某個節(jié)點(diǎn)請求一個區(qū)塊得到響應(yīng)所需的時間約為70 ms，約為采用算 法1響應(yīng)延遲的7倍.

若查詢時發(fā)現(xiàn)某編碼塊丟失，采用糾刪碼解碼方式恢復(fù)數(shù)據(jù)，再返回給用戶，響應(yīng)延遲約為238 ms. 用戶會感受到輕微的卡頓，但如果系統(tǒng)運(yùn)行在一個較可靠的環(huán)境中，節(jié)點(diǎn)發(fā)生故障的概率將大大降低， 從而很少需要進(jìn)行解碼恢復(fù)，不會影響用戶的使用體驗(yàn).

3.2.4穩(wěn)定性

系統(tǒng)的穩(wěn)定性體現(xiàn)了系統(tǒng)應(yīng)對外界干擾和故障的能力，采用全復(fù)制存儲方式的系統(tǒng)能夠容忍小 于等于?的拜占庭節(jié)點(diǎn)數(shù).采用糾刪碼存儲方式的系統(tǒng)穩(wěn)定性以功能測試的形式，通過模擬系統(tǒng)故 障情況進(jìn)行.首先，從系統(tǒng)外部將存儲的數(shù)據(jù)塊從數(shù)據(jù)庫中刪除，模擬數(shù)據(jù)丟失的情況.其次，通過命 令行指令強(qiáng)制節(jié)點(diǎn)掉線，模擬系統(tǒng)中的拜占庭節(jié)點(diǎn).在以上兩組模擬功能測試中，糾刪碼的解碼恢復(fù) 功能都能正常運(yùn)行，系統(tǒng)能夠在發(fā)生故障時，通過糾刪碼解碼恢復(fù)功能給出準(zhǔn)確的查詢結(jié)果，系統(tǒng)能 夠容忍小于等于^的拜占庭節(jié)點(diǎn)數(shù)，沒有因糾刪碼的加入降低系統(tǒng)的穩(wěn)定性.

4結(jié)論

本文將糾刪碼與拜占庭容錯算法相結(jié)合，在滿足系統(tǒng)容錯率的基礎(chǔ)上，降低了區(qū)塊存儲的冗余度. 本文提出了原始區(qū)塊數(shù)據(jù)劃分的方法，提高了區(qū)塊查詢的速度，提出了無需節(jié)點(diǎn)間通信的存儲編碼塊 方法，減少了節(jié)點(diǎn)間的通信開銷.提出了根據(jù)節(jié)點(diǎn)的加入和刪除動態(tài)同步編碼的方法，降低了歷史數(shù) 據(jù)重編碼的系統(tǒng)消耗.最后，通過實(shí)驗(yàn)測試，驗(yàn)證了系統(tǒng)的可用性和效率提升.

本文的方法將系統(tǒng)的存儲空間復(fù)雜度由O（n）降低到O（1），但不可避免因糾刪碼編碼解碼造成的 時間消耗，在后續(xù)的工作中將重視糾刪碼的編碼和解碼效率的優(yōu)化.

[參考文獻(xiàn)]

[1]CASTRO M， LISKOV B. Practical byzantine fault tolerance [C]//Proceedings of the Third Symposium on Operating Systems Design and Implementation. 1999： 173-186.

[2]WOOD G. Ethereum： A secure decentralised generalised transaction ledger [J]. Ethereum Project Yellow Paper， 2014， 151： 1-32.

[3] BURCHERT C， DECHER C， WATTENHOFER R. Scalable funding of bitcoin micropayment channel networks [J]. Royal Society Open Science， 2018， 5（8）： 180089.

[4]DANG H， DINH T T A， LOGHIN D， et al. Towards scaling blockchain systems via sharding [C]// Proceedings of the 2019 International Conference on Management of Data. 2019： 123-140.

[5] AL-BASSAM M， SONNINO A， BANO S， et al. Chainspace： A sharded smart contracts platform [EB/OL]. （2017-08-1（2） [2021-07-05]. http：//arXiv.org/pdf/1708.03778.pdf.

[6] REED I S， SOLOMON G. Polynomial codes over certain finite fields [J]. Journal of the Society for Industrial & Applied Mathematics， 1960， 8（2）： 300-304.

[7]LIN W K， CHIU D M， LEE Y B. Erasure code replication revisited [C]//Proceedings of the Fourth International Conference on Peer- to-Peer Computing. IEEE， 2004： 90-97.

[8]賈大宇，信俊昌，王之瓊，等.區(qū)塊鍵的存儲容量可擴(kuò)展模型[J].計(jì)算機(jī)科學(xué)與探索，2018， 12（4）： 525-535.

[9] DAI M， ZHANG S， WANG H， et al. A Low Storage Room Requirement Framework for Distributed Ledger in Blockchain [J]. IEEE Access， 2018（6）： 22970-22975.

[10]XU Y， HUANG Y. Segment blockchain： A size reduced storage mechanism for blockchain. IEEE Access， 2020（8）： 17434-17441.

[11]PERARD D， LACAN J， BACHY Y， et al. Erasure code-based low storage blockchain node [C]//2018 IEEE International Conference on Internet of Things and IEEE Green Computing and Communications and IEEE Cyber， Physical and Social Computing and IEEE Smart Data. IEEE， 2018： 1622-1627.

[12]QI X， ZHANG Z， JIN C， et al. BFT-Store： Storage partition for permissioned blockchain via erasure coding [C]// 2020 IEEE 36th International Conference on Data Engineering. IEEE， 2020： 1926-1929.

（責(zé)任編輯：林晶）