區(qū)塊鏈數(shù)據(jù)庫:一種可查詢且防篡改的數(shù)據(jù)庫*

焦 通,申德榮,聶鐵錚,寇 月,李曉華,于 戈

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,遼寧 沈陽 110169)

通訊作者:申德榮,E-mail:shendr@mail.neu.edu.cn

隨著比特幣、以太幣等一系列加密貨幣的興起,其底層的區(qū)塊鏈技術(shù)也受到了越來越廣泛的關(guān)注[1,2].比特幣最核心的意圖是為了實(shí)現(xiàn)去中心化,即:在沒有第三方信任機(jī)構(gòu)參與的情況下,實(shí)現(xiàn)兩個(gè)對(duì)等實(shí)體的數(shù)字貨幣交易.然而,現(xiàn)實(shí)世界中不可避免地存在很多自然中心,比如提供貸款的銀行、提供電信服務(wù)的電信運(yùn)營(yíng)商等.雖然我們可以把這些中心機(jī)構(gòu)當(dāng)作對(duì)等實(shí)體,將其與用戶的交易記錄到區(qū)塊鏈上,比如用比特幣去交話費(fèi),但是這種做法是不切實(shí)際的,因?yàn)檫@不利于機(jī)構(gòu)管理用戶數(shù)據(jù)(包括用戶的信用等級(jí)等).實(shí)際上,現(xiàn)有的中心機(jī)構(gòu)都是由自己管理其存儲(chǔ)用戶相關(guān)信息的數(shù)據(jù)庫,但是這種模式存在很多缺陷:(1)不同的數(shù)據(jù)庫可能存儲(chǔ)著相同的用戶基本身份信息,導(dǎo)致數(shù)據(jù)冗余度高;(2)不同的中心機(jī)構(gòu)各自管理自己的數(shù)據(jù),不利于機(jī)構(gòu)之間的數(shù)據(jù)共享;(3)每個(gè)數(shù)據(jù)庫大都由單一機(jī)構(gòu)中心化管理,使得用戶必須無條件信任該機(jī)構(gòu),存在中心化問題;(4)用戶不能夠獨(dú)立驗(yàn)證數(shù)據(jù)的正確性,如果數(shù)據(jù)被惡意篡改,用戶與機(jī)構(gòu)都無法察覺.不僅如此,在供應(yīng)鏈以及商品溯源等領(lǐng)域,也對(duì)數(shù)據(jù)可信性以及數(shù)據(jù)可回溯提出了新的要求.

而區(qū)塊鏈技術(shù)具有去中心化、防篡改以及可回溯的特性,為解決上述這些問題提供了可能.為此,我們提出了區(qū)塊鏈數(shù)據(jù)庫的概念,核心思想是:通過限制中心機(jī)構(gòu)對(duì)數(shù)據(jù)記錄的操作,來達(dá)到防篡改和去中心化的目的.該數(shù)據(jù)庫中有多條區(qū)塊鏈,每一條區(qū)塊鏈相當(dāng)于傳統(tǒng)數(shù)據(jù)庫中的一張表,所有的中心機(jī)構(gòu)充當(dāng)數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn),所有的存儲(chǔ)節(jié)點(diǎn)根據(jù)共識(shí)算法生成區(qū)塊鏈,所有節(jié)點(diǎn)(包括用戶)存儲(chǔ)區(qū)塊頭信息,可以由區(qū)塊頭信息檢索到記錄并驗(yàn)證記錄的正確性.我們希望有高效的共識(shí)算法來提高系統(tǒng)的吞吐率,并有高效的查詢算法實(shí)現(xiàn)在區(qū)塊鏈上檢索數(shù)據(jù).當(dāng)前,在共識(shí)算法上已經(jīng)有很多研究,例如POW[3,4],POS[5,6],PBFT[7].然而針對(duì)區(qū)塊鏈查詢的研究相對(duì)較少,而且現(xiàn)有的區(qū)塊鏈系統(tǒng)并不能兼顧數(shù)據(jù)回溯與數(shù)據(jù)查詢.在比特幣中可以根據(jù)每一筆交易回溯前一筆交易,但是存在的問題是交易本身不易檢索.在以太坊中是狀態(tài)樹+交易樹,狀態(tài)樹存儲(chǔ)的是用戶賬號(hào)信息,狀態(tài)樹支持檢索,可以根據(jù)狀態(tài)樹查詢用戶當(dāng)前余額,但是狀態(tài)樹本身不記錄歷史信息,不能對(duì)狀態(tài)進(jìn)行數(shù)據(jù)回溯,而且狀態(tài)樹不直接關(guān)聯(lián)交易,同樣無法有效對(duì)交易進(jìn)行回溯.雖然已有一些研究利用同步技術(shù)將交易數(shù)據(jù)同步到傳統(tǒng)數(shù)據(jù)庫,根據(jù)各數(shù)據(jù)項(xiàng)建立索引,從而實(shí)現(xiàn)快速查詢,但是這種做法并不能保證索引的不可篡改,所以損失了區(qū)塊鏈不可篡改的特性.基于此,本文提出一種不可篡改的索引結(jié)構(gòu),兼顧數(shù)據(jù)查詢以及數(shù)據(jù)回溯.

本文首先提出了區(qū)塊鏈數(shù)據(jù)庫系統(tǒng)框架,將區(qū)塊鏈技術(shù)應(yīng)用于數(shù)據(jù)管理;其次,提出了一種基于哈希指針的不可篡改索引,根據(jù)該索引快速檢索區(qū)塊內(nèi)數(shù)據(jù),以此實(shí)現(xiàn)區(qū)塊鏈的查詢;最后,通過實(shí)驗(yàn)測(cè)試數(shù)據(jù)庫的讀寫性能,實(shí)驗(yàn)結(jié)果表明,本文提出的不可篡改索引在保證不可篡改的同時(shí)具有較好的讀寫性能.

1 相關(guān)工作

文獻(xiàn)[3]中,中本聰將數(shù)字簽名技術(shù)、P2P 技術(shù)、時(shí)間戳技術(shù)、Merkle 樹技術(shù)和工作量證明機(jī)制巧妙地結(jié)合起來,解決了雙花與女巫攻擊問題,實(shí)現(xiàn)了擁有去中心化、防篡改和數(shù)據(jù)可回溯等特性的數(shù)字貨幣系統(tǒng)——比特幣系統(tǒng).文獻(xiàn)[8]中,Buterin 等人對(duì)比特幣系統(tǒng)進(jìn)行擴(kuò)展,構(gòu)建了新一代智能合約和去中心化應(yīng)用平臺(tái)——以太坊.除了比特幣的功能之外,以太坊還有圖靈完備的合約語言,內(nèi)置的持久化狀態(tài)存儲(chǔ),具有可編程性,使開發(fā)者可以很快地在以太坊平臺(tái)上創(chuàng)建自己的區(qū)塊鏈應(yīng)用.這兩個(gè)應(yīng)用都是自下而上設(shè)計(jì)區(qū)塊鏈,有內(nèi)置代幣,比特幣主要應(yīng)用于貨幣,而以太坊的主要功能則是智能合約.

