多点打开证明

假设 $A, B, C, D$ 分别是多项式 $a (X), b (X), c (X), d (X)$ 的多项式承诺值。比如说，我们要打开多项式 $a, b$ 在点 $x$ 的取值，与此同时，打开 $c, d$ 在两个点 $x, ω x$ 的取值。（此处的 $ω$ 是乘法子群的本原单位根）。

比较容易想到的方法是，为每一个点构造一个多项式 $Q$ （每一个打开点就会对应电路中的一个相对转动（rotation））。但这不是一个有效的方法；比如， $c (X)$ 会出现在多个多项式中。

相反地，我们按打开点的集合，将多项式承诺值组织在一起： ${x} A B {x, ω x} C D$

对于每一个组，我们将这些多项式合并成一个多项式集合，然后构造一个多项式 $Q$ ，并在该点打开所有相对偏移。

优化步骤

多点打开的优化算法的输入为：

验证者采样出一个随机点 $x$ ，我们将计算多项式 $a (X), b (X), c (X), d (X)$ 在该点的值；
证明者计算出那些我们想要的多项式点值： $a (x), b (x), c (x), d (x), c (ω x), d (ω x)$ 。

这些数据是 vanishing证明的输出。

多点打开优化算法的步骤如下：

采样一个随机点 $x_{1}$ ，用来让 $a, b, c, d$ 线性无关；
对于每一个点集，将对应的多项式集合聚合成一个多项式，得到新的多项式集合 q_polys。

$q_{1} (X) q_{2} (X) = = a (X) c (X) + + x_{1} b (X) x_{1} d (X)$ 同理对于每一个点集，也计算出新的多项式点值集合 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，构造插值多项式集合 r_polys: $r_{1} (X) s . t . r_{2} (X) s . t . r_{1} (x) r_{2} (x) r_{2} (ω x) = = = a (x) + x_{1} b (x) c (x) + x_{1} d (x) c (ω x) + x_{1} d (ω x)$
构造 f_polys 来检查 q_polys 的正确性：

$f_{1} (X) f_{2} (X) = = \frac{q _{1} ( X ) - r _{1} ( X )}{X - x} \frac{q _{2} ( X ) - r _{2} ( X )}{( X - x ) ( X - ω x )}$

如果 $q_{1} (x) = r_{1} (x)$ ，则 $f_{1} (X)$ 应当是一个多项式；如果 $q_{2} (x) = r_{2} (x)$ 并且 $q_{2} (ω x) = r_{2} (ω x)$ ，则 $f_{2} (X)$ 应当是一个多项式。
采样一个随机数 $x_{2}$ ，用来让 f_polys 线性无关。
构造 $f (X) = f_{1} (X) + x_{2} f_{2} (X)$ 。
采样一个随机数 $x_{3}$ ，并计算 $f (X)$ 在该点的取值： $f (x_{3}) = = f_{1} (x_{3}) \frac{q _{1} ( x _{3} ) - r _{1} ( x _{3} )}{x _{3} - x} + + x_{2} f_{2} (x_{3}) x_{2} \frac{q _{2} ( x _{3} ) - r _{2} ( x _{3} )}{( x _{3} - x ) ( x _{3} - ω x )}$
采样一个随机数 $x_{4}$ ，用来让 $f (X)$ 和 q_polys 线性无关。
构造 final_poly多项式 \textrm{final_poly}(X) = f(X) + x_4 q_1(X) +x_4^2 q_2(X) final_poly多项式就是传入内积证明的多项式。

The halo2 Book

多点打开证明

优化步骤