Paper 2023/1192
CycleFold: Foldingschemebased recursive arguments over a cycle of elliptic curves
Abstract
This paper introduces CycleFold, a new and conceptually simple approach to instantiate foldingschemebased recursive arguments over a cycle of elliptic curves, for the purpose of realizing incrementally verifiable computation (IVC). Existing approach to solve this problem originates from BCTV (CRYPTO'14) who describe their approach for a SNARKbased recursive argument, and it was adapted by Nova (CRYPTO'22) to a foldingschemebased recursive argument. A downside of this approach is that it represents a folding scheme verifier as a circuit on both curves in the cycle. (e.g., with Nova, this requires $\approx$10,000 multiplication gates on both curves in the cycle). CycleFold’s starting point is the observation that foldingschemebased recursive arguments can be efficiently instantiated without a cycle of elliptic curves—except for a few scalar multiplications in their verifiers (2 in Nova, 1 in HyperNova, and 3 in ProtoStar). Accordingly, CycleFold uses the second curve in the cycle to merely represent a single scalar multiplication ($\approx$1,0001,500 multiplication gates). CycleFold then folds invocations of that tiny circuit on the first curve in the cycle. This is nearly an order of magnitude improvement over the prior stateoftheart in terms of circuit sizes on the second curve. CycleFold is particularly beneficial when instantiating foldingschemebased recursive arguments over “half pairing” cycles (e.g., BN254/Grumpkin) as it keeps the circuit on the nonpairingfriendly curve minimal. The running instance in a CycleFoldbased recursive argument consists of an instance on the first curve and a tiny instance on the second curve. Both instances can be proven using a zkSNARK defined over the scalar field of the first curve. On the conceptual front, with CycleFold, an IVC construction and nor its security proof has to explicitly reason about the cycle of elliptic curves. Finally, due to its simplicity, CycleFoldbased recursive argument can be more easily be adapted to support parallel proving with the socalled "binary tree" IVC.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 succinct argumentsrecursive argumentscycles of elliptic curves
 Contact author(s)

akothapalli @ cmu edu
srinath @ microsoft com  History
 20230807: approved
 20230804: received
 See all versions
 Short URL
 https://ia.cr/2023/1192
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1192, author = {Abhiram Kothapalli and Srinath Setty}, title = {{CycleFold}: Foldingschemebased recursive arguments over a cycle of elliptic curves}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1192}, year = {2023}, url = {https://eprint.iacr.org/2023/1192} }