基于狀態樹的鏈上數據高效可信查詢索引模型及方法

摘要：區塊鏈技術以其去中心化，不可篡改等特性在分布式數據管理領域中逐漸得到關注。但區塊鏈系統在數據查詢處理方面存在查詢功能單一、效率低以及查詢可信性難以保證等問題。筆者基于以太坊狀態樹的設計思路，在保證索引不可篡改的前提下，提出一種全局索引結構KMPT，可一次定位目標區塊，避免了遍歷區塊的檢索過程，同時結合塊內索引TMPT，實現了基于內容的高效區塊鏈數據檢索。經實驗驗證，相比于僅構建塊內索引的方法，該索引模型在可接受的索引構建代價內極大提升了查詢檢索的效率和穩定性，還可同時提供查詢數據存在或不存在證明，提升了查詢結果的可信性。

關鍵詞：區塊鏈數據查詢；區塊鏈內容檢索；可信索引模型；不可篡改索引；狀態樹

中圖分類號：TP311 """"""""""文獻標志碼：A """""""""文章編號：1000-582X（2023）07-009-14

Efficient and trusted query index model and method for blockchain data based on Merkle Patricia tree

YUAN Xu， HUANG Lihuang， CHEN Zhikui， YU Shuo

（School of Software Technology， Dalian University of Technology， Dalian， Liaoning 116620， P. R. China）

Abstract： Blockchain technology has attracted significantly attention in the field of distributed data management because of its decentralized and immutable nature. However， current blockchain systems face limitations in data query processing including single query function， low query efficiency and difficulties in ensuring query credibility. To address these challenges， in this paper， a global index structure called KMPT is proposed， inspired by the design concept of Ethereum Merkle Patricia tree on the premise of ensuring the immutability of index. The KMPT structure aims to realize the function of locating the target block at one time， avoiding the retrieval process of traversing blocks. Furthermore， by incorporating the intra-block index TMPT， the proposed approach enables high-efficiency content-based blockchain data retrieval. Experiments demonstrate that， compared with the method of only building intra block index， the proposed index model significantly improved the efficiency and stability of query retrieval within the acceptable index construction cost. In addition， it can provide the proof of existence or non-existence of data query at the same time， enhancing the credibility of query results.

Keywords： blockchain data query; blockchain content retrieval; trusted query index model; immutable index; Merkle Patricia tree

隨著比特幣^[1]，以太幣^[2]等加密貨幣的興起，其底層區塊鏈技術得到了越來越多的關注。區塊鏈以其去中心化、不可篡改、多方共享以及可回溯特性^[3]為解決數據可信存儲問題提供了新的可能。在區塊鏈中，共識算法負責數據的寫入，在如何提升共識算法效率方面，目前已有很多研究并且取得了不錯的成效^[4]，但在對區塊鏈數據庫的讀性能，即查詢處理方面的研究相對較少。現有的區塊鏈系統在數據查詢處理方面仍暴露出很大的局限性，如比特幣系統中僅支持根據交易哈希值查詢具體交易，而無法針對交易的具體細節展開查詢；以太坊支持賬戶查詢，由于其引入了狀態樹^[5]維護全局賬戶狀態^[6]，可根據賬戶地址對賬戶狀態進行高效的查詢，但狀態樹本身與交易并無關聯，查詢交易數據仍需通過交易哈希值進行查詢。在面向區塊鏈中數據的查詢處理優化技術方面，于戈等^[7]首先提出將區塊鏈用于解決不可信環境下的分布式數據管理問題，深入討論了區塊鏈系統與傳統分布式數據庫之間的異同點，系統地總結了目前區塊鏈系統在數據存儲結構、查詢處理方面的優化技術。王千閣等^[8]總結了當前區塊鏈系統因數據存儲模式限制而普遍面臨著查詢功能簡單、查詢性能較低等嚴重問題，深入研究了區塊鏈系統數據存儲與查詢優化之間的關系。

