part_3.md

Nova Folding Part 3: Cycle of Curve in Nova

This part explains about what is the Cycle of Curve and How it works in Nova Folding. The original Nova paper used a single elliptic curve. However, Recursion, which generally repeats Proving and (partial) Verifying, can improve the efficiency of proof generation by using a special pair of two elliptic curves called a Cycle of Curves. So the implementation of Nova Folding also employs the Cycle of Curve. The paper, Revisiting the Nova Proof System on a Cycle of Curves, discusses how Nova works with the Cycle of Curve and bugs found in early implementations of Nova with the Cycle of Curve.

The purpose of this article is to provide a basic understanding of elliptic curves and the Cycle of Curves and how it is utilized in Nova Folding.

We begin with knowledge of elliptic curves.

1 Group and Field

1.1 The Set $Z_7$

$Z_7$ contains the integers ${0, 1, 2, 3, 4, 5, 6}$. In this set, we define two operations: addition and multiplication, both performed with modulus $7$. The way these operations interact with the elements of $Z_7$ gives rise to two important mathematical structures: a group and a field.

Order

Order refers to the number of elements in a group or a field. For $Z_7$, both as a group and a field, the order is 7, representing its seven unique elements.

1.2 Group

1.2.1 What is a Group?

A group is a set combined with an operation (such as addition or multiplication) that satisfies Four conditions: Closure, Associativity, Identity, and Invertibility. When we examine $Z_7$ under addition, it forms a group, especially an abelian group.

1.2.2 Group Structure of $Z_7$ under Addition

In $Z_7$, when we add numbers using our special rule (modulo 7), some neat patterns emerge:

• Closure: For any two elements $a, b$ in $Z_7$, the operation $a + b$ results in an element also in $Z_7$. For instance, $6 + 2 = 8 \mod 7 = 1$.

• Associativity: For any three elements $a, b, c$ in $Z_7$, the equation $(a + b) + c = a + (b + c)$ always holds. For example, $(1 + 2) + 3 = 6$, and $1 + (2 + 3) = 6$.

• Identity: For any element $a$ in $Z_7$, adding 0 does not change the element, making 0 the identity element. For example, $4 + 0 = 4$.

• Invertibility: For every element $a$ in $Z_7$, there exists an element $b$ such that $a + b = 0 \mod 7$. For example, the inverse of 3 is 4 because $3 + 4 = 7 \mod 7 = 0$.

In the case of group under multiplication, $Z_7^$ consists non-zero element $1,2,3,4,5,6$. And the identity element is $1$, not $0$, as every number multiplied by $1$ remains unchanged. In invertibility, for each element $a$ in $Z_7^$, there exists a corresponding element $b$ such that $a \cdot b = 1 \mod 7$.

1.2.3 Abelian group

An Abelian group, also known as a commutative group, is a group in which the operation is commutative in addition to the four rules of group.

• commutative: For any two elements $a, b$, $a + b = b + a$. For instance, $Z_7$ forms an Abelian group under addition, as shown by $3 + 4 = 7 \mod 7 = 0$ and $4 + 3 = 7 \mod 7 = 0$.

1.2.4 Cyclic Group Generated by 2 in $Z_7$

To further understand the concept of a cyclic group and its generator, let's focus on $Z_7$ and observe the behavior when we repeatedly add the number 2.

• $2 \mod 7 = 2$
• $(2 + 2) \mod 7 = 4$
• $(2 + 2 + 2) \mod 7 = 6$
• $(2 + 2 + 2 + 2) \mod 7 = 1$
• $(2 + 2 + 2 + 2 + 2) \mod 7 = 3$
• $(2 + 2 + 2 + 2 + 2 + 2) \mod 7 = 5$
• $(2 + 2 + 2 + 2 + 2 + 2 + 2) \mod 7 = 0$
• $(2 + 2 + 2 + 2 + 2 + 2 + 2 + 2) \mod 7 = 2$

In this sequence, we start with 2 and, by continuously adding 2, we eventually produce every element in $Z_7$. Once we reach 0 again, the pattern repeats, starting once more with 2. This behavior is characteristic of a cyclic group. The element 2, in this case, is called the generator because it generates all elements of the group through repeated addition.

The fascinating aspect of cyclic groups, especially in a set like $Z_7$, is that when the number of elements (in this case, 7) is a prime number, any number in the set except 0 can act as a generator.

1.2.5 Subgroup

