李 皓，樂 鵬，姜良存，張明達(dá)，梁哲恒

1. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079； 2. 湖北大學(xué)資源環(huán)境學(xué)院, 湖北 武漢 430062； 3. 廣東南方數(shù)碼科技股份有限公司，廣東 廣州 510665

在空間基礎(chǔ)設(shè)施背景下，地理數(shù)據(jù)的生產(chǎn)、應(yīng)用過程逐漸由傳統(tǒng)集中式向分布式協(xié)作方向發(fā)展。在集中式的平臺環(huán)境下，數(shù)據(jù)產(chǎn)品嚴(yán)格按照算法處理和工作流等流程生成，具有較高的可信性[1]。而分布式環(huán)境下，數(shù)據(jù)來源多樣、質(zhì)量各異，未經(jīng)質(zhì)檢的數(shù)據(jù)被廣泛而頻繁地處理、應(yīng)用和共享，數(shù)據(jù)產(chǎn)品的質(zhì)量具有很大不確定性。地理數(shù)據(jù)產(chǎn)品可能來源于專業(yè)測繪數(shù)據(jù)、眾源地理數(shù)據(jù)或自發(fā)地理信息(VGI)等[2-3]，難以評估數(shù)據(jù)是否可用可靠，因此通過溯源信息對地理數(shù)據(jù)產(chǎn)品進(jìn)行可信評價(jià)尤為重要[4-7]。溯源信息記錄了地理數(shù)據(jù)的來源、變動和數(shù)據(jù)提供者等信息，為數(shù)據(jù)產(chǎn)品評價(jià)提供參考依據(jù)。對于地理數(shù)據(jù)溯源的研究，國內(nèi)外學(xué)者已開展了較多關(guān)于溯源模型、追蹤方法、溯源信息組織等方面的研究[1,4-6,8-12]，但尚缺乏對溯源信息本身的可靠和可信性研究。在分布式協(xié)作環(huán)境下，對于地理數(shù)據(jù)產(chǎn)品的溯源信息同樣存在著可靠性保證問題，在數(shù)據(jù)產(chǎn)品的共享、分發(fā)和交換中存在元數(shù)據(jù)的篡改風(fēng)險(xiǎn)。究其原因，在于地理數(shù)據(jù)共享時(shí)缺乏可信的溯源技術(shù)支持。特別在數(shù)據(jù)產(chǎn)品資產(chǎn)化的趨勢下[13]，對數(shù)據(jù)權(quán)利人、時(shí)間戳等元數(shù)據(jù)進(jìn)行偽造篡改等行為嚴(yán)重影響了數(shù)據(jù)評價(jià)。因此，可信的溯源信息存儲管理是地理數(shù)據(jù)溯源重要的基礎(chǔ)和保障[14]。

近年來，區(qū)塊鏈技術(shù)快速發(fā)展，其所具有的去中心化、不可篡改、可信透明的特點(diǎn)為溯源信息可靠可信的存儲管理提供了新的解決思路。區(qū)塊鏈?zhǔn)且环N多方共同參與和維護(hù)的去中心化數(shù)據(jù)庫，也是一種融合了加密算法、共識機(jī)制、智能合約等模塊的新型分布式賬本技術(shù)[15-16]。目前已有部分學(xué)者將區(qū)塊鏈技術(shù)應(yīng)用于數(shù)據(jù)溯源領(lǐng)域[17-22]。文獻(xiàn)[17]利用智能合約和OPM模型(open provenance model)進(jìn)行了安全捕獲溯源信息和溯源驗(yàn)證的試驗(yàn)。文獻(xiàn)[19]基于區(qū)塊鏈構(gòu)建了一個(gè)分布式系統(tǒng)用于管理溯源元數(shù)據(jù)以及設(shè)置數(shù)據(jù)訪問權(quán)限。文獻(xiàn)[20]提出了一種云環(huán)境下基于區(qū)塊鏈的數(shù)據(jù)溯源架構(gòu)，用區(qū)塊鏈存儲溯源信息來提供云文件的防篡改安全特性。

