基于學習索引的圖式區(qū)塊鏈高效可驗證查詢機制

常 健 林立成 李彬弘 肖 江 金 海

（華中科技大學計算機科學與技術學院 武漢 430074）

（大數(shù)據(jù)技術與系統(tǒng)國家地方聯(lián)合工程研究中心（華中科技大學）武漢 430074）

（服務計算技術與系統(tǒng)教育部重點實驗室（華中科技大學）武漢 430074）

（集群與網(wǎng)格計算湖北省重點實驗室（華中科技大學）武漢 430074）

（j_chang@hust.edu.cn）

區(qū)塊鏈技術具有分布式、去中心化和防篡改等特性，已被廣泛應用于數(shù)字金融、供應鏈等各個領域.然而，由于傳統(tǒng)鏈式區(qū)塊鏈的數(shù)據(jù)存儲結(jié)構(gòu)和共識機制等限制[1]，現(xiàn)有的區(qū)塊鏈系統(tǒng)普遍存在交易處理確認延遲高、吞吐率低和可擴展性差等局限性，限制了其應用范圍.為了解決這些問題并滿足實際應用需求，研究學者提出了基于有向無環(huán)圖（directed acyclic graph,DAG）的圖式區(qū)塊鏈方案，將傳統(tǒng)鏈式結(jié)構(gòu)擴展成圖式結(jié)構(gòu)，如IOTA[2],Byteball[3],Conflux[4]等.這些圖式區(qū)塊鏈解決方案也帶來新的挑戰(zhàn)，由于交易的并發(fā)度高，數(shù)據(jù)查詢無法像傳統(tǒng)鏈式結(jié)構(gòu)依次遍歷.根據(jù)圖式區(qū)塊鏈結(jié)構(gòu)可以采取廣度優(yōu)先遍歷策略或深度優(yōu)先遍歷策略，這些查詢方式存在效率低、可驗證性差等問題.本文提出了一種基于學習索引的圖式區(qū)塊鏈高效可驗證查詢機制，該機制通過引入學習索引結(jié)構(gòu)和基于圖式區(qū)塊鏈時序數(shù)據(jù)特征的查詢優(yōu)化策略，實現(xiàn)了高效的圖式區(qū)塊鏈數(shù)據(jù)查詢和驗證.同時，該機制能夠有效應對索引結(jié)構(gòu)和驗證開銷大等問題，為圖式區(qū)塊鏈技術的應用發(fā)展提供了一種新的查詢方案的技術支持.

近年來，為提高吞吐量、降低交易時延，圖式區(qū)塊鏈應運而生，其結(jié)構(gòu)與傳統(tǒng)的鏈式區(qū)塊鏈相比也有較大變化.圖式區(qū)塊鏈結(jié)構(gòu)擴展了傳統(tǒng)鏈式區(qū)塊鏈的數(shù)據(jù)結(jié)構(gòu)和共識機制，它采用基于圖數(shù)據(jù)結(jié)構(gòu)DAG 的分布式賬本技術，不僅能夠保證事務處理的高并發(fā)，同時其獨特的拓撲排序機制能夠?qū)崿F(xiàn)交易數(shù)據(jù)保持全局有序.圖式區(qū)塊鏈采用與傳統(tǒng)鏈式結(jié)構(gòu)相同的P2P 網(wǎng)絡實現(xiàn)整個網(wǎng)絡節(jié)點的連接，所有節(jié)點對等且保持同步，保證系統(tǒng)的安全和可靠性.每個全節(jié)點都具有保存維護和驗證全網(wǎng)數(shù)據(jù)區(qū)塊、轉(zhuǎn)發(fā)和廣播交易信息、支持輕節(jié)點數(shù)據(jù)查詢等功能.IOTA以每筆交易作為DAG 的頂點[2]，這種方式不需要挖礦節(jié)點對交易數(shù)據(jù)驗證打包，用戶發(fā)起交易不需要產(chǎn)生交易費，交易之間可以并行處理從而提高了整個網(wǎng)絡的吞吐量.在整個圖式區(qū)塊鏈的執(zhí)行過程中，新交易對它之前產(chǎn)生的2 筆或以上交易進行引用，從而完成交易數(shù)據(jù)驗證.Conflux 以區(qū)塊作為DAG頂點形成樹圖結(jié)構(gòu)[4]，礦工向圖式區(qū)塊鏈系統(tǒng)中并行產(chǎn)生新的交易數(shù)據(jù)時，全節(jié)點將在本地保存該交易并通過P2P 網(wǎng)絡廣播給相鄰的節(jié)點.礦工可以并行打包區(qū)塊，這些區(qū)塊引用多個當前最新的區(qū)塊，從而使得各區(qū)塊之間并發(fā)產(chǎn)生的同時保持全局有序.

然而，圖式區(qū)塊鏈這種基于DAG 的數(shù)據(jù)結(jié)構(gòu)，給查詢帶來了2 方面的挑戰(zhàn).首先在查詢效率方面，不同于傳統(tǒng)的鏈式區(qū)塊鏈，圖式區(qū)塊鏈的交易并發(fā)度高，交易數(shù)據(jù)規(guī)模更為龐大，區(qū)塊間引用關系多樣.2 個相鄰的紀元（epoch）之間可能包含著數(shù)個并發(fā)區(qū)塊，數(shù)據(jù)結(jié)構(gòu)更為復雜，使得遍歷區(qū)塊鏈數(shù)據(jù)的查詢方式效率低下.此外，圖式區(qū)塊鏈依然采用LevelDB[5]數(shù)據(jù)存儲方式.這種結(jié)構(gòu)主要是針對寫密集型的應用場景，在提升寫效率的同時降低了讀數(shù)據(jù)的效率[6]，難以滿足實際應用場景的需求，圖式區(qū)塊鏈亟需一種高效索引機制來加速查詢.另一方面則是查詢結(jié)果的可驗證性，與傳統(tǒng)中心化數(shù)據(jù)庫管理方式的不同之處在于，區(qū)塊鏈系統(tǒng)采用分布式全賬本形式[7]，在不可信環(huán)境中數(shù)據(jù)是分布式存儲在多個全節(jié)點上.隨著區(qū)塊鏈系統(tǒng)中產(chǎn)生的歷史數(shù)據(jù)不斷累積[8]，客戶端對歷史數(shù)據(jù)查詢的需求也將增加，這使得系統(tǒng)需要支持對可能存在惡意節(jié)點的查詢結(jié)果進行驗證.因此，在實現(xiàn)高效查詢的同時，保證圖式區(qū)塊鏈數(shù)據(jù)查詢結(jié)果的可驗證性成為另一個重要方面.

高效的索引機制設計是加快數(shù)據(jù)查詢的重要手段之一.通過使用索引，服務提供者可以快速定位所需數(shù)據(jù)，而無需掃描整個數(shù)據(jù)集.現(xiàn)有的區(qū)塊鏈查詢工作大多聚焦于傳統(tǒng)的樹結(jié)構(gòu)索引（如B+樹索引[9]），其主要是基于數(shù)據(jù)指針結(jié)構(gòu)，索引結(jié)構(gòu)被提前載入內(nèi)存當中，這種緩存索引機制僅適用于小規(guī)模數(shù)據(jù)庫并能夠提升查詢效率.但是，區(qū)塊鏈數(shù)據(jù)量只增不減，且成指數(shù)級規(guī)模遞增.當規(guī)模達到TB 級甚至PB級時，樹結(jié)構(gòu)索引所占用的空間也隨之遞增，此時索引結(jié)構(gòu)將不能全部載入內(nèi)存，只能不斷通過I/O 訪問磁盤，導致查詢性能降低.總體而言，傳統(tǒng)的樹結(jié)構(gòu)索引在大規(guī)模數(shù)據(jù)情況下存在2 方面主要問題：1）存儲空間占用大.例如，B+樹索引的空間復雜度為O(n)，數(shù)據(jù)量只增不減的情況下，索引結(jié)構(gòu)所占用的存儲空間不可忽視.2）查詢速度變慢.例如，樹結(jié)構(gòu)索引每次遍歷都需要從樹根節(jié)點依次訪問整棵樹的深度直到葉子節(jié)點，路徑上不相關的間接節(jié)點也都需要被訪問，其時間復雜度為這使得在大規(guī)模數(shù)據(jù)上的查詢性能變得較差.

