基于Merkle山脈的數(shù)據(jù)可信溯源方法

劉 煒，張聰，佘維，宋軒，田釗*

（1.鄭州大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，鄭州 450002；2.互聯(lián)網(wǎng)醫(yī)療與健康服務(wù)河南省協(xié)同創(chuàng)新中心（鄭州大學(xué)），鄭州 450052）

0 引言

隨著物聯(lián)網(wǎng)［1］、大數(shù)據(jù)等信息技術(shù)的發(fā)展，數(shù)據(jù)呈現(xiàn)爆炸性增長［2］。在大數(shù)據(jù)時代下，數(shù)據(jù)作為重要資產(chǎn)，背后的價值日益凸顯。數(shù)據(jù)共享可以實現(xiàn)數(shù)據(jù)價值的交換和利用，為了防止數(shù)據(jù)惡意篡改和造假等行為，需要對共享數(shù)據(jù)的真?zhèn)?、?shù)據(jù)的質(zhì)量進(jìn)行監(jiān)管和存證，即對數(shù)據(jù)的演變過程進(jìn)行記錄，便于日后產(chǎn)生異議時進(jìn)行數(shù)據(jù)溯源［3］。溯源是指記錄、訪問、驗證數(shù)據(jù)在整個流轉(zhuǎn)過程中的演變，從數(shù)據(jù)的生產(chǎn)源頭到最終的流轉(zhuǎn)結(jié)果。通過對數(shù)據(jù)溯源，防止記錄在流轉(zhuǎn)過程中被非法篡改，保證數(shù)據(jù)的安全性、真實性和可靠性［4］。目前，常見的溯源方法有標(biāo)注法，雖然可以達(dá)到數(shù)據(jù)溯源的目的，但在大數(shù)據(jù)時代下，需要極大的存儲空間，給存儲系統(tǒng)帶來巨大的存儲壓力；此外，現(xiàn)有的存儲技術(shù)多采用中心化數(shù)據(jù)庫，一旦中央服務(wù)器遭受惡意攻擊，系統(tǒng)會出現(xiàn)單點(diǎn)故障［5-6］，且中心化的存儲方式由于監(jiān)管力度不夠，存在利益驅(qū)使而造假數(shù)據(jù)，使數(shù)據(jù)溯源過程變得困難且可信度不高。在物聯(lián)網(wǎng)系統(tǒng)中，大多數(shù)是輕量級節(jié)點(diǎn)，節(jié)點(diǎn)的可用資源有限，而數(shù)據(jù)溯源過程中驗證需要消耗大量時間和設(shè)備資源，對輕量級節(jié)點(diǎn)來說是一個嚴(yán)峻的挑戰(zhàn)。

區(qū)塊鏈［7］技術(shù)源于2008 年，它是一個分類賬本，具有不可篡改、分布式存儲、去中心化等特性。區(qū)塊鏈獨(dú)特的鏈?zhǔn)浇Y(jié)構(gòu)，使每一個區(qū)塊都包含前一區(qū)塊的哈希，提供了可追溯和可驗證性，解決了傳統(tǒng)溯源方法中存在的問題。文獻(xiàn)［8］中提出了密文策略基于屬性加密（Ciphertext-Policy Attribute-Based Encryption，CP-ABE）的溯源方案，基于策略的加密算法使區(qū)塊內(nèi)容可以動態(tài)更新，保護(hù)數(shù)據(jù)隱私的同時實現(xiàn)溯源信息共享；文獻(xiàn)［9］中提出了一種基于聯(lián)盟鏈和IPFS（Inter-Planetary File System）的質(zhì)量數(shù)據(jù)追溯方案，將加密的質(zhì)量數(shù)據(jù)和對應(yīng)的密鑰存儲在IPFS 中，實現(xiàn)質(zhì)量數(shù)據(jù)的追溯過程；文獻(xiàn)［10］中基于區(qū)塊鏈提出了一種疾病信息跟蹤方法，以2019 冠狀病毒病為例，形成疾病信息時間序列區(qū)塊鏈，便于追蹤傳染病傳播途徑；文獻(xiàn)［11］中基于區(qū)塊鏈提出了一個食品追溯模型，通過食品質(zhì)量指數(shù)算法生成食品質(zhì)量數(shù)，存儲在區(qū)塊鏈中，并結(jié)合產(chǎn)品標(biāo)識符實現(xiàn)可靠的食品溯源；文獻(xiàn)［12］中針對多層次紡織品供應(yīng)鏈，提出了一個基于區(qū)塊鏈可追溯框架，智能合約實現(xiàn)特定的交易規(guī)則，并驗證該區(qū)塊鏈系統(tǒng)的可行性；文獻(xiàn)［13］中提出了一種雙聯(lián)盟鏈存儲結(jié)構(gòu)，使用區(qū)塊鏈記錄網(wǎng)絡(luò)中動態(tài)數(shù)據(jù)的流轉(zhuǎn)過程，通過公鑰機(jī)制完成數(shù)據(jù)的安全傳輸，實現(xiàn)對數(shù)據(jù)的追溯；文獻(xiàn)［14］中以飛機(jī)配件為例，借助區(qū)塊鏈技術(shù)，實現(xiàn)一個追溯系統(tǒng)，通過該系統(tǒng)可以實現(xiàn)配件供應(yīng)鏈中各個組織的信息共享和數(shù)據(jù)追溯；文獻(xiàn)［15］中基于區(qū)塊鏈技術(shù)設(shè)計了一個農(nóng)產(chǎn)品供應(yīng)鏈的信息存儲和查詢追溯系統(tǒng)，結(jié)合數(shù)據(jù)庫和區(qū)塊鏈實現(xiàn)鏈上鏈下雙存儲，緩解區(qū)塊鏈存儲壓力；文獻(xiàn)［16］中提出了一種基于聯(lián)盟鏈的農(nóng)產(chǎn)品溯源方法，采用拜占庭容錯算法（Practical Byzantine Fault Tolerance，PBFT）減少共識時間，實現(xiàn)高效的溯源過程。

