HyperNova: Recursive Arguments for Customizable Constraint Systems

We introduce HyperNova, a new 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. HyperNova makes four contributions, each resolving a major problem in the area of recursive arguments.

First, it provides a folding scheme for CCS where the prover's cryptographic cost is a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSMbased commitment scheme. The folding scheme can fold multiple instances at once, making it easier to build generalizations of IVC such as PCD. Second, when proving program executions on stateful machines (e.g., EVM, RISC-V), 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 ("a la carte" cost profile). Third, we show how to achieve zero-knowledge for "free" and without the need to employ zero-knowledge SNARKs. Fourth, we show how to efficiently instantiate HyperNova over a cycle of elliptic curves. For this, we provide a general technique, which we refer to as CycleFold, that applies to all modern folding-scheme-based recursive arguments. This is an extended version of a paper from CRYPTO 2024 [40]. Compared to an initial version, this version of the paper incorporates material from prior preprints [38,39]. Additionally, this version provides an approach to achieve zeroknowledge in folding-scheme-based recursive arguments without needing to use zk-SNARKs.

Given the high costs imposed by universal circuits, designers of these machines aim to employ a minimal instruction set, to keep the size of the universal circuit and thereby the cost of proving a program step minimal [6,4,31]. However, this is a not a panacea: for real applications, one needs to execute an enormous number of iterations of the minimal circuit (e.g., billions of iterations), making the prover's work largely untenable. This also means that emulating real programs that target existing virtual machines with rich instruction sets (e.g., EVM, RISC-V, Wasm) via a machine with a minimal instruction set would incur enormous costs.

An open question is whether one can achieve an "a la carte" cost profile, where the cost of proving a step of a program execution is proportional only to the size of the circuit representing the instruction invoked by the program step and independent of the circuit sizes of the uninvoked instructions.

(3) The need for providing zero-knowledge without needing zkSNARKs. Nova [41] shows how to efficiently achieve zero-knowledge for its IVC proofs by producing a zkSNARK proving the knowledge of valid IVC proofs. The zk-SNARK scheme that is natively compatible with Nova is Spartan [54], which internally uses the sum-check protocol [44]. The most efficient way to achieve zero-knowledge in Spartan is to use the Cramer-Damgard transformation [23,66], where sum-check messages are committed with homomorphic commitments (e.g., Pedersen) and the sum-check verifier's checks are proven in zero-knowledge using Schnorr-type proofs. This means that the Spartan verifier must perform public key operations (e.g., group scalar multiplications), which are far too expensive especially in blockchain settings where the verifier is deployed on-chain.

An open question is whether one can leverage folding schemes to "blind" the IVC proof such that one can use a non-zk Spartan, where the verifier verifies the sum-check messages in plaintext (which are orders of magnitude more efficient).