Authors: Youssef El Housni (ConsenSys, GRACE) and Aurore Guillevic (Inria, Aarhus University) Last year in [HG20], we introduced the BW6-761 curve which is a pairing-friendly curve that forms a 2-chain with BLS12-377 (previously introduced in ZEXE). That is, BW6-761 has a subgroup order $r$ precisely equal to the characteristic $q$ of the base field on which BLS12-377 is defined. In a recent work [HG21], we generalised the curve construction, the pairing formulas ($e : \mathbb{G}_1 \times \mathbb{G}_2 → \mathbb{G}_T$) and the group operations to any BW6 curve defined on top of any BLS12 curve, forming a family of 2-chain pairing-friendly curves. We also investigated other possible 2-chain families, and much more (read the paper!). Since BW6-761 is already implemented in few projects (gnark-crypto, arkworks, EY/libff, kilic/bw6 and constantine) and is used in production (Celo, Aleo), natural questions arise: What changes for BW6-761 after this work? Is the new formulas backward-compatible with the current implementations? If not, does it worth switching? The new general construction where BW6-761 would fall, is coherent with the groups operations and pairing formulae found previously in [HG20]. However, we found new pairing algorithms that are faster. In this note, we try to shed light on the differences and the backward compatibilty. Pairing computation Given $P \in \mathbb{G}_1$ and $Q \in \mathbb{G}_2$, a pairing computation for BW6 is

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

Authors: Youssef El Housni (ConsenSys, GRACE) and Aurore Guillevic (inria) Following the recent work on FFT over non-smooth fields (ECFFT), it might be viable to instantiate a SNARK with an elliptic curve of non-smooth subgroup order. Particularly, one layer SNARK composition can be achieved with less constraints for the choice of curves. In this note we propose a 2-chain based on the widely used BL12-381 curve. The outer curve is a BW6 with a subgroup order 2-adicity equal to one. ECFFT For smooth finite fields $\mathbb{F_q}$ (i.e., when $q−1$ factors into small primes) the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. However, the same operations over fields with no smooth order root of unity suffer from an asymptotic slowdown. [In a recent work by Ben-Sasson, Carmon, Kopparty and Levit, called ECFFT, the authors proposed a new approach to fast algorithms for polynomial operations over all large finite fields.] The key idea is to replace the group of roots of unity with a set of points $L \subset F$ suitably related to a well-chosen elliptic curve group (the set $L$ itself is not a group). The key advantage of this approach is that elliptic curve groups can be of any size in the Hasse-Weil interval $[q+1\pm2\sqrt{q}]$ and thus can have subgroups of large, smooth order, which an FFT-like divide and conquer algorithm can exploit. (From the paper's abstract) 2-chains

last benchmark update: 29/01/21 There are several pairing-friendly elliptic curves libraries used in zero-knowledge proofs (ZKP) projects. Typically, the most important elliptic curve operations in ZKP schemes are "multi scalar multiplication" (MSM) and "pairing product" (PP). This writeup is a try to benchmark and compare the building blocks of these operations in two different architechtures. In fact, since MSM and PP are size-dependant, we focus on timings of mixed addition in G1/G2, doubling in G1/G2, Miller loop and Final exponentiation. The libraries are written in different languages with different software and mathematical optimizations, and with more or less assembly code. The target curves are: BN254, BLS12-381, BLS12-377 and BW6-761. The chosen libraries are:

In this note we describe PLONK, a recent zero-knowledge proof system. The goal is to walk through the scheme step by step and explain the cryptographic primitives at play. Arithmetization The arithmetization a program consists in expressing a program as a sequence of constraint which have a simple mathematic form. There are lots of ways to do this, but in this post we will look at a variation of Rank 1 Constraint System (R1CS). Namely, the $i-th$ constraint binds variables $(w_i)$ by relations of this form: \begin{align} (q_L)iw{i_a}+(q_R)iw{i_b}+(q_M)iw{i_a}w_{i_b}+d_i=(q_c)iw{i_c} \end{align}

In this note we describe Halo, a recent zero-knowledge proof system. The goal is to walk through the scheme step by step and explain the cryptographic primitives at play. We look at the problem of proving a very long sequence of statements. For instance a blockchain-rollup operator needs to accumulate as many transactions as possible before providing a proof of correct execution of all those transactions to the blockchain. The proof has to be succint, verified in constant time (ideally) no matter the number of operations in the sequence. Pedersen commitments Halo relies mainly on the Pedersen commitment scheme, along with an opening technique borrowed from bullet proof (with a little modification from its original description). :::info Let $p\neq r$ be prime numbers, $E(\mathbf{F}_p)$ an elliptic curve defined over $\mathbf{F}p$ such that $E$ contains a group $E[r]$ of $\mathbf{F}p$ rational points of order $r$. Let $n<<r$ be an integer and $(G_i){i\in[n]}$ a list of points in $E[r]$.

Introducing goff: fast modular arithmetic in Go We are proud to introduce goff (go finite field): a tool that generates pure Go source code for fast modular arithmetic operations for any modulus. goff at a glance goff produces pure Go code (no assembly^[until this PR]) that is competitive with state-of-the-art libraries written in C++, Rust, or assembly. Modular multiplication is especially fast in goff. :fire: We discovered and implemented an algorithmic improvement that yields a 10%--15% speed gain over state-of-the-art algorithms. See our article Faster big-integer modular multiplication for most moduli for details and benchmarks. The source code for goff is available on GitHub under the Apache 2.0 License. :::info

We discovered an optimization that reduces the number of operations needed to compute the modular multiplication of two big integers for most (but not quite all) choices of modulus. Big-integer modular multiplication is a low-level component found in most modern cryptographic protocols including Elliptic curve cryptography, such as Elliptic Curve Digital Signature Algorithm (ECDSA) Elliptic Curve Diffie-Hellman key exchange (ECDH) Elliptic Curve pairings

Introducing gnark: a fast zero-knowledge proof library We are proud to introduce gnark---a fast, open-source library for zero-knowledge proof protocols written in Go. gnark at a glance: gnark offers a high-level API and CLI that makes it easy for developers to write functions and produce zero-knowledge proofs for those functions. gnark currently supports the Groth16 zk-SNARK protocol. We intend to add support for other protocols in the future. gnark is faster than bellman, which is a popular state-of-the-art implementation of Groth16. (See our benchmarks below.) The source code for gnark is available on GitHub under the Apache 2.0 License.