目前區塊鏈系統在數據查詢方面的優化方法大體可分為兩類：一類是外聯數據庫方法，很多研究者將區塊鏈中的數據加載到鏈下數據庫中存儲，利用已有成熟的數據庫索引技術實現了對區塊鏈數據高效而豐富的檢索。Li等^[9]將以太坊區塊鏈數據和K-V數據庫里的數據加載到MongoDB 數據庫中，利用MongoDB 進行查詢操作，包括范圍查詢和Top-K查詢，查詢效率和查詢功能豐富性都得到了提高。通過區塊鏈網絡同步數據庫操作以更新鏈下數據庫，并利用鏈下數據庫對外提供高效豐富的查詢訪問服務。這類工作本質上都是將區塊鏈數據轉移到鏈下數據庫中存儲，難以保證數據和索引的不可篡改性，犧牲了數據安全性，同時增加了額外的存儲負擔，沒有從根本上解決區塊鏈系統數據查詢的問題^[10?11]。另一類是內置索引方法，與外聯數據庫方法不同，內置索引方法是在原有的區塊鏈數據結構上進行設計修改，將索引內嵌于區塊結構中，沒有給系統額外帶來過大的存儲負擔，致力于在保證數據不可篡改性的同時豐富查詢功能并提升查詢效率。例如，焦通等^[12]提出了一種可查詢區塊鏈數據的模型Blockchain DB，并設計了一種基于紅黑樹和Merkle樹結合的塊內索引結構MerkleRBTree，實現基于Key值的數據記錄最新版本查詢。賈大宇等^[13]提出了一種區塊鏈存儲容量可拓展模型的高效查詢方法—ElasticQM，采用一種基于B-M樹的區塊存儲結構組織塊內交易來加快塊內內容檢索的效率。Zhang等^[14]用數據關鍵字來代替傳統Merkle樹中葉子節點存儲的交易哈希值，并結合B+樹設計了MB樹索引，實現了基于數據關鍵字的查詢。塊內進行索引設計可以加快塊內內容檢索的速度，但仍需從最新區塊開始向前遍歷區塊檢索，當目標數據所在區塊深度較深時，這種檢索方式由于在無關區塊中進行了大量的無效搜索，降低了檢索效率，更糟糕的是，若目標交易不存在，需遍歷到創世區塊才能返回目標交易數據不存在信息，檢索響應慢，且無法提供數據不存在性證明，查詢可信性無法驗證。

為加快遍歷檢索過程中無關區塊的過濾速度，鄭浩瀚等^[15]對MB樹索引進行了改進，提出一種混合塊內索引結構，標識本區塊存儲交易連續屬性值的范圍，在區塊頭中引入一個布隆過濾器^[16]，標識本區塊交易離散屬性值集合，在開始對某區塊進行檢索前先將查詢目標值和塊頭信息比較，以此來避免對無關區塊進行無效搜索，該混合索引結構在保證索引不可篡改的同時實現了針對連續型和離散型變量的檢索，并加速了檢索過程中區塊的過濾速度。現有系統如比特幣、以太坊等也都通過在區塊頭引入布隆過濾器來避免對無關區塊的無效搜索，以提高檢索速度。然而，在區塊頭引入布隆過濾器或設置標識的方法雖然加快了區塊的過濾速度，但存在2個問題：一是布隆過濾器存在假陽性錯誤，有一定的誤報率，無法實現完全準確的過濾，設置標識字段方法也存在同樣的問題；二是方法雖避免了對大部分區塊的無效檢索，提升了檢索效率，但過濾區塊仍需遍歷區塊頭，遍歷過程中不斷產生的磁盤IO過程限制了檢索的效率。

綜上所述，目前區塊鏈數據查詢處理研究存在如下局限。

1）外聯數據庫方法無法保證數據不可篡改性，損失了區塊鏈特性，同時給系統帶來了額外的存儲負擔，沒有從根本上解決區塊鏈系統的查詢問題。

2）內置索引方法僅針對塊內數據構建索引，無法確定目標數據所在區塊。因此，需遍歷區塊進行檢索，難以避免在大量無關區塊中的無效搜索過程，大大降低了查詢檢索的效率。

3）當目標數據不存在時，僅使用塊內索引方法查詢響應慢，且無法向輕節點提供數據不存在證明，查詢結果的正確性無法驗證，查詢可信性差。

針對以上問題，在保證數據和索引不可篡改的前提下，筆者提出了一種基于以太坊狀態樹的全局區塊索引模型KMPT（key-Merkle Patricia tree），完成由數據內容到目標區塊之間的映射，實現由最新區塊一次鎖定目標數據所在的區塊，避免了遍歷區塊的檢索過程，同時可提供數據不存在性的證明。此外，對塊內數據記錄設計塊內索引TMPT（transaction-Merkle Patricia tree），加快在目標塊中的檢索速度，提供數據存在性的證明。實現基于內容的高效可信查詢，屬于內置索引方法范疇。本研究的主要貢獻如下。

1）針對內置索引方法在檢索中如何避免遍歷區塊的問題，基于以太坊狀態樹設計了一種針對區塊鏈中數據內容的不可篡改全局區塊索引，一次鎖定目標塊，避免了遍歷無關區塊檢索的過程，結合塊內索引，極大提升了基于數據內容對區塊鏈數據記錄的檢索效率。

2）基于提出的索引模型，可同時向輕節點提供查詢目標數據存在性和不存在性證明，提升了查詢可信性。

1 索引模型

1.1 數據及數據操作定義

為解決現有區塊鏈系統中數據模型單一問題，Blockchain DB^[13]模型中將交易數據結構擴展到任意記錄格式。筆者在Blockchain DB數據模型的基礎上研究查詢方法，將該模型中的數據和數據操作定義如下。

1.1.1 數據結構

為使區塊鏈中數據更具一般化，將原有交易結構重新定義。如圖1所示，交易由交易頭（transaction）和數據（data）組成。數據記錄兩者表述等價。