上述文獻(xiàn)將區(qū)塊鏈應(yīng)用于溯源場景，解決了傳統(tǒng)溯源系統(tǒng)中數(shù)據(jù)不透明、追溯結(jié)果不可信、數(shù)據(jù)庫中心化程度高、信息孤島等問題，實現(xiàn)了在農(nóng)業(yè)、工業(yè)等領(lǐng)域的數(shù)據(jù)可信溯源，但提出的區(qū)塊鏈溯源方案，沒有考慮到數(shù)據(jù)追溯驗證時資源消耗和效率問題。由于物聯(lián)網(wǎng)系統(tǒng)中的設(shè)備多為輕量級節(jié)點(diǎn)［17］，這些節(jié)點(diǎn)計算能力和存儲資源有限，在進(jìn)行數(shù)據(jù)追溯時，保存海量的物聯(lián)網(wǎng)數(shù)據(jù)較為困難，溯源驗證過程效率低下，即使基于區(qū)塊鏈技術(shù)，只需保存區(qū)塊頭信息，對資源有限的輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)來說，也是一個嚴(yán)峻的考驗。隨著區(qū)塊鏈網(wǎng)絡(luò)高度的增加，溯源時需要下載的數(shù)據(jù)量增大，對驗證節(jié)點(diǎn)的存儲空間和資源要求較高，因此不適用于資源有限的物聯(lián)網(wǎng)場景。

綜上所述，本文提出一種基于Merkle 山脈（Merkle Mountain Range，MMR）［18］的數(shù)據(jù)可信溯源方法MMRBCV（Merkle Mountain Range BlockChain Verification），引入IPFS，提高系統(tǒng)存儲容量，緩解區(qū)塊鏈存儲壓力；設(shè)計雙鏈結(jié)構(gòu)，源數(shù)據(jù)與數(shù)據(jù)流轉(zhuǎn)記錄分開存儲，提高數(shù)據(jù)的隱私性和安全性；在區(qū)塊中引入Merkle 山脈（MMR）減少驗證過程中所需下載的數(shù)據(jù)量和驗證時間，解決輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)因資源受限存在的驗證問題。

1 相關(guān)技術(shù)

1.1 區(qū)塊鏈

區(qū)塊鏈網(wǎng)絡(luò)中節(jié)點(diǎn)相互獨(dú)立，共同參與數(shù)據(jù)管理和交易記錄，部分節(jié)點(diǎn)出現(xiàn)宕機(jī)問題不會影響整個網(wǎng)絡(luò)的運(yùn)行，可以避免單點(diǎn)故障。

