VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System

arXiv:2611.04240v1 [cs.CR] 3 Nov 2026

VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System Tianyi Ma

Yuncong Zhang

Yuanzhuo Yu

Shanghai Jiao Tong University mty021129@sjtu.edu.cn

Shandong University yuncong@sdu.edu.cn

Shanghai Jiao Tong University yzyu2000@sjtu.edu.cn

Boshi Yuan

Shi-Feng Sun

Shanghai Jiao Tong University nemoyuan2008@sjtu.edu.cn

Shanghai Jiao Tong University shifeng.sun@sjtu.edu.cn

Abstract—Graph databases are often used to manage relationship-rich data, whose graph structure and attributes may be sensitive. In many applications, a database owner or a service provider evaluates queries over a private graph for a client. Because the graph cannot be fully disclosed and independently reexecuting the query may be impractical, the client cannot directly verify the returned result. This creates a need for verifiable graph query evaluation that preserves data confidentiality. We present VerfGraph, a zero-knowledge system for verifiable graph query evaluation, which enables a client to verify that the query result was correctly computed over a committed graph data, without revealing private graph records or intermediate query values beyond the public inputs and what is implied by the query result. Building on the expansioncentric model introduced by the state-of-the-art zero-knowledge verifiable graph query evaluation system ZKGraph (ICDE’26), VerfGraph achieves more efficient and expressive zero-knowledge verifiable graph query evaluation by advancing design in two key ways. First, we propose novel operator-proof methods for core expansion and shortest-path operations that reduce costly sorting and comparison checks and eliminate edge canonicalization for bidirectional expansion. Furthermore, we introduce correctness proofs for count and weighted shortest-path operators, broadening the class of graph queries that can be verified. We evaluate VerfGraph using the LDBC Social Network Benchmark. Compared with ZKGraph on complex IC queries, VerfGraph achieves 33.9×–59.7× speedups in proof generation and reduces peak prover memory by factors of 4.5×–6.6×, while maintaining millisecond-level verification and producing sub-MB proofs. Index Terms—graph databases, verifiable query evaluation, zero-knowledge proofs, database security

I. I NTRODUCTION Graph databases organize data around entities and relationships, making them well suited to workloads dominated by neighborhood exploration, multi-hop connectivity, and path analysis [1]–[3]. In outsourced or cross-organizational deployments, however, the party that evaluates a query may not be fully trusted. A service provider may evaluate a query against an unintended or stale snapshot, omit qualifying vertices or paths, or return an incorrect result because of implementation faults or adversarial behavior. Because the client neither sees the private graph nor can necessarily afford to replay an expensive traversal, the query result alone does not establish that it was computed faithfully.

This setting gives rise to two coupled requirements. The first is confidentiality: the raw graph, sensitive node and edge properties, and private intermediate results should remain hidden except for information revealed by an authorized query answer. The second is verifiability: the client should be able to establish that the reported answer is sound and complete with respect to a precisely specified query and a public commitment to an agreed graph snapshot. Neither requirement implies the other. Revealing the graph enables direct recomputation but defeats confidentiality, whereas keeping the graph private without cryptographic evidence forces the client to trust an opaque execution process. For example, consider an e-commerce platform that maintains a private graph whose vertices represent products, sellers, and buyers, and whose edges encode transactions, co-purchase relationships, and referral links. An external auditor may be authorized to ask for the number of buyers reachable from a suspicious seller within a fixed number of hops and the minimum-risk referral path between two flagged accounts, where edge weights encode risk scores. Disclosing the full graph would reveal sensitive commercial and user data, yet returning only the count and path gives the auditor no basis for detecting omitted edges, use of an outdated snapshot, or an incorrectly computed path. A suitable protocol should bind both answers to the same committed graph snapshot and prove the requested properties without exposing unrelated accounts, transactions, or intermediate traversal states. Zero-knowledge proofs (ZKPs) provide a cryptographic foundation for addressing this problem. A ZKP allows a prover to convince a verifier that a public statement is true without revealing the private witness beyond what is implied by the statement [4]. To use ZKPs to establish query correctness, existing ZK database systems commonly decompose queries into operators and design specialized proof constructions for their input–output relations. Proving these input–output relations efficiently is a central challenge: the proofs must establish that each operator’s output is correct and complete without revealing private intermediate values. For example, ZKSQL [5] and PoneglyphDB [6] develop such proof constructions for relational operators, including sorting, joins, and aggregation.

However, graph queries introduce proof requirements, such as establishing shortest-path optimality and correctly handling traversal over bidirectional edge relations, for which these systems do not directly provide specialized proof constructions. To address these requirements, ZKGraph [7] introduces an expansion-centric model for decomposing queries into composable operators, including single-source expansion, set-based expansion, and single-source shortest path (SSSP), and develops specialized proof constructions for these operators. Through these operator-proof constructions, ZKGraph demonstrates the feasibility of using zero-knowledge proofs to support confidential and verifiable graph query evaluation. Despite this progress, two limitations remain. First, ZKGraph’s constructions for set-based expansion and bidirectional edge relations rely on repeated comparisons [7]. Proving these comparisons requires a large number of range checks to establish whether one value is greater than another, and performing these checks across graph records increases proof-generation costs. However, simply removing these range checks would no longer guarantee operator correctness, so new proof constructions are needed to preserve correctness while reducing the number of range checks. Second, ZKGraph does not provide dedicated proof constructions for count or weighted SSSP, both of which are important graph query operations, and developing such constructions would broaden the query support of zero-knowledge verifiable graph query systems. To address these limitations, we present VerfGraph, an efficient zero-knowledge verifiable graph query evaluation system. VerfGraph retains ZKGraph’s expansion-centric model and advances the operator design in two ways. First, we propose new proof methods for set-based expansion and for expansion and SSSP over bidirectional edge relations. These methods establish the same operator input–output relations through alternative proof conditions that require fewer comparisons and range checks, preserving correctness and completeness while lowering proof-generation costs. Second, we introduce a dedicated proof construction for the count operator and extend the SSSP construction to weighted graphs, broadening the class of graph queries that can be verified. We implement VerfGraph using Plonky3 [8] with a polynomial commitment scheme (PCS) based on Fast Reed–Solomon Interactive Oracle Proofs of Proximity (FRI) [9]. Unlike ZKGraph’s Halo2/KZG backend [7], this transparent, hash-based backend requires no trusted setup and relies on assumptions believed to resist quantum attacks [10]. We evaluate the performance of VerfGraph using the LDBC SNB benchmark [11]. Compared with ZKGraph on complex IC queries, VerfGraph substantially reduces proof-generation time and peak prover memory while retaining millisecond-level verification and subMB proofs. The remainder of this paper is organized as follows. Section II introduces the necessary background. Section III presents the system overview. Section IV describes the circuit design of the verifiable graph operators. Section V presents our experimental results. Section VI discusses related work,

and Section VII concludes the paper. II. BACKGROUND A. Zero-Knowledge Proofs Zero-knowledge proofs (ZKPs) allow a prover to convince a verifier that a statement is true without revealing private information beyond what the statement itself reveals [4]. In graph query processing, the prover is the server holding the private graph, and the verifier is the client requesting a query. For example, the server may prove that a returned set contains exactly the neighbors of a queried vertex without disclosing the rest of the graph. In this example, the statement concerns the correctness of the returned neighbors, while the private graph records and intermediate values used to establish it form the witness. For practical query verification, a particular class of ZKPs, called zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs), provides three properties: proofs are compact; verification is fast relative to the computation being proved; and proofs can be checked without further interaction with the prover. These properties make zkSNARKs suitable for verifiable graph queries: the server returns the result together with a compact proof, and the client checks it efficiently without accessing the private graph, repeating the query computation, or engaging in further communication with the server. B. AIR Arithmetization To prove query correctness with a zkSNARK, we first express the conditions for a valid result as polynomial equations, called constraints. This translation, known as arithmetization, allows the verifier to check a proof that these equations hold without repeating the query computation. VerfGraph uses an Algebraic Intermediate Representation (AIR) [10], which organizes the values involved in these equations into a table called an execution trace. Each row records a computation step, while the columns store inputs and intermediate values. These polynomial constraints enforce the computation within each row, connect successive rows, and require the relevant trace values to match the public inputs and claimed output. Satisfying these constraints establishes that the trace represents a valid computation producing the claimed result. Example: To illustrate how these constraints establish correctness, consider computing the sum of pairwise products of two vectors, as shown in Figure 1. Let the public inputs be a = (1, 2, 3, 4) and b = (2, 3, 2, 1), and let the claimed output be y = 18. Each row stores two inputs a[i] and b[i], their product p[i], and a running sum s[i]. A local polynomial constraint requires each product to be computed correctly: p[i] − a[i]b[i] = 0 for 0 ≤ i ≤ 3. To accumulate these products, a transition constraint connects consecutive rows: s[i + 1] − s[i] − p[i + 1] = 0 for 0 ≤ i < 3. The boundary constraints s[0] = p[0] and s[3] = y initialize the sum and require its final value to equal the claimed output. With a