其中交易頭包含PreHash，指向相同Key的上一版本記錄；Time是該版本記錄的發布時間；ScriptPubK指定擁有該記錄寫操作權限的下一擁有者公鑰，ScriptSig是擁有本記錄寫操作權限的擁有者的簽名，兩者用于數據寫權限控制。

1.1.2 數據操作

增加記錄：向區塊鏈數據庫中添加某一新Key記錄時，數據擁有者可以指定下一擁有者對該條記錄寫操作權限的公鑰，然后用自己的私鑰發布該記錄簽名。

修改記錄：針對某一Key記錄的修改通過發布一個新的相同Key記錄以追加方式實現。只有擁有對該Key記錄寫操作權限的操作者才可修改記錄，記錄發布后需驗證其私鑰簽名是否與父記錄中的公鑰匹配，匹配則有效，否則該修改無效。

查詢記錄：所有參與者都可以進行查詢操作，對以Key為關鍵字的查詢會返回其最新的版本，可通過溯源操作查詢所有修改的歷史版本。

刪除記錄：數據一旦寫入便無法刪除。

1.2 索引模型

索引模型如圖2所示，分為塊內TMPT索引和全局狀態索引KMPT，TMPT與KMPT都基于以太坊MPT結構實現。與以太坊中交易樹和狀態樹類似，TMPT組織塊內數據記錄，而KMPT維護全局Key記錄狀態。所不同的是，以太坊中交易樹是由塊內交易序號構建的MPT，狀態樹是由賬戶地址編碼構建的MPT，而本文中TMPT與KMPT都是根據數據記錄Key值來構建的。

如圖2所示，每個區塊內數據記錄存儲于TMPT葉節點中，TMPT以塊內數據Key值為關鍵字構建而成，組織塊內數據，同時將TMPT根哈希值添加到區塊頭中。TMPT是一棵多叉搜索樹（前綴樹），與基于二叉搜索樹的塊內索引結構相比檢索效率更高。此外，每個區塊頭中再添加一個根哈希值KMPT Root，鏈接到當前的全局狀態索引樹KMPT樹根，KMPT是由Key值構建的一棵MPT，與以太坊狀態樹葉節點中Value存儲賬戶余額信息不同，KMPT葉節點中存儲一個哈希值LatestTMPTRoot，指向當前該Key記錄最新版本所在區塊的TMPT樹根，實現定位目標區塊的功能，避免了遍歷區塊檢索目標數據的過程。需說明的是，KMPT葉節點中維護的是目標數據所在區塊TMPT根哈希，得到此根哈希后可以直接開始塊內檢索，而塊內檢索的過程即是提供目標數據Merkle存在性證明路徑的過程，這樣便保證了查詢結果的可驗證性，也是之所以不在KMPT葉節點中直接存儲目標數據最新版本哈希而是維護其所在TMPT根哈希的原因。

值得一提的是，塊內TMPT檢索樹只組織本區塊內數據記錄，加快在區塊內部基于Key值的查找效率，而KMPT維護的是全局Key狀態，且每個區塊都有一顆完整的KMPT，存儲了到本區塊時刻的全局Key記錄狀態信息。為了減輕存儲負擔，這里KMPT采用與以太坊狀態樹相同的存儲策略，即區塊間共享KMPT樹中節點，構建和更新索引時，僅對本區塊內數據所關聯的Key狀態以新建分支的方式進行，并與前序區塊共享其他未改變狀態的KMPT節點，以減小存儲開銷。

1.2.1 數據插入

插入算法是TMPT和KMPT構建的基礎，以圖3為例說明在MPT中插入４個Key-Value對的構建過程。

如圖3-①所示，首先插入lt;a711355，value1gt;，由于此時樹中只有一個節點，則將該Key-Value對直接保存為葉節點，且此時該葉節點為樹的根節點。

如圖3-②所示，插入lt;a77d337，value2gt;，由于該Key與a711355共享前綴a7，故創建共享前綴為a7的擴展節點為根節點，且創建一個分支節點鏈接兩個葉節點。

如圖3-③所示，繼續將lt;a7f9365，value3gt;插入，也是與之前節點共享前綴a7，故只需在分支節點上新增一個葉節點即可。

最后插入lt;a77d397，value4gt;，如圖3-④所示，該Key與a77d337共享前綴a77d3，因此需再創建一個共享前綴為d3的擴展節點，并新建一個分支節點鏈接兩者。

需說明的是，每次插入一個節點后須從下至上更新其所在分支路徑上的哈希值及根哈希，節點哈希值計算方法與Merkle Tree類似，規則如下。

葉節點

Hash（Leaf Node）=Hash（Node.Key-End，Node.Value），

擴展節點

Hash（Extension Node）=Hash（Node.Shared nibble（s），Node.Next Node），

分支節點

Hash（Branch Node）=Hash（Node.Children[0]，...，Node.Children[f]，Node.Value）。

分支節點哈希值的計算方法是將存儲的每個子節點哈希值與節點Value中存儲的值一起進行哈希，最后得到該分支節點哈希值，若存儲哈希值為空，則使用空字節參與運算。

