Disclaimer: In case of inaccuracies, please open an issue on Github.

In recent years, SNARKs proliferated themselves as a potential privacy and scaling solution for permissionless blockchains. However, due to the complexity of underlying cryptography and mathematical constructions, SNARKs are hard to grasp for application oriented computer scientists and hardware developers. In this article, we will give a short introduction to pairing-friendly elliptic curves and how the choice of elliptic curve influences the feasability of constructing a recursive SNARK, a primitive of primary interest for especially for rollups and incrementally verifiable computation (IVC).

1. Mathematical Background

Let’s shortly revise the background on elliptic curves, under the assumption that the reader is familiar with the basics of finite fields (for a more detailed discussion of elliptic curves in the context of recursive SNARKs, the PhD Thesis of Youssef El Housni does an excellent job at providing a detailed background on elliptic curves).

We denote \(\mathbb{F}_p\) as a finite field for some prime \(p > 3\). Elliptic curves over finite fields form the basis for various cryptographic protocols. A typical elliptic curve can be expressed in the following equation (also termed Short Weierstrass Form):

\(y^2=x^3+a \cdot x+b\)

where \(a\) and \(b\) are coefficients in \(\mathbb{F}_p\) that satisfy the condition \(4 \cdot a^3 + 27 \cdot b^2 \neq 0\) to ensure that there are no singular points (cusps or self-intersections) on the curve.

These curves have a set of points, denoted \(E(\mathbb{F}_p)\), which includes all solutions to the curve equation over \(\mathbb{F}_p\)​ along with a special ‘point at infinity’. This set forms an abelian group under addition. Pairing-friendly elliptic curves are a special class of elliptic curves that facilitate the computation of bilinear pairings. The pairing operation enables novel cryptographic schemes that could not be built from discrete logarithm groups. On a high level, a bilinear pairing is a mapping that take two points from specific groups related to elliptic curves and output an element in a finite field, shortly denoted as \( e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T \). Here, \(\mathbb{G}_1\), \(\mathbb{G}_2\) are distinct prime-order \(r\) subgroups of \(E\), and \(\mathbb{G}_T \subset \mathbb{F}_q \) of the same order \(r\).

Pairing-friendly curves are chosen for their ability to compute these pairings efficiently, a property that not all elliptic curves possess. This efficient computation is crucial in applications like recursive SNARKs, where the cryptographic strength and efficiency of pairings directly impact the overall system’s performance and security. The most common elliptic curves used in cryptographic applications, particularly in the context of pairings and advanced cryptographic protocols, are the BN254 and BLS12-381 curves. Whereas BN254 is defined over a 256-bits prime field, BLS12-381 is defined over a 381-bits prime field. Due to a larger prime field, BLS12-381 is ought to be more secure, whereas operations like Scalar Multiplication are also less efficient (see e.g. practical benchmarks in our paper).

2. Recursion and Incrementally Verifiable Computation

2.1 Incrementally Verifiable Computation

Incrementally Verifiable Computation (IVC) targets the verification of long-running computations. Initially, this concept was introduced by Valiant in 2008 Val08. Formally, an IVC proof proves tha the \(i\)-th step of a computation was executed correctly, and there exists a proof that the computation was executed correctly for all \(i − 1\) previous steps, i.e. it holds that \(F(z_{i-1}) = z_i\), where \(F\) is the function applied at the \(i\)-th step, and there exists a proof \(\pi_{i-1}\) that attests to the correctness of \(z_{i-1}\).

Figure 1: Visualization of Incrementally Verifiable Computation

2.2 Recursion Overhead

Now, the overhead of recursive verification is simple - at each step, the prover needs to additionally verify the previous proof, i.e. the relation includes the circuit to be proven AND the circuit for verifiying the proof produced in the previous step. Hence, inital proposals for recursive SNARKs relied on state-of-the-art succinct SNARKs, where the verification involves only a minimal amount of operations (to minimize the recursion overhead). There is an additional caveat though, as pairing-based SNARKs that rely on elliptic curves have a differing scalar and base field, i.e. the prover operates over a different field than the verifier. In particular, prover operates in the scalar field \(\mathbb{F}_r\) and the verifiers checks the generated proofs in the extension field \(\mathbb{F}_q\) of the curves base field. The reason why recursive verification is costly in a naive approach in this setting is so-called non-native field arithemtic, where operations in \(\mathbb{F}_r\) need to be simulated in \(\mathbb{F}_q\) , which is expensive (remember that SNARKs verify proofs with bilinear pairings \(\mathbb{G}_1, \mathbb{G}_2 \xrightarrow{} \mathbb{G}_T\)). One could choose an elliptic curve \(E\) where \(q = r\) , but this yields a trivial discrete logarithm problem in \(E\).

