Generalized inner product argument

$$This is a summary of [BMMTV19]. In the previous post, we introduced the inner product argument which recursively reduces the size of the witness. In [BMMTV19], they extend this argument to general inner products with some assumptions, which is called GIPA.

Generalized inner product argument (GIPA)

Let's define the desired properties of our inner products and commitment scheme. Let $K$ be a commitment key space, $M$ be a message space, and $C$ be a commitment space. We need all the spaces $K,M,C$ to be abelian groups, and $\mathrm{CM}(\cdot ;\cdot ):K\times M\to C$ to be a bilinear commitment scheme. For example, in the previous post, $K={\mathbb{G}}^n,M={\mathbb{F}}_p^n,C=\mathbb{G}$ and $\mathrm{CM}(\mathbf{g};\mathbf{a})=\sum a_i{g}_i$. Next, we define an inner product $\odot :M_1\times M_2\to M_3$ on abelian message spaces. We abuse notation for Cartesian products, that is, $\odot :M_1^n\times M_2^n\to M_3$ is defined by $(a_i)\odot (b_i)=\sum a_i\odot b_i$. For example, in the previous post, $M_1=M_2={\mathbb{F}}_p$ and $\odot$ is a field multiplication.

Like the inner product argument, we want to reduce the size of messages for each round. Suppose we have a series of commitment schemes. That is, for each $n=2^j$, we have

$${\mathrm{CM}}_n:(K_1^n\times K_2^n\times K)\times (M_1^n\times M_2^n\times M_3)\to C_n$$

Here, $K_1,K_2,K_3,M_1,M_2,M_3$ are groups of order $p$. The collapse function is a series of functions ${\mathrm{Collapse}}_n:C_{2n}\to C_n$ such that

$${\mathrm{Collapse}}_n({\mathrm{CM}}_{2n}(k_1||k_1^{\prime },k_2||k_2^{\prime },k_3;m_1||m_1,m_2||m_2,m_3))={\mathrm{CM}}_n(k_1+k_1^{\prime },k_2+k_2^{\prime },k_3;m_1,m_2,m_3)$$

Given such a series of commitments and a collapse function, the goal of GIPA is to prove that

$$C={\mathrm{CM}}_n(k_1,k_2,k_3;\mathbf{a},\mathbf{b},\mathbf{a}\odot \mathbf{b}).$$

Here, $\mathbf{a}\in M_1^n$ and $\mathbf{b}\in M_2^n$ are witnesses the prover has, and they are committed using the commitment keys $k_1,k_2,k_3$ by $C$. The process is similar to the previous post. First, the prover sends a new commitment

$$C_L={\mathrm{CM}}_n(k_1,k_2,k_3;l(\mathbf{a})||0,0||r(\mathbf{b}),l(\mathbf{a})\odot r(\mathbf{b}))$$

$$C_R={\mathrm{CM}}_n(k_1,k_2,k_3;0||r(\mathbf{a}),l(\mathbf{b})||0,r(\mathbf{a})\odot l(\mathbf{b}))$$

Then, the verifier makes a random challenge $x\in {\mathbb{F}}_p^{\times }$. With the new commitment keys and new witnesses

$$k_1^{\prime }=r(k_1)+x^{-1}l(k_1),$$

$$k_2^{\prime }=r(k_2)+xl(k_1),$$

$${\mathbf{a}}^{\prime }=r(\mathbf{a})+xl(\mathbf{a}),$$

$${\mathbf{b}}^{\prime }=r(\mathbf{b})+x^{-1}l(\mathbf{a}),$$

the prover now wants to prove that

$${\mathrm{CM}}_{\frac{n}{2}}(k_1^{\prime },k_2^{\prime },k_3;{\mathbf{a}}^{\prime },{\mathbf{b}}^{\prime },{\mathbf{a}}^{\prime }\odot {\mathbf{b}}^{\prime })={\mathrm{Collapse}}_n(x{C}_L+C+x^{-1}{C}_R)$$

The size of the witnesses becomes half, and one can show that the correctness of the first commitment implies the last equation using bilinearity of commitment and collapse property. Also, the converse is true for high probability. Continuing this process, we can reduce the size of witnesses to $n=1$, and then send them to the verifier.

Reduce verifier time using KZG

A problem of GIPA is that the verifier should compute new commitment keys $k_1^{\prime },k_2^{\prime }$ for each round. Some special commitment scheme allows removing these calculations. Instead of computing each commitment key, the verifier believes the prover is using valid commitment keys for each round. Then, the verifier checks all the commitment keys are valid simultaneously using the KZG commitment scheme. The special property is that the first commitment key $k_1$ is of the form

$$\mathbf{g}=(g,g^{\alpha },\cdots ,g^{{\alpha }^{n-1}})\in {\mathbb{G}}_1^n$$

In order to prove each commitment key is valid, it's enough to prove that the final commitment key $v$ equals to

$$g^{\prod _{j=0}^{\log n}(1+x_j{\alpha }^{j+1})}$$

where $x_j$ is the $(\log n-j)$th challenge in GIPA. Similarly, this can be applied to $k_2$ with $x_j^{-1}$ instead of $x_j$. To prove this, we can use the KZG commitment scheme. Let

$$f(X)=\prod _{j=0}^{\log n}(1+x_j{\alpha }^{j+1}).$$

Using KZG, the prover can show that $g^f(\alpha )=v$ efficiently.

Application

As an application, I will introduce the TIPP protocol. Let ${\mathbb{G}}_1=⟨g⟩,{\mathbb{G}}_2=⟨h⟩,{\mathbb{G}}_T$ be cyclic groups of order $p$, and $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$ be a non-degenerate bilinear pairing. You may think of these as paring-friendly curve groups for example. Let ${\mathbf{g}}^{\alpha }=(g,g^{\alpha },\dots ,g^{{\alpha }^{n-1}})\in {\mathbb{G}}_1^n$ be a trusted setup, and ${\mathbf{h}}^{\beta }\in {\mathbb{G}}_2^n$ similarly. The prover has witnesses $A\in {\mathbb{G}}_1^n$ and $B\in {\mathbb{G}}_2^n$, and commits them using $T=⟨A,{\mathbf{h}}^{\beta }⟩$ and $U=⟨{\mathbf{g}}^{\alpha },B⟩$. After commitment, the verifier chooses a random challenge $r\in \mathbb{F}$. The prover wants to prove that $(A\cdot B{)}^{\mathbf{r}}=\prod _{i=0}^{m-1}e(A_i,B_i{)}^{r^i}$ equals known $Z$ and the commitments are valid.

Note that the commitment scheme is bilinear, and the inner product is defined by pairing $e$. For each round, the commitment belongs to the same ${\mathbb{G}}_T$, so we can choose the collapse function as identity. Now, the prover and verifier can use GIPA with two commitment keys and two witnesses

$$(g,g^{(r^{-1}\alpha },\dots ,g^{r^{-(n-1)}{\alpha }^{n-1}}),(h,h^{\beta },\dots ,h^{{\beta }^{n-1}})$$

$$(A_0,A_1^r,\dots ,A_{n-1}^{r^{n-1}}),(B_0,B_1,\dots ,B_{n-1})$$

Since the first commitment keys are the desired form, the verifier needs not to compute each commitment key but needs to check final commitment keys are valid using KZG.