針對傳統(tǒng)樹結(jié)構(gòu)索引存在的這些問題，一種新的數(shù)據(jù)索引結(jié)構(gòu)——學習索引[10]，近年來被研究者提出，它是一種結(jié)合機器學習和索引機制的查詢優(yōu)化技術[11].本文觀察圖式區(qū)塊鏈數(shù)據(jù)的時序分布特征，根據(jù)時間戳與紀元間的關系，采用適合的學習模型自動學習出最優(yōu)的索引函數(shù)，并將其參數(shù)作為索引存儲在列表中.當進行數(shù)據(jù)查詢時，節(jié)點可以通過模型計算快速定位查詢數(shù)據(jù)所在的大概位置.相比傳統(tǒng)的樹結(jié)構(gòu)索引，學習索引的查詢效率更高、擴展性更好，更適用于區(qū)塊鏈系統(tǒng).本文利用圖式區(qū)塊鏈數(shù)據(jù)的分布規(guī)律，將機器學習訓練方法應用于圖式區(qū)塊鏈數(shù)據(jù)索引的構(gòu)建過程中，其目的是通過參數(shù)列表代替?zhèn)鹘y(tǒng)樹結(jié)構(gòu)索引，降低區(qū)塊鏈系統(tǒng)中索引所占的空間大小，同時利用函數(shù)運算的方式代替對樹結(jié)構(gòu)索引的依次遍歷，提升索引的查詢性能.

本文的主要貢獻包括3 個方面：

1）針對圖式區(qū)塊鏈的數(shù)據(jù)分布特征，提出了一種基于學習索引的高效查詢機制Lever，加快圖式區(qū)塊鏈數(shù)據(jù)查詢.

2）為了提升圖式區(qū)塊鏈紀元內(nèi)區(qū)塊的遍歷速度，設計聚合布隆過濾器，該機制能有效過濾不存在的查詢數(shù)據(jù)，提升查詢效率；針對布隆過濾器存在假陽性的問題，提出排序默克爾樹結(jié)構(gòu)，該機制能夠保證查詢結(jié)果的可驗證性并降低可驗證對象的大小.

3）實驗結(jié)果表明，與Conflux 的基本查詢機制相比，Lever 的查詢性能最高可以提升10 倍，可驗證對象大小最多能夠降低90%.

接下來，本文將分析現(xiàn)有的區(qū)塊鏈查詢相關技術和工作，并總結(jié)現(xiàn)有工作存在的局限性.然后介紹圖式區(qū)塊鏈的基本概念以及本文工作將涉及的相關技術，緊接著針對圖式區(qū)塊鏈的數(shù)據(jù)分布特征提出一種基于學習索引的查詢優(yōu)化方法，闡述圖式區(qū)塊鏈索引構(gòu)建的實現(xiàn)細節(jié)和性能優(yōu)化策略.

1 相關工作

隨著區(qū)塊鏈技術的廣泛應用，用戶對區(qū)塊鏈上數(shù)據(jù)查詢的功能和效率提出越來越高的要求[12]，特別是在區(qū)塊鏈金融、電子商務、供應鏈等在線分析應用場景中.然而原生的區(qū)塊鏈系統(tǒng)存在查詢功能單一、查詢效率低和查詢可信驗證難等問題.當前區(qū)塊鏈查詢相關研究主要聚焦在鏈式區(qū)塊鏈上的高效查詢、可驗證查詢和功能性查詢.

1）高效查詢.賈大宇等人[13]提出了一種區(qū)塊鏈高效查詢方法ElasticQM，利用B-M 樹實現(xiàn)高效的數(shù)據(jù)查詢.在查詢層增加查詢超節(jié)點和校驗節(jié)點，用戶可以緩存查詢結(jié)果，再次查詢相同數(shù)據(jù)時可以加快數(shù)據(jù)訪問速度，提高查詢效率.Ruan 等人[14]提出了一個細粒度、安全、高效的區(qū)塊鏈數(shù)據(jù)追溯系統(tǒng)Lineagchain，支持智能合約的賬戶數(shù)據(jù)查詢和歷史數(shù)據(jù)追溯.在智能合約執(zhí)行期間獲取溯源信息，并有效地存儲在默克爾樹中.此外，Lineagchain 提供了一種新的跳表索引結(jié)構(gòu)，支持快速高效的溯源查詢處理.Zhang等人[15]提出了GEM2-Tree 數(shù)據(jù)結(jié)構(gòu)來減少查詢過程中產(chǎn)生的gas 開銷.蔡磊等人[16]對分布在多個區(qū)塊中的數(shù)據(jù)進行有效處理，通過建立物化視圖，利用字典樹加快多物化視圖維護進程，以區(qū)塊為單位提高查詢性能.針對Hyperledger Fabric 平臺的時間查詢問題，Gupta 等人[17]提出TQF 框架改進Fabric 上關于時間數(shù)據(jù)查詢的性能，將數(shù)據(jù)的時間范圍按照不同的時間間隔進行劃分，建立細粒度時間片數(shù)據(jù)索引，提高Fabric 上時間查詢的性能.總結(jié)發(fā)現(xiàn)，這些數(shù)據(jù)結(jié)構(gòu)優(yōu)化并未有效利用區(qū)塊鏈系統(tǒng)具有的時序特征，對于查詢效率的提高有限.

2）可驗證查詢.為了在輕節(jié)點上實現(xiàn)可驗證查詢，降低用戶的存儲和計算成本，Xu 等人[18]提出了一種在不可信環(huán)境下的可驗證查詢處理框架vChain.輕節(jié)點客戶端需要接收和驗證全節(jié)點返回的查詢結(jié)果和累加器驗證對象，其中累加器的密鑰需要占用大量的網(wǎng)絡和計算開銷.為了實現(xiàn)完整性驗證，Dai 等人[19]提出一個輕量級的可驗證查詢方法LVQ，降低節(jié)點存儲需求和網(wǎng)絡開銷，實現(xiàn)輕量化數(shù)據(jù)驗證，減少輕節(jié)點的數(shù)據(jù)存儲.通過將布隆過濾器（Bloom filter,BF）的哈希值存儲在區(qū)塊的頭部，LVQ 引入了一種新的BMT 結(jié)構(gòu)用于輕量級查詢，該結(jié)構(gòu)通過合并多個連續(xù)的布隆過濾器來降低查詢結(jié)果的通信代價.針對部分數(shù)據(jù)存儲在鏈上、原始數(shù)據(jù)存儲在鏈下的混合存儲架構(gòu)，Zhang 等人[20]研究了基于混合存儲區(qū)塊鏈中的可驗證范圍查詢.針對外包數(shù)據(jù)的完整性驗證問題，Hao 等人[21]提高了數(shù)據(jù)完整性驗證的安全性和效率，而不需要借助第三方審計.除此之外，另外一種方法通過可信執(zhí)行環(huán)境實現(xiàn)輕節(jié)點上的可驗證查詢，Shao 等人[22]提出了一種基于可信硬件Intel SGX 的可驗證查詢認證方式.輕節(jié)點無需接收或驗證全節(jié)點返回的查詢結(jié)果和加密證明，減少了網(wǎng)絡傳輸和本地計算的開銷，并通過基于冷熱數(shù)據(jù)的分層存儲方案來緩解可信內(nèi)存空間有限的問題.在可信飛地（Enclave）和非可信內(nèi)存中分層組織數(shù)據(jù)，Enclave 中只緩存熱數(shù)據(jù)，冷數(shù)據(jù)存于非可信內(nèi)存中.這種方法依賴于可信硬件，但是Enclave 的可信內(nèi)存有限僅128 MB，其性能和處理能力無法實現(xiàn)大規(guī)模應用.目前這些驗證機制主要是針對串行區(qū)塊的鏈式結(jié)構(gòu)，而無法直接應用于含有并行區(qū)塊的圖式結(jié)構(gòu)中.

