# BW6 over BLS12-381
*Authors: [Youssef El Housni](https://yelhousni.github.io/) ([ConsenSys](https://consensys.net/), [GRACE](https://team.inria.fr/grace/)) and [Aurore Guillevic](https://members.loria.fr/AGuillevic/) ([inria](https://www.inria.fr/en/caramba))*
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*](https://arxiv.org/abs/2107.08473), 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](https://arxiv.org/abs/2107.08473)'s abstract*)
## 2-chains
In [HG20](https://eprint.iacr.org/2020/351.pdf), the authors proposed a method to construct a fast pairing-friendly elliptic curve over BLS12-377. That is, a curve $E_2$ with a subgroup order $r_2$ equal to field size $q_1$ of BLS12-377. This method can be generalized to any inner curve and especially to BLS12 curves. The choice of BLS12-377 was interesting because $q_1-1 \equiv 0 \mod 2^{46}$ yielding efficient radix-2 FFT needed to generate SNARK proofs over the outer BW6 curve. With the *ECFFT* breakthrough, one can swap BLS12-377 for the more widely used BLS12-381 and construct a new BW6 outer curve. This latter curve would have a subgroup order $r_2$ s.t. $r_2-1 \equiv 0 \mod 2$, but *ECFFT* approach might lead to acceptably efficient polynomial operations over $\mathbb{F}_{r_2}$.
## Inner curve: BLS12-381
BLS12-381 is a pairing-friendly elliptic curve from the family Barreto-Lynn-Scott with an embedding degree $k=12$ (Construction 6.6 in [FST06](https://eprint.iacr.org/2006/372.pdf), case $k\equiv 0 \mod6$). It is defined over a 381-bit field $\mathbb{F}_q$ and is defined by the equation $y^2=x^3+4$. The curve parameters are parametrized by polynomials that are evaluated at the seed $u=-15132376222941642752$.
Parameter | Polynomial | Value | 2-adicity|
--------- | ---------- | ----- | --------- |
field size $q$ | $(x-1)^2/3\cdot r(x)+x$ | 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab | 1
subgroup order $r$ | $x^4-x^2+1$ | 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 | 32
Besides the sizes of $q$, $r$ and the the low hamming-weight of $u$, which makes the pairing-friendly curve efficient and secure at almost 128-bit level, the high 2-adicity of $r-1$ makes it a fit for SNARK applications. However, the low 2-adicity of $q-1$ makes it inefficient to construct an outer curve with subgroup order $r_2=q$.
## Outer curve: BW6-767
Following [HG20](https://eprint.iacr.org/2020/351.pdf), we're looking for a curve $E_2$ with a subgroup order $r_2$ equal to BLS12-381 $q$. The same observations apply: we need $q_2$ to be less than 768 bits and $D=-3$. We use the modified Brezing-Weng method with tailored Frobenius trace $t(x)=t_0(x)+h_t \cdot r(x)$ and CM parameter $y(x)=y_0(x)+h_y \cdot r(x)$ (from CM equation $4q=t^2+Dy^2$). The lifting cofactors $h_t$ and $h_y$ must be chosen carefully according to the desired bit lengths and the CM discriminant $-D$. Given these constraints, we found 4 curves, which boils down basically to two pair of curves (a curve and its twist over the base field $\mathbb{F}_q$).
Our script, which will be soon open-sourced under MIT license, outputs the following curves:
```
test_vector_BLS12_381_BW6_768 = [
{'u':-0xd201000000010000, 'D':3, 'ht':-4, 'hy':-6, 'b':1, 'pnbits':767, 'rnbits':381, 'px':[31,65,37,115,112,-100,56,29,-191,79,142,-127,31], 'px_denom':9, 'rx':[1,1,0,2,0,-2,1], 'rx_denom':3, 'cx':[52,16,21,41,12,-65,31], 'cx_denom':3, 'yx':[6,7,0,9,3,-13,6], 'yx_denom':3, 'tx':[-4,-1,0,-17,9,5,-4], 'tx_denom':3, 'betax':[72,62,-16,258,-86,-152,234,-97,-190,300,-158,31], 'betax_denom':33, 'lambx':[1,-1,0,3,-3,1], 'lambx_denom':1, 'g2cx':[19,16,21,41,12,-65,31], 'g2cx_denom':3, 'label':"BLS12_BW6_767"},
{'u':-0xd201000000010000, 'D':3, 'ht':5, 'hy':9, 'b':9, 'pnbits':768, 'rnbits':381, 'px':[67,128,64,286,238,-262,209,38,-515,304,241,-262,67], 'px_denom':9, 'rx':[1,1,0,2,0,-2,1], 'rx_denom':3, 'cx':[61,43,21,140,-15,-128,67], 'cx_denom':3, 'yx':[9,8,0,21,-3,-17,9], 'yx_denom':3, 'tx':[5,8,0,1,9,-13,5], 'tx_denom':3, 'betax':[186,107,-43,663,-293,-359,729,-511,-199,570,-329,67], 'betax_denom':48, 'lambx':[1,-1,0,3,-3,1], 'lambx_denom':1, 'g2cx':[109,43,21,140,-15,-128,67], 'g2cx_denom':3, 'label':"BLS12_BW6_768"},
{'u':-0xd201000000010000, 'D':3, 'ht':7, 'hy':5, 'b':3, 'pnbits':767, 'rnbits':381, 'px':[31,65,37,115,112,-100,56,29,-191,79,142,-127,31], 'px_denom':9, 'rx':[1,1,0,2,0,-2,1], 'rx_denom':3, 'cx':[19,16,21,41,12,-65,31], 'cx_denom':3, 'yx':[5,4,0,13,-3,-9,5], 'yx_denom':3, 'tx':[7,10,0,5,9,-17,7], 'tx_denom':3, 'betax':[72,62,-16,258,-86,-152,234,-97,-190,300,-158,31], 'betax_denom':33, 'lambx':[1,-1,0,3,-3,1], 'lambx_denom':1, 'g2cx':[52,16,21,41,12,-65,31], 'g2cx_denom':3, 'label':"BLS12_BW6_767"},
{'u':-0xd201000000010000, 'D':3, 'ht':-11, 'hy':-7, 'b':3, 'pnbits':768, 'rnbits':381, 'px':[67,128,64,286,238,-262,209,38,-515,304,241,-262,67], 'px_denom':9, 'rx':[1,1,0,2,0,-2,1], 'rx_denom':3, 'cx':[109,43,21,140,-15,-128,67], 'cx_denom':3, 'yx':[7,8,0,11,3,-15,7], 'yx_denom':3, 'tx':[-11,-8,0,-31,9,19,-11], 'tx_denom':3, 'betax':[186,107,-43,663,-293,-359,729,-511,-199,570,-329,67], 'betax_denom':48, 'lambx':[1,-1,0,3,-3,1], 'lambx_denom':1, 'g2cx':[61,43,21,140,-15,-128,67], 'g2cx_denom':3, 'label':"BLS12_BW6_768"}
]
```
All these curves benefit from endomorphism-based optimizations as $D=-3$ and from fast Miller loop as the seed $u$ has low hamming-weight (same as BLS12-381).
That is said, the best curve is the first one: $y^2=x^3+1$ defined over a 767-bit field with $D=-3$, $h_t=-4$ and $h_y=-6$.
- The field $\mathbb{F}_q$ can be implemented in twelve 64-bit limbs, with one bit to spare for carries or for compressed y-coordinate flags.
- The cofactors $h_t,h_y$ give the fastest final exponentiation in the pairing computation as an exponentiation by $h_t^2+3h_y^2$ is needed.
- The coefficient $b=1$ is convenient for checking that a point is on the curve.
- There is a 2-isogeny from a curve with $j \ne 0$ or $1728$, allowing use of the "simplified SWU" method for hashing to an elliptic curve.
The constant $c=3$ is a sextic non-residue in $\mathbb{F}_q$ and so the twisted curve is a M-twist that corresponds to the third output curve: $y^2=x^3+3$ over the same field $\mathbb{F}_q$ with $D=-3$, $h_t=7$ and $h_y=5$. The extension fields can be constructed as $\mathbb{F}_{q^3}[u]=\mathbb{F}_q/u^3-3$ and $\mathbb{F}_{q^6}[v]=\mathbb{F}_{q^3}/v^2-u$.
$\rightarrow$ Below are the polynomial forms of the curves' parameters:
Curve | subgroup order $r(x)$ <br />(same as BLS12-381 $q(x)$)| field size $q(x)$ | cofactor $c(x)$ | Frobenius trace $t(x)$ | CM $y(x)$ | GLV $\lambda(x)$ | GLV $\beta(x)$ |
-- | -- | -- | -- | -- | -- | -- | -- |
$y^2=x^3+1$ | $(x-1)^2/3\cdot (x^4-x^2+1)+x$ | $(31x^{12} - 127x^{11} + 142x^{10} + 79x^9 - 191x^8 + 29x^7 + 56x^6 - 100x^5 + 112x^4 + 115x^3 + 37x^2 + 65x + 31)/9$ | $(93x^6 - 195x^5 + 36x^4 + 123x^3 + 63x^2 + 48x + 156)/9$ | $(-4x^6 + 5x^5 + 9x^4 - 17x^3 - x - 4)/3$ | $(6x^6 - 13x^5 + 3x^4 + 9x^3 + 7x + 6)/3$ | $1-x+3x^3-3x^4+x^5$ | $(72+62x-16x^2+258x^3-86x^4-152x^5+234x^6-97x^7-190x^8+300x^9-158x^{10}+31x^{11})/33$
$y^2=x^3+3$ (twist) | $(x-1)^2/3\cdot (x^4-x^2+1)+x$ | $(31x^{12} - 127x^{11} + 142x^{10} + 79x^9 - 191x^8 + 29x^7 + 56x^6 - 100x^5 + 112x^4 + 115x^3 + 37x^2 + 65x + 31)/9$ | $(93x^6 - 195x^5 + 36x^4 + 123x^3 + 63x^2 + 48x + 57)/9$ | $(7x^6 - 17x^5 + 9x^4 + 5x^3 + 10x + 7)/3$ | $(5x^6 - 9x^5 - 3x^4 + 13x^3 + 4x + 5)/3$ | $1-x+3x^3-3x^4+x^5$ | $(72+62x-16x^2+258x^3-86x^4-152x^5+234x^6-97x^7-190x^8+300x^9-158x^{10}+31x^{11})/33$
where $\lambda(x)$ is the endomorphism eigenvalue which when multiplied by a point $P=(x_P,y_P)$ on the curve acts as $(x_P,y_P) \mapsto (\beta(x)\cdot x_P, y_P)$.
$\rightarrow$ Below are the hexadecimal values of the shared curves' parameters, when evaluated at the seed $u=-015132376222941642752$:
Curve | subgroup order $r$ <br />(same as BLS12-381 $q$)| field size $q$ | GLV $\beta$ | GLV $\lambda$ |
-- | -- | -- | -- | -- |
$y^2=x^3+1$ and $y^2=x^3+3$ (twist) | 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab | 0x51e2bcf25fa8992238259ea59a063294c36dc4098befce4230f8d18f41e3fc19665e4360b872007d3dd5a1b865cbe8dadc2ce0c034926d18fe0ef8c1c63df7d97cbc118805598e5c31732000974254c83a38b08e7179beb96896aaaec71538e7 | 0x4a7108dc56f65caaa3748933617f8fb542e1d6e9ef88f166a011051b5f65b0b728456c117f8e93508e38b5b4682991ce3dae358b1b36f832f0bb174392eb6c806d9cd8a33550dbe01e63601ff328f27c5a594f723162ca74e40326ccf309a81a | 0x1a0111ea397fe699ec02408663d4de85aa0d857d89759ad4897d29650fb85f9b409427eb4f49fffd8bfd00000000aaac
## Implementation
$\rightarrow$ A first version of an optimized implementation of the curve arithmetic and the underlying finite fields, alongside optimal ate pairing computation (with fast final exp) was written in Golang under [gnark-crypto](https://github.com/ConsenSys/gnark-crypto) library (zkTeam @ConsenSys). It can be found in this fork's branch: https://github.com/yelhousni/gnark-crypto/tree/feat/bw6_on_bls12-381/ecc/bw6-767
Some more optimizations are WIP:
- [x] fast cofactor clearing
- [ ] fast subgroups check
- [ ] hash-to-curve
$\rightarrow$ To implement ECFFT, one needs an elliptic curve $\mathcal{E}$ defined over $\mathbb{F}_q$ that has a subgroup of order $n=2^K$, i.e. $n \mid \#\mathcal{E}$. Here is a curve $\mathcal{E}/\mathbb{F}_q$ with $n=2^{14}$:
$$ y^2 = x^3 + 1084536974112898056475867277898384818908861744259412476665320257443741025575627992627439521320036359935138329757479 $$
## Conclusion
For interoperability of blockchain projects, it would be great to use the same elliptic curve. BLS12-381 is a secure, optimized and widely used pairing-friendly elliptic curve in many patforms. For projects that need one layer proof composition, it might be viable to stick to BLS12-381 and use this BW6-767 alongside ECFFT for composing proofs.
A detailed paper that proposes a generic framework for constructing optimized 2-chains for SNARK composition with open-sourced code was published in [Eurocrypt 2022 proceedings](https://link.springer.com/chapter/10.1007/978-3-031-07085-3_13) and an extended version is available in [ePrint](https://eprint.iacr.org/2021/1359.pdf).

gnark
We’re a research team @ConsenSys. We work on zero knowledge proof systems.

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

10/12/2022With 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

6/14/2022last 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:

4/22/2021In 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}

12/18/2020
Published on ** HackMD**