上述對區(qū)塊鏈溯源的研究均是面向通用的溯源場景。借鑒相似的思路，區(qū)塊鏈同樣能夠在地理數(shù)據(jù)的可信溯源方面產(chǎn)生重要價(jià)值，為地理信息數(shù)據(jù)的分發(fā)、共享和追溯提供可信技術(shù)支持。然而，在地理信息科學(xué)領(lǐng)域，特別是VGI場景下，地理數(shù)據(jù)的生產(chǎn)和更新速度快，產(chǎn)生的溯源信息量大，且溯源信息的記錄往往發(fā)生在不同粒度層級上[10]。因此，本文以矢量數(shù)據(jù)為研究對象，提出一種利用MPT樹對矢量溯源信息進(jìn)行鏈上存儲組織的方法，并設(shè)計(jì)了基于該存儲結(jié)構(gòu)的溯源可信驗(yàn)證算法，實(shí)現(xiàn)了對矢量溯源信息高效的溯源驗(yàn)證。

1 矢量數(shù)據(jù)溯源

1.1 矢量數(shù)據(jù)溯源模型研究現(xiàn)狀

矢量數(shù)據(jù)溯源記錄了矢量數(shù)據(jù)生產(chǎn)、變更所涉及的數(shù)據(jù)實(shí)體、活動、個(gè)人或組織等相關(guān)信息[1]?，F(xiàn)有的研究已從矢量數(shù)據(jù)處理類型和溯源性能等方面，對矢量數(shù)據(jù)溯源提出了不同粒度劃分的需求[1,4,7,10,23]。例如文獻(xiàn)[10]分析了從數(shù)據(jù)集、要素、屬性3個(gè)粒度級別進(jìn)行矢量數(shù)據(jù)溯源的必要性。具體而言，矢量數(shù)據(jù)集級別溯源描述了受到相同影響的多個(gè)要素的溯源信息。要素溯源用于描述特定要素的變更信息。而屬性溯源可分為幾何屬性和非幾何屬性的溯源，分別用于描述要素的幾何屬性和非幾何屬性上的變化?？傮w而言，矢量溯源記錄在粗粒度上記錄細(xì)粒度級別的共有信息，而在細(xì)粒度級別記錄更詳細(xì)的溯源信息，從而減少溯源信息的冗余和重復(fù)性。

溯源模型是溯源信息共享和互操作的基礎(chǔ)。PROV是W3C數(shù)據(jù)溯源工作組在2013年推出一種通用的數(shù)據(jù)溯源模型[24]，其核心結(jié)構(gòu)包含3種類型，分別為實(shí)體(entity)、活動(activity)以及代理(agent)，通過3種核心類型之間的關(guān)系來描述溯源信息。實(shí)體可以是任何形式存在的事物，包括客觀世界的地理實(shí)體和數(shù)字世界的地理數(shù)據(jù)(如所有粒度級別的數(shù)據(jù)源或輸出結(jié)果)?；顒邮亲饔糜趯?shí)體的行為，例如軌跡數(shù)據(jù)的繪制操作，活動內(nèi)容包括了活動類型、活動時(shí)間等。代理是對實(shí)體、行為負(fù)責(zé)的對象，可以是人或組織，代理內(nèi)容包括代理的名稱及社會屬性信息等。文獻(xiàn)[10]分析了PROV模型適合作為一種地理空間數(shù)據(jù)的溯源模型，并擴(kuò)展了矢量數(shù)據(jù)集(dataset)、要素(feature)、屬性(attribute)3種類型實(shí)體。屬性被作為一種實(shí)體類型，可分為幾何屬性(geometry feature)和非幾何屬性(property)。擴(kuò)展的PROV溯源模型如圖1所示。在本文后續(xù)的工作中將基于該擴(kuò)展的PROV溯源模型對矢量溯源信息進(jìn)行記錄。

1.2 矢量數(shù)據(jù)溯源案例

