Cryptographic Pairings for zk-snarks | Guide for lazy people

Introduction

Pairings are mathematical tools that allow efficient verification of certain cryptographic properties without revealing any additional information to the other party. Verifiers rely on cryptographic pairings because pairings enable efficient and secure verification of complex algebraic relationships, particularly those arising from polynomial commitments without knowing the underlying polynomial's coefficients thus satisfying the zero knowledge property.

Pairings are used in commitment schemes, where the Prover commits to certain values (e.g., polynomials) without revealing them.

• The Verifier uses pairings to ensure the commitments are consistent with the proof and the public inputs.

• For example, pairings verify that a committed polynomial satisfies certain algebraic constraints.

• Bilinear pairings enable Verifiers to detect forgery or invalid proofs by enforcing algebraic consistency.

Homomorphism

Let’s take an example,

$$$
200 \space G+275 \space G = 475 \space G
$$$

$$$
\begin{align*}
& A = 200 \space G \
& B = 275 \space G \
& C = 475 \space G
\end{align*}
$$$

If I want to calculate what C is, there are two possible ways to do so.

Method 1 :

First calculate $$ 200 \times G = A$$ then $$275 \times G = B$$ and finally do $$A+B = 475 \space G = C$$.

Method 2 :

First calculate $$200 + 275 = 475$$ then do $$475 \times G = C$$

If you perform scalar multiplication first and then addition (Method 1), or addition first and then scalar multiplication (Method 2), both methods produce the same result. This property is why elliptic curve groups are said to be homomorphic under addition.

Example 1

The Prover calculates A and B, then sends A, B, and G to the Verifier. The Verifier computes A + B and returns C to the Prover. The advantage here is that the Verifier can do proper computation without knowing the underlying secret values.

Example 2

The Prover calculates A and B, then adds them together to obtain a new value C. The Prover then asks the Verifier to confirm whether A + B indeed equals C.

Both Example 1 and 2 are homomorphic under addition but are they homomorphic under multiplication ?

Calculating $$D$$ such that $$D = (200 \times 275) G$$ by multiplying $$A \times B$$ won’t work because we cannot multiply two elliptic curve points. We say this is not homomorphic under multiplication.

The only way we can calculate D is if we first multiply $$200 \times 275$$ then multiply the result with G.

Fully Homomorphic = homomorphic under addition and homomorphic under multiplication

Providing the Verifier with A and B alone does not allow them to compute D under multiplication. Therefore, similarly to example 2, where 200 and 275 remain secret, the Prover computes A, B, and D and sends them to the Verifier. Using elliptic curve pairings, the Verifier can then verify that $$A \times B = D$$.

Definition

Cryptographic pairings are special mathematical functions that map two group elements into a target group. Formally, a pairing $$e$$ is a function:

$$$
e : G_1 \times G_2 \rightarrow G_T
$$$

where $$G_1$$, $$G_2$$, and $$G_T$$ are groups, and the function 𝑒 satisfies the following properties:

• Bilinearity:

  For all $$a,b \in \mathbb{Z}$$, $$P \in G_1, Q \in G_2$$ :

  $$$
  e(aP,bQ)=e(P,Q)^{ab}
  $$$

• Non-degeneracy:

  If $$𝑃 ≠ 0$$ and $$𝑄 ≠ 0$$, then $$𝑒 ( 𝑃 , 𝑄 ) ≠ 1$$ . This ensures the pairing provides useful information.

• Computability/Efficiency:

  There exists an efficient algorithm to compute $$e(P,Q)$$ for all $$P \in G_1, Q \in G_2$$.

Note that $$G_1$$ and $$G_2$$ are elliptic curve groups and $$G_T$$ isn’t.

Elliptic Curve Pairings

A pairing on $$(G_1,G_2,G_T)$$ defines the function $$e : G_1 \times G_2 \rightarrow G_T$$, and where $$g_1$$ is a generator for $$G_1$$ and $$g_2$$ is a generator for $$G_2$$. If we have the points of $$\color{lightblue}U_1$$ and $$\color{lightblue}U_2$$ on $$\color{lightblue}G_1$$ and $$\color{pink}V_1$$ and $$\color{pink}V_2$$ on $$\color{pink}G_2$$, we get the bilinear mapping of:

$$$
\begin{align*}
& e(U_1+U_2,V_1)=e(U_1,V_1) \times e(U_2,V_1) \
& e(U_1,V_1+V_2)=e(U_1,V_1) \times e(U_1,V_2)
\end{align*}
$$$

If $$\color{lightblue}U$$ is a point on $$\color{lightblue}G_1$$, $$\color{pink}V$$ is a point on $$\color{pink}G_2$$ and $$\color{orange}a,b$$ are scalars, we get:

$$$
e(\textcolor{orange}{a}U,\textcolor{orange}{b}V)=e(U,V)^{\textcolor{orange}{ab}} = e(\textcolor{orange}{ab}U,V) = e(U,\textcolor{orange}{ab}V)
$$$

If $$G_1$$ and $$G_2$$ are the same group, we get a symmetric grouping $$(G_1=G_2=G)$$, and the following commutative property will apply:

$$$
e(U^{\textcolor{orange}{a}},V^{\textcolor{orange}{b}})=e(U^{\textcolor{orange}{b}},V^{\textcolor{orange}{a}})=e(U,V)^{\textcolor{orange}{ab}} = e(V,U)^{\textcolor{orange}{ab}}
$$$