Cycles of curves: what are they and do we need them?

The term 'cycles of elliptic curves' has been garnering significant attention recently. This surge in interest is largely due to their application in 'incremental verifiable computation', the folding scheme, and more broadly, SNARK recursion. Often, when a SNARK needs to self-verify, it is typically implemented as a cycle of elliptic curves.

Recent research has highlighted that incorrect implementation of cycles of curves can lead to substantial security implications. A blog post dissecting this work offers an analysis of an earlier implementation of the Nova proving system, specifically addressing its use of cycles of curves. It is worth noting that the identified bug has since been rectified.

At ICME, we're in the process of implementing SuperNova. In the current state of things, this means we're required to use the existing cycles of curves for performance optimization. Consequently, we're faced with the necessity of adding more code and more checks, essentially duplicating the same task across two circuits.

It is not only us — creators of a parallelizable Nova scheme called 'ParaNova' are noticing the same thing - check out their mirror image charts representing duplicated work across a cycle of curves. But even so, we cannot simply not use them: "Using an elliptic curve pair typically makes the IWPC (instance-witness-pair collection) 100-200x shorter than wrong-field arithmetic".

This leads us to the questions: What exactly are these 'cycles of curves'? And, can they ever be avoided in proof recursion?

Why we use cycles of curves.

Elliptic curves are commonly employed in zero-knowledge proof schemes. A 'base field' is where the curve is defined; in essence, the curve is a set of points within this base field, often denoted as 𝔽𝑞.

Typically, the curve has a prime number of points, referred to as 𝔽p or the 'scalar field', where 'p' is a large prime number. These prime-ordered elliptic curves have arithmetic defined within the scalar field. When we formulate circuits, we utilize this scalar field.

However, when we want to 'commit' to these values in 𝔽p, we end up with values in the base field, 𝔽𝑞. Subsequently, when we need to use these values, we encounter what is known as 'non-native arithmetic'. This is exceedingly costly to simulate in the original field.

Mitigation strategies in dealing with non-native arithmetic in Zero-Knowledge Proof (ZKP) systems generally focus on improving efficiency while maintaining the security of the system. There are a few key strategies which are common:

1. Lookup arguments: Another important strategy to mitigate non-native arithmetic involves the use of a large lookup table containing elliptic curve operations over a foreign field. This approach transforms the problem of performing non-native elliptic curve operations into performing native elliptic curve operations, thereby reducing the complexity of the task. (We will return to this point later.)
2. Weak prover - strong prover: This strategy seeks to defer as much  computation as possible from a weak prover to a stronger one without leaking information, thereby minimizing the computational load on the weak prover. i.e. Fold on the weak machine and do non-native heavy work on servers.
3. Range checks: This method simply ensures that the numbers we are working with do not exceed the prime number of our scalar field. If these numbers are constrained within a certain range, we can use them much as we would use integers.
4. Bignum techniques: In many cases, calculations do exceed mod p. We can break these numbers into "limbs" and verify each limb with range checks. We can perform a large number of these checks and also use techniques to ignore 'high limbs.'
5. Cycles of curves: This strategy is the central focus of this blog post..

Where did cycles come from and how do they work?

The earliest work on 'cycles of curves' started in 2014 with "Scalable Zero Knowledge via Cycles of Elliptic Curves" (BCTV14). Here the authors were interested in practical IVC (incremental verifiable computation). At the time IVC was not practical due to the very large computational costs of such systems. However, they realised by using cycles of curves they could make such a system of SNARK recussion work in an efficient manner.

The team at the Electric Coin Company (Zcash) created a highly popular proving system called Halo2. This system uses a cycles of curves for folding ('accumulating'), which is called the 'Pasta curves'. Daira from their team can be heard explaining in detail how cycles work and why they used them in Halo2: in this video.

*Daira appears a lot on talks and videos about cutting edge work.

Cycles of curves serve as a solution to the problem of non-native arithmetic by employing a pair of elliptic curves, each operating in a manner that the base field of one becomes the scalar field of the other. To put it simply, imagine we have two elliptic curves. The first curve has a base field 𝔽𝑞 and a scalar field 𝔽p. Conversely, the second curve's base field is 𝔽p and its scalar field is 𝔽𝑞.

This setup enables each curve to perform operations in its respective native field, thus addressing the problem of non-native arithmetic. It's akin to two interrelated systems working in tandem, wherein they pass values back and forth to each other. Each curve processes the values in its own native field, ensuring that each arithmetic operation is performed where it's native and thus most efficient. In essence, the complex task of non-native arithmetic is divided and conquered by these two curves, each executing their respective tasks in their native environments.

Since 2014, every production-grade recursive proof system has employed some variant of cycles of curves. However, historical patterns do not necessarily dictate future practices.

What we expect in the future?

Any time I see a visualization of cycles of curves it is apparent to me that at some point a less redundant solution will be found. In academic papers, they often do not even specify the usage of cycles of curves, as they are likely seen as an implementation detail rather than a feature of the ZKP schemes.

Cycles of curve optimization is a prime target for anyone looking to build simpler, likely faster, easier to build, and more easy to reason about ZK systems. Once again, we are not alone in this search!

Goblin Plonk from the Aztec team attacks this exact problem. "The main goal (of Goblin Plonk) is to remove the need to bounce between curve cycles at each layer of recursion, and significantly reduce Prover costs". They do this by using aggregation techniques on non-native group operation instructions: making them into a single set of instructions. They propose a curve transposition method that runs these operations only once for a set of recursive proofs. Using Goblin Plonk, one could 'fold' locally and have the aggregated non-native arithmetic be handled by specialized servers. This is amazingly cutting edge work!

Other interesting reasearch focuses on the elliptic curves themselves. Can we use super-singular curves or other elliptic curve traits to side-step the issues that cause non-native arithmetic to arise in the first place? A recent video from @CPerezz19 covers this.

The team at ICME is working in the direct context of folding schemes as key part of our proving system. We have interest in sum-check based approaches that can be optimized for resource constrained systems. Our current hypothesis, is that analogous methods to Goblin plonk exist for Nova based folding scheme, and that within these systems advanced lookup arguments can be used to mitigate non-native arithmetic in a very efficient manner.

In a historic post, Brendan Farmer from Polygon asks Ariel from Aztec about their use of lookup arguments for this exact problem. Somewhat like a 'cycle of curves', we think it is a good time to revisit lookup arguments, as a method for non-native arithmetic in folding based scheme.  Here be dragons! 🐉