本文通過一項(xiàng)矢量數(shù)據(jù)合并的案例來展示不同粒度的矢量溯源信息的記錄細(xì)節(jié)及特征。該案例的數(shù)據(jù)來源包括一份專業(yè)測繪機(jī)構(gòu)繪制的數(shù)據(jù)(圖2(a))作為參考數(shù)據(jù)源，以及一份從Open StreetMap(OSM)下載的不同時(shí)相的相同區(qū)域的數(shù)據(jù) (圖2(b)) 作為待匹配數(shù)據(jù)源。通過特定的匹配算法合并最終生成一個(gè)數(shù)據(jù)結(jié)果(圖2(c))。擴(kuò)展的PROV溯源模型對合并處理過程中的3種粒度的溯源信息進(jìn)行記錄。溯源信息的捕獲參考了文獻(xiàn)[23]中提出的一種捕獲流程。該流程在矢量數(shù)據(jù)操作流程中擴(kuò)展了數(shù)據(jù)集和要素的溯源捕獲模塊。數(shù)據(jù)合并完成后，用戶若想了解合并結(jié)果來自哪些數(shù)據(jù)源，甚至某一矢量要素或其屬性信息來自哪個(gè)數(shù)據(jù)源，需要在合并時(shí)捕獲不同級別上的來源信息。在粗粒度級別，捕獲模塊記錄數(shù)據(jù)集級別的溯源信息，包括數(shù)據(jù)源、匹配算法、執(zhí)行參數(shù)、處理時(shí)間和執(zhí)行者等信息；在細(xì)粒度級別上，如果某一要素完全來自一個(gè)數(shù)據(jù)源，則可記錄至要素級別上的溯源信息，如果該要素保留了不同數(shù)據(jù)源的屬性信息，則需要記錄屬性級別上的溯源信息，其中對應(yīng)的活動類型包括了屬性的保留、新增和更新等。因此在合并處理完成后，溯源捕獲將在3種粒度層級上記錄豐富的溯源信息?？紤]到矢量數(shù)據(jù)集可能包含了大量的要素及要素屬性，單次的矢量數(shù)據(jù)操作(合并、更新等)便可能產(chǎn)生大量的要素、屬性級別上的溯源信息。

圖2 矢量數(shù)據(jù)合并的案例Fig.2 An example of vector data merging

2 基于區(qū)塊鏈的矢量數(shù)據(jù)溯源挑戰(zhàn)

區(qū)塊鏈?zhǔn)且环N多方共同參與和維護(hù)的去中心化數(shù)據(jù)庫，由帶有時(shí)間戳的區(qū)塊組成，每一區(qū)塊引用前一區(qū)塊的加密散列值，并依此連接成鏈狀結(jié)構(gòu)。在區(qū)塊鏈中單個(gè)區(qū)塊是存儲數(shù)據(jù)的基本單元。區(qū)塊由區(qū)塊頭和區(qū)塊體兩部分組成。區(qū)塊頭中主要包含父區(qū)塊散列值、時(shí)間戳、區(qū)塊高度、難度值、證明值以及存儲樹的根哈希值(tree root hash)。區(qū)塊體是區(qū)塊鏈中存儲數(shù)據(jù)記錄的位置，通常以樹形結(jié)構(gòu)組織，是區(qū)塊鏈中重要的數(shù)據(jù)結(jié)構(gòu)。梅克爾(Merkle)樹結(jié)構(gòu)[25]是最常見的一種鏈上信息存儲結(jié)構(gòu)，例如經(jīng)典的比特幣系統(tǒng)[26]采用了二叉Merkle樹結(jié)構(gòu)來組織一個(gè)區(qū)塊內(nèi)所有的交易信息，其葉子節(jié)點(diǎn)的值為交易信息的散列值，通過逐層合并計(jì)算得到整棵樹以及根哈希值。區(qū)塊體采用Merkle樹等樹形結(jié)構(gòu)的作用在于驗(yàn)證過程中不需要下載整棵樹，而是通過驗(yàn)證路徑(tree path)即可完成對信息的驗(yàn)證，驗(yàn)證路徑為從該節(jié)點(diǎn)出發(fā)達(dá)到根節(jié)點(diǎn)所經(jīng)過的路徑。區(qū)塊鏈的這種可信驗(yàn)證機(jī)制為鏈上的溯源信息提供了防篡改、可信任的安全特性。然而在地理數(shù)據(jù)場景中，由于矢量溯源記錄的特征，直接采用Merkle樹結(jié)構(gòu)面臨著如下挑戰(zhàn)：

(1) 由于矢量溯源記錄信息量豐富，若將溯源信息直接記錄到區(qū)塊鏈，必然造成區(qū)塊鏈存儲壓力，并進(jìn)一步對區(qū)塊鏈網(wǎng)絡(luò)中賬本同步的效率造成挑戰(zhàn)。

(2) 在地理協(xié)作過程中，地理數(shù)據(jù)更新頻繁、不確定性高、溯源數(shù)據(jù)量大，單個(gè)區(qū)塊內(nèi)存入大量溯源信息會造成Merkle樹的規(guī)模增大，這將對溯源信息的查詢和驗(yàn)證性能形成挑戰(zhàn)。

