Halo2 Part III, Inner product argument

In the halo2 protocol, we commit a polynomial and then evaluate, and later check whether the committed polynomial is the same as the evaluated one. To do this, the original halo2 by ZCash uses inner product argument. The main reference is [BCMS20] and [4.2] in halo2 book.

Assume that we have a polynomial $f(X)\in {\mathbb{F}}_p[X]$ of degree $d$, and $d+1$ is a power of 2. Let $\mathbb{G}$ be an additive group of prime order with DLP security. We randomly sampled nonzero $G_i\in \mathbb{G}$ for $0\le i\le d$. We also choose a random nonzero hiding factor $W,H\in \mathbb{G}$. For convenience, every vector notation denotes its vector form, for example, $\overrightarrow{G}=(G_i)$ and $\overrightarrow{f}=(m_i)$ if $f(X)=\sum _{i=0}^d{m}_i{X}^d$. And, $l$ and $r$ function make a vector into a half-lengthed vector which output the left half and right half respectively.

Commitment

To commit the polynomial $f(X)$, let $m_i$ be a $i$-th coefficient of $f$. The prover chooses a random $\xi \in {\mathbb{F}}_p$, and commits

$$C=\text{Commit}(f,\xi )=\sum _{i=0}^d{m}_i{G}_i+\xi W.$$

Note that this commitment is linear in $m_i$ and $\xi$.

Open and Check

In this stage, the prover evaluates $f(x)$ for some $x\in {\mathbb{F}}_p$ and makes an evaluation proof so that the verifier can check the evaluation is valid.

Let $v=f(x)$. The prover samples a random polynomial $\overline{f}(X)$ of degree $d$ with zero at $x$. This can be done by choosing a random polynomial of degree $d-1$ and multiplying $X-x$. Now, for a random $\overline{\xi }$, commit $\overline{f}$.

$$\overline{C}=\text{Commit}(\overline{f},\overline{\xi })$$

The verifier makes a random challenge $z,\overline{z}\in {\mathbb{F}}_p^{\times }$. Then, the prover sets

$$f^{\prime }(X)=f(X)-v+\overline{z}\overline{f}(X).$$

and commits $f^{\prime }$ by $C^{\prime }=⟨\overrightarrow{f^{\prime }},\overrightarrow{G}⟩$ without hiding factor. Now, we want to recursively reduce the size of the proof as in [BCCGP16]. Let $\overrightarrow{x}=(1,x,x^2,\dots ,x^{d-1})$. I'd like to emphasize that the prover wants to prove $⟨\overrightarrow{f^{\prime }},\overrightarrow{x}⟩=0$ and $⟨\overrightarrow{f^{\prime }},\overrightarrow{G}⟩=C^{\prime }$. For the first round, let ${\overrightarrow{G}}_0=\overrightarrow{G}$, ${\overrightarrow{x}}_0=\overrightarrow{x}$, and ${\overrightarrow{f^{\prime }}}_0=\overrightarrow{f^{\prime }}$. The prover sends

$$L_0=⟨r(\overrightarrow{f^{\prime }}),l(\overrightarrow{G})⟩+(z⟨r(\overrightarrow{f^{\prime }}),l(\overrightarrow{x})⟩)H+L_0^{\ast }W$$

$$R_0=⟨l(\overrightarrow{f^{\prime }}),r(\overrightarrow{G})⟩+(z⟨l(\overrightarrow{f^{\prime }}),r(\overrightarrow{x})⟩)H+R_0^{\ast }W$$

with random $L_0^{\ast }$ and $R_0^{\ast }$. The verifier makes a random challenge $u_0$. To make a half-lengthed proof, let

$$\overrightarrow{G_1}=l(\overrightarrow{G})+u_{0}r(\overrightarrow{G})$$

$$\overrightarrow{x_1}=l(\overrightarrow{x})+u_{0}r(\overrightarrow{x})$$

and the prover calculates new witness

$$\overrightarrow{f_1^{\prime }}=l(\overrightarrow{f^{\prime }})+u_0^{-1}r(\overrightarrow{f^{\prime }})$$

Since $⟨l(\overrightarrow{f^{\prime }}),l(\overrightarrow{x})⟩+⟨r(\overrightarrow{f^{\prime }}),r(\overrightarrow{x})⟩=0$ and $⟨l(\overrightarrow{f^{\prime }}),l(\overrightarrow{G})⟩+⟨r(\overrightarrow{f^{\prime }}),r(\overrightarrow{G})⟩=C^{\prime }$, direct computation yields

