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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 區(qū)塊鏈式數(shù)據(jù)模型

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

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

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

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

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

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

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

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

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

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

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

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

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ù)據(jù)的hash值,根據(jù)hash值,先在內(nèi)存中的MapTransaction 中查找;如果沒有查找到,則根據(jù)hash值到k-v數(shù)據(jù)庫中查找對應索引信息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ù)處理,缺少一般性;在進行數(shù)據(jù)讀寫操作時,只能夠根據(jù)數(shù)據(jù)的hash值進行處理,在不知道數(shù)據(jù)hash值的情況下,無法進行數(shù)據(jù)查詢操作.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出:根節(jié)點.

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

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

· 第7 行～第10 行是當插入key值大于節(jié)點key值時:

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

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

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

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

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

為了便于理解,可以認為MerkleRBIndex 對應一個map 集合mapMerkleIndex.

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

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

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

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

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

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

· 算法2 的第2 行初始化當前查找hash值為merkleroot;

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

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

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

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

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

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

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

輸入:交易信息tx,驗證路徑path,根哈希merkleroot;

輸出:true or false.

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

5 實 驗

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

· 實驗1:MerkleRBTree 的性能測試

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

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

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

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

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

· 實驗3:key值查詢與hash值查詢性能對比

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

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

· 實驗4:區(qū)塊深度對于查詢時間的影響

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

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

· 實驗5:數(shù)據(jù)溯源性能測試

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

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

6 總結(jié)

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

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

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

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