文獻(xiàn)[9]中,超級(jí)賬本則采用自上而下的設(shè)計(jì)方式,去除了內(nèi)置代幣,提出了商用區(qū)塊鏈框架.它采用了松耦合的設(shè)計(jì),將共識(shí)機(jī)制、身份驗(yàn)證等組件模塊化,使之在應(yīng)用過程中可以方便地根據(jù)應(yīng)用場(chǎng)景來選擇相應(yīng)的模塊,除此之外還采用了容器技術(shù),將智能合約放在docker 中運(yùn)行,從而使得智能合約可以用幾乎任意的高級(jí)語言來編寫.

比特幣、以太坊和超級(jí)賬本三大應(yīng)用平臺(tái)的主要功能是針對(duì)數(shù)字貨幣與智能合約,但是數(shù)據(jù)管理性能較弱,一些機(jī)構(gòu)發(fā)現(xiàn)了區(qū)塊鏈不可篡改、去中心化與數(shù)據(jù)可回溯特性,力圖將區(qū)塊鏈技術(shù)與傳統(tǒng)的數(shù)據(jù)庫技術(shù)相結(jié)合,提升數(shù)據(jù)管理的性能,同時(shí)兼顧區(qū)塊鏈去中心化、數(shù)據(jù)可回溯、防篡改的特性.

文獻(xiàn)[10]中,Dinh 等人受區(qū)塊鏈鏈?zhǔn)浇Y(jié)構(gòu)以及Git 版本控制的啟發(fā),為每個(gè)key創(chuàng)建設(shè)計(jì)了一個(gè)有向無環(huán)圖,圖中每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)key的某一歷史版本,節(jié)點(diǎn)的前驅(qū)后繼分別對(duì)應(yīng)其版本的前驅(qū)后繼,在保證高擴(kuò)展性和高吞吐率的同時(shí),實(shí)現(xiàn)了數(shù)據(jù)可共享與不可篡改的特性.文獻(xiàn)[11]中,BigchainDB 將區(qū)塊鏈技術(shù)與RethinkDB 相結(jié)合,在企業(yè)級(jí)分布式數(shù)據(jù)庫的基礎(chǔ)上添加區(qū)塊鏈不可篡改和去中心化等特性,提出了一種基于管程的一致性策略,提高了數(shù)據(jù)的安全性,同時(shí)解決了區(qū)塊鏈的數(shù)據(jù)存儲(chǔ)容量問題.文獻(xiàn)[12]提供了基于區(qū)塊鏈的加密存儲(chǔ)網(wǎng)絡(luò),通過將原始數(shù)據(jù)加密并簽名后,保存到P2P 文件系統(tǒng)中,用戶可以對(duì)數(shù)據(jù)的完整性進(jìn)行驗(yàn)證.文獻(xiàn)[13]中,Tuan 等人提出了一種區(qū)塊鏈測(cè)試框架,包括針對(duì)區(qū)塊鏈應(yīng)用的一致性算法、數(shù)據(jù)模型、執(zhí)行引擎和鏈上應(yīng)用的測(cè)試方法,并且分析了以太坊、超級(jí)賬本、Parity 以及UStore 的讀寫以及查詢能力,對(duì)于區(qū)塊鏈的設(shè)計(jì)以及瓶頸發(fā)現(xiàn)和解決帶來了極大的幫助.文獻(xiàn)[14]中,Tsai 等人總結(jié)了基于區(qū)塊鏈的應(yīng)用開發(fā)方法,給出了開發(fā)區(qū)塊鏈應(yīng)用時(shí)需要注意的關(guān)鍵問題,設(shè)計(jì)并實(shí)現(xiàn)了”北航鏈”.文獻(xiàn)[15]中,Li 等人提出了一種高效的檢索區(qū)塊鏈的方法,包括范圍查詢和Top-k查詢,有較好的靈活性.但是其解決方法是通過把區(qū)塊鏈數(shù)據(jù)以及k-v數(shù)據(jù)庫里面的數(shù)據(jù)同步到MongoDB 數(shù)據(jù)庫中,利用MongoDB 進(jìn)行查詢操作,沒有從根本上解決區(qū)塊鏈的查詢問題.為了將區(qū)塊鏈技術(shù)應(yīng)用于數(shù)據(jù)存儲(chǔ),ChainSQL[16]將數(shù)據(jù)庫操作日志存儲(chǔ)于區(qū)塊鏈中,將數(shù)據(jù)存儲(chǔ)于附屬關(guān)系型數(shù)據(jù)庫中,在底層支持SQLite3,MySQL,PostgreSQL 等關(guān)系數(shù)據(jù)庫,可以根據(jù)區(qū)塊鏈里的日志記錄將數(shù)據(jù)庫表恢復(fù)到任意時(shí)刻點(diǎn),但是其恢復(fù)粒度是以表為單位,不利于以交易為單位的數(shù)據(jù)溯源.

2 區(qū)塊鏈數(shù)據(jù)庫系統(tǒng)框架

通過結(jié)合區(qū)塊鏈和數(shù)據(jù)庫技術(shù),提出一種去中心化、防篡改同時(shí)支持查詢的區(qū)塊鏈數(shù)據(jù)庫框架.如圖1 所示,分4 層,具體如下.

· 存儲(chǔ)層:在最底部,為k-v數(shù)據(jù)庫,負(fù)責(zé)分布式存儲(chǔ)數(shù)據(jù),為每一個(gè)區(qū)塊鏈備份多個(gè)副本;

· 網(wǎng)絡(luò)層:是該框架的核心,負(fù)責(zé)節(jié)點(diǎn)間的數(shù)據(jù)傳輸以及根據(jù)共識(shí)協(xié)議確定區(qū)塊的先后順序.其中,節(jié)點(diǎn)由存儲(chǔ)節(jié)點(diǎn)以及用戶組成,每一機(jī)構(gòu)為一個(gè)存儲(chǔ)節(jié)點(diǎn),用于存儲(chǔ)本機(jī)構(gòu)的數(shù)據(jù)信息,可以是一個(gè)數(shù)據(jù)庫,也可以是多個(gè)數(shù)據(jù)庫.當(dāng)添加或者修改用戶相關(guān)的數(shù)據(jù)時(shí),需要由用戶和機(jī)構(gòu)共同簽名認(rèn)可;簽名后的數(shù)據(jù)由機(jī)構(gòu)封裝到區(qū)塊中,當(dāng)區(qū)塊大小達(dá)到某一閾值時(shí),將其打包發(fā)送給其他機(jī)構(gòu)進(jìn)行驗(yàn)證.機(jī)構(gòu)間根據(jù)共識(shí)算法驗(yàn)證區(qū)塊的正確性,并決定區(qū)塊的先后順序.將驗(yàn)證正確的區(qū)塊發(fā)送給存儲(chǔ)節(jié)點(diǎn)存儲(chǔ),將區(qū)塊頭廣播給所有節(jié)點(diǎn),包括用戶.在進(jìn)行查詢操作時(shí),用戶向存儲(chǔ)節(jié)點(diǎn)發(fā)送查詢請(qǐng)求,存儲(chǔ)節(jié)點(diǎn)會(huì)返回查詢到的記錄項(xiàng)以及查詢路徑,用戶根據(jù)查詢路徑以及區(qū)塊頭信息,可以驗(yàn)證查詢結(jié)果的正確性;

