acceptodds
Under review as a conference paper at ICLR 2027

zkMPNN: Query-Local Zero-Knowledge Proofs of Complete Message-Passing Inference

Abstract

Message passing neural networks (MPNNs) are a powerful class of deep learning models for graph-structured data. To our knowledge, no existing approaches to verifiable machine learning establish both the correctness of the computation and the completeness of the required neighbors and intermediate states for a prediction. This paper formalizes this requirement as complete GNN verification and proposes zkMPNN, a modular framework for complete, query-local graph neural network (GNN) inference over committed models and graphs using zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs). Our evaluation demonstrates end-to-end proving for all 48 selected cases across four GNN families on node-classification and link-prediction tasks. Compressed proofs are 14.2–18.4 KiB and verify in 3.2–11.1 s with the public parameters and verifier key available. Controlled synthetic experiments show that proving costs depend jointly on query dependencies and authentication-circuit shape, rather than total graph size alone.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Graph neural networks, Verifiable inference, Zero-knowledge proofs, Message passing neural networks, Incrementally verifiable computation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_SH6uOpenReview ↗
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
  1. A well-motivated and precisely specified problem.

  2. 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 (T=13T = 13) 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 Θ(32P)\Theta(32P) grows linearly with model size. Meanwhile, the public execution length tt is determined by the closure sizes KℓK_\ell and the multi-hop degree sum UU, 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
  1. Leakage through execution length. Since tt is public and TT depends on KℓK_\ell and UU, how much does tt 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?

  2. 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.

  3. 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?

  4. 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.

  5. Scaling with model size. Every block re-opens and range-checks all PP coefficients. How do prover time and key size scale for deeper or wider models (e.g., L=3L = 3 with width 256) where PP 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
AuthorsOpenReview ↗

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 zkMPNN at 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′G\to 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; in zkMPNN, PP/PK/VK depend only on (A,Q,task,policy,B,Dg)(\mathcal{A},\mathcal{Q},\text{task},\text{policy},B,D_g), staying reusable across valid feature/edge/node updates in the same 2Dg2^{D_g} bucket (for frozen θ\theta, G′G' updates CG′C_{G'} while CθC_\theta holds if rθr_\theta is kept, though our CLI refreshes both and rebuilds the tree; each CG′C_{G'} claim needs a fresh proof, with zero proving until queried); and (iii) at t=1t=1, folding is zero and proof time is one-time Spartan/IPA compression (Table 7), so prospective shared-memo batching before DONE would pay compression once over ⋃iSℓ(qi)\bigcup_i S_\ell(q_i), 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-arxiv and ogbl-collab have ~63×63\times–87×87\times more nodes (Table 3), naive linear node scaling projects ~16–28 TiB, exceeding our 512 GiB cap and 2 TiB host RAM (Table 1's est. rows rescale Cora by zkMPNN max-TT prove-time ratios), whereas zkMPNN proves 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\delta_u,\delta_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=0c_{v,\delta_v}=0, Eq. (4)) to authenticated original degrees, binding GAT's two-pass rewind stream before ELU under Q\mathcal{Q}, and stage-addressing write-once memo states (ℓ2Dg+v\ell 2^{D_g}+v; Sec. 4, App. F.1).

Execution-length leakage & padding (W2, Q1): Without padding, tmin⁡=⌈T/B⌉t_{\min}=\lceil T/B\rceil bounds TT to [B(tmin⁡−1)+1,Btmin⁡][B(t_{\min}-1)+1, Bt_{\min}], constraining the multi-hop aggregate (Kℓ,U)(K_\ell,U) (Eqs. (7), (18)) without uniquely fixing per-node degrees or topology in general. Since readout clears state to canonical DONE and trailing DONE ops preserve it with no minimal-schedule rule, the planner can pad tt to coarse buckets tb≥tmin⁡t_b\ge t_{\min} 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=16B=16, single-run shared-host scope; App. E.2.3), padding min and lmed queries up to tb=38t_b=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±1t\pm 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-snark 0.76 (Pallas/Vesta, IPA, Spartan CompressedSNARK) lacks a standalone crate proof (App. D.2), Theorem 1(iii) pairs our circuit guarantees (randomized (CG,Cθ)(C_G,C_\theta), private roots, and DONE clearing) with an explicit conditional simulator assumption.