3）功能性查詢.對于功能性查詢，由于區(qū)塊鏈底層基于Key-Value 鍵值對的存儲方式在一定程度上導致了查詢功能單一的問題，并且隨著賬本數(shù)據(jù)規(guī)模增大，進一步導致查詢速度降低.EtherQL[23]和VQL[24]采用基于以太坊設計的數(shù)據(jù)查詢層，以提取存儲在底層區(qū)塊鏈系統(tǒng)中的交易，為區(qū)塊鏈系統(tǒng)提供高效且可驗證的數(shù)據(jù)查詢服務，通過間接查詢分布式數(shù)據(jù)庫而不是P2P 網(wǎng)絡來獲得交易和區(qū)塊.查詢層維護了一個專門的分布式數(shù)據(jù)庫，可以提供包括范圍查詢和TOP-K查詢在內(nèi)的分析區(qū)塊鏈數(shù)據(jù)的高效查詢方式.Zhu 等人[25]提出并實現(xiàn)了新的區(qū)塊鏈數(shù)據(jù)庫SEBDB，設計了類似數(shù)據(jù)庫SQL 語句的查詢語句和索引結(jié)構(gòu)，查詢效率進一步提高.SEBDB 是首個區(qū)塊鏈數(shù)據(jù)庫平臺，同時兼顧可用性和可擴展性.首先，系統(tǒng)將事務表示為具有多個屬性的元組存儲在預定義表中.其次，SEBDB 使用類SQL 語言作為通用接口，將關系數(shù)據(jù)語義添加到區(qū)塊鏈平臺，以支持豐富的數(shù)據(jù)查詢功能.以上的功能性查詢框架，通過引入數(shù)據(jù)庫實現(xiàn)鏈下多功能查詢，難以支持在鏈上的多功能查詢.

2 預備知識

本節(jié)對系統(tǒng)設計中涉及的關鍵技術進行初步的介紹，包括圖式區(qū)塊鏈、學習索引和布隆過濾器.

2.1 圖式區(qū)塊鏈

圖式區(qū)塊鏈采用DAG 作為底層存儲模型的數(shù)據(jù)結(jié)構(gòu)，支持并發(fā)處理交易和打包區(qū)塊，與傳統(tǒng)鏈式區(qū)塊鏈相比具有更高的吞吐量性能.圖式區(qū)塊鏈具有實時性強和確認速度快的特點，因此更適用于物聯(lián)網(wǎng)、即時通訊、小額結(jié)算等領域[26].

圖式區(qū)塊鏈沿用了鏈式區(qū)塊鏈的P2P 網(wǎng)絡結(jié)構(gòu)來組織全網(wǎng)節(jié)點，這使得網(wǎng)絡中每個節(jié)點都是平等且相互連接.由于區(qū)塊鏈去中心化的特性，可能存在惡意節(jié)點篡改查詢結(jié)果的情況，這要求圖式區(qū)塊鏈查詢必須具備可驗證性.在另一方面，圖式區(qū)塊鏈結(jié)構(gòu)更為復雜，典型的DAG 圖式區(qū)塊鏈模型將圖中的每個節(jié)點定義為一筆交易，如IOTA[2].與鏈式區(qū)塊鏈相比，其優(yōu)點在于交易處理并行度更高，從而具有更低的處理延遲.然而，這種方案將新發(fā)布的交易任意地添加到現(xiàn)有的節(jié)點上，導致DAG 拓撲向不可預測的方向增長.為了保證交易數(shù)據(jù)有序，一些工作將區(qū)塊作為DAG 中的每個節(jié)點，擴展了鏈式區(qū)塊鏈的共識算法（如Conflux[4]和OHIE[27]），允許并發(fā)處理多個區(qū)塊以提高系統(tǒng)吞吐量.所有并發(fā)區(qū)塊被組織成一個固定的DAG 結(jié)構(gòu)，從而實現(xiàn)有向拓撲增長，并通過區(qū)塊排序算法來確定數(shù)據(jù)的完整順序.Conflux 采用一條主鏈來指導DAG 拓撲的生長方向，OHIE 將多個單鏈實例組織成一個平行鏈結(jié)構(gòu)，這兩類基于DAG 的區(qū)塊鏈因其高安全性、良好的可擴展性和支持智能合約的能力而成為當前圖式區(qū)塊鏈的主流.但這種支持高并發(fā)區(qū)塊的圖式結(jié)構(gòu)相較于鏈式結(jié)構(gòu)，其數(shù)據(jù)查詢變得復雜且低效.本文針對具有主鏈和引用關系的樹圖結(jié)構(gòu)Conflux 建立高效索引機制，提升圖式區(qū)塊鏈數(shù)據(jù)查詢的效率，同時保證查詢結(jié)果的可驗證性.

2.2 學習索引

學習索引利用機器學習技術學習數(shù)據(jù)分布[9]，并通過函數(shù)運算，即通過參數(shù)列表采用函數(shù)的方式代替?zhèn)鹘y(tǒng)指針的方式進行數(shù)據(jù)定位，從而提高數(shù)據(jù)查找速度并減小索引占用的存儲開銷.Kraska 等人[28]提出了學習索引（learned index）的概念，他們根據(jù)數(shù)據(jù)的分布規(guī)律采用機器學習的方式獲取數(shù)據(jù)之間的映射關系，并提出了遞歸模型索引（recursive-model indexes,RMI）解決學習索引的精度問題.RMI 將數(shù)據(jù)集分為更小的子集，并在每個子集上訓練模型，從而提高查找精度.上層學習模型的輸出用于選擇下層模型，最后一層模型將直接預測鍵值在數(shù)據(jù)集中的位置，由于模型精度的問題，在RMI 輸出預測的位置后，還需要在數(shù)組中進行搜索.為了減少最后的搜索時間，最底層模型在訓練時會保存一個誤差閾值，定位后只需在誤差范圍內(nèi)進行搜索.

索引結(jié)構(gòu)（如B+Tree[9]）在數(shù)據(jù)查詢技術中扮演著重要角色，但是這種基于樹結(jié)構(gòu)的索引機制沒有考慮被索引數(shù)據(jù)分布的信息，每條數(shù)據(jù)被視為獨立的個體.學習索引通過機器學習模型將數(shù)據(jù)分布所構(gòu)建的映射關系應用于索引中，利用模型參數(shù)值代替?zhèn)鹘y(tǒng)的數(shù)據(jù)指針結(jié)構(gòu)，從而降低索引存儲開銷，同時利用函數(shù)運算的方式快速定位數(shù)據(jù)并提升查詢性能.傳統(tǒng)的B+樹索引使用簡單的葉子指針指向原始數(shù)據(jù)，數(shù)據(jù)之間缺乏聯(lián)系，僅使用單一的有序分布來映射數(shù)據(jù)，其時間復雜度和空間復雜度都比學習索引開銷大.學習索引采用學習模型計算的方式替代傳統(tǒng)樹形索引的遍歷方式，給定輸入key值返回對應數(shù)據(jù)的位置，可以大幅度地降低索引的空間代價并提高查詢性能.

2.3 布隆過濾器