為應(yīng)對挑戰(zhàn)(1)，本文的溯源區(qū)塊鏈采用鏈上鏈下的存儲模式，即鏈上只存儲溯源條目的散列值，而完整的溯源信息存儲在鏈下的本地溯源數(shù)據(jù)庫。這里的溯源條目為鏈下溯源信息經(jīng)過溯源模型生成的單元。溯源區(qū)塊鏈將溯源條目進(jìn)行MD5 Hash算法得到散列值，并在區(qū)塊體中對散列值進(jìn)行存儲組織。該散列值與溯源條目原始信息具有對應(yīng)的映射關(guān)系，同時(shí)鏈上存儲散列值減小了區(qū)塊鏈的存儲壓力。為應(yīng)對挑戰(zhàn)(2)，本文采用基于MPT樹的多粒度矢量溯源信息鏈上存儲組織方法，根據(jù)溯源驗(yàn)證算法的流程對溯源驗(yàn)證性能進(jìn)行對比試驗(yàn)。

3 矢量數(shù)據(jù)溯源區(qū)塊鏈設(shè)計(jì)

3.1 溯源鏈設(shè)計(jì)要求

基于溯源模型需求分析及上述區(qū)塊鏈挑戰(zhàn)分析，著重考慮矢量溯源信息的多粒度層級、數(shù)據(jù)量大等特性，本文歸納矢量數(shù)據(jù)溯源信息的鏈上存儲結(jié)構(gòu)應(yīng)該盡可能滿足以下3個(gè)條件：

(1) 在分布式協(xié)作的環(huán)境下，假設(shè)系統(tǒng)環(huán)境對溯源記錄具有篡改風(fēng)險(xiǎn)，溯源信息存儲結(jié)構(gòu)應(yīng)具有溯源信息的可查詢和可驗(yàn)證的特性。

(2) 提供多粒度、可伸縮性的溯源查詢請求，以滿足用戶不同粒度層級(矢量數(shù)據(jù)集、矢量要素、要素屬性)的溯源查詢。

(3) 各溯源粒度層級間保持關(guān)聯(lián)關(guān)系，同一數(shù)據(jù)集下的要素溯源信息與對應(yīng)數(shù)據(jù)集的溯源信息存在關(guān)聯(lián)性，以增強(qiáng)溯源查詢驗(yàn)證的能力。

3.2 溯源信息的鏈上存儲結(jié)構(gòu)

本文設(shè)計(jì)了一種利用MPT樹結(jié)構(gòu)對不同粒度的矢量溯源信息進(jìn)行鏈上存儲和組織的方法。MPT樹是以太坊賬戶信息和交易信息的存儲結(jié)構(gòu)，結(jié)合了Merkle樹和Patricia前綴樹的特點(diǎn)，既具有Merkle樹可驗(yàn)證的特點(diǎn)，也具有Patricia樹節(jié)點(diǎn)間共享前綴的特點(diǎn)。MPT樹包含以下3種類型節(jié)點(diǎn)，分別是葉子結(jié)點(diǎn)(leaf node)、前綴節(jié)點(diǎn)(prefix node)、分支節(jié)點(diǎn)(branch node)。

(1) 葉子節(jié)點(diǎn)為樹型結(jié)構(gòu)中的最底層存儲節(jié)點(diǎn)，存儲了編碼段Key和溯源條目散列值Val。Key由地理數(shù)據(jù)統(tǒng)一資源標(biāo)志符(URI)經(jīng)特殊編碼和處理得到。葉子節(jié)點(diǎn)存儲的Val也作為節(jié)點(diǎn)散列值，被用于后續(xù)的真實(shí)性驗(yàn)證。

(2) 前綴節(jié)點(diǎn)壓縮了不同編碼的相同前綴，存儲了壓縮編碼段Key和節(jié)點(diǎn)散列值hash。

(3) 分支節(jié)點(diǎn)為擁有超過1個(gè)孩子節(jié)點(diǎn)以上的非葉子節(jié)點(diǎn)，由指向孩子節(jié)點(diǎn)的索引ChildrenNode、所有孩子節(jié)點(diǎn)Val值拼接后的節(jié)點(diǎn)散列值hash、溯源條目散列值Val構(gòu)成。其中，ChildrenNode是一個(gè)長度為16的數(shù)組，范圍是十六進(jìn)制表示的0至f。

3.3 矢量溯源信息的上鏈方法

