Insights from R1CS Normalization Benchmark Analysis

Table of Links

Abstract & Introduction

Preliminaries

Normalization Algorithm

Evaluation

Conclusion & References

IV. EVALUATION

In this section, we introduced the self-designed benchmark used in this paper. We evaluated the effectiveness of the paradigm generation algorithm by analyzing the test results and the intermediate outputs.

A. Benchmark Design

To evaluate the proposed algorithm in this paper, we implemented the entire process of paradigm generation explained in the former section using Python to verify its results.

Due to the lack of related research, this field has no comprehensive benchmark. Therefore, we summarized some rules for generating equivalent R1CS constraint groups based on the logic the mainstream Circom compiler used to create R1CS and designed a more comprehensive benchmark based on these rules. The benchmark includes the following main categories depending on the reflected situation:

1. Replacement of variable order in R1CS.

   
   

2. Transformation of constraint order in R1CS.

   
   

3. Introduction of multiple new variables in a single linear constraint in R1CS.

   
   

4. Introduction of new variables in multiple linear constraints in R1CS, with shared new variables.

   
   

5. Merging and splitting of constraints in R1CS.

The different categories in the benchmark correspond to the other reasons for generating equivalent R1CS. Each category contains 2-3 basic R1CS constraints. To comprehensively test the robustness and correctness of the algorithm, 5-6 equivalent R1CS constraint groups are generated for each R1CS based on the respective reasons. The equivalent constraint groups of each constraint group are paired and inputted into the algorithm to verify whether the algorithm can generate consistent and R1CS-compliant output results defined in definition II.5, when processing different equivalent constraint groups.

The publicly available data set used in this study can be found at the following GitHub repository: https://github. com/Ash1sc/R1CS normalization benchmark. This repository contains the raw data that was utilized for testing purposes. It is important to note that the data set is licensed under the GNU General Public License version 3.0 (GPL-3.0). This license allows for the data set and scripts to be freely distributed, modified, and used, with the condition that any derived works are also licensed under the GPL-3.0 and that the original copyright and license information is retained. If you would like to learn more about the details of the GPL-3.0, please visit https://www.gnu.org/licenses/gpl-3.0.en.html.

B. Result Evaluation

Table I shows the result of the experiments.

Observation shows that the generated paradigms meet the requirements of the R1CS paradigm mentioned above and have equal semantics as the original R1CS constraint groups.

Through analysis of the intermediate outputs at each stage of the conversion process, it was found that for equivalent R1CS constraint groups generated by reordering constraints, the only difference in the resulting data flow graphs lies in the order in which nodes representing intermediate variables are created. This is due to different processing orders of each constraint during traversal, leading to other orders of introducing intermediate variables in each constraint.

For equivalent R1CS constraint groups generated by variable replacement, the differences lie in the order in which RNodes representing initial variables in the R1CS are developed and in the order of addition in the summation chain structure caused by differences in variable order in linear constraints. However, these changes do not affect the selected tile set, and the same data flow graph is obtained after abstraction.

In the final step of the algorithm, we proposed a novel variable ordering method to solve the sorting confusion issue when multiple variables are introduced to a linear constraint. Experimental results demonstrate that our algorithm is capable of correctly identifying these variables and produces a variable mapping sequence that conforms to the definition.

After the abstraction of the data flow graph, the splitting and merging of linear constraints can lead to changes in the order of addition in the summation chain. However, this issue is resolved. When equivalent R1CS constraint groups are created through the merging and splitting of constraints, the only discrepancy in the resulting data flow graphs is with regards to the vertices representing intermediate variables. These vertices can either represent existing variables or intermediate variables introduced during the data flow graph’s creation. Nevertheless, the structure of the data flow graph remains unaffected.