混合存儲模型：
只有少量meta-data（加密哈希）存在鏈上，原始數據外包給鏈下的存儲服務商

貢獻

提出了一個新的ADS
1.首先提出了抑制默克爾倒置（Merkle inv）索引，該索引僅在鏈上維護部分 ADS 結構，可以使用對數加密證明進行安全更新。
2.提出了一個變色龍倒置（Chameleon inv）索引，它利用變色龍向量承諾來實現恒定的維護成本。它使用Bloom過濾器進一步優(yōu)化，以增強查詢和驗證性能。

問題：
1.要支持完整性保證的數據檢索
2.ADS要是更新高效的（即可以被智能合約高效維護，且計算和存儲成本低）
3.GEM2-tree支持范圍查詢，不支持關鍵字查詢和相似查詢
4.GEM2-tree會存儲很多中間數據

解決1
Merkel inv index
1.每個關鍵字對應一棵MBTree，這個index用來索引對應objects的ID
2.搜索時的輸入是合取范式，這可以看作是每個連接組件的結果的并集
3.每個連接組件，可以作為可認證的連接查詢，在查詢關鍵字的MBTree上進行處理
帶來問題：
存儲操作過多，在鏈上智能合約維護這個index開銷很大

Suppressed Merkle inv index
主要思想：智能合約只維護 Merkle inv index中每個 MB-tree 的根摘要。
因為：在可認證的關鍵字查詢時只有鏈上ADS中的根摘要用到了
更新時，有新數據進來，SP發(fā)送update proof給智能合約，由可認證的信息組成，來安全計算新的根摘要
存儲操作變成常數級別（貴）
內存操作變成對數級別（便宜）

Chameleon inverted (Chameleon inv) index
index的作用：恒定維護成本
CVC作用：
1.可以公開驗證存儲在向量中的數據。
2.數據所有者可以通過使用秘密陷門來更新向量而不改變其承諾
所以用CVC可以構建具有不變根承諾的變色龍樹。

在這個index里，每個關鍵詞是一棵Chameleon樹
智能合約使用這個index的一些輔助數據維護根承諾，SP 維護完整的index以進行高效的查詢處理。

兩者概述：
Suppressed Merkle inv index：在智能合約維護ADS中，減少gas
Chameleon inverted (Chameleon inv) index：進一步減少ADS維護成本到一個恒定值，且仍然高效查詢

問題定義

Fig.1
O object
id
{wi} 一組與object關聯(lián)的關鍵詞
v object的內容

新對象到了之后，DO發(fā)送給
SP：<id, {wj}, vi>
區(qū)塊鏈：<id, {wj}, h(oi)>
??
作用：保證數據完整性的同時降低了存儲

SP和智能合約都維護ADS，DO調用智能合約維護鏈上的ADS，SP同步更新區(qū)塊鏈上最新確認的對象
ADS的digest就是SP和智能合約共享的認證信息（authenticated information）

本文的查詢：關鍵字查詢
查詢輸入：單調布爾表達式Q，是DNF
用戶檢索得到的輸出：R = {oi = <id, {wj}, vi> | Q({wj}) = true}
Q = q1 ∨ q2 ∨ · · · ∨ qn
qi = w1 ∧ w2 ∧ · · · ∧ wl

查詢過程：
客戶端向SP發(fā)送關鍵字查詢請求->SP用ADS計算查詢結果和驗證對象VOsp
result和VOsp都發(fā)送給客戶
驗證過程：
客戶從區(qū)塊鏈檢索認證摘要VOchain，客戶通過VOchian和VOsp驗證result的正確性

提出問題：
integrity
soundness
completeness

本文中研究的問題是：如何設計能夠由鏈上智能合約有效維護的 ADS，在 gas 成本方面，同時有效地支持混合中的認證關鍵字搜索-存儲區(qū)塊鏈。

原文中，第 III 節(jié)中提供了一些初步信息，然后介紹了一個baseline解決方案，然后在第 IV 節(jié)和第 V 節(jié)中介紹了兩種節(jié)能 ADS 方案。

基礎前提

密碼學原語

MHT：
1.每個葉節(jié)點是索引對象的digest
2.根哈希由DO簽名并公開
3.可以用來認證數據對象的任意子集是否被存在葉節(jié)點，復雜度是對數級別
4.在關系型數據庫里，已經從二叉樹擴展到了多路樹

Vector Commitment（VC）
1.把變長向量映射成定長的承諾
2.可以證明mi是第i個承諾信息
3.
? Gen(1λ, q)：q為向量大小，輸出-公共參數pp
? Compp(<m1, m2, · · · , mq>, r)：<>內為有q個message的向量，輸出-承諾c、輔助信息aux
? Openpp(i, m, aux)：當且僅當m是向量（vector w.r.t. c）里第i個message時，返回一個證明π
? Verpp(c, i, m, π): 當且僅當π通過驗證——c是根據消息序列來計算的，這個消息序列m在位置i，這個函數返回1

