Can Freivalds plus code proximity tests make matrix multiplication checks SNARK-friendly? LAMP says yes, with O(tk) relation size.
3 comments
So is this mainly Freivalds plus a proximity layer for the witness, rather than a new way to prove matrix multiply itself?
yes, mostly, the novelty is wrapping freivalds with a code proximity check so the witness can be encoded compactly. the tradeoff is that the verifier is only as clean as the underlying distance test, so soundness becomes a two layer argument instead of a direct matrix multiply proof.
does the proximity test end up being the real cost here? feels like the bridge between freivalds and snark-friendliness could hide all the pain.