论文笔记-Authenticated Keyword Search in Scalable Hybrid-Storage Blockchains

这篇具有很好参考价值的文章主要介绍了论文笔记-Authenticated Keyword Search in Scalable Hybrid-Storage Blockchains。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

混合存储模型:
只有少量meta-data(加密哈希)存在链上,原始数据外包给链下的存储服务商
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链

贡献

提出了一个新的ADS
1.首先提出了抑制默克尔倒置(Merkle inv)索引,该索引仅在链上维护部分 ADS 结构,可以使用对数加密证明进行安全更新。
2.提出了一个变色龙倒置(Chameleon inv)索引,它利用变色龙向量承诺来实现恒定的维护成本。它使用Bloom过滤器进一步优化,以增强查询和验证性能。

问题:
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发送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维护成本到一个恒定值,且仍然高效查询

问题定义

authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
Fig.1
O object
id
{wi} 一组与object关联的关键词
v object的内容

新对象到了之后,DO发送给
SP:<id, {wj}, vi>
区块链:<id, {wj}, h(oi)>
👇
作用:保证数据完整性的同时降低了存储

SP和智能合约都维护ADS,DO调用智能合约维护链上的ADS,SP同步更新区块链上最新确认的对象
ADS的digest就是SP和智能合约共享的认证信息(authenticated information)

本文的查询:关键字查询
查询输入:单调布尔表达式Q,是DNF
用户检索得到的输出:R = {oi = <id, {wj}, vi> | Q({wj}) = true}
Q = q1 ∨ q2 ∨ · · · ∨ qn
qi = w1 ∧ w2 ∧ · · · ∧ wl

查询过程:
客户端向SP发送关键字查询请求->SP用ADS计算查询结果和验证对象VOsp
result和VOsp都发送给客户
验证过程:
客户从区块链检索认证摘要VOchain,客户通过VOchian和VOsp验证result的正确性

提出问题:
integrity
soundness
completeness

本文中研究的问题是:如何设计能够由链上智能合约有效维护的 ADS,在 gas 成本方面,同时有效地支持混合中的认证关键字搜索-存储区块链。

原文中,第 III 节中提供了一些初步信息,然后介绍了一个baseline解决方案,然后在第 IV 节和第 V 节中介绍了两种节能 ADS 方案。

基础前提

密码学原语

MHT:
1.每个叶节点是索引对象的digest
2.根哈希由DO签名并公开
3.可以用来认证数据对象的任意子集是否被存在叶节点,复杂度是对数级别
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

可认证关键字搜索过程

authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
两个MB-Tree上的可认证连接处理:
S和R是两个表,里面的内容用树Ts和Tr索引
1.从Tr树的r1作为目标开始,在树Ts的匹配对象是s3,边界对象是s4
2.下一轮,交换Ts和Tr的角色
3.目标变为s4,检索到边界对象r2
4…角色切换一直到目标为r5,它的左边界对象是s12,s12是Ts的最后一个叶节点
结果验证
1.所有匹配和边界对象,以及它们的Merkel proof(图中阴影部分),都添加到VO
2.客户把每棵树根据这些阴影部分重新构建,对比DO签名的根,来证明匹配的和边界目标的完整性
3.客户端检查每一轮的目标是否是上一轮的右边界,并且在对应的边界内,确保没有丢失任何信息

Suppressed Merkle inv index

先介绍倒排索引
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
倒排索引:
由一个关键字字典组成,每个关键字都指向一个包含该关键字的对象列表

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.然后被发送到智能合约进行根哈希的更新

下面部分详细介绍UpdVO怎么构造、怎么用它更新根哈希

authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
构造(算法1):SP从上往下遍历,如果不是叶节点,就把它的孩子,除了最右的孩子append进UpdVO,直到叶节点,这个叶节点就是最新进来的object的ID,因为是按照时间戳的
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链

智能合约验证UpdVO
1.对比UpdVO一起发来的新object的哈希和DO发来的哈希
2.对比SP发来的其他信息,也就是根据UpdVO自底向上重建,然后与存在链上的对比,匹配上了就可以证明UpdVO的完整性

authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
智能合约更新MB-Tree的根哈希(算法2):验证了UpdVO的完整性后再更新。
1.与插入类似,先计算叶节点的哈希,然后逐层向上计算
2.如果因为溢出拆分节点,用内存变量h’记录更新后的哈希值(如果没有分裂),用h1’和h2’记录两个拆分的节点的哈希(如果分裂了,要分别重新计算再存储)
3.最后,更新的根哈希被智能合约存储到链上
4.如果成功,智能合约发送一个事件指示更新操作的完成,如“Successful update for UpdVO.h(o)”
5.SP收到这个事件后才能用更新后的ADS进行后续的查询操作
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链

