Paper 2023/573

HyperNova: Recursive arguments for customizable constraint systems

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

This paper introduces HyperNova, a recursive argument for proving incremental computations whose steps are expressed with CCS (Setty et al. ePrint 2023/552), a customizable constraint system that simultaneously generalizes Plonkish, R1CS, and AIR without overheads. A distinguishing aspect of HyperNova is that the prover’s cost at each step is dominated by a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSM-based commitment scheme. To construct HyperNova, we generalize folding schemes (CRYPTO 22) to allow instances from two (potentially) different NP relations, that share a compatible structure, to be folded; we refer to this generalization as multi-folding schemes. Furthermore, we devise a public-coin multi-folding scheme for instances in CCS and linearized CCS (a variant of CCS that we introduce). This construction can be viewed as an "early stopping" version of Spartan (CRYPTO 20), applied to a carefully-crafted polynomial that includes claims about prior linearized CCS instances. The prover’s work in the multi-folding scheme is a linear number of finite field operations and the verifier’s work is a logarithmic number of finite field operations and a single group scalar multiplication. We then construct incrementally verifiable computation (IVC) from non-interactive multi-folding schemes with the lowest prover costs. We also provide an alternate realization of HyperNova with a black box use of Nova, which nearly eliminates the need for deferred arithmetic when instantiated with a cycle of elliptic curves. As an additional contribution, we describe nlookup, a lookup argument, that is particularly suited for recursive arguments based on folding schemes. Specifically, at a particular step in an incremental computation, for m lookups into a table of size $n$ $(m << n)$, the prover’s work is dominated by $O(n)$ finite field operations and it requires only $O(m \cdot \log{n})$ degree-2 constraints and $O(\log{n})$ hash evaluations in the incremental computation. nlookup is currently not suitable for efficiently encoding bitwise operations, but it provides a powerful tool for efficiently encoding (large) finite state machines and proving their transitions with recursive arguments.

Note: Fix typos.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
succinct argumentscustomizable constraintsrecursive argumentsfolding schemes
Contact author(s)
akothapalli @ cmu edu
srinath @ microsoft com
History
2023-08-04: revised
2023-04-23: received
See all versions
Short URL
https://ia.cr/2023/573
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/573,
      author = {Abhiram Kothapalli and Srinath Setty},
      title = {HyperNova: Recursive arguments for customizable constraint systems},
      howpublished = {Cryptology ePrint Archive, Paper 2023/573},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/573}},
      url = {https://eprint.iacr.org/2023/573}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.