Paper 2026/111

Structured Matrix Constraint Systems for Architecture-Hiding Succinct Zero-Knowledge Proofs for Neural Networks

Abstract

Succinct zero-knowledge machine learning (zkML) uses zk succinct non-interactive arguments of knowledge (zkSNARKs) to prove neural-network (NN) computations with logarithmic-size proofs. However, general-purpose zkSNARKs do not scale in zkML because compiling matrix-heavy NNs into arithmetic circuits is memory-prohibitive. Existing zkML methods rely on rank-1 constraint systems (R1CS) to hide NN architectures while retaining succinctness. Removing circuit-based representations, it has remained unclear how to hide NN architectures without sacrificing succinctness. Motivated by this gap, we introduce matrix-circuit satisfiability (Mat-Circ-SAT) and a high-dimensional variant of R1CS, termed high-dimensional R1CS (HD-R1CS), for Mat-Circ-SAT. Architecturally, HD-R1CS encodes NN architectures via sparse matrices whose dimensions scale with the number of matrices, rather than with the total number of scalar entries, as in R1CS. Notably, we present zkSMART (zero-knowledge sparse matrix argument via restructuring transform) as a zkSNARK protocol for HD-R1CS. Compared to Evalyn (Asiacrypt '25), which hides the NN architecture using the proof-of-proof technique, zkSMART performs better in concrete prover time for deep NNs. More precisely, for NN computations with $M$ matrices of size $n \times n$, we achieve $O(n^2 M)$ prover time, $O(\log(nM))$ proof size and verifier time, and $O(n^2 M)$ RAM usage with a small constant factor. Such asymptotic efficiency enables our protocol to scale to NNs with up to a billion parameters.