1
$\begingroup$

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. enter image description here

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Sir/Madam, from the parameters in verification key i.e., { g^α, g^t(s) }, it is assumed they are integers. g^p is also some number. Now, we need to compare and verify that g^p = (g^h)^t(s). But, as we see in verification key, we got g^t(s) not t(s) alone. $\endgroup$ May 1, 2023 at 8:13
  • $\begingroup$ @INDUKURIMANIVARMA21911012 You don't need $t(s)$ - if you verify $g^a = g^{b\star c}$, then it means $a = b \star c$. Check Page 15 of Maksym's doc - $g^p = ({g^h})^{t(s)}$ ==> $g^p = g^{t(s)\cdot h}$ ==> $p = t(s)\cdot h$ $\endgroup$
    – user93353
    May 1, 2023 at 8:20
  • $\begingroup$ Sir, you mean the setup phase is run by the verifier only ? It means verifier knows t(s) beforehand. $\endgroup$ May 1, 2023 at 8:27
  • $\begingroup$ Both verifier & prover know $t(x)$. And since verifier also knows $s$, he can calculate $t(x=s)$. $\endgroup$
    – user93353
    May 1, 2023 at 8:34
  • $\begingroup$ @INDUKURIMANIVARMA21911012 - I have added a link in the answer about Elliptic Curve Pairings which explains Pairings & also how they help to check equalities even if you do not know the values themselves. SNARKs uses Elliptic Curve pairings as the bilinear maps $\endgroup$
    – user93353
    May 1, 2023 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.