基于中國剩余定理的區塊鏈存儲擴展模型

卿欣藝，陳玉玲*，周正強，涂園超，李 濤

（1.貴州大學計算機科學與技術學院，貴州 550025；2.省部共建公共大數據國家重點實驗室（籌）（貴州大學），貴州 550025）

0 引言

自《比特幣：一種點對點電子現金系統》［1］發表以來，比特幣的底層技術區塊鏈被認為是下一代的顛覆性技術。區塊鏈是一種去中心化、由多方共同維護的分布式賬本技術，它基于P2P（Peer-to-Peer）網絡［2］，要求每個節點都需持有該賬本的數據副本并同步更新。區塊鏈中，數據的寫入由節點之間的分布式共識算法來完成，如工作量證明（Proof-of-Work，POW）［3］等，數據以塊的方式進行存儲，并按照時間順序構成鏈式結構。此外，還采用密碼學技術來保證分布式賬本防篡改、可溯源。

區塊鏈由于其去中心化、防篡改和可以溯源等特點，引起了金融機構、投資機構、監管部門以及政府部門的廣泛關注。但目前區塊鏈仍存在較多技術難點，存儲問題就是其中之一。區塊鏈網絡中，節點以哈希鏈的形式存儲完整的數據副本，而由于其鏈式結構的特殊性只能對區塊進行增加和查詢。對節點而言，即使沒有參與交易，也必須存儲該筆交易數據，這極大增加了節點存儲成本。以比特幣為例：比特幣每秒平均交易不到3.5 筆［4］，即使按照這個速度，節點平均每天也需要消耗近160 MB 的存儲空間，大約60 GB/a。截至2020 年7 月15日，比特幣一共產生了639 487 個區塊，平均區塊大小為1.28 MB，整個區塊鏈大小約為287.9 GB，有效地址總數約3 000 萬［5］。為了達到最高的安全性和信任度，節點需要浪費將近300 GB 的存儲空間來記錄大量無關的交易數據，而整個區塊鏈系統需要使用近9 000 PB 的空間來存儲300 GB 的有效數據，而且隨著區塊和節點數量不斷增加，存儲消耗將持續增加，因此解決區塊鏈的存儲問題日漸緊迫。

針對這一問題，許多學者進行了大量研究。文獻［1］提出SPV（Simplified Payment Verification）協議，輕量級節點（運行SPV 的節點）只存儲區塊頭，本身無法驗證交易。故輕量級節點執行支付驗證全部依賴于全節點（存儲全部區塊數據），導致區塊鏈的去中心化減弱、安全性和穩定性降低。Franca等［6］針對比特幣網絡提出迷你區塊鏈，節點只存儲區塊頭和最新的區塊，并使用賬戶樹來保障用戶余額，這極大地降低了節點的存儲壓力，但會導致交易數據的丟失。Xu 等［7］針對傳感器以及智能手機等移動設備的存儲能力缺乏問題提出了EPBC（Efficient Public Blockchain Client），節點存儲區塊鏈摘要來驗證數據的正確性，但不能解決數據中心化的問題。Jia等［8］提出存儲容量可擴展性模型，根據每個區塊安全性高低來決定其存儲副本的數量，節點按照功能劃分，不再要求每個節點存儲完整的區塊鏈信息；但該模型使用了兩條輔助鏈，增加了系統的復雜性。文獻［9-10］在文獻［6］研究的基礎上引入余數系統（Residual Number System，RNS）與冗余余數系統（Redundant Residual Number System，RRNS）將賬戶樹分片來減小節點的存儲壓力并保障數據的完整性，但仍然無法解決交易數據丟失的問題。文獻［11-14］中分別使用哈希一致性算法、糾刪碼、改進的Shamir秘密共享技術［15］和建立路由表來減小節點的存儲壓力。

本文在現有研究的基礎上提出了一種基于中國剩余定理（Chinese Remainder Theorem，CRT）的區塊鏈存儲擴展模型。在該模型中，根據基于CRT 的分割算法將高安全性區塊的區塊體進行分片，每個節點存儲一份數據碎片來減少存儲消耗，多個節點（共識單元［16］）共同保存一份高安全性區塊的數據副本，而全網節點都需要存儲一份低安全性區塊數據副本；此外，還加入了RRNS 錯誤檢測與糾正來提高數據的穩定性和完整性。

本文主要的工作如下：

