LAMP: Linear Verification of Matrix Multiplication via Proximity Testing

본문 미리보기

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 LAMP, a matrix-multiplication checking protocol that combines Freivalds' randomized check with proximity testing