VeriDKG: A Verifiable SPARQL Query Engine for Decentralized Knowledge Graphs

Enyuan Zhou, Song Guo, Zicong Hong, Christian S. Jensen, Yang Xiao, Dalin Zhang, Jinwen Liang, Qingqi Pei

Research output: Contribution to journalConference article in JournalResearchpeer-review

27 Downloads (Pure)

Abstract

The ability to decentralize knowledge graphs (KG) is important to exploit the full potential of the Semantic Web and realize the Web 3.0 vision. However, decentralization also renders KGs more prone to attacks with adverse effects on data integrity and query verifiability. While existing studies focus on ensuring data integrity, how to ensure query verifiability - thus guarding against incorrect, incomplete, or outdated query results - remains unsolved. We propose VeriDKG, the first SPARQL query engine for decentralized knowledge graphs (DKG) that offers both data integrity and query verifiability guarantees. The core of VeriDKG is the RGB-Trie, a new blockchain-maintained authenticated data structure (ADS) facilitating correctness proofs for SPARQL query results. VeriDKG enables verifiability of subqueries by gathering global index information on subgraphs using the RGB-Trie, which is implemented as a new variant of the Merkle prefix tree with an RGB color model. To enable verifiability of the final query result, the RGB-Trie is integrated with a cryptographic accumulator to support verifiable aggregation operations. A rigorous analysis of query verifiability in VeriDKG is presented, along with evidence from an extensive experimental study demonstrating its state-of-the-art query performance on the largeRDFbench benchmark.
Original languageEnglish
JournalProceedings of the VLDB Endowment
Volume17
Issue number4
Pages (from-to)912-925
Number of pages14
ISSN2150-8097
DOIs
Publication statusPublished - Dec 2023
Event50th International Conference on Very Large Data Bases - Gungzhou, China
Duration: 25 Aug 202429 Aug 2024
https://vldb.org/2024/

Conference

Conference50th International Conference on Very Large Data Bases
Country/TerritoryChina
CityGungzhou
Period25/08/202429/08/2024
Internet address

Fingerprint

Dive into the research topics of 'VeriDKG: A Verifiable SPARQL Query Engine for Decentralized Knowledge Graphs'. Together they form a unique fingerprint.

Cite this