R1CS encoding
R1CS instance \(x=(\mathbb{F},A,B,C,io,m,n)\)
let \(Z=(io,1,w)\), then we have for example
\(\underbrace{\begin{bmatrix}0&1&1&0\\0&0&1&0\\…&…&…&..\\…&…&…&..\end{bmatrix}}_{A}\begin{pmatrix}w_1\\1\\w_2\\w_3\end{pmatrix}\circ \underbrace{\begin{bmatrix}0&1&0&0\\0&0&1&0\\…&…&…&..\\…&…&…&..\end{bmatrix}}_{B}\begin{pmatrix}w_1\\1\\w_2\\w_3\end{pmatrix}\)
\(=\underbrace{\begin{bmatrix}1&0&0&0\\0&0&0&1\\…&…&…&..\\…&…&…&..\end{bmatrix}}_{C}\begin{pmatrix}w_1\\1\\w_2\\w_3\end{pmatrix}\)
This express the constraints:
$$(1+w_2) \cdot 1=w_1$$
$$w_2 \cdot w_2=w_3$$
In order to use the sum-check protocol, we need to encode R1CS in a different way, as sum-check is about …