區(qū)塊由區(qū)塊頭和區(qū)塊體組成：區(qū)塊頭包含交易、時間戳、難度值、目標(biāo)散列、Merkle 樹根（Merkle Tree Root，MTR）等關(guān)鍵字，通過保存前一區(qū)塊的哈希，形成一種鏈?zhǔn)浇Y(jié)構(gòu)，為區(qū)塊鏈提供了可追溯性；區(qū)塊體包含網(wǎng)絡(luò)中的交易，采用Merkle樹（Merkle Tree，MT）的結(jié)構(gòu)存儲。區(qū)塊結(jié)構(gòu)如圖1所示。

圖1 區(qū)塊結(jié)構(gòu)Fig.1 Block structure

區(qū)塊鏈根據(jù)其開放程度和應(yīng)用場景，可以分為公有鏈、聯(lián)盟鏈和私有鏈3 種［19］，如表1 所示。公有鏈去中心化程度最高，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)可以自由地加入或退出，節(jié)點(diǎn)身份匿名，數(shù)據(jù)的公開性和透明性強(qiáng)；聯(lián)盟鏈去中心化程度相對較弱，只有經(jīng)過授權(quán)的節(jié)點(diǎn)才可以加入網(wǎng)絡(luò)中，節(jié)點(diǎn)身份需要通過審核，多用于商業(yè)機(jī)構(gòu)，由Linux 基金會發(fā)起的Hyperledger Fabric 就是典型的聯(lián)盟鏈［20］；私有鏈中心化程度最高，開放程度最低，只有私人或者某一特定組織有使用權(quán)限，一般多用于企業(yè)內(nèi)部。

表1 區(qū)塊鏈類型Tab.1 Blockchain types

1.2 IPFS

IPFS 是一個面向全球、點(diǎn)對點(diǎn)的分布式的文件系統(tǒng)［21］。它基于BitTorrent 協(xié)議進(jìn)行文件分發(fā)，上傳到IPFS 的文件會返回一個哈希值作為CID（Content-ID）。當(dāng)文件內(nèi)容被修改時，對應(yīng)的哈希值也會發(fā)生變化，保證文件與CID 一一對應(yīng)。對于已經(jīng)存在的數(shù)據(jù)文件，再次上傳時不會返回新的哈希值。IPFS 存儲如圖2 所示。

圖2 IPFS存儲Fig.2 IPFS storage

IPFS 存儲文件時步驟如下：

1）把文件拆分成若干個256 KB 大小的數(shù)據(jù)塊，如果文件大小沒超過256 KB，則不執(zhí)行此步驟。

2）對拆分后的文件數(shù)據(jù)塊1，2，…，n，逐個進(jìn)行哈希運(yùn)算，得到數(shù)據(jù)塊對應(yīng)的哈希值hash(1)，hash(2)，…，hash(n)。

3）將所有的hash(1)，hash(2)，…，hash(n)拼湊，構(gòu)成一個數(shù)組，將該數(shù)組再次進(jìn)行哈希運(yùn)算，得到文件對應(yīng)的hash(file)，hash(file)=hash(∑hash(i))（i=1，2，…，n），即文件的CID，再次查找只需通過該CID 即可在IPFS 中找到相關(guān)文件。

本文使用IPFS 作為數(shù)據(jù)存儲層，緩解區(qū)塊鏈存儲壓力，提高存儲容量。

1.3 Merkle山脈

Merkle 山脈是Peter Todd 提出的變種數(shù)據(jù)結(jié)構(gòu)［22］，是一種特殊的Merkle 樹。在構(gòu)造數(shù)據(jù)結(jié)構(gòu)時，Merkle 樹是一棵完美二叉樹，而Merkle 山脈不一定是完美二叉樹。當(dāng)Merkle 樹構(gòu)建完成后，不可再對數(shù)據(jù)進(jìn)行增加或者刪除，而Merkle 山脈可以動態(tài)地進(jìn)行數(shù)據(jù)的追加，不需要重新構(gòu)建該數(shù)據(jù)結(jié)構(gòu)。Merkle 樹和Merkle 山脈都是由葉子節(jié)點(diǎn)進(jìn)行哈希運(yùn)算，最后生成該數(shù)據(jù)結(jié)構(gòu)。Merkle 山脈也可以驗證一個葉子節(jié)點(diǎn)是否存在該結(jié)構(gòu)之中。Merkle 樹和Merkle 山脈兩種數(shù)據(jù)結(jié)構(gòu)中已有的葉子節(jié)點(diǎn)中數(shù)據(jù)發(fā)生改變都會導(dǎo)致父節(jié)點(diǎn)的改變，所以MTR 的值和Merkle 山脈根（Merkle Mountain Range Root，MMRR）的值也會發(fā)生變化。如果MTR 或MMRR 中存儲的哈希值沒有變，則說明葉子節(jié)點(diǎn)存儲的數(shù)據(jù)沒有改變，因此廣泛應(yīng)用于區(qū)塊鏈中進(jìn)行交易驗證。

