(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210385844.7 (22)申请日 2022.04.13 (71)申请人 北京理工大 学 地址 100081 北京市海淀区中关村南大街5 号 (72)发明人 李丝雨　张志威　袁野　杨晓春　 王国仁　 (74)专利代理 机构 北京正阳理工知识产权代理 事务所(普通 合伙) 11639 专利代理师 张利萍 (51)Int.Cl. G06F 16/36(2019.01) (54)发明名称 一种基于区块链的图谱查询验证方法 (57)摘要 本发明涉及链上链下混合存储区块链领域， 涉及一种基于区块链的 图谱查询验证方法， 特别 涉及基于混合存储区块链的可验证子图查询处 理方法。 本发 明提供了一种基于区块链的图谱查 询验证方法， 完善了区块链中图式结构数据的可 验证查询机制。 本发明通过在服务器端基于大图 顶点的结构信息构建树形可验证索引， 有效捕获 数据以及区块间的复杂拓扑结构， 借助区块链的 不可篡改和可溯源的性质 存储树形可验证索引 的根节点以及大图的哈希值， 实现了查询结果与 验证信息高效 并行生成。 权利要求书2页 说明书6页 附图1页 CN 114840681 A 2022.08.02 CN 114840681 A 1.一种基于区块链的图谱查询验证方法， 其特 征在于包括以下步骤： S1， 服务器端根据大图顶点的结构信息计算大图的哈希值并构建类Merkle  Patricia   Trie的树形 可验证索引结构， 将计算得到的大图哈希值和树的根节点哈希值存 储在链上； S2， 客户端向服务器端发起子图查询请求， 服务器端利用S1得到的可验证索引结构进 行查询处 理， 生成查询结果子图以及可验证信息返回给客户端； S3， 客户端根据 可验证信息和查询结果子图重建根节点哈希值和大图哈希值并与S1中 存储在链上的大图哈希值和树的根节点哈希值进 行对比， 以此验证查询结果的正确性和完 整性。 2.根据权利要求1所述的一种基于区块链的图谱查询验证方法， 其特 征在于： 所述S1中的服 务器端的角色由混合存 储区块链中的全节点充当。 3.根据权利要求1所述的一种基于区块链的图谱查询验证方法， 其特 征在于： 所述S1中的， 客户端的角色由混合存 储区块链中的轻节点或外 部节点充当。 4.根据权利要求1所述的一种基于区块链的图谱查询验证方法， 其特 征在于： 所述S1中的服务器端由链上存储和链下存储两部分构 成， 链下负责存储大图的内容和 结构信息以及构建的树形可验证索引信息， 链上负责存储大图的哈希值以及树形可验证索 引的根节点哈希值。 5.根据权利要求1 ‑4任一所述的一种基于区块链的图谱查询验证方法， 其特 征在于： 所述步骤S1中的具体步骤为： S11， 大图顶点的结构信息指的是每个顶点一跳内的所有邻居， 计算某顶点一跳内邻居 的标记的哈希值的异或和， 对该异或和进行哈希计算作为该顶点的结构哈希值； 服务器端根据 大图顶点的结构信 息计算大图的哈希值的方法为： 采用广度优先遍历的 方法， 依次访问并计算大图中每个顶点的结构哈希值， 将计算得到的所有顶点的结构哈希 值求取异或和， 对该异或和进行最后的哈希计算得到最终的大图哈希值存 储在链上； S12， 服务器端基于大图顶点的结构信息构建类Merkle  Patricia  Trie的树形可验证 索引结构的方法为： (1)将大图中每个顶点一跳内所有邻居顶点的标记按照字典序排序得 到大图中每个顶点的结构信息表达； (2)基于所有顶点的结构信息表达构建前缀树索引； (3)为构建好的前缀树索引中的每个节点添加可验证信息得到类Merkle  Patricia  Trie的 树形可验证索引结构， 并将根节点的哈希值存 储在链上。 6.根据权利要求5所述的一种基于区块链的图谱查询验证方法， 其特 征在于： 所述步骤S2中的具体步骤为： S21、 服务器端在接收到来自客户端的子图查询请求后， 首先对查询子图进行预处理， 即为查询子图中的每 个顶点构建如步骤S12中的(1)中的结构信息表达； S22、 服务器端根据查询顶点的结构信息表达， 利用树形可验证索引进行搜索， 为查询 子图中的每个查询顶 点生成候选集， 并将搜索路径上所有访问过的节点和其兄弟 节点的哈 希值加入可验证信息VO1中； S23、 服务器端根据定义的cost  function计算每个查询顶点的cost， cost包括匹配效 率和生成的可验证信息VO2的大小， 选择一个具有最低cost的查询顶点由此开始匹配； S24、 服务器端在大图中按层扩展选定的查询顶点候选集中的每个候选顶点得到匹配 结果子图和可验证信息VO2， 按层 扩展指的是按照每个顶点的一跳邻居、 两跳邻居等这样扩权　利　要　求　书 1/2 页 2 CN 114840681 A 2展， 扩展的层数 取决于选定的查询顶点扩展得到整个查询子图需要扩展的层数。 7.根据权利要求6所述的一种基于区块链的图谱查询验证方法， 其特 征在于： 所述步骤S3中的具体步骤为： S31、 客户端首 先从链上获取 大图的哈希值和树形 可验证索引的根节点哈希值； S32、 客户端根据可验证信息VO1自底向上重建树形可验证索引根节点的哈希值， 之后 与链上获取的根节点哈希值进 行对比， 若二者一致则说明服务器端通过树形可验证索引搜 索得到的查询顶点的候选集是正确且完整的， VO1验证通过； S33、 客户端验证VO1通过后， 首先根据 查询顶点候选集结合可验证信息VO2判断是否所 有的候选顶 点都得到了扩展， 之后借助VO2重新进 行子图匹配， 将得到的结果与服务器端返 回的结果进行对比并重新计算大图的哈希值， 与链上获取 的大图哈希值进行对比， 若都是 一致则说明服 务器端匹配得到的结果子图是正确且完整的。 8.根据权利要求1所述的一种基于区块链的图谱查询验证方法， 其特 征在于： 该方法利用区块链上数据的不可篡改和可溯源性保证链上存储的哈希值的安全性， 并 根据构建的树形 可验证索引实现可验证子图查询。权　利　要　求　书 2/2 页 3 CN 114840681 A 3