在索引模型中，TMPT與KMPT的構建都基于以上插入算法。區別在于TMPT維護的Key?Value對中，Key為數據的Key值，Value為具體交易數據的哈希值，而在KMPT中，Key為數據Key值，Value為Key記錄最新版本所在TMPT根哈希值，即LatestTMPTRoot。

1.2.2 索引構建

索引構建以區塊為單位，首先根據區塊內數據Key值構建塊內TMPT索引，塊內索引構建完成后將TMPT根哈希添加到區塊頭中。然后遍歷塊內數據記錄，以新建分支方式構建及更新KMPT，最后將KMPT根哈希添加到區塊頭中完成索引構建。相應的索引構建算法.

算法1. "索引構建算法：

輸入：已驗證交易集合transactionMap

輸出：Block

Begin：

TMPTRoot=1; //初始化TMPTRoot

for（Transaction tx： transactionMap）{ //遍歷交易集合

TMPTRoot=TMPT.insert（TMPTRoot，tx.key，tx）; //將tx插入交易樹TMPT中

} //塊內TMPT索引構建完畢

//構建全局KMPT索引

KMPTRoot=Blockchain.getCurrentBlock（）.KMPTRoot; //獲取當前最新塊KMPT根哈希

for（Transaction tx： transactionMap）{ //遍歷交易集合

KMPTRoot=KMPT.newBranch（KMPTRoot，tx.Key，TMPTRoot）;//將Key－TMPTRoot插入KMPT中

}

Block.TMPTRoot=TMPTRoot; //將TMPT根哈希添加到區塊頭中

Block.KMPTRoot=KMPTRoot; //將KMPT根哈希添加到區塊頭中

return Block;

End.

算法1構建塊內TMPT索引。首先初始化TMPT根，遍歷交易集合，將交易插入到塊內TMPT中，并記錄每次插入后的最新TMPTRoot，循環結束，此時塊內TMPT索引構建完畢。

構建全局KMPT索引。首先從當前系統中最新塊獲取最新KMPTRoot，遍歷交易集合，以當前KMPTRoot、當前交易Key值及已經構建好的本塊TMPT根哈希為參數，將該Key-TMPTRoot對以新建分支的方式插入到當前KMPT中，記錄插入后的KMPT根哈希。

最后循環結束，KMPT索引構建完畢，將構建完成后的最新TMPT及KMPT根哈希添加到區塊頭中，將區塊返回，即完成一個區塊的索引構建過程。

1.2.3 檢索過程

針對Key值進行的檢索，分為2個檢索過程。首先根據最新塊KMPT根哈希到當前KMPT全局狀態樹中檢索到目標Key對應狀態葉節點，從該葉節點中獲取到目標Key最新版本所在區塊TMPT根哈希，由此TMPTRoot開始進行塊內檢索。在TMPT和KMPT中的檢索過程均與前綴樹的匹配過程相同，不再贅述。需注意的是，檢索過程中需保存檢索路徑，以提供Merkle證明路徑，相應的Key記錄最新版本檢索算法如下。

算法2. "Key記錄最新版本檢索算法

輸入：Key

輸出：lt;transaction，pathgt; Key對應數據記錄最新版本及驗證路徑

Begin：

Stack path; //用棧保存Merkle驗證路徑

Block=Blockchain.getCurrentBlock（）; //獲取當前最新塊

KMPTRoot=Block.KMPTRoot; //獲取最新塊中KMPT根哈希

Leafnode=KMPT.Find（Key，KMPTRoot，path）; //在KMPT中檢索Key對應葉節點

if（Leafnode==1） //若Key對應記錄不存在

return lt;1，pathgt;; //返回空的記錄及KMPT檢索路徑

else{ //若Key記錄存在

target_TMPTRoot=Leafnode.Latest TMPTRoot; //從該葉節點中獲取到Key記錄最新版本所在區塊的TMPTRoot

path.clear（）; //將棧path清空

transaction=TMPT.Find（Key，target_TMPTRoot，path）; //塊內檢索目標Key記錄

return lt;transaction，pathgt;; //返回目標Key記錄和塊內TMPT檢索路徑

}

End.

算法2創建一個用于保存檢索路徑的棧path，以進行Merkle存在性和不存在性證明。獲取系統當前最新塊，并獲取最新塊中保存的當前KMPT根哈希，由此根哈希在KMPT全局狀態索引樹中檢索到目標Key狀態節點Keynode，并將在KMPT中的檢索路徑保存在path中。若該Key記錄不存在，即KMPT中無該Key對應的狀態節點，此時將返回一個空的交易記錄和在KMPT中的檢索路徑path，此path可用于對該Key記錄的不存在性證明。若該Key記錄存在，從在KMPT中查詢到的狀態節點中獲取該Key最新版本所在區塊中的交易記錄TMPT根哈希，由于此時Key存在，則不再需要path中保存的用于不存在證明的KMPT檢索路徑，隨后將path清空，然后根據獲取到的TMPT根哈希在目標區塊中檢索目標Key記錄，同時將塊內檢索路徑保存在path中，用于該Key的最新版本存在性的證明。將檢索到的目標Key記錄和塊內檢索路徑返回。

