Nova

Nova's core innovation is the folding scheme, a cryptographic method that reduces the task of checking two instances of a constraint system into checking a single instance. Instead of verifying each step of a computation separately, Nova folds multiple steps together, amortizing the cost of expensive operations like polynomial commitments. This allows the prover to defer heavy cryptographic work to the final step, dramatically accelerating incremental computation.

Nova implements IVC, a paradigm where a prover updates a proof after each step of a long-running computation. The key property: proof size and verification time remain constant regardless of the total number of steps executed. This is achieved by recursively folding each new step's witness into an accumulated instance, producing a single succinct proof at the end. Ideal for verifiable ML training loops and blockchain state transitions.

Unlike Groth16 and other pairing-based zkSNARKs, Nova operates with a transparent setup. It relies on collision-resistant hash functions rather than a structured common reference string generated through a multi-party ceremony. This eliminates the toxic waste security risk and makes Nova suitable for decentralized applications where a trusted setup ceremony is impractical or undesirable.

Nova generalizes the standard Rank-1 Constraint System (R1CS) into a relaxed R1CS that introduces a slack variable. This relaxation is what enables folding: two relaxed R1CS instances can be combined into one, whereas standard R1CS instances cannot be directly folded. The prover works with this relaxed system throughout the computation, only resolving to a strict R1CS at the final verification step.

Nova's prover is dominated by O(C) group operations where C is the circuit size, avoiding the expensive polynomial commitments and Fast Fourier Transforms that bottleneck other systems. Key performance characteristics:

• Linear prover time in the circuit size per step
• No FFTs required during proving
• Constant-size proofs after recursive composition
• Suitable for large circuits where other provers become prohibitively slow

Nova is particularly well-suited for zero-knowledge machine learning (zkML) workloads where computations span thousands of sequential steps. Use cases include:

• Verifiable inference: Prove a model's prediction is correct without revealing weights
• Training integrity: Attest that a model was trained on a specific dataset
• Recursive neural network verification: Handle sequential architectures efficiently
• Federated learning audits: Prove correct aggregation of model updates

Nova operates on a relaxed version of the Rank-1 Constraint System. Standard R1CS requires exact equality: A·z ∘ B·z = C·z. Nova introduces a slack term u and an error vector E, transforming the relation into A·z ∘ B·z = u·C·z + E. This relaxation is what enables folding: two relaxed instances can be combined into one without the prover needing to satisfy strict equality at every intermediate step. The error is eventually eliminated in the final proof.

A key capability of Nova that distinguishes it from earlier folding schemes. Standard IVC applies the same function at each step. Nova supports non-uniform computation, where each step can execute a different function F_i. This is essential for zkML: a neural network's layers are not identical; a convolution layer differs from a ReLU activation. Nova can prove the sequential execution of heterogeneous operations without requiring a single monolithic circuit, dramatically simplifying circuit design for ML inference.