# Arithmetic Circuit to Square Arithmetic Program (SAP)

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.

• Did you mean to have the abbreviation QAP in the title or SAP? Commented Feb 13, 2023 at 19:52
• Yes SAP, my bad Commented Feb 13, 2023 at 22:28