Model scaling (W2, Q5): RQ4 sweeps depth up to L=8L=8 (Table 15), and Exp. 1 reaches nearly 10510^5 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=3L=3, width-256 GCN (above our dℓ≤64d_\ell\le 64 bound and enlarging dense products in CμC_\mu) has ~1.1×1051.1\times 10^5 parameters on ogbn-arxiv (near Cora LP GraphSAGE) and ~4.3×1054.3\times 10^5 on Cora (App. E.3). For much larger PP, per-block κθ(P)=Θ(32P)\kappa_\theta(P)=\Theta(32P) becomes a bottleneck; range-checking θ\theta once in an init block and carrying a blinded commitment across blocks (cleared at DONE) 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).

AuthorsOpenReview ↗

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 tt, 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 L=8L=8, and Θ(32P)\Theta(32P) 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.

Reviewer_Sx1jOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper starts by motivating that to the authors' knowledge, no existing approaches to verifiable ML for MPNN establish both the correctness of the computation and the completeness of the required neighbors and intermediate states for a prediction. The paper formalizes this requirement as complete GNN verification and proposes their solution called zkMPNN using cryptographic tools such as commitment schemes and zk-SNARKs. The authors present experimental results on several GNN families on node-classification and link-prediction tasks to show the practicality of their proposal.

Critical strengths

The topic itself is important; privacy of model and graph is important and formalizing the requirements, proposing a solution, and evaluating with several networks and datasets are meaningful.

Critical weaknesses
  1. The motivation and the contribution of the paper are rather confusing.
  • For the motivation, there is a gap between abstract and introduction. More precisely, the authors said in the abstract that "To our knowledge, no existing approaches to verifiable machine learning establish both the correctness of the computation and the completeness of the required neighbors and intermediate states for a prediction." Here, the authors pointed out the absence of a solution for the correctness and the completeness, without mentioning the confidentiality or zero-knowledgeness. That is, it seems like verifiable computation without zero-knowledge would be sufficient for this problem. But their solution zkMPNN has zero-knowledgeness. In the introduction, the authors emphasize the importance of both zero-knowledgeness and completeness together by saying that "This motivates a mechanism for verifying predictions without revealing the underlying model or graph data." and "This motivates query-local proof generation as a cost-reduction strategy, while retaining the same completeness guarantee." I think that the above sentence in the abstract is too broad as written, because the introduction itself says that "A straightforward way to meet this completeness requirement is to prove full-graph inference and the subsequent queries over its outputs," and the EZKL-based full-graph baseline in Section 6 implements full-graph inference, although its disclosure setting and numerical semantics differ from zkMPNN's. In addition, Appendix F.3 describes the contribution as "the relation and the query-local authenticated message-passing construction," which is more specific than the claim in the abstract. So it would be better to clarify the motivation and the explanation about previous results.
  • I think that the confidentiality of the underlying model or graph data is a main motivation of this work. However, the proposal reveals some information about them and the paper did not clearly analyze the impact of such leakage on the motivation scenarios mentioned in the introduction. Appendix F.4 acknowledges that protection from inference through public outputs or metadata is not established, but the implications of this limitation for the motivating scenario are not clearly discussed in the main part of the paper. For example, as already mentioned in the main security theorem (Theorem 1), the declared public view is revealed, where the public statement contains the commitments, the declared public configuration and execution length, the query, and the result. These public data may contain information about the graph. It would be better to clarify why proposing a solution without hiding public data can be a solution for the motivating scenarios.
  1. The comparison with the full-graph baseline (EZKL) is done only with Cora, and the baseline costs for the other datasets are just estimated from zkMPNN's own prove-time ratios (Table 1).
Questions for authors

Could you comment on why proposing a solution without hiding public data can be a solution for the motivating scenarios?

2 comments
AuthorsOpenReview ↗

Author Response to Reviewer Sx1j

We thank Reviewer Sx1j for recognizing our problem formulation, model and graph confidentiality focus, and multi-family evaluation, and for noting the narrative gap between the Abstract and Introduction.

Motivation gap between the Abstract, Introduction, and Appendix F.3 (W1, point 1): We completely agree with your observation. While the third sentence of the original Abstract mentioned "committed models and graphs using zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs)," the second sentence described the gap in terms of computation correctness and neighborhood completeness alone, omitting confidentiality over a private graph/model and overlooking that upfront full-graph proving (such as our EZKL baseline) achieves completeness at higher resource cost. In the revised manuscript, we rewrote the second sentence of the Abstract to match Section 1 and Appendix F.3 directly: "Existing verifiable inference methods either do not authenticate complete multi-hop neighborhoods over a private graph or require proving full-graph inference upfront."

