RNA: R1CS Normalization Algorithm Based on Data Flow Graphs for Zero-Knowledge Proofs

Abstract

The communities of blockchains and distributed ledgers have been stirred up by the introduction of zero-knowledge proofs (ZKPs). Originally designed as a solution to privacy issues, ZKPs have now evolved into an effective remedy for scalability concerns. To enable ZKPs, Rank-1 Constraint Systems (R1CSs) offer a verifier for bilinear equations. In order to accurately and efficiently represent R1CSs, several language tools, such as Circom, Noir, and Snarky, have been proposed to automate the compilation of advanced programs into R1CSs. However, due to the flexible nature of R1CS representation, there can be significant differences in the compiled R1CS forms generated from circuit language programs with the same underlying semantics. To address this issue, this article puts forth a dataflow-based R1CS paradigm algorithm, which produces a standardized format for different R1CS instances with identical semantics. Additionally, we present an R1CS benchmark, and our experimental evaluation demonstrates the efficacy of our methods.