A subgroup is a subset of a group that itself forms a group under the same operation defined for the original group. To qualify as a subgroup, this subset must satisfy the group's rules: Closure, Associativity, Identity, and Invertibility.

1.3 Field

1.3.1 What is a Field?

A field is an algebraic structure where two operations, addition and multiplication, have six characteristics: Closure, Associativity, Commutativity, Identity, Invertibility, and Distributivity.

1.3.2 Field Structure of $Z_7$ Under Addition and Multiplication

• Closure:

  • Closure under Addition: For any two elements $a, b$ in $Z_7$, their sum $a + b$ is also in $Z_7$. For instance, adding 6 and 2 gives $6 + 2 = 8 \mod 7 = 1$.
  • Closure under Multiplication: For any two elements $a, b$ in $Z_7$, their product $a \times b$ is also in $Z_7$. For example, the product of 3 and 2 is $3 \times 2 = 6 \mod 7 = 6$.

• Associativity:

  • Additive Associativity: For any three elements $a, b, c$ in $Z_7$, the equation $(a + b) + c = a + (b + c)$ always holds. For example, taking $a = 2, b = 3, c = 4$ in $Z_7$, we have $(2 + 3) + 4 = 5 + 4 = 9 \mod 7 = 2$ and $2 + (3 + 4) = 2 + 7 \mod 7 = 2$.
  • Multiplicative Associativity: Similarly, for any three elements $a, b, c$ in $Z_7$, the equation $(a \times b) \times c = a \times (b \times c)$ is always true. For example, with $a = 2, b = 3, c = 4$ in $Z_7$, $(2 \times 3) \times 4 = 6 \times 4 = 24 \mod 7 = 3$ and $2 \times (3 \times 4) = 2 \times 12 \mod 7 = 3$.

• Commutativity:

  • Additive Commutativity: For any two elements $a, b$, the operation $a + b = b + a$ holds. For example, in $Z_7$, $2 + 5 = 7 \mod 7 = 0$ and $5 + 2 = 7 \mod 7 = 0$. This property is a hallmark of an Abelian group.
  • Multiplicative Commutativity: Similarly, for multiplication, $a \times b = b \times a$ for any $a, b$, excluding the special case of the additive identity (0). For example, $3 \times 4 = 12 \mod 7 = 5$ and $4 \times 3 = 12 \mod 7 = 5$. This extends the concept of Abelian groups to the multiplicative operation within a field.

• Identity:

  • Additive Identity: The element $0$ acts as the additive identity, where $a + 0 = a$ for any $a$. For example, $4 + 0 = 4$.
  • Multiplicative Identity: The element $1$ serves as the multiplicative identity in $Z_7$, where $a \times 1 = a$ for any $a$. For example, $5 \times 1 = 5$.

• Invertibility:

  • Additive Inverses: For each element $a$ in $Z_7$, there exists an additive inverse $-a$ such that $a + (-a) = 0$. For example, the additive inverse of $3$ is $4$ because $3 + 4 = 7 \mod 7 = 0$.
  • Multiplicative Inverses: For each non-zero element $a$ in $Z_7$, there exists a multiplicative inverse $a^{-1}$ such that $a \times a^{-1} = 1$. For example, the multiplicative inverse of $3$ is $5$ because $3 \times 5 = 15 \mod 7 = 1$.

• Distributivity: This law connects the two operations in $Z_7$, stating that $a \times (b + c) = a \times b + a \times c$ and $(a + b) \times c = a \times c + b \times c$. For example, $2 \times (3 + 4) = 2 \times 7 \mod 7 = 0$ and $(2 \times 3) + (2 \times 4) = 6 + 8 \mod 7 = 0$.

1.3.3 Finite Field

A Finite Field is defined as a field that contains a finite number of elements. $Z_7$ is the field that has 7 elements so $Z_7$ is a finite field. When a prime number $p$ is chosen, the set of numbers ${0,1,…,p−1}$ consisting of $p$ elements forms a finite field.

2 Elliptic curves on Finite Fields

2.1 Mathematical Definition of Elliptic Curves

Elliptic curves are defined by a specific equation, commonly known as the Weierstrass equation, represented as follows:

$$ y^2 = x^3 + ax + b $$

In cryptography, elliptic curves are defined over finite fields $F_p$, not over the field of real numbers. The coefficients $a,b$ of the elliptic curve formula are chosen from the finite field $F_p$. The calculations on elliptic curves are performed within this finite field, following modular arithmetic. Then, the all coordinates (x,y) satisfying the formula form a group.

2.2 Base Field and Elliptic Curve Group