每一个关键字的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

authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
Chameleon Tree
1.是一个q叉树,每个节点对应一个object和位置pos,从上到下从左到右数数来分配pos
2.根节点:没有对应对象,它只包括一个CVC,计算见橙色波浪线(q+1个0组成的message向量,sk是DO的私钥,w是关键字)
3.(见Fig.8) 每个非根节点:由四个部分组成 {h(o), Cpos, πpos, ρpar,j},Cpos的计算与根不同,多并入了pos;
πpos证明h(o)是存储在更新后的Cpos向量里的第一个元素;
ρpar,j证明这个节点链接到了父节点第j个子节点par的位置,父节点位置是par,证明这个节点是par的子节点中的第j个
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链

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

1.初始节点都是用q+1个0组成的常数,和固定的数预定义的,之后用陷门更新,向量改变,CVC不改变
2.更新了(插入了新object)的节点总是从左往右与父节点相连
由以上两点,给定对象总数,就能确定Chameleon Tree的结构
所以链上维护的是cnt的值,是常数级的。

Chameleon inv index中,每个关键字一棵Chameleon tree
智能合约只要维护根CVC(不变)和cnt,只有这两者在可认证关键字查找里有作用,作为可认证信息

B:Maintenance of the Chameleoninv Index

Chameleon inv index的维护

初始化,由DO创建初始的Chameleon tree:(算法3)
1.从创建必要的keys开始创建,比如sk、td、pp(比如pp就是Gen函数生成的),且sk和td需要DO保管好,不然就可以篡改index了
2.这些keys生成好后就可以计算出根节点的CVC
3.把w(关键词)和这个CVC(C0)发送给链和SP
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链

插入新O:(算法4)
1.给O创建一个新节点
①分配一个新pos,并计算初始CVC(Cpos)
②DO用td找到CVC的collision,更新向量的第一个元素变为对象的哈希h(o)
③生成πpos
2.链接到对应的父节点
①DO定位父节点npar(par暂且认为就是object的ID)和CVC里的j
②npar里的Cpar要重新计算,找一个collision第j+1个元素,更新为Cpos(第一个元素存自己的h(o),后面的存子节点的C?标号:j和j+1)
③计算相应证明ρpar,j,证明npos是npar的第j个子节点
3.<cpos, πpos, ρpar,j>作为新Object的插入证明,DO把这个插入证明、cnt、O、h(o)发送给SP,把cnt、w发给区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链

π是自己(即第1个element)的collision证明,ρ是父节点的,替换父节点的第j+1个位置(还是第j个?)一个节点有两个message向量吗
是第j+1,向量也是p+1个分量

C: Authenticated Keyword Search with Chameleoninv Index

认证关键字查询

成员资格测试(证明pos位置上有一个object存在)
1.SP生成一个membership prrof,包括:前面的插入证明+所有除根节点的祖先节点(自己的C、π、 ρ,祖先的C、ρ)
2.客户验证:自下而上递归
①自己的π证明自己存在,
②自己的ρ证明是父节点的第i个孩子,
③父节点的ρ和根节点的C(这个C从链上得到)证明父节点是根的第i个孩子,验证完成

认证关键字搜索(算法5)
给每个Chameleon tree建一个object ID和位置的映射哈希表
连接过程:
1.连接也在两棵树之间轮换
2.每一轮,目标、匹配、边界的objects都被加入VOsp
3.两棵树切换角色以找到匹配的对象,直到到达一棵树的末端。
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链

客户端验证(算法6)类似于两个树的连接过程:(注意到这个连接和Fig.4的连接略有不同)
1.客户端检索每个相关的C0和cnt(也就是VOchain)
2.客户端检查每轮连接的VOsp
①本轮的目标的位置是否为1或者上一轮的边界的位置
②用membership proof证明边界对象的完整性
③用membership proof证明目标的完整性,并且如果这个ID和左边界ID匹配就加入到结果
④验证目标对象ID在左右边界ID之间
⑤最后一轮时,客户端额外检查中止位置不能比cnt小
②③保证了健全性(都存在) ①④⑤保证了完整性(无遗漏)
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链
authenticated keyword search in scalable hybrid-storage blockchains,笔记,区块链

论文笔记仅为个人观点,仅供参考文章来源地址https://www.toymoban.com/news/detail-799644.html

