References: SP1 V4 turbo note SP1 github code ZK12: Memory checking in IVC-based zkVMs - Jens Groth image (screenshot from SP1 V4 turbo note)

_____ _ ____ _ __ __ | ___|_ _| | _____ / ___| |\ \ / / | |_ / _` | |/ / _ \ | | _| | \ \ / / | _| (_| | < __/ | |_| | |__\ V / |_| \__,_|_|\_\___| \____|_____\_/ IntroductionOther applications Background

This note focuses on the techniques used for optimizing the emulated bilinear pairing circuit in gnark library. This is the part 2 of the part 1 by @ivokub. :::info Goal: Express a pairing on BN254 (and BLS12-381) in a SNARK circuit instantiated on BN254 in as less constraints as possible. The pairing curve: BN254 or BLS12-381 The SNARK curve: BN254 The pairing curve is independent of the choice of the SNARK curve. :::

A "potential security issue" in gnark-crypto was mentioned in the EF security call and was later reported to the gnark team by Besu, geth and EF teams. It was about a BN254 pairing value not consistant with google and cloudflare implementations discovered by the geth fuzzer. :::info TL;DR there is no bug. Starting from v0.8.0, gnark-crypto uses a different algorithm for the final exponentiation that outputs different (correct) results compared to google and cloudflare. ::: Example of a failing test vector: bn256.G1(192c207ae0491ac1b74673d0f05126dc5a3c4fa0e6d277492fe6f3f6ebb4880c, 168b043bbbd7ae8e60606a7adf85c3602d0cd195af875ad061b5a6b1ef19b645) bn256.G2((07caa9e61fc843cf2f3769884e7467dd341a07fac1374f901d6e0da3f47fd2ec, 2b31ee53ccd0449de5b996cb8159066ba398078ec282102f016265ddec59c354), (1b38870e413a29c6b0b709e0705b55ab61ccc2ce24bbee322f97bb40b1732a4b, 28d255308f12e81dc16363f0f4f1410e1e9dd297ccc79032c0379aeb707822f9))

Let $E$ be an elliptic curve $y^2 = x^3 + ax +b$ over some finite field $\mathbb{F}_p$, where $p$ is a prime $\ne 2, 3$. For simplicity, let's focus on $j$-invariant $0$ i.e. $y^2=x^3+b$. With division polynomials, one can come up with the following formulas due to Katherine E. Stange. input: $P = (x_1,y_1)$ output: $[n]P = (x_n, y_n)$ where $x_n=x_1−\frac{W(n-1, 0)\cdot W(n+ 1, 0)}{W(n, 0)^2}$ $y_n=\frac{W(n− 1, 0)^2 \cdot W(n+ 2, 0) −W(n+1, 0)^2 \cdot W(n− 2, 0)}{4y_1 \cdot W(n, 0)^3}$ With:

Twisted Edwards curve: $-x^2+y^2=1+dx^2y^2$ over $\mathbb{F}_r$ (e.g. SNARK field of BN254) of order $n = h\cdot \texttt{prime}$ ($h=4$ or $h=8$) with generator point $G$. keys: secret key: scalar $a$

With my co-authors Aurore Guillevic and Diego F. Aranha, we published on ePrint mid-May a survey of elliptic curves for proof systems (ePrint 2022/586). Recently, there have been many tailored constructions of these curves that aim at efficiently implementing different kinds of proof systems. In that survey we provide the reader with a comprehensive view on existing work and revisit the contributions in terms of efficiency and security. We present an overview at three stages of the process: curves to instantiate a SNARK, curves to instantiate a recursive SNARK, and curves to express an elliptic-curve related statement. In this post, we are only interested in the first case. For pairing-based SNARKs, such as the circuit-specific Groth16 [1], bilinear pairings ($e:\mathbb{G}_1\times \mathbb{G}_2 \rightarrow \mathbb{G}_T$) are needed for the proof verification. For universal SNARKs, such as PLONK [2] or Marlin [3], a polynomial commitment scheme is needed. An example of an efficient one is the Kate-Zaverucha-Goldberg (KZG) scheme [4]. The verifier needs to verify some polynomial openings using bilinear pairings. So far, for both circuit-specific and universal constructions, the verification algorithms boil down mainly to pairing computations. However, the prover work is not the same. For Groth16, it is mainly multi-scalar-multiplications (MSM) in both $\mathbb{G}_1$ and $\mathbb{G}_2$ while for KZG-based schemes it is mainly MSMs in $\mathbb{G}_1$ only. In section 4 of the survey paper, we look at a particular family of pairing-friendly elliptic curves suitable for KZG. We derive algorithm 6 to tailor this family to the SNARK context. Note that KZG is also useful for other compelling applications such as Verkle trees for blockchain stateless clients. Pairing-friendly curves

Let $E$ be an elliptic curve from the BLS12 family. We denote by $r$ its prime subgroup order. Let $P(x,y) \in E$ a point of order $r$. The goal is to verify efficiently that $r\cdot P = \infty$. Notations $E$ is an elliptic curve defined over a finite field $\mathbb{F}_p$ with the short Weierstrass equation $y^2=x^3+ax+b$ $r$ is a prime-order subgroup of $E(\mathbb{F}_p)$ $k$ is the embedding degree, i.e. the smallest integer s.t. $r \mid p^k-1$ A pairing is a map $e: \mathbb{G}_1 \times \mathbb{G}_2 \mapsto \mathbb{G}_T$, where $\mathbb{G}_1 \subset Er$, $\mathbb{G}_2 \subset Er$ and $\mathbb{G}_T$ the group of $r$-th roots of unity in $\mathbb{F}_p$. BLS12

All the Groth16 circuits compiled with ZoKrates result in partially the same verification.key and proving.key when setup command is run. We try to explain here why this problem occurs for verification.key. The same goes for proving.key but it's easier for the verification.key file because it is human-readable. Groth16: Verification equation $$ e(A,B)=VK_{\alpha,\beta}\cdot e(VK_{\gamma_{abc}},VK_{\gamma})\cdot e(C,VK_{\delta}) $$ where $\pi=(A,B,C)$ is a proof and $VK=(VK_{\alpha,\beta},VK_{\gamma_{abc}},VK_{\gamma},VK_{\delta})$ a verification key. $VK_{\alpha,\beta}=e(VK_{\alpha},VK_{\beta}), VK_{\gamma}$ and $VK_{\delta}$ are independant from the public inputs $\phi_i$

$a_1G_1+a_2G_2+\dots+a_nG_n$ $n \rightarrow$ size of MSM $b \rightarrow$ bit-size of $a_i$ Bucket method $S_1+2S_2+3S_3+\dots+(2^c-1)S_{2^c-1}$ Original