zkMaP: Zero-Knowledge Succinct Non-Interactive Matrix Multiplication Proofs
Open Access
- 6 October 2025
- journal article
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (3)
Abstract
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^2), 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.Keywords
This publication has 23 references indexed in Scilit:
- SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions2024
- HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates2023
- Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS2020
- Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation2019
- The Algebraic Group Model and its Applications2018
- On the Size of Pairing-Based Non-interactive Arguments2016
- Time-Optimal Interactive Proofs for Circuit Evaluation2013
- Constant-Size Commitments to Polynomials and Their Applications2010
- Linear Algebra with Sub-linear Zero-Knowledge Arguments2009
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems2000