2.3 Practical Recursion over Cycles and 2-Chains of Elliptic Curves

Practical solutions circumvent this caveat by leveraging cycles of elliptic curves, as first demonstrated by Ben-Sasson et. al BCTV14a. This approaches leverage the fact that for the cycles of applied elliptic curves, the base field of either curve is the scalar field of the other. However, only curves MNT4/6 (of embedding degree 4 or 6) achieve this property, which requires the use of large fields \(~(» r~)\) to achieve adequate security. In ZEXE, the authors circumvent this issue by constructing new curves (BLS12-377/ CP6-782, cmp. Fig.16 in ZEXE), which form a chain rather than a cycle - hence, only the base field of one curve is equivalent to the scalar field of the other, but not the other way around. A similar approach has been taken in Zebra, which instantiates the inner SNARK with discrete log based Spartan over the Grumpkin Curve and the outer SNARK with Groth16 over BN254. BN254 and Grumpkin form a cycle of elliptic curves and hence faciliate recursion without the need for emulation of non-native arithmetic. BN254 has pre-compiles on Ethereum, and hence proofs can be verified efficiently in a smart contract. Recent work has further shown that the BLS12 and BLS24 based families can be tailored for Groth’16 and KZG-based SNARKs recursive proof composition.

However, it turns out that this is not sufficient, and one can do better (see Section 3). Many SNARKs do not satisfy the requirement of succinct verification, and if they do they rely on trusted setups that have to be run in a pre-processing step. Further, pairing-based SNARKs involve a verification algorithm that relies on operations in elliptic curves (i.e. Groth16 involves 3 pairings for verifying a proof), and for recursive verification these operations need to be emulated in an arithmetic circuit (e.g. R1CS), which is prohibitively expensive. Hence, requiring a SNARK with a sublinear-time verifier significantly restricts the practicability of IVC, and PCD, in practice.

3. Recursion without Succinct Arguments

Weakening the requirement of sublinear-time verifier SNARKs led to the development of recursive arguments of knowledge from accumulation schemes (BCLMS20, Nova). At a high-level, an accumulation scheme requires the SNARK to be accompanied by an “accumulator“ that is updated at each recursion step and enables “postponing” the verification of SNARK proofs to the last step in the recursive chain of arguments (Benedikt Bunz covers the BCLMS20 construction for split-accumulation in detail in this presentation). In the following, we will skip a bunch of related works that construct IVC from atomic accumulation as they still require SNARKs with sublinear verification, and further FFT-friendly cycles of elliptic curves (BCMS20, Halo).

3.1 NOVA - An argument system based on a folding scheme without the requirement for Succinct Arguments

3.1.1 Preliminaries & Overview

In the following, consider that \(F\) describes the relation that we want to prove at each step (i.e., Nova describes uniform IVC, where the computation at each step is the same). Nova relies on a variant fo R1CS for arithmetization, hence recall that an R1CS instance is defined as \(A,B,C \in \mathbb{F}^{n \times n}\) such that \(F(x)=y\) iff there exists a vector \(z \coloneqq (x,y,w)\) for a witness \(w\) such that \( (A \cdot z) \circ (B \cdot z) = C \cdot z \). Note, that \(\cdot\) denotes the matrix-vector product and \(\circ\) denotes the entrywise (“Hadamard”) product. In the case of IVC, where \(F^{(i)}\) is the i-th step, this is equivalent to proving that \(F^{(i)}(x)=y\) with \(z \coloneqq (y_{i-1},y_i,w_i)\) and \( (A_i \cdot z) \circ (B_i \cdot z) = C_i \cdot z \).

