译自 halo2 book:https://zcash.github.io/halo2/design/proving-system/multipoint-opening.html

多点打开论证(Multipoint opening argument)

考虑对多项式 $a(X),b(X),c(X),d(X)$ 的承诺 $A,B,C,D$。假设 $a$ 和 $b$ 在点 $x$ 处被查询,而 $c$ 和 $d$ 在 $x$ 与 $\omega x$ 两个点处都被查询。(这里,$\omega$ 是我们用来构造这些多项式的乘法子群中的本原单位根(primitive root of unity)。)

为了打开(open)这些承诺,我们可以为每个查询的点(对应电路中使用的每个相对旋转)创建一个多项式 $Q$。但这在电路中并不高效;例如,$c(X)$ 会出现在多个多项式中。

我们改为按照查询点的集合对承诺进行分组: $$\begin{array}{ccccc}& \{x\}& & \{x,\omega x\}& \\ & A& & C& \\ & B& & D& \end{array}$$

对于这些分组中的每一个,我们把它们合并成一个多项式集合,并为该集合创建单个 $Q$,然后在每个旋转处打开它。

优化步骤

多点打开优化以下列内容作为输入:

• 由验证者采样的随机 $x$,我们在该点对 $a(X),b(X),c(X),d(X)$ 求值。
• 由证明者提供的、每个多项式在每个相关点处的求值: $a(x),b(x),c(x),d(x),c(\omega x),d(\omega x)$

这些是消失论证(vanishing argument)的输出。

多点打开优化按如下方式进行:

1. 采样随机 $x_1$,以保持 $a,b,c,d$ 线性无关。

2. 根据多项式被查询时所在的点集,累加多项式及其对应的求值: q_polys: $$\begin{array}{rcclc}{q}_1(X)& =& a(X)& +& x_{1}b(X)\\ q_2(X)& =& c(X)& +& x_{1}d(X)\end{array}$$ q_eval_sets:

           [
               [a(x) + x_1 b(x)],
               [
                   c(x) + x_1 d(x),
                   c(\omega x) + x_1 d(\omega x)
               ]
           ]
   

   注:q_eval_sets 是一个由求值集合构成的向量,其中外层向量对应点集(本例中为 $\{x\}$ 和 $\{x,\omega x\}$),内层向量对应每个集合中的点。

3. 对 q_eval_sets 中的每个值集合做插值(interpolate): r_polys: $$\begin{array}{cccc}{r}_1(X)s.t.& & & \\ & r_1(x)& =& a(x)+x_{1}b(x)\\ r_2(X)s.t.& & & \\ & r_2(x)& =& c(x)+x_{1}d(x)\\ & r_2(\omega x)& =& c(\omega x)+x_{1}d(\omega x)\end{array}$$

4. 构造 f_polys,用于检查 q_polys 的正确性: f_polys $$\begin{array}{rcl}{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)}\end{array}$$

   如果 $q_1(x)=r_1(x)$,那么 $f_1(X)$ 应当是一个多项式。 如果 $q_2(x)=r_2(x)$ 且 $q_2(\omega x)=r_2(\omega x)$, 那么 $f_2(X)$ 应当是一个多项式。

5. 采样随机 $x_2$ 以保持 f_polys 线性无关。

6. 构造 $f(X)=f_1(X)+x_2{f}_2(X)$。

7. 采样随机 $x_3$,我们在该点对 $f(X)$ 求值: $$\begin{array}{rcccl}f(x_3)& =& f_1(x_3)& +& x_2{f}_2(x_3)\\ & =& \frac{q_1(x_3)-r_1(x_3)}{x_3-x}& +& x_2\frac{q_2(x_3)-r_2(x_3)}{(x_3-x)(x_3-\omega x)}\end{array}$$

8. 采样随机 $x_4$ 以保持 $f(X)$ 与 q_polys 线性无关。

9. 构造 final_poly,$$final\_poly(X)=f(X)+x_4{q}_1(X)+x_4^2{q}_2(X),$$ 这就是我们在内积论证(inner product argument)中要承诺的多项式。