基于一致性哈希算法的區塊鏈優化模型

蘇暢

摘要：近些年來，區塊鏈技術憑借著其去中心化的優勢實現了安全的點對點交易、協調與協作。然而隨之而來的也有區塊鏈運作效率低下，浪費大量時間和空間的問題。本文擬通過一致性哈希算法（Consistent Hashing）對區塊鏈運行中出現的問題進行了研究和優化，較好地解決了區塊鏈存儲空間問題、重復驗證問題和數據分層管理問題。有效節約了網絡存儲資源。從而在保證區塊鏈運轉安全，可靠之外提供了更加高效的運行模型。

關鍵詞：區塊鏈技術;運作效率;一致性哈希算法;區塊鏈存儲

中圖分類號：TP311 ? ? ? ?文獻標識碼：A

文章編號：1009-3044（2019）14-0163-03

1 研究背景

狹義講，區塊鏈是一種按照時間順序將數據區塊以順序相連的方式組合成的一種鏈式數據結構，并以密碼學方式保證的不可篡改和不可偽造的分布式賬本。區塊鏈技術有效地解決了拜占庭將軍問題中的共識問題，實現了節點在無須互相信任的情況下能夠完成去中心化的點對點交易。但隨之而來的也有區塊鏈運作效率低下，浪費大量時間和空間等問題。為了更好的優化區塊鏈技術存儲方式，我們展開了調查、分析與研究。

2 區塊鏈運行原理探究

區塊鏈作為一種較為安全可靠的網上交易和存儲模式，被廣泛地運用在各種商業及金融領域。區塊鏈系統大約每十分鐘將全網產生的所有交易存儲到一個區塊中。由于區塊鏈節點之間是對等而互不信任的關系，區塊鏈使用了工作量證明（Proof-of-Work）。這使得生成的區塊具有較高的價值和可信任性。最終當一個區塊生成成功時向全網廣播，使得每個電腦上都有一份完整區塊鏈的拷貝。從而實現了節點在無須互相信任的情況下能夠完成去中心化的點對點交易的過程。

3 區塊鏈運行過程中的弊端

從上述區塊鏈運行原理中可以看出，區塊鏈在運行過程中具有十分高的安全性和穩定性，但是也存在以下幾個問題：

1）區塊鏈占用的網絡存儲資源十分大，這讓主區塊鏈在每一個節點中都存在一份備份變得越來越不實際。

2）當我們需要對新交易進行檢驗時，每個節點認證交易都需要對歷史區塊進行大量訪問。而全網中所有的節點都需要對重復的交易或區塊進行驗證，缺乏恰當的合作方式。

綜上，提出一種優化存儲與計算的區塊鏈模型刻不容緩。

4 一致性哈希算法原理與應用探究

一致性哈希算法是哈希算法的一種擴展。該算法實現了為服務器和存儲信息均實時變化的情況下較為合理地分配網絡緩存。接下來我們將簡要介紹一致性哈希算法：

1） 一致性哈希算法首先將服務器特征信息通過哈希函數映射到一個環上，并按照順時針將信息存儲到距離其最近的服務器上（如圖1，其中S代表服務器，A代表信息，虛線為存儲關系）。由于哈希函數的隨機性，每個服務器期望存儲的信息個數均相同。

2）如果服務器的個數增加時（如圖2，S3服務器為新增服務器），為了維護每個元素均存儲于順時針遇到的第一個服務器的原則，在S3右邊和S2左邊的所有數據（如A2）均需要從原服務器（S1）轉移到新增的服務器（S3）。而如果服務器個數減少，只需要將要刪除的服務器中的全部元素轉移到順時針遇到的下一個服務器即可。

分析算法效率可知：每個服務器平均存儲的信息量為信息總數除以服務器總數，同時在服務器變動時也只需要移動一個服務器中的信息。因此一致性哈希算法是一種高效而合理地分配網絡存儲資源的優秀算法，這為本文基于一致性哈希算法的區塊鏈優化模型的提出提供了正常高效運轉的基石。