Why proving over the public statement xx solves the motivating scenarios (W1, point 2; Q1): Proving over the declared public statement x=(A,Q,N,Dg,B,policy,task,Cθ,CG,q,y,t)x=(\mathcal{A},\mathcal{Q},N,D_g,B,\text{policy},\text{task},C_\theta,C_G,q,y,t) without hiding those fields directly fits remote prediction and compliance or partner audits (Section 1, Figure 1). Here, the verifier is the querying client, partner, or auditor who submits or audits a target node/pair qq (e.g., a flagged account or transaction link) and receives yy under agreed (A,Q)(\mathcal{A},\mathcal{Q}) and registered commitments (CG,Cθ,N,Dg)(C_G,C_\theta,N,D_g); hiding qq or yy from the requester is neither needed nor meaningful. What prevents the verifier from recomputing y=EvalA,θQ(G,q)y=\mathsf{Eval}_{\mathcal{A},\theta}^{\mathcal{Q}}(G,q) directly to check completeness is witness confidentiality: direct recomputation would force the operator to disclose proprietary weights θ\theta and third-party customers' private feature vectors xux_u, edges EE, and neighbor lists R(v)R(v) in GG. Under Theorem 1(iii), all witness data beyond xx, including θ\theta, unqueried graph records, randomizers (rG,rθ)(r_G,r_\theta), and intermediate embeddings hv(ℓ)h_v^{(\ell)}, remains computationally protected, conditional on commitment hiding and the backend simulator assumption (Section 3, Appendix F.4).

Coarsening execution-length disclosure tt via bucket padding (W1, point 2; Q1): Among the fields in xx, the remaining query-dependent metadata beyond (q,y)(q,y) is the block count t≥tmin⁡=⌈T/B⌉t\ge t_{\min}=\lceil T/B\rceil. Because readout clears witness state into canonical DONE and trailing DONE instructions preserve it with no minimal-schedule rule, the operator can coarsen tt by padding to a public bucket tbucket≥tmin⁡t_{\mathrm{bucket}}\ge t_{\min} (or a fixed policy cap) without modifying the circuit, commitments, or verifier key. On our frozen Cora/GCN/NC instance (B=16B=16, single-run shared-host scope; Appendix E.2.3), bucket padding added only 2.16–2.35 s of folding per added block while one-time Spartan/IPA compression stayed approximately stable, raising online proof time by about 25–26% even at the largest tested bucket (tbucket=38t_{\mathrm{bucket}}=38), with all padded proofs verifying under the unchanged verifier key and rejecting t±1t\pm 1 relabelling.

Full-graph EZKL baseline on Cora vs. OGB extrapolations (W2): Full-graph EZKL was measured on Cora while the OGB entries in Table 1 are reported as est. because monolithic Halo2 full-graph proving already required roughly 255–327 GiB peak RSS on Cora under an expanded 512 GiB process limit. Because ogbn-arxiv and ogbl-collab have roughly 63×63\times–87×87\times more nodes (Table 3), materializing all node states in a single full-graph table scales linearly into the tens of TiB, exceeding both our 512 GiB process limit and our 2 TiB host RAM. Table 1 therefore explicitly labels OGB EZKL rows as descriptive rescalings from Cora via zkMPNN's max-workload prove-time ratios rather than measured runs, whereas zkMPNN proves OGB queries locally within ~7–12 GiB peak RSS (Table 8, Appendix A.2).

Manuscript revisions: Corresponding updates are highlighted in blue in the revised PDF (Abstract; Sections 3, 5, 6.2; Table 1; Appendices A.2, E.2.3, F.4).

AuthorsOpenReview ↗

Brief follow-up as the discussion period concludes

Dear Reviewer Sx1j,

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 question and concerns.

In particular, we have (1) rewritten the Abstract's motivation sentence to align directly with Section 1 and Appendix F.3, (2) clarified why verifying over the declared public statement xx fits remote prediction and compliance/partner audits while keeping model weights and graph witnesses private, together with new Cora bucket-padding measurements for coarsening tt (Sections 3, 5; Appendices E.2.3, F.4), and (3) documented why monolithic full-graph EZKL exceeds memory limits on OGB graphs (Section 6.2; Table 1; Appendix A.2).

We would greatly appreciate hearing whether these clarifications and additions resolve your concerns, or if we can clarify anything further before the discussion closes. Thank you again for your time and consideration.

Reviewer_MP41OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies zero-knowledge verification of GNN inference over a private graph and a private model. The proposed system, zkMPNN, proves only the query’s dependency closure instead of the whole graph.

Critical strengths

The implementation is careful and evaluated end to end.

The paper checks fidelity against floating-point checkpoints on full test sets, and achieves nearly perfect decision agreement.

