# BN254 pairing in gnark vs. google and cloudflare

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))

## Pairing algorithm
Given two points $P \in \mathbb{G}_1$ and $Q \in \mathbb{G}_2$ (of order $r$ with coordinates in e.g. $\mathbb{F}_p$ and $\mathbb{F}_{p^2}$ resp.), a pairing is the bilinear map $e(P,Q): \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. All gnark-crypto, google and cloudflare implement the optimal ate pairing for the BN254 curve which is a 2-step computation
$$ e(P,Q) = ML(P,Q)^{FE} $$
Where $ML$ is called the Miller loop and $FE$ is called the final exponentiation.
After the computation of the Miller loop, we obtain an element of the quotient group $\mathbb{F}_{p^{12}} /(\mathbb{F}_{p^{12}})^r$ (the ate pairing is only defined up to a multiple by an $r$-th power in $\mathbb{F}_{p^{12}}^*$). Then the final exponentiation, namely the exponentiation by a fixed large exponent $(p^{12} − 1)/r$, must be performed to obtain an element of $\mathbb{G}_T$ of order $r$. This operation is also known as the cofactor clearing to ensure output
uniqueness, algorithmic correctness, and security for pairing-based cryptography.

This is said, $(p^{12}-1)/r$ is not the only exponent to ensure these properties. It is the smallest one but not necessarily the *fastest* one. We can always raise (shift) to a multiple $s\cdot(p^{12}-1)/r$ such that $r \nmid s\cdot(p^{12}-1)$ and the pairing properties would still be verified. In this sense, there is no "correct" and "wrong" value of an ate (or a Tate) pairing.

Google and cloudflare use the exponent $(p^{12}-1)/r$ while gnark-crypto, starting from v.0.8.0, uses the exponent $s \cdot (p^{12}-1)/r$ where $s=2u(6u^2+ 3u+1)$ with $u=\texttt{0x44e992b44a6909f1}$ the curve seed. This allows a better decomposition of the $FE$ in a basis containing $p$ i.e. $FE = \texttt{function}(p,u)$ so that we can better leverage frobenius maps (exponentiation by $p$ is cheap). This specific exponent was suggested by [Fuentes in al.](https://link.springer.com/chapter/10.1007/978-3-642-28496-0_25) and allows a faster computation of $FE$.

## Discussion
- All implementations of gnark-crypto, google and cloudflare are correct but give different (shifted) results.
- google, cloudflare and gnark-crypto (v.0.7.0 or earlier) use a development of $(p^{12}-1)/r$ (see Sec.5 in [Scott et al.](https://eprint.iacr.org/2008/490.pdf) (2008)).
- gnark-crypto starting from v.0.8.0 uses [Fuentes et al.](https://link.springer.com/chapter/10.1007/978-3-642-28496-0_25) (2011) (see Alg.6 or 10 [Ghammam and Duquesne](https://eprint.iacr.org/2015/192.pdf) (2015)).
- In gnark-crypto v.0.8.0, we implement Alg.10 in this [PR](https://github.com/ConsenSys/gnark-crypto/pull/189) and then change it to Alg.6 in v.11.0 in this [commit](https://github.com/ConsenSys/gnark-crypto/commit/4cbf9757a9056547e8e7ea58b97fee11502350ad) (results do not change).
- The test vector comparison succeeds in v.0.7.0 and fails in later versions for the explained reasons. In any later version (e.g. v.0.8.0 or v.0.11.0) if we replace the hard part in the final exponentiation by the one in v.0.7.0, the comparison test succeeds. Or even if we replace it by just:

        // (p⁴-p²+1)/r
        var s big.Int
        s.SetString("10486551571378427818905133077457505975217533156541166536005452068033223782873764572151541189142778783267711471998854717549
389605644966361077867290379973073897271417449614939788000730910148473503528371060814157528868116901618729649", 10)
        result.Exp(result, &s)

- All applications of pairings we are aware of, use a product of pairings $e(P_1,Q_1) \times \dots \times e(P_n,Q_n) =^? 1$. So it does not matter if implementations output the very same result of each pairing or not as long as the properties are guaranteed.
- The EVM also implements the precompile in this same way. If someone calls the precompile with a single pair (which boils down to computing a single pairing) the precompile would fail anyway because it cannot be equal to 1 ($e$ is a non-degenerate map).
- There is no consensus issue. Consistance of EVM clients when implementing a single pairing does not matter as per the Ethereum yellow paper (p. 24)

- Maybe for ease of audit, one would like to have the exact same implementation accross clients. The question then is what variant to choose? The one with the smallest exponent but slower (2008) or the one with a bigger exponent but faster and more memory-efficient (2015)?
- The argument saying "the smallest exponent should be the canonical one" is not too convincing because for BLS12-381 all clients implement $s\cdot(p^{12}-1)/r$ with $s=3$.