本文在區(qū)塊中引入Merkle 山脈結(jié)構(gòu)、輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)溯源時，只需下載鏈上的一個最新區(qū)塊即可完成數(shù)據(jù)溯源中的驗證過程。

2 數(shù)據(jù)可信溯源方法

本文設(shè)計基于Merkle 山脈的數(shù)據(jù)可信溯源方法，以IPFS作為數(shù)據(jù)層，提出數(shù)據(jù)私有鏈（Data Private BlockChain，DPBC）和記錄聯(lián)盟鏈（Record Consortium BlockChain，RCBC）雙鏈模型，保護(hù)數(shù)據(jù)隱私性，提高存儲安全性。在此模型上設(shè)計一種Merkle 山脈區(qū)塊結(jié)構(gòu)，用于物聯(lián)網(wǎng)系統(tǒng)中輕量級節(jié)點(diǎn)進(jìn)行數(shù)據(jù)溯源時的驗證。

2.1 雙鏈架構(gòu)

數(shù)據(jù)溯源過程既要滿足溯源數(shù)據(jù)真實可靠，數(shù)據(jù)流轉(zhuǎn)過程公開透明，又要保證數(shù)據(jù)追溯過程中的隱私性和安全性［23］。本文提出基于聯(lián)盟鏈和私有鏈的雙鏈溯源模型，如圖3 所示。同一局域網(wǎng)的物聯(lián)網(wǎng)設(shè)備作為私有鏈節(jié)點(diǎn)，包括全節(jié)點(diǎn)和輕節(jié)點(diǎn)，DPBC 的作用是實現(xiàn)數(shù)據(jù)的可靠存儲。物聯(lián)網(wǎng)節(jié)點(diǎn)采集的源數(shù)據(jù)上傳到IPFS 中，IPFS 返回文件對應(yīng)的CID，文件CID 和文件摘要作為私有鏈中的交易，存儲在Merkle 樹的葉子節(jié)點(diǎn)里，便于后續(xù)對數(shù)據(jù)的查詢和追溯。私有鏈的中心化程度高，只有少數(shù)節(jié)點(diǎn)可以訪問，保證鏈上數(shù)據(jù)的隱私性，區(qū)塊鏈不可篡改的特性以及IPFS 的唯一對應(yīng)性，保證鏈上存儲的數(shù)據(jù)文件不可篡改。

圖3 雙鏈結(jié)構(gòu)Fig.3 Double-blockchain structure

數(shù)據(jù)私有鏈中的物聯(lián)網(wǎng)全節(jié)點(diǎn)組成聯(lián)盟成員，構(gòu)成聯(lián)盟鏈。RCBC 主要功能是溯源信息的查詢共享，記錄數(shù)據(jù)文件的流轉(zhuǎn)過程。通過智能合約，物聯(lián)網(wǎng)全節(jié)點(diǎn)將數(shù)據(jù)文件的操作記錄同步到聯(lián)盟鏈中，通過共識算法達(dá)成一致，以Merkle樹的結(jié)構(gòu)存儲在RCBC 的區(qū)塊體中，第三方對數(shù)據(jù)文件的操作產(chǎn)生爭議時，可以通過聯(lián)盟鏈對數(shù)據(jù)以及結(jié)果進(jìn)行追溯，獲取區(qū)塊內(nèi)容，保證數(shù)據(jù)流轉(zhuǎn)記錄的安全可信。

聯(lián)盟鏈和私有鏈中均引入Merkle 山脈結(jié)構(gòu)（區(qū)塊結(jié)構(gòu)在2.2 節(jié)進(jìn)行詳細(xì)說明），把當(dāng)前高度之前的所有區(qū)塊頭作為Merkle 山脈的葉子節(jié)點(diǎn)存儲：一方面實現(xiàn)區(qū)塊的錨定，保證該高度前的所有區(qū)塊存儲內(nèi)容不可篡改；另一方面引入Merkle 山脈結(jié)構(gòu)，便于輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)進(jìn)行溯源數(shù)據(jù)時的快速高效驗證。

