MicroNova: Folding-Based Arguments with Efficient (On-Chain) Verification

We describe the design and implementation of MicroNova, a folding-based recursive argument for producing proofs of incremental computations of the form $y=F^{(\ell)}(x)$, where $F$ is a possibly non-deterministic computation (encoded using a constraint system such as R1CS), $x$ is the initial input, $y$ is the output, and $\ell > 0$ The proof of an $e$-step computation is produced step-by-step such that the proof size nor the time to verify it depends on $e$. The proof at the final iteration is then compressed, to achieve further succinctness in terms of proof size and verification time. Compared to prior folding-based arguments, a distinguishing aspect of MicroNova is the concrete efficiency of the verifier-even in a resource-constrained environment such as Ethereum's blockchain. In particular, the compressed proof consists of O(log N) group elements and it can be verified with O(log N) group scalar multiplications and two pairing operations, where $N$ is the number of constraints for a single invocation of $F$ MicroNova requires a universal trusted setup and can employ any existing setup material created for the popular KZG univariate polynomial commitment scheme. Finally, we implement and experimentally evaluate MicroNova. We find that MicroNova's proofs can be efficiently verified on the Ethereum blockchain with ≈2.2M gas. Furthermore, MicroNova's prover incurs minimal overheads atop its baseline Nova's prover.