1）提出基于CRT 的區塊鏈存儲擴展模型，模型中節點采用不同的策略存儲安全性不同的區塊，節點存儲一部分區塊鏈數據來降低存儲消耗。該模型解決了節點因存儲能力不足而變為輕量級節點，導致全節點網絡帶寬壓力增大以及區塊鏈系統去中心化減弱的問題。

2）在確保區塊數據安全性和可用性的前提下，提出了一種基于CRT 的分割算法來對區塊數據進行分片，并將分片后的區塊碎片以分布式的方式進行存儲。此外，利用RRNS 的錯誤檢測和校正［17］來恢復區塊數據，使部分節點相互通信就可以恢復區塊數據，提高了數據穩定性和模型的容錯性。

3）對模型進行安全性分析以及仿真實驗，結果表明本文提出的基于CRT 的區塊鏈存儲擴展模型在降低節點存儲壓力的同時，具有良好的容錯性和安全性。

1 相關知識

1.1 中國剩余定理

m1，m2，…，mk是兩兩互素的正整數，組成模數集合β={m1，m2，…，mk}，M=當X＜M，則X能被唯一的φ={a1，a2，…，ak}表示，其中X≡ai(modmi)(i=1，2，…，k)。當β和φ可知時，就能夠恢復X，X可表示為：

1.2 冗余余數系統

使用CRT 進行數據恢復時，若有惡意節點提供錯誤信息，將無法還原正確數據。因此，引入RRNS 的錯誤檢測與糾正來提升數據穩定性和保障數據完整性。

假設余數集合φ={a1，a2，…，ak，ak+1，…，ak+s}由原始數據X對新模數集合β={m1，m2，…，mk，mk+1，…，mk+s}中的模數取余得到，并且φ={a1，a2，…，ak，ak+1，…，ak+s}中存在被惡意篡改的余數項。

圖1 RRNS的錯誤檢測與糾正流程Fig.1 Flowchart of RRNS error detection and correction

1.3 共識單元

共識單元由多個節點組成，多個節點共同存儲一份區塊鏈數據副本。共識單元可以看作一個存儲能力較強的節點，通過整合多個節點的存儲能力來存儲全部區塊數據，共識單元基本框架如圖2 所示。由圖2 可知，共識單元中的節點為N1～N6，每個節點的存儲空間各不相同。假設在一個區塊鏈的應用場景中，區塊鏈的總數據量為100 GB，N1～N6 都不能獨自存儲全部區塊鏈數據，但可以分別存儲區塊鏈的部分數據來共同存儲一份完整的區塊鏈數據副本。節點可以向共識單元中的其他節點發送請求來獲得完整的區塊鏈數據，以達到全節點的效果。

圖2 共識單元基本框架Fig.2 Basic framework of consensus unit

2 基于CRT的區塊鏈存儲擴展模型

本文利用分布式存儲方法［19-20］和分片思想來提出一個基于CRT 的區塊鏈存儲擴展模型，其核心思想是在保證區塊數據的安全性與可靠性的前提下，將區塊數據分片，分布式存儲分片后的區塊數據，模型框架如圖3 所示。該模型中包含多個共識單元，共識單元由多個節點組成。模型通過對區塊的安全性進行判定，將區塊鏈分為高安全性和低安全性區塊，區塊鏈網絡中的節點直接存儲低安全性區塊，而對于高安全性的區塊，區塊鏈網絡中的節點利用基于CRT 的分割算法進行分片，節點只需要存儲區塊碎片。此外，節點可以向同一共識單元的節點發送請求獲取區塊碎片以還原區塊數據。

圖3 基于CRT的區塊鏈存儲擴展模型Fig.3 Blockchain storage expansion model based on CRT

在現有的區塊鏈模型中，想要篡改區塊數據，需要控制區塊鏈網絡中半數以上的節點。在本模型中，共識單元存儲一份完整的區塊鏈數據，將會導致區塊鏈副本數量減少，而攻擊者掌握少于區塊鏈網絡中半數的節點，就有可能篡改區塊數據。同時，為提高區塊數據的穩定性和模型的安全性，本文模型添加了RRNS 的錯誤檢測與糾正，使共識單元中的少量節點相互通信就能正確恢復區塊數據，節點的數量與信息模數基相關。模型為不同的共識單元設置不同的模數集合β={m1，m2，…，mk，mk+1，…mk+s}，節點可根據自身存儲能力和網絡帶寬來選擇共識單元，加入共識單元并隨機選擇一個模數，其中{m1，m2，…，mk}為信息模數基，{mk+1，…，mk+s}為冗余檢錯基。若所有的節點同屬一個共識單元，很難設定信息模數基的長度k，k值若太大，會增加某些節點的帶寬壓力；而太小的話，會增加某些節點的存儲壓力。因此，本模型設置多個共識單元，來提升系統的負載均衡。