布隆過濾器[29]通過對數(shù)據(jù)集合中的元素進行哈希映射來判斷一個數(shù)據(jù)集合中是否存在某個特定數(shù)據(jù)元素，它是目前針對“存在查詢”類型最經(jīng)典的數(shù)據(jù)結(jié)構(gòu).在區(qū)塊數(shù)據(jù)結(jié)構(gòu)中，布隆過濾器可以作為區(qū)塊頭的一部分對區(qū)塊內(nèi)的交易進行過濾，從而加快對塊內(nèi)數(shù)據(jù)的遍歷.在傳統(tǒng)數(shù)據(jù)庫，也可以使用它來判斷某個鍵值是否存在于特定表格中，以此減少對磁盤的訪問.

布隆過濾器由位數(shù)組哈希函數(shù)構(gòu)成，具有快速過濾數(shù)據(jù)、低占用空間等優(yōu)點[30].布隆過濾器在插入新元素時，使用Hash 函數(shù)運算添加到位數(shù)組對應的值.在查詢數(shù)據(jù)時，再次通過Hash 函數(shù)運算查詢元素，如果計算得到的值不在位數(shù)組中，則可以判斷該數(shù)據(jù)元素一定不存在于原始數(shù)據(jù)集合當中.值得注意的是，由于哈希函數(shù)在一定概率下存在哈希碰撞沖突，當計算出某查詢元素哈希存在于該位數(shù)組中時，并不能判斷該元素一定存在于原始數(shù)據(jù)集合中.這種現(xiàn)象被稱為布隆過濾器的假陽性，即它只能過濾不存在于集合中的數(shù)據(jù)元素，對于存在于集合中的元素存在一定的誤判.布隆過濾器的假陽性誤判率與其位數(shù)組的長度具有負相關關系，位數(shù)組越長誤判率越低.但是在大數(shù)據(jù)集合上，需要很高的空間成本才能獲得較低的假陽性，這也在一定程度上限制了布隆過濾器在大規(guī)模數(shù)據(jù)集上的使用效率.

3 系統(tǒng)概述

本節(jié)介紹一種基于學習索引的圖式區(qū)塊鏈高效可驗證查詢機制Lever，并討論其系統(tǒng)結(jié)構(gòu)和工作流程.

3.1 系統(tǒng)架構(gòu)

圖式區(qū)塊鏈系統(tǒng)中所有的區(qū)塊數(shù)據(jù)保存在系統(tǒng)的全節(jié)點上，賬本數(shù)據(jù)由網(wǎng)絡中各全節(jié)點維護.客戶端（輕節(jié)點）由于計算和存儲能力有限，僅保存部分的區(qū)塊頭數(shù)據(jù)進行驗證，對存儲空間的需求大大降低.另一方面，由于客戶端本地未保存區(qū)塊鏈的賬本數(shù)據(jù)，它需要向全節(jié)點發(fā)起查詢請求，依賴于全節(jié)點返回正確的查詢結(jié)果.在存在惡意節(jié)點的不可信環(huán)境中，客戶端需要對查詢結(jié)果的正確性和完整性進行驗證.為保證查詢結(jié)果的可驗證性，全節(jié)點在返回結(jié)果的同時需要包含可驗證對象數(shù)據(jù).

系統(tǒng)架構(gòu)如圖1 所示，包括客戶端、學習索引、區(qū)塊數(shù)據(jù)、可驗證對象和查詢結(jié)果5 個部分.具體來說，客戶端對需要查詢的交易數(shù)據(jù)發(fā)送查詢請求，并接收全節(jié)點返回的查詢結(jié)果數(shù)據(jù).同時，客戶端本地同步保存最新區(qū)塊頭數(shù)據(jù)，通過本地計算驗證查詢結(jié)果.學習索引由礦工在打包區(qū)塊產(chǎn)生新的紀元時構(gòu)建，索引機制采用動態(tài)分段函數(shù)學習紀元高度與時間戳之間的映射關系.區(qū)塊數(shù)據(jù)由提供查詢服務的全節(jié)點同步保存，系統(tǒng)中的主區(qū)塊（例如區(qū)塊A，C，E等）由共識節(jié)點產(chǎn)生，根據(jù)主區(qū)塊和并發(fā)區(qū)塊之間的引用關系，系統(tǒng)中區(qū)塊被劃分為依次遞增的紀元，每個紀元內(nèi)包含不同數(shù)量的區(qū)塊數(shù)據(jù).可驗證對象是由全節(jié)點根據(jù)查詢結(jié)果生成的驗證數(shù)據(jù)，主要包含2 種情形：數(shù)據(jù)存在和數(shù)據(jù)不存在.數(shù)據(jù)存在則根據(jù)查詢結(jié)果生成存在性證明，即交易數(shù)據(jù)與其默克爾樹路徑；數(shù)據(jù)不存在則需返回不存在證明，即布隆過濾器對應的位數(shù)組，或布隆過濾器出現(xiàn)假陽性時對應的排序默克爾樹分支.查詢結(jié)果由查詢請求對應的交易數(shù)據(jù)和可驗證對象構(gòu)成，全節(jié)點根據(jù)請求數(shù)據(jù)完成查詢后，生成查詢結(jié)果返回給客戶端.

Fig.1 The achitecture of Lever圖1 Lever 系統(tǒng)架構(gòu)

本文針對圖式區(qū)塊鏈的時序數(shù)據(jù)特征，設計了基于學習索引的高效查詢機制Lever，加快圖式區(qū)塊鏈數(shù)據(jù)查詢.首先當客戶端向全節(jié)點發(fā)送查詢請求時，全節(jié)點通過構(gòu)建的學習索引快速定位查詢數(shù)據(jù)所在的紀元區(qū)間.其次，為了提升圖式區(qū)塊鏈紀元內(nèi)區(qū)塊的遍歷速度，通過設計聚合布隆過濾器，快速過濾不存在查詢數(shù)據(jù)的區(qū)塊，提升查詢效率.最后，針對布隆過濾器可能存在的假陽性，采用排序默克爾樹結(jié)構(gòu)，客戶端在接收查詢結(jié)果數(shù)據(jù)以外，會額外收到全節(jié)點返回的默克爾樹分支作為可驗證對象數(shù)據(jù)，該機制能夠保證查詢結(jié)果的高效性并降低可驗證對象的大小.客戶端利用本地同步保存的區(qū)塊頭數(shù)據(jù)對全節(jié)點返回的結(jié)果數(shù)據(jù)進行驗證，從而保證查詢結(jié)果的可驗證性.

3.2 系統(tǒng)工作流程

Lever 利用學習索引取代傳統(tǒng)樹結(jié)構(gòu)索引，以函數(shù)的方式存儲函數(shù)參數(shù)信息，避免對每條數(shù)據(jù)采用指針的方式降低索引占用的存儲空間，并通過函數(shù)運算實現(xiàn)對紀元間數(shù)據(jù)的快速定位.同時，系統(tǒng)根據(jù)定位后的區(qū)間對紀元內(nèi)的區(qū)塊進行遍歷.每個紀元內(nèi)采用聚合布隆過濾器對區(qū)塊內(nèi)的交易進行哈希映射，并據(jù)此快速過濾不存在的查詢數(shù)據(jù).區(qū)塊內(nèi)通過排序默克爾樹對布隆過濾器可能存在的假陽性做進一步判斷，存在則返回交易數(shù)據(jù)對應的默克爾樹路徑，不存在則返回相鄰交易的排序默克爾樹分支作為不存在證明.

