[Stwo Backend]: Efficient MatMul Verification in Circuits with Freivalds

[raphaelDkhn]

Here is a proposition. We can implement a verification mechanism for matrix multiplication 𝐶 = 𝐴 𝐵 in the circuit using a Freivalds' randomized algorithm.
This approach avoids directly multiplying 𝐴 and 𝐵 in the circuit. The MatMul can be computed in an non-trusted environment, and verify in the circuit with a high probability that 𝐶 = 𝐴 𝐵.

Flow:

1. Sample a random field element 𝑟 ∈ 𝐹 𝑝 using the Fiat-Shamir transform.
2. Construct vector 𝑣 = ( 1 , 𝑟 , 𝑟 2 , … , 𝑟 𝑚 − 1 ).
3. Compute 𝐴 ( 𝐵 𝑣 ) and 𝐶 𝑣.
4. Verify 𝐴 ( 𝐵 𝑣 ) = 𝐶 𝑣

Requirements:

1. Prover must commit to 𝐴, 𝐵, and 𝐶 before sampling 𝑟.
2. Allow the Prover to compute 𝐶 outside the circuit.