Data-Flow-Based Normalization Generation Algorithm of R1CS: Conclusion & References

Table of Links

Abstract & Introduction

Preliminaries

Normalization Algorithm

Evaluation

Conclusion & References

V. CONCLUSION

In this paper, we propose an algorithm based on data flow analysis to construct a paradigm for R1CS. The correctness and equivalence of R1CS have long been challenging to study due to the diversity and flexibility of constraint construction methods. Our algorithm aims to eliminate the differences between equivalent R1CS constraint systems through a series of abstraction processes. We introduce ordering methods for internal variables and constraints in R1CS, which provide reference information for the final paradigm generation. Through experimental results, we demonstrate that our algorithm can identify equivalent R1CS resulting from constraint merging, intermediate variable selection, and variable and constraint reordering, and transform them into a unique paradigm. Therefore, R1CS plays an indispensable part in zk-SNARKS. Further work includes establishing rules for merging constraints and a more comprehensive benchmark. This requires us to conduct more in-depth research and exploration of the generation rules of R1CS to improve the algorithm.

REFERENCES

[1] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof-systems,” in Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019, pp. 203–225.

[2] Zcash company, https://z.cash/, 2014.

[3] E. B. Sasson, A. Chiesa, C. Garman, et al., “Zerocash: Decentralized anonymous payments from bitcoin,” in 2014 IEEE symposium on security and privacy, IEEE, 2014, pp. 459–474.

[4] G. Drevon, J-r1cs – a json lines format for r1cs, 2019.

[5] E. Albert, M. Belles-Mu ´ noz, M. Isabel, C. Rodrı ˜ eguez- ´ Nu´nez, and A. Rubio, “Distilling constraints in zero- ˜ knowledge protocols,” in Computer Aided Verification: 34th International Conference, CAV 2022, Haifa, Israel, August 7–10, 2022, Proceedings, Part I, Springer, 2022, pp. 430–443.

[6] E. Ben-Sasson, A. Chiesa, M. Riabzev, N. Spooner, M. Virza, and N. P. Ward, “Aurora: Transparent succinct arguments for r1cs,” in Advances in Cryptology– EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part I 38, Springer, 2019, pp. 103–128.

[7] J. Lee, S. Setty, J. Thaler, and R. Wahby, “Lineartime and post-quantum zero-knowledge snarks for r1cs,” Cryptology ePrint Archive, 2021.

[8] A. Golovnev, J. Lee, S. Setty, J. Thaler, and R. S. Wahby, “Brakedown: Linear-time and post-quantum snarks for r1cs,” Cryptology ePrint Archive, 2021.

[9] Y. Muzi, F. Muyue, B. Gu, et al., Semantic comparison method and device between a kind of source code and binary code, 2019.

[10] G. Li, L. Zhongqi, Y. Dongsheng, and Y. Liu, Compiling method from intermediate language (il) program to c language program of instruction list, 2013.

[11] Z. Yongsheng, C. Zhiyong, C. Rongtao, and W. Zhili, A kind of assembly language is to the code conversion method of higher level language and device, 2015.

[12] E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza, “Succinct {non-interactive} zero knowledge for a von neumann architecture,” in 23rd USENIX Security Symposium (USENIX Security 14), 2014, pp. 781–796.

[13] V. Buterin, “Quadratic arithmetic programs: From zero to hero,” URl: https://medium. com/@ VitalikButerin/quadratic-arithmetic-programs-fromzero-to-hero-f6d558cea649, 2016.

[14] H. Vollmer, Introduction to circuit complexity: a uniform approach. Springer Science & Business Media, 1999.

[15] J. Groth, “On the size of pairing-based non-interactive arguments,” in Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35, Springer, 2016, pp. 305–326.

[16] J. B. Dennis, “First version of a data flow procedure language,” in Programming Symposium: Proceedings, Colloque sur la Programmation Paris, April 9–11, 1974, Springer, 2005, pp. 362–376.

[17] P. C. Treleaven, D. R. Brownbridge, and R. P. Hopkins, “Data-driven and demand-driven computer architecture,” ACM Computing Surveys (CSUR), vol. 14, no. 1, pp. 93–143, 1982.

[18] W. Xing and A. Ghorbani, “Weighted pagerank algorithm,” in Proceedings. Second Annual Conference on Communication Networks and Services Research, 2004., IEEE, 2004, pp. 305–314.

[19] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bring order to the web,” Technical report, stanford University, Tech. Rep., 1998.