矢量數(shù)據(jù)溯源鏈通過上述MPT樹結(jié)構(gòu)對矢量溯源信息進(jìn)行鏈上的存儲和組織，將此步驟定義為溯源信息的上鏈過程。根據(jù)擴(kuò)展的PROV模型，溯源的實(shí)體具有不同的粒度級別。不同粒度實(shí)體的URI需符合相應(yīng)規(guī)范，對于細(xì)粒度實(shí)體應(yīng)將其所在粗粒度實(shí)體的URI作為自身URI的前綴部分，例如數(shù)據(jù)集A對應(yīng)的URI為“http:∥example.com/resource/dataset_A”，則數(shù)據(jù)集A中要素B對應(yīng)的URI為“http:∥example.com/resource/dataset_A/feature_B”。上鏈過程主要依據(jù)溯源實(shí)體的URI將溯源條目的散列值插入到MPT樹的特定位置和深度。具體的上鏈步驟如下：

(1) 對溯源實(shí)體的URI進(jìn)行原生字符向十六進(jìn)制(Raw-Hex)編碼轉(zhuǎn)換。首先Raw編碼操作，對原始的URI逐個(gè)分隔為單個(gè)字符，并轉(zhuǎn)換成ASCII碼值。接著Hex編碼操作，對轉(zhuǎn)換得到的ASCII碼值除以16取除數(shù)和余數(shù)依次作為新編碼的結(jié)果，目的是將編碼結(jié)果的數(shù)值控制在16以內(nèi)。由URI原生字符經(jīng)過Raw-Hex編碼得到的結(jié)果記為對應(yīng)溯源條目的初始編碼段。例如數(shù)據(jù)集A的URI為“http:∥example.com/resource/dataset_A”，則其初始編碼段表示為(僅展示前后6位)[6,8,7,4,7,4,…,7,4,5,f,4,1]。

(2) 生成初始樹節(jié)點(diǎn)。選取某一粗粒度的溯源條目插入MPT樹中，依據(jù)樹節(jié)點(diǎn)類型的定義，第1個(gè)樹節(jié)點(diǎn)也是最底層的存儲節(jié)點(diǎn)，即為葉子節(jié)點(diǎn)。

(3) 繼續(xù)插入粗粒度溯源條目。將當(dāng)前待插入的溯源條目定義為新插入的節(jié)點(diǎn)。根據(jù)新插入節(jié)點(diǎn)的初始編碼段尋找當(dāng)前樹型結(jié)構(gòu)中的具有最長相同前綴的樹節(jié)點(diǎn)，將剩余編碼段定義為初始編碼段減去當(dāng)前樹型中相同前綴后所剩余的編碼部分。若尋找到的樹節(jié)點(diǎn)為分支節(jié)點(diǎn)，則將當(dāng)前溯源條目作為一個(gè)葉子節(jié)點(diǎn)插入到分支節(jié)點(diǎn)對應(yīng)的孩子節(jié)點(diǎn)位置。若尋找到的樹節(jié)點(diǎn)為葉子節(jié)點(diǎn)或前綴節(jié)點(diǎn)，判斷該樹節(jié)點(diǎn)與新插入節(jié)點(diǎn)的剩余編碼段是否具有相同前綴，若有則新生成一個(gè)前綴節(jié)點(diǎn)，并將該樹節(jié)點(diǎn)變更為分支節(jié)點(diǎn)，原樹節(jié)點(diǎn)與新插入節(jié)點(diǎn)作為分支節(jié)點(diǎn)的兩個(gè)孩子節(jié)點(diǎn)插入。若兩者無相同前綴，則直接生成分支節(jié)點(diǎn)，原樹節(jié)點(diǎn)與新插入節(jié)點(diǎn)作為兩個(gè)孩子節(jié)點(diǎn)插入。

(4) 重復(fù)步驟(3)，直至所有的粗粒度溯源條目插入到MPT樹中。

(5) 插入更細(xì)粒度級別的溯源條目。例如溯源條目對應(yīng)實(shí)體為數(shù)據(jù)集A下要素B，要素B的URI為“http:∥example.com/resource/dataset_A/feature_B”,則其初始編碼段表示為(僅展現(xiàn)部分編碼)[6,8,7,4,7,4,…,7,4,5,f,4,1,…,6,5,5,f,4,2]。

(6) 同理粗粒度溯源條目的插入，直至完成所有細(xì)粒度溯源條目的插入。

(7) 逐層計(jì)算節(jié)點(diǎn)散列值，最后得到整棵樹的tree root hash，將tree root hash存入?yún)^(qū)塊頭內(nèi)。

