Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
Abhiram Kothapalli
Abstract:
Zero-knowledge proofs are a powerful cryptographic technique for demonstrating the correctness of computations without revealing any secret inputs. Modern applications are beginning to employ recursive zero-knowledge proofs (proofs that demonstrate the existence of other proofs) due to their distinct ability to prove stateful computations with dynamic control flow. For instance, one can prove large statements such as “the current state of the blockchain is valid” by proving that “there exists a proof for the previous state of the blockchain and the most recent update is valid”. Recursive proofs can similarly be utilized to incrementally prove the correct execution of delay functions, virtual machines, transparency dictionaries, and distributed computations.
In this talk, I will present Nova, a built zero-knowledge recursive proof system that marks the latest development in a growing line of work that brings recursive proofs significantly closer to practice. Nova achieves the smallest recursion overhead (i.e., additional “glue” computation proven in each recursive step) and the most efficient prover in the literature. Moreover, Nova features the smallest proof size and verifier runtime, both of which are independent of the recursion depth.
Underlying Nova’s efficiency results is a new construction, which we refer to as a folding scheme, that efficiently reduces the task of checking two NP instances into the task of checking a single NP instance of the same size. We show how folding schemes can be used to fully defer the task of checking all intermediate recursive proofs into a single succinct proof.