2.2.1 Base Field

Elliptic curves are defined over a finite field $F_p$, which consists of integers from 0 to $p-1$, where $p$ is a prime number. This finite field is called Base Field.

2.2.2 Elliptic Curve Group as a Cyclic Group

The calculations on elliptic curves are performed within this finite field, following modular arithmetic. Then, the coordinates (x,y) are satisfying the formula form a group.

The elliptic curve group $E(F_p)$ is the set of all pairs of $(x, y)$ that satisfy the above equation.

To confirm that the elliptic curve group is indeed a group, let's check that the axioms are satisfied. Here we want to focus on Invertibility.

Addition of elliptic curves over a finite field is defined as:

Pairing-based Cryptography와 BLS signature의 이해 — Part 1

So if we try to add $P$ and its reciprocal $-P$, the line connecting those lines goes to the infinity point. This is one of the invertibility of the axioms of the group.

Pairing-based Cryptography와 BLS signature의 이해 — Part 1

When the order $q$ of the elliptic curve group $E(F_p)$ is a prime number, the group, $G$ exhibits the properties of a cyclic group. A cyclic group is one in which all the elements of the group can be generated by the repeated addition of a single element (the generator).

2.2.3 Subgroup

In the previous chapter, we mainly dealt with the case where the order of the elliptic curve group itself is prime.

However, in advanced elliptic curve cryptography such as ZKP, the order of the elliptic curve group is not prime. And instead of using the entire elliptic curve group $G$, we have to select a subgroup of it to use.

This subgroup, which is a subset of the whole elliptic curve group, $G_r$, possesses a prime order. Despite the entire group having a non-prime order, potentially even an even number, the chosen subgroup maintains a prime order.

In this situation, a prime order in a subgroup also assures that the subgroup is cyclic group.

2.2.4 Scalar Field

Given an elliptic curve group $E(F_p)$ with an order $q$, and focusing on a specific subgroup $G$ with a prime order $n$, the scalar field is defined relative to this subgroup.

The scalar field is denoted as $Z_n$, which comprises the set of integers from $0$ to $n-1$. Within this field, each scalar is employed for the scalar multiplication of points on the elliptic curve. Meaning, for any point $P$ in the subgroup $G$ and any integer $k$ in the scalar field, the scalar multiplication $kP$ results in another point within $G$.

3 The Role of Finite Fields and (Sub) Groups in ZKP

Now that you understand the concepts of Finite field and Subgroup, let's see how they are utilized in ZKP.

3.1 Finite Fields

When you write circuits for ZKP in Circom or Halo2, they are defined in Finite Field $F_p$. Also, when you enter a value into that Circuit, the witness and output are calculated. Those calculations are also done in the Finite Field $F_p$.

3.2 (Sub) Groups and Scalar Field

As you may know, in the context of pairing-based SNARKs, the process begins by transforming an Arithmetic Circuit into a set of polynomials defined over a finite field, known as a Quadratic Arithmetic Program (QAP). Subsequently, the coefficients of these polynomials are encoded onto points on an elliptic curve. This encoding is achieved by performing scalar multiplications with respect to a generator of a (sub)group $G$. The verification of Zero-Knowledge Proofs (ZKPs), which includes operations such as multi-scalar multiplication, pairings, and the verification of commitments, is carried out on this (sub)group.

4 The arithmetic problem in Recursion

Please remember the naive snark-based IVC. At each step, $SNARK.V$ in $IVC.P$ verifies the previous proof $\Pi_i$ in Augmented circuit and $SNARK.P$ in $IVC.P$ generates next proof for the Augmented circuit.

Here, we encounter a mathematical challenge due to the prover and verifier operating within different orders. The prover $SNARK.P$, is capable of creating proofs for circuits over the finite field $F_p$.

Meanwhile, the verifier $SNARK.V$, needs to perform operations within a (sub)group $G_s$ of $E(F_p)$. This (sub)group $G_s$ has a prime order $s$.

The core issue is that the prover $SNARK.P$ operates within the finite field $F_p$, but the verifier $SNARK.V$ requires operations based on the prime order $s$ of the subgroup $G_s$. This results in a mismatch in the recursive proof process, as $SNARK.P$ and $SNARK.V$ use different parameters for their respective operations. Circuits operating over $F_p$ cannot directly handle elements of $G_s$.