· 區(qū)塊鏈層:顯示的是區(qū)塊鏈的“世界狀態(tài)”,上層應(yīng)用可以據(jù)此對(duì)區(qū)塊鏈數(shù)據(jù)進(jìn)行查詢操作;

· 應(yīng)用層:是最上層,可以對(duì)查詢到的數(shù)據(jù)進(jìn)行進(jìn)一步的分析處理.

針對(duì)這一框架,本文重新定義了數(shù)據(jù)庫中的數(shù)據(jù)結(jié)構(gòu)以及數(shù)據(jù)操作,并提出了Merkle RBTree 索引,基于哈希指針構(gòu)建不可篡改的索引,在保證不可篡改的前提下實(shí)現(xiàn)高效查詢.系統(tǒng)中數(shù)據(jù)的操作定義如下.

· 增加記錄:數(shù)據(jù)在初次添加時(shí),數(shù)據(jù)擁有者指定可以進(jìn)行數(shù)據(jù)寫操作的公鑰,生成權(quán)限鎖定腳本,然后用自己的私鑰對(duì)該數(shù)據(jù)進(jìn)行簽名;

· 修改記錄:操作者用自己的私鑰對(duì)其父記錄進(jìn)行簽名,然后驗(yàn)證該簽名是否能夠解鎖父記錄的鎖定腳本,當(dāng)且只當(dāng)在解鎖鎖定腳本的情況下,才可以添加一條相同key值的記錄,以此實(shí)現(xiàn)對(duì)父記錄的修改.其中,權(quán)限鎖定腳本只有數(shù)據(jù)擁有者可以修改.需要說明的是,數(shù)據(jù)修改與數(shù)據(jù)防篡改并不沖突,本文中的防篡改指的是對(duì)應(yīng)版本的數(shù)據(jù)不可改且數(shù)據(jù)的更改歷史不可改,但是支持?jǐn)?shù)據(jù)從較老版本更新到新的版本;

· 查找記錄:所有的參與者都可以進(jìn)行查找操作,查找操作返回最新值為有效值,但是可以通過溯源操作查看該記錄的完整修改歷史;

· 刪除記錄:數(shù)據(jù)一旦添加便不可刪除,當(dāng)數(shù)據(jù)已經(jīng)被修改多次,處于非常古老的版本時(shí),為了節(jié)約磁盤空間,可以刪除該數(shù)據(jù)的具體信息,但是該數(shù)據(jù)的哈希值則需要永久保存.

Fig.1 Blockchain database system framework圖1 區(qū)塊鏈數(shù)據(jù)庫系統(tǒng)框架

3 區(qū)塊鏈?zhǔn)綌?shù)據(jù)模型

3.1 已有的區(qū)塊鏈系統(tǒng)模型

(1)數(shù)據(jù)結(jié)構(gòu)

為了能夠較好地理解區(qū)塊鏈的結(jié)構(gòu),我們給出了哈希指針的定義.一個(gè)數(shù)據(jù)項(xiàng)的哈希指針是指將該數(shù)據(jù)項(xiàng)的內(nèi)容做哈希操作后得到固定長(zhǎng)度的哈希值,同時(shí)以該哈希值為key,該數(shù)據(jù)項(xiàng)的內(nèi)容為value,將此k-v對(duì)存儲(chǔ)于k-v數(shù)據(jù)庫,則該key即為該數(shù)據(jù)項(xiàng)的哈希指針.

區(qū)塊鏈就是一個(gè)個(gè)的區(qū)塊根據(jù)哈希指針首尾相連,每一個(gè)區(qū)塊一旦形成便不可改變.如圖2 所示,區(qū)塊分為區(qū)塊頭和區(qū)塊體兩部分:區(qū)塊頭包括版本號(hào)、前一區(qū)塊哈希指針(由前一區(qū)塊頭數(shù)據(jù)哈希得到)、區(qū)塊形成時(shí)的時(shí)間戳、區(qū)塊體中交易自下而上哈希得到的Merkle 根以及用于工作量證明的隨機(jī)數(shù)和目標(biāo)哈希;區(qū)塊體中保存著區(qū)塊中的所有交易記錄.

如圖3 所示,交易(transaction)包含版本號(hào)(nVersion)、交易輸入(TxIn)、交易輸出(Txout)以及交易時(shí)間(nLockTime).其中:交易輸入包含其要花費(fèi)的交易輸出(preout)以及鎖定腳本(ScriptSig),并且當(dāng)且僅當(dāng)SicriptSig是上一個(gè)輸出中ScriptPubk 對(duì)應(yīng)的私鑰簽名時(shí)才被認(rèn)為是有效的;交易輸出指定該筆交易的輸出金額(nValue),以及收款人的公鑰(ScripPubk).數(shù)字簽名技術(shù)[17]保證每筆交易被支付到一個(gè)公鑰里,然后只有擁有私鑰的人才能花費(fèi)掉這筆交易.

(2)數(shù)據(jù)讀寫流程

對(duì)于數(shù)據(jù)的存儲(chǔ)管理,在寫入數(shù)據(jù)時(shí),每個(gè)區(qū)塊的數(shù)據(jù)操作流程如下.

1)收集交易.將未寫入到區(qū)塊內(nèi)的交易數(shù)據(jù)進(jìn)行正確性檢查(包括格式檢查以及雙花檢查),并將有效的交易數(shù)據(jù)收集在集合(MapTransaction)中,其中,MapTransaction 只存放在內(nèi)存中,其內(nèi)存放了從交易哈希到交易的map 映射;

2)創(chuàng)建區(qū)塊.將MapTransaction 中的數(shù)據(jù)添加到區(qū)塊體中;之后運(yùn)行PoW 機(jī)制,搜索合適的隨機(jī)數(shù)值,使得區(qū)塊頭的哈希值小于目標(biāo)哈希,從而證明該區(qū)塊有效,即挖礦成功并獲得獎(jiǎng)勵(lì);

