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
Edenproof systemzero knowledgeSTARKzkSTARKfunctional 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.