Mina中的多项式承诺方案

1. 引言

Mina系列博客有：

• Mina概览
• Mina的支付流程
• Mina的zkApp
• Mina中的Pasta（Pallas和Vesta）曲线
• Mina中的Schnorr signature
• Mina中的Pickles SNARK
• Mina中的Kimchi SNARK
• Mina Kimchi SNARK 代码解析
• Mina Berkeley QANet测试网zkApp初体验
• Mina中的Poseidon hash

2. 多项式 VS 函数

令 R R R为某域，基于域 R R R变量为 X X X的多项式表示为： a 0 + a 1 X + a 2 X 2 + ⋯ + a d X d a_0+a_1X+a_2X^2+\cdots +a_dX^d a0​+a1​X+a2​X2+⋯+ad​Xd 其中 a i ∈ R a_i\in R ai​∈R且 d d d为任意自然数。

针对基于 R R R的多项式的函数 e v a l : R [ X ] → ( R → R ) \mathsf{eval}:R[X]\rightarrow (R\rightarrow R) eval:R[X]→(R→R)定义为：【可将 e v a l \mathsf{eval} eval看成是对多项式采样。】 e v a l ( a 0 + a 1 X + ⋯ + a d X d ) = ( x : R ) ↦ a 0 + a 1 x + ⋯ + a d x d \mathsf{eval}(a_0+a_1X+\cdots+a_dX^d)=(x:R)\mapsto a_0+a_1x+\cdots +a_dx^d eval(a0​+a1​X+⋯+ad​Xd)=(x:R)↦a0​+a1​x+⋯+ad​xd 其中 X X X为未赋值的变量名， e v a l \mathsf{eval} eval将其映射为field element x x x，整个evaluation函数可看成是系数 < a 0 , a 1 , ⋯   , a d > 与 < 1 , x , ⋯   , x d > 的inner product。

注意，多项式与函数是不同的。多项式是一组系数列表，基于某些域值，对于多项式 p 1 , p 2 p1,p2 p1,p2，会存在 e v a l ( p 1 ) = e v a l ( p 2 ) \mathsf{eval}(p1)=\mathsf{eval}(p2) eval(p1)=eval(p2)，但 p 1 ≠ p 2 p1\neq p2 p1=p2的情况。 如，以 F 2 [ X ] \mathbb{F}_2[X] F2​[X]为域的多项式 X X X和 X 2 X^2 X2，二者可映射为相同的函数 F 2 → F 2 \mathbb{F}_2\rightarrow \mathbb{F}_2 F2​→F2​（即意味着对 x ∈ R = F 2 = { 0 , 1 } x\in R=\mathbb{F}_2=\{0,1\} x∈R=F2​={0,1} 有 x = x 2 x=x^2 x=x2），但是二者是不同的多项式。

使用多项式的原因在于：

• 1）将关于一组域值的statement 转换为 关于多项式的statement，从而可构建zkSNARKs。
• 2）基于多项式的特定运算效率更高。