3)存儲(chǔ)區(qū)塊.在網(wǎng)絡(luò)上將該區(qū)塊廣播,在本地將該區(qū)塊順序存儲(chǔ)在本地磁盤文件(blk000x.bat)中;

4)更新區(qū)塊索引(CblockIndex).在k-v數(shù)據(jù)庫中更新CblockIndex,CblockIndex 記錄著區(qū)塊的磁盤存儲(chǔ)位置以及該區(qū)塊的前驅(qū)和后繼區(qū)塊,根據(jù)區(qū)塊索引,能夠得到區(qū)塊鏈的世界狀態(tài);

5)更新交易索引(TxIndex).TxIndex 存儲(chǔ)在k-v數(shù)據(jù)庫中,包含每一筆交易的磁盤存儲(chǔ)位置以及交易的后繼交易(以該交易作為輸入的交易).后繼交易初始為空,標(biāo)識(shí)該交易是未花費(fèi)的,當(dāng)該交易被花費(fèi)后更新其后繼交易,也是根據(jù)該標(biāo)識(shí)位判斷交易是否被雙花;

6)將寫入到磁盤的交易數(shù)據(jù)從MapTransaction 中移除.

Fig.2 Block structure diagram圖2 區(qū)塊結(jié)構(gòu)示意圖

Fig.3 Transaction structure diagram圖3 交易結(jié)構(gòu)示意圖

在讀取數(shù)據(jù)的時(shí)候,必須要提供要讀取數(shù)據(jù)的hash值,根據(jù)hash值,先在內(nèi)存中的MapTransaction 中查找;如果沒有查找到,則根據(jù)hash值到k-v數(shù)據(jù)庫中查找對(duì)應(yīng)索引信息TxIndex;最后,根據(jù)TxIndex 在磁盤文件blk000x.bat 中讀取到數(shù)據(jù).

(3)已有模型存在的不足

已有的模型利用數(shù)字簽名技術(shù)以及MerkleRoot 來保證數(shù)據(jù)不可篡改和數(shù)據(jù)安全,但是其交易數(shù)據(jù)結(jié)構(gòu)固定,只能處理固定結(jié)構(gòu)的交易數(shù)據(jù),不能處理一般數(shù)據(jù),不適合傳統(tǒng)數(shù)據(jù)庫中的數(shù)據(jù)處理,缺少一般性;在進(jìn)行數(shù)據(jù)讀寫操作時(shí),只能夠根據(jù)數(shù)據(jù)的hash值進(jìn)行處理,在不知道數(shù)據(jù)hash值的情況下,無法進(jìn)行數(shù)據(jù)查詢操作.

3.2 面向數(shù)據(jù)庫的區(qū)塊鏈系統(tǒng)模型

針對(duì)已有模型中的不足,本文提出一種面向數(shù)據(jù)庫的區(qū)塊鏈系統(tǒng)模型,將交易結(jié)構(gòu)擴(kuò)展到任意記錄格式,為每一個(gè)區(qū)塊創(chuàng)建一個(gè)不可篡改的索引,在保證不可篡改的同時(shí)實(shí)現(xiàn)高效查詢,為數(shù)據(jù)的所有者賦予新的語義,并重新定義數(shù)據(jù)操作.

(1)數(shù)據(jù)結(jié)構(gòu)

為了能夠操作更一般的數(shù)據(jù),本文將交易結(jié)構(gòu)進(jìn)行了擴(kuò)展,如圖4 所示,交易分為交易頭(transaction)和數(shù)據(jù)(data)兩部分:交易頭包含版本號(hào)(version)、父交易哈希(PreHash)、交易時(shí)間(nTime)、交易下一擁有者公鑰(ScriptPubk)、證明本交易有效的簽名(ScriptSig);數(shù)據(jù)部分類似于傳統(tǒng)數(shù)據(jù)庫中的表結(jié)構(gòu),包含關(guān)鍵字key以及各個(gè)字段(field).根據(jù)交易頭部分實(shí)現(xiàn)數(shù)據(jù)的權(quán)限管理以及不可篡改和可回溯,根據(jù)數(shù)據(jù)部分記錄各種類型的數(shù)據(jù).其中,PreHash 指向相同Key 的前一交易.在進(jìn)行寫入數(shù)據(jù)的時(shí)候,首先查詢是否存在關(guān)鍵字為key的交易:如果存在,則檢驗(yàn)當(dāng)前交易的SicriptSig 是否與前一交易的ScriptPubk 相匹配,只有在匹配的情況下,才認(rèn)為交易有效;如果該key是第1 次出現(xiàn),則將PreHash 置為0.在進(jìn)行數(shù)據(jù)讀取的時(shí)候,根據(jù)key進(jìn)行檢索,返回最近的查詢結(jié)果,但是可以根據(jù)交易中的PreHash 進(jìn)行溯源.數(shù)據(jù)的修改通過寫入新交易實(shí)現(xiàn),所有的記錄都不可刪除.

Fig.4 Database-oriented transaction structure圖4 面向數(shù)據(jù)庫的交易結(jié)構(gòu)示意圖

區(qū)塊結(jié)構(gòu)與已有的大體類似,特別之處是在區(qū)塊的MerkleTree 中添加了關(guān)于交易key值的索引信息,使得可以從MerkleRoot 根據(jù)key值直接檢索到對(duì)應(yīng)交易,實(shí)現(xiàn)了交易的可查詢性;同時(shí),索引是經(jīng)由Hash 運(yùn)算保存在Merkle 樹中,保證了索引的不可篡改.

(2)數(shù)據(jù)讀寫流程

為了實(shí)現(xiàn)針對(duì)于key的查詢,寫入數(shù)據(jù)時(shí),在每一個(gè)區(qū)塊中創(chuàng)建一個(gè)關(guān)于key的不可篡改索引,并將該索引記錄保存在k-v數(shù)據(jù)庫中;在讀取數(shù)據(jù)時(shí),根據(jù)key從區(qū)塊頭的MerkleRoot 開始索引,在O(logN)時(shí)間內(nèi)索引到交易的hash值,然后根據(jù)該hash值到k-v數(shù)據(jù)庫中查詢到對(duì)應(yīng)的TxIndex,最后,在磁盤文件blk000x.dat 中讀取交易信息.

4 數(shù)據(jù)操作算法

4.1 Merkle RBTree索引構(gòu)建

區(qū)塊鏈數(shù)據(jù)庫要求其數(shù)據(jù)滿足不可篡改性,則對(duì)于數(shù)據(jù)的索引自然也應(yīng)該是不可篡改的.我們定義區(qū)塊一旦形成便不可修改,因此,我們對(duì)于每一個(gè)區(qū)塊構(gòu)造一個(gè)二叉查找樹,然后將數(shù)據(jù)與二叉查找樹一起做哈希運(yùn)算,從而實(shí)現(xiàn)數(shù)據(jù)與索引的不可篡改.

