ZK-GSP: Zero-Knowledge Verifiable Graph Neural Network Inference

Abstract

We propose ZK-GSP, a framework for privacy-preserving, verifiably correct graph neuralnetwork (GNN) inference using zero-knowledge STARKs. The key insight is a structuralisomorphism between RISC Zero's zkVM and graph signal processing (GSP) pipelines:both are typed, deterministic data-flow graphs whose execution can be committed to witha succinct, publicly verifiable proof. By implementing GSP operators as instructions insidethe RISC Zero executor, we obtain a system that runs GNN programs on private graphdata and emits a STARK receipt proving correct execution, without revealing the graphtopology, node features, or intermediate embeddings. We demonstrate an end-to-endimplementation in Rust, measure proof generation time and RISC-V cycle count acrossgraph sizes N = 4 to 32, and find that cycle count scales as O(N2), matching thecomplexity of the underlying GCN operator. Code: github.com/brack-6/zk-gsp