$$⟨\overrightarrow{f_1^{\prime }},{\overrightarrow{x}}_1⟩=u_0⟨r(\overrightarrow{f^{\prime }}),l(\overrightarrow{x})⟩+u_0^{-1}⟨l(\overrightarrow{f^{\prime }}),r(\overrightarrow{x})⟩,$$

$$⟨{\overrightarrow{f^{\prime }}}_1,\overrightarrow{G_1}⟩=C^{\prime }+u_0⟨r(\overrightarrow{f^{\prime }}),l(\overrightarrow{G})⟩+u_0^{-1}⟨l(\overrightarrow{f^{\prime }}),r(\overrightarrow{G})⟩,$$

and

$$z⟨\overrightarrow{f_1^{\prime }},\overrightarrow{x_1}⟩H+⟨\overrightarrow{f_1^{\prime }},\overrightarrow{G_1}⟩=C^{\prime }+u_0{L}_0+u_0^{-1}{R}_0-(u_0{L}_0^{\ast }+u_0^{-1}{R}_0^{\ast })W.$$

By applying this process for $m+1=\log (d+1)$ rounds, the last $\overrightarrow{G_m}$, $\overrightarrow{x_m}$, and $\overrightarrow{f_m^{\prime }}$ is just length-one vectors. By accumulating calculations,

$$z\overrightarrow{f_m^{\prime }}\overrightarrow{x_m}H+\overrightarrow{f_m^{\prime }}\overrightarrow{G_m}=C^{\prime }+\sum _{j=0}^{m-1}(u_j{L}_j+u_j^{-1}{R}_j)-\sum _{j=0}^{m-1}(u_j{L}_j^{\ast }+u_j^{-1}{R}_j^{\ast })W.$$

The prover sent each $L_j$ and $R_j$ for each round, and lastly send witness $\overrightarrow{f_m^{\prime }}$ and blinding factors $L_j^{\ast }$ and $R_j^{\ast }$. Then, the verifier accepts only if the above equation holds.

Multipoint opening argument

We explained how to check evaluation for one polynomial $f(X)$. However, in the halo2 protocol, we use multiple polynomials corresponding to each column and multiple evaluations corresponding to each rotation. To check several evaluations work well with commitments efficiently, halo2 uses a multipoint opening argument.

Let's explain this using an example. What the prover committed is a set of polynomials and rotated polynomials. Say $a_i(X)$ for $0\le i\le 8$, $a_i(\omega X)$ for $3\le i\le 8$, and $a_i({\omega }^{2}X)$ for $6\le i\le 8$ are committed. We can group $\{a_i\}$ by which rotations are used. That is, non-rotated $\{a_0(X),a_1(X),a_2(X)\}$ are group one, $\{a_3(X),a_4(X),a_5(X)\}$ are group two, and $\{a_6(X),a_7(X),a_8(X)\}$ are group three. For each group, let

$$q_1(X)=a_0(X)+x_1{a}_1(X)+x_1^2{a}_2(X)$$

$$q_2(X)=a_3(X)+x_1{a}_4(X)+x_1^2{a}_5(X)$$

$$q_3(X)=a_6(X)+x_1{a}_7(X)+x_1^2{a}_8(X)$$

where $x_1$ is a random challenge given by the verifier. Now, calculate an interpolation polynomial for each group. Recall that $x$ is a random challenge. $r_1(X)$ interpolates $(x,q_1(x))$. $r_2(X)$ interpolates $(x,q_2(x))$ and $(\omega x,q_2(\omega x))$, and $r_3(X)$ interpolates $(x,q_3(x)),(\omega x,q_3(\omega x)),({\omega }^{2}x,q_3({\omega }^{2}x))$.

Next, the prover computes

$$f_1(X)=\frac{q_1(X)-r_1(X)}{X-x}$$

$$f_2(X)=\frac{q_2(X)-r_2(X)}{(X-x)(X-\omega x)}$$

$$f_3(X)=\frac{q_3(X)-r_3(X)}{(X-x)(X-\omega x)(X-{\omega }^{2}x)}$$

and for random $x_2$ given by the verifier, the prover computes

$$f(X)=f_1(X)+x_2{f}_2(X)+x_2^2{f}_3(X).$$

The verifier makes a random challenge $x_3$, then the prover sends evaluations $q_i(x_3)$. After receiving, the verifier sends a challenge $x_4$ again. Then, we use the inner product argument with

$$f_{\text{final}}(X)=f(X)+x_4{q}_1(X)+x_4^2{q}_2(X)+x_4^3{q}_3(X).$$

You can find the full process of halo2 using IPA here. I tried to use consistent notation from there.