对于函数 φ : A → F \varphi: A\rightarrow F φ:A→F， A A A为数组，长度为 ∣ A ∣ |A| ∣A∣，需基于 ∀ x ∈ A , ( x , φ ( x ) ) \forall x\in A, (x,\varphi(x)) ∀x∈A,(x,φ(x))进行插值构建多项式。 对于每一个 x i ∈ A x_i\in A xi​∈A，可构建多项式： f i ( X ) = { φ ( x i ) X = x i 0 X ≠ x i f_{i}(X) =\left\{\begin{matrix} \varphi(x_i)& X=x_i\\ 0 & X\neq x_i \end{matrix}\right. fi​(X)={φ(xi​)0​X=xi​X=xi​​ 最终的多项式： f ( X ) = ∑ i f i ( X ) f(X)=\sum_if_i(X) f(X)=∑i​fi​(X)。

相应的vanishing 多项式表示为： v S ( X ) = ( X − x 0 ) ( X − x 1 ) ⋯ ( X − x d ) v_S(X)=(X-x_0)(X-x_1)\cdots(X-x_d) vS​(X)=(X−x0​)(X−x1​)⋯(X−xd​)。

同时有 i n t e r p A ( e v a l A ( f ) ) = f \mathsf{interp}_A(\mathsf{eval}_A(f))=f interpA​(evalA​(f))=f，即对多项式 f f f基于 A A A采样后，再插值获得的多项式仍然是 f f f。（多项式degree为 d d d，不同的采样点数为 d + 1 d+1 d+1。）【 i n t e r p A \mathsf{interp}_A interpA​和 e v a l A \mathsf{eval}_A evalA​为同构集合（即双射），为同构环。】

对同一Field，两个不同多项式 f , g f,g f,g的最大degree为 d d d，若在 d + 1 d+1 d+1个不同的点 x i x_i xi​均有 f ( x i ) = g ( x i ) f(x_i)=g(x_i) f(xi​)=g(xi​)，则认为2多项式相等，即 f = g f=g f=g。 对2个不同多项式 f , g : A → F f,g:A\rightarrow F f,g:A→F采样后的加法、惩罚运算可表示为： f + g : = a ↦ f ( a ) + g ( a ) ， f ⋅ g = a ↦ f ( a ) ⋅ g ( a ) f+g:=a\mapsto f(a)+g(a)，f\cdot g=a\mapsto f(a)\cdot g(a) f+g:=a↦f(a)+g(a)，f⋅g=a↦f(a)⋅g(a)。

Fundamental theorem of polynomials (final version)

Let d ∈ N d \in \N d∈N and let A ⊆ F A \subseteq F A⊆F with ∣ A ∣ = d + 1 |A| = d + 1 ∣A∣=d+1. With

e v a l A  ⁣ : F [ x ] ≤ d → ( A → F ) i n t e r p A  ⁣ : ( A → F ) → F [ x ] ≤ d \mathsf{eval}_A \colon F[x]_{\leq d} \to (A \to F)\\ \mathsf{interp}_A \colon (A \to F) \to F[x]_{\leq d} evalA​:F[x]≤d​→(A→F)interpA​:(A→F)→F[x]≤d​

defined as above, these two functions define an isomorphism of rings.

That is is, they are mutually inverse and each one respects addition, subtraction and multiplication.

基于以上表示，可借助FFT算法以 O ( n log ⁡ n ) O(n\log n) O(nlogn)实现2个degree为 n n n的多项式乘法运算，而直接的乘法运算需要 O ( n 2 ) O(n^2) O(n2)。

3. 多项式的程序表示

在实际计算机实现时，对多项式有3种常用的表达方式：

• 1）dense coefficient形式：将degree为 d d d的多项式以长度为 d + 1 d+1 d+1的向量来表示其所有系数。该向量中的第 i i i个元素对应系数 a i a_i ai​。这就是arkworks中的DensePolynomial类型。有时也可以单项式集合来表示多项式，因为多项式是单项式 x i x^i xi的线性组合。【系数表示法】
• 2）sparse coefficient形式：若多项式中没有很多非零系数，则以dense coefficient来表示将很浪费。采用sparse形式，可将多项式表示为pairs ( u s i z e , F ) (usize,F) (usize,F)向量，其中 F F F为系数的类型。数组 [ ( i 0 , b 0 ) , ⋯   , ( i n , b n ) ] [(i_0,b_0),\cdots ,(i_n,b_n)] [(i0​,b0​),⋯,(in​,bn​)]对应的多项式为 b 0 x i 0 + ⋯ + b n x i n b_0x^{i_0}+\cdots + b_nx^{i_n} b0​xi0​+⋯+bn​xin​。
• 3）evaluation形式。对于固定的index set A ⊆ F A\subseteq F A⊆F，其中 A = { a 0 , ⋯   , a d } A=\{a_0,\cdots, a_d\} A={a0​,⋯,ad​}，将多项式 f ∈ F [ X ] ≤ d f\in F[X]_{\leq d} f∈F[X]≤d​表示为向量 [ f ( a 0 ) , ⋯   , f ( a d ) ] [f(a_0), \cdots, f(a_d)] [f(a0​),⋯,f(ad​)]。【点值表示法】

evaluation形式很重要，因为evaluation形式下，2个多项式相乘仅需对2个向量中的对应每个元素相乘，所需time为 O ( n ) O(n) O(n)。而直接相乘需要 O ( n 2 ) O(n^2) O(n2)。

对于特定的集合 A ⊆ F A\subseteq F A⊆F，可高效的在dense coefficient形式和evaluation形式之间相互转换。因为，对于特定的 A A A， i n t e r p A \mathsf{interp}_A interpA​和 e v a l A \mathsf{eval}_A evalA​的计算效率要远远优于 O ( n 2 ) O(n^2) O(n2)。

4. FFT计算多项式乘法

前序博客有：

• Halo中的快速傅里叶（逆）变换算法(I)FFT

通过Cooley-Tukey fast Fourier transform（简称FFT）算法（由Gauss 160年前发明，但由Cooley-Tukey独立再发现并公布），进行多项式乘法运算所需复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

FFT算法的核心是系数表示法与点值表示法之间的相互转换，而不是直接进行多项式乘法运算。给定以dense coefficient表示的2个degree为 n − 1 n-1 n−1的多项式 p , q p,q p,q，FFT计算 p ⋅ q p\cdot q p⋅q的流程为：

• 1）借助FFT，将 p , q p,q p,q由系数表示法转换为点值表示法，相应的复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)。
• 2）依次将2个点值表示法的每个元素相乘 r = p ∗ q r=p*q r=p∗q，相应的复杂度为 O ( n ) O(n) O(n)。
• 3）借助iFFT，将点值表示的 r r r转换为系数表示，相应的复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

关键点在于，可选择任意 n n n个不同的evaluation点来表示任意的degree为 n − 1 n-1 n−1的多项式。Cooley-Tukey FFT通过选择合适的点来生成高效的FFT算法，这些点为固定的，且适于特定degree的任意多项式。

特别地，具有 n n n-th root of unity ω ∈ F \omega\in F ω∈F，使得 ω n = 1 \omega^n=1 ωn=1，且对于任意的 0 < r < n 0