CVC
不改變承諾c的情況下改變m
CGen(1λ, q)：輸出pp和td(trapdoor)
CColpp(c, i, m, m’, td, aux)：計算出一個新aux’，當不是m而是m’在第i個位置的時候，承諾還是c
Openpp(i, m’, aux’)：輸出π’
Verpp(c, i, m’, π’)：輸出1，證明m’是c向量存的第i個message

可認證關鍵字搜索過程

兩個MB-Tree上的可認證連接處理：
S和R是兩個表，里面的內容用樹Ts和Tr索引
1.從Tr樹的r1作為目標開始，在樹Ts的匹配對象是s3，邊界對象是s4
2.下一輪，交換Ts和Tr的角色
3.目標變?yōu)閟4，檢索到邊界對象r2
4…角色切換一直到目標為r5，它的左邊界對象是s12，s12是Ts的最后一個葉節(jié)點
結果驗證：
1.所有匹配和邊界對象，以及它們的Merkel proof（圖中陰影部分），都添加到VO
2.客戶把每棵樹根據這些陰影部分重新構建，對比DO簽名的根，來證明匹配的和邊界目標的完整性
3.客戶端檢查每一輪的目標是否是上一輪的右邊界，并且在對應的邊界內，確保沒有丟失任何信息

Suppressed Merkle inv index

先介紹倒排索引

倒排索引：
由一個關鍵字字典組成，每個關鍵字都指向一個包含該關鍵字的對象列表

1.為了支持可認證的關鍵字查詢，給每個關鍵字的對象列表構建一個 MB-tree，這個ADS就是(Merkle inv) index
2.每個 MB-tree的搜索鍵就是對象ID（且假設對象id遞增，比如用時間戳）
3.當有一個新object進入這個ADS時，這個object的ID和hash值<oi.id, h(oi)>會被插入每個相關關鍵詞的MB-tree

Suppressed Merkle inv Index：
鏈上的MBTrees只存根哈希，以減少維護成本
SP上存MBTrees的完整結構，以支持高效查詢

問題：
智能合約怎樣能在不知道完整MBTree結構的情況下維護根哈希？
1.讓SP，在新對象插入時構造一個UpdVO
2.UpdVO由足夠的可認證信息組成
3.然后被發(fā)送到智能合約進行根哈希的更新

下面部分詳細介紹UpdVO怎么構造、怎么用它更新根哈希

構造（算法1）：SP從上往下遍歷，如果不是葉節(jié)點，就把它的孩子，除了最右的孩子append進UpdVO，直到葉節(jié)點，這個葉節(jié)點就是最新進來的object的ID，因為是按照時間戳的

智能合約驗證UpdVO：
1.對比UpdVO一起發(fā)來的新object的哈希和DO發(fā)來的哈希
2.對比SP發(fā)來的其他信息，也就是根據UpdVO自底向上重建，然后與存在鏈上的對比，匹配上了就可以證明UpdVO的完整性

智能合約更新MB-Tree的根哈希（算法2）：驗證了UpdVO的完整性后再更新。
1.與插入類似，先計算葉節(jié)點的哈希，然后逐層向上計算
2.如果因為溢出拆分節(jié)點，用內存變量h’記錄更新后的哈希值（如果沒有分裂），用h1’和h2’記錄兩個拆分的節(jié)點的哈希（如果分裂了，要分別重新計算再存儲）
3.最后，更新的根哈希被智能合約存儲到鏈上
4.如果成功，智能合約發(fā)送一個事件指示更新操作的完成，如“Successful update for UpdVO.h(o)”
5.SP收到這個事件后才能用更新后的ADS進行后續(xù)的查詢操作

每一個關鍵字的MBTree更新需要的消耗：
1.UpdVO由SP送給智能合約，有交易成本
2.UpdVO的完整性驗證（驗證新Object和樹的每一層）
3.更新MBTree的根哈希，并且有可能要拆分
4.智能合約把根哈希更新到鏈上

成本低的操作，系數是對數級的，成本高的操作，系數是常數級的

Chameleon inverted (Chameleon inv) index

因為MBTree的結構，Merkel inv index還是對數級別的花費
Chameleon inv index可以使花費變成常數級別

A:Overview of the Chameleoninv Index