我們選擇紅黑樹和Merkle 樹結(jié)合,選擇紅黑樹有以下幾個(gè)原因.

1)紅黑樹是二叉查找樹,同時(shí)也是平衡二叉樹,雖然不是完美平衡,但是能夠保證查詢復(fù)雜度為O(logN);

2)和Merkle 樹一樣,紅黑樹是由下往上生長(zhǎng)的,從而能夠保證父節(jié)點(diǎn)是由子節(jié)點(diǎn)哈希得到的,在插入新節(jié)點(diǎn)時(shí),父節(jié)點(diǎn)信息可以得到相應(yīng)更新.

然而,傳統(tǒng)索引中的記錄值并不是全部存儲(chǔ)在葉子節(jié)點(diǎn),其內(nèi)部節(jié)點(diǎn)也都存儲(chǔ)著記錄值.然而這會(huì)在兩個(gè)方面影響Merkle 樹的性能.

1)不利于輕量級(jí)存在性證明.

如圖5 所示:如果輕量級(jí)節(jié)點(diǎn)持有MerkleRoot 即H11以及記錄信息Data4,我們想證明Data4是否存在于這棵樹中.我們直接將序列{H3,H7,H9}發(fā)送給該節(jié)點(diǎn),該節(jié)點(diǎn)計(jì)算Hash(Hash(H7,Hash(H3,Hash(Data4))),H9),如果得到的值等于H11,則證明Data4存在于這棵樹中;否則不存在.其實(shí),存在性證明就是通過將孩子節(jié)點(diǎn)兩兩哈希得到父親節(jié)點(diǎn),通過判斷父親節(jié)點(diǎn)是否相同來驗(yàn)證孩子節(jié)點(diǎn)的正確性.這就要求我們可以由孩子節(jié)點(diǎn)哈希得到父親節(jié)點(diǎn),但是如果父親節(jié)點(diǎn)存放了與孩子節(jié)點(diǎn)無關(guān)的記錄,我們便無法根據(jù)孩子節(jié)點(diǎn)哈希得到父親節(jié)點(diǎn),也便無法進(jìn)行存在性證明;

Fig.5 MerkleRBTree logical structure圖5 MerkleRBTree 邏輯結(jié)構(gòu)圖

2)不利于分支刪減,不能節(jié)省磁盤空間.

考慮到這樣一種情景:Data1,Data2,Data3,Data4已經(jīng)被修改過多次,而Data5,Data6則很少被修改,根據(jù)第2節(jié)對(duì)于修改記錄的描述可知:前面4 個(gè)數(shù)據(jù)項(xiàng)已經(jīng)有了很多后繼,相當(dāng)于非常久遠(yuǎn)的版本;而后兩個(gè)數(shù)據(jù)項(xiàng)還是屬于較新的版本.我們希望可以刪除Data1～Data4但是不影響后續(xù)對(duì)于Data5,Data6的查詢驗(yàn)證等操作.如果數(shù)據(jù)項(xiàng)都存在葉子節(jié)點(diǎn),我們可以通過刪除Data1～Data4只保留H10來節(jié)省磁盤空間而不影響樹的功能;但是如果有數(shù)據(jù)記錄存放在分支節(jié)點(diǎn),我們便無法刪除分支節(jié)點(diǎn)來節(jié)省磁盤空間,因?yàn)槟菢訒?huì)影響樹的功能(無法對(duì)剩余分支進(jìn)行存在性證明).

因此,我們將索引內(nèi)部節(jié)點(diǎn)的記錄值往左下方移動(dòng),直到葉子節(jié)點(diǎn)為止,從而使得記錄值只存放在葉子節(jié)點(diǎn).在實(shí)現(xiàn)上,就是將小于等于節(jié)點(diǎn)關(guān)鍵字的記錄存儲(chǔ)在左子樹,大于關(guān)鍵字的記錄存放在右子樹,中間節(jié)點(diǎn)只存放關(guān)鍵字和子節(jié)點(diǎn)hash值.

如圖5 所示,共有6 條記錄項(xiàng):Data1,Data2,…,Data6,每個(gè)記錄項(xiàng)都有一個(gè)關(guān)鍵值分別為5,8,10,12,15,16.按照關(guān)鍵值順序?qū)⒂涗涰?xiàng)存儲(chǔ)到葉子節(jié)點(diǎn)中.分支節(jié)點(diǎn)中存放著左右子樹的哈希值以及關(guān)鍵字,同時(shí)保證該節(jié)點(diǎn)的左子樹中的關(guān)鍵值都小于等于該節(jié)點(diǎn)的關(guān)鍵值,右子樹中的關(guān)鍵值都大于該節(jié)點(diǎn)關(guān)鍵值.

4.2 基于索引的數(shù)據(jù)操作算法

(1)數(shù)據(jù)插入算法

根據(jù)數(shù)據(jù)結(jié)構(gòu)定義,節(jié)點(diǎn)結(jié)構(gòu)如下.

葉子節(jié)點(diǎn)包含交易信息,中間分支節(jié)點(diǎn)存儲(chǔ)索引信息.如果節(jié)點(diǎn)是分支節(jié)點(diǎn),其lefthash和righthash分別為左右孩子節(jié)點(diǎn)哈希,key值等于左子樹最大關(guān)鍵值.如果節(jié)點(diǎn)是葉子節(jié)點(diǎn),其左右子樹為空,為了區(qū)別于分支節(jié)點(diǎn),其lefthash為0,righthash等于交易哈希值,value為交易記錄.節(jié)點(diǎn)的哈希值定義為

我們從根節(jié)點(diǎn)開始插入數(shù)據(jù),如果關(guān)鍵值小于等于根節(jié)點(diǎn),則插入到其左子樹;如果大于,則插入到右子樹,直到最后一層分支節(jié)點(diǎn)h,根據(jù)如下所述4 種情況分別在該節(jié)點(diǎn)處插入新值.

· 情況1:如果該分支節(jié)點(diǎn)為空(只在MerkleRoot 為空時(shí)出現(xiàn)),先新建一個(gè)葉子節(jié)點(diǎn)存放(key,value)數(shù)據(jù),然后新建一個(gè)分支節(jié)點(diǎn),并定義其左孩子為葉子節(jié)點(diǎn),關(guān)鍵值為key,左哈希為葉子節(jié)點(diǎn)哈希值.插入結(jié)果如圖6(a)所示.這也說明了一棵樹只要不為空,則其分支節(jié)點(diǎn)一定不為空,而且最后一層分支節(jié)點(diǎn)的key值一定與其左孩子key值相同;

