{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T08:16:01Z","timestamp":1776932161342,"version":"3.51.2"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T00:00:00Z","timestamp":1733356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61872232"],"award-info":[{"award-number":["61872232"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3665339","type":"journal-article","created":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T10:11:49Z","timestamp":1715940709000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["RNA: R1CS Normalization Algorithm Based on Data Flow Graphs for Zero-Knowledge Proofs"],"prefix":"10.1145","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-6699-2686","authenticated-orcid":false,"given":"Chenhao","family":"Shi","sequence":"first","affiliation":[{"name":"School of Software, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-2698-1836","authenticated-orcid":false,"given":"Ruibang","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Software, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3675-1344","authenticated-orcid":false,"given":"Hao","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Software, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9005-7112","authenticated-orcid":false,"given":"Guoqiang","family":"Li","sequence":"additional","affiliation":[{"name":"School of Software, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9411-6156","authenticated-orcid":false,"given":"Sinka","family":"Gao","sequence":"additional","affiliation":[{"name":"Delphinus Lab, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,5]]},"reference":[{"key":"e_1_3_2_2_1","unstructured":"2014. ZCash Company. Retrieved from https:\/\/z.cash\/"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/390013.808479"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/360018.360025"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3607839"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3545180"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-021-00558-z"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2022.3232813"},{"key":"e_1_3_2_9_1","first-page":"46","article-title":"Scalable, transparent, and post-quantum secure computational integrity","volume":"2018","author":"Ben-Sasson Eli","year":"2018","unstructured":"Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2018. Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptol. ePrint Arch. 2018 (2018), 46.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_10_1","first-page":"103","volume-title":"Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT \u20192019)","author":"Ben-Sasson Eli","year":"2019","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. 2019. Aurora: Transparent succinct arguments for R1CS. In Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT \u20192019). Springer, 103\u2013128."},{"key":"e_1_3_2_11_1","first-page":"1021","article-title":"Halo: Recursive proof composition without a trusted setup","volume":"2019","author":"Bowe Sean","year":"2019","unstructured":"Sean Bowe, Jack Grigg, and Daira Hopwood. 2019. Halo: Recursive proof composition without a trusted setup. IACR Cryptol. ePrint Arch. 2019 (2019), 1021.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_12_1","volume-title":"Quadratic Arithmetic Programs: From Zero to Hero","author":"Buterin Vitalik","year":"2016","unstructured":"Vitalik Buterin. 2016. Quadratic Arithmetic Programs: From Zero to Hero. Retrieved from https:\/\/medium.com\/@VitalikButerin\/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649"},{"key":"e_1_3_2_13_1","first-page":"651","article-title":"Leo: A programming language for formally verified, zero-knowledge applications","volume":"2021","author":"Chin Collin","year":"2021","unstructured":"Collin Chin, Howard Wu, Raymond Chu, Alessandro Coglio, Eric McCarthy, and Eric Smith. 2021. Leo: A programming language for formally verified, zero-knowledge applications. IACR Cryptol. ePrint Arch. 2021 (2021), 651. https:\/\/eprint.iacr.org\/2021\/651","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_14_1","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/3-540-06859-7_145","volume-title":"Programming Symposium: Proceedings, Colloque sur la Programmation Paris, April 9\u201311, 1974","author":"Dennis Jack B.","year":"1974","unstructured":"Jack B. Dennis. 1974. First version of a data flow procedure language. In Programming Symposium: Proceedings, Colloque sur la Programmation Paris, April 9\u201311, 1974, B. Robinet (Ed.). Springer, Berlin, 362\u2013376."},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/Cybermatics_2018.2018.00199"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484795"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/24039.24041"},{"key":"e_1_3_2_18_1","unstructured":"Li Gao Zhongqi Li Dongsheng Yang and Yinzhong Liu. 2013. Compiling method from intermediate Language (IL) Program to C Language Program of Instruction List. (2013). Patent No. CN103123590A."},{"key":"e_1_3_2_19_1","first-page":"1063","article-title":"Cairo\u2013a Turing-complete STARK-friendly CPU architecture","volume":"2021","author":"Goldberg Lior","year":"2021","unstructured":"Lior Goldberg, Shahar Papini, and Michael Riabzev. 2021. Cairo\u2013a Turing-complete STARK-friendly CPU architecture. IACR Cryptol. ePrint Arch. 2021 (2021), 1063.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_20_1","first-page":"203","volume-title":"Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali","author":"Goldwasser Shafi","year":"2019","unstructured":"Shafi Goldwasser, Silvio Micali, and Chales Rackoff. 2019. The knowledge complexity of interactive proof systems. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali. 203\u2013225."},{"key":"e_1_3_2_21_1","first-page":"1043","article-title":"Brakedown: Linear-time and post-quantum SNARKs for R1CS","author":"Golovnev Alexander","year":"2021","unstructured":"Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, and Riad S. Wahby. 2021. Brakedown: Linear-time and post-quantum SNARKs for R1CS. IACR Cryptol. ePrint Arch. (2021), 1043. https:\/\/eprint.iacr.org\/2021\/1043","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_22_1","first-page":"30","article-title":"Linear-time and post-quantum zero-knowledge SNARKs for R1CS","author":"Lee Jonathan","year":"2021","unstructured":"Jonathan Lee, Srinath Setty, Justin Thaler, and Riad Wahby. 2021. Linear-time and post-quantum zero-knowledge SNARKs for R1CS. IACR Cryptol. ePrint Arch. (2021), 30. https:\/\/eprint.iacr.org\/2021\/030","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3572782"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46214.2022.9833782"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.36"},{"key":"e_1_3_2_26_1","first-page":"191","volume-title":"Proceedings of the IEEE 28th Pacific Rim International Symposium on Dependable Computing (PRDC \u20192023)","author":"Shi Chenhao","year":"2023","unstructured":"Chenhao Shi, Hao Chen, Ruibang Liu, and Guoqiang Li. 2023. Data-flow-based normalization generation algorithm of R1CS for zero-knowledge proof. In Proceedings of the IEEE 28th Pacific Rim International Symposium on Dependable Computing (PRDC \u20192023). IEEE, 191\u2013197."},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/356869.356873"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"e_1_3_2_29_1","first-page":"190","article-title":"Practical security analysis of zero-knowledge proof circuits","volume":"2023","author":"Wen Hongbo","year":"2023","unstructured":"Hongbo Wen, Jon Stephens, Yanju Chen, Kostas Ferles, Shankara Pailoor, Kyle Charbonnet, Isil Dillig, and Yu Feng. 2023. Practical security analysis of zero-knowledge proof circuits. IACR Cryptol. ePrint Arch. 2023 (2023), 190.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_30_1","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1109\/DNSR.2004.1344743","volume-title":"Proceedings of the 2nd Annual Conference on Communication Networks and Services Research, 2004. (CNSR \u201904)","author":"Xing Wenpu","year":"2004","unstructured":"Wenpu Xing and Ali Ghorbani. 2004. Weighted PageRank algorithm. In Proceedings of the 2nd Annual Conference on Communication Networks and Services Research, 2004. (CNSR \u201904). IEEE, 305\u2013314."},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1768"},{"key":"e_1_3_2_32_1","unstructured":"Zimu Yuan Muyue Feng Gu Ban Yang Xiao Jiahuan Xu Chendong Yu Yi Huo and Wei Zou. 2019. Semantic comparison method and device between a Kind of source code and binary code. (2019). Patent No. CN110147235A."},{"key":"e_1_3_2_33_1","unstructured":"Yongsheng Zhao Zhiyong Chen Rongtao Cui and Zhili Wen. 2015. A kind of assembly language is to the code conversion method of higher level language and device. (2015). Patent No. CN102830975A."}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3665339","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3665339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:19Z","timestamp":1750291399000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3665339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,5]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3665339"],"URL":"https:\/\/doi.org\/10.1145\/3665339","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,5]]},"assertion":[{"value":"2023-12-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}