We introduce zkMaP (Zero-Knowledge Succinct Non-Interactive Matrix Multiplication Proofs), a novel non-interactive zero-knowledge proof system for verifying matrix multiplication with significant improvements in efficiency and scalability. Our protocol leverages KZG polynomial commitments and an innovative inner-product reduction technique to reduce the verification of n x n matrix multiplication to a single pairing equation, thereby enabling constant-time verification independent of the matrix size. In particular, zkMaP requires only two pairing operations and produces proofs as small as 320 bytes, yielding a 96 percent reduction in proof size compared to prior schemes. Furthermore, the prover's computational complexity follows the state-of-the-art at O (n²), with experimental results demonstrating that proofs for 1024 x 1024 matrices can be generated in approximately 12. 21 seconds, offering a 16. 14x speedup over previous methods. Our implementation also exhibits better memory efficiency, using only 24. 58 MB of prover-side RAM for 1024 x 1024 matrices, and supports scalable batch processing, achieving per-proof generation times of 46. 79 milliseconds for 1024 instances while maintaining a constant verification time of 3. 6 ms.
Deressa et al. (Mon,) studied this question.