5 基于一致性哈希算法的區塊鏈的優化模型

本模型繼承了區塊鏈分布式存儲的方法，擬建立用戶節點和服務節點兩種類型節點。其中用戶節點數量龐大、容易變動、安全等級低且存儲和計算能力均比較弱。而服務節點則具有運算能力強、存儲空間大和連接穩定等特點。

基于上述不同節點的特點，本模型將在每個服務節點上存儲整個主區塊鏈的備份并在服務節點上建立數據結構快速查找索引。而用戶節點只根據網絡要求在用戶節點上存儲少量區塊數據，同時用戶節點的驗證、計算等工作也將分攤一部分到服務節點。

下面將詳細介紹模型中節點的任務以及在實際情況中的模型的運轉流程。

1） 當用戶節點上線時，需要先搜尋一個服務節點作為自己的服務節點。并將自己的特征標識+當前時間+環內節點最后一個通過驗證的區塊輸入哈希函數并作為自己的在環上的位置（如圖3）。這樣決定節點位置可以保證位置定時刷新且無法被預測。當節點移動時，節點存儲信息利用一致性哈希算法移動。

2）當區塊鏈中有新的區塊產生的時候，首先由服務節點計算出區塊的哈希值并將其通過一致性哈希算法映射到該服務器管理的環中。（如圖4，綠色為區塊的映射位置，藍色為用戶節點的映射位置）并根據當前網絡安全程度、對信息來源可靠性的分析和當前在線節點個數，自動地沿著順時針方向尋找若干個節點（如標星節點）并令這些節點對該新生成的區塊進行校驗與認證。標星節點驗證完畢則視為該服務區對該區塊驗證成功。由于一致性哈希具有的隨機性質，其過程可以等價于在該服務區中隨機抽取若干個節點進行驗證工作。這使得少數的節點可以使用較少的工作量代替大多數節點驗證，同時由于系統的隨機性質使得這些節點難以被預測和攻擊。從而使這些節點的驗證具有代表性。

3）當一個區塊最終接入主區塊鏈后，服務節點需要將這個區塊加入主區塊鏈。同時，服務器將這個經過認證的區塊再次經過哈希映射在環上，并使得順時針若干個節點存儲區塊的備份文件。當節點需要讀取某區塊時，服務器將通過快速索引優先返回本地儲存的區塊鏈信息，同時該節點將隨機選擇1～2個存儲了所需區塊的節點，使其發送校驗信息到請求節點進行比對和認證。從而在保證讀取效率的情況下盡可能保證數據不會被篡改。

4）服務器需要定期對本地的數據和所有節點中緩存的數據進行查驗比較。如果發現了數據缺失或者數據不相同則通過網絡向其他服務節點獲取更加可靠的區塊鏈。這樣就可以避免由于本地錯誤或其他原因導致數據遺失和破壞，同時也使得入侵者難以對數據進行攻擊和破壞。

綜上，該模型在提升了區塊鏈的工作效率和優化區塊鏈占用的存儲的同時，有著一套較為可行的防攻擊和安全維護機制，使得模型穩定、高效而可靠。

6 針對實例的進一步優化

區塊鏈技術除了應用在金融領域，在網絡電子商務中也有廣泛應用。由于網上的廠商相對買家和賣家來說較為固定，所以可以在區塊鏈網絡中擔任服務節點的角色。而買賣雙方具有流動性大，變化迅速等特點，在網絡中扮演用戶節點的角色會比較合適。

在實際的網上交易中，一個交易單往往包含大量的信息。因此，我們可以按照數據的重要程度給數據分級，并將不同層級的交易單信息進行分片式存儲與管理。對于重要的數據，系統要求工作量證明難度更高、在認證時需要得到更多的用戶節點的認可，以及存儲時在多個不同的節點上保存備份文件以防篡改和丟失。而對于相對次要的數據，則可以適當地降低提供工作量證明的難度，在存儲時減少備份數量。