系統(tǒng)工作流程如圖1 所示，當客戶端向全節(jié)點查詢某地址在一段時間內(nèi)的所有交易時，①客戶端向全節(jié)點發(fā)送包含交易地址和時間戳的查詢請求；②全節(jié)點首先獲取查詢請求中的時間戳，并通過所構(gòu)建的學習索引快速定位查詢數(shù)據(jù)所在的紀元區(qū)間；③全節(jié)點通過聚合布隆過濾器對紀元內(nèi)的多個區(qū)塊進行過濾，如果不存在則直接遍歷時間范圍內(nèi)的其他紀元，如果存在則需要分別對每個區(qū)塊頭的布隆過濾器進行檢驗，對于可能存在假陽性的區(qū)塊通過默克爾樹進一步遍歷，并生成對應的可驗證對象和查詢結(jié)果數(shù)據(jù)；④全節(jié)點向客戶端返回查詢結(jié)果，包括查詢請求對應的結(jié)果數(shù)據(jù)和查詢結(jié)果對應的可驗證對象數(shù)據(jù).客戶端在收到全節(jié)點返回的結(jié)果后，通過區(qū)塊頭和本地計算對查詢結(jié)果進行驗證.

4 面向圖式區(qū)塊結(jié)構(gòu)的可驗證學習索引設計

在本節(jié)中，我們將介紹Lever 的詳細設計，包括基于紀元間的時序高度學習索引構(gòu)建過程、基于紀元內(nèi)的多區(qū)塊聚合布隆過濾器、基于區(qū)塊內(nèi)交易的可驗證排序默克爾樹和Lever 高效數(shù)據(jù)查詢過程.本部分將從這4 個方面具體闡述各模塊內(nèi)容.

4.1 基于紀元間的時序高度學習索引

本文采用機器學習的方法實現(xiàn)圖式區(qū)塊鏈數(shù)據(jù)之間的映射關系，如圖2 所示.紀元間的學習索引通過學習數(shù)據(jù)集的時序分布特征來建立，相比于基于B+樹的索引機制，能夠?qū)崿F(xiàn)更高的查詢效率和更低的存儲開銷.

Fig.2 Learned index between epochs圖2 紀元間的學習索引

不同于傳統(tǒng)的樹結(jié)構(gòu)索引方法需要將所有的數(shù)據(jù)指針都存儲在索引結(jié)構(gòu)中，本文所構(gòu)建的學習索引只需將數(shù)據(jù)的一些統(tǒng)計特征和函數(shù)參數(shù)存儲在列表中.學習索引通過訓練后的模型參數(shù)列表實現(xiàn)數(shù)據(jù)定位，可以實現(xiàn)內(nèi)存的最小化占用和更高效的數(shù)據(jù)查找速度.節(jié)點進行查詢時，利用存儲的參數(shù)值計算查詢條件來預測目標數(shù)據(jù)的位置，從而避免對整個索引結(jié)構(gòu)進行遍歷的開銷，降低開銷.通過使用學習索引，節(jié)點可以實現(xiàn)更快的查詢速度和更低的存儲開銷，從而提高在大規(guī)模圖式區(qū)塊鏈數(shù)據(jù)場景中的查詢性能.

在圖式區(qū)塊鏈中紀元的定位僅依靠其高度值，無法直接根據(jù)時間屬性獲取某段時間內(nèi)的紀元數(shù)據(jù)，但通過觀察發(fā)現(xiàn)時間戳與紀元高度存在映射關系.因此本文在構(gòu)建索引時利用紀元的時序特征，并采用機器學習的思想構(gòu)建模型，建模出時間戳到紀元高度的映射關系.在模型中，我們采用分段線性回歸的方法來擬合映射關系.為了控制預測值與實際值之間的誤差范圍，Lever 在動態(tài)回歸過程中引入了誤差閾值 μ，以確保異常值偏離正常分布時也可以被索引，從而保證模型的準確度.

具體而言，模型在訓練過程中通過上、下誤差邊界控制回歸函數(shù)的分段數(shù)，上邊界為預測值hpre加上誤差閾值 μ，下邊界為預測值hpre減去誤差閾值 μ.如圖2 所示，點e1和e2是構(gòu)成起始函數(shù)的2 個基本點，點e3在這2 個邊界內(nèi)，則當前回歸模型不需要更新.由于點e4在誤差邊界之外，即實際值hact(e4)不在預測范圍 (hpre±μ) 之內(nèi)，此時，點e3作為新分段回歸函數(shù)的起點，點e4將成為新模型中的點進行訓練.時間區(qū)間[t1,t3]為已訓練好的模型，模型中數(shù)據(jù)的預測值與實際值偏差控制在誤差閾值 μ以內(nèi).對于偏離誤差范圍的點e4，在時間區(qū)間[t3,t4]構(gòu)建新的模型.點e5和e6在新模型的誤差范圍以內(nèi)，模型保持不變，直到點e7成為新的偏離點生成新的回歸模型.

同時，由于區(qū)塊鏈不可篡改的特性，歷史數(shù)據(jù)的分布不可改變，完成訓練的學習索引模型不會因為新產(chǎn)生的區(qū)塊數(shù)據(jù)而改變.因此，學習索引模型一旦被構(gòu)建并保存便不再需要進行重新訓練，降低了模型訓練的計算成本.

4.2 基于紀元內(nèi)的多區(qū)塊聚合布隆過濾器

通過學習索引快速定位到紀元后，為了避免依次遍歷區(qū)塊內(nèi)的每條交易數(shù)據(jù)，本文采用一種高效的查詢過濾機制，即在區(qū)塊頭引入布隆過濾器.我們采用布隆過濾器進行區(qū)塊內(nèi)交易數(shù)據(jù)集合的元素檢查，首先將區(qū)塊中所包含的交易數(shù)據(jù)構(gòu)成原始數(shù)據(jù)集，然后通過哈希函數(shù)對數(shù)據(jù)集中的每個元素進行哈希運算，將得到的值映射到隆過濾器的位數(shù)組中，最后比對位數(shù)組中的比特值進行元素檢查.

紀元內(nèi)的每個區(qū)塊都在區(qū)塊頭保存相應位數(shù)組，遍歷區(qū)塊內(nèi)數(shù)據(jù)前，先通過位數(shù)組進行過濾，成功過濾的區(qū)塊無需遍歷塊內(nèi)交易數(shù)據(jù).利用布隆過濾器提高查詢過程中塊內(nèi)數(shù)據(jù)的遍歷速度，這主要得益于其時間和空間的高效優(yōu)勢，每一個比特位即可實現(xiàn)對一條交易數(shù)據(jù)的映射，通過一次哈希運算即可實現(xiàn)對塊內(nèi)所有交易數(shù)據(jù)的過濾.為了進一步加快過濾紀元內(nèi)不含目標交易數(shù)據(jù)的區(qū)塊，本文將多個區(qū)塊中的布隆過濾器進行聚合，如圖3 所示.

Fig.3 Intra-epoch aggregated Bloom filter圖3 紀元內(nèi)聚合布隆過濾器

聚合布隆過濾器將多個區(qū)塊的布隆過濾器位數(shù)組通過或運算聚合在一起，以實現(xiàn)更好的去重效果和查詢過濾性能.與單個區(qū)塊布隆過濾器相比，聚合布隆過濾器可以更好地處理交易數(shù)據(jù)集合較大、數(shù)據(jù)分布不均等問題.聚合布隆過濾器的具體實現(xiàn)和工作步驟為：

1）將紀元按區(qū)塊分成多個部分，并為每個區(qū)塊創(chuàng)建一個獨立的布隆過濾器；

2）將多個布隆過濾器通過或運算進行合并聚合；

3）當需要查詢某個元素是否存在于數(shù)據(jù)集合中時，將該元素傳入聚合布隆過濾器中查詢；

4）如果聚合布隆過濾器返回該元素不存在于紀元數(shù)據(jù)集合中，則認為該元素一定不存在于該紀元內(nèi)的所有區(qū)塊數(shù)據(jù)集合中；

5）如果聚合布隆過濾器返回該元素存在于數(shù)據(jù)集合中，則認為該元素可能存在于數(shù)據(jù)集合中，因此需要對區(qū)塊中的每一個獨立布隆過濾器進一步判斷.