2.1 區塊安全性判定

共識機制中最早出現的是POW。在POW 中，率先計算出滿足規則的隨機數的節點獲得記賬權，計算出滿足規則的隨機數的概率與節點算力成正比，若攻擊者獲得全網一半以上的算力，就能控制整個區塊鏈系統。51%攻擊通過區塊鏈分叉來實現區塊數據的篡改，攻擊者產生一條攻擊鏈來代替區塊鏈，要使區塊數據篡改成功，攻擊者需要比誠實者更快地產生下一個區塊。文獻［1］中已給出關于51%攻擊的證明，攻擊者潛在進展符合泊松分布，分布期望為：

其中：p為誠實者率先計算出滿足規則的隨機數概率；q為攻擊者率先計算出滿足規則的隨機數概率(p+q=1)；z為誠實節點領先的區塊數。攻擊者成功篡改區塊的概率Pz如下：

由式（1）可知，攻擊者成功篡改區塊的概率與p、q和z有關。當p＞q時，隨著z增加，攻擊者成功篡改區塊數據的概率呈指數趨勢下降，如圖4所示。

圖4 攻擊成功的概率Fig.4 Probability of successful attack

從圖4 可以看出，隨著誠實者領先的區塊數量增加，攻擊者成功篡改區塊的概率不斷減小，并趨向于0。因此，可以得出越原始的區塊數據被篡改的可能性就越低，其安全性越高。Borel 定律［21］定義了任何事件低于10-50的概率都是不可能的事件。由式（1）可知，當誠實者領先的區塊數量z增加到某一定數量時，Pz就會低于10-50。因此，在一條高度為n的區塊鏈中，高度為n-z+1之前的區塊可以被視為無法篡改的，故稱為高安全性區塊，高度為n-z+1 之后的區塊則被稱為低安全性區塊，如圖5所示。

圖5 區塊的安全性判定Fig.5 Security judgment of block

2.2 數據存儲

模型進行數據存儲時，需對區塊的安全性進行判定，對不同安全性的區塊采取不同的存儲策略。根據式（1）計算出Pz＜10-50時z的大小，來判斷區塊安全性的高低。區塊鏈的高度會隨著區塊地不斷加入逐漸增大，當區塊鏈的高度n≤z，區塊全部是低安全性區塊，節點直接存儲全部區塊；當區塊鏈的高度n＞z，將會有低安全性區塊轉變為高安全性區塊，因此節點需要根據基于CRT 的分割算法將高安全性區塊分片，然后存儲區塊碎片數據。基于CRT的分割算法如下：

算法1 基于CRT的分割算法。

輸入 區塊bki，節點選擇的模數mi；

輸出 區塊bki的碎片數據。

在算法1中，第1）行來判斷區塊是否為高安全性區塊，第3）～7）行來進行區塊數據分片。節點將高安全性區塊的區塊體bli轉為16進制數，再轉為10進制數來得到Ti。然后節點使用Ti與節點加入共識單元時選取的模數mi做取余運算，得到區塊體碎片，并將區塊體碎片以及區塊頭存儲到本地磁盤。為保證數據恢復時的正確性，共識單元在設定模數集合時，需要保證Ti＜Mk。

隨著時間的推移和區塊數量的增加，區塊會從剛加入區塊鏈時的低安全性區塊轉變為高安全性塊。節點通過算法1將高安全性區塊的區塊體數據分片來獲得區塊體碎片數據。節點存儲區塊體碎片與區塊頭數據不但降低了存儲消耗，而且由于區塊頭的存儲，也有效增加了攻擊者生成攻擊鏈來代替區塊鏈的難度，增強了模型的安全性。

2.3 數據讀取

節點讀取屬于低安全性區塊的區塊數據，直接訪問本地磁盤獲取區塊信息，而讀取屬于高安全性塊的區塊數據，則需要向其他節點發送請求獲取區塊碎片，并利用RRNS 的錯誤檢測與糾正來正確恢復區塊數據。其中，節點讀取高安全性區塊數據分為兩個階段：數據碎片獲取階段和數據恢復階段。

在數據碎片獲取階段，數據讀取節點向同一共識單元中的節點發送請求，其他節點收到請求返回所選取模數以及碎片數據，如圖6所示，具體過程如下：

