I'm trying to figure out how to convert a circuit into a Square Arithmetic Program (SAP). This is to eventually use it for zk-SNARKs such as Groth16.
I do however understand how to convert arithmetic circuits into Quadratic Arithmetic Programs (QAP). As an example if we have the following circuit $c_1 \cdot c_2 = c_3$. Here we would define the following three polynomials: $L_1 = R_2 = O_3 = x$ (where L denotes left, R denotes right and O denotes output). Thus the final polynomial $$P = L \cdot R-O = c_1 \cdot x \cdot c_2 \cdot x - c_3 \cdot x$$
Therefore we have P(1)=0 whenever the circuit is satisfied.
Now for SAPs we want to eliminate multiplication gates, such that we do not require the 3 lists of polynomials (L,R,O), but rather 2. In Appendix A of: https://eprint.iacr.org/2017/540.pdf they explain how to write the product in terms of squares of the two operands:
$$
c_1\cdot c_2 = \frac{(c_1+c_2)^2-(c_1-c_2)^2}{4}
$$
It also shows the two new constraints that appear, but I can't translate this into some polynomials for where the new equation $P = I^2 - O$ (where I now denotes input) holds.
Hopefully one of you can lead me in the right direction.