基于全局Key記錄狀態索引模型，檢索目標Key對應數據記錄時，可根據最新塊KMPTRoot在KMPT樹中檢索到目標Key記錄最新版本所在區塊交易樹TMPT根哈希，直接開始塊內檢索，避免了遍歷區塊檢索方式帶來的大量無效搜索，節省了查詢過程的時間消耗。

此外，在索引模型中，若Key對應數據記錄存在，塊內TMPT檢索的過程即是提供Key最新版本記錄Merkle存在性證明路徑的過程；若Key不存在，則在KMPT中的檢索過程即是提供Key記錄不存在證明路徑的過程。因此，可提供基于Key值查詢的數據存在性和不存在性的證明。

針對查詢最新版本的存在性證明與其他區塊鏈系統中的Merkle存在性證明類似，這里僅針對不存在性證明進行說明。如圖4所示，KMPT中存儲有Key為a711355、a77d337、a7f9365、a77d397的4個Key記錄狀態信息，對某個不存在的Key為a77d367的記錄查詢，需提供其不存在證明。由前綴樹的特性可知，某Key記錄在樹中的位置僅由Key值決定，即若該Key為a77d367的記錄存在，則必存在于圖中虛線節點處，為證明其不存在，則將該虛線節點所在分支發給輕節點驗證即可。

如算法2所述，在對該Key的KMPT檢索過程中，將其檢索路徑保存于path＝｛P1，P2，P3，P4｝中，輕節點接收到該分支路徑path后，首先計算P1節點哈希，并將其與自身存儲最新區塊頭中KMPTRoot對比，一致則P1有效，開始對該Key為a77d367的記錄進行前綴匹配以檢驗分支，為防止分支遭到篡改，在匹配過程中需驗證其有效性，即匹配P2之前先計算其哈希值，將其與P1中Next node域中的哈希值比較，一致則P2有效，對P2進行匹配；用同樣的方法驗證P3和P4；驗證P4有效，即說明該分支有效，對P4匹配失敗，即證明Key為a77d367的記錄確實不存在，完成不存在性證明的過程。

數據可溯源是區塊鏈的重要特性，在不同場景中區塊鏈數據溯源的含義有所區別：在數字資產領域，數據溯源一般指追溯出某筆數字資產的歷史流轉過程，即價值流轉軌跡；在本文所屬的區塊鏈數據庫領域，數據溯源是指追溯出某數據記錄的所有歷史版本，即數據修改軌跡。基于本文索引模型可實現對Key記錄的所有歷史修改版本進行溯源查詢，具體溯源查詢算法如下。

算法3. "Key記錄溯源查詢算法：

輸入：Key

輸出：Key記錄所有歷史版本transactionList

Begin：

List transactionList; //創建transactionList保存查詢結果

lt;transaction，pathgt;=Blockchain.Find（Key）; //查詢到Key記錄最新版本

if（transaction==1） //Key對應記錄不存在

return 1； //返回空值結束程序

else{

transactionList.add（transaction）; //將Key最新版加入transactionList

temp=transaction.Prehash; //獲取上一版本記錄哈希值

While（temp！=1）{

transaction=LevelDB.get（temp）; //從LevelDB中讀取上一版本記錄具體信息

transactionList.add（transaction）; //將讀取出的記錄加入transactionList

temp=transaction.Prehash; //繼續獲取上一版本記錄哈希值

}

}

return transactionList; //最后返回Key記錄所有歷史版本transactionList

End.

算法3創建用于保存溯源查詢結果的交易數據記錄列表，在系統中查詢Key對應的最新版本記錄，若查詢Key對應記錄不存在，則返回空值并結束程序，若查詢Key記錄存在，首先將查詢到的Key最新版本存入transactionList中，再獲取上一版本的記錄哈希值，若哈希值不為空值，則從LevelDB中取出上一版本交易記錄，存入transactionList，繼續獲取上一版本記錄哈希，重復此過程，直到上一版本記錄哈希為空值，即完成所有歷史版本的溯源查詢，最后返回保存的記錄列表，結束。

1.2.4 檢索效率分析

區塊鏈由一個個區塊根據哈希指針鏈接形成，本質上屬于單鏈表結構，假設區塊鏈中有N個區塊，每個區塊中包含M筆數據記錄。傳統基于Merkle樹結構的區塊鏈由于沒有提供高效的檢索方法，查詢某一特定Key值記錄需遍歷搜索所有區塊和區塊中的數據，這一過程時間復雜度為

。

而塊內索引方法由于在區塊內基于Merkle樹構建關鍵字索引，將在塊內的檢索過程時間復雜度降到了對數級別，但由于無法避免遍歷區塊過程，故其時間復雜度為

。