聚合布隆過濾器的優(yōu)勢在于，數(shù)據(jù)不存在的情況下可以快速過濾紀元內(nèi)的多個區(qū)塊，提高去重和查詢的準確率和效率.在查詢過程中，客戶端向全節(jié)點發(fā)送查詢請求信息，全節(jié)點根據(jù)請求信息通過哈希函數(shù)進行運算，將得到的值與布隆過濾器的位數(shù)組進行對比.如果為0 則表明查詢數(shù)據(jù)一定不存在于該數(shù)據(jù)集合中，此時位數(shù)組也可以作為不存在證明構(gòu)建可驗證對象.但當運算結(jié)果比對為1 時，并不能確定查詢數(shù)據(jù)一定存在于該數(shù)據(jù)集中，這是因為哈希函數(shù)存在碰撞沖突，布隆過濾器此時的結(jié)果可能誤報，即假陽性.

布隆過濾器只能確定某個元素一定不存在于特定集合中，但由于哈希沖突可能導致判斷存在的元素并不一定存在于該集合中.其中，包含的元素個數(shù)是影響布隆過濾器中誤報率的重要因素之一，通過增加位數(shù)組的長度能夠有效降低誤報率，但同時會增大布隆過濾占用的存儲空間.為了克服布隆過濾器存在的誤報率，接下來本文通過設計排序默克爾樹解決假陽性問題，保證查詢結(jié)果的正確性和完整性.

4.3 基于區(qū)塊內(nèi)的可驗證排序默克爾樹

客戶端可以通過2 種基本的方式實現(xiàn)對查詢結(jié)果的驗證：1）全節(jié)點在完成查詢操作后，直接將包含查詢結(jié)果的所有區(qū)塊直接返回給客戶端.該方案只能保證查詢結(jié)果的正確性，客戶端通過對比區(qū)塊內(nèi)的全部交易數(shù)據(jù)獲得正確的查詢結(jié)果.但是該方案需要額外返回大量的無關數(shù)據(jù)，并且無法保證查詢結(jié)果的完整性，即全節(jié)點可能遺漏包含查詢數(shù)據(jù)的區(qū)塊，而客戶端只能驗證已收到的區(qū)塊數(shù)據(jù)，無法驗證是否有數(shù)據(jù)丟失.2）客戶端在存儲能力范圍內(nèi)盡量保存更多的賬本數(shù)據(jù)，此時客戶端將由輕節(jié)點逐漸變成全節(jié)點，當同步完整的賬本數(shù)據(jù)后，可以實現(xiàn)在本地直接查詢.這種方式直接采用空間換時間，客戶端的存儲開銷與輕節(jié)點的初衷相悖.

本文設計的圖式區(qū)塊鏈可驗證機制與上述2 種基本方案不同，其目標主要有2 點：1）全節(jié)點在查詢過程中返回盡量少的數(shù)據(jù).由于返回的數(shù)據(jù)主要包含結(jié)果數(shù)據(jù)和驗證數(shù)據(jù)2 方面，結(jié)果數(shù)據(jù)的大小與客戶端的查詢請求相關，驗證數(shù)據(jù)的大小與驗證機制相關.此目標主要圍繞降低驗證數(shù)據(jù)大小，使得全節(jié)點在生成可驗證對象時產(chǎn)生較小的證明數(shù)據(jù)量.2）客戶端本身無需存儲大量的賬本數(shù)據(jù).驗證機制應避免對客戶端造成較大的額外存儲開銷，客戶端僅保存區(qū)塊頭數(shù)據(jù)，通過驗證計算與所同步的區(qū)塊頭哈希值進行對比，保證查詢結(jié)果的可驗證性.此目標主要圍繞利用客戶端的計算性能降低額外存儲的數(shù)據(jù)，從而保證客戶端在存儲方面的輕量化.

圖式區(qū)塊鏈系統(tǒng)采用了與比特幣系統(tǒng)設計中相同的最基本默克爾樹結(jié)構(gòu).如圖4 所示，在一個區(qū)塊內(nèi)礦工打包了4 筆區(qū)塊鏈交易，它們的交易地址元素(T x eacd f,T x acdbg,T x d feag,T x bdc fe)用于構(gòu)建默克爾樹，基本的默克爾樹直接根據(jù)當前的交易順序進行構(gòu)建，葉子節(jié)點元素之間的關系隨機.當查詢T x caed f布隆過濾器出現(xiàn)假陽性時，全節(jié)點返回的不存在證明需要包含完整默克爾樹的數(shù)據(jù).這種方式將導致驗證對象占用的存儲空間較大，造成結(jié)果數(shù)據(jù)的網(wǎng)絡傳輸和客戶端的驗證開銷增大.

Fig.4 Intra-block sorted Merkle tree圖4 區(qū)塊內(nèi)排序默克爾樹

本文采用排序默克爾樹降低驗證對象大小，首先將交易數(shù)據(jù)集合中的元素通過排序函數(shù)S ort(·)排序為(T x acdbg＜T x bdcfe＜T x d feag＜T x eacd f)，然后基于排序后的元素構(gòu)建默克爾樹，得到如圖4 所示的排序默克爾樹結(jié)構(gòu).由于葉子節(jié)點之間的元素有序，當出現(xiàn)不存在的元素T x caed f時，可以通過對比相鄰元素T x bdcfe和T x d feag的大小.因此，針對布隆過濾器出現(xiàn)假陽性，不存在證明可以利用排序默克爾樹的相鄰葉子節(jié)點分支，可驗證對象僅需返回相鄰葉子節(jié)點和對應路徑，客戶端即可判斷數(shù)據(jù)是否存在于分支之間.

4.4 Lever 的高效數(shù)據(jù)查詢過程

為了便于說明，本文首先考慮一個特定的時間戳，并應用于具有學習索引的點查詢.然后，將其擴展到時間范圍條件，以說明如何高效地處理時間范圍查詢請求.Lever 維護學習索引函數(shù)的每個分段函數(shù)參數(shù)，包括起點、斜率和截距.由于時間戳具有遞增屬性，因此本文采用變體二分查找算法快速定位查詢值所在的分段.查找元素所在指定段的時間復雜度為O(lbn)，其中n為分段參數(shù)列表的長度.一旦找到了具有相應時間戳的分段，我們就可以通過計算該段中的函數(shù)來快速定位給定時間戳對應的紀元高度.在創(chuàng)建分段線性函數(shù)時，鍵的實際位置與回歸函數(shù)運算的位置保持在一個范圍內(nèi)（即誤差閾值 μ）.根據(jù)分段的斜率和截距參數(shù)，給定時間戳t的預測位置計算方式為：

其中，Nslope和Nintercept分別為分段函數(shù)對應的斜率和截距.

通過動態(tài)分段線性函數(shù)構(gòu)造索引，可以將元素的真實位置限制在誤差范圍內(nèi).因此，在計算得到預測位置后，采用順序遍歷的方法對誤差范圍內(nèi)的紀元進行局部檢索.給定時間戳t和誤差閾值 μ的實際位置范圍為：