上述上鏈方法根據(jù)實(shí)體URI確定了不同粒度溯源條目在MPT樹中的位置，并形成一種粗細(xì)粒度間的包含關(guān)系，即細(xì)粒度的溯源條目存儲于所屬粗粒度溯源條目所在的子樹中?；诒?的用例數(shù)據(jù)在圖3中展示了一個(gè)MPT樹的示例,樹狀結(jié)構(gòu)的不同深度層次分別對應(yīng)矢量數(shù)據(jù)集、矢量要素和要素屬性3種粒度的溯源條目存儲位置。

表1 溯源信息的用例數(shù)據(jù)

圖3 不同粒度溯源條目在MPT樹中存儲位置的一個(gè)示例Fig.3 An examples of storage locations of provenance entries with different granularities in the MPT tree

4 矢量數(shù)據(jù)溯源驗(yàn)證

MPT樹結(jié)構(gòu)保留了Merkle樹的驗(yàn)證原則，通過驗(yàn)證算法對溯源信息真實(shí)性進(jìn)行判斷。溯源驗(yàn)證包括溯源查詢和真實(shí)性驗(yàn)證兩部分。首先進(jìn)行溯源查詢，通過遍歷樹形結(jié)構(gòu)檢索到目標(biāo)溯源條目的存儲樹節(jié)點(diǎn)位置；第2步是進(jìn)行真實(shí)性驗(yàn)證，通過溯源條目的存儲位置計(jì)算得到一條驗(yàn)證路徑。由于無法確定分布式環(huán)境下驗(yàn)證路徑的響應(yīng)是否存在欺詐，因此需利用驗(yàn)證路徑計(jì)算得到一個(gè)最終的哈希值，并與區(qū)塊頭中的根哈希進(jìn)行比較，若相同則證明溯源條目可信。

矢量溯源信息驗(yàn)證的一個(gè)特征在于溯源驗(yàn)證請求需要同時(shí)驗(yàn)證粗粒度溯源信息及大量細(xì)粒度溯源信息。這對溯源驗(yàn)證性能造成挑戰(zhàn)。為方便理解，本文將驗(yàn)證矢量數(shù)據(jù)集及其包含的要素、屬性級別的溯源信息的過程定義為矢量數(shù)據(jù)綜合溯源驗(yàn)證。本文提出的溯源信息鏈上存儲結(jié)構(gòu)支持綜合溯源驗(yàn)證能力。在驗(yàn)證過程中，對粗粒度(數(shù)據(jù)集級別)溯源條目驗(yàn)證可信后，可依據(jù)粗粒度的驗(yàn)證路徑快速定位到所包含的細(xì)粒度(矢量要素級別、要素屬性級別)溯源條目所在的樹節(jié)點(diǎn)位置，并在驗(yàn)證子樹中完成細(xì)粒度的溯源驗(yàn)證。圖4以一個(gè)簡化的MPT樹展示了矢量數(shù)據(jù)綜合溯源驗(yàn)證。圖中Hash78所在的樹節(jié)點(diǎn)存儲了要素溯源條目,其父節(jié)點(diǎn)存儲了數(shù)據(jù)集溯源條目，在數(shù)據(jù)集溯源條目驗(yàn)證通過后，只需在驗(yàn)證子樹中完成更細(xì)粒度的溯源驗(yàn)證即可，不需要重新對整棵樹進(jìn)行遍歷計(jì)算。具體驗(yàn)證算法流程如圖5所示。

圖4 綜合溯源驗(yàn)證示意圖Fig.4 Comprehensive provenance verification diagram

圖5 矢量數(shù)據(jù)綜合溯源驗(yàn)證流程Fig.5 Vector data comprehensive provenance verification flowchart

5 試驗(yàn)與分析

5.1 試驗(yàn)環(huán)境與準(zhǔn)備

矢量溯源區(qū)塊鏈系統(tǒng)的試驗(yàn)環(huán)境采用分布式集群架構(gòu)，試驗(yàn)集群由5臺服務(wù)器組成，服務(wù)器系統(tǒng)版本為Ubuntu16.04.6，配置為雙核、4 GB，且保證服務(wù)器之間可互相通信，如圖6所示。每個(gè)服務(wù)器配置PostgreSQL 9.3數(shù)據(jù)庫用于存儲完整的溯源信息。網(wǎng)絡(luò)中所有服務(wù)器節(jié)點(diǎn)共同維護(hù)區(qū)塊鏈賬本，用戶可通過任意服務(wù)器節(jié)點(diǎn)連接的客戶端進(jìn)行溯源查詢與驗(yàn)證。