索引方法引入了基于狀態樹的KMPT全局區塊索引結構，避免了遍歷區塊的檢索過程，只需在最新KMPT樹中檢索到目標區塊后，直接在目標區塊TMPT樹中進行塊內檢索，將2個過程的時間復雜度都降到了對數級別，即索引模型的檢索時間復雜度為

。

顯然，

。

即索引模型的檢索時間復雜度在理論上要明顯低于傳統基于Merkle樹方法和塊內索引優化方法，具有更高的檢索效率。

2 實""驗

實驗采用的硬件環境為Intel（R） Core（TM） i5-7300HQ CPU（2.50 GHz），RAM（8 GB），操作系統Windows 10，參考Bitcoin開源代碼v0.1.0和以太坊開源代碼Geth v1.8.0，使用Java語言構建實驗代碼，底層數據庫使用LevelDB，主要針對交易格式、交易塊內組織形式、狀態樹結構等底層數據結構進行修改，實現本文索引模型。同時，將Blockchain DB模型中的Merkle RB tree方法作為塊內索引方法的代表，以及Merkle tree方法作為傳統區塊鏈系統的代表，與提出方法進行對比實驗。由于研究屬于區塊鏈全節點中的查詢方法，不涉及網絡多節點間共識，所以在單機上進行實驗，并將區塊數據記錄有效性驗證過程視為共識的過程。實驗中的主要指標為算法運行時間，并將算法獨立運行50次的平均值定義為算法的運行時間。實驗數據固定2個數據字段，分別為Key和Field1兩個域，其中Key為數據的關鍵字，每條數據記錄的Field1域設置值為該記錄所在區塊的區塊號。實驗使用的數據集為自采數據集，公開在https：//gitee.com/huang_li_huang/blockchain_query.git中。

2.1 區塊深度對于查詢時間的影響

實驗1.數據存儲時以區塊為單位按照時間順序添加到鏈上，再持久化存儲到LevelDB中。對某一關鍵字為Key的記錄查詢需返回其最新版本。當系統中最新區塊的塊高度為h₁，目標數據最新版本所在區塊高度為h₂時，定義區塊深度為。本實驗的目的是探究目標數據最新版本所在區塊深度對查詢時間的影響情況。實驗中順序寫入100萬條Key升序（Key為0～999 999）的數據記錄，每個區塊設置存儲1 000條數據記錄，總共1 000個區塊，當查詢目標交易所在區塊深度為時，對比Merkle tree、Merkle RB tree及本文索引方法所需查詢時間，實驗結果見圖5。

由實驗結果可知，Merkle tree方法和Merkle RB tree方法的查詢時間隨目標Key記錄最新版本所在區塊深度呈線性增加的趨勢，這是由于Merkle tree并沒有提供高效的查詢方法，檢索需從最新區塊開始遍歷，在區塊內部同樣也采用遍歷交易列表的方式，檢索時間復雜度為，當目標Key記錄所在區塊深度較深時，需在最新塊和目標塊之間的區塊中做大量的無效檢索，查詢時間隨區塊深度線性增長；而Merkle RB tree由于使用紅黑樹優化了塊內檢索方式，在塊內不需遍歷交易列表查詢，將塊內檢索的時間從線性降到了對數級別，其檢索時間復雜度為，比Merkle tree方法的檢索效率更高。但由于無法確定目標數據所在區塊，檢索還需采用遍歷區塊方式進行，且遍歷區塊過程不斷進行磁盤讀寫，大大限制了檢索的效率，使查詢時間仍隨區塊深度線性增加；而基于提出的索引模型KMPT，可從最新塊中的KMPT樹根開始，檢索到目標Key記錄所在區塊中的TMPT根，實現了定位目標塊的效果，避開了遍歷區塊不斷讀寫磁盤的檢索過程，同時在塊內使用TMPT結構加速塊內檢索速度，無需遍歷交易列表，將時間復雜度降到，因此，查詢基本不受區塊深度的影響，可在很短的時間內穩定完成檢索任務。

2.2 目標Key不存在情況下查詢響應時間與區塊數的關系

實驗2.本實驗的目的是探究極端情況下，查詢目標Key不存在時3種方法的查詢響應時間。同實驗1，順序寫入Key升序數據記錄，每個區塊設置存儲1 000筆數據記錄，當系統中總區塊數為100（Key為0～99"999）、200（Key為0～199 999）、300（Key為0～299 999）……1 000（Key為0～999 999）時，輸入一個不存在的目標Key值，對比測試3種方法查詢響應時間。實驗結果如圖6所示。

由于查詢目標Key值不存在，Merkle tree和Merkle RB tree方法需遍歷檢索完全部區塊數據才可返回不存在信息，與實驗1類似，兩者查詢響應時間都隨系統區塊數線性增長，其中Merkle RB tree方法由于加快了塊內檢索的速度，將檢索時間從Merkle tree方法的降到了，所以響應時間比Merkle tree方法更短，但受制于其遍歷區塊檢索時需不斷進行磁盤讀寫，導致這一優化結果并不明顯。不同于前兩者，基于本文索引模型的方法當查詢目標Key值不存在時，只需根據最新塊KMPTRoot到當前最新KMPT樹中檢索，不需遍歷檢索區塊數據，即可返回不存在響應及不存在證明路徑，且這一過程不需進行塊內檢索，時間開銷比檢索數據存在時的更低，因此在很短時間內便可返回查詢不存在響應，且響應時間受區塊數的影響微乎其微，在提升了查詢不存在可信性的同時具有更高效更穩定的表現。

