EDEN - a practical, SNARK-friendly combinator VM and ISA

Logan Allen; Brian Klatt; Philip Quirk; Yaseen Shaikh

Paper 2023/1021

EDEN - a practical, SNARK-friendly combinator VM and ISA

Logan Allen, Zorp

Brian Klatt, Zorp

Philip Quirk, Zorp

Yaseen Shaikh, Zorp

Abstract

Succinct Non-interactive Arguments of Knowledge (SNARKs) enable a party to cryptographically prove a statement regarding a computation to another party that has constrained resources. Practical use of SNARKs often involves a Zero-Knowledge Virtual Machine (zkVM) that receives an input program and input data, then generates a SNARK proof of the correct execution of the input program. Most zkVMs emulate the von Neumann architecture and must prove relations between a program's execution and its use of Random Access Memory. However, there are conceptually simpler models of computation that are naturally modeled in a SNARK yet are still practical for use. Nock is a minimal, homoiconic combinator function, a Turing-complete instruction set that is practical for general computation, and is notable for its use in Urbit. We introduce Eden, an Efficient Dyck Encoding of Nock that serves as a practical, SNARK-friendly combinator function and instruction set architecture. We describe arithmetization techniques and polynomial equations used to represent the Eden ISA in an Interactive Oracle Proof. Eden provides the ability to prove statements regarding the execution of any program that compiles down to the Eden ISA. We present the Eden zkVM, a particular instantiation of Eden as a zk-STARK.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Eden proof system zero knowledge STARK zkSTARK functional programming
Contact author(s): logan @ zorp io
brian @ zorp io
phil @ zorp io
yaseen @ zorp io
History: 2023-07-03: approved; 2023-06-30: received; See all versions
Short URL: https://ia.cr/2023/1021
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1021,
      author = {Logan Allen and Brian Klatt and Philip Quirk and Yaseen Shaikh},
      title = {{EDEN} - a practical, {SNARK}-friendly combinator {VM} and {ISA}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1021},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1021}
}