圖6 矢量溯源區(qū)塊鏈試驗(yàn)測試環(huán)境Fig.6 Experimental test environment of vector data provenance blockchain

在溯源信息上鏈準(zhǔn)備階段，試驗(yàn)在地理矢量數(shù)據(jù)處理平臺進(jìn)行了多次矢量數(shù)據(jù)合并操作，并通過收集、監(jiān)聽模塊對產(chǎn)生的溯源信息進(jìn)行捕獲上鏈。矢量數(shù)據(jù)合并所使用的多份參考數(shù)據(jù)源來自專業(yè)測繪機(jī)構(gòu)繪制的建筑物矢量數(shù)據(jù)，匹配數(shù)據(jù)源來自O(shè)SM中不同時(shí)相、相同區(qū)域的矢量數(shù)據(jù)。其中數(shù)據(jù)源中矢量數(shù)據(jù)集包含的要素?cái)?shù)量在2至100條，每要素包含的屬性數(shù)量在2至20項(xiàng)。為方便對比溯源驗(yàn)證性能，試驗(yàn)基于原比特幣機(jī)制中固定區(qū)塊容量大小的出塊策略[27]，設(shè)置了包含500、1000、1500、2000、2500、3000條溯源條目作為區(qū)塊大小分級，即溯源信息按照區(qū)塊大小分級的數(shù)量上鏈至每區(qū)塊中。在試驗(yàn)測試中，本文忽略了搜尋溯源信息所在區(qū)塊高度的耗時(shí)，而重點(diǎn)測試基于通用的二叉Merkle樹與本文提出的基于MPT的鏈上組織結(jié)構(gòu)的溯源驗(yàn)證性能。

5.2 原型系統(tǒng)展示

為幫助理解矢量數(shù)據(jù)溯源鏈的使用與運(yùn)行，本文開發(fā)了基于區(qū)塊鏈的矢量數(shù)據(jù)溯源驗(yàn)證原型系統(tǒng)，原型系統(tǒng)可作為區(qū)塊鏈節(jié)點(diǎn)的交互客戶端，系統(tǒng)界面如圖7所示。用戶可以查詢合并案例中的數(shù)據(jù)結(jié)果及其溯源信息，系統(tǒng)界面的下邊欄展示了從本地溯源數(shù)據(jù)庫中查詢到的所有溯源信息。進(jìn)一步，用戶通過原型系統(tǒng)向區(qū)塊鏈網(wǎng)絡(luò)發(fā)起驗(yàn)證請求，利用區(qū)塊鏈對查詢到的溯源信息進(jìn)行真實(shí)性驗(yàn)證，如系統(tǒng)界面中紅線框內(nèi)即為驗(yàn)證結(jié)果。當(dāng)結(jié)果返回“True”時(shí)表示溯源信息真實(shí)可靠，未被篡改；當(dāng)驗(yàn)證結(jié)果為“False”時(shí)表明該條溯源信息已被改動。

圖7 基于區(qū)塊鏈的矢量數(shù)據(jù)溯源驗(yàn)證系統(tǒng)Fig.7 Vector data provenance and verification system based on blockchain

5.3 溯源驗(yàn)證耗時(shí)對比

以下對比測試基于二叉Merkle樹和MPT樹的溯源驗(yàn)證耗時(shí)。首先對比在不同區(qū)塊大小分級下兩種鏈上組織結(jié)構(gòu)的單次溯源驗(yàn)證耗時(shí)。選取100次溯源驗(yàn)證耗時(shí)的平均值進(jìn)行對比(圖8)，不難發(fā)現(xiàn)單個(gè)溯源條目的響應(yīng)耗時(shí)均在秒級。從整體來看，溯源驗(yàn)證耗時(shí)都隨著區(qū)塊大小增大而增加，二叉Merkle樹下的溯源驗(yàn)證耗時(shí)要大于MPT構(gòu)建的3種粒度的溯源驗(yàn)證耗時(shí)。當(dāng)溯源查詢驗(yàn)證所需遍歷的樹節(jié)點(diǎn)數(shù)目越少，驗(yàn)證耗時(shí)與開銷也相應(yīng)減少。本文進(jìn)而對比了不同區(qū)塊大小下樹節(jié)點(diǎn)的數(shù)量(圖9)，可以看出MPT樹相比二叉Merkle樹大約可以減少28.8%～37.5%的樹節(jié)點(diǎn)的冗余。在3種粒度的溯源驗(yàn)證耗時(shí)對比中，數(shù)據(jù)集級別的驗(yàn)證耗時(shí)最少，原因是粗粒度的溯源條目平均存儲位置相比細(xì)粒度的溯源條目更加靠近根節(jié)點(diǎn)，驗(yàn)證路徑更短，其單次溯源響應(yīng)的耗時(shí)也相對更短。