時間范圍查詢是點查詢的一種特殊擴展情況，具有時間范圍附加條件，它需要檢查查詢的數(shù)據(jù)結(jié)果是否在給定的時間范圍內(nèi)，如算法1 所示.查詢請求為Q=(addr,〈t1,t2〉)，表示對地址addr在時間段t1～t2相關交易的查詢.首先，全節(jié)點找到t1與t2所對應的學習索引分片 (seg1,seg2)，并讀取相應分片的斜率Nslope與截距Nintercept.根據(jù)斜率與截距，全節(jié)點通過函數(shù)運算得到包含t1和t2的紀元范圍(pre_epoch1-μ,pre_epoch1+μ）.對于范圍內(nèi)的所有紀元，全節(jié)點執(zhí)行5 個操作：1）使用聚合布隆過濾器檢測紀元內(nèi)是否存在地址addr的相關交易；2）若存在相關交易，則搜索紀元內(nèi)所有時間戳在 〈t1,t2〉之間的區(qū)塊，檢查區(qū)塊內(nèi)是否存在地址addr的相關交易；3）若區(qū)塊內(nèi)包含addr相關交易T x，則將T x加入結(jié)果集，否則就加入T x的前序與后繼交易；4）將相應排序默克爾樹分支加入驗證對象集合；5）返回結(jié)果集T xS et與驗證對象集VO.因此，與點查詢不同，時間范圍查詢的條件對查詢的總時間和結(jié)果大小有較大的影響.這2 種查詢類型的主要區(qū)別在于，時間范圍查詢需要判斷給定時間范圍的2 個端點.由于分段函數(shù)滿足給定的誤差閾值，因此在分段中查找鍵的開銷可以得到控制.更準確地說，在誤差邊界范圍內(nèi)查詢數(shù)據(jù)的時間復雜度為O(1+2μ).在連續(xù)時間范圍內(nèi)，分段線性函數(shù)指向的鍵要么連續(xù)地分布在同一段函數(shù)中，要么存在于相鄰的分段函數(shù)中.當節(jié)點進行時間范圍查詢時，Lever 首先在誤差范圍內(nèi)直接從時間范圍的起始點位置開始掃描，然后遍歷相鄰分段函數(shù)中，直到時間范圍的結(jié)束點.

算法1.時間范圍可驗證查詢算法.

5 可驗證性分析

為實現(xiàn)在不可信的區(qū)塊鏈環(huán)境中進行可驗證查詢，客戶端需要對返回的查詢結(jié)果進行驗證.全節(jié)點除了返回查詢請求對應的查詢結(jié)果數(shù)據(jù)以外，還需要額外返回與結(jié)果相關的證明數(shù)據(jù)，即可驗證對象.客戶端根據(jù)查詢結(jié)果和可驗證對象數(shù)據(jù)進行計算，并與本地保存的區(qū)塊頭數(shù)據(jù)進行對比，從而實現(xiàn)對查詢結(jié)果的驗證.對查詢結(jié)果的驗證目標主要包括2個方面：正確性和完整性.

5.1 正確性分析

查詢結(jié)果的正確性，即驗證全節(jié)點返回的結(jié)果數(shù)據(jù)是在區(qū)塊鏈賬本中未被篡改且真實存在的.當前的Conflux 系統(tǒng)實現(xiàn)中礦工在進行區(qū)塊打包時，將區(qū)塊中的交易采用默克爾樹的形式進行組織，并將默克爾樹根保存在區(qū)塊頭.客戶端根據(jù)全節(jié)點返回的交易數(shù)據(jù)進行該默克爾哈希運算，直到得出默克爾樹根.如果計算得到的值與本地同步的區(qū)塊頭數(shù)據(jù)值相同，則可以證明返回的結(jié)果數(shù)據(jù)是真實存在且未被篡改，否則查詢結(jié)果不正確.因此，全節(jié)點可以通過返回交易默克爾樹直接作為查詢結(jié)果的正確性證明，客戶端基于該證明，通過本地計算即可對查詢結(jié)果的真實性進行驗證.

5.2 完整性分析

查詢結(jié)果的完整性，即驗證全節(jié)點返回的結(jié)果數(shù)據(jù)沒有遺漏.Lever 采用聚合布隆過濾器首先判斷紀元內(nèi)是否包含查詢數(shù)據(jù)，如果聚合布隆過濾器返回值為0，則該數(shù)據(jù)一定不存在于該紀元內(nèi)，此時全節(jié)點返回聚合布隆過濾的位數(shù)組作為不存在證明.當聚合布隆過濾器返回值為1 時，全節(jié)點對紀元內(nèi)各區(qū)塊的區(qū)塊頭布隆過濾器進行遍歷，查找可能存在交易數(shù)據(jù)的區(qū)塊.如果遍歷區(qū)塊該交易數(shù)據(jù)真實存在，則返回對應交易數(shù)據(jù)；如果遍歷區(qū)塊后該交易數(shù)據(jù)并不存在，說明布隆過濾器產(chǎn)生了誤報，全節(jié)點需要將該數(shù)據(jù)對應排序默克爾樹的2 個相鄰邊界葉子節(jié)點和默克爾樹路徑分支作為不存在證明返回給客戶端.客戶端在驗證查詢結(jié)果時，首先利用布隆過濾器的位數(shù)組驗證紀元內(nèi)不存在所查詢的交易數(shù)據(jù)；其次，如果出現(xiàn)假陽性，客戶端利用排序默克爾樹分支和相鄰葉子節(jié)點進行對比，即可驗證查詢數(shù)據(jù)的不存在性，從而判斷查詢結(jié)果未被遺漏.

6 實驗評估

6.1 實驗環(huán)境

本文實驗使用的數(shù)據(jù)集是基于Conflux 系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)所生成，它包含2 048 epoch，8 192 個區(qū)塊，交易被重新組織成〈epoch，block，address，amount，timestamp〉作為Lever 的輸入數(shù)據(jù).實驗采用Intel Xeon Platinum 8369B 服務器16 核32 GB 內(nèi)存，CPU 3.5 GHz，運行CentOS 7.6 操作系統(tǒng).Lever 系統(tǒng)基于Rust 語言編寫，搭建了一個用于創(chuàng)建圖式區(qū)塊鏈系統(tǒng)和索引結(jié)構(gòu)的開源框架.實驗從索引構(gòu)建開銷、查詢性能和誤差閾值對系統(tǒng)的影響這3 個方面進行評估.通過2 個基準測試來評估Lever 的索引構(gòu)建開銷：1）索引構(gòu)建所需的CPU 時間，包括紀元間的學習索引、紀元內(nèi)的布隆過濾器和排序默克爾樹；2）不同紀元高度下索引結(jié)構(gòu)占用的存儲開銷.在系統(tǒng)參數(shù)影響評估實驗中，本文在不同紀元高度下對索引構(gòu)建開銷和查詢性能進行了評估，并選擇了查詢延遲、誤報率和驗證開銷3 個評估指標.

6.2 索引構(gòu)建開銷

實驗對礦工節(jié)點在打包數(shù)據(jù)時構(gòu)建區(qū)塊的總時間和構(gòu)建學習索引所需的時間進行了比較，其中學習索引的誤差閾值μ設置為5，參數(shù)設置原因可以通過6.3 節(jié)誤差閾值對系統(tǒng)查詢的影響分析可知.從圖5可以看出，隨著生成區(qū)塊數(shù)量的增加，兩者的構(gòu)建時間都有所增長.但總的區(qū)塊構(gòu)建時間是學習索引構(gòu)建時間的104倍，這是因為在構(gòu)建學習索引時，本文采用動態(tài)更新的方式，僅在新增數(shù)據(jù)與學習索引模型預估的誤差在誤差閾值外時更新模型，其占用的CPU 時間開銷并不大.值得一提的是，對于一段特定區(qū)間的學習索引模型，其存儲的參數(shù)為起始時間戳、斜率和對應的截距，這種分段參數(shù)方式相比于數(shù)據(jù)指針方式降低了索引的存儲開銷.

Fig.5 The overhead of index building圖5 索引構(gòu)建開銷

6.3 誤差閾值對系統(tǒng)查詢的影響

