Halo2 学习笔记——设计之Proving system之Multipoint opening argument（5）

1. 引言

假设 A , B , C , D A,B,C,D A,B,C,D分别对应多项式 a ( X ) , b ( X ) , c ( X ) , d ( X ) a(X), b(X), c(X), d(X) a(X),b(X),c(X),d(X)的commitment。 假设 a ( X ) , b ( X ) a(X), b(X) a(X),b(X) are queried at point x x x， c ( X ) , d ( X ) c(X), d(X) c(X),d(X) are queried at point x x x和 ω x \omega x ωx。（此处， ω \omega ω为the primitive root of unity in the multiplicative subgroup over which we constructed the polynomials。）

为了open这些commitments，可构建多项式 Q Q Q for each point that queried at（对应为circuit中的每个relative rotation），但是这样的circuit效率并不开，如 c ( X ) c(X) c(X)将在多个多项式中出现。

相反，可将commitments和queried points 进行分组： { x } { x , ω x } A C B D \begin{array}{cccc} &\{x\}& &\{x, \omega x\}& \\ &A& &C& \\ &B& &D& \end{array} ​{x}AB​​{x,ωx}CD​​

对于每组，可combine为a polynomial set，然后create a single Q Q Q for that set，which we open at each rotation。

2. Optimization steps

multipoint opening optimization 的输入有：

• 由Verifier提供的随机值 x x x，基于该随机值来evaluate a ( X ) , b ( X ) , c ( X ) , d ( X ) a(X), b(X), c(X), d(X) a(X),b(X),c(X),d(X)。
• 在每个point每个多项式的evaluations值，由Prover提供： a ( x ) , b ( x ) , c ( x ) , d ( x ) , c ( ω x ) , d ( ω x ) a(x), b(x), c(x), d(x), c(\omega x), d(\omega x) a(x),b(x),c(x),d(x),c(ωx),d(ωx)

这些都是vanishing argument的输出。

multipoint opening optimization的处理流程为：

• 1）引入随机值 x 1 x_1 x1​，来keep a , b , c , d a,b,c,d a,b,c,d linearly independent。
• 2）Accumulate polynomials and their corresponding evaluations according to the point set at which they were queried： q_polys: q 1 ( X ) = a ( X ) + x 1 b ( X ) q 2 ( X ) = c ( X ) + x 1 d ( X ) \begin{array}{rccl} q_1(X) &=& a(X) &+& x_1 b(X) \\ q_2(X) &=& c(X) &+& x_1 d(X) \end{array} q1​(X)q2​(X)​==​a(X)c(X)​++​x1​b(X)x1​d(X)​ q_eval_sets:【为a vector of sets of evaluations，其中最外层vector对应为polynomial sets，最里层vector对应为evaluation of point sets in each polynomial set。】

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

• 3） 对q_eval_sets中每个set of values进行插值： r_polys: 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 ( ω x ) = c ( ω x ) + x 1 d ( ω x ) \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} r1​(X)s.t.r2​(X)s.t.​r1​(x)r2​(x)r2​(ωx)​===​a(x)+x1​b(x)c(x)+x1​d(x)c(ωx)+x1​d(ωx)​
• 4）构建f_polys来check q_polys的正确性：【注意，f_polys为witness，需进行blind commit，详细可参看 实际代码实现。】 f_polys f 1 ( X ) = q 1 ( X ) − r 1 ( X ) X − x f 2 ( X ) = q 2 ( X ) − r 2 ( X ) ( X − x ) ( X − ω x ) \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} f1​(X)f2​(X)​==​X−xq1​(X)−r1​(X)​(X−x)(X−ωx)q2​(X)−r2​(X)​​ 若 q 1 ( x ) = r 1 ( x ) q_1(x) = r_1(x) q1​(x)=r1​(x), 则 f 1 ( X ) f_1(X) f1​(X)应为 a polynomial. 若 q 2 ( x ) = r 2 ( x ) q_2(x) = r_2(x) q2​(x)=r2​(x) 且 q 2 ( ω x ) = r 2 ( ω x ) q_2(\omega x) = r_2(\omega x) q2​(ωx)=r2​(ωx) 则 f 2 ( X ) f_2(X) f2​(X) 应为 a polynomial.
• 5）Sample random x 2 x_2 x2​ 来keep f_polys linearly independent。
• 6）构建 f ( X ) = f 1 ( X ) + x 2 f 2 ( X ) f(X)=f_1(X)+x_2f_2(X) f(X)=f1​(X)+x2​f2​(X)。
• 7）Sample random x 3 x_3 x3​，用于evaluate f ( X ) f(X) f(X)： f ( x 3 ) = f 1 ( x 3 ) + x 2 f 2 ( x 3 ) = q 1 ( x 3 ) − r 1 ( x 3 ) x 3 − x + x 2 q 2 ( x 3 ) − r 2 ( x 3 ) ( x 3 − x ) ( x 3 − ω 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} f(x3​)​==​f1​(x3​)x3​−xq1​(x3​)−r1​(x3​)​​++​x2​f2​(x3​)x2​(x3​−x)(x3​−ωx)q2​(x3​)−r2​(x3​)​​
• 8）Sample random x 4 x_4 x4​ 来keep f ( X ) f(X) f(X) 和 q_polys linearly independent。
• 9）构建final_poly： f i n a l _ p o l y ( X ) = f ( X ) + x 4 q 1 ( X ) + x 4 2 q 2 ( X ) final\_poly(X) = f(X) + x_4 q_1(X) + x_4^2 q_2(X) final_poly(X)=f(X)+x4​q1​(X)+x42​q2​(X) final_poly为最终commit到inner product argument的多项式。

参考资料

[1] Halo2 之 Multipoint opening argument