{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:21:04Z","timestamp":1773246064685,"version":"3.50.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031131844","type":"print"},{"value":"9783031131851","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,7]],"date-time":"2022-08-07T00:00:00Z","timestamp":1659830400000},"content-version":"vor","delay-in-days":218,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The most widely used <jats:italic>Zero-Knowledge<\/jats:italic> (ZK) protocols require provers to prove they know a solution to a computational problem expressed as a <jats:italic>Rank-1 Constraint System<\/jats:italic> (R1CS). An R1CS is essentially a system of non-linear arithmetic constraints over a set of signals, whose security level depends on its non-linear part only, as the linear (additive) constraints can be easily solved by an attacker. Distilling the essential constraints from an R1CS by removing the part that does not contribute to its security is important, not only to reduce costs (time and space) of producing the ZK proofs, but also to reveal to cryptographic programmers the real hardness of their proofs. In this paper, we formulate the problem of distilling constraints from an R1CS as the (hard) problem of simplifying constraints in the realm of non-linearity. To the best of our knowledge, it is the first time that constraint-based techniques developed in the context of formal methods are applied to the challenging problem of analysing and optimizing ZK protocols.<\/jats:p>","DOI":"10.1007\/978-3-031-13185-1_21","type":"book-chapter","created":{"date-parts":[[2022,8,6]],"date-time":"2022-08-06T19:29:09Z","timestamp":1659814149000},"page":"430-443","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Distilling Constraints in\u00a0Zero-Knowledge Protocols"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0048-0705","authenticated-orcid":false,"given":"Elvira","family":"Albert","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5278-4252","authenticated-orcid":false,"given":"Marta","family":"Bell\u00e9s-Mu\u00f1oz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5474-9258","authenticated-orcid":false,"given":"Miguel","family":"Isabel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5417-8934","authenticated-orcid":false,"given":"Clara","family":"Rodr\u00edguez-N\u00fa\u00f1ez","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0501-9830","authenticated-orcid":false,"given":"Albert","family":"Rubio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,7]]},"reference":[{"key":"21_CR1","unstructured":"Albert, E., Bell\u00e9s-Mu\u00f1oz, M., Isabel, M., Rodr\u00edguez-N\u00fa\u00f1ez, C., Rubio, A.: circom fork including non-linear simplification. GitHub (2022). github.com\/clararod9\/circom. Accessed 21 Jan 2022"},{"key":"21_CR2","unstructured":"Albert, E., Bell\u00e9s-Mu\u00f1oz, M., Isabel, M., Rodr\u00edguez-N\u00fa\u00f1ez, C., Rubio, A.: An optimizer for non-linear constraints. GitHub (2022). github.com\/miguelis\/nonlinearoptimizer. Accessed 21 Jan 2022"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Bell\u00e9s-Mu\u00f1oz, M., Whitehat, B., Baylina, J., Daza, V., Tapia, J.L.M.: Twisted edwards elliptic curves for zero-knowledge circuits. Mathematics, 9(23), 2021","DOI":"10.3390\/math9233022"},{"key":"21_CR4","unstructured":"Sasson, E.B., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 459\u2013474 (2014)"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-40084-1_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"E Ben-Sasson","year":"2013","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 90\u2013108. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40084-1_6"},{"key":"21_CR6","unstructured":"Benarroch, D., Gurkan, K., Kahat, R., Nicolas, A., Tromer, E.: zkInterface, a standard tool for zero-knowledge interoperability, June 2019. github.com\/QED-it\/zkinterface\/blob\/master\/zkInterface.pdf. Accessed 15 Jan 2022"},{"key":"21_CR7","unstructured":"Bowe, S.: Bellman: zk-snark library. github.com\/ebfull\/bellman. Accessed 15 Jan 2022"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"B\u00fcnz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 315\u2013334 (2018)","DOI":"10.1109\/SP.2018.00020"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-319-41591-8_24","volume-title":"Software Engineering and Formal Methods","author":"A Champion","year":"2016","unstructured":"Champion, A., Gurfinkel, A., Kahsai, T., Tinelli, C.: CoCoSpec: a mode-aware contract language for reactive systems. In: De Nicola, R., K\u00fchn, E. (eds.) SEFM 2016. LNCS, vol. 9763, pp. 347\u2013366. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-41591-8_24"},{"key":"21_CR10","unstructured":"Chin, C., Wu, H., Chu, R., Coglio, A., McCarthy, E., Smith, E.: Leo: a programming language for formally verified, zero-knowledge applications. IACR Cryptology ePrint Archive, Report 2021\/651 (2021). ia.cr\/2021\/651. Accessed 15 Jan 2022"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Cimatti, A., Griggio, A., Irfan, A., Roveri, M., Sebastiani, R.: Incremental linearization for satisfiability and verification modulo nonlinear arithmetic and transcendental functions. ACM Trans. Comput. Log., 19(3), 19:1\u201319:52 (2018)","DOI":"10.1145\/3230639"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Eberhardt, J., Tai, S.: ZoKrates - scalable privacy-preserving off-chain computations. In: 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), pp. 1084\u20131091 (2018)","DOI":"10.1109\/Cybermatics_2018.2018.00199"},{"key":"21_CR13","unstructured":"Gabizon, A., Williamson, Z.J.: Plookup: a simplified polynomial protocol for lookup. IACR Cryptology ePrint Archive, Report 2020\/315 (2020). ia.cr\/2020\/315. Accessed 15 Dec 2021"},{"key":"21_CR14","unstructured":"Gabizon, A., Williamson, Z.J., Ciobotaru, O.: Plonk: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Paper 2019\/953 (2019). eprint.iacr.org\/2019\/953"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC \u201985, pp. 291\u2013304, New York, NY, USA (1985). Association for Computing Machinery","DOI":"10.1145\/22145.22178"},{"key":"21_CR16","unstructured":"Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: a new hash function for zero-knowledge proof systems. IACR Cryptology ePrint Archive, Report 2019\/458, 2019. ia.cr\/2019\/458. Accessed 15 Dec 2021"},{"key":"21_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Groth","year":"2016","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305\u2013326. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_11"},{"key":"21_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-030-51280-4_12","volume-title":"Financial Cryptography and Data Security","author":"L Gudgeon","year":"2020","unstructured":"Gudgeon, L., Moreno-Sanchez, P., Roos, S., McCorry, P., Gervais, A.: SoK: layer-two blockchain protocols. In: Bonneau, J., Heninger, N. (eds.) FC 2020. LNCS, vol. 12059, pp. 201\u2013226. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51280-4_12"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Handschuh, H.: SHA Family (Secure Hash Algorithm), pp. 565\u2013567. Springer, US, Boston, MA (2005)","DOI":"10.1007\/0-387-23483-7_388"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Hermez Network. Hermez whitepaper, October 2020. hermez.io\/hermez-whitepaper.pdf. Accessed 15 Dec 2021","DOI":"10.1155\/2021\/9914982"},{"key":"21_CR21","unstructured":"Iden3. Circom: Circuit compiler for zero-knowledge proofs. GitHub (2020). ithub.com\/iden3\/circom. Accessed 21 Jan 2022"},{"key":"21_CR22","unstructured":"Iden3. Circomlib: Library of circom templates. GitHub (2020). github.com\/iden3\/circomlib. Accessed 15 Dec 2021"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Kosba, A., Papamanthou, C., Shi, E.: xJsnark: a framework for efficient verifiable computation. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 944\u2013961 (2018)","DOI":"10.1109\/SP.2018.00018"},{"key":"21_CR24","unstructured":"Matter Labs. Zinc v0.2.3. Cryptology ePrint Archive, Report 2019\/953 (2019). ia.cr\/2020\/352. Accessed 15 Dec 2021"},{"key":"21_CR25","doi-asserted-by":"crossref","unstructured":"Nakos, G.C., Turner, P.R., Williams, R.M.: Fraction-free algorithms for linear and polynomial equations. SIGSAM Bull. 31(3), 11\u201319 (1997)","DOI":"10.1145\/271130.271133"},{"key":"21_CR26","unstructured":"Ozdemir, A., Brown, F., Wahby, R.S.: Unifying compilers for snarks, smt, and more. IACR Cryptology ePrint Archive, Report 2020\/1586, 2020. ia.cr\/2020\/1586. Accessed 15 Jan 2022"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 238\u2013252. IEEE, May 2013","DOI":"10.1109\/SP.2013.47"},{"key":"21_CR28","unstructured":"Protocol, M., Snarky. GitHub (2020). minaprotocol.com\/blog\/snarky-a-high-level-language-for-verifiable-computation. Accessed 21 Jan 2022"},{"key":"21_CR29","unstructured":"Succinct Computational Integrity and Privacy Research (SCIPR) Lab. libsnark: a c++ library for zk-snark proofs. GitHub, First release, June 2014. github.com\/scipr-lab\/libsnark. Accessed 15 Jan 2022"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-13185-1_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,3]],"date-time":"2022-11-03T17:14:20Z","timestamp":1667495660000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-13185-1_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031131844","9783031131851"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-13185-1_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"7 August 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CAV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computer Aided Verification","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Haifa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Israel","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"34","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cav2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/i-cav.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"209","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.9","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}