采用雙鏈結(jié)構(gòu)的設(shè)計：一方面可以提高區(qū)塊鏈網(wǎng)絡(luò)的性能，數(shù)據(jù)流轉(zhuǎn)記錄和數(shù)據(jù)分開存儲的方式，減輕網(wǎng)絡(luò)中的通信負(fù)擔(dān)，提高溯源查詢效率；另一方面私有鏈可以保證鏈上存儲數(shù)據(jù)的隱私安全。IPFS 作為模型的數(shù)據(jù)層，可以將大量的物聯(lián)網(wǎng)設(shè)備采集的數(shù)據(jù)存儲在IPFS中，緩解區(qū)塊鏈的存儲壓力，實現(xiàn)數(shù)據(jù)鏈上鏈下的高效存儲。IPFS 和區(qū)塊鏈結(jié)合，提高了系統(tǒng)的存儲能力和安全性，解決了區(qū)塊鏈擴(kuò)展性不足的問題。

2.2 MMR區(qū)塊結(jié)構(gòu)

本文對區(qū)塊結(jié)構(gòu)進(jìn)行了改進(jìn)，設(shè)計一種新的Merkle 山脈區(qū)塊結(jié)構(gòu)如圖4 所示。區(qū)塊包含區(qū)塊頭和區(qū)塊體兩部分，區(qū)塊頭中新增字段MMRR，區(qū)塊體中新增Merkle 山脈結(jié)構(gòu)。區(qū)塊頭包含版本號、時間戳、難度值、目標(biāo)散列、前一區(qū)塊哈希、MTR 和MMRR，區(qū)塊體由Merkle 樹和Merkle 山脈組成。Merkle 樹中的葉子節(jié)點(diǎn)存儲區(qū)塊鏈網(wǎng)絡(luò)中的交易信息，DPBC 中Merkle 樹的葉子節(jié)點(diǎn)存儲文件CID 和文件摘要，RCBC 中Merkle 樹的葉子節(jié)點(diǎn)存儲文件流轉(zhuǎn)過程。Merkle 樹的葉子節(jié)點(diǎn)經(jīng)過哈希計算，得到MTR，并將該數(shù)據(jù)錨定在區(qū)塊頭中。Merkle 山脈中的葉子節(jié)點(diǎn)存儲區(qū)塊鏈上的區(qū)塊頭，DPBC 和RCBC 的葉子節(jié)點(diǎn)均為該區(qū)塊前的所有區(qū)塊頭，經(jīng)過哈希計算得到MMRR。通過Merkle 樹證明和Merkle 山脈證明可驗證Merkle 樹和Merkle 山脈中的數(shù)據(jù)是否被篡改。

圖4 Merkle山脈區(qū)塊結(jié)構(gòu)Fig.4 Block structure based on Merkle mountain range

隨著區(qū)塊鏈網(wǎng)絡(luò)的應(yīng)用，區(qū)塊高度線性增長。對于計算及存儲能力較小的輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)來說，同步區(qū)塊鏈上所有的區(qū)塊頭日志，會消耗大量節(jié)點(diǎn)資源和時間。如果在區(qū)塊中引入Merkle 山脈結(jié)構(gòu)，通過MMRR 可以驗證包含該交易的區(qū)塊是否在網(wǎng)絡(luò)中的最長合法鏈上，用來驗證區(qū)塊頭的合法性，可以減少區(qū)塊鏈網(wǎng)絡(luò)中驗證時造成的資源浪費(fèi)、縮短驗證時間，降低輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)的工作壓力。當(dāng)鏈上有新的區(qū)塊生成時，只需將新區(qū)塊作為Merkle 山脈一個葉子節(jié)點(diǎn)，動態(tài)追加即可。

2.3 Merkle山脈證明

數(shù)據(jù)溯源過程中需要對Merkle 山脈葉子節(jié)點(diǎn)存儲的數(shù)據(jù)進(jìn)行驗證，確保數(shù)據(jù)未被篡改、真實可信，即Merkle 山脈證明［22］。把Merkle 山脈證明集合進(jìn)行哈希計算，記為MMRR'，將MMRR'與區(qū)塊中存儲MMRR 哈希值進(jìn)行對比：如果相同，則表明數(shù)據(jù)真實可信未被篡改；如果結(jié)果不同，根據(jù)哈希計算的不可逆性，表明待驗證葉子節(jié)點(diǎn)數(shù)據(jù)被惡意篡改，數(shù)據(jù)不可信。Merkle 山脈證明過程為：