2.3 數據溯源查詢效率對比

實驗3.在Blockchain DB模型中，數據溯源指查詢出某特定Key記錄所有歷史版本，以追溯出該Key記錄數據的修改軌跡。溯源查詢需先查詢到目標Key最新版本，再由最新版本中Prehash依次追溯出該Key的所有歷史版本，即分為最新版本查詢和追溯歷史版本2個過程，因此溯源查詢時間與最新版本的查詢時間相關。在Merkle RB tree方法中，最新版本的查詢時間受目標數據所在區塊深度影響，為對比Merkle RB tree方法與本文KMPT方法在追溯歷史版本上的效率，實驗中首先設置每個區塊中都寫入Key為0～999標識的數據，每條數據Field1域中的值為該數據所在區塊號，以此來模擬數據版本的更新，對比測試歷史版本數分別為10，20，30，...，100時，Merkle RB tree方法與提出的索引模型方法溯源查詢時間。實驗結果如圖7所示。

由圖7可知，Merkle RB tree方法與KMPT方法溯源查詢時間主要集中于最新版本的查詢時間，由于兩者都通過數據記錄中的Prehash追溯歷史版本，且這一過程的時間消耗都由底層數據庫Level DB決定，因此具有相近的歷史版本追溯效率，此外可知歷史版本數對溯源查詢的時間影響較小。

由于溯源查詢受最新版本查詢時間影響，且歷史版本數對溯源查詢的時間影響較小，實驗繼續探究最新版本所在區塊深度對溯源查詢時間的影響。首先為每個Key記錄設置100個歷史版本，測試當其最新版本所在區塊深度為100，200，300...1 000時，對比Merkle RB tree方法與本文方法溯源查詢的效率。

實驗結果如圖8所示，由于兩者溯源查詢時間主要集中于最新版本的查詢時間，由實驗1可知，Merkle RB tree方法最新版本查詢時間隨區塊深度線性增加，而本文方法最新版本的查詢基本不受區塊深度影響，故當最新版本所在區塊深度增加時，Merkle RB tree方法溯源查詢總時間線性增加，而KMPT方法溯源查詢仍不受影響，查詢效率遠高于Merkle RB tree方法，即本文索引模型由于提高了最新版本的查詢效率，且查詢時間與最新版本所在區塊深度無關，相比塊內Merkle RB tree索引方法而言，有更高更穩定的溯源查詢效率。

2.2.4 索引構建代價對比

實驗4.索引的更新以區塊為單位，區塊內包含的數據數量決定了單塊索引的構建時間，實驗中通過向區塊鏈數據庫中寫入不同大小的塊，即包含1 000，2 000，3 000，...，8 000條數據的區塊，探究對比在不同數據數量下Merkle RB tree方法與本文索引構建的時間代價情況。實驗結果如圖9所示。

本文索引方法與Merkle RB tree方法單區塊索引構建時間都隨區塊數據量增大而增加，且本文方法的構建時間比Merkle RB tree方法更長，這是由于本文索引模型在構建塊內索引的基礎上增加了全局KMPT索引結構，故相比于單純的塊內索引模型Merkle RB tree來說，構建索引的時間開銷有所增加。但與查詢效率、查詢可信性及穩定性的極大提升相比，單塊索引構建的時間代價付出維持在毫秒級別，沒有為系統帶來過大的額外負擔。即本文索引模型在可接受的代價范圍內，實現了查詢效率、查詢穩定性和查詢可信性的極大提升。

3 結束語

目前在區塊鏈內置索引查詢優化方法中，由于無法確定目標數據所在區塊，檢索需遍歷區塊進行，導致查詢效率低下。針對這一問題，在Blockchain DB數據模型的基礎上，基于以太坊狀態樹結構提出一種全局狀態索引模型，在保證索引及數據不可篡改的前提下，實現根據檢索Key值直接定位目標數據所在區塊，避免了遍歷區塊檢索的過程，大大提升了最新版本記錄的檢索時間，且查詢可同時提供數據存在和不存在性的證明，提升了查詢可信性。最后，通過實驗測試，與Blockchain DB模型中以Merkle RB tree為代表的塊內檢索方法相比，本文索引模型在數據最新版本查詢、數據不存在響應、數據溯源查詢上具有更高更穩定的查詢效率。