圖8 二叉Merkle樹與MPT樹的溯源耗時(shí)對比Fig.8 Time-consuming comparison of provenance between binary trees and MPT

圖9 二叉Merkle樹與MPT樹節(jié)點(diǎn)數(shù)量對比Fig.9 Binary tree and MPT node number comparison

本文進(jìn)一步測試了矢量數(shù)據(jù)綜合溯源驗(yàn)證的試驗(yàn)。在實(shí)際場景中，不同的綜合溯源驗(yàn)證對象所需驗(yàn)證的溯源條目數(shù)量往往相差較大，對溯源驗(yàn)證耗時(shí)影響也較大。因此本次試驗(yàn)在不同區(qū)塊大小分級下，對不同的矢量數(shù)據(jù)合并案例生成的數(shù)據(jù)集實(shí)體進(jìn)行100次綜合溯源驗(yàn)證，圖10顯示了二叉Merkle樹與MPT樹的驗(yàn)證耗時(shí)結(jié)果。從試驗(yàn)結(jié)果來看，二叉Merkle樹綜合溯源驗(yàn)證的耗時(shí)隨區(qū)塊大小增大而快速增加，且具有較大的浮動，而基于MPT樹的綜合溯源驗(yàn)證基本保持了較低的驗(yàn)證耗時(shí)，且更加穩(wěn)定。經(jīng)對比，不同區(qū)塊大小分級下二叉Merkle樹綜合溯源驗(yàn)證的平均耗時(shí)約為MPT樹的2.29～19.95倍，表明本文提出的基于MPT的鏈上存儲組織方法具有更高效的溯源驗(yàn)證性能，更加適應(yīng)實(shí)際場景中的矢量數(shù)據(jù)綜合溯源驗(yàn)證。

圖10 二叉Merkle樹與MPT樹的矢量數(shù)據(jù)綜合溯源驗(yàn)證耗時(shí)對比Fig.10 Time-consuming comparison of comprehensive provenance between binary trees and MPT

6 結(jié) 論

針對矢量溯源信息的可靠性問題，本文將區(qū)塊鏈技術(shù)應(yīng)用到了矢量數(shù)據(jù)溯源領(lǐng)域，探索了基于區(qū)塊鏈的矢量溯源信息鏈上存儲組織和驗(yàn)證方法。首先分析了基于區(qū)塊鏈的矢量數(shù)據(jù)溯源存在的挑戰(zhàn)，接著提出了矢量溯源區(qū)塊鏈的設(shè)計(jì)要求。本文提出了一種利用MPT樹對不同層級的矢量溯源信息進(jìn)行鏈上存儲組織的方法，并設(shè)計(jì)了相應(yīng)的溯源信息驗(yàn)證算法。試驗(yàn)表明，與通用的二叉Merkle樹相比，本文所提出的顧及矢量數(shù)據(jù)溯源粒度的鏈上存儲組織方法具有更高效的溯源驗(yàn)證性能，可基本滿足實(shí)際場景下的驗(yàn)證需求。

目前區(qū)塊鏈應(yīng)用于地理信息領(lǐng)域的研究剛剛起步。除了矢量數(shù)據(jù)溯源方向，在面向地理信息領(lǐng)域更為豐富的場景和數(shù)據(jù)源時(shí)，上鏈數(shù)據(jù)的范疇與接口標(biāo)準(zhǔn)需要進(jìn)行必要的約定和統(tǒng)一。同時(shí)考慮到區(qū)塊鏈政策因素，對于一些區(qū)塊鏈隱私保護(hù)、權(quán)益分配等都應(yīng)在相應(yīng)的政策監(jiān)管范圍下實(shí)施。因此，未來對于區(qū)塊鏈在地理信息領(lǐng)域的研究，也將從數(shù)據(jù)標(biāo)準(zhǔn)、技術(shù)研發(fā)、政策制定等多角度展開探討。