- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper formalizes complete GNN verification: proving that a query's output is derived from all dependencies required by full-graph MPNN inference over a committed private graph and model. It also proposes zkMPNN to achieve this query-locally. Hash-chained neighbor lists in a Merkle tree authenticate complete neighborhoods and original degrees, a verified-write-only memo enables safe state reuse, and Nova folding produces succinct proofs. The framework supports GCN, GraphSAGE, GIN, and GAT for node classification and link prediction. On Cora and OGB graphs, proofs are 14–18 KiB and verify in 3–11 s. Proving takes minutes to hours depending on query workload. On Cora, zkMPNN is cheaper than an EZKL full-graph baseline.
Critical strengths
-
A well-motivated and precisely specified problem.
-
A complete, carefully scoped end-to-end system.
Critical weaknesses
1. The evaluation does not establish when query-local proving actually pays off. The only measured baseline is a single EZKL run per task on Cora GCN. It differs in numerical semantics, privacy (deterministic digests, public topology), and memory limits, and the OGB baseline numbers are extrapolated rather than measured. More importantly, one full-graph proof certifies every node's output. On Cora, zkMPNN costs about 320–650 s per query versus about 4,100–5,300 s for the full-graph proof, so it loses after roughly 5–10 queries per snapshot. The paper never analyzes this amortization trade-off. Fixed costs are also high: trivial queries () still take 160–630 s, large queries take hours, and verifier keys are 0.9–2.7 GB.
2. Limited technical novelty.
The construction composes standard primitives: Merkle trees with hash chains, write-once memory checking, VM-style fixed-shape instructions, and Nova/Spartan. The authors acknowledge that the decomposition is inspired by Wu et al. (ICDE 2026), so the contribution is mainly careful systems design with little ML-specific insight. It is evaluated only on two-layer, narrow models, and the per-block re-opening cost grows linearly with model size. Meanwhile, the public execution length is determined by the closure sizes and the multi-hop degree sum , which range from 13 to over 100k across the selected queries. This directly reveals neighborhood structure around the queried node and weakens the stated goal of not revealing the graph. The zero-knowledge claim also rests only on a sketch and on an unanalyzed property of the specific compressed backend.
[1] Wu, H., Wei, C., Wang, Y., Lin, L., Leng, Y., He, S., ... & Zhou, A. (2026, May). Zero-knowledge verifiable graph query evaluation via expansion-centric operator decomposition. In 2026 IEEE 42nd International Conference on Data Engineering (ICDE) (pp. 461-473). IEEE.
Questions for authors
-
Leakage through execution length. Since is public and depends on and , how much does reveal about the queried node's multi-hop neighborhood? Can the system pad to a fixed public budget, or to coarse size buckets? What would that cost on the evaluated queries?
-
Zero-knowledge of the backend. Does the specific Nova 0.76 CompressedSNARK (Pallas/Vesta, IPA, Spartan) configuration you use provide zero-knowledge for the folded witness, including the running relaxed instance? Please point to the relevant security result rather than the implementation mechanism.
-
Amortization against full-graph proving. For a fixed snapshot, at how many queries does proving them individually with zkMPNN become more expensive than one full-graph proof? Can zkMPNN prove a batch of queries with a shared memo in one proof? If so, how does its cost compare with EZKL when the batch covers all test nodes?
-
Measured OGB baseline. Can you provide a measured (not extrapolated) full-graph baseline on at least one OGB graph, or explain concretely why it is infeasible, for example because it exceeds memory limits? Explaining infeasibility would itself support the paper's argument.
-
Scaling with model size. Every block re-opens and range-checks all coefficients. How do prover time and key size scale for deeper or wider models (e.g., with width 256) where grows by orders of magnitude? Could the parameters be bound once, for example by carrying a hidden parameter commitment in the folded state, instead of re-opened per block?
2 comments
Brief follow-up as the discussion period concludes
Dear Reviewer SH6u,
As the author-reviewer discussion period is approaching its end, we wanted to kindly follow up and ask whether our response above and the revised manuscript (highlighted in blue) have adequately addressed your five questions and concerns.
In particular, we have added (1) static break-even and dynamic-update amortization analyses, prospective shared-memo batching discussion, and concrete OGB full-graph out-of-memory scaling (Section 6.2; Table 1; Appendix A.2), (2) coarse bucket-padding scheduling with measured Cora overhead for , alongside an explicit separation between Nova/Spartan zero-knowledge results and our conditional backend simulator assumption (Section 5; Appendices D.2, E.2.3), and (3) clarified MPNN-specific completeness mechanisms, synthetic depth sweeps up to , and parameter-opening scaling (Sections 4.1, 6.5, 7; Appendices E.3, F.1).
We would greatly appreciate knowing whether these additions address your questions, or if any point would benefit from further clarification before the discussion closes. Thank you again for your thorough review and consideration.
Author Response to Reviewer SH6u
We thank Reviewer SH6u for valuing our problem and system, and for five questions.
Amortization, dynamic updates, and batching (W1, Q3): On a static Cora snapshot, full-graph EZKL cold totals break even with single-query
zkMPNNat 6–8 (NC) and 8–11 (LP) cold queries (Tables 9–10; ~5–9 prove-only, Tables 1, 10, App. A.2). Three factors govern payoff: (i) our EZKL circuit publishes only the three selected outputs via runtime selectors, so serving more queries from one proof needs public outputs/embeddings for all nodes or output commitments (else a new proof); (ii) amortization restarts on graph updates (G→G′): in our static-topology EZKL baseline, feature edits (fixed support) reuse setup+re-prove, while edge/support edits alter compiled constants and also need recompile+Halo2 setup; inzkMPNN, PP/PK/VK depend only on (A,Q,task,policy,B,Dg), staying reusable across valid feature/edge/node updates in the same 2Dg bucket (for frozen θ, G′ updates CG′ while Cθ holds if rθ is kept, though our CLI refreshes both and rebuilds the tree; each CG′ claim needs a fresh proof, with zero proving until queried); and (iii) at t=1, folding is zero and proof time is one-time Spartan/IPA compression (Table 7), so prospective shared-memo batching beforeDONEwould pay compression once over ⋃iSℓ(qi), whereas certifying all nodes of a small static graph with ample RAM favors a monolithic circuit.OGB baseline (W1, Q4): Full-graph EZKL on Cora already needed ~255–327 GiB peak RSS under a 512 GiB cap. Because
ogbn-arxivandogbl-collabhave ~63×–87× more nodes (Table 3), naive linear node scaling projects ~16–28 TiB, exceeding our 512 GiB cap and 2 TiB host RAM (Table 1'sest.rows rescale Cora byzkMPNNmax-T prove-time ratios), whereaszkMPNNproves OGB queries in ~7–12 GiB peak RSS (Table 8, App. A.2).Technical novelty (W2): Unlike stateless graph queries (Wu et al., ICDE 2026), learned MPNNs depend on boundary-node original degrees (δu,δv) and multi-pass reductions (GAT stabilization before softmax). While semantic local-to-full-graph equivalence (Proposition 1) holds by layer induction, enforcing it against an untrusted prover goes beyond generic ADS or zkVM memory by coupling chain termination (cv,δv=0, Eq. (4)) to authenticated original degrees, binding GAT's two-pass rewind stream before ELU under Q, and stage-addressing write-once memo states (ℓ2Dg+v; Sec. 4, App. F.1).
Execution-length leakage & padding (W2, Q1): Without padding, tmin=⌈T/B⌉ bounds T to [B(tmin−1)+1,Btmin], constraining the multi-hop aggregate (Kℓ,U) (Eqs. (7), (18)) without uniquely fixing per-node degrees or topology in general. Since readout clears state to canonical
DONEand trailingDONEops preserve it with no minimal-schedule rule, the planner can pad t to coarse buckets tb≥tmin or a fixed cap with unchanged circuit, commitments, and VK, coarsening disclosure to the bucket/cap range (output/timing side channels remain separate, App. D.2). On Cora/GCN/NC (B=16, single-run shared-host scope; App. E.2.3), paddingminandlmedqueries up to tb=38 (pool max) added only 2.16–2.35 s of folding per extra block with near-stable compression, raising online time by up to ~26%, with all proofs verifying and t±1 relabelling rejected.Backend zero-knowledge (W2, Q2): Nova (Kothapalli et al., CRYPTO 2022, Sec. 4.4/Thm. 4) achieves ZK for relaxed R1CS instances by folding a random satisfying instance under hiding Pedersen commitments, and Spartan (Setty, CRYPTO 2020, Sec. 7) uses blinded commitments and ZK openings. Because
nova-snark0.76 (Pallas/Vesta, IPA, SpartanCompressedSNARK) lacks a standalone crate proof (App. D.2), Theorem 1(iii) pairs our circuit guarantees (randomized (CG,Cθ), private roots, andDONEclearing) with an explicit conditional simulator assumption.Model scaling (W2, Q5): RQ4 sweeps depth up to L=8 (Table 15), and Exp. 1 reaches nearly 105 parameters on two-layer Cora LP GraphSAGE, where two-matrix layers roughly double key sizes and compression vs. GCN (Tables 7, 9). A hypothetical L=3, width-256 GCN (above our dℓ≤64 bound and enlarging dense products in Cμ) has ~1.1×105 parameters on
ogbn-arxiv(near Cora LP GraphSAGE) and ~4.3×105 on Cora (App. E.3). For much larger P, per-block κθ(P)=Θ(32P) becomes a bottleneck; range-checking θ once in an init block and carrying a blinded commitment across blocks (cleared atDONE) is prospective, needing a cross-block consistency proof.Manuscript revisions: Highlighted in blue in the revised PDF (Secs. 4.1, 5, 6.2, 6.5, 7; Apps. A.2, D.2, E.2.3, E.3, F.1).