區塊鏈數據庫致力于在不互信的多節點環境中建立可信的數據存儲環境，這對數據存儲安全有重大意義。在確保數據安全、不可篡改、可信性等特性不受損失的前提下，研究如何提升區塊鏈數據庫的讀寫性能，是發揮其重大應用價值的關鍵。目前對區塊鏈數據寫入（共識算法）的研究已取得很多不錯的進展，然而在對其讀性能即查詢檢索方面的研究則相對較少，有關區塊鏈數據查詢還需很多后續工作，如研究如何更高效地實現更多的查詢功能以豐富查詢語義，如范圍查詢、Top-K查詢等。此外，研究新型區塊鏈數據結構如DAG下的高效查詢，在未來也具有重要的應用價值。

參考文獻

［1］""Nakamoto S. Bitcoin： a peer-to-peer electronic cash system [EB/OL]. [2021-05-12]. https：//www.bitcoinpaper.info/bitcoinpaper-html/.

［2］""Buterin V. Ethereum： a next-generation smart contract and decentralized application platform[EB/OL]. [2021-05-12]. https：//courses.cs.duke.edu/spring23/compsci512/papers/ethereum.pdf.

［3］""袁勇， 王飛躍. 區塊鏈技術發展現狀與展望[J]. 自動化學報， 2016， 42（4）： 481-494.

Yuan Y， Wang F. Blockchain： the state of the art and future trends[J]. Acta Automatica Sinica， 2016， 42（4）： 481-494. （in Chinese）

［4］""Bamakan S M H， Motavali A， Bondarti A B. A survey of blockchain consensus algorithms performance evaluation criteria[J]. Expert Systems With Applications， 2020， 154： 113385.

［5］""Tikhomirov S. Ethereum： state of knowledge and research perspectives[C]//International Symposium on Foundations and Practice of Security. Cham： Springer， 2018： 206-221.

［6］""Wood G. Ethereum： a secure decentralised generalised transaction ledger[EB/OL]. [2021-05-12]. https：//www.win.tue.nl/～mholende/seminar/references/ethereum_yellowpaper.pdf.

［7］""于戈， 聶鐵錚， 李曉華， 等. 區塊鏈系統中的分布式數據管理技術： 挑戰與展望[J]. 計算機學報， 2021， 44（1）： 28-54.

Yu G， Nie T Z， Li X H， et al. The challenge and prospect of distributed data management techniques in blockchain systems[J]. Chinese Journal of Computers， 2021， 44（1）： 28-54. （in Chinese）

［8］""王千閣， 何蒲， 聶鐵錚， 等. 區塊鏈系統的數據存儲與查詢技術綜述[J]. 計算機科學， 2018， 45（12）： 12-18.

Wang Q G， He P， Nie T Z， et al. Survey of data storage and query techniques in blockchain systems[J]. Computer Science， 2018， 45（12）： 12-18. （in Chinese）

［9］""Li Y， Zheng K， Yan Y， et al. EtherQL： a query layer for blockchain system[C]//International Conference on Database Systems for Advanced Applications. Cham： Springer， 2017： 556-567.

［10］""Muzammal M， Qu Q， Nasrulin B， et al. A blockchain database application platform[EB/OL]. 2018 [2021-05-12]. https：//arxiv.org/abs/1808.05199.

［11］""Peng Y Q， Du M， Li F F， et al. FalconDB： blockchain-based collaborative database[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data， June 14-19， 2020， Portland， OR， USA. New York： ACM， 2020： 637-652.

［12］""焦通， 申德榮， 聶鐵錚， 等. 區塊鏈數據庫： 一種可查詢且防篡改的數據庫[J]. 軟件學報， 2019， 30（9）： 2671-2685.

Jiao T， Shen D R， Nie T Z， et al. BlockchainDB： querable and immutable database[J]. Journal of Software， 2019， 30（9）： 2671-2685. （in Chinese）

［13］""賈大宇， 信俊昌， 王之瓊， 等. 存儲容量可擴展區塊鏈系統的高效查詢模型[J]. 軟件學報， 2019， 30（9）： 2655-2670.

Jia D Y， Xin J C， Wang Z Q， et al. Efficient query model for storage capacity scalable blockchain system[J]. Journal of Software， 2019， 30（9）： 2655-2670. （in Chinese）

［14］""Zhang C， Xu C， Xu J L， et al. GEM^2-tree： a gas-efficient structure for authenticated range queries in blockchain[C]//2019 IEEE 35th International Conference on Data Engineering （ICDE）， April 8-11， 2019， Macao， China. IEEE， 2019： 842-853.

［15］""鄭浩瀚， 申德榮， 聶鐵錚， 等. 面向混合索引的區塊鏈系統的可查詢性優化[J]. 計算機科學， 2020， 47（10）： 301-308.

Zheng H H， Shen D R， Nie T Z， et al. Queryability optimization of blockchain system for hybrid index[J]. Computer Science， 2020， 47（10）： 301-308. （in Chinese）

［16］""Abdennebi A， Kaya K. A bloom filter survey： variants for different domain applications[EB/OL]. 2021-06-23 [2021-07-12]. https：//arxiv.org/abs/2106.12189.

（編輯""羅敏）