LURK: Lambda, the Ultimate Recursive Knowledge

Nada Amin; John Burnham; François Garillot; Rosario Gennaro; Chhi'mèd Künzang; Daniel Rogozin; Cameron Wong

Paper 2023/369

LURK: Lambda, the Ultimate Recursive Knowledge

Nada Amin, Harvard University

John Burnham, Lurk Lab

François Garillot, Lurk Lab

Rosario Gennaro, Protocol Labs

Chhi'mèd Künzang, Lurk Lab

Daniel Rogozin, University College London

Cameron Wong, Harvard University

Abstract

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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. ICFP 2023
DOI: 10.1145/3607839
Keywords: Lisp Rust
Contact author(s): namin @ seas harvard edu
john @ lurk-lab com
francois @ garillot net
rosario @ protocol ai
clkunzang @ lurk-lab com
d rogozin @ ucl ac uk
cwong @ g harvard edu
History: 2024-12-09: revised; 2023-03-14: received; See all versions
Short URL: https://ia.cr/2023/369
License: CC BY

BibTeX

@misc{cryptoeprint:2023/369,
      author = {Nada Amin and John Burnham and François Garillot and Rosario Gennaro and Chhi'mèd Künzang and Daniel Rogozin and Cameron Wong},
      title = {{LURK}: Lambda, the Ultimate Recursive Knowledge},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/369},
      year = {2023},
      doi = {10.1145/3607839},
      url = {https://eprint.iacr.org/2023/369}
}