圖6 數據讀取過程Fig.6 Process of data reading

1）數據讀取節點隨機向共識單元中k+s個節點發送請求；

2）節點收到請求，返回所選取的模數mi和存儲的碎片數據Si；

3）數據讀取返回數據并刪除重復的(mi，Si)，重復1）、2），當(mi，Si)個數為k+s時，結束。

在數據恢復階段，節點通過RRNS 錯誤檢測與糾正進行數據恢復，具體過程如下：

1）節點使用CRT 恢復來區塊數據X。若X≤Mk-1，執行步驟3）；若X＞Mk-1，執行步驟2）。

2）節點通過RRNS錯誤檢測與糾正，獲得X。

3）將X轉化為16 進制數，最后將16 進制轉為數據信息輸出。

在區塊鏈系統中，可能存在惡意節點，數據讀取節點可能接收到被惡意篡改的數據，使用CRT 可能無法恢復正確的區塊數據，因此模型使用RRNS 的錯誤檢測和糾正來恢復區塊數據。RRNS 的錯誤檢測和糾正能夠有效地保證區塊數據被正確恢復，并提高模型的容錯性和數據的完整性。

新節點加入區塊鏈網絡，需要進行數據同步。新加入的節點隨機選取一個共識單元模數集合β={m1，m2，…，mk，mk+1，…，mk+s}中的模數mi，向共識單元中的其他節點發送請求，獲取低安全性區塊和區塊頭，以及同一模數節點存儲的數據碎片數據。當獲取多個同一模數節點的數據碎片存在不同時，新節點選取多數節點保存的數據碎片進行存儲。

2.4 安全性分析

若在區塊鏈網絡中節點數量為N，惡意節點數量為Nd，惡意節點的概率為：pd=其中，共識單元中節點數量為Nc（Nc≥k+s）。對于低安全性區塊，所有節點都需存儲，因此將低安全性區塊視為無法被篡改的。高安全性區塊被分片由節點分布式存儲。因此，只需要對高安全性區塊進行分析。分析最簡單的情況，Nc=k+s，共識單元中至少需要k個誠實節點才可以恢復正確的區塊數據，共識單元中的節點能夠恢復區塊數據的概率為：

由式（2）可知，隨著惡意節點的概率不斷增加，數據恢復的概率由開始的基本沒影響，然后呈指數化下降，最后趨向于0。模型選取不同的k、s進行分析，具體情況如圖7所示。

圖7 數據恢復的概率變化Fig.7 Probability change of data recovery

對比k=30，s=30 和k=50，s=50 圖像發現，k、s相等時，取值越大，數據恢復的概率會相對較慢地呈指數化下降，但總體來說k、s相等時的取值對數據恢復影響較小。而對比k=50，s=50；k=50，s=70 和k=50，s=100 圖像，發現k設定為定值時，s的值越大，數據恢復的概率就越慢呈指數化下降，模型會具有更好的容錯性，能夠更好地保障數據的完整性和穩定性；并且隨著節點源源不斷地加入區塊鏈系統，多個節點獲取同一模數并存儲相同的數據碎片，模型的容錯性將持續提高。

在模型中，所有節點保存低安全性區塊來防止攻擊者通過區塊鏈分叉來篡改數據，并通過存儲高安性區塊的區塊頭來保障區塊數據的真實性和增加攻擊者生成攻擊鏈替代區塊鏈的難度。此外，節點存儲的高安全性區塊的區塊體碎片是一串沒有意義的數值，能夠有效地提高數據的隱私性，確保模型的安全性。

模型將高安全性區塊分片后分布式存儲，有效地降低了節點的存儲壓力，但會增加節點的計算消耗和通信消耗。針對節點計算和通信消耗問題，模型可以根據不同的應用場景來設置不同的信息模數基的和冗余檢錯基來進行調節，并且隨著計算和通信技術的發展，所遇問題可能迎刃而解。

3 實驗結果與分析