至此，優化模型的原理與概況基本闡述完畢，下表1為傳統區塊鏈與優化模型的優劣比較：

7 驗證數據與探究結果

通過自行編寫區塊鏈程序和本文中優化模型的程序、搭建小型網絡進行模擬測試，我們得到了以下若干實驗數據，并進行了對比分析。

實驗采用控制變量法，測試了若干個因素對程序的時間效率以及空間效率的影響。首先控制處理數據大小不變，控制PoW相對于網絡節點總算力難度不變，改變網絡中節點的數量，測得程序運行時所使用物理內存空間以及虛擬內存空間如表2：（注：其中內存占用為網絡中所有節點內存占用的平均值）

通過上述實驗數據我們可以看出以下幾個結論：①優化模型在面對同樣大小的數據時，其處理所用內存空間相對于普通區塊鏈來說具有較大的優勢。②對于優化模型，節點數的增加反而使得內存空間變少，因此在實際網絡中運行時優化模型也會具有更大的存儲優勢。

接著控制上述變量不變情況下，探究節點變化對算法運行時間的影響，測得數據如表3：

由表中凈運行時間的對比可見，節點數增加時，原區塊鏈算法的凈運行時間基本呈線性增長，而優化模型的凈運行時間則隨著節點個數的增多快速下降。這主要是因為通過網絡中服務節點的合理調度，優化模型較好地分配了各個節點的計算資源，使得節點消耗的運算資源大幅度減少。但在處理過程中，優化模型所需要的總處理時間要略多于原區塊鏈的處理時間。

接下來我們控制節點數量不變（始終為4），通過改變數據規模獲得相關信息。通過實驗測得在改變數據規模的情況下，程序運行時間和占用內存如表4：

通過比較我們發現，在數據規模變化時各個算法的時間基本呈現出線性增長，但是優化模型所用總時間相對于原區塊鏈所用總時間仍有一定差距。但是對比算法凈運行時間和內存效率，我們可以發現優化模型在不同的數據規模之下仍然擁有更加高效的凈處理時間和內存使用量，這進一步體現出了優化模型調配網絡計算、存儲資源的優越性。

綜上，本文提出的基于一致性哈希算法的區塊鏈優化模型具有十分優秀的存儲效率，具有優秀的存儲容量可擴展性。同時本文模型在處理的時間效率上也與普通區塊鏈差距不大，單個節點的工作量大幅降低。

8 結語

在當今信息爆炸式增長的時代，區塊鏈也難免存在著存儲和計算效率的問題。本文通過對一致性哈希算法和區塊鏈相關技術的有效結合，成功創立了基于一致性哈希算法的區塊鏈優化模型。該模型從區塊鏈存儲，區塊鏈運算和數據分級管理等多個方面對現有區塊鏈進行補充和優化，彌補了區塊鏈存儲與計算方面的不足。同時模型提出了服務器定期自動核查、同步的方式來確保區塊鏈的安全運行，極大程度上防止了外來攻擊對重要數據的破壞與篡改。其優異的性能和可靠的安全性，使該模型在現代信息社會具有重要的現實意義。

參考文獻：

[1] 賈大宇，信俊昌，王之瓊，等.區塊鏈的存儲容量可擴展模型[J].計算機科學與探索，2017（9）.

[2] 郝琨，信俊昌，黃達，等.去中心化的分布式存儲模型[J].計算機工程與應用，2017（12）.

[3] Tim Roughgarden Gregory Valiant.CS168：The Modern Algorithmic Toolbox Lecture #1： Introduction and Consistent Hashing.2018-04-02

[4] 邱寧佳，胡小娟，王鵬，等. 一致性哈希的數據集群存儲優化策略研究[J].信息與控制，2016（12）.

【通聯編輯：唐一東】