{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T06:27:13Z","timestamp":1761719233396,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T00:00:00Z","timestamp":1693353600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,8,30]]},"abstract":"<jats:p>We introduce Lurk, a new LISP-based programming language for zk-SNARKs. Traditional approaches to programming over zero-knowledge proofs require compiling the desired computation into a flat circuit, imposing serious constraints on the size and complexity of computations that can be achieved in practice. Lurk programs are instead provided as data to the universal Lurk interpreter circuit, allowing the resulting language to be Turing-complete without compromising the size of the resulting proof artifacts. Our work describes the design and theory behind Lurk, along with detailing how its implementation of content addressing can be used to sidestep many of the usual concerns of programming zero-knowledge proofs.<\/jats:p>","DOI":"10.1145\/3607839","type":"journal-article","created":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T17:40:31Z","timestamp":1693503631000},"page":"259-274","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["LURK: Lambda, the Ultimate Recursive Knowledge (Experience Report)"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0830-7248","authenticated-orcid":false,"given":"Nada","family":"Amin","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6945-2090","authenticated-orcid":false,"given":"John","family":"Burnham","sequence":"additional","affiliation":[{"name":"Lurk Lab, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6991-2011","authenticated-orcid":false,"given":"Fran\u00e7ois","family":"Garillot","sequence":"additional","affiliation":[{"name":"Lurk Lab, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3297-3750","authenticated-orcid":false,"given":"Rosario","family":"Gennaro","sequence":"additional","affiliation":[{"name":"City College of New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4389-6488","authenticated-orcid":false,"given":"Chhi\u2019m\u00e8d","family":"K\u00fcnzang","sequence":"additional","affiliation":[{"name":"Lurk Lab, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6180-4323","authenticated-orcid":false,"given":"Daniel","family":"Rogozin","sequence":"additional","affiliation":[{"name":"University College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7496-3964","authenticated-orcid":false,"given":"Cameron","family":"Wong","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.7146\/brics.v10i14.21784"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609619"},{"key":"e_1_2_1_3_1","unstructured":"Jean-Philippe Aumasson. 2022. The Security of ZKP projects: same but different. ZK Summit 7 workshop. https:\/\/www.aumasson.jp\/data\/talks\/zksec_zk7.pdf"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2022.3232813"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44381-1_16"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 23rd USENIX Conference on Security Symposium (SEC\u201914)","author":"Ben-Sasson Eli","year":"2014","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2014. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. In Proceedings of the 23rd USENIX Conference on Security Symposium (SEC\u201914). USENIX Association, USA. 781\u2013796. isbn:978-1-931971-15-7"},{"key":"e_1_2_1_7_1","volume-title":"2nd ZKProof Workshop. https:\/\/docs.zkproof.org\/pages\/standards\/accepted-workshop2\/proposal\u2013zk-interop-zkinterface.pdf","author":"Benarroch Daniel","year":"2019","unstructured":"Daniel Benarroch, Kobi Gurkan, Ron Kahat, Aur\u00e9lien Nicolas, and Eran Tromer. 2019. zkInterface, a Standard Tool for Zero-Knowledge Interoperability. In 2nd ZKProof Workshop. https:\/\/docs.zkproof.org\/pages\/standards\/accepted-workshop2\/proposal\u2013zk-interop-zkinterface.pdf"},{"key":"e_1_2_1_8_1","unstructured":"Dan Boneh Wilson Nguyen and Alex Ozdemir. 2021. Efficient Functional Commitments: How to Commit to a Private Function. Cryptology ePrint Archive Paper 2021\/1342. https:\/\/eprint.iacr.org\/2021\/1342"},{"key":"e_1_2_1_9_1","volume-title":"Mina: Decentralized Cryptocurrency at Scale.","author":"Bonneau Joseph","year":"2021","unstructured":"Joseph Bonneau, Izaak Meckler, and Vanishree Rao. 2021. Mina: Decentralized Cryptocurrency at Scale."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00050"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64378-2_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_26"},{"volume-title":"Innovations in Computer Science","author":"Chiesa Alessandro","key":"e_1_2_1_14_1","unstructured":"Alessandro Chiesa and Eran Tromer. 2010. Proof-Carrying Data and Hearsay Arguments from Signature Cards. In Innovations in Computer Science. Tsinghua University, Beijing, China. 310\u2013331."},{"key":"e_1_2_1_15_1","volume-title":"Zero-Knowledge Applications. In 4th ZKProof Workshop. https:\/\/eprint.iacr.org\/2021\/651","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. In 4th ZKProof Workshop. https:\/\/eprint.iacr.org\/2021\/651.pdf"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411203.1411206"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79876-5_37"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/Cybermatics_2018.2018.00199"},{"key":"e_1_2_1_19_1","volume-title":"Robert Bruce Findler, and Matthew Flatt","author":"Felleisen Matthias","year":"2009","unstructured":"Matthias Felleisen, Robert Bruce Findler, and Matthew Flatt. 2009. Semantics Engineering with PLT Redex. MIT Press. isbn:978-0-262-25817-3"},{"volume-title":"Proceedings of The Conference on Formal Description of Programming Concepts","author":"Felleisen Matthias","key":"e_1_2_1_20_1","unstructured":"Matthias Felleisen and Daniel P. Friedman. 1986. Control Operators, the SECD-machine, and the \u03bb -Calculus. In Proceedings of The Conference on Formal Description of Programming Concepts. Ebberup, Denmark."},{"key":"e_1_2_1_21_1","first-page":"2018","volume-title":"Blockchain Protocol Analysis and Security Engineering","author":"Fisch Ben","year":"2018","unstructured":"Ben Fisch, Joseph Bonneau, Juan Benet, and Nicola Greco. 2018. Proofs of replication using depth robust graphs. Blockchain Protocol Analysis and Security Engineering, 2018 (2018)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-18283-9_10"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"e_1_2_1_24_1","unstructured":"Alex Gluchowski. 2021. Introducing zkSync. https:\/\/blog.matter-labs.io\/introducing-zk-sync-the-missing-link-to-mass-adoption-of-ethereum-14c9cea83f58"},{"volume-title":"Monocopy and Associative Algorithms in an Extended LISP","author":"Goto Eiichi","key":"e_1_2_1_25_1","unstructured":"Eiichi Goto. 1974. Monocopy and Associative Algorithms in an Extended LISP. Tokyo, University of."},{"key":"e_1_2_1_26_1","volume-title":"POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems. In 30th Usenix Security Symposium. Virtual.","author":"Grassi Lorenzo","year":"2021","unstructured":"Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. 2021. POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems. In 30th Usenix Security Symposium. Virtual."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/800068.802129"},{"key":"e_1_2_1_29_1","volume-title":"Natural Semantics. In Symposium on Theoretical Aspects of Computer Science.","author":"Kahn Gilles","year":"1987","unstructured":"Gilles Kahn. 1987. Natural Semantics. In Symposium on Theoretical Aspects of Computer Science."},{"key":"e_1_2_1_30_1","unstructured":"Abhiram Kothapalli and Srinath Setty. 2022. SuperNova: Proving Universal Machine Executions without Universal Circuits. Cryptology ePrint Archive Paper 2022\/1758. https:\/\/eprint.iacr.org\/2022\/1758.pdf"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15985-5_13"},{"key":"e_1_2_1_32_1","volume-title":"43rd International Colloquium on Automata, Languages and Programming (ICALP","author":"Libert Beno\u00eet","year":"2016","unstructured":"Beno\u00eet Libert, Somindu C. Ramanna, and Moti Yung. 2016. Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions. In 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/367177.367199"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46214.2022.9833782"},{"key":"e_1_2_1_35_1","volume-title":"A structural approach to operational semantics. J. Log. Algebraic Methods Program., 60-61","author":"Plotkin Gordon D.","year":"2004","unstructured":"Gordon D. Plotkin. 2004. A structural approach to operational semantics. J. Log. Algebraic Methods Program., 60-61 (2004), 17\u2013139."},{"key":"e_1_2_1_36_1","unstructured":"Polygon. 2022. Polygon zkEVM. https:\/\/polygon.technology\/solutions\/polygon-zkevm"},{"key":"e_1_2_1_37_1","unstructured":"Starkware. 2021. StarkNet. https:\/\/starkware.co\/starknet\/"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_5"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78524-8_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357179"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/582153.582179"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/567067.567086"},{"key":"e_1_2_1_43_1","unstructured":"Ye Zhang. 2019. Scroll Overview. https:\/\/scroll.io\/blog\/zkEVM"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607839","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3607839","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:06Z","timestamp":1750178226000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607839"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,30]]},"references-count":42,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2023,8,30]]}},"alternative-id":["10.1145\/3607839"],"URL":"https:\/\/doi.org\/10.1145\/3607839","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2023,8,30]]},"assertion":[{"value":"2023-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}