Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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].
