How exactly bilinear pairing multiplication in the exponent of g is used in zk-SNARK polynomial verification step?

Question

I am reading this explanation of zkSnark written by Maksym Petkus - https://arxiv.org/pdf/1906.07221.pdf

In page 24, the zk-SNARK of polynomial is explained. In setup phase, the proving and verification keys are created by a trusted setup. I understood how proof is created using the proving key.

However, if we see the verification key = ${ g^α, g^t(s) }$, I didn't get how it is used in verification phase.

The steps in verification phase are as follows.

In step $e(g^{p'}, g) = e(g^p, g^α)$, what operations are performed for this check ? I am assuming $g^{p'} = (g^p)^α$. To do this, I don't know α. I only know $g^α$ from verification in terms of integers.

Same doubt for polynomial cofactors check also, I know $g^{t(s)}$ from verification key but not $t(s)$. How does this check happen ? I am assuming the verifier doesn't have access to setup phase.

Please help me.

Answer 1

A Bilinear Pairing has many properties including

$e(A^\alpha, B) = e(A, B^\alpha) = {e(A, B)}^{\alpha}$ (where $\alpha$ is a scalar)

i.e. you can move the exponent of the left hand side term to the right hand side or you can move it outside of the $e$ map itself.

(In your example, $A = B$)

---

Polynomial Restriction Check

The verifier needs to check if $p' = p^\alpha$

This can be checked by checking if

$g^{p'} \stackrel {?}{=} g^{p^\alpha}$

Let $m = g^p$.

So, the check becomes

$g^{p'} \stackrel {?}{=} m^\alpha$

Using Bilinear Pairings,

$e(g^{p'}, g) \stackrel {?}{=} e(m^\alpha, g)$

As per the properties of bilinear pairings, the $\alpha$ can be moved to the other side, so

$e(g^{p'}, g) = e(m, g^\alpha) = e(g^p, g^\alpha)$

So he needs to check if

$e(g^{p'}, g) \stackrel {?}{=} e(g^p, g^\alpha)$$

If the above check is true, then it means

$p' = p^\alpha$

---

Cofactors check

The verifier needs to check if $p = t(s)\star h$

This will be true if

$e(g^p, g) = e(g^{t(s)\star h}, g)$

Now, since $x^{a\star b} = x^{a^b}$

$e(g^p, g) = e(g^{{t(s)}^ h}, g)$

Again as per the properties of Bilinear Pairings, the $h$ can be moved to the 2nd parameter, i.e. the verifier needs to check

$e(g^p, g) \stackrel {?}{=} e(g^{t(s)}, g^h)$

If the above is true, then it means

$p = t(s)\star h$

---

Vitalik's post on Pairings gives more info about how you can check equalities with pairings

https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

I have rewritten a statement from his post in multiplicative notation

Pairings go a step further in that they allow you to check certain kinds of more complicated equations on elliptic curve points — for example, if $P = g ^ p$, $Q = g ^ q$ and $R = g ^ r$, you can check whether or not $p \star q = r$, having just $P$, $Q$ and $R$ as inputs.