Critical weaknesses

The technical contribution is a composition of standard techniques, and the paper does not show what it improves on. Hash-chained neighbor lists in Merkle leaves are standard authenticated data structures. The verified-write-only memo is Merkle-based memory checking inside IVC. Folding fixed-shape instruction blocks with Nova follows zkVM designs.

The only baseline is a single EZKL full-graph GCN run on Cora. EZKL is a general-purpose framework, and it is not where the state of the art in zkML lies. Most recent zkML systems (e.g., zkCNN, zkLLM, zkGPT) build customized, highly optimized proof backends on efficient protocols such as sumcheck/GKR and lookup arguments. Being faster than EZKL therefore says little about whether the proposed design is competitive. The paper should compare against with the strongest possible baselines under the SOTA ZKP techniques.

The paper fails to cite most of the popular literature in ZKML.

The execution length t is public. Since T = U + 2A_q + 1, it reveals the size of the query’s dependency closure, i.e., local degree and neighborhood information about the private graph. This conflicts with the claim of not revealing the graph.

Questions for authors

NA

2 comments
AuthorsOpenReview ↗

Author Response to Reviewer MP41

We thank Reviewer MP41 for appreciating our end-to-end implementation and full-test-set fidelity study against floating-point checkpoints.

Technical novelty (W1): While zkMPNN builds on established primitives (Merkle trees, Poseidon hash chains, write-once memory checking, and Nova/Spartan folding) rather than proposing a new cryptographic primitive, generic authenticated data structures or zkVM memory alone do not enforce sound query-local MPNN inference. Unlike stateless declarative graph queries (Wu et al., ICDE 2026), learned message-passing layers depend on boundary-node original degrees (δu,δv\delta_u,\delta_v in GCN normalization) and multi-pass neighborhood reductions (GAT's stabilization pass followed by softmax accumulation). Proving arithmetic on an extracted induced subgraph silently alters boundary degrees or permits omitting unfavorable high-attention neighbors. While semantic local-to-full-graph equivalence (Proposition 1) holds by layer induction, enforcing this equivalence against an untrusted prover requires MPNN-specific protocol mechanisms: coupling neighbor-chain termination (cv,δv=0c_{v,\delta_v}=0 at cursor δv\delta_v, Eq. (4)) to authenticated original degrees δu,δv\delta_u,\delta_v, binding GAT's two-pass rewind stream so both passes traverse the identical complete neighbor list before ELU under fixed-point contract Q\mathcal{Q}, and isolating verified states via stage-addressed write-once memoization (ℓ2Dg+v\ell 2^{D_g}+v) to prevent cross-stage substitution while avoiding exponential multi-hop re-expansion (Section 4, Appendix F.1).

Comparison with specialized zkML backends and literature coverage (W2, W3): Section 2 and Appendix F cited zkCNN (Liu et al., CCS 2021), ZKML (Chen et al., EuroSys 2024), zkGCN (Ding et al., ICA3PP 2025/2026), EZKL, and the verifiable ML survey (Lyu et al., ACM CSUR 2026); we have now added zkLLM (Sun et al., CCS 2024) and zkGPT (Qu et al., USENIX Security 2025). Architecturally, zkCNN, zkLLM, and zkGPT design specialized sumcheck/GKR and lookup protocols (tlookup, zkAttn) for dense, fixed-shape tensor operators on regular inputs, without authenticating sparse multi-hop extraction, boundary degrees δu,δv\delta_u,\delta_v, or DAG state reuse over a committed private graph CGC_G. Conversely, zkGCN computes degree normalization and aggregation outside the circuit and passes the pre-aggregated matrix as a public input, sacrificing both graph privacy and in-circuit completeness. We selected EZKL as a mature end-to-end Halo2/KZG baseline for full-graph message passing (under documented disclosure and arithmetic differences, Appendix A.1.1). A monolithic full-graph circuit must account for all computations required by full-graph inference, whereas zkMPNN restricts the proved computation to the query-dependent closure. Our full-graph EZKL baseline required roughly 255–327 GiB peak RSS on Cora under a 512 GiB process limit, whereas query-local zkMPNN proves queries on OGB graphs with ~63×63\times–87×87\times more nodes using only ~7–12 GiB peak RSS (Tables 1 and 8). Because zkCNN, zkLLM, and zkGPT do not authenticate this complete query-local graph relation, an equivalent-relation benchmark against those specialized backends is not available and our evaluation does not claim backend speed superiority over them; accelerating dense subcircuits inside CμC_\mu with sumcheck or lookup arguments is orthogonal and complementary to our query-local relation.

Public execution length tt and neighborhood leakage (W4): The formal public statement xx includes the declared block count t≥tmin⁡=⌈T/B⌉t\ge t_{\min}=\lceil T/B\rceil (Appendix D.1), while Theorem 1(iii) protects witness data beyond xx. Crucially, readout enters canonical DONE (clearing the memo root and witness scratch state), and trailing DONE instructions legally preserve that terminal state with no minimal-schedule rule in the circuit. A privacy-hardened planner can therefore pad tt to a coarse public bucket tbucket≥tmin⁡t_{\mathrm{bucket}}\ge t_{\min} with no changes to the circuit, commitments, or verifier key. On our frozen Cora/GCN/NC instance (B=16B=16, single-run shared-host scope; Appendix E.2.3), bucket padding added only 2.16–2.35 s of folding per extra block while one-time Spartan/IPA compression stayed approximately stable, increasing online proof time by about 25–26% even at the largest tested bucket (tbucket=38t_{\mathrm{bucket}}=38), with all padded proofs verifying under the unchanged verifier key and rejecting t±1t\pm 1 relabelling.

Manuscript revisions: Corresponding updates are highlighted in blue in the revised PDF (Sections 1, 2, 4.1, 5, 6.2; Appendices A.2, E.2.3, F.1, F.3; References).

AuthorsOpenReview ↗

Brief follow-up as the discussion period concludes

Dear Reviewer MP41,

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 concerns.

In particular, we have (1) clarified the MPNN-specific protocol mechanisms required to enforce complete query-local inference against an untrusted prover beyond generic ADS/zkVM primitives (Sections 1, 4.1; Appendix F.1), (2) added citations and architectural positioning for zkLLM and zkGPT alongside documented full-graph memory limits and relation differences from dense-tensor zkML backends (Sections 2, 6.2; Table 1; Appendix A.2), and (3) added coarse bucket-padding scheduling with new Cora overhead measurements for the public execution length tt under an unchanged circuit and verifier key (Section 5; Appendix E.2.3).

We would greatly appreciate knowing whether these additions address your concerns, and we remain happy to clarify any remaining points before the discussion closes. Thank you again for your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response and Summary of Manuscript Revisions

We sincerely thank the Area Chairs and Reviewers (MP41, Sx1j, SH6u) for their thoughtful feedback and for recognizing our complete GNN verification formulation, end-to-end evaluation across four MPNN families and four dataset–task settings, and full-test-set floating-point fidelity study. We carefully considered all comments (spanning motivation and audit disclosure scope, protocol-level novelty and zkML literature positioning, execution-length mitigation and backend zero-knowledge assumptions, and full-graph baseline feasibility, amortization, and model scaling) and updated the manuscript with clarified discussions, targeted bucket-padding measurements, and static/dynamic amortization analyses. Each individual reviewer response below is self-contained with detailed explanations and empirical results; all manuscript revisions are highlighted in blue in the revised PDF and indexed below by structural section, table, and appendix labels:

Summary of Manuscript Revisions (highlighted in blue):

  • Abstract, Section 3, and Appendix F.4 (Sx1j-W1, Q1): Rewrote the Abstract's motivation sentence to align with Section 1 and Appendix F.3, and clarified how verifying over the declared public statement serves remote prediction and compliance audits while protecting private model and graph witnesses.
  • Sections 1, 2, 4.1, Appendices F.1, F.3, and References (MP41-W1, W2, W3; SH6u-W2): Clarified our protocol-level design for enforcing complete query-local MPNN inference against an untrusted prover, and added citations and positioning for zkLLM and zkGPT alongside zkCNN, ZKML, EZKL, and zkGCN.
  • Section 5 and Appendices D.2, E.2.3 (MP41-W4; Sx1j-W1, Q1; SH6u-W2, Q1, Q2): Added coarse bucket-padding scheduling for the public execution length with new Cora overhead measurements, and separated theoretical Nova/Spartan zero knowledge from our conditional backend simulator assumption.
  • Section 6.2, Table 1, and Appendix A.2 (MP41-W2; Sx1j-W2; SH6u-W1, Q3, Q4): Documented why full-graph baseline runs exceed memory limits on OGB graphs, added static break-even and dynamic-graph update amortization analyses, and discussed prospective multi-query batching.
  • Sections 6.5, 7, and Appendix E.3 (SH6u-W2, Q5): Clarified depth and width scaling observations, analyzed parameter-opening scaling on deeper and wider architectures, and outlined prospective cross-block parameter binding as future work.

We welcome any further questions during the discussion period.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.