Elliptic Curve Pairings

Elliptic curve pairings play an important role in Ethereum’s Proof of Stake and in proof systems such as Groth16 and Plonk. They allow us to perform some sort of encrypted multiplication, crucial to aggregatable signatures and some polynomial commitment schemes. However, pairings seem shrouded in mystery and complexity. Read on if you want to learn more!

Let's explore type 3 pairings, which are widely used in applications. These functions take two elements from different groups in the elliptic curve, G1 and G2, both of size r, and produce an element from a subgroup of an extension field, also of size r. Mathematically, we can represent the pairing as e: G1 x G2 → Gt, with the result denoted as e( x , y ).

The key properties for pairings are:

1. Bilinearity: given x,z from G1, e(x + z,y)=e(x,y)e(z,y) and given y,z from G2, e(x,y+z)=e(x,y)e(x,z).
2. Non-degeneracy: e(x,y) is different from 1 unless x or y are the point at infinity.

Pairings provide additional structure to elliptic curves. Originally, they were thought of as a problem for elliptic curves, since they provide a way to transform the discrete log problem over the curve into a problem over (an extension of) the integers. Later, it was found that they could be useful to build cryptographic applications.

To compute the pairing, one needs to find at least two groups of order/size r. To do so, we have to work over extension fields. The smallest extension that contains all points r corresponds to k>0 such that r divides p^k - 1. We call k the embedding degree of the curve. For BN254 and BLS12-381, the embedding degree is 12. We can think of elements over the degree 12 extension of the base field as a vector of 12 coordinates with a special multiplication operation.

A higher embedding degree means that the pairing’s computation is more expensive. So, in terms of computational time, we would like it to be as small as possible. However, if the embedding degree is too low, breaking the discrete log problem is easier. In practice, 12 seems a common choice, balancing the trade-off between speed and security. Luckily, there are a couple of tricks we can use to make computations even easier.

Until 1985, there was no efficient algorithm to compute elliptic curve pairings. Miller provided the first algorithm, consisting of two steps: the Miller loop and the final exponentiation. Gas costs for pairings in the EVM are 45,000 + 34,000k, with k as the number of pairs. The first part corresponds to the exponentiation, and the second is related to the Miller loop. In practice, this implies that if we have to check the equality between two pairings, we can compute it for just 113,000 gas.

If you want to learn more about pairings, check out this content by LambdaClass and this by Mamy Ratsimbazafy.

Stay tuned:  🐦 Twitter | 🗨️ Telegram | 👾 Discord | 🌐 Website | 🌌 Galxe | 📝 Manifesto