I have been following the medium post of Vitalik, where he shows step by step how to convert program --> Circuit --> R1CS --> QAP.

I am aware of the Pinocchio protocol, where they utilize the Groth13 QAP to generate proofs. I am also aware of Groth16, which improves QAP generation.

However, besides Vitalik's post, I haven't seen anyone in those papers talk anything regarding the R1CS constraints. Is this process somehow get done inside the QAP generation?

What am I missing?


In the original Pinocchio [GGPR13], the authors didn't use R1CS at all.

As a ZKP friendly computational representation, R1CS was proposed later that year in [BCGTV13] Appendix E. The reduction from an arithmetic circuit to R1CS is quite straightforward, which I guess is the reason why there's no dedicated papers introducing such a computation model.

Soon after its introduction, the BCGTV13 authors started to implement the system into libsnarks, and people started to realise that R1CS is quite easy to be arithmetized. (normally a SNARK is based on Linear IOP or a polynomial IOP that operates on polynomials, thus the efficiency of the arithmetization of R1CS or other representation into polynomials is important).

Ben-Sasson et.al has a pretty good empirical reason on why R1CS became a popular choice in his 2018 Aurora paper (Page 4):

We choose R1CS because it strikes an attractive balance: it generalizes circuits by allowing “native” field arithmetic and having no fan-in/fan-out restrictions, but it is simple enough that one can design efficient argument systems for it. Moreover, R1CS has demonstrated strong empirical value: it underlies real-world systems [Zca] and there are compilers that reduce program executions to it (see [WB15] and references therein). This has led to efforts to standardize R1CS formats across academia and industry [Zks].


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.