# Where & how is the 2nd group used in the KZG Commitment Scheme in case the 2 groups are not the same?

This is about the KZG Polynomial Commitment Scheme

In Section 2, it's written

We use the notation $$e : \mathbb G \times \mathbb G \mapsto \mathbb G_T$$ to denote a symmetric (type 1) bilinear pairing.The choice of type 1 pairings was made to simplify presentation, however, our constructions can easily be modified to work with pairings of types 2 and 3 as well.

The above uses only one Elliptic Curve Group whose generator $$\mathbb G$$.

In the appendix where the document describes Bilinear Pairings, this is the description.

For three cyclic groups $$\mathbb G,\widehat{\mathbb G}$$ and $$\mathbb G_T$$ (all of which we shall write multiplicatively) of the same prime order $$p$$, a bilinear pairing $$e$$ is a map $$e : \mathbb G \times \widehat{\mathbb G} \mapsto \mathbb G_T$$

Note that here 2 different elliptic curve groups $$\mathbb G$$ & $$\widehat{\mathbb G}$$ respectively are used (instead of $$\mathbb G$$ being used as both the first & second group in the earlier description).

And this is not just for type 1 pairings, but all 3 types of pairings can have different generators.

I am a little confused about how the proof would work if the 2 generators were different.

For e.g. if we have to prove

$$Q(x) = \frac {F(x) - c} {x-b}$$,

This is how we do it.

$$Q(x)(x-b) = F(x) -c$$

Evaluating at $$x=a$$

$$Q(a)(a-b) = F(a) - c$$

Now we multiply both sides by $$G$$ (which is the generator of the group $$\mathbb G$$ & this becomes

$$Q(a).G.(a-b) = F(a).G - c$$

Now $$C_Q = Q(a).G$$ (commitment of $$Q$$) &

$$C_F = F(a).G$$ (commitment of $$F$$)

From here, it's easy to prove that if $$e(Q(a)G, (a-b)G) \stackrel{?}{=} e((F(a)-c)G, G)$$ is true, then the original statement $$Q(x)(x-b) = F(x) -c$$ is true. (This proof is also given in the KGZ paper in multiplicative notation). However, I am not able to derive the proof for $$G_1 \ne G_2$$ - how do I derive the proof for the above in case I am using two different groups with generators $$G_1$$ & $$G_2$$.

Now this easy converting of a polynomial into it's commitment by multiplying both sides by the single generator is key to using pairings to prove without knowing the polynomial itself.

I am not sure how this translates to the two groups being different $$\mathbb G$$ & $$\widehat{\mathbb G}$$ because they would then have different generators & you won't be able to multiply both sides by the same generator to convert the polynomial into it's commitment so as to verify a proof without knowing the polynomial itself (and just knowing the SRS).

So where exactly is the generator of the 2nd Group $$\widehat{\mathbb G}$$ used & how does one convert the polynomials into their respective commitments in that case.

Pairings allow to do "multiplications in the exponent". Therefore, a good candidate for where $$G_2$$ comes in is where there's multiplication. The winner is $$Q(x)(x-b) = F(x) -c.$$ The polynomial equality required for verification can be computed by: $$e(Q(a)G_1, (a-b)G_2) \stackrel{?}{=} e((F(a)-c)G_1, G_2).$$

Correctness: Assuming $$e(Q(a)G_1, (a-b)G_2) = e((F(a)-c)G_1, G_2),$$

then, by the bi-linearity of the pairing we have $$Q(a)*(a-b)e(G_1, G_2) = (F(a) - c)e(G_1, G_2).$$ Which holds if and only if $$Q(a)(a-b) = F(a) - c$$ (over the appropriate field) as desired.

This version of the KZG in the asymmetric paring setting requires that the setup algorithm produces $$aG_2$$ as well.

• I can prove that if $e(Q(a)G, (a-b)G) \stackrel{?}{=} e((F(a)-c)G, G)$ is true, then the original statement $Q(x)(x-b) = F(x) -c$ is true - note that I am using $G_1 = G_2$ - this proof is given in the KGZ paper & it can be proven easily. However, I am not able to derive the proof for $G_1 \ne G_2$ - that's my question. Aug 21, 2023 at 0:18
• The proof is generally the same. We just need to use the bilinearity of the pairing. I'll develop this later. Aug 21, 2023 at 5:59
• But in the case where $G_1 = G_2 = G$, converting the polynomial into a commitment involves multiplying both sides of the equation to be proved with $G$ at $x = a$ which converts the polynomial into a commitment of the polynomial - i.e. if there is a $Q(x)$ on one side then $Q(a).G$ is the commitment of the Polynomial $Q$. How would you do this if $G_1 \ne G_2$? Aug 21, 2023 at 6:10
• As written in the answer any commitment is computed with $G_1$. In other words, polynomial evaluation at $a$ will use group elements from the first group. But that is a separate question than Correctness. Aug 21, 2023 at 6:39
• I understand that commitments will use $G_1$. My question is about proof of correctness. I am able to derive proof of correctness when $G_1 = G_2$. I am unable to derive the same when $G_1 \ne G_2$ Aug 21, 2023 at 6:41