· 情況2:如果待插入數(shù)據(jù)key值小于該節(jié)點(diǎn)key值,我們應(yīng)該將該數(shù)據(jù)插入到該節(jié)點(diǎn)左側(cè),但是由情況1可知:該節(jié)點(diǎn)左孩子一定不為空,而且是葉子節(jié)點(diǎn).為此,我們新建一個(gè)葉子節(jié)點(diǎn)存放待插入的(key,value)數(shù)據(jù),然后新建一個(gè)分支節(jié)點(diǎn),其關(guān)鍵字為待插入節(jié)點(diǎn)key,左孩子為新建的葉子節(jié)點(diǎn),右孩子為原來分支節(jié)點(diǎn)的左孩子,父節(jié)點(diǎn)為原分支節(jié)點(diǎn),插入結(jié)果如圖6(b)所示,其中,連接和分支節(jié)點(diǎn)用虛線表示;

· 情況3:如果待插入數(shù)據(jù)key值大于該節(jié)點(diǎn),而且該節(jié)點(diǎn)右孩子為空,則直接新建葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù),并將其定義為分支節(jié)點(diǎn)右孩子,插入結(jié)果如圖6(c)所示;

· 情況4:如果待插入數(shù)據(jù)key值大于該節(jié)點(diǎn),而且該節(jié)點(diǎn)右孩子不為空,我們先新建葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù),然后新建分支節(jié)點(diǎn),分支節(jié)點(diǎn)關(guān)鍵值為待插入數(shù)據(jù)key值與原分支節(jié)點(diǎn)右孩子key值中的較小者,左孩子為待插入數(shù)據(jù)與原分支節(jié)點(diǎn)右孩子中key值較小者,右孩子為較大者,父節(jié)點(diǎn)為原分支節(jié)點(diǎn),插入后結(jié)果如圖6(d)所示.

Fig.6 Example of last layer branch node insertion圖6 最后一層分支節(jié)點(diǎn)插入示例

算法1.數(shù)據(jù)插入算法.

輸入:根節(jié)點(diǎn)h,插入記錄關(guān)鍵值key,插入數(shù)據(jù)值value;

輸出:根節(jié)點(diǎn).

· 算法1 的第2 行、第3 行是區(qū)塊為空時(shí)的初始插入操作;

· 第4 行～第6 行是當(dāng)插入key值小于節(jié)點(diǎn)key值時(shí),如果該節(jié)點(diǎn)左孩子是最后一層分支節(jié)點(diǎn),則按照之前所述情況2 插入數(shù)據(jù);否則,以左孩子節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)遞歸插入數(shù)據(jù);

· 第7 行～第10 行是當(dāng)插入key值大于節(jié)點(diǎn)key值時(shí):

? 如果右孩子為空,則該節(jié)點(diǎn)是最后一層分支節(jié)點(diǎn),按照情況3 插入數(shù)據(jù);

? 如果右孩子不為空,且是最后一層分支節(jié)點(diǎn),則按照情況4 插入數(shù)據(jù);否則,以右孩子為當(dāng)前節(jié)點(diǎn),遞歸插入數(shù)據(jù);

· 第11 行～第13 行添加紅黑樹旋轉(zhuǎn)規(guī)則,保證該樹黑色平衡;

· 第14 行、第15 行更新節(jié)點(diǎn)哈希值.

數(shù)據(jù)插入之后,我們得到從根節(jié)點(diǎn)開始的二叉搜索樹,而每個(gè)節(jié)點(diǎn)的哈希值即Hash(lefthash,righthash,key)又完全映射成一個(gè)基于哈希的不可篡改索引.數(shù)據(jù)是先寫入到內(nèi)存區(qū)塊當(dāng)中,當(dāng)內(nèi)存區(qū)塊大小到達(dá)一定的閾值,則將該區(qū)塊順序?qū)懭氲酱疟P中,將其對(duì)應(yīng)的MerkleRBIndex 存儲(chǔ)到k-v數(shù)據(jù)庫中.數(shù)據(jù)庫中存儲(chǔ)格式:

為了便于理解,可以認(rèn)為MerkleRBIndex 對(duì)應(yīng)一個(gè)map 集合mapMerkleIndex.

(2)數(shù)據(jù)查找算法

根據(jù)之前創(chuàng)建的索引,我們可以提供一種針對(duì)關(guān)鍵字key的查詢方法,并且根據(jù)Merkle 樹的特性,提供對(duì)應(yīng)該查詢結(jié)果的驗(yàn)證路徑,使得輕量級(jí)客戶端可以根據(jù)極少量信息去自我驗(yàn)證查詢結(jié)果的正確性.

當(dāng)輸入關(guān)鍵值key時(shí),首先在內(nèi)存區(qū)塊中檢索,如果檢索不到,就加載k-v數(shù)據(jù)庫中上一區(qū)塊的MerkleRBIndex 索引,直到檢索到該數(shù)據(jù)項(xiàng)或者不存在該記錄.當(dāng)在特定區(qū)塊中檢索的時(shí)候,首先從MerkleRoot節(jié)點(diǎn)開始檢索,如果目標(biāo)關(guān)鍵字小于等于根節(jié)點(diǎn)關(guān)鍵字,則在mapMerkleIndex 中查找k為root.lefthash的目錄,其對(duì)應(yīng)的v則為下次要比對(duì)的對(duì)象;否則,查找root.righthash.最后,查詢鎖定在葉子節(jié)點(diǎn),如果葉子節(jié)點(diǎn)的關(guān)鍵值等于目標(biāo)關(guān)鍵值則查詢成功;否則,記錄不存在該區(qū)塊中.

算法2.數(shù)據(jù)查找算法.

輸入:關(guān)鍵值key,索引map〈Hash(lefthash,righthash,key),〈lefthash,righthash,key〉〉mmap;

輸出:節(jié)點(diǎn)哈希值以及驗(yàn)證路徑Vector〈〈hash,key〉〉path.

· 算法2 的第2 行初始化當(dāng)前查找hash值為merkleroot;

· 第3 行～第9 行向下檢索直到葉子節(jié)點(diǎn),其中:第4 行～第6 行是如果目標(biāo)key值小于等于當(dāng)前索引項(xiàng)key值,則更新索引項(xiàng)為當(dāng)前索引項(xiàng)的左哈希對(duì)應(yīng)的索引項(xiàng),并將其右哈希和索引key值保存在驗(yàn)證路徑中;第7 行～第9 行對(duì)應(yīng)目標(biāo)key值大于當(dāng)前索引key值的情況;

· 第10 行～第14 行是檢驗(yàn)葉子節(jié)點(diǎn)是否包含目標(biāo)key值:如果不在,則清空驗(yàn)證路徑;如果在,則更新交易哈希值,并且將該項(xiàng)對(duì)應(yīng)的驗(yàn)證值添加到驗(yàn)證路徑中.

在圖5 所示的MerkleRBTree 中,對(duì)于關(guān)鍵字key=10 的查詢,從節(jié)點(diǎn)H11開始,依次查詢H10,H8和H3,驗(yàn)證路徑為path={(H9,12),(H7,8),(H4,10),(0,10)}.

