Paper 2023/1021

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

Logan Allen, Zorp
Brian Klatt, Zorp
Philip Quirk, Zorp
Yaseen Shaikh, Zorp

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.

Available format(s)
Cryptographic protocols
Publication info
Edenproof systemzero knowledgeSTARKzkSTARKfunctional programming
Contact author(s)
logan @ zorp io
brian @ zorp io
phil @ zorp io
yaseen @ zorp io
2023-07-03: approved
2023-06-30: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.