Chameleon Tree
1.是一個q叉樹，每個節(jié)點對應一個object和位置pos，從上到下從左到右數數來分配pos
2.根節(jié)點：沒有對應對象，它只包括一個CVC，計算見橙色波浪線（q+1個0組成的message向量，sk是DO的私鑰，w是關鍵字）
3.（見Fig.8） 每個非根節(jié)點：由四個部分組成 {h(o), Cpos, πpos, ρpar,j}，Cpos的計算與根不同，多并入了pos；
πpos證明h(o)是存儲在更新后的Cpos向量里的第一個元素；
ρpar,j證明這個節(jié)點鏈接到了父節(jié)點第j個子節(jié)點par的位置，父節(jié)點位置是par，證明這個節(jié)點是par的子節(jié)點中的第j個

πpos和ρpar,j的生成? B部分
自上而下遍歷可以很快驗證O C部分

1.初始節(jié)點都是用q+1個0組成的常數，和固定的數預定義的，之后用陷門更新，向量改變，CVC不改變
2.更新了（插入了新object）的節(jié)點總是從左往右與父節(jié)點相連
由以上兩點，給定對象總數，就能確定Chameleon Tree的結構
所以鏈上維護的是cnt的值，是常數級的。

Chameleon inv index中，每個關鍵字一棵Chameleon tree
智能合約只要維護根CVC（不變）和cnt，只有這兩者在可認證關鍵字查找里有作用，作為可認證信息

B:Maintenance of the Chameleoninv Index

Chameleon inv index的維護

初始化，由DO創(chuàng)建初始的Chameleon tree：（算法3）
1.從創(chuàng)建必要的keys開始創(chuàng)建，比如sk、td、pp（比如pp就是Gen函數生成的），且sk和td需要DO保管好，不然就可以篡改index了
2.這些keys生成好后就可以計算出根節(jié)點的CVC
3.把w（關鍵詞）和這個CVC（C0）發(fā)送給鏈和SP

插入新O：（算法4）
1.給O創(chuàng)建一個新節(jié)點
①分配一個新pos，并計算初始CVC（Cpos）
②DO用td找到CVC的collision，更新向量的第一個元素變?yōu)閷ο蟮墓(o)
③生成πpos
2.鏈接到對應的父節(jié)點
①DO定位父節(jié)點npar（par暫且認為就是object的ID）和CVC里的j
②npar里的Cpar要重新計算，找一個collision第j+1個元素，更新為Cpos（第一個元素存自己的h(o)，后面的存子節(jié)點的C？標號：j和j+1）
③計算相應證明ρpar,j，證明npos是npar的第j個子節(jié)點
3.<cpos, πpos, ρpar,j>作為新Object的插入證明，DO把這個插入證明、cnt、O、h(o)發(fā)送給SP，把cnt、w發(fā)給區(qū)塊鏈

π是自己（即第1個element）的collision證明，ρ是父節(jié)點的，替換父節(jié)點的第j+1個位置（還是第j個？）一個節(jié)點有兩個message向量嗎
是第j+1，向量也是p+1個分量

C: Authenticated Keyword Search with Chameleoninv Index

認證關鍵字查詢

成員資格測試（證明pos位置上有一個object存在）
1.SP生成一個membership prrof，包括：前面的插入證明+所有除根節(jié)點的祖先節(jié)點（自己的C、π、 ρ，祖先的C、ρ）
2.客戶驗證：自下而上遞歸
①自己的π證明自己存在，
②自己的ρ證明是父節(jié)點的第i個孩子，
③父節(jié)點的ρ和根節(jié)點的C(這個C從鏈上得到)證明父節(jié)點是根的第i個孩子，驗證完成

認證關鍵字搜索（算法5）
給每個Chameleon tree建一個object ID和位置的映射哈希表
連接過程：
1.連接也在兩棵樹之間輪換
2.每一輪，目標、匹配、邊界的objects都被加入VOsp
3.兩棵樹切換角色以找到匹配的對象，直到到達一棵樹的末端。

客戶端驗證（算法6）類似于兩個樹的連接過程：（注意到這個連接和Fig.4的連接略有不同）
1.客戶端檢索每個相關的C0和cnt（也就是VOchain）
2.客戶端檢查每輪連接的VOsp
①本輪的目標的位置是否為1或者上一輪的邊界的位置
②用membership proof證明邊界對象的完整性
③用membership proof證明目標的完整性，并且如果這個ID和左邊界ID匹配就加入到結果
④驗證目標對象ID在左右邊界ID之間
⑤最后一輪時，客戶端額外檢查中止位置不能比cnt小
②③保證了健全性(都存在) ①④⑤保證了完整性(無遺漏)

論文筆記僅為個人觀點，僅供參考文章來源地址http://www.zghlxwxcb.cn/news/detail-799644.html

到了這里，關于論文筆記-Authenticated Keyword Search in Scalable Hybrid-Storage Blockchains的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！