row 𝑖

input 𝑎[𝑖 ]

0

1

input 𝑏 [𝑖 ] ×

2

product 𝑝 [𝑖 ] = 𝑎[𝑖 ]𝑏 [𝑖 ] =

running sum 𝑠 [𝑖 ]

2

2 + =

1

2

3

6

2

3

2

6

14

3

4

1

4

𝑦 = 18

public inputs

8

public output

Fig. 1. Four-row multiplication-and-accumulation AIR trace.

and b fixed to the public inputs, these constraints require p = (2, 6, 6, 4) and s = (2, 8, 14, 18). The prover uses the trace as a witness to generate a zkSNARK proving that these constraints hold without revealing private trace values. The same row-oriented representation applies to database scans, accumulations, and iterative graph operations, where repeated steps can be described by the same constraints across rows. C. Permutation, Lookup, and Range Checks This subsection introduces three protocols that are repeatedly used in our graph query proofs: permutation, lookup, and range checks. At the database level, these protocols support bag equality checks, membership checks against a reference table, and integer comparisons through bounded representations, respectively. Each protocol is implemented by a proof circuit, which encodes the conditions that the prover’s data must satisfy. We measure circuit cost by the number of constraints enforced across the execution trace. Permutation check. A permutation check proves that two length-n columns A and B contain the same values with the same multiplicities, regardless of order. The column values belong to a finite field F, a finite set supporting addition, subtraction, multiplication, and division by nonzero values. To compare the columns without matching rows individually, we follow LogUp and the reciprocal argument of Bulletproofs++ [12], [13] and compare sums of reciprocals. These sums use a shared random value β, sampled uniformly from F after both columns have been fixed. The protocol checks whether n−1 n−1 X X 1 1 = . β + A[i] β + B[i] i=0 i=0 This logarithmic-derivative equality always holds for equal multisets when all denominators are nonzero. With appropriate field parameters, different multisets satisfy it only with small probability over the random choice of β. The circuit cost of this protocol is O(n). Lookup check. A lookup check proves that every value in a column A ∈ Fn appears in a reference table B ∈ Fℓ . A reference entry may match several occurrences in A. The

prover records the number of occurrences assigned to each B[j] as m[j] and uses these counts as weights in the sum comparison above. After A, B, and m have been fixed, the protocol samples a random value β as above and checks whether ℓ−1 X m[j] 1 = . β + A[i] β + B[j] j=0 i=0

n−1 X

The circuit cost of this protocol is O(n + ℓ). Range check. Finite-field arithmetic does not directly express integer ordering, so we verify integer comparisons by bounding differences between the compared values. For integers x and y, checking x ≤ y amounts to checking that the difference y − x is nonnegative. A range check establishes such bounds by proving that a value represents an integer in [0, 2w ), where w is the required bit width. A lookup against {0, . . . , 2w − 1} would establish this bound but require a table with 2w entries. The protocol instead splits the value into smaller bit groups, called limbs, and checks that combining them in their original bit positions reproduces the value. Each limb is then checked against a smaller lookup table. Using 8-bit limbs requires the table {0, . . . , 255}; using 16-bit limbs reduces the number of limbs but requires a table with 65,536 entries. Following ZKGraph’s implementation [7], VerfGraph uses 8-bit limbs, requiring ⌈w/8⌉ limb lookups per value. If w is not divisible by 8, the most significant limb is checked against a smaller table covering only the remaining bits. The circuit cost of this protocol is O(⌈w/8⌉(q + T )) for q checked values, where T = 256 is the lookup-table size.

D. ZKGraph’s Query Model and Graph Representation ZKGraph [7] addresses the cost of proving complex graph queries through operator decomposition. Its expansion-centric model centers on expansion, which follows graph edges from a vertex or a set of vertices to their neighbors. The model includes single-source expansion, set-based expansion, and single-source shortest path (SSSP), with specialized proof constructions for their input–output relations. These operators are composed by using one operator’s output relation as the next operator’s input relation, and the proof enforces consistency between these relations. VerfGraph adopts this model, introduces new proof methods for several existing operators, and extends the set of supported operations. The cost of proving these operators also depends on how graph edges are represented. An edge-list representation stores each edge as a row containing its two endpoints and optional attributes. An alternative, compressed sparse row (CSR), stores each vertex’s neighbors consecutively in an array and uses offsets to locate each neighbor list. ZKGraph shows that proof generation is faster with edge lists than with CSR [7]. VerfGraph therefore adopts the edge-list representation for proof construction.

III. S YSTEM OVERVIEW A. System Model VerfGraph consists of two parties: a prover P and a verifier V. The prover maintains a private graph database G, including its vertex and edge relations and their attributes. Given a graph query q, P evaluates q over G, returns the query result y, and generates a proof π of the computation. The verifier submits q and checks π using the public query description, the claimed result, and the corresponding verification parameters. If verification succeeds, V accepts y without accessing the private graph or re-executing the query. B. Security Model VerfGraph considers two potential adversaries. A malicious prover may substitute graph data or construct incorrect intermediate and final query results. A malicious verifier may attempt to learn private graph records or intermediate values beyond what is revealed by the public inputs and query result. To fix the graph data against which results are verified, the verifier records a public database commitment CG before receiving the result and proof. Under this threat model, we consider the following three properties: Completeness. An honest prover that correctly evaluates the declared query over the graph data committed by CG can generate a proof accepted by the verifier. • Soundness. The probability that a malicious prover convinces the verifier to accept a result inconsistent with the declared query over the graph data committed by CG is negligible. • Zero knowledge. The verifier learns no information about private graph records, intermediate relations, or auxiliary witness values beyond what is implied by the public inputs and query result. •

We next explain how the proof construction and operator constraints support these properties. Database and computation integrity: To bind query evaluation to the agreed graph data, the prover encodes the database columns as polynomials and commits to them using a polynomial commitment scheme (PCS), producing CG . The PCS allows the verifier to check that database values used in the proof are consistent with these committed columns. Starting from these values, AIR constraints establish each operator’s input–output relation and require one operator’s output to match the next operator’s input. The final output is bound to the public result y. An honest computation supplies a witness satisfying these constraints, while the proof establishes that the claimed answer follows from the declared query over the committed data. For polynomial commitments, two major approaches are group-based schemes, such as KZG and IPA, and hash-based schemes. Hash-based schemes require no trusted setup and rely on assumptions believed to resist known quantum attacks [10]. These properties motivate our choice of an FRI-based PCS [9], a representative hash-based construction.

