Paper 2026/1571

LAMP: Linear Verification of Matrix Multiplication via Proximity Testing

Abstract

Verifiable computation systems often need to prove large matrix multiplication statements, but a direct SNARK arithmetization of a \(k \times k\) product requires \(\mathcal{O}(k^3)\) constraints. Freivalds' randomized check reduces the algebraic computation to vector-matrix products, but proving those products inside a SNARK still costs \(\mathcal{O}(k^2)\) constraints. We present $\textsf{LAMP}$, a matrix-multiplication checking protocol that combines Freivalds' randomized check with proximity testing over linear error-correcting codes. The prover commits to encoded matrices and intermediate vectors before the sampled query positions are derived. The CP-SNARK circuit then checks only the sampled codeword positions and commits to the values used inside the circuit, while Merkle openings and CP-Link proofs ensure consistency between the in-circuit witnesses and the externally committed values. We prove soundness for this committed-input setting under the soundness of the SNARK backend, the binding of the commitments, the correctness of the CP-Link checks, and the distance of the code. For a fixed number \(t\) of sampled positions, the main in-circuit SNARK relation has \(\mathcal{O}(tk)\) constraints, with additional \(\mathcal{O}(t\log n)+E_{\mathsf{link}}(k)\) backend work for Merkle openings and CP-Link checks. We implement $\textsf{LAMP}$ in Go and compare it with a Freivalds-based SNARK circuit. In the matrix benchmark at \(k=2^{12}\), $\textsf{LAMP}$ reduces the constraint count by \(30.3\times\) and shortens proof generation time by \(8.43\times\); verification stays at about \(0.06\) seconds across the measured matrix dimensions.