Cyclo: Lightweight Lattice-Based Folding via Partial Range Checks
摘要
Folding is a powerful technique for constructing efficient succinct proof systems, especially for computations that are expressed in a streaming fashion. In this work, we present Cyclo, a new lattice-based folding protocol that improves upon LatticeFold+ [Boneh and Chen ’25] in multiple dimensions and which incorporates, among others, the pay-per-bit techniques from Neo when folding constraints expressed over a field \(\mathbb {F}_q\) [Nguyen and Setty ’25]. Cyclo proposes a new framework for building lattice-based folding schemes that eliminates the need for norm checks on the accumulator by adopting an amortized norm-refreshing design, ensuring that the witness norm grows additively per round within a (generously) bounded number of folds. This design simplifies the protocol and reduces prover overhead. In particular, Cyclo only performs range checks on the input non-accumulated witness, and when applied to fold constraints over \(\mathbb {F}_q\) , it does not decompose any witnesses into low-norm chunks within the folding protocol itself. Cyclo, supporting a complete family of cyclotomic rings, combines two simple building blocks: an extension commitment that reduces the norm of the witness by decomposing it and recommitting, and an \(\ell _\infty \) range test via a sum-check protocol. We demonstrate, by proving communication and runtime estimates that the construction results in an efficient and proof-size-friendly folding scheme. We also establish an algebraic connection between \(\mathcal {R}_q\) and \(\mathbb {F}_q\) using the polynomial evaluation map, enabling efficient reduction from R1CS/CCS over \(\mathbb {F}_q\) to a linear relation over \(\mathcal {R}_q\) , providing a new and simpler formulation of the techniques in [Nguyen and Setty ’25]. In practical settings, Cyclo achieves succinct proof sizes on the order of 30 KB, improving by an order of magnitude over LatticeFold+. Our efficiency benchmarks indicate that our protocol also outperforms LatticeFold+ in practice.