Witness privacy: VerfGraph protects private witness values through its randomized proof construction. Graph operators also produce intermediate relations whose sizes depend on private data. To prevent these sizes from changing the public trace dimensions, VerfGraph follows ZKSQL [5] and pads relations with dummy rows to predetermined public capacities. Private Boolean activity tags distinguish actual rows from dummy rows and prevent dummy rows from affecting query results. With these padded relations, each operator applies the same constraint pattern across a fixed-capacity trace, yielding an oblivious AIR layout for fixed public inputs. Public information and scope: The query, query plan, result, database commitment, AIR descriptor, and trace dimensions and capacities are public. The graph schema, relation and attribute types, and edge directionality are also public information needed to interpret the query. Given this public information, our security model addresses database and computation integrity against a malicious prover and witness privacy against a malicious verifier. Other concerns, including queryresult inference, access control, denial of service, and side channels in native query execution and witness construction, are outside our scope. C. System Workflow VerfGraph processes a graph query in five stages, as summarized in Figure 2. Offline database commitment. The prover encodes the agreed graph-data columns as polynomials and commits to these polynomials using the PCS, producing CG . The verifier records CG for subsequent verification, fixing the graph data against which query results must be proved. Query submission. With CG recorded, the verifier submits a graph query q to be evaluated over the committed graph data. Query planning and preprocessing. VerfGraph decomposes q into graph operators and organizes them into a query plan. From this plan, it constructs a proof circuit in AIR form by combining the operators’ constraints and connecting their input and output relations. Preprocessing this circuit produces proving parameters ppP for proof generation and verification parameters ppV , which the verifier uses together with the public AIR description to check proofs. Query execution and proof generation. The prover executes the query plan over its private graph data to obtain the result y. From the database values and intermediate operator relations, it constructs a witness for the proof circuit. Using this witness and ppP , the prover generates a proof π that y is the result of evaluating q over the graph data committed by CG . The prover returns y and π to the verifier. Proof verification. The verifier checks the received proof π using the public query description, the recorded commitment CG , the claimed result y, and ppV . If verification succeeds, the verifier accepts y; otherwise, it rejects the response. D. An End-to-End Example Consider a private graph database with directed edge relation De = {(1, 2), (1, 3), (2, 4)}. Its source and target columns

PRIVATE INFORMATION

PUBLIC INFORMATION

Graph Database G

Database Commitment CG

1

PROVER P

Query Planning and Preprocessing

3

Proving Parameters ppP

4

Result y Proof π

Query Execution and Proof Generation

2

5

VERIFIER V

Query Submission q

Verification Parameters ppV

Proof Verification

0/1

Fig. 2. System workflow of VerfGraph.

are (1, 1, 2) and (2, 3, 4), respectively. The prover encodes these columns as separate polynomials and commits to them using the PCS, producing the database commitment CG . The verifier records CG , fixing the graph data against which subsequent query results must be proved. With CG recorded, the verifier submits a query q requesting all outgoing edges of vertex 1. The query plan consists of a single-source expansion operator with De and vertex 1 as inputs. For this operator, VerfGraph constructs a proof circuit to establish that the output contains exactly the edges originating from vertex 1 in the committed graph. Preprocessing this circuit produces the proving parameters ppP and verification parameters ppV . Executing the operator over De yields the result y = Dout = {(1, 2), (1, 3)}. Both returned edges originate from vertex 1, while (2, 4) originates from vertex 2 and is excluded. From the input edges and this result, the prover constructs the witness required by the circuit. Using this witness and ppP , it generates a proof π that y contains exactly vertex 1’s outgoing edges in the graph committed by CG . The prover returns y and π to the verifier. The verifier checks π using its recorded CG , the query q, the claimed result y, and ppV . Successful verification allows the verifier to accept the two returned edges as the complete answer without receiving the full edge relation or re-executing the query. IV. C IRCUIT D ESIGN Following the expansion-centric model described in Section II-D, this section presents VerfGraph’s circuit designs for core operators, including single-source expansion, set-based expansion, single-source shortest path (SSSP), and count. For each operator, we explain the proof intuition and construct its circuit using the protocols introduced in Section II-C, expressing permutation and lookup checks in logarithmic-derivative form. For operators improved over ZKGraph, we sum the costs of these protocols and the remaining constraints to compare circuit complexity between VerfGraph and ZKGraph. A. Single-Source Expansion Single-source expansion is a basic traversal operation in graph query processing. Given a source vertex, it returns the one-hop edges that can be traversed from that vertex, and therefore serves as a building block for graph queries. The

