[發明專利]一種基于索引的面向區塊鏈輕客戶端的范圍查詢可驗證查詢方法

有效

• 申請號: 201910066166.6
• 申請日: 2019-01-24
• 公開（公告）號: CN109885615B
• 公開（公告）日: 2020-09-22
• 發明（設計）人: 方敏;朱燕超;張召;金澈清
• 申請（專利權）人: 華東師范大學
• 主分類號: G06F16/27
• 分類號: G06F16/27;G06F16/22;G06F16/2455
• 代理公司: 上海藍迪專利商標事務所(普通合伙) 31215
• 代理人: 徐筱梅;張翔

1.一種基于索引的面向區塊鏈輕客戶端的范圍查詢可驗證查詢方法，其特征在于，該方法包括以下具體步驟：

步驟S1：區塊索引和層次索引結構生成

全節點在關鍵字區塊時間戳上構造一個區塊層B⁺-tree索引結構；對不同交易類型構造位圖索引并對每一個區塊在關鍵字交易時間戳上構造Merkle B-tree索引，記作MB-tree索引，構成一個由位圖索引和MB-tree索引組成的層次索引結構；

步驟S2：全節點進行數據可驗證查詢

全節點根據區塊層B⁺-tree索引結構和層次索引結構處理輕客戶端發送來的查詢請求，并將表示當前區塊鏈版本的區塊高度h和查詢生成的驗證對象VO返回給輕客戶端；

步驟S3：全節點進行輔助可驗證查詢

全節點獲取表示當前區塊鏈版本的區塊高度H，并判斷其是否與步驟S2中獲取到的區塊高度h一致，若一致則根據區塊層B⁺-tree索引結構和層次索引結構處理輕客戶端發送來的查詢請求，并將查詢生成的輔助驗證對象AVO返回給輕客戶端；否則，不進行操作而將AVO=?返回給輕客戶端；

步驟S4：輕客戶端進行可驗證查詢

輕客戶端根據VO和AVO來驗證查詢結果的完備性和完整性，得到最終正確的查詢結果；其中：

所述步驟S1具體包括：

步驟 A1：全節點在關鍵字區塊時間戳上構造一個區塊層B⁺-tree索引結構，用來獲取給定查詢時間范圍內的區塊id；

步驟A2：全節點首先對所有的交易數據按照交易類型劃分，得到多個分類；然后為每一個分類創建一個位向量，即一行二進制串數據，每一行中的第i位二進制數據代表區塊i中是否包含這種交易類型的數據，1代表包含，0代表不包含；若出現一種新的交易類型，則添加新的一行二進制串數據來記錄此類型交易，所有交易類型的二進制數據共同組成了層次索引的第一層索引結構——位圖索引；

步驟A3：全節點對每一個區塊在關鍵字交易id上構造一個MB-tree，MB-tree是B⁺樹和Merkle Hash Tree 的結合體，其中每一個葉子節點都含有本身的哈希值，每一個非葉子節點中都含有其孩子節點級聯的哈希值，構成了層次索引的第二層索引結構——MB-tree索引；當一個新的區塊生成后，全節點為該區塊構建一個在關鍵字交易id上的MB-tree；

所述步驟S2具體包括：

步驟B1：全節點接收來自輕客戶端的查詢請求，獲取表示當前區塊鏈版本的區塊高度h，并根據區塊層B⁺-tree索引結構使用范圍搜索獲取給定查詢時間范圍內的區塊范圍；

步驟B2：全節點根據步驟B1中獲取到的區塊范圍查詢層次索引的第一層索引結構——位圖索引；全節點根據查詢請求中的交易類型查詢位圖索引中的對應行，并按位掃描該行中在區塊范圍內的所有二進制數據，若為0則跳過，若為1則將對應的區塊id加入包含查詢結果的一個區塊集合；

步驟B3：全節點根據步驟B2中獲取到的區塊集合查詢層次索引的第二層索引結構——MB-tree索引；對于在區塊集合內的任意區塊i，全節點將在該區塊i的MB-tree上執行范圍搜索來生成驗證對象，并將其添加到VO中；

步驟B4：全節點將當前的區塊高度h和查詢生成的驗證對象VO返回給輕客戶端；

所述步驟S3具體包括：

步驟C1：全節點接收來自輕客戶端的查詢請求和區塊高度h，獲取表示當前區塊鏈版本的區塊高度H，并判斷其是否與h一致，若一致則進行步驟C2，否則進行步驟C6；

步驟C2： 全節點根據區塊層B⁺-tree索引結構使用范圍搜索獲取給定查詢范圍內包含有查詢交易類型的區塊范圍；

步驟C3：全節點根據步驟C2中獲取到的區塊范圍查詢層次索引的第一層索引結構——位圖索引；全節點根據查詢請求中的交易類型查詢位圖索引中的對應行，并按位掃描該行中在區塊范圍內的所有二進制數據，若為0則跳過，若為1則將對應的區塊id加入包含查詢結果的一個區塊集合；

步驟C4：全節點根據步驟C3中獲取到的區塊集合查詢層次索引的第二層索引結構——MB-tree索引；對于在區塊集合內的任意區塊i，全節點將獲取該區塊i的MB-tree根Root_i，并將區塊id號i和對應的Root_i將添加到AVO中；

步驟C5：全節點將查詢生成的輔助驗證對象AVO返回給輕客戶端；

步驟C6：全節點不進行操作而將AVO=?返回給輕客戶端；

所述步驟S4具體包括：

步驟D1：輕客戶端獲取步驟B4中返回的驗證對象VO，以及步驟C5中返回的輔助驗證對象AVO；

步驟D2：對VO中的每一個區塊i，輕客戶端通過VO中的每一個區塊的VO_i重新構建相應的MB-tree根，并將其與AVO中包含的區塊i對應的索引根進行對比來驗證；

步驟D3：如果VO中所有的區塊的驗證結果都是正確的，則查詢結果是正確的。