基于狀態(tài)樹的鏈上數(shù)據(jù)高效可信查詢索引模型及方法

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

關(guān)鍵詞：區(qū)塊鏈數(shù)據(jù)查詢；區(qū)塊鏈內(nèi)容檢索；可信索引模型；不可篡改索引；狀態(tài)樹

中圖分類號：TP311 """"""""""文獻(xiàn)標(biāo)志碼：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]等加密貨幣的興起，其底層區(qū)塊鏈技術(shù)得到了越來越多的關(guān)注。區(qū)塊鏈以其去中心化、不可篡改、多方共享以及可回溯特性^[3]為解決數(shù)據(jù)可信存儲問題提供了新的可能。在區(qū)塊鏈中，共識算法負(fù)責(zé)數(shù)據(jù)的寫入，在如何提升共識算法效率方面，目前已有很多研究并且取得了不錯的成效^[4]，但在對區(qū)塊鏈數(shù)據(jù)庫的讀性能，即查詢處理方面的研究相對較少。現(xiàn)有的區(qū)塊鏈系統(tǒng)在數(shù)據(jù)查詢處理方面仍暴露出很大的局限性，如比特幣系統(tǒng)中僅支持根據(jù)交易哈希值查詢具體交易，而無法針對交易的具體細(xì)節(jié)展開查詢；以太坊支持賬戶查詢，由于其引入了狀態(tài)樹^[5]維護(hù)全局賬戶狀態(tài)^[6]，可根據(jù)賬戶地址對賬戶狀態(tài)進(jìn)行高效的查詢，但狀態(tài)樹本身與交易并無關(guān)聯(lián)，查詢交易數(shù)據(jù)仍需通過交易哈希值進(jìn)行查詢。在面向區(qū)塊鏈中數(shù)據(jù)的查詢處理優(yōu)化技術(shù)方面，于戈等^[7]首先提出將區(qū)塊鏈用于解決不可信環(huán)境下的分布式數(shù)據(jù)管理問題，深入討論了區(qū)塊鏈系統(tǒng)與傳統(tǒng)分布式數(shù)據(jù)庫之間的異同點(diǎn)，系統(tǒng)地總結(jié)了目前區(qū)塊鏈系統(tǒng)在數(shù)據(jù)存儲結(jié)構(gòu)、查詢處理方面的優(yōu)化技術(shù)。王千閣等^[8]總結(jié)了當(dāng)前區(qū)塊鏈系統(tǒng)因數(shù)據(jù)存儲模式限制而普遍面臨著查詢功能簡單、查詢性能較低等嚴(yán)重問題，深入研究了區(qū)塊鏈系統(tǒng)數(shù)據(jù)存儲與查詢優(yōu)化之間的關(guān)系。

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

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

綜上所述，目前區(qū)塊鏈數(shù)據(jù)查詢處理研究存在如下局限。

1）外聯(lián)數(shù)據(jù)庫方法無法保證數(shù)據(jù)不可篡改性，損失了區(qū)塊鏈特性，同時給系統(tǒng)帶來了額外的存儲負(fù)擔(dān)，沒有從根本上解決區(qū)塊鏈系統(tǒng)的查詢問題。

2）內(nèi)置索引方法僅針對塊內(nèi)數(shù)據(jù)構(gòu)建索引，無法確定目標(biāo)數(shù)據(jù)所在區(qū)塊。因此，需遍歷區(qū)塊進(jìn)行檢索，難以避免在大量無關(guān)區(qū)塊中的無效搜索過程，大大降低了查詢檢索的效率。

3）當(dāng)目標(biāo)數(shù)據(jù)不存在時，僅使用塊內(nèi)索引方法查詢響應(yīng)慢，且無法向輕節(jié)點(diǎn)提供數(shù)據(jù)不存在證明，查詢結(jié)果的正確性無法驗(yàn)證，查詢可信性差。

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

1）針對內(nèi)置索引方法在檢索中如何避免遍歷區(qū)塊的問題，基于以太坊狀態(tài)樹設(shè)計(jì)了一種針對區(qū)塊鏈中數(shù)據(jù)內(nèi)容的不可篡改全局區(qū)塊索引，一次鎖定目標(biāo)塊，避免了遍歷無關(guān)區(qū)塊檢索的過程，結(jié)合塊內(nèi)索引，極大提升了基于數(shù)據(jù)內(nèi)容對區(qū)塊鏈數(shù)據(jù)記錄的檢索效率。

2）基于提出的索引模型，可同時向輕節(jié)點(diǎn)提供查詢目標(biāo)數(shù)據(jù)存在性和不存在性證明，提升了查詢可信性。

1 索引模型

1.1 數(shù)據(jù)及數(shù)據(jù)操作定義

為解決現(xiàn)有區(qū)塊鏈系統(tǒng)中數(shù)據(jù)模型單一問題，Blockchain DB^[13]模型中將交易數(shù)據(jù)結(jié)構(gòu)擴(kuò)展到任意記錄格式。筆者在Blockchain DB數(shù)據(jù)模型的基礎(chǔ)上研究查詢方法，將該模型中的數(shù)據(jù)和數(shù)據(jù)操作定義如下。

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

為使區(qū)塊鏈中數(shù)據(jù)更具一般化，將原有交易結(jié)構(gòu)重新定義。如圖1所示，交易由交易頭（transaction）和數(shù)據(jù)（data）組成。數(shù)據(jù)記錄兩者表述等價(jià)。

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

1.1.2 數(shù)據(jù)操作

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

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

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

刪除記錄：數(shù)據(jù)一旦寫入便無法刪除。

1.2 索引模型

索引模型如圖2所示，分為塊內(nèi)TMPT索引和全局狀態(tài)索引KMPT，TMPT與KMPT都基于以太坊MPT結(jié)構(gòu)實(shí)現(xiàn)。與以太坊中交易樹和狀態(tài)樹類似，TMPT組織塊內(nèi)數(shù)據(jù)記錄，而KMPT維護(hù)全局Key記錄狀態(tài)。所不同的是，以太坊中交易樹是由塊內(nèi)交易序號構(gòu)建的MPT，狀態(tài)樹是由賬戶地址編碼構(gòu)建的MPT，而本文中TMPT與KMPT都是根據(jù)數(shù)據(jù)記錄Key值來構(gòu)建的。

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

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

1.2.1 數(shù)據(jù)插入

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

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

如圖3-②所示，插入lt;a77d337，value2gt;，由于該Key與a711355共享前綴a7，故創(chuàng)建共享前綴為a7的擴(kuò)展節(jié)點(diǎn)為根節(jié)點(diǎn)，且創(chuàng)建一個分支節(jié)點(diǎn)鏈接兩個葉節(jié)點(diǎn)。

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

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

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

葉節(jié)點(diǎn)

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

擴(kuò)展節(jié)點(diǎn)

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

分支節(jié)點(diǎn)

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

分支節(jié)點(diǎn)哈希值的計(jì)算方法是將存儲的每個子節(jié)點(diǎn)哈希值與節(jié)點(diǎn)Value中存儲的值一起進(jìn)行哈希，最后得到該分支節(jié)點(diǎn)哈希值，若存儲哈希值為空，則使用空字節(jié)參與運(yùn)算。

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

1.2.2 索引構(gòu)建

索引構(gòu)建以區(qū)塊為單位，首先根據(jù)區(qū)塊內(nèi)數(shù)據(jù)Key值構(gòu)建塊內(nèi)TMPT索引，塊內(nèi)索引構(gòu)建完成后將TMPT根哈希添加到區(qū)塊頭中。然后遍歷塊內(nèi)數(shù)據(jù)記錄，以新建分支方式構(gòu)建及更新KMPT，最后將KMPT根哈希添加到區(qū)塊頭中完成索引構(gòu)建。相應(yīng)的索引構(gòu)建算法.

算法1. "索引構(gòu)建算法：

輸入：已驗(yàn)證交易集合transactionMap

輸出：Block

Begin：

TMPTRoot=1; //初始化TMPTRoot

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

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

} //塊內(nèi)TMPT索引構(gòu)建完畢

//構(gòu)建全局KMPT索引

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

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

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

}

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

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

return Block;

End.

算法1構(gòu)建塊內(nèi)TMPT索引。首先初始化TMPT根，遍歷交易集合，將交易插入到塊內(nèi)TMPT中，并記錄每次插入后的最新TMPTRoot，循環(huán)結(jié)束，此時塊內(nèi)TMPT索引構(gòu)建完畢。

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

最后循環(huán)結(jié)束，KMPT索引構(gòu)建完畢，將構(gòu)建完成后的最新TMPT及KMPT根哈希添加到區(qū)塊頭中，將區(qū)塊返回，即完成一個區(qū)塊的索引構(gòu)建過程。

1.2.3 檢索過程

針對Key值進(jìn)行的檢索，分為2個檢索過程。首先根據(jù)最新塊KMPT根哈希到當(dāng)前KMPT全局狀態(tài)樹中檢索到目標(biāo)Key對應(yīng)狀態(tài)葉節(jié)點(diǎn)，從該葉節(jié)點(diǎn)中獲取到目標(biāo)Key最新版本所在區(qū)塊TMPT根哈希，由此TMPTRoot開始進(jìn)行塊內(nèi)檢索。在TMPT和KMPT中的檢索過程均與前綴樹的匹配過程相同，不再贅述。需注意的是，檢索過程中需保存檢索路徑，以提供Merkle證明路徑，相應(yīng)的Key記錄最新版本檢索算法如下。

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

輸入：Key

輸出：lt;transaction，pathgt; Key對應(yīng)數(shù)據(jù)記錄最新版本及驗(yàn)證路徑

Begin：

Stack path; //用棧保存Merkle驗(yàn)證路徑

Block=Blockchain.getCurrentBlock（）; //獲取當(dāng)前最新塊

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

Leafnode=KMPT.Find（Key，KMPTRoot，path）; //在KMPT中檢索Key對應(yīng)葉節(jié)點(diǎn)

if（Leafnode==1） //若Key對應(yīng)記錄不存在

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

else{ //若Key記錄存在

target_TMPTRoot=Leafnode.Latest TMPTRoot; //從該葉節(jié)點(diǎn)中獲取到Key記錄最新版本所在區(qū)塊的TMPTRoot

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

transaction=TMPT.Find（Key，target_TMPTRoot，path）; //塊內(nèi)檢索目標(biāo)Key記錄

return lt;transaction，pathgt;; //返回目標(biāo)Key記錄和塊內(nèi)TMPT檢索路徑

}

End.

算法2創(chuàng)建一個用于保存檢索路徑的棧path，以進(jìn)行Merkle存在性和不存在性證明。獲取系統(tǒng)當(dāng)前最新塊，并獲取最新塊中保存的當(dāng)前KMPT根哈希，由此根哈希在KMPT全局狀態(tài)索引樹中檢索到目標(biāo)Key狀態(tài)節(jié)點(diǎn)Keynode，并將在KMPT中的檢索路徑保存在path中。若該Key記錄不存在，即KMPT中無該Key對應(yīng)的狀態(tài)節(jié)點(diǎn)，此時將返回一個空的交易記錄和在KMPT中的檢索路徑path，此path可用于對該Key記錄的不存在性證明。若該Key記錄存在，從在KMPT中查詢到的狀態(tài)節(jié)點(diǎn)中獲取該Key最新版本所在區(qū)塊中的交易記錄TMPT根哈希，由于此時Key存在，則不再需要path中保存的用于不存在證明的KMPT檢索路徑，隨后將path清空，然后根據(jù)獲取到的TMPT根哈希在目標(biāo)區(qū)塊中檢索目標(biāo)Key記錄，同時將塊內(nèi)檢索路徑保存在path中，用于該Key的最新版本存在性的證明。將檢索到的目標(biāo)Key記錄和塊內(nèi)檢索路徑返回。

基于全局Key記錄狀態(tài)索引模型，檢索目標(biāo)Key對應(yīng)數(shù)據(jù)記錄時，可根據(jù)最新塊KMPTRoot在KMPT樹中檢索到目標(biāo)Key記錄最新版本所在區(qū)塊交易樹TMPT根哈希，直接開始塊內(nèi)檢索，避免了遍歷區(qū)塊檢索方式帶來的大量無效搜索，節(jié)省了查詢過程的時間消耗。

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

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

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

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

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

輸入：Key

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

Begin：

List transactionList; //創(chuàng)建transactionList保存查詢結(jié)果

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

if（transaction==1） //Key對應(yīng)記錄不存在

return 1； //返回空值結(jié)束程序

else{

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

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

While（temp！=1）{

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

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

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

}

}

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

End.

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

1.2.4 檢索效率分析

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

。

而塊內(nèi)索引方法由于在區(qū)塊內(nèi)基于Merkle樹構(gòu)建關(guān)鍵字索引，將在塊內(nèi)的檢索過程時間復(fù)雜度降到了對數(shù)級別，但由于無法避免遍歷區(qū)塊過程，故其時間復(fù)雜度為

。

索引方法引入了基于狀態(tài)樹的KMPT全局區(qū)塊索引結(jié)構(gòu)，避免了遍歷區(qū)塊的檢索過程，只需在最新KMPT樹中檢索到目標(biāo)區(qū)塊后，直接在目標(biāo)區(qū)塊TMPT樹中進(jìn)行塊內(nèi)檢索，將2個過程的時間復(fù)雜度都降到了對數(shù)級別，即索引模型的檢索時間復(fù)雜度為

。

顯然，

。

即索引模型的檢索時間復(fù)雜度在理論上要明顯低于傳統(tǒng)基于Merkle樹方法和塊內(nèi)索引優(yōu)化方法，具有更高的檢索效率。

2 實(shí)""驗(yàn)

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

2.1 區(qū)塊深度對于查詢時間的影響

實(shí)驗(yàn)1.數(shù)據(jù)存儲時以區(qū)塊為單位按照時間順序添加到鏈上，再持久化存儲到LevelDB中。對某一關(guān)鍵字為Key的記錄查詢需返回其最新版本。當(dāng)系統(tǒng)中最新區(qū)塊的塊高度為h₁，目標(biāo)數(shù)據(jù)最新版本所在區(qū)塊高度為h₂時，定義區(qū)塊深度為。本實(shí)驗(yàn)的目的是探究目標(biāo)數(shù)據(jù)最新版本所在區(qū)塊深度對查詢時間的影響情況。實(shí)驗(yàn)中順序?qū)懭?00萬條Key升序（Key為0～999 999）的數(shù)據(jù)記錄，每個區(qū)塊設(shè)置存儲1 000條數(shù)據(jù)記錄，總共1 000個區(qū)塊，當(dāng)查詢目標(biāo)交易所在區(qū)塊深度為時，對比Merkle tree、Merkle RB tree及本文索引方法所需查詢時間，實(shí)驗(yàn)結(jié)果見圖5。

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

2.2 目標(biāo)Key不存在情況下查詢響應(yīng)時間與區(qū)塊數(shù)的關(guān)系

實(shí)驗(yàn)2.本實(shí)驗(yàn)的目的是探究極端情況下，查詢目標(biāo)Key不存在時3種方法的查詢響應(yīng)時間。同實(shí)驗(yàn)1，順序?qū)懭隟ey升序數(shù)據(jù)記錄，每個區(qū)塊設(shè)置存儲1 000筆數(shù)據(jù)記錄，當(dāng)系統(tǒng)中總區(qū)塊數(shù)為100（Key為0～99"999）、200（Key為0～199 999）、300（Key為0～299 999）……1 000（Key為0～999 999）時，輸入一個不存在的目標(biāo)Key值，對比測試3種方法查詢響應(yīng)時間。實(shí)驗(yàn)結(jié)果如圖6所示。

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

2.3 數(shù)據(jù)溯源查詢效率對比

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

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

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

實(shí)驗(yàn)結(jié)果如圖8所示，由于兩者溯源查詢時間主要集中于最新版本的查詢時間，由實(shí)驗(yàn)1可知，Merkle RB tree方法最新版本查詢時間隨區(qū)塊深度線性增加，而本文方法最新版本的查詢基本不受區(qū)塊深度影響，故當(dāng)最新版本所在區(qū)塊深度增加時，Merkle RB tree方法溯源查詢總時間線性增加，而KMPT方法溯源查詢?nèi)圆皇苡绊懀樵冃蔬h(yuǎn)高于Merkle RB tree方法，即本文索引模型由于提高了最新版本的查詢效率，且查詢時間與最新版本所在區(qū)塊深度無關(guān)，相比塊內(nèi)Merkle RB tree索引方法而言，有更高更穩(wěn)定的溯源查詢效率。

2.2.4 索引構(gòu)建代價(jià)對比

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

本文索引方法與Merkle RB tree方法單區(qū)塊索引構(gòu)建時間都隨區(qū)塊數(shù)據(jù)量增大而增加，且本文方法的構(gòu)建時間比Merkle RB tree方法更長，這是由于本文索引模型在構(gòu)建塊內(nèi)索引的基礎(chǔ)上增加了全局KMPT索引結(jié)構(gòu)，故相比于單純的塊內(nèi)索引模型Merkle RB tree來說，構(gòu)建索引的時間開銷有所增加。但與查詢效率、查詢可信性及穩(wěn)定性的極大提升相比，單塊索引構(gòu)建的時間代價(jià)付出維持在毫秒級別，沒有為系統(tǒng)帶來過大的額外負(fù)擔(dān)。即本文索引模型在可接受的代價(jià)范圍內(nèi)，實(shí)現(xiàn)了查詢效率、查詢穩(wěn)定性和查詢可信性的極大提升。

3 結(jié)束語

目前在區(qū)塊鏈內(nèi)置索引查詢優(yōu)化方法中，由于無法確定目標(biāo)數(shù)據(jù)所在區(qū)塊，檢索需遍歷區(qū)塊進(jìn)行，導(dǎo)致查詢效率低下。針對這一問題，在Blockchain DB數(shù)據(jù)模型的基礎(chǔ)上，基于以太坊狀態(tài)樹結(jié)構(gòu)提出一種全局狀態(tài)索引模型，在保證索引及數(shù)據(jù)不可篡改的前提下，實(shí)現(xiàn)根據(jù)檢索Key值直接定位目標(biāo)數(shù)據(jù)所在區(qū)塊，避免了遍歷區(qū)塊檢索的過程，大大提升了最新版本記錄的檢索時間，且查詢可同時提供數(shù)據(jù)存在和不存在性的證明，提升了查詢可信性。最后，通過實(shí)驗(yàn)測試，與Blockchain DB模型中以Merkle RB tree為代表的塊內(nèi)檢索方法相比，本文索引模型在數(shù)據(jù)最新版本查詢、數(shù)據(jù)不存在響應(yīng)、數(shù)據(jù)溯源查詢上具有更高更穩(wěn)定的查詢效率。

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

參考文獻(xiàn)

［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］""袁勇， 王飛躍. 區(qū)塊鏈技術(shù)發(fā)展現(xiàn)狀與展望[J]. 自動化學(xué)報(bào)， 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］""于戈， 聶鐵錚， 李曉華， 等. 區(qū)塊鏈系統(tǒng)中的分布式數(shù)據(jù)管理技術(shù)： 挑戰(zhàn)與展望[J]. 計(jì)算機(jī)學(xué)報(bào)， 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］""王千閣， 何蒲， 聶鐵錚， 等. 區(qū)塊鏈系統(tǒng)的數(shù)據(jù)存儲與查詢技術(shù)綜述[J]. 計(jì)算機(jī)科學(xué)， 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］""焦通， 申德榮， 聶鐵錚， 等. 區(qū)塊鏈數(shù)據(jù)庫： 一種可查詢且防篡改的數(shù)據(jù)庫[J]. 軟件學(xué)報(bào)， 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］""賈大宇， 信俊昌， 王之瓊， 等. 存儲容量可擴(kuò)展區(qū)塊鏈系統(tǒng)的高效查詢模型[J]. 軟件學(xué)報(bào)， 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］""鄭浩瀚， 申德榮， 聶鐵錚， 等. 面向混合索引的區(qū)塊鏈系統(tǒng)的可查詢性優(yōu)化[J]. 計(jì)算機(jī)科學(xué)， 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.

（編輯""羅敏）