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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.