1）從待驗證的目標(biāo)節(jié)點(diǎn)開始，向上層父節(jié)點(diǎn)查找，到目標(biāo)節(jié)點(diǎn)所在Merkle 樹的MTR 結(jié)束，查找所經(jīng)過節(jié)點(diǎn)集合稱為Merkle 山脈路徑；

2）查找Merkle 山脈中所有子樹的MTR；

3）將Merkle 山脈路徑中的節(jié)點(diǎn)和第2）步中中子樹的MTR 構(gòu)成一個證明集合，即Merkle 山脈證明集合；

4）對Merkle 山脈證明集合進(jìn)行哈希運(yùn)算得到MMRR'，與區(qū)塊頭中的MMRR 字段比較是否一致，完成Merkle 山脈證明。

以圖5 中葉子節(jié)點(diǎn)L8 為例說明Merkle 山脈證明過程，要證明L8，就需要得到圖5 中虛線圈住的節(jié)點(diǎn)哈希值，其中hash（）表示取哈希值。

圖5 Merkle山脈結(jié)構(gòu)Fig.5 Structure of Merkle mountain range

1）計算葉子節(jié)點(diǎn)L8 哈希值H'(8)、H'(8)=hash(L8)，獲取Merkle 山脈路徑中葉子節(jié)點(diǎn)L9、L12 哈希值H(9)、H(12)，H(9)=hash(L9)、H(12)=hash(L12)。

2）獲取Merkle 山脈中葉子節(jié)點(diǎn)L8 所在子樹中的一個右子根H(10，11)，即H(10，11)=hash(H(10)&H(11))。

3）將葉子節(jié)點(diǎn)L8 的哈希值H'(8)、葉子節(jié)點(diǎn)L9 的哈希值H(9)，哈希運(yùn)算得H'(8，9)=hash(H'(8)&H(9))。

4）將步驟3）計算結(jié)果H'(8，9)與步驟2）H(10，11)，再次進(jìn)行哈希運(yùn)算，計算得到H'(H'(8，9)，H(10，11))，即H'(H'(8，9)，H(10，11))=hash(H'(8，9)&H(10，11))。

5）獲取圖5 中，Merkle 山脈結(jié)構(gòu)中最左側(cè)一個完美二叉子樹的根，即H(((0，1)&(2，3))&((4，5)&(6，7)))。

6）將數(shù)據(jù)H(12)、H(((0，1)&(2，3))&((4，5)&(6，7)))、H'(H'(8，9)，H(10，11))哈希得到MMRR'，如式（1）所示：

7）將計算得到的MMRR'與存儲在區(qū)塊中的MMRR進(jìn)行對比，如果MMRR'=MMRR，證明節(jié)點(diǎn)L8 數(shù)據(jù)未被篡改。

上述證明過程流程如圖6 所示。

圖6 Merkle山脈證明流程Fig.6 Flow of Merkle mountain range proof

2.4 Merkle山脈區(qū)塊溯源方法

本文提出一種基于Merkle 山脈的數(shù)據(jù)溯源方法，溯源方法流程如圖7 所示，其中K表示當(dāng)前網(wǎng)絡(luò)中最新的區(qū)塊高度；k表示待驗證的區(qū)塊高度。當(dāng)需要對高度為k(k＜K)的區(qū)塊中的數(shù)據(jù)流轉(zhuǎn)記錄（Data Flow Record，DFR）進(jìn)行驗證時，輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)只需要從網(wǎng)絡(luò)中同步第k個區(qū)塊以及最新高度K的區(qū)塊頭即可完成驗證，具體內(nèi)容如算法1 所示。當(dāng)需要驗證通過第k(k≤K)個區(qū)塊中的交易時，首先通過區(qū)塊高度為k的區(qū)塊頭中的MTR可以驗證區(qū)塊體中的數(shù)據(jù)是否存在且正確；其次通過第K個區(qū)塊頭中的MMRR 可以驗證第k個區(qū)塊的MTR 是否正確，即驗證第k(k＜K)個區(qū)塊是否在最長合法鏈上。通過上述兩步即可完成驗證過程而無需下載整條鏈的區(qū)塊頭，從而節(jié)省存儲空間，減少輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)能源消耗。

圖7 MMRBCV溯源流程Fig.7 Flow chart of MMRBCV traceability

驗證步驟如下：

1）物聯(lián)網(wǎng)系統(tǒng)中的輕量級節(jié)點(diǎn)，從DPBC 網(wǎng)絡(luò)中全節(jié)點(diǎn)的本地賬本同步高度為k的區(qū)塊信息，從k區(qū)塊中獲得該區(qū)塊中MT 的MTR。