本文提出的索引結(jié)構(gòu)能夠讓索引自我檢測(cè)索引的正確性和完整性.在區(qū)塊內(nèi)檢索數(shù)據(jù)的過程,就是對(duì)mapMerkleIndex進(jìn)行map 映射的過程.由于該map 最初是根據(jù)交易數(shù)據(jù)和索引信息自下往上兩兩哈希得到的,每一個(gè)條目都是確定且不可缺少的,當(dāng)從最頂端開始向下檢索的時(shí)候,能且只能檢索到構(gòu)建索引時(shí)存在的節(jié)點(diǎn),直到葉子節(jié)點(diǎn).如果在檢索過程中指向一個(gè)map 中不存在的條目,則可以確定該索引數(shù)據(jù)缺失或者數(shù)據(jù)被篡改.

(3)數(shù)據(jù)驗(yàn)證算法

不僅存儲(chǔ)節(jié)點(diǎn)可以在查詢的時(shí)候檢測(cè)到索引的正確性和完整性,而且用戶節(jié)點(diǎn)可以在接收到查詢結(jié)果之后對(duì)查詢進(jìn)行驗(yàn)證.如第2 節(jié)所述:用戶節(jié)點(diǎn)存有區(qū)塊頭信息,而區(qū)塊頭當(dāng)中有MerkleRoot 值,用戶根據(jù)查詢結(jié)果和驗(yàn)證路徑,對(duì)路徑上的值兩兩哈希生成查詢結(jié)果對(duì)應(yīng)的MerkleRoot 值,用戶通過比較該值是否與自己保存的區(qū)塊頭中的MerkleRoot 值相同,從而驗(yàn)證查詢的正確性.而且查詢路徑的長(zhǎng)度對(duì)應(yīng)交易在二叉查找樹中的深度,對(duì)于含有N個(gè)交易的區(qū)塊,任意交易的查詢路徑長(zhǎng)度為logN,而且查詢路徑中的值為256 位的哈希值,驗(yàn)證的存儲(chǔ)代價(jià)極小而且高效.

算法3.數(shù)據(jù)驗(yàn)證算法.

輸入:交易信息tx,驗(yàn)證路徑path,根哈希merkleroot;

輸出:true or false.

算法3 的第2 行計(jì)算交易哈希值;第3 行～第5 行根據(jù)驗(yàn)證路徑,從該交易開始向上重新生成父節(jié)點(diǎn),最后生成根節(jié)點(diǎn);第6 行～第8 行比對(duì)根據(jù)驗(yàn)證路徑生成的根節(jié)點(diǎn)值與本地保存的根節(jié)點(diǎn)值,如果相同,則查詢有效.

5 實(shí) 驗(yàn)

實(shí)驗(yàn)的硬件環(huán)境是Intel(R)Core(TM)i5-6500 CPU(3.2GHz),RAM 為8Gb 的PC 機(jī),操作系統(tǒng)為Windows10.借助Bitcoin 的開源代碼v0.1.0 版本構(gòu)建了一個(gè)區(qū)塊鏈數(shù)據(jù)庫,實(shí)驗(yàn)中主要修改了Bitcoin 的底層數(shù)據(jù)結(jié)構(gòu),包括交易格式以及在區(qū)塊中交易的組織形式,其中:交易格式擴(kuò)展為支持更一般的數(shù)據(jù)格式,交易的組織形式由Merkle 樹改為MerkleRBTree;保留了非對(duì)稱加密技術(shù)以及UTXO 的思想,類比Bitcoin 中的公鑰與私鑰腳本結(jié)合形成價(jià)值傳遞軌跡,本實(shí)驗(yàn)中利用公鑰私鑰腳本結(jié)合形成數(shù)據(jù)的修改軌跡,并且利用該軌跡進(jìn)行數(shù)據(jù)溯源.需要說明的是,本文的主要研究點(diǎn)是對(duì)于區(qū)塊鏈數(shù)據(jù)的索引方法,不涉及網(wǎng)絡(luò)以及共識(shí)協(xié)議,故在實(shí)驗(yàn)時(shí)利用單機(jī)進(jìn)行測(cè)試,并將共識(shí)替換為檢查交易的合法性,將有效交易存入到區(qū)塊中,當(dāng)區(qū)塊大小達(dá)到閾值,則將整個(gè)區(qū)塊存入磁盤.在本節(jié)中,我們?cè)O(shè)計(jì)多組實(shí)驗(yàn)來測(cè)試本文所提出的不可篡改索引的性能,實(shí)驗(yàn)中的主要指標(biāo)為算法的運(yùn)行時(shí)間,并將算法獨(dú)立運(yùn)行30 次的平均值定義為算法的運(yùn)行時(shí)間.

· 實(shí)驗(yàn)1:MerkleRBTree 的性能測(cè)試

在比特幣中生成區(qū)塊時(shí),需要對(duì)交易兩兩哈希得到 MerkleRoot.本文的模型中將 MerkleTree 替換成MerkleRBTree,在得到MerkleRoot 的同時(shí)生成對(duì)應(yīng)的索引.我們?cè)O(shè)計(jì)實(shí)驗(yàn)測(cè)試了在區(qū)塊交易數(shù)為26,27,…,216時(shí)對(duì)應(yīng)的索引構(gòu)建的時(shí)間代價(jià).如圖7 所示:MerkleTree 和MerkleRBTree 的構(gòu)建代價(jià)隨著交易數(shù)的增加而線性增加,有著相近的性能.說明在可接受的代價(jià)內(nèi)實(shí)現(xiàn)了索引的構(gòu)建,增加了查詢功能.這里,MerkleRBTree 的時(shí)間代價(jià)多于MerkleTree 的時(shí)間代價(jià),主要是因?yàn)樵谶M(jìn)行哈希操作時(shí),MerkleTree 每次哈希輸入為兩個(gè)值,分別為左右子哈希;在MerkleRBTree 中,每次哈希操作為3 個(gè)值,分別為左右子哈希和對(duì)應(yīng)的key值.

· 實(shí)驗(yàn)2:區(qū)塊大小對(duì)于交易平均寫入時(shí)間以及內(nèi)存消耗的影響

