Paper 2022/1758

SuperNova: Proving universal machine executions without universal circuits

Abhiram Kothapalli, Carnegie Mellon University
Srinath Setty, Microsoft Research
Abstract

This paper introduces SuperNova, a new recursive proof system for incrementally producing succinct proofs of correct execution of programs on a stateful machine with a particular instruction set (e.g., EVM, RISC-V). A distinguishing aspect of SuperNova is that the cost of proving a step of a program is proportional only to the size of the circuit representing the instruction invoked by the program step. This is a stark departure from prior works that employ universal circuits where the cost of proving a program step is proportional at least to the sum of sizes of circuits representing each supported instruction—even though a particular program step invokes only one of the supported instructions. Naturally, SuperNova can support a rich instruction set without affecting the per-step proving costs. SuperNova achieves its cost profile by building on Nova, a prior high-speed recursive proof system, and leveraging its internal building block, folding schemes, in a new manner. We formalize SuperNova’s approach as a way to realize non-uniform IVC, a generalization of IVC. Furthermore, SuperNova’s prover costs and the recursion overhead are the same as Nova’s, and in fact, SuperNova is equivalent to Nova for machines that support a single instruction.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
incrementally verifiable computationrecursive proof compositionzero-knowledge arguments
Contact author(s)
akothapa @ andrew cmu edu
srinath @ microsoft com
History
2022-12-27: approved
2022-12-22: received
See all versions
Short URL
https://ia.cr/2022/1758
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1758,
      author = {Abhiram Kothapalli and Srinath Setty},
      title = {SuperNova: Proving universal machine executions without universal circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1758},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1758}},
      url = {https://eprint.iacr.org/2022/1758}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.