Paper 2025/1905

Symphony: Scalable SNARKs in the Random Oracle Model from Lattice-Based High-Arity Folding

Abstract

Folding/Accumulation schemes are a powerful tool for building scalable proof systems. However, standard approaches for leveraging folding schemes, such as IVCs or PCDs, require embedding hash functions (modeled as random oracles) into recursive circuits, introducing both security concerns and significant proving overhead. We re-envision how to use folding schemes, and introduce Symphony, the first proving paradigm that leverages folding schemes as a black box without embedding hashes in SNARK circuits. It is memory-efficient, parallelizable, and plausibly post-quantum secure, with polylogarithmic proof size and verification. The (low-memory) prover requires O(log log n) passes of the input data and its computation is dominated by committing to the input witnesses. A core component of our construction is a new lattice-based folding scheme that compresses a large number of NP-complete statements into one in a single shot. Furthermore, we design a generic compiler that converts a folding scheme into a SNARK without embedding the Fiat-Shamir circuit into proven statements. Our evaluation shows its concrete efficiency, making Symphony fit for large-scale applications such as zkVM and verifiable machine learning.

Note: Major revision of Section 1 and Section 3.4