Database
VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System
arXiv cs.CR0 views
arXiv:2611.04240v2 Announce Type: replace Abstract: Graph databases are widely used to manage relationship-rich data and support multi-hop traversal and shortest-path queries in applications such as financial risk control and social networks. When a client issues such queries to a database owner, the returned result may be incorrect. However, the client cannot directly verify it because the graph is typically large and private, making re-executing the query both infeasible and insecure. Verifiable and confidential graph query evaluation thus plays an important role in such applications. We present VerfGraph, a zero-knowledge verifiable graph query evaluation system, which enables a client to verify that the query result was correctly computed over a committed graph, without revealing anything beyond the public inputs and what is implied by the query result. While adopting the expansion-centric operator model introduced by ZKGraph (ICDE'26), VerfGraph improves both proving efficiency and query expressiveness in two key ways. First, we propose new proof methods for the core operators in ZKGraph, such as graph expansion and shortest path, that require substantially fewer expensive comparisons and eliminate edge canonicalization for bidirectional edge relations. Second, we introduce dedicated proofs for count and weighted shortest-path operators, which ZKGraph does not support, broadening the class of graph queries that can be verified. We evaluate VerfGraph using the LDBC Social Network Benchmark. Compared with the state-of-the-art zero-knowledge graph query system ZKGraph on complex IC queries, VerfGraph achieves $33.9\times$-$59.7\times$ speedups in proof generation and reduces peak prover memory by a factor of $4.5\times$-$6.6\times$, while maintaining millisecond-level verification and producing sub-MB proofs.
Source:https://arxiv.org/abs/2611.04240PreviousFrom TS-SUF-2 to TS-SUF-4: Practical Security Enhancements for FROST2 Threshold SignaturesNextCoordX Types: A Trustless, Swappable Type System for Shared Records
Related posts
WordPress Güncelleme Sonrası Çöken Siteyi Kurtarma Rehberi
0dev.to PHP
![Robot Database and Storage — Ch.10: Database Replication and HA [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fbjp07uvlsesy9gh6elq8.png)
Robot Database and Storage — Ch.10: Database Replication and HA [EN]
0dev.to Programming
Build a Production-Ready REST API with Spring Boot 3 and PostgreSQL
0dev.to Java
WordPress Bozuk Veritabanı Tablolarını phpMyAdmin ile Onarma
0dev.to Database
Ranking lifetime free credit cards by rupees returned
0dev.to WebDev
Technical Audits: What to Look For Before Series A
0dev.to WebDev