2）節(jié)點(diǎn)通過哈希計算得到MTR'，如果MTR'=MTR，則證明該交易包含在區(qū)塊中且正確。

3）需要進(jìn)行數(shù)據(jù)驗證的物聯(lián)網(wǎng)系統(tǒng)輕量級節(jié)點(diǎn)，從RCBC 網(wǎng)絡(luò)中全節(jié)點(diǎn)的本地賬本，同步當(dāng)前最新高度K的區(qū)塊信息，從K區(qū)塊獲得MMRR。

4）輕量級節(jié)點(diǎn)通過哈希計算得到，如果MMRR'=MMRR，則證明高度為k（k＜K）的區(qū)塊在網(wǎng)絡(luò)中的最長合法鏈上，完成驗證。

上述過程如算法1 所示。

算法1 數(shù)據(jù)溯源方法。

輸入 數(shù)據(jù)流轉(zhuǎn)記錄DFR；

輸出 追溯結(jié)果true/false。

上述驗證過程先驗證某筆交易包含在高度為k的區(qū)塊中，再驗證高度為k的區(qū)塊在最長合法鏈上，從而完成數(shù)據(jù)追溯過程。

3 實驗與分析

為評估本文提出的數(shù)據(jù)追溯方法性能，進(jìn)行仿真實驗，使用Python 語言，對SPV（Simplified Payment Verification）和MMRBCV 方法進(jìn)行對比分析。實驗環(huán)境為Intel Core i7-4790 CPU 和8 GB 內(nèi)存，操作系統(tǒng)為64 位Windows 10。

3.1 數(shù)據(jù)下載量對比分析

數(shù)據(jù)下載量是指節(jié)點(diǎn)進(jìn)行數(shù)據(jù)追溯驗證時，需要在本地保存的數(shù)據(jù)大小。數(shù)據(jù)下載量與節(jié)點(diǎn)的資源消耗成正比。區(qū)塊鏈高度越高，輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)需要下載的區(qū)塊頭數(shù)據(jù)量越大，需要的節(jié)點(diǎn)資源越多。本實驗對比分析相同區(qū)塊高度下，節(jié)點(diǎn)使用SPV 需要下載的數(shù)據(jù)量和MMRBCV 需要下載的數(shù)據(jù)量。為討論區(qū)塊數(shù)量對資源消耗的影響，選擇區(qū)塊高度為1 000、2 000、3 000、10 000、20 000、30 000、60 000、100 000、150 000、200 000 時，SPV 和本文提出的MMRBCV 兩種方法進(jìn)行驗證時的數(shù)據(jù)下載量，實驗結(jié)果如表2 所示。

表2 SPV和MMRBCV的數(shù)據(jù)下載量Tab.2 Data downloaded by SPV and MMRBCV

隨著區(qū)塊鏈高度增加，SPV 和MMRBCV 所需下載的數(shù)據(jù)量都會增大；但SPV 進(jìn)行數(shù)據(jù)驗證時，需要下載整條鏈的區(qū)塊頭信息，本文方法只需要下載最長合法鏈中的最新區(qū)塊。從表2 中數(shù)據(jù)可以看出，在相同的區(qū)塊高度下，MMRBCV 方法比SPV 下載數(shù)據(jù)量小，一定程度上可以減少輕節(jié)點(diǎn)的資源消耗。

3.2 驗證時間對比分析

驗證時間是指驗證某筆交易所需要的時間。驗證時間是溯源過程中一個重要指標(biāo)，時間越短，溯源效率越高。本文中驗證時間測試的是從提交包含某筆交易的MTR 到查找到該哈希值之間的時間。為討論不同數(shù)量級區(qū)塊對驗證時間的影響，實驗選擇區(qū)塊高度為1 000、2 000、3 000、10 000、20 000、30 000、60 000、100 000、150 000、200 000 時，對比SPV和MMRBCV 數(shù)據(jù)驗證的時間。