為了分析模型的相關性能，在Python 環境下搭建仿真平臺，開啟不同的服務器端口來創建本地共識節點，硬件參數：8 GB內存，i5-6 500 CPU和GeForce GT 730顯卡。實驗將本文提出的基于CRT 的區塊鏈存儲擴展模型和傳統區塊鏈模型所需要的時間和存儲空間進行對比。實驗主要針對存儲和時間消耗，因此簡化了工作量證明，將兩模型POW 的難度值設為2（當取的隨機數滿足整個區塊的哈希值前2 位為0 時獲得記賬權）。實驗一共建立了12 個節點，每產生10 筆交易數據進行一次挖礦（每筆交易數據相同）。本文模型中每個節點選取不同的模數mi（模數集合為{m1，m2，…，m12}，其中信息模數基的長度為k=5，冗余檢錯基的長度為s=7）形成共識單元，并且選取q=0.1，p=0.9，故z增加到100，Pz＜10-50，即區塊鏈當前高度的前100個區塊都是低安全性區塊。

實驗生成300 個區塊，將兩模型區塊生成和存儲的時間消耗進行對比。其中，本文模型只對生成300 個區塊中的前200 個區塊進行分片，兩模型后100 區塊時間消耗相同，因此只需對比前200 個區塊生成和存儲時間消耗。為了更好地測試時間消耗，實驗中直接對前200 區塊進行分片，并計算出平均時間消耗，結果如圖8 所示。由圖8 可知，本文模型與傳統區塊模型的時間消耗相差不大。傳統區塊鏈模型中，區塊生成后直接存儲，主要的時間消耗包括挖礦時間和存儲時間；而本文模型需要判斷已經生成的區塊的安全性，低安全性區塊直接存儲，高安全性區塊分片后存儲。兩種模型中區塊生成時間相同，主要差異為是否進行區塊分片。對前200 個區塊，本文模型平均時間消耗約為0.042 2 s，傳統區塊鏈模型平均時間消耗約為0.040 5 s。本文模型時間消耗略高于傳統區塊鏈模型的原因是模型需要將高安全性區塊的區塊體數字化，節點根據所選取的模數來分片。

圖8 傳統區塊鏈模型與本文模型在區塊生成與存儲的時間對比Fig.8 Comparison of time consumption of traditional blockchain model and the proposed model in block generation and storage time

實驗中分別生成不同的區塊數，包括0、100、200、300，對比模型中的節點將區塊數據存入數據庫，以此對比存儲消耗，如圖9、10所示。由圖9可知，隨著區塊數量的增加，與傳統區塊鏈模型相比，本文模型具有更低的存儲消耗。圖10 為圖9在0 個區塊數據時，兩個模型的節點所消耗的存儲空間。本文模型因需要存儲一個額外的模數，所以存儲消耗略大于傳統區塊鏈模型。當區塊鏈中的區塊數量小于或等于100 時，本文模型節點的存儲消耗略大于傳統區塊鏈模型中的節點。這是由于所有區塊都屬于低安全性區塊，兩模型中的節點都是直接存儲，而相比傳統區塊鏈模型中的節點，基于CRT 的區塊鏈存儲擴展模型中的節點需要額外存儲選取的模數。當區塊鏈中的區塊數量大于100 時，隨著區塊數量的增加，本文模型節點的存儲消耗逐漸小于傳統區塊鏈模型中的節點。這是由于將會有區塊從低安全性區塊變為高安全性區塊，本文模型中的節點將高安全性區塊分片，存儲區塊碎片，減少了存儲消耗。因此，本文模型能有效減輕節點的存儲壓力，增加區塊鏈系統的存儲擴展性。

圖9 兩模型節點存儲消耗對比Fig.9 Comparison of two models for node storage consumption

圖10 在0個區塊時節點存儲消耗對比Fig.10 Comparison of node storage consumption with 0 block

4 結語

本文主要對區塊鏈的存儲問題進行研究，提出了一種基于CRT 的區塊鏈存儲擴展模型來降低節點的存儲消耗。通過對區塊數據被篡改的可能性進行分析，將區塊鏈劃分為高安全性區塊和低安全性區塊。區塊鏈網絡中的節點根據區塊的安全性使用不同的存儲策略來存儲區塊：低安全性區塊直接存儲，高安全性區塊被基于CRT 的分割算法分片后被存儲，有效地減少了節點的存儲消耗。為保障區塊數據的完整性和提升區塊鏈系統的容錯性，引入RRNS 的錯誤檢測和糾正來防止區塊數據被篡改以及惡意節點作惡。實驗結果表明，該模型在保障區塊鏈系統安全的前提下，有效地降低了節點的存儲壓力，增加了區塊鏈系統的存儲可擴展性。未來可以進一步研究由節點的存儲能力和網絡帶寬來確定其所屬共識單元，提升系統的負載均衡。同時，將繼續研究怎么更加完善地解決區塊系統的存儲問題。