Paper 2023/1579

KiloNova: Preprocessing Folding-based SNARKs for Machine Executions

Abstract

Succinct non-interactive arguments of knowledge have enabled efficient verification of complex computations, but practical applications such as zero-knowledge virtual machines face scalability challenges due to rapidly growing circuit sizes. While folding-based incrementally verifiable computation and proof-carrying data frameworks offer improved performance, existing constructions struggle to efficiently support non-uniform circuits. In this work, we present KiloNova, a preprocessing recursive SNARK for universal machine execution. KiloNova introduces a novel holographic folding scheme that enables efficient folding across multiple high-degree relations with non-uniform indices, achieving both asymptotic and concrete efficiency. Building on this, we construct a multi-predicate PCD system in which the prover maintains constant-size intermediate instances, thereby significantly reducing recursion overhead and memory usage. Finally, we instantiate KiloNova as a preprocessing SNARK by compiling the PCD proof with corresponding polynomial commitment schemes. Theoretical analysis and experimental results show that KiloNova achieves state-of-the-art performance in multi-predicate settings and therefore provides a scalable, practical foundation for zero-knowledge proofs in real-world applications.