實驗結(jié)果如圖8 所示，當(dāng)區(qū)塊鏈網(wǎng)絡(luò)中區(qū)塊數(shù)量增多時，SPV 和MMRBCV 方法的驗證時間會逐步增加，相比之下，SPV 驗證時間長，這是因為該方法需要從最新高度區(qū)塊開始向下遍歷，直到追溯到目標(biāo)區(qū)塊。MMRBCV 方法驗證時間短，這是由于MMRBCV 只需獲取Merkle 山脈的驗證路徑計算得到MMRR，與最新高度區(qū)塊頭中哈希值進(jìn)行對比。當(dāng)區(qū)塊高度為200 000 時，SPV 的最大時間開銷約為36 ms，MMRBCV 的最大時間開銷約為10 ms，驗證時間較SPV 縮短了約72%，提高數(shù)據(jù)溯源過程中的驗證效率。

圖8 SPV和MMRBCV的驗證時間Fig.8 Verification time of SPV and MMRBCV

3.3 區(qū)塊高度對驗證時間的影響分析

Merkle 山脈是一種可變的數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)中的節(jié)點(diǎn)數(shù)量會影響結(jié)構(gòu)中二叉樹的個數(shù)和形狀，當(dāng)數(shù)據(jù)中的節(jié)點(diǎn)數(shù)據(jù)量為2n時，Merkle 山脈可以組成一個完美二叉樹的結(jié)構(gòu)，即和Merkle 樹的結(jié)構(gòu)相同，Merkle 山脈中的結(jié)構(gòu)包含多個二叉樹。為討論Merkle 山脈結(jié)構(gòu)對數(shù)據(jù)溯源效率的影響，從樹的高度和是否為完美二叉樹兩個方面驗證，當(dāng)樹高度為14、15、16 時，分別討論Merkle 山脈為完美二叉樹和非完美二叉樹兩種情況，即214-1、214、215-1、215、216-1、216，對應(yīng)葉子節(jié)點(diǎn)個數(shù)為16 383、16 384、32 767、32 768、65 535、65 536 時完成一次驗證所需的時間，實驗結(jié)果如表3 所示。

表3 不同區(qū)塊高度時的驗證時間Tab.3 Verification time with different block height

以Merkle 山脈高度是15 為例，測試Merkle 山脈葉子節(jié)點(diǎn)個數(shù)為30 000 至34 000 時，完成一次驗證所需的時間，實驗結(jié)果如圖9 所示。

圖9 高度為30 000～34 000時MMRBCV的驗證時間Fig.9 MMRBCV’s verification time with height of 30 000 to 34 000

數(shù)據(jù)驗證時間與Merkle 山脈結(jié)構(gòu)有關(guān)，當(dāng)Merkle 山脈可以組成一個完美二叉樹時，完成一次驗證過程所需的時間，比Merkle 山脈是一個非完美二叉樹的驗證時間短，即使非完美二叉樹結(jié)構(gòu)的Merkle 山脈葉子節(jié)點(diǎn)少。因為Merkle 山脈是一個完美二叉樹時只需要對整棵樹進(jìn)行驗證，而Merkle 山脈是非完美二叉樹時，需要對多個數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找驗證，所以驗證時間比Merkle 山脈是一個完美二叉樹時的驗證時間長。

4 結(jié)語

針對物聯(lián)網(wǎng)系統(tǒng)中數(shù)據(jù)量大、處理速度快、輕量級節(jié)點(diǎn)數(shù)量多等特點(diǎn)，以及基于區(qū)塊鏈的溯源系統(tǒng)中輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)驗證困難、資源浪費(fèi)等問題，本文提出一種基于Merkle山脈的物聯(lián)網(wǎng)數(shù)據(jù)溯源方法MMRBCV。將IPFS 作為系統(tǒng)的數(shù)據(jù)層存儲數(shù)據(jù)，實現(xiàn)鏈上鏈下存儲，緩解區(qū)塊鏈面向物聯(lián)網(wǎng)海量數(shù)據(jù)時的存儲壓力；雙鏈結(jié)構(gòu)實現(xiàn)數(shù)據(jù)安全存儲；基于Merkle 山脈結(jié)構(gòu)設(shè)計適用于物聯(lián)網(wǎng)系統(tǒng)的區(qū)塊結(jié)構(gòu)，減少輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)對溯源數(shù)據(jù)驗證時下載的數(shù)據(jù)量和驗證時間，提高驗證效率。Merkle 山脈一定程度上可以節(jié)省輕量級物聯(lián)網(wǎng)節(jié)點(diǎn)資源，提高驗證效率；但引入新的數(shù)據(jù)結(jié)構(gòu)，區(qū)塊內(nèi)容增多，加重了網(wǎng)絡(luò)中全節(jié)點(diǎn)的存儲壓力，在未來工作中，將考慮存儲性能方面的問題。