IACR News item: 24 April 2023
Abhiram Kothapalli, Srinath Setty
ePrint Report
This paper introduces HyperNova, a recursive argument for proving incremental computations whose steps are expressed with CCS (Setty et al. ePrint 2023), 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 the same 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 and the lowest recursion overheads in the literature. 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 SNARKs.
To construct HyperNova, we generalize folding schemes (CRYPTO 22), to allow instances from two (potentially) different NP relations, that share the same 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 and the lowest recursion overheads in the literature. 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 SNARKs.
Additional news items may be found on the IACR news page.