Now, Nova describes “folding”, i.e. at each step of the IVC two R1CS instances are “folded” into a single R1CS instance, which then is again folded with another R1CS instance and so on (this is only roughly true, as folding two R1CS instances yields an error vector, which we will cover in 3.1.2). Trivially, one can fold two instances of uniform computations at each step. However, extensions of Nova support folding of non-uniform computations, allowing for efficient parallelization as described in this post on using IVC for zkVM. Each iterative step thereby does not compute the verification of the previous proof, which would be expensive. Rather, Nova levereages the additive homomorphism of additively homomorphic vector commitments (i.e. Pedersen Vector Commitment) to defer the verification until the last step.

3.1.2 Folding Scheme

In principle, a folding scheme is rather trivial to construct. As you will see, opposing to the common belief that binomial eqquations are useless after high school, they are quite helpful to construct a folding scheme!

At a high-level, a folding scheme leverages nothing besides the fact that one can combine tow algebraic R1CS instances \(z_1 \coloneqq (x_1,1,w_1)\) and \(z_2 \coloneqq (x_2,1,w_2)\) by computing their random linear combination (with a small quirk to account for errors). Now, we first show (i) the need for an error vector and (ii) how to use cross-terms as a valid error vector to enforce soundness of the argument system.

(i) Naive Approach. The naive approach, without correction for errors, would be to compute

\(x \xleftarrow{} x_1 + r \cdot x_2\)

\(w \xleftarrow{} w_1 + r \cdot w_2\)

and successively set \(z \coloneqq (x,1,w)\). Now, this doesn’t quite work as

\((A \cdot z) \circ (B \cdot z)\) = \((A \cdot (z_1 + r \cdot z_2)) \circ (B \cdot (z_1 + r \cdot z_2)) \)

\(= A \cdot z_1 \circ B \cdot z_1 + r \cdot (A \cdot z_1 \circ B \cdot z_2 + A \cdot z_2 \circ B \cdot z_1) + r^2 \cdot (A \cdot z_2 \circ B \cdot z_2)\)

\(\neq C \cdot z\)

The problem here is that our random linear combination introduces a cross-term that we need to account for (This is the part \(r \cdot (\textit{long term})\)). Further, even if we eliminate the cross-term, the constant and quadratic part of our equation still doesn’t yield the correct result \(C \cdot z\).

(ii) Introducing Scaling and Error. Now assume we introduce to additional vectors \(u\) and \(E\), such the prover claims validity of a relaxed R1CS of the form \( (A \cdot z) \circ (B \cdot z) = u \cdot (C \cdot z) + E \). We would like to show that

\( (A \cdot z) \circ (B \cdot z) = u \cdot (C \cdot z) + E \)

holds, if and only if BOTH of the following equations hold:

\( (A \cdot z_1) \circ (B \cdot z_1) = u \cdot (C \cdot z_1) + E \)

\( (A \cdot z_2) \circ (B \cdot z_2) = u \cdot (C \cdot z_2) + E \)

To do so, when folding two of these relaxed instances, we define our updated scaling and error vectors as random linear combinations of the form:

\(u \xleftarrow{} u_1 + r \cdot u_2\)

\(E \xleftarrow{} E_1 + r \cdot T + r^2 \cdot E_2\)

where

\(T = (A \cdot z_1) \circ (B \cdot z_2) + (A \cdot z_2) \circ (B \cdot z_1) - u_1 \cdot C \cdot z_2 - u_2 \cdot C \cdot z_1\)

Now, it can be shown that \( (A \cdot z) \circ (B \cdot z) = u \cdot (C \cdot z) + E \) holds for every choice of \(r \in \mathbb{F}\) by simple algebraic deduction (feel free to have a look at the book of Justin Thaler where this algebraic relation is proven on page 290). Note, that it is important for the prover to commit to the cross-term \(T\) before receiving the randomness \(r\) by the verifier. Furher, committing to \(E\) and \(w\) is essential to preserve zero-knowledge. The resulting constraint system is termed committed relaxed R1CS.

3.1.3 Building IVC from a folding scheme with NARKs

Great, now we already know how to take two (committed relaxed) R1CS instances at one step of a computation and fold them into a single instance. It remains to construct a concrete scheme that provides IVC, by combining the folding scheme with an argument of knowledge.

ToDo - Explain how to construct IVC