input consists of a source identifier ids and an edge-list table De . The output table Dout = (C, D) contains exactly the rows (ids , idt ) for which idt is reachable from ids in one hop through an edge recorded in De . Which input edges belong in the output depends on whether De represents a directed or bidirectional relation. We therefore consider the two cases separately. Circuit design for the directed edge relation: For a directed edge relation, let De = (A, B), where A stores source identifiers and B stores target identifiers. We follow the same proof-construction strategy as ZKGraph: selection followed by multiset matching. Selection identifies exactly the input edges whose source is ids , while multiset matching requires the output to contain all and only these edges with the same multiplicities. To prove the selection, the prover introduces a flag column isid over De , where isid [i] = 1 iff A[i] = ids , and isid [i] = 0 otherwise. The flag is proved using an inverse-witness column invid , defined as ( 0, A[i] = ids , invid [i] = (ids − A[i])−1 , A[i] ̸= ids . For every i ∈ {0, . . . , |A| − 1}, the circuit constrains isid [i] to be Boolean and enforces isid [i](ids − A[i]) = 0,

isid [i] + invid [i](ids − A[i]) = 1.

When A[i] = ids , the second constraint forces isid [i] = 1; when A[i] ̸= ids , the first constraint forces isid [i] = 0, and the second verifies the inverse witness. The remaining task is to prove that the selected edge rows are exactly the output rows. To apply the permutation check to edge rows, we compress each pair of endpoints into a single field element using a random challenge α, and use another random challenge β in the check below: Cinput [i] = A[i] + αB[i],

Coutput [i] = C[i] + αD[i].

The prover then uses a permutation check to prove that the rows of De satisfying isid [i] = 1 and the rows of Dout are permutations of one another, namely, |C|−1 X 1 isid [i] = . β + C [i] β + C [i] input output i=0 i=0

|A|−1

X

Thus every output edge must come from an edge whose source is ids , and every such input edge must appear in the output with the same multiplicity. ZKGraph baseline for the bidirectional edge relation: For a bidirectional edge relation, let De = (A, B), where each row stores two endpoints and denotes a symmetric adjacency that can be traversed in either direction. Applying the directed protocol only to the first column would prove only the edges where A[i] = ids and would miss valid traversals where B[i] = ids , thereby failing to establish completeness. ZKGraph handles this case using Bidirectional Relationship Canonicalization (BiRC). It canonicalizes each row of De and Dout by placing the smaller endpoint first, and checks that

each canonicalized row contains the same two endpoints as the original row. With both tables in canonical form, it marks the rows of De that contain ids and uses a permutation check to match the selected rows with the canonicalized Dout . To prove that the smaller endpoint appears first, it uses two range checks, one for each table. These range checks require multiple limb lookups per row, adding to the circuit cost. Our circuit design: To avoid these canonicalization checks, we treat De as two directed views, (A, B) and (B, A). From the first view, we select rows (A[i], B[i]) with A[i] = ids ; from the second, we select rows (B[i], A[i]) with B[i] = ids . In both cases, ids appears first. The selected rows from both views therefore represent all traversals from ids , and a single permutation check proves that Dout contains exactly these rows with the same multiplicities. Both views reuse the original edge columns, without materializing or separately committing to a concatenated table. To identify the selected rows in each view, the prover provides two equality flags: ( 1, A[i] = ids , lef tequal [i] = 0, A[i] ̸= ids , and

( rightequal [i] =

1, 0,

B[i] = ids , B[i] ̸= ids .

The prover proves both flag columns using the same inversewitness equality constraints as in the directed design. These flags identify the edges traversed in the forward and reverse directions, respectively. To match both directions against the output, we compress the rows as Cinput [i] = A[i] + αB[i], ′ Cinput [i] = B[i] + αA[i],

Coutput [i] = C[i] + αD[i], The circuit then checks the following equality: ! |C|−1 |A|−1 X X rightequal [i] 1 lef tequal [i] + = . ′ β + C [i] β + C [i] β + C input output [i] input i=0 i=0 Correctness: For both constructions, correctness follows from two facts. First, the flag constraints identify exactly the edge rows that can be traversed from ids . In the directed case this means rows with A[i] = ids ; in the bidirectional case it means rows with either endpoint equal to ids . Second, the permutation check proves that the selected traversals and the rows of Dout are permutations of one another. Together, these constraints prove the correctness of the one-hop traversals from the source. Circuit complexity: Since the directed construction follows ZKGraph’s strategy, we focus our comparison on bidirectional expansion. Let N and M denote the input and output edge counts. For fixed identifier and limb widths, let T be the range-table size and n the number of limb lookups per range-checked value. Each limb lookup accounts for both

the checked column and its reference table. ZKGraph’s bidirectional single-source expansion requires two range checks costing O(n(N + T )) and O(n(M + T )), respectively, and one permutation check costing O(N + M ). Together with O(N + M ) selection and canonicalization constraints, its total circuit complexity is
O N + M + n(N + M + 2T ) . VerfGraph instead uses two equality tests per input row, costing O(N ), and one permutation check over both input orientations and the output, costing O(2N + M ). Its total circuit complexity is therefore O(2N + M ). By replacing canonicalization with equality tests, VerfGraph eliminates both limb-based range checks and their associated lookup-table processing, reducing the circuit cost of this operator. B. Set-Based Expansion The set-based expansion operator generalizes single-source expansion from one source vertex to a set of source vertices. Its input consists of a source set IDs and an edge-list table De . The output table Dout = (C, D) contains exactly the onehop traversals that start from a vertex in IDs , where C and D store the starting and adjacent vertex identifiers, respectively. We consider set-based expansion over a directed edge relation in this subsection. Unless explicitly stated otherwise, “set-based expansion” hereafter refers to this directed case. Let De = (A, B), where A stores source identifiers and B stores target identifiers. ZKGraph baseline: To identify the edges belonging to the output, ZKGraph [7] proves whether each edge source belongs to IDs . It establishes membership by locating the source between two consecutive values in the sorted source set: the source belongs to the set exactly when it equals the lower value. To construct these intervals, ZKGraph augments IDs with minimum and maximum boundary values outside the identifier f s . It also sorts domain and sorts the resulting column as ID e e = (A, e B). e The first two De by source identifier to obtain D f s to the augmented source set permutation checks bind ID e e to De , respectively. Two range checks then enforce and D f s [i] < ID f s [i + 1] and A[i] e ≤ A[i e + 1] on adjacent rows, ID thereby certifying the two sort orders. e For every sorted edge source A[i], the prover supplies a f s not lower bracket L[i], equal to the greatest value in ID e exceeding A[i], and its successor U [i]. A lookup check against f s proves that the consecutive-pair columns derived from ID (L[i], U [i]) are adjacent source-set values. The remaining two e and A[i] e < U [i]. Hence A[i] e range checks enforce L[i] ≤ A[i] e belongs to IDs exactly when A[i] = L[i]. A Boolean selector records this equality, and the third permutation check proves e e form exactly Dout . that the selected rows of D Our circuit design: Our target is to prove that Dout contains all and only the input edges whose source identifiers belong to IDs , with the same multiplicities. We decompose this target into three conditions: the output and non-output edges together form the input; every output source belongs to

IDs ; and no non-output source belongs to IDs . To certify the last condition, we prove that the distinct source identifiers of the non-output edges are disjoint from IDs . The prover first constructs the following witnesses: n n n • De = (A , B ), the non-output edge table consisting of the rows of De whose source identifiers do not belong to IDs , where An and B n store the source and target identifiers of these rows, respectively; n,d • A , a duplicate-free column containing one representative of each distinct source identifier appearing in An ; this column is used to prove collectively that the sources of all non-output edges lie outside IDs ; • IDunion , a sorted column obtained from the concatenation of An,d and IDs ; its strict ordering is used to certify that no identifier appears in both columns. The prover then proves the following constraints. First, a permutation check proves that concatenating Dout and Den yields a permutation of the input edge table De . Let α and β be random challenges and define the row compressions Cout [i] = C[i] + αD[i], Cn [i] = An [i] + αB n [i], Ce [i] = A[i] + αB[i]. The prover proves n

|A |−1 |A|−1 X X 1 1 1 + = . β + C [i] β + C [i] β + Ce [i] out n i=0 i=0 i=0

|C|−1

X

This constraint ensures that every row occurrence in De is accounted for exactly once by either Dout or Den , and that neither table contains a fabricated edge row. Second, a lookup check proves that every source identifier in An appears in An,d . This ensures that An,d covers all source identifiers represented in the non-output edge table. Third, a permutation check proves that concatenating An,d and IDs yields a permutation of IDunion . A range check further proves IDunion [i] < IDunion [i + 1] for every adjacent pair. Any identifier shared by An,d and IDs would appear twice in IDunion , violating its strict ordering. These two checks therefore establish that the two columns share no identifier. Fourth, a lookup check proves that every source identifier in the output column C belongs to IDs , thereby certifying that every reported edge satisfies the set-based expansion condition. Correctness: The correctness follows from the following facts. The first-step permutation check establishes that, as multisets, Dout and Den together contain exactly the rows of De ; hence, every input-edge occurrence is assigned to one of these two tables, with no row inserted or omitted. The second-step lookup check proves that An,d covers every source identifier in An . The third-step permutation and range checks establish that An,d and IDs share no identifier. Together, the second and third steps therefore prove that no edge in Den starts from a vertex in IDs . Finally, the fourth-step lookup check proves that every source identifier in C belongs to IDs , so every edge in Dout satisfies the expansion condition. These

constraints jointly prove that Dout contains all and only the one-hop traversals that start from vertices in IDs . Circuit complexity: Let N and M denote the input and output edge counts, S = |IDs |, and K = |An,d |. Let n be the number of limbs per range-checked value and T the lookuptable size. For ZKGraph, the permutation checks for the source-set ordering, edge ordering, and output matching have circuit costs of O(S), O(N ), and O(N + M ), respectively. The consecutive-pair lookup costs O(N + S). The range check for source-set ordering costs O(n(S + T )), while edge ordering and the two bracket comparisons each cost O(n(N + T )). Together with O(N + S) auxiliary constraints, the total circuit cost is O(N + M + S + n(3N + S + 4T )). For our construction, the partition and union permutation checks cost O(N ) and O(K + S), respectively. The lookups from An to An,d and from C to IDs cost O(N − M + K) and O(M +S), respectively. The strict-order range check over IDunion costs O(n(K + S + T )). Including the remaining linear-cost constraints, the total circuit cost is O(N + K + S + n(K + S + T )). Since the prover constructs An,d with one entry per distinct source identifier among the N − M non-output edges, K ≤ N − M . Our construction replaces the range checks for source-set ordering, edge ordering, and per-edge bracket comparisons with a single strict-order check over the K + S union entries, avoiding repeated comparisons for non-output edges with the same source. Bidirectional relations: The set-based expansion operators evaluated in our comparison use directed relations. A bidirectional extension can apply our construction to the two views (A, B) and (B, A), combine their outputs as a multiset, and count self-loops once. We leave the implementation and evaluation of this extension to future work. C. Single-Source Shortest Path This subsection presents our proof for single-source shortest path (SSSP). Unless otherwise specified, SSSP refers to the unweighted setting, where every edge has unit cost. We first describe ZKGraph’s construction and our improvements for bidirectional edge relations, and then extend the construction to weighted SSSP. The input consists of a source identifier ids , an edge table De = (A, B), and a node column Cnid . The output is a distance column Cdist aligned with Cnid . For each node reachable from ids , the corresponding entry records its shortest-path distance; otherwise, the entry is set to a predefined sentinel dmax , chosen larger than every admissible finite distance. ZKGraph baseline: We first describe ZKGraph’s construction for a directed edge relation [7]. ZKGraph’s proof combines two conditions: each finite claimed distance must be realized by a path from the source, and no shorter path may exist. It uses predecessor witnesses to establish the first condition and edge-relaxation checks to establish the second. At the node level, the prover supplies a source-flag column Is , a predecessor column Cpre , and a predecessor-distance column Cpd , all aligned with Cnid . At the edge level, the

prover supplies two columns Cud and Cvd , aligned with De , which record the claimed distances of the endpoints in A and B, respectively. Using the equality constraints from Section IV-A, the circuit establishes Is [i] = 1 iff Cnid [i] = ids , and sets the source distance to zero. For each non-source row i with a finite claimed distance, a lookup check proves that (Cpre [i], Cpd [i]) appears in the global node-distance table (Cnid , Cdist ). A second lookup check proves that the predecessor edge (Cpre [i], Cnid [i]) appears in (A, B). The distancepropagation constraint then enforces Cdist [i] = Cpd [i] + 1. These checks bind each claimed distance to its predecessor through an input edge. The edge-level constraints additionally establish shortestpath optimality. For each edge row j, the prover binds both endpoint distances to (Cnid , Cdist ) through two lookup checks, one for (A[j], Cud [j]) and the other for (B[j], Cvd [j]). A range check then enforces the relaxation condition Cvd [j] ≤ Cud [j] + 1. For a bidirectional edge relation, the same proof strategy must account for traversal in both directions. Each edge is stored once, so its stored orientation may be opposite to the predecessor traversal. ZKGraph handles the predecessoredge lookup using BiRC, introduced in Section IV-A. It canonicalizes both edge rows and predecessor–node pairs, proves the correctness of their canonical representations, and performs the lookup over the canonical edge table. The two canonicalization range checks increase the circuit cost. Our circuit design: For directed edge relations, we retain the preceding construction. For bidirectional relations, we replace canonicalization with a lookup over both traversal directions and enforce relaxation in both directions. Following the two-view representation in Section IV-A, we use (A, B) and (B, A) to represent the two traversal directions. Unlike expansion, which matches all selected traversals against the output, SSSP only requires membership of the predecessor edges. We therefore use a lookup check to prove that each predecessor edge appears in either view. Both views reuse the original edge columns without materializing a concatenated table. Let R ⊆ {0, . . . , |Cnid | − 1} denote the indices of nonsource node rows with finite claimed distances. With random challenges α and β, define the row compressions for i ∈ R and 0 ≤ j < |A| as Cquery [i] = Cpre [i] + αCnid [i], Cinput [j] = A[j] + αB[j], ′ Cinput [j] = B[j] + αA[j].

The prover supplies multiplicity columns m1 and m2 and proves ! |A|−1 X X m1 [j] m2 [j] 1 = + . ′ β + Cquery [i] β + Cinput [j] β + Cinput [j] j=0 i∈R

This check proves that every predecessor edge exists in at least one traversal direction without canonicalizing either table. The lookup establishes predecessor-edge membership in either direction. To also establish shortest-path optimality, we enforce relaxation in both directions: Cvd [j] ≤ Cud [j] + 1,

Cud [j] ≤ Cvd [j] + 1.

These conditions are equivalent to the squared-difference bound (Cud [j] − Cvd [j])2 ≤ 1. The circuit enforces this bound with a range check establishing that 1 − (Cud [j] − Cvd [j])2 is nonnegative, using bounded integer representations with parameters chosen to prevent finite-field wraparound. Correctness: Correctness follows from two facts. First, following finite-distance predecessors decreases the claimed distance by one at each step until reaching the source. The predecessor-edge lookups therefore establish a source path b realizing each finite claimed distance d(v). Hence, the true b shortest-path distance satisfies δ(v) ≤ d(v). Second, the endpoint-distance lookups and relaxation constraints enforce b ≤ d(u) b + 1 in every valid traversal direction. Applying d(v) b these inequalities along a shortest path gives d(v) ≤ δ(v). b = δ(v) for every reachable node. A finite predeThus, d(v) cessor path certifies reachability, while assigning dmax to a reachable node contradicts relaxation along its source path. Therefore, dmax labels exactly the unreachable nodes. Circuit complexity: We analyze the circuit cost of our construction for bidirectional SSSP. Let N = |A| be the number of edge rows, V = |Cnid | the number of node rows, and r = |R| ≤ V the number of non-source nodes with finite claimed distances. Let n be the number of limbs per rangechecked value and T the lookup-table size, with the limb count chosen to accommodate the squared-difference bounds. The predecessor-distance lookup costs O(r + V ), and the two endpoint-distance lookups each cost O(N + V ). The predecessor-edge lookup uses r query rows and 2N reference rows across the two traversal views, costing O(r + 2N ). The node-level constraints contribute O(V ), and computing the squared endpoint-distance differences contributes O(N ). The circuit enforces (Cud [j] − Cvd [j])2 ≤ 1 with one range check per edge, costing O(n(N + T )) across all edge rows. Combining these costs and using r ≤ V , the total circuit cost is
O N + V + n(N + T ) . For fixed limb width, limb count, and lookup-table size, this cost is linear in the numbers of edges and nodes. Weighted SSSP: Weighted SSSP retains the preceding proof structure and changes only the predecessor-edge representation and the distance constraints. The input additionally includes a column W of positive integer edge weights aligned with De . First, the prover supplies a node-aligned column Wpn recording predecessor-edge weights. For each non-source row

with a finite claimed distance, the predecessor-edge lookup now checks (Cpre [i], Cnid [i], Wpn [i]) ∈ (A, B, W ), and the propagation constraint becomes Cdist [i] = Cpd [i] + Wpn [i]. For bidirectional relations, the lookup uses both (A, B, W ) and (B, A, W ), following the same two-view construction. Second, the endpoint-distance lookups remain unchanged, while directed relaxation becomes Cvd [j] ≤ Cud [j] + W [j]. For bidirectional relations, the endpoint-distance difference is now bounded by W [j] instead of 1. We therefore generalize the unweighted squared-difference bound with a range check enforcing W [j]2 − (Cud [j] − Cvd [j])2 ≥ 0. Since edge weights are positive, the same predecessor-path and relaxation argument establishes correctness. D. Count The count operator groups identical input values and returns the number of occurrences in each group. It is a common aggregation primitive in graph queries, where it can be used to compute, for example, vertex degrees, tag frequencies, and per-type edge counts. This subsection presents our proof construction for this operator. ZKGraph does not provide a corresponding proof construction [7]. We address this limitation with a dedicated count proof, thereby broadening the class of graph queries that can be expressed and verified. The input to the count operator is a vector A. Its output is Dout = (B, C), where B contains distinct keys and C[i] records the number of occurrences of B[i] in A. Rows with C[i] = 0 do not contribute to the logical count result. Circuit design: The prover first proves the equality between the input multiset represented by A and the weighted output multiset represented by (B, C), where C[i] specifies the multiplicity of B[i]. Let β denote the random challenge. The proof reduces this weighted multiset equality to the identity |A|−1

|B|−1 X 1 C[i] = . β + A[i] β + B[i] i=0 i=0

X

Then, the prover proves B[i + 1] > B[i] for each adjacent pair using a range check, which ensures that B contains no duplicate elements (consequently, the output keys in B must appear in ascending order; this restriction is immaterial to the semantics of count). Correctness: The range check above ensures that the prover cannot split the occurrences of a value in A across multiple output rows. Together with the weighted multiset check, it further ensures that any key included in B but absent from A must have multiplicity zero and therefore does not affect the logical count result. Thus, (B, C) correctly encodes the group cardinalities of A.

E. Summary The operators presented above provide the building blocks for verifying graph queries under the expansion-centric model. Other operations include filtering, order-by and limit-k (topk), reachability, and all-shortest-path enumeration. For these operations, VerfGraph retains ZKGraph’s operator-level proof strategies. Together, the operators described in this section are composed according to the query plan, with intermediate results passed from one operator to another. To verify this data flow, VerfGraph uses AIR constraints to check both each operator’s input–output relationship and the consistency of intermediate results between operators. Specifically, when an operator consumes a relation produced by another operator, the constraints ensure that the input used by the consuming operator matches the output of the producing operator. This connects the individual operator checks according to the dependencies in the query plan. The proof also checks that the query reads the agreed graph data. Starting from these data, each operator produces the result required by its semantics, which is then passed consistently to the operators that consume it. Following these dependencies establishes that the returned answer is the result of evaluating the query over the agreed graph data. VerfGraph generates a zero-knowledge proof of this evaluation, allowing the verifier to check the answer without accessing private graph records or intermediate results. V. E XPERIMENTS In this section, we evaluate VerfGraph from three perspectives: system-level performance and query coverage across LDBC SNB queries and database scales, operator-level proving costs, and a controlled circuit-level comparison with ZKGraph under the same Halo2/KZG backend. A. Experimental Setup We implemented VerfGraph in Rust on top of Plonky3, using its AIR arithmetization framework and FRI-based PCS. This hash-based PCS allows the use of small prime fields for efficient arithmetic, so we choose Goldilocks64, a widely used 64-bit prime field that supports efficient machine arithmetic and FFT-based polynomial operations for proof generation. We set the FRI parameters for an approximately 100-bit classicalsecurity target, comparable to the estimated classical-security level of the BN254 curve used in ZKGraph’s Halo2/KZG backend [14]. We evaluate VerfGraph on a subset of the LDBC Social Network Benchmark (SNB) Interactive workload [11]: IS3, IS4, IS5, IC1, IC2, IC9, and IC13. These seven queries cover all queries evaluated in ZKGraph’s experiments and enable a direct comparison between the two systems. We additionally evaluate IC6 and IC14 V2 to demonstrate the query support enabled by our new proof constructions for count and weighted SSSP, respectively. For these queries, we measure database scale by the number of rows in the relevant fact table, following ZKGraph. We use person_knows_person for IS3, IC1, and IC13;

TABLE I DATABASE COMMITMENT TIME BY QUERY AND DATABASE SCALE ( S ).

Scale IS3 IS4 IS5 IC1 IC2 IC6 IC9 IC13 IC14 V2 60k 0.053 0.057 0.064 0.163 0.096 0.065 0.097 0.045 0.143 120k 0.105 0.109 0.110 0.306 0.196 0.136 0.195 0.088 0.284 240k 0.208 0.219 0.220 0.596 0.396 0.279 0.396 0.173 0.562 TABLE II C IRCUIT PREPROCESSING TIME BY QUERY AND DATABASE SCALE ( S ).

Scale IS3 IS4 IS5 IC1 IC2 IC6 IC9 IC13 IC14 V2 60k 0.043 0.041 0.042 0.271 0.043 0.042 0.043 0.089 0.301 120k 0.083 0.081 0.080 0.520 0.084 0.082 0.085 0.170 0.593 240k 0.163 0.156 0.156 1.041 0.164 0.163 0.164 0.330 1.209

comment_hasCreator_person for IS4, IS5, IC2, and IC9; and post_hasTag_tag for IC6. For IC14 V2, we use the combined number of rows in comment_replyOf_ comment and comment_replyOf_post. Unless otherwise stated, we evaluate the queries at database scales of 60k, 120k, and 240k rows to assess performance as database size increases. These scales match those used in ZKGraph’s evaluation, and both systems use the same datasets for the seven shared queries. All experiments were conducted on a server with 24 vCPUs (Intel Ice Lake, 3.0 GHz) and 192 GiB of RAM, running 64bit Ubuntu 24.04. All experimental results are averaged over multiple runs.

We compare proof generation time, peak prover memory usage, proof size, and verification time. The experimental results are shown in Table III. Proof generation time. Compared with ZKGraph, VerfGraph substantially reduces proof generation time. The improvement is more pronounced for the IC queries, with speedups of 33.9×–59.7×. Peak prover memory usage. VerfGraph also substantially reduces peak prover memory usage relative to ZKGraph. For the IC queries, the reduction factor ranges from 4.5× to 6.6×. Proof size. The proof size of VerfGraph is larger than that of ZKGraph, but remains sub-MB for every evaluated query and scale. This larger proof size reflects our use of an FRI-based PCS and is an acceptable tradeoff for faster proof generation and lower peak prover memory usage. Verification time. Although verification takes longer than in ZKGraph, VerfGraph maintains millisecond-level verification across all evaluated queries and scales. The evaluated database scales also characterize scalability. As database scale increases, proof generation time generally increases, while proof size and verification time grow slowly. Additional Query Coverage: Beyond the seven queries shared with ZKGraph, we evaluate IC6 and IC14 V2 at the 60k, 120k, and 240k database scales. These queries use our new proof constructions for count and weighted SSSP, respectively. The experimental results are shown in Table IV. These results demonstrate VerfGraph’s support for both queries while retaining sub-MB proofs and millisecond-level verification at the evaluated scales. C. Operator Proof Performance

B. System-Level Performance This subsection evaluates VerfGraph’s offline databasecommitment and circuit-preprocessing costs, its system-level performance compared with ZKGraph, and its performance on additional graph queries enabled by count and weighted SSSP. Database Commitment and Circuit Preprocessing: We measure database commitment time and circuit preprocessing time. For each evaluated query template, the database commitment covers the input tables and columns used by that query. The experimental results are shown in Tables I and II. Benchmarking with ZKGraph: ZKGraph is the stateof-the-art zero-knowledge verifiable graph query evaluation system [7]. We compare VerfGraph and ZKGraph on IS3, IS4, IS5, IC1, IC2, IC9, and IC13, which are supported by both systems, at the 60k, 120k, and 240k fact-table scales. Both systems use the same datasets. For all three scales, we apply the same value-encoding rules as ZKGraph to nonnumeric values such as strings and dates. For each query, we use the same operator decomposition as ZKGraph, replacing its operator proofs with the circuits in Section IV. Following ZKGraph, we prove friends-of-friends queries with bidirectional SSSP rather than a sequence of expansion proofs; hence this comparison does not separately exercise bidirectional set-based expansion.

To evaluate the proving costs of the operator-proof constructions introduced in Section IV, we measure single-source expansion and the two set-based expansions in IC2; unweighted SSSP and count in IC6; and weighted SSSP in IC14 V2. These operators are drawn from the IC queries evaluated in Section V-B. We construct standalone circuits for these operators and measure their proof-generation times using inputs from the corresponding queries at the 60k database scale. The two setbased expansions in IC2 are proved jointly in one circuit. The experimental results are shown in Table V. D. Same-Backend Performance Comparison To isolate the contribution of our proposed operator-proof constructions from the choice of proving backend, we implement them within ZKGraph’s Halo2/KZG framework. We retain the same backend and implementations of permutation, lookup, and range checks, replacing ZKGraph’s corresponding operator-proof constructions with ours. We refer to this implementation as VG-Halo2. System-level comparison: We first evaluate complete query circuits for IS3, IS4, IS5, IC1, IC2, IC9, and IC13 in both systems. These seven queries cover all queries evaluated in ZKGraph’s experimental section. Both implementations use

TABLE III S YSTEM - LEVEL COMPARISON BETWEEN V ERF G RAPH AND ZKG RAPH .

Query Scale

Proof Generation Time (s)

Proof Size (KiB)

Verification Time (ms)

Peak Memory Usage (GiB)

VerfGraph ZKGraph VerfGraph ZKGraph VerfGraph ZKGraph VerfGraph ZKGraph IC1

60k 120k 240k

1.742 3.409 6.681

77.880 156.440 330.215

679.079 718.237 758.958

57.938 57.938 57.938

24.904 27.240 28.558

21.351 21.435 21.581

1.678 3.152 6.095

7.947 15.901 31.380

IC2

60k 120k 240k

1.050 2.071 4.114

56.143 113.194 240.029

558.924 598.082 638.803

40.250 40.250 40.250

18.986 20.296 21.616

16.229 16.372 16.207

0.941 1.789 3.512

5.752 11.511 23.176

IC9

60k 120k 240k

1.099 2.164 4.294

60.893 122.647 256.487

566.096 605.254 645.975

43.688 43.688 43.688

19.307 20.558 21.907

17.170 17.326 17.246

1.001 1.886 3.662

6.069 12.135 24.051

IC13

60k 120k 240k

0.402 0.768 1.525

13.622 27.195 56.903

460.734 499.893 540.613

9.000 9.000 9.000

14.872 16.137 17.367

6.745 6.842 6.667

0.327 0.630 1.239

1.481 2.958 5.860

IS3

60k 120k 240k

0.630 1.254 2.628

13.975 28.652 60.454

499.278 539.702 585.907

10.219 10.219 10.219

16.358 17.671 19.273

7.178 7.070 7.266

0.536 1.046 2.182

1.612 3.275 6.561

IS4

60k 120k 240k

0.336 0.648 1.269

3.899 7.871 16.341

451.822 490.980 531.701

2.562 2.562 2.562

14.548 15.773 17.017

4.569 4.559 4.727

0.295 0.578 1.146

0.793 1.600 3.382

IS5

60k 120k 240k

0.379 0.670 1.331

4.015 8.111 16.721

453.088 492.246 532.967

2.781 2.781 2.781

14.554 15.866 17.102

4.466 4.387 4.500

0.292 0.573 1.132

0.812 1.635 3.348

TABLE IV P ERFORMANCE OF ADDITIONAL LDBC SNB QUERIES IN V ERF G RAPH .

Proof Generation Proof Size Verification Peak Memory Query Scale Time (s) (KiB) Time (ms) Usage (GiB) 60k 120k 240k

2.502 4.900 9.877

566.394 605.552 646.272

18.908 20.184 21.502

1.852 3.755 7.441

60k IC14 V2 120k 240k

1.986 3.928 7.960

590.856 631.577 673.860

19.769 20.945 22.301

1.799 3.496 6.903

IC6

the same datasets, query parameters, and execution environment. We evaluate each query at the 60k, 120k, and 240k database scales and report five metrics: key-generation time, proof-generation time, proof size, verification time, and peak prover memory usage. Tables III and VI present the results for ZKGraph and VGHalo2, respectively. Compared with ZKGraph, VG-Halo2 achieves substantial performance improvements, especially for complex IC queries. For these queries, VG-Halo2 reduces proof generation time by 44.3%–62.5%, proof size by 42.6%–62.2%, and peak prover memory usage by 26.7%–48.8%, while maintaining millisecond-level verification. These results demonstrate that VerfGraph achieves better overall performance than ZKGraph

TABLE V S TANDALONE OPERATOR - PROOF GENERATION TIME AT THE 60 K DATABASE SCALE . T HE TWO IC2 SET- BASED EXPANSIONS ARE PROVED JOINTLY.

Operator

Source query

Proof generation time (s)

Single-source expansion Set-based expansion ×2 Unweighted SSSP Count Weighted SSSP

IC2 IC2 IC6 IC6 IC14 V2

0.315 0.484 0.666 0.336 0.435

under the same proving backend. The key-generation times of VG-Halo2 and ZKGraph are shown in Table VII. The results indicate that both systems incur comparable key-generation costs. Operator-level comparison: To explain the query-level performance gains, we further conduct operator-level comparisons using IC2 and IC9 at the 60k database scale. Together, these queries cover all operator-proof constructions for which we propose improvements over ZKGraph: single-source expansion over bidirectional edge relations, unweighted SSSP over bidirectional edge relations, and set-based expansion. We decompose the IC2 and IC9 query circuits of ZKGraph and VG-Halo2 into operator circuits using the same procedure and compare the proof-generation time of each corresponding

TABLE VI P ERFORMANCE OF VG-H ALO 2.

ZKGraph

Proof Generation Proof Size Verification Peak Memory Query Scale Time (s) (KiB) Time (ms) Usage (GiB) IC1

60k 120k 240k

43.374 87.175 181.695

32.406 32.406 32.406

14.330 14.388 32.889

5.822 11.656 22.990

IC2

60k 120k 240k

30.368 61.477 129.966

23.094 23.094 23.094

10.779 10.823 10.738

3.882 7.761 15.261

IC9

60k 120k 240k

32.677 65.952 138.687

24.500 24.500 24.500

11.802 11.714 12.970

4.028 8.213 15.889

60k IC13 120k 240k

5.191 10.403 21.339

3.406 3.406 3.406

4.918 4.870 4.964

0.790 1.514 3.038

IS3

60k 120k 240k

8.332 16.868 35.020

6.000 6.000 6.000

5.912 5.893 6.091

1.027 2.087 4.187

IS4

60k 120k 240k

2.205 4.354 8.669

1.844 1.844 1.844

4.020 3.969 3.942

0.376 0.781 1.574

IS5

60k 120k 240k

3.234 6.480 13.349

2.062 2.062 2.062

4.243 4.181 4.365

0.626 1.229 2.573

IC2

IC9

IC13

IS3

IS4

IC2 Single-source expansion 2 Set-based expansion Filter Top-20

0

5

10

15

20

25

Proof Generation Time (s)

IC9 SSSP 2 Set-based expansion Filter Top-20

0

5

10

15

20

25

30

Proof Generation Time (s)

Fig. 3. Operator-level proof generation time of ZKGraph and VG-Halo2 for IC2 and IC9 at the 60k database scale.

TABLE VII C IRCUIT- SPECIFIC KEY- GENERATION TIME OF VG-H ALO 2 AND ZKG RAPH UNDER THE SAME H ALO 2/KZG BACKEND ( S ).

IC1

VG-Halo2

Scale

System

IS5

60k

VG-Halo2 6.435 4.319 4.176 0.994 1.039 1.032 1.371 ZKGraph 6.225 5.322 5.556 1.424 2.141 1.604 1.822

120k

VG-Halo2 12.542 8.369 8.373 1.901 2.123 2.065 2.748 ZKGraph 11.724 10.603 11.176 2.716 4.276 3.176 3.660

240k

VG-Halo2 25.625 17.759 17.943 3.795 4.357 4.179 5.690 ZKGraph 23.798 22.330 23.273 5.622 9.111 6.651 7.707

operator. Figure 3 presents the results. The results show that our proposed constructions reduce proof-generation time for expansion and SSSP. These improvements contribute to the query-level gains under the same backend. VI. R ELATED W ORK Verifiable query processing allows a client to check the correctness and completeness of a result returned by an untrusted database service without re-executing the query. Existing approaches can be broadly grouped into authenticated data structures, trusted hardware, and cryptographic proof systems. ADS-based methods: Authenticated data structures (ADSs) bind a database or index to a compact public di-

gest. The server returns a verification object containing the authenticated index fragments needed to check a query answer. Dynamic authenticated indexes support updates and freshness in outsourced databases [15], while vChain develops authenticated indexes for Boolean range queries over blockchain data [16]. For graph data, authenticated hints support shortestpath verification [17], and Merkle-based feature indexes authenticate subgraph queries [18]. ADS-based methods can be efficient for queries supported by a particular authenticated index, but their verification objects are tied to its access paths and generally provide integrity rather than data privacy. TAP augments a tree-based ADS with independent audits and zero-knowledge range proofs to support privacy-preserving verification of statistical data services [19]. Hardware-based methods: Trusted hardware executes selected database functionality within an attested environment. CorrectDB uses a tamper-resistant coprocessor to authenticate SQL queries [20], and VeriDB builds verifiable relational storage and general SQL execution around SGX [21]. These systems offer low verification overhead and support expressive queries, but rely on the hardware and attestation stack; concealing data-dependent access may require additional oblivious mechanisms. Cryptographic proof methods: IntegriDB and vSQL use cryptographic verifiable computation to support broad classes of SQL queries over outsourced databases [22], [23]; their primary objective is result integrity rather than zero-knowledge privacy. ZQL compiles simple computations on private data into zero-knowledge protocols that provide result integrity while protecting the remaining data [24]. ZKSQL decomposes ad-hoc SQL queries into operator-level interactive zeroknowledge protocols [5], whereas PoneglyphDB uses optimized PLONKish circuits and recursive composition to pro-

duce non-interactive proofs for relational queries [6]. V3DB specializes database-aware proof design for vector search by proving a fixed-shape IVF-PQ pipeline over a committed snapshot [25]. For graph processing, ALITHEIA develops tailored verification for shortest path, longest path, and maximum flow [26]. For decentralized graph data, VeriDKG uses a blockchainmaintained ADS and a cryptographic accumulator to verify SPARQL queries over knowledge graphs, whereas VGQ integrates an external graph database to execute and verify queries over blockchain transaction graphs [27], [28]. These systems focus on query integrity in decentralized-data settings rather than zero-knowledge evaluation over private graph data. ZKGraph introduced an expansion-centric decomposition and corresponding PLONKish circuits for zero-knowledge graph query evaluation [7]. VerfGraph retains this model, redesigns comparison-heavy expansion and shortest-path proofs, and develops proof constructions for count and weighted shortestpath operators. VII. C ONCLUSION We present VerfGraph, a zero-knowledge system for verifiable graph query evaluation over committed graph data. Building on the expansion-centric model, VerfGraph redesigns the proof constructions for expansion and shortest-path operations and develops proof constructions for count and weighted shortest-path operators. The experimental results show that VerfGraph substantially reduces proof generation time and peak prover memory usage compared with ZKGraph while maintaining millisecond-level verification and producing subMB proofs on the evaluated LDBC SNB queries. R EFERENCES [1] R. Angles and C. Gutierrez, “Survey of graph database models,” ACM Computing Surveys, vol. 40, no. 1, 2008. [2] R. Angles, M. Arenas, P. Barceló, A. Hogan, J. Reutter, and D. Vrgoč, “Foundations of modern query languages for graph databases,” ACM Computing Surveys, vol. 50, no. 5, 2017. [3] O. Erling, A. Averbuch, J. Larriba-Pey, H. Chafi, A. Gubichev, A. Prat, M.-D. Pham, and P. Boncz, “The LDBC social network benchmark: Interactive workload,” in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2015, pp. 619–630. [4] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM Journal on Computing, vol. 18, no. 1, pp. 186–208, 1989. [5] X. Li, C. Weng, Y. Xu, X. Wang, and J. Rogers, “ZKSQL: Verifiable and efficient query evaluation with zero-knowledge proofs,” Proceedings of the VLDB Endowment, vol. 16, no. 8, pp. 1804–1816, 2023. [6] B. Gu, J. Fang, and F. Nawab, “PoneglyphDB: Efficient non-interactive zero-knowledge proofs for arbitrary sql-query verification,” Proceedings of the ACM on Management of Data, vol. 3, no. 1, 2025. [7] H. Wu, C. Wei, Y. Wang, L. Lin, Y. Leng, S. He, M. Zhao, H. Wu, Y. Yan, and A. Zhou, “Zero-knowledge verifiable graph query evaluation via expansion-centric operator decomposition,” 2025. [8] Plonky3 Contributors, “Plonky3: A toolkit for polynomial IOPs,” GitHub repository, 2026, accessed 10 July 2026. [Online]. Available: https://github.com/Plonky3/Plonky3 [9] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, “Fast reed– solomon interactive oracle proofs of proximity,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), ser. Leibniz International Proceedings in Informatics, vol. 107. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 14:1–14:17.

[10] ——, “Scalable, transparent, and post-quantum secure computational integrity,” Cryptology ePrint Archive, Report 2018/046, 2018. [Online]. Available: https://eprint.iacr.org/2018/046 [11] Linked Data Benchmark Council, “LDBC Social Network Benchmark,” https://ldbcouncil.org/benchmarks/snb/, 2026, accessed: 2026-07-09. [12] U. Haböck, “Multivariate lookups based on logarithmic derivatives,” Cryptology ePrint Archive, Paper 2022/1530, 2022. [Online]. Available: https://eprint.iacr.org/2022/1530 [13] L. Eagen, S. Kanjalkar, T. Ruffing, and J. Nick, “Bulletproofs++: Next generation confidential transactions via reciprocal set membership arguments,” in Advances in Cryptology – EUROCRYPT 2024, ser. Lecture Notes in Computer Science, vol. 14655. Cham, Switzerland: Springer, 2024, pp. 249–279. [14] R. Barbulescu and S. Duquesne, “Updating key size estimations for pairings,” Journal of Cryptology, vol. 32, no. 4, pp. 1298–1336, 2019. [15] F. Li, M. Hadjieleftheriou, G. Kollios, and L. Reyzin, “Dynamic authenticated index structures for outsourced databases,” in Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2006, pp. 121–132. [16] C. Xu, C. Zhang, and J. Xu, “vChain: Enabling verifiable boolean range queries over blockchain databases,” in Proceedings of the 2019 ACM SIGMOD International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2019, pp. 141– 158. [17] M. L. Yiu, Y. Lin, and K. Mouratidis, “Efficient verification of shortest path search via authenticated hints,” in 2010 IEEE 26th International Conference on Data Engineering. Los Alamitos, CA, USA: IEEE Computer Society, 2010, pp. 237–248. [18] Z. Fan, Y. Peng, B. Choi, J. Xu, and S. S. Bhowmick, “Towards efficient authenticated subgraph query service in outsourced graph databases,” IEEE Transactions on Services Computing, vol. 7, no. 4, pp. 696–713, 2014. [19] D. Reijsbergen, A. Maw, Z. Yang, T. T. A. Dinh, and J. Zhou, “TAP: Transparent and privacy-preserving data services,” in 32nd USENIX Security Symposium (USENIX Security 23). Anaheim, CA: USENIX Association, 2023, pp. 6489–6506. [Online]. Available: https: //www.usenix.org/conference/usenixsecurity23/presentation/reijsbergen [20] S. Bajaj and R. Sion, “CorrectDB: Sql engine with practical query authentication,” Proceedings of the VLDB Endowment, vol. 6, no. 7, pp. 529–540, 2013. [21] W. Zhou, Y. Cai, Y. Peng, S. Wang, K. Ma, and F. Li, “VeriDB: An SGXbased verifiable database,” in Proceedings of the 2021 International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2021, pp. 2182–2194. [22] Y. Zhang, J. Katz, and C. Papamanthou, “IntegriDB: Verifiable sql for outsourced databases,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA: Association for Computing Machinery, 2015, pp. 1480–1491. [23] Y. Zhang, D. Genkin, J. Katz, D. Papadopoulos, and C. Papamanthou, “vSQL: Verifying arbitrary sql queries over dynamic outsourced databases,” in 2017 IEEE Symposium on Security and Privacy. Los Alamitos, CA, USA: IEEE Computer Society, 2017, pp. 863–880. [24] C. Fournet, M. Kohlweiss, G. Danezis, and Z. Luo, “ZQL: A compiler for privacy-preserving data processing,” in 22nd USENIX Security Symposium (USENIX Security 13). Washington, D.C.: USENIX Association, 2013, pp. 163–178. [Online]. Available: https://www.usenix .org/conference/usenixsecurity13/technical-sessions/presentation/fournet [25] Z. Qiu, W. Qu, J. Zhang, and B. Yuan, “V3DB: Audit-on-demand zero-knowledge proofs for verifiable vector search over committed snapshots,” 2026. [26] Y. Zhang, C. Papamanthou, and J. Katz, “ALITHEIA: Towards practical verifiable graph processing,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA: Association for Computing Machinery, 2014, pp. 856–867. [27] E. Zhou, S. Guo, Z. Hong, C. S. Jensen, Y. Xiao, D. Zhang, J. Liang, and Q. Pei, “VeriDKG: A verifiable SPARQL query engine for decentralized knowledge graphs,” Proceedings of the VLDB Endowment, vol. 17, no. 4, pp. 912–925, 2023. [28] Z. Yao, T. Li, J. Xin, Y. Li, C. Wang, Z. Wang, D. Srivastava, and C. S. Jensen, “VGQ: Enabling verifiable graph queries on blockchain systems,” in 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 2025, pp. 3602–3614.

Related documents

• GraphRAGProv: GraphRAG Meets How-Provenance#1473701
• GraphRAGProv: GraphRAG Meets How-Provenance#1468841
• A graph testing framework for provenance network analytics#309910
• Soft Redaction of Image Provenance via Zero-Knowledge Proofs#440296
• Enabling Knowledge Graph Understanding at Scale with the EXplore Your Graphs ENgine (EXYGEN)#673529