交易到內(nèi)存之后,需要等到形成一個(gè)完整區(qū)塊才能存入到磁盤,這就使得第1 個(gè)進(jìn)入到區(qū)塊的交易和最后一個(gè)進(jìn)入?yún)^(qū)塊的交易有時(shí)間差,故在此取多個(gè)交易的平均時(shí)間.在這里,用交易數(shù)來度量區(qū)塊大小,分別設(shè)置區(qū)塊中最大交易數(shù)量為64,128,256,512,1024,2048,4096,8192,設(shè)置交易的字段數(shù)為3.如圖8 所示,交易的平均寫入時(shí)間隨著區(qū)塊最大交易數(shù)的增加而減小.這是因?yàn)閰^(qū)塊中交易數(shù)越多,寫入磁盤的時(shí)間代價(jià)均分到每一個(gè)交易上的代價(jià)就會(huì)越小.同時(shí)發(fā)現(xiàn):當(dāng)最大交易數(shù)為1024 以后,平均寫入代價(jià)趨于穩(wěn)定.另一方面,區(qū)塊越大交易數(shù)越大,對(duì)應(yīng)的內(nèi)存消耗越大,且在區(qū)塊交易數(shù)超過1024 以后,內(nèi)存消耗增加明顯.綜合考慮兩者因素,確定區(qū)塊大小為1024 個(gè)交易.

Fig.7 MerkleRBTree and MerkleTree build cost comparison圖7 MerkleRBTree 和MerkleTree 構(gòu)建代價(jià)對(duì)比

Fig.8 Impact of block size on memory and write time圖8 區(qū)塊大小對(duì)內(nèi)存和寫入時(shí)間的影響

· 實(shí)驗(yàn)3:key值查詢與hash值查詢性能對(duì)比

現(xiàn)有的區(qū)塊鏈系統(tǒng)只能根據(jù)交易哈希值進(jìn)行查詢,哈希值形如“1ef4c1a9c62aa236766d2864c4c0f2d609aa83 d4f256dc35962a603a6832a476”抽象且與數(shù)據(jù)沒有直接關(guān)聯(lián).本文實(shí)現(xiàn)了針對(duì)數(shù)據(jù)關(guān)鍵字key進(jìn)行查詢,我們?cè)O(shè)計(jì)的實(shí)驗(yàn)測(cè)試了針對(duì)key值與hash值的查詢性能比較.如圖9 所示,本文提出的針對(duì)key值的查詢和比特幣中針對(duì)哈希值的查詢有相當(dāng)?shù)男阅?表明在可接受的時(shí)間代價(jià)內(nèi),實(shí)現(xiàn)了交易的可查詢性.

Fig.9 Comparison of key value query and hash value query圖9 key 值查詢與hash 值查詢對(duì)比

· 實(shí)驗(yàn)4:區(qū)塊深度對(duì)于查詢時(shí)間的影響

數(shù)據(jù)在存儲(chǔ)時(shí)是按照寫入順序依次添加到區(qū)塊中,區(qū)塊順序?qū)懭氪疟P.我們?cè)O(shè)計(jì)的實(shí)驗(yàn)測(cè)試了數(shù)據(jù)寫入先后順序?qū)τ诓樵兊挠绊?實(shí)驗(yàn)中順序?qū)懭?0 萬條key升序數(shù)據(jù),每一個(gè)區(qū)塊大小為1 000 條數(shù)據(jù),一共500 區(qū)塊,測(cè)試不同深度的數(shù)據(jù)查詢時(shí)間.如圖10 所示:數(shù)據(jù)查詢操作并不受區(qū)塊深度影響,對(duì)于先后寫入的數(shù)據(jù)具有相近的查詢時(shí)間,查詢時(shí)間均勻分布在0.36s 左右.圖中的異常點(diǎn)主要是因?yàn)樵谶M(jìn)行數(shù)據(jù)查詢時(shí),需要訪問k-v數(shù)據(jù)庫讀取元數(shù)據(jù)信息,而k值為256 位的哈希值,k-v數(shù)據(jù)庫的不穩(wěn)定性導(dǎo)致了異常點(diǎn)的出現(xiàn).

Fig.10 Block depth influence on query time圖10 區(qū)塊深度對(duì)于查詢時(shí)間的影響

· 實(shí)驗(yàn)5:數(shù)據(jù)溯源性能測(cè)試

區(qū)塊鏈的特性之一就是數(shù)據(jù)可回溯,即返回任意數(shù)據(jù)的完整修改歷史.我們?cè)O(shè)計(jì)實(shí)驗(yàn)測(cè)試了數(shù)據(jù)版本數(shù)對(duì)于溯源時(shí)間的影響,分別設(shè)置7 條區(qū)塊鏈,每條鏈的區(qū)塊個(gè)數(shù)依次為10,20,30,40,50,60,70,區(qū)塊中交易個(gè)數(shù)固定為1 024,交易的字段數(shù)固定為3,字段值為value+區(qū)塊號(hào),每個(gè)區(qū)塊中key為0～1023,以此模擬數(shù)據(jù)的版本更新.分別在7 條鏈上針對(duì)同一關(guān)鍵字key進(jìn)行數(shù)據(jù)溯源,記錄查詢到最初版本所需要的時(shí)間.如圖11 所示,數(shù)據(jù)溯源的查詢代價(jià)接近于單次數(shù)據(jù)查詢的時(shí)間代價(jià).這說明數(shù)據(jù)溯源的查詢代價(jià)集中于最新版本的查詢時(shí)間,歷史數(shù)據(jù)的溯源時(shí)間相對(duì)于單次查詢時(shí)間微乎其微,具有很好的溯源效率.

Fig.11 Impact of version number on query time圖11 版本數(shù)對(duì)于查詢時(shí)間的影響

6 總結(jié)

本文首先提出了一種區(qū)塊鏈數(shù)據(jù)庫模型,將區(qū)塊鏈技術(shù)應(yīng)用于數(shù)據(jù)管理;其次提出了一種基于哈希指針的樹型索引結(jié)構(gòu),用于管理區(qū)塊內(nèi)的記錄項(xiàng),并由此實(shí)現(xiàn)查詢;最后,通過實(shí)驗(yàn)測(cè)試數(shù)據(jù)庫的讀寫性能.實(shí)驗(yàn)結(jié)果表明:本文提出的不可篡改索引在保證不可篡改的同時(shí),具有較好的讀寫性能.同時(shí),本文提出的針對(duì)key值的查詢方法,是對(duì)于區(qū)塊鏈數(shù)據(jù)庫進(jìn)行多值查詢以及范圍查詢的基礎(chǔ),之后還會(huì)在此基礎(chǔ)上進(jìn)一步研究區(qū)塊鏈的復(fù)雜查詢.

當(dāng)下人們對(duì)于數(shù)據(jù)安全的要求越來越高,區(qū)塊鏈憑借著安全不可篡改的特性,必然會(huì)有出色的表現(xiàn).然而要構(gòu)建一個(gè)成熟的區(qū)塊鏈數(shù)據(jù)庫還需要一些后續(xù)工作.

(1)利用高效的共識(shí)算法提升系統(tǒng)的吞吐率;

(2)利用智能合約管理每一個(gè)數(shù)據(jù)項(xiàng)的讀寫權(quán)限,保證只有擁有者授權(quán)的公鑰可以訪問和修改數(shù)據(jù).