到了这里,关于论文笔记-Authenticated Keyword Search in Scalable Hybrid-Storage Blockchains的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【论文笔记】OpenAI宫斗背后:发现了可能优于小鸡毛表现的机器人,AGI的希望 Q* search and Q transformer(A star search with Q-Learning)

            最近OpenAI的宫斗剧上演的精妙绝伦,简直就是《硅谷》+《继承》,强烈推荐这两部剧集。AIGC的群里都在说Q*是揭示AI接近AGI的一篇论文,那就费点时间拨开云雾吧。为了方便大众更好地理解Q*,本人在快速浏览过论文后首先得出此结论公式:         Q* = (1992年的

    2024年02月05日
    浏览(64)
  • 论文阅读《Block-NeRF: Scalable Large Scene Neural View Synthesis》

    论文地址:https://arxiv.org/pdf/2202.05263.pdf 复现源码:https://github.com/dvlab-research/BlockNeRFPytorch   Block-NeRF是一种能够表示大规模环境的神经辐射场(Neural Radiance Fields)的变体,将 NeRF 扩展到渲染跨越多个街区的城市规模场景。该方法将场景分解为单独训练的 NeRF,使渲染时间与

    2024年02月03日
    浏览(46)
  • NICE-SLAM: Neural Implicit Scalable Encoding for SLAM论文阅读

    标题 :NICE-SLAM: Neural Implicit Scalable Encoding for SLAM 作者 :Zihan Zhu, Songyou Peng,Viktor Larsson — Zhejiang University 来源 :CVPR 代码 :https://pengsongyou.github.io/nice-slam 时间 :2022 神经隐式(Neural implicit representations)表示最近在同步定位和地图绘制(SLAM)方面有一定的进展,但现有方法

    2024年02月15日
    浏览(53)
  • 论文中文翻译——VulCNN An Image-inspired Scalable Vulnerability Detection System

    论文下载地址——Web Of Science 论文中文翻译——VulCNN An Image-inspired Scalable Vulnerability Detection System   此博客为VulCNN An Image-inspired Scalable Vulnerability Detection System论文的中文翻译,本篇论文将漏洞检测与图分类联系到一起,并结合神经网络进行漏洞检测,思路比较新奇,效果看来

    2024年02月05日
    浏览(53)
  • Attentive Moment Retrieval in Videos论文笔记

    2018 Attentive Moment Retrieval in Videos 设计了一种记忆注意机制来强调查询中提到的视觉特征,并同时合并它们的上下文,在DiDeMo and TACoS两个数据集表现的比较好。 候选时刻的选择和相关性估计是任务的关键所在,目前常见的方法是在不同尺度上对滑动窗口进行密集采样。但是这

    2024年02月11日
    浏览(40)
  • 论文笔记——Influence Maximization in Undirected Networks

    好久没发paper笔记了,这篇比较偏理论,可能边看边记比较高效一些,仅作为个人笔记,如有解读不到的还请包涵。这篇paper的贡献有两个,首先是证明了在无向图中使用greedy可以突破 1 − 1 / e 1-1/e 1 − 1/ e 的barrier(也就是greedy在无向图上会更强),达到 1 − 1 / e + c 1-1/e+c

    2024年02月15日
    浏览(42)
  • DIT: Scalable Diffusion Models with Transformers--Sora/SD3相关DIT技术论文阅读

    OpenAI发布Sora,以及Stability.AI发布的SD3,根据其技术报告,使用了可扩展的transformer扩展模型,《Scalable Diffusion Models with Transformers》是其相关的一篇重要论文。 关于DIT作者进阶的论文SIT《SiT: Exploring Flow and Diffusion-based Generative Models with Scalable Interpolant Transformers 》介绍,下一篇

    2024年03月17日
    浏览(39)
  • 论文解析——Ascend: a Scalable and Unified Architecture for Ubiquitous Deep Neural Network Computing

    H. Liao et al., “Ascend: a Scalable and Unified Architecture for Ubiquitous Deep Neural Network Computing : Industry Track Paper,” 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA), Seoul, Korea (South), 2021, pp. 789-801, doi: 10.1109/HPCA51647.2021.00071. 计算核内cube、vector、scaler部件的指令同步 昇腾910包

    2024年03月11日
    浏览(91)
  • 3D Clothed Human Reconstruction in the Wild论文笔记

    论文地址:https://arxiv.org/pdf/2207.10053.pdf 作者:Moon, Gyeongsik, Nam, Hyeongjin, Shiratori, Takaak 发表:CVPR 2022 链接:https://github.com/hygenie1228/ClothWild_RELEASE 最近的大多数三维人体重建方法都需要三维扫描来进行训练;因此,它们是在合成数据集上训练的,这些数据集由3D扫描和从扫描中渲

    2024年01月19日
    浏览(49)
  • Cross-modal Moment Localization in Videos论文笔记

    2018年 Cross-modal Moment Localization in Videos 一种称为“语言-时间注意力网络”的方法,该方法利用视频中的时间上下文信息学习单词的注意力。因此,我们的模型可以自动选择“听哪些单词”以定位所需的瞬间。 以一个具有代表性的查询来说:一个摩天轮首先进入视野。之前的模

    2024年02月09日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包