So Field emulation may be one of the solution, but it is very unefficient. The purpose of field emulation is to "emulate" operations of $G_s$ using only operations in $F_p$, thus resolving the mathematical discrepancy between the two. To emulate the operations of $G_s$ over $F_p$, complex circuits that mimic the operations of $G_s$ using only the arithmetic of $F_p$ are required. However, it necessitates numerous additions and multiplications, significantly enlarging the circuit size. Finally, the larger circuit size means that field emulation further lengthens the speed of proof generation.

5 Cycle of Groups

The solution to this mismatch lies in an advanced approach known as "Cycles of Groups." By introducing two groups, $G_1$ and $G_2$, each operating over distinct finite fields, we can bridge the gap between the prover $SNARK.P$ and the verifier $SNARK.V$.

• Group $G_1$, with order $p$, operates over the finite field $F_q$.
• Conversely, Group $G_2$, having order $q$, is defined over the finite field $F_p$.

This innovative setup enables an extended recursion capability, allowing the prover and verifier to effectively 'jump' between the two proof systems. Consequently, both parties can conduct their operations within their respective fields, $F_p$ and $F_q$, while maintaining coherence in the overall recursive proof process.

5.1 Example of Cycle of Curve

For instance, the Pasta curves comprise two elliptic curves named "Pallas" and "Vesta," which are used in what's referred to as "Cycles of Curve." In this case, a notable point is that the Base field and Scalar field are inverted for each of the curves.

5.2 Recursion with Cycle of Curve

Next, let's look at why Cycle of Curve can make recursion more efficient. Please remember this relationship.

In recursion, two elliptic curves are used alternately.

This illustration was inspired by The Halo2 Book

First, suppose we want to prove a circuit defined by a finite field $F_q$. Then we create a proof $\Pi$ whose value is on $G_{1(p)}$, order $p$. Then, in the next recursive step, we define a circuit on a finite field of $F_p$ whose order is $p$ and create the proof $\Pi$ from there. Here, the order $p$ of the proof and the order $p$ of the finite field of the new circuit are the same and compatible. After that, the order of the next proof of the circuit defined on $F_p$ will be $q$ in $G_{2(q)}$, and in the next recursion step, the circuit is compatible with the finite field $F_q$ whose order is $q$. Thus, by using the Cycle of Curve, we can make the proof $\Pi$ compatible with the order of the circuit at each recursion step.

6 Why does the Cycle of Curve makes Nova efficient?

Recall the Augmented Circuit, which includes Non-Interactive Folding.

In the Non-Interactive Folding Scheme, it folds two committed relaxed R1CS instances into one. These instances each have commitment values: $\overline{W}$ , $\overline{E}$ and $\overline{T}$, which are points on the curve. Then, these points are multiplied by a scalar $r$, indicating that the calculations occur within a Group. However, the Augmented Constraints are defined over the Finite Field, as they constitute a circuit component. This situation creates incompatibility. If an Augmented Constraint system, defined on the Finite Field and enforces calculations on the Group, it results in added complexity and inefficiency.

This is precisely where the Cycle of Curves becomes relevant. It would be better to define the Augmented Circuit that does the Folding on the two elliptic curves of the Cycle of Curves, and move the value to be Folded back and forth on the two elliptic curves.

7 How the Cycle of Curve works in Nova

Recall this figure, the $u_i$ computed from the Augmented Constraints defined in the Base Field is giving values on the curve. Here, we should use Cycle of Curve in the IVC step.

To address these inefficiencies, this part explains the use of elliptic curves from a Cycle of Curves to establish the Augmented Constraints over two distinct finite fields.

Images are borrowed from this video: Revisiting the Nova Proof System - Wilson Nguyen.

First, define an Augmented Circuit that contains Non-Interactive Folding on a finite field of two elliptic curves, the pair of the Cycle of Curve.

This approach transfers the $u_i$, which validates the correct execution of the previous step and which is on the curve, between the two Augmented Constraints that defined on the Cycle of Curve. This method circumvents the inefficiencies associated with performing non-native (group) computations in a native (field) circuit.

Revisiting Nova provides a detailed description of Nova utilizing the Cycle of Curve and a clear explanation of the bugs found in early Nova implementations, so I recommend anyone interested to take a look. Revisiting the Nova Proof System - Wilson Nguyen

8 Reference

• ZKP MOOC Lecture 10: Recursive SNARKs
• Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
• Revisiting the Nova Proof System - Wilson Nguyen
• Revisiting the Nova Proof System on a Cycle of Curves
• Pairing-based Cryptography와 BLS signature의 이해 — Part 1
• The Halo2 Book