實驗評估了不同誤差閾值對CPU 處理時間、索引大小和查詢延遲的影響.本文針對紀元高度進行了可擴展性實驗，采用256～2 048 個不同數(shù)量的紀元高度數(shù)據(jù)集.圖6（a）和圖6（b）顯示了CPU 處理時間和索引大小的性能，誤差閾值從1 遞增到10.實驗結(jié)果表明，隨著誤差閾值的增加，CPU 處理時間幾乎保持不變，而索引大小隨著誤差閾值的增加逐漸減小，其原因在于較大的誤差閾值會使得分段函數(shù)的數(shù)量降低，存儲的參數(shù)減少，但這種情況下預測值與實際值之間的誤差范圍也隨之增大，模型的精確度會降低.隨后，實驗評估了誤差閾值對查詢延遲的影響.圖6（c）顯示了不同區(qū)塊高度的查詢延遲，當誤差閾值小于4 時，查詢延遲略有振蕩，然后隨著誤差閾值的增加而增加，其原因在于較大的誤差閾值在數(shù)據(jù)定位時需要對更多的紀元進行遍歷.在CPU 處理時間基本保持不變的條件下，綜合考慮查詢延遲和索引大小2 個因素，當誤差閾值為5 時，查詢延遲增幅并不高且索引占用的空間降幅較大，因此，實驗中選取誤差閾值為5 作為系統(tǒng)參數(shù).

Fig.6 Impact of different error bounds on system performance圖6 不同誤差閾值對系統(tǒng)性能的影響

圖7 顯示了Lever 在區(qū)塊數(shù)量為256～8 192 且誤差閾值為5時的查詢性能.實驗將圖式區(qū)塊鏈Conflux 上的基本查詢方法作為實驗基準（DAG Baseline），并采用傳統(tǒng)的B+Tree 結(jié)構(gòu)建立紀元間索引作為對比，在此基礎上對本文提出的Lever 框架進行消融實驗，主要包括不含學習索引的Lever（Lever w/o Index）以及不含有聚合布隆過濾器的Lever（Lever w/o AGG-BF）.實驗結(jié)果表明，隨著區(qū)塊數(shù)量的增多，Lever 和Lever w/o AGG-BF 查詢延遲基本保持不變，維持在10～20 ms 之間，其查詢效率是Lever w/o Index 的10 倍左右.B+Tree 和B+Tree w AGG-BF的查詢延遲相較于DAG Baseline 平均降低60%，然而它們的查詢延遲是Lever 的5 倍以上，其原因在于B+Tree 結(jié)構(gòu)是基于二分查找策略，相比于線性依次遍歷有較大提升，但對比于函數(shù)運算其查詢延遲依然較大.DAG Baseline 和Lever w/o Index 的查詢延遲與區(qū)塊數(shù)量基本呈線性關系，當區(qū)塊數(shù)量達到8 192時，兩者的查詢延遲都高于103ms，其原因主要是隨著區(qū)塊數(shù)量的增加，這2 類查詢類型都需要依次訪問每個紀元并遍歷整個區(qū)塊數(shù)據(jù)集.

Fig.7 Query latency with different number of blocks圖7 不同區(qū)塊數(shù)量下的查詢延遲

6.4 系統(tǒng)參數(shù)影響

布隆過濾器的長度會在2 個方面對系統(tǒng)產(chǎn)生影響：1）布隆過濾器的假陽性概率；2）布隆過濾器占用的存儲大小.本文針對不同布隆過濾器位數(shù)組長度對這2 個因子進行評估，以選擇較為合適的布隆過濾器位數(shù)組長度作為系統(tǒng)參數(shù).如圖8 所示，實驗選取大小約為6 000 筆交易的區(qū)塊，布隆過濾器比特位長度在[1 000,500 000]范圍內(nèi)對假陽性概率和布隆過濾器占用的存儲空間大小進行對比.

Fig.8 False positive of Bloom filter at different bit lengths圖8 不同位長度下布隆過濾器的假陽性

從實驗中可以總結(jié)出2 個方面的關鍵點:1）對于假陽性概率，如圖8 所示，布隆過濾器長度超過10 000 b時，假陽性概率迅速降低，直到布隆過濾器的長度大于50 000 b 時，假陽性概率趨于0.01.假陽性概率高會使得在查詢過程中，將一些不包含記錄的區(qū)塊作為目標塊返回給輕節(jié)點，這會增加全節(jié)點返回的可驗證對象大小和對應的通訊開銷.2）對于布隆過濾器占用存儲空間大小，從圖8 可以直觀地發(fā)現(xiàn)，布隆過濾器的比特位長度與其占用存儲空間大小呈正相關.實驗結(jié)果表明，隨著布隆過濾器比特位的增加，布隆過濾器假陽性概率降低，被誤判的區(qū)塊數(shù)量減少，查詢效率提高.理論上，實驗可以取任何大于50 000 b 的參數(shù)值作為布隆過濾器的比特位.但在實際情況下，需要考慮空間開銷和對應的假陽性概率，因此在實驗中，本文將布隆過濾器的比特位設置為50 000 b 作為系統(tǒng)參數(shù).

實驗針對布隆過濾器在假陽性條件下，分別對使用排序默克爾樹和不使用排序默克爾樹返回的可驗證對象數(shù)據(jù)集大小進行了評估，如圖9 所示.

Fig.9 The size of the verifiable object in two cases圖9 2 種情形下的可驗證對象大小

在查詢過程中，當關鍵字存在于區(qū)塊中時，兩者的存在性證明一致，因此其可驗證對象大小相同.當關鍵字不存在于區(qū)塊中時，無排序默克爾樹返回的可驗證對象數(shù)據(jù)集大小約是排序默克爾樹返回的可驗證對象集大小的25 倍.其原因在于，當布隆過濾器出現(xiàn)假陽性時，無排序默克爾樹需要返回區(qū)塊內(nèi)所有的數(shù)據(jù)集作為可驗證對象，而排序默克爾樹能夠返回區(qū)塊內(nèi)的邊界交易和默克爾樹分支作為可驗證對象.

7 結(jié)論

本文提出了一種基于學習索引的高效可驗證的圖式區(qū)塊鏈查詢機制Lever，該機制通過引入學習索引技術對圖式區(qū)塊鏈中時序數(shù)據(jù)分布特征進行學習來實現(xiàn)對索引過程的優(yōu)化.針對圖式區(qū)塊鏈數(shù)據(jù)查詢的效率和可驗證性問題，將學習索引應用于圖式區(qū)塊鏈的紀元高度與時間戳的映射關系中，通過函數(shù)運算的方式定位查詢數(shù)據(jù)，提高圖式區(qū)塊鏈的查詢速度和效率.同時，為了加快紀元內(nèi)多個區(qū)塊數(shù)據(jù)的過濾速度，在每個區(qū)塊頭部添加布隆過濾器，并為每個紀元生成一個聚合布隆過濾器，從而提高紀元內(nèi)的數(shù)據(jù)遍歷速度.此外，為保證查詢結(jié)果的正確性和完整性，該機制結(jié)合布隆過濾器和排序默克爾樹生成可驗證對象，通過部分默克爾樹分支實現(xiàn)對布隆過濾器假陽性的不存在證明，有效減小驗證對象的規(guī)模，從而保證圖式區(qū)塊鏈查詢可驗證性并提高驗證效率.實驗結(jié)果表明，Lever 能有效提高基于DAG的圖式區(qū)塊鏈查詢效率和可驗證性，與Conflux 的基本查詢機制相比，Lever 的查詢延遲可以降低至1/10，不存在證明的可驗證對象大小開銷可以大幅度降低.

未來工作主要將從2 個方面展開：1）關于查詢類型的擴展，如何將學習索引擴展到其他屬性值，支持更多類型的查詢.2）如何在保證查詢結(jié)果可驗證性的前提下，將驗證機制進一步優(yōu)化.

作者貢獻聲明：常健設計了研究方案并撰寫論文；林立成提出了算法思路和完成實驗；李彬弘負責方案討論、論文修改；肖江提出指導意見并修改論文；金海提出指導意見及討論定稿.