Skip to article frontmatterSkip to article content

Mercury 笔记：实现常数证明尺寸

Mercury [EG25] 是一个基于 KZG10 的多元线性多项式承诺方案，即 Prover 向 Verifier 证明一个 nn 元线性多项式 f~(X0,X1,…,Xn−1)\tilde{f}(X_0,X_1,\ldots,X_{n-1}) 在某一个公开点 u⃗=(u0,u1,…,un−1)\vec{u} = (u_0,u_1,\ldots,u_{n-1}) 处的取值为 vv 。设 N=2nN = 2^n ，那么 f~\tilde{f} 的大小就为 NN 。对比同样基于 KZG10 的 ph23 [PH23]、zeromorph [BCHO23]、gemini [KT23]方案，mercury 能在不牺牲 Prover 线性 O(N)O(N) 的有限域运算的情况下，达到常数的证明尺寸，而非对数级别的 O(log⁡N)O(\log N)。同期的研究工作 SamaritanPCS [GPS25] 也达到了这样的性能。这两个协议在思想上有类似的地方，它们都在基于 pairing 的多元线性多项式承诺方案的研究中取得了显著的突破。本系列文章将详细介绍 mercury 是如何做到这一点的。

mercury 能做到常数证明尺寸的核心在于其洞见了一元多项式分解与多元线性多项式求值之间的关系，能将一个一元多项式在一个随机点处的求值转换为一个多元线性多项式在一个点处的求值，该求值可以转换为常数证明尺寸的内积证明，而一元多项式的分解证明也只需要常数的证明尺寸。

mercury 协议的整体思路与 Hyrax [WTSTW16] 协议有一些类似，先将 f~\tilde{f} 在 boolean hypercube B={0,1}n\mathbf{B} = \{0,1\}^n 上的 NN 个值排成一个 N×N\sqrt{N} \times \sqrt{N} 的矩阵，先将这个矩阵一次按列「拍扁」。设 b=N,t=log⁡bb = \sqrt{N}, t = \log b ，「拍扁」的动作相当于先代入 u⃗\vec{u} 中前半部分值求和，即先计算 h~(Xt,…,Xn−1):=f~(u0,…,ut−1,Xt,…,Xn−1)\tilde{h}(X_t, \ldots, X_{n - 1}):=\tilde{f}(u_0, \ldots, u_{t - 1}, X_t, \ldots, X_{n - 1}) ，接着再计算 h~(ut,…,un−1)=f~(u0,…,ut−1,ut,…,un−1)\tilde{h}(u_t, \ldots, u_{n - 1}) = \tilde{f}(u_0, \ldots, u_{t - 1}, u_t, \ldots, u_{n - 1}) ，证明其等于 vv 。这样分成两部分求和有一个好处，可以将计算的规模从原来的 NN 长变为 N\sqrt{N} 长，Prover 有一些计算复杂度原来是 Nlog⁡NN \log N ，现在计算的规模变小后，计算复杂度最多达到 Nlog⁡N=O(N)\sqrt{N} \log \sqrt{N} = O(N) ，这也是 mercury 能保持 Prover 线性 O(N)O(N) 复杂度的一个重要原因。

多元线性多项式的表示

对于一个多元线性多项式 f~(X0,X1,…,Xn−1)\tilde{f}(X_0, X_1,\ldots, X_{n-1}) ，用其在 boolean hypercube Bn={0,1}n\mathbf{B}_n = \{0,1\}^n 的取值进行表示，

f~(X0,X1,…,Xn−1)=∑i=02n−1fi⋅eq~(bits(i),(X0,X1,…,Xn−1))\tilde{f}(X_0,X_1,\ldots, X_{n-1}) = \sum_{i=0}^{2^n - 1} f_i \cdot \tilde{eq}(\mathsf{bits}(i),(X_0, X_1, \ldots, X_{n-1}))
(1)

其中 bits(i)=(i0,i1,…,in−1)\mathsf{bits}(i) = (i_0, i_1, \ldots, i_{n-1}) 是 ii 的二进制表示，i0i_0 表示最低位，满足 i=∑j=0n−1ij⋅2ji = \sum_{j = 0}^{n - 1}i_j \cdot 2^j 。eq~(bits(i),(X0,X1,…,Xn−1))\tilde{eq}(\mathsf{bits}(i),(X_0, X_1, \ldots, X_{n-1})) 可以看作是在 B={0,1}n\mathbf{B} = \{0,1\}^n 上的 Lagrange 插值函数，其具体表达式为

eq~(bits(i),(X0,X1,…,Xn−1))=∏j=0n−1((1−ij)(1−Xj)+ij⋅Xj)\tilde{eq}(\mathsf{bits}(i),(X_0, X_1, \ldots, X_{n-1})) = \prod_{j = 0}^{n-1} ((1- i_j)(1- X_j) + i_j \cdot X_j)
(2)

当 (X0,X1,…,Xn−1)∈Bn(X_0, X_1, \ldots, X_{n-1}) \in \mathbf{B}_n 时，若 bits(i)=(X0,X1,…,Xn−1)\mathsf{bits}(i) = (X_0, X_1, \ldots, X_{n-1}) ，那么这两个向量的各个分量都是相等的，因此 (1−ij)(1−Xj)+ij⋅Xj=1(1- i_j)(1- X_j) + i_j \cdot X_j = 1 ，最后 eq~\tilde{eq} 函数的计算结果也为 1 。当 bits(i)≠(X0,X1,…,Xn−1)\mathsf{bits}(i) \neq (X_0, X_1, \ldots, X_{n-1}) 时，eq~\tilde{eq} 函数的计算结果为 0 。

由于 eq~\tilde{eq} 函数实际上是 nn 项连乘，乘积具有结合律，因此是可以对 eq~\tilde{eq} 函数进行分解。设 n=2⋅t,b=2t=Nn = 2 \cdot t, b = 2^t = \sqrt{N} 。将向量 bits(i)\mathsf{bits}(i) 分成等长的两部分，bits(i)=((i0,…,it−1),(it,…,in−1))\mathsf{bits}(i) = ((i_0,\ldots,i_{t-1}), (i_t,\ldots,i_{n-1})) ，同样将 (X0,X1,…,Xn−1)(X_0, X_1, \ldots, X_{n-1}) 也分成两部分，(X0,X1,…,Xn−1)=((X0,…,Xt−1),(Xt,…,Xn−1)):=(X⃗1,X⃗2)(X_0, X_1, \ldots, X_{n-1}) = ((X_0, \ldots, X_{t-1}), (X_t, \ldots, X_{n-1})) := (\vec{X}_1, \vec{X}_2) ，那么

eq~(bits(i),(X0,X1,…,Xn−1))=∏j=0n−1((1−ij)(1−Xj)+ij⋅Xj)=(∏j=0t−1((1−ij)(1−Xj)+ij⋅Xj))⋅(∏j=tn−1((1−ij)(1−Xj)+ij⋅Xj))=eq~((i0,…,it−1),X⃗1)⋅eq~((it,…,in−1),X⃗2)\begin{align} \tilde{eq}(\mathsf{bits}(i),(X_0, X_1, \ldots, X_{n-1})) & = \prod_{j = 0}^{n-1} ((1- i_j)(1- X_j) + i_j \cdot X_j) \\ & = \left(\prod_{j = 0}^{t-1} ((1- i_j)(1- X_j) + i_j \cdot X_j) \right) \cdot \left(\prod_{j = t}^{n-1} ((1- i_j)(1- X_j) + i_j \cdot X_j) \right) \\ & = \tilde{eq}((i_0,\ldots,i_{t-1}),\vec{X}_1) \cdot \tilde{eq}((i_t,\ldots,i_{n-1}),\vec{X}_2) \end{align}
(3)

正因为 eq~\tilde{eq} 函数具有这样的拆分性质，因此我们可以更加方便的将 f~\tilde{f} 的求值也进行拆分。

拆分

现在要证明 f~\tilde{f} 在点 u⃗=(u0,u1,…,un−1)\vec{u} = (u_0, u_1, \ldots, u_{n-1}) 处的值为 vv ，即证明

f~(u0,u1,…,un−1)=∑i=02n−1fi⋅eq~(bits(i),(u0,u1,…,un−1))=v(1)\tilde{f}(u_0,u_1,\ldots, u_{n-1}) = \sum_{i=0}^{2^n - 1} f_i \cdot \tilde{eq}(\mathsf{bits}(i),(u_0, u_1, \ldots, u_{n-1})) = v \tag{1}
(4)

这里涉及到 NN 个项的求和，将其分为两个部分进行计算证明。

将变量 u⃗=(u⃗1,u⃗2)\vec{u} = (\vec{u}_1, \vec{u}_2) 拆分成两个等长的向量，u⃗1=(u0,…,ut−1),u2⃗=(ut,…,un−1)\vec{u}_1 = (u_0,\ldots,u_{t-1}), \vec{u_2} = (u_t,\ldots,u_{n - 1}) 。另外将 f~\tilde{f} 在 Bn\mathbf{B}_n 上的取值 (f0,f1,…,f2n−1)(f_0,f_1, \ldots, f_{2^n - 1}) 划分成 bb 组，用两个下脚标进行表示

(f0,f1,…,f2n−1)=(f0,0,f0,1,…,f0,b−1,…,fb−1,0,…,fb−1,b−1)(f_0,f_1, \ldots, f_{2^n - 1}) = (f_{0,0}, f_{0,1}, \ldots, f_{0,b-1}, \ldots, f_{b-1,0}, \ldots, f_{b-1,b-1})
(5)

用矩阵排列下表示为

Mf=[f0,0f0,1⋯f0,b−1f1,0f1,1⋯f1,b−1⋮⋮ ⋮fb−1,0fb−1,1⋯fb−1,b−1]M_f = \begin{bmatrix} f_{0,0} & f_{0,1} & \cdots & f_{0,b-1} \\ f_{1,0} & f_{1,1} & \cdots & f_{1,b-1} \\ \vdots & \vdots & \ & \vdots \\ f_{b-1,0} & f_{b-1,1} & \cdots & f_{b-1,b-1} \end{bmatrix}
(6)

那么根据前面介绍的 eq~\tilde{eq} 函数可以进行分解，可以得到

f~(u⃗1,u⃗2)=∑i=02n−1fi⋅eq~(bits(i),(u⃗1,u⃗2))=∑i=02t−1∑j=02t−1fi,j⋅eq~((bits(j),bits(i)),(u⃗1,u⃗2))=∑i=02t−1∑j=02t−1fi,j⋅eq~(bits(j),u⃗1)⋅eq~(bits(i),u⃗2)=∑i=02t−1(eq~(bits(i),u⃗2)⋅(∑j=02t−1fi,j⋅eq~(bits(j),u⃗1)))\begin{align} \tilde{f}(\vec{u}_1, \vec{u}_2) & = \sum_{i=0}^{2^n - 1} f_i \cdot \tilde{eq}(\mathsf{bits}(i),(\vec{u}_1, \vec{u}_2)) \\ & = \sum_{i=0}^{2^t - 1} \sum_{j=0}^{2^t - 1} f_{i,j} \cdot \tilde{eq}((\mathsf{bits}(j),\mathsf{bits}(i)),(\vec{u}_1, \vec{u}_2))\\ & = \sum_{i=0}^{2^t - 1} \sum_{j=0}^{2^t - 1} f_{i,j} \cdot \tilde{eq}(\mathsf{bits}(j),\vec{u}_1) \cdot \tilde{eq}(\mathsf{bits}(i),\vec{u}_2) \\ & = \sum_{i=0}^{2^t - 1} \left(\tilde{eq}(\mathsf{bits}(i),\vec{u}_2) \cdot\left(\sum_{j=0}^{2^t - 1} f_{i,j} \cdot \tilde{eq}(\mathsf{bits}(j),\vec{u}_1) \right) \right) \end{align}
(7)

上面的形式用矩阵表示更为直观，

f~(u⃗1,u⃗2)=[eq~(bits(0),u⃗2)eq~(bits(1),u⃗2)⋯eq~(bits(b−1),u⃗2)][f0,0f0,1⋯f0,b−1f1,0f1,1⋯f1,b−1⋮⋮ ⋮fb−1,0fb−1,1⋯fb−1,b−1][eq~(bits(0),u⃗1)eq~(bits(1),u⃗1)⋯eq~(bits(b−1),u⃗1)]=△v⃗2⊺⋅(Mf⋅v⃗1)\begin{align} & \tilde{f}(\vec{u}_1, \vec{u}_2) \\ & =\begin{bmatrix} \tilde{eq}(\mathsf{bits}(0), \vec{u}_2) & \tilde{eq}(\mathsf{bits}(1), \vec{u}_2) & \cdots & \tilde{eq}(\mathsf{bits}(b-1), \vec{u}_2) \end{bmatrix} \begin{bmatrix} f_{0,0} & f_{0,1} & \cdots & f_{0,b-1} \\ f_{1,0} & f_{1,1} & \cdots & f_{1,b-1} \\ \vdots & \vdots & \ & \vdots \\ f_{b-1,0} & f_{b-1,1} & \cdots & f_{b-1,b-1} \end{bmatrix} \begin{bmatrix} \tilde{eq}(\mathsf{bits}(0), \vec{u}_1) \\ \tilde{eq}(\mathsf{bits}(1), \vec{u}_1) \\ \cdots \\ \tilde{eq}(\mathsf{bits}(b-1), \vec{u}_1) \end{bmatrix} \\ & \stackrel{\triangle}{=} \vec{v}_2^{\intercal} \cdot (M_f \cdot \vec{v}_1) \end{align}
(8)

以 n=2n = 2 为例，分解过程如下图所示：

要证明 f~(u⃗1,u⃗2)=v\tilde{f}(\vec{u}_1, \vec{u}_2) = v ，可以分成两部分：

  1. 证明 Mf⋅v⃗1=b⃗M_f \cdot \vec{v}_1 = \vec{b} ，对应于先计算一个多元线性多项式 h~(X⃗2):=f~(u⃗1,X⃗2)\tilde{h}(\vec{X}_2) := \tilde{f}(\vec{u}_1, \vec{X}_2)
  2. 证明 v⃗2⊺⋅b⃗=v\vec{v}_2^{\intercal} \cdot \vec{b} = v ，对应于计算 h~(u⃗2)=f~(u⃗1,u2⃗)\tilde{h}(\vec{u}_2) = \tilde{f}(\vec{u}_1, \vec{u_2}) ，证明其结果为 vv 。

至此我们已经将 (1)(1) 中 NN 项的求和转换成了两个计算步骤，先代入 u⃗1\vec{u}_1 进行部分求和，再代入 u2⃗\vec{u_2} 得到最终的求和结果 vv 。下面先引入多元线性多项式到一元多项式的转换，再借助于一元多项式的承诺方案 KZG10 来进行证明。

从多元线性多项式到一元多项式

对于多元线性多项式

f~(X0,X1,…,Xn−1)=∑i=02n−1fi⋅eq~(bits(i),(X0,X1,…,Xn−1))\tilde{f}(X_0,X_1,\ldots, X_{n-1}) = \sum_{i=0}^{2^n - 1} f_i \cdot \tilde{eq}(\mathsf{bits}(i),(X_0, X_1, \ldots, X_{n-1}))
(9)

将其在 boolean hypercube Bn\mathbf{B}_n 上的取值 fif_i 直接作为一元多项式的系数，得到其对应的一元多项式为

f(X)=∑i=02n−1fi⋅Xif(X) = \sum_{i = 0}^{2^n - 1} f_i \cdot X^i
(10)

对于任意的一个多元线性多项式，都按照这种方式对应到一元多项式，即将多元线性多项式在 boolean hypercube 上的取值直接作为一元多项式的系数。

依然以 n=2n = 2 为例，多元线性多项式到一元多项式的转换，可以理解为只是变换了不同的基，多元线性多项式的基为 Lagrange 基，(eq~(bits(0),X⃗),eq~(bits(1),X⃗),eq~(bits(2),X⃗),eq~(bits(3),X⃗))(\tilde{eq}(\mathsf{bits}(0), \vec{X}), \tilde{eq}(\mathsf{bits}(1), \vec{X}), \tilde{eq}(\mathsf{bits}(2), \vec{X}), \tilde{eq}(\mathsf{bits}(3), \vec{X})) ，而一元多项式的基为 (1,X,X2,X3)(1, X, X^2, X^3) 。

对于前面提到的 h~(X⃗2)=f~(u⃗1,X⃗2)\tilde{h}(\vec{X}_2) = \tilde{f}(\vec{u}_1, \vec{X}_2) ，其用矩阵表示为

h~(X⃗2)=f~(u⃗1,X⃗2)=[eq~(bits(0),X⃗2)eq~(bits(1),X⃗2)⋯eq~(bits(b−1),X⃗2)][f0,0f0,1⋯f0,b−1f1,0f1,1⋯f1,b−1⋮⋮ ⋮fb−1,0fb−1,1⋯fb−1,b−1][eq~(bits(0),u⃗1)eq~(bits(1),u⃗1)⋯eq~(bits(b−1),u⃗1)]=[eq~(bits(0),X⃗2)eq~(bits(1),X⃗2)⋯eq~(bits(b−1),X⃗2)][f0,0⋅eq~(bits(0),u⃗1)+f0,1⋅eq~(bits(1),u⃗1)+…+f0,b−1⋅eq~(bits(b−1),u⃗1)f1,0⋅eq~(bits(0),u⃗1)+f1,1⋅eq~(bits(1),u⃗1)+…+f1,b−1⋅eq~(bits(b−1),u⃗1)⋮fb−1,0⋅eq~(bits(0),u⃗1)+fb−1,1⋅eq~(bits(1),u⃗1)+…+fb−1,b−1⋅eq~(bits(b−1),u⃗1)]\begin{align} & \tilde{h}(\vec{X}_2) = \tilde{f}(\vec{u}_1, \vec{X}_2) \\ & =\begin{bmatrix} \tilde{eq}(\mathsf{bits}(0), \vec{X}_2) & \tilde{eq}(\mathsf{bits}(1), \vec{X}_2) & \cdots & \tilde{eq}(\mathsf{bits}(b-1), \vec{X}_2) \end{bmatrix} \begin{bmatrix} f_{0,0} & f_{0,1} & \cdots & f_{0,b-1} \\ f_{1,0} & f_{1,1} & \cdots & f_{1,b-1} \\ \vdots & \vdots & \ & \vdots \\ f_{b-1,0} & f_{b-1,1} & \cdots & f_{b-1,b-1} \end{bmatrix} \begin{bmatrix} \tilde{eq}(\mathsf{bits}(0), \vec{u}_1) \\ \tilde{eq}(\mathsf{bits}(1), \vec{u}_1) \\ \cdots \\ \tilde{eq}(\mathsf{bits}(b-1), \vec{u}_1) \end{bmatrix} \\ & = \begin{bmatrix} \tilde{eq}(\mathsf{bits}(0), \vec{X}_2) & \tilde{eq}(\mathsf{bits}(1), \vec{X}_2) & \cdots & \tilde{eq}(\mathsf{bits}(b-1), \vec{X}_2) \end{bmatrix} \begin{bmatrix} f_{0,0} \cdot \tilde{eq}(\mathsf{bits}(0), \vec{u}_1) + f_{0,1} \cdot \tilde{eq}(\mathsf{bits}(1), \vec{u}_1) + \ldots + f_{0,b-1} \cdot \tilde{eq}(\mathsf{bits}(b-1), \vec{u}_1)\\ f_{1,0} \cdot \tilde{eq}(\mathsf{bits}(0), \vec{u}_1) + f_{1,1} \cdot \tilde{eq}(\mathsf{bits}(1), \vec{u}_1) + \ldots + f_{1,b-1} \cdot \tilde{eq}(\mathsf{bits}(b-1), \vec{u}_1) \\ \vdots \\ f_{b-1,0} \cdot \tilde{eq}(\mathsf{bits}(0), \vec{u}_1) + f_{b-1,1} \cdot \tilde{eq}(\mathsf{bits}(1), \vec{u}_1) + \ldots + f_{b-1,b-1} \cdot \tilde{eq}(\mathsf{bits}(b-1), \vec{u}_1) \end{bmatrix} \end{align}
(11)

可以发现右边列向量的每一项其实就是 h~(X⃗2)\tilde{h}(\vec{X}_2) 在 boolean hypercube Bt={0,1}t\mathbf{B}_t = \{0,1\}^t 上的取值，对应到一元多项式 h(X)h(X) ，右边列向量的第 ii 行就是 h(X)h(X) 中 XiX^i 项前面的系数。

h(X)=∑i=0b−1((∑j=0b−1fi,j⋅eq~(bits(j),u⃗1))⋅Xi)h(X) = \sum_{i = 0}^{b - 1} \left(\left( \sum_{j = 0}^{b - 1} f_{i,j} \cdot \tilde{eq}(\mathsf{bits}(j), \vec{u}_1)\right) \cdot X^i \right)
(12)

可以发现 h(X)h(X) 中每一项的系数 ∑j=0b−1fi,j⋅eq~(bits(j),u⃗1)\sum_{j = 0}^{b - 1} f_{i,j} \cdot \tilde{eq}(\mathsf{bits}(j), \vec{u}_1) 也是一个数乘以 eq~\tilde{eq} 的形式，其实我们还可以将 fi,jf_{i,j} 作为一元多项式的系数，将 MfM_f 矩阵的每一列作为一个一元多项式对应的系数，表示为

f0(X)=f0,0+f1,0X+…+fb−1,0Xb−1f1(X)=f0,1+f1,1X+…+fb−1,1Xb−1…fb−1(X)=f0,b−1+f1,b−1X+…+fb−1,b−1Xb−1\begin{align} & f_0(X) = f_{0,0} + f_{1,0} X + \ldots + f_{b-1, 0} X^{b-1} \\ & f_1(X) = f_{0,1} + f_{1,1} X + \ldots + f_{b-1, 1} X^{b-1} \\ & \qquad \qquad \qquad \qquad \ldots \\ & f_{b-1}(X) = f_{0,b-1} + f_{1,b-1} X + \ldots + f_{b-1, b-1} X^{b-1} \end{align}
(13)

将 MfM_f 的每一列作为一元多项式的系数的好处是，MfM_f 矩阵的第 ii 行的元素对应的正好是 XiX^i 的系数，例如矩阵 MfM_f 的第 1 行，其元素为 (f1,0,f1,1,…,f1,b−1)(f_{1,0}, f_{1,1}, \ldots, f_{1,b-1}) ，其分别是 f0(X),f1(X),…,fb−1(X)f_0(X), f_1(X), \ldots, f_{b-1}(X) 中 X1X^1 前面的系数。

fi(X)f_i(X) 其实也可以看作是对 f(X)f(X) 的一个分解，

f(X)=∑i=02n−1fi⋅Xi=∑i=0b−1∑j=0b−1fi,j⋅Xi⋅b+j=∑i=0b−1∑j=0b−1fi,j⋅(Xb)i⋅Xj=∑j=0b−1∑i=0b−1fi,j⋅(Xb)i⋅Xj=∑j=0b−1fj(Xb)⋅Xj=∑i=0b−1fi(Xb)⋅Xi\begin{align} f(X) & = \sum_{i = 0}^{2^n - 1} f_i \cdot X^i = \sum_{i = 0}^{b - 1} \sum_{j = 0}^{b - 1} f_{i,j} \cdot X^{i \cdot b + j} \\ & = \sum_{i = 0}^{b - 1} \sum_{j = 0}^{b - 1} f_{i,j} \cdot (X^{b})^i \cdot X^{j} \\ & = \sum_{j = 0}^{b - 1} \sum_{i = 0}^{b - 1} f_{i,j} \cdot (X^{b})^i \cdot X^{j} \\ & = \sum_{j = 0}^{b - 1} f_j(X^b) \cdot X^j \\ & = \sum_{i = 0}^{b - 1} f_i(X^b) \cdot X^i \end{align}
(14)

即将 f(X)f(X) 分解成 bb 个多项式求和，

f(X)=f0(Xb)+X⋅f1(Xb)+…+Xb−1⋅fb−1(Xb)(2)f(X) = f_0(X^b) + X \cdot f_1(X^b) + \ldots + X^{b-1} \cdot f_{b-1}(X^b) \tag{2}
(15)

其实这里对一元多项式的分解与上一小节讲到的对多元多项式求值 f~(u⃗1,u⃗2)\tilde{f}(\vec{u}_1,\vec{u}_2) 的分解是一致的，多元线性多项式利用了 eq~\tilde{eq} 函数的可拆分性，一元多项式中对 XiX^i 也可以进行拆分分解。以 n=2n = 2 为例，对两者进行对比，如下图所示。

此时 h(X)h(X) 就可以表示为

h(X)=∑i=0b−1((∑j=0b−1fi,j⋅eq~(bits(j),u⃗1))⋅Xi)=∑j=0b−1((∑i=0b−1fi,j⋅Xi)⋅eq~(bits(j),u⃗1))=∑j=0b−1eq~(bits(j),u⃗1)⋅fj(X)=∑i=0b−1eq~(bits(i),u⃗1)⋅fi(X)\begin{align} h(X) & = \sum_{i = 0}^{b - 1} \left(\left( \sum_{j = 0}^{b - 1} f_{i,j} \cdot \tilde{eq}(\mathsf{bits}(j), \vec{u}_1)\right) \cdot X^i \right) \\ & = \sum_{j = 0}^{b - 1} \left(\left( \sum_{i = 0}^{b - 1} f_{i,j} \cdot X^i \right) \cdot \tilde{eq}(\mathsf{bits}(j), \vec{u}_1) \right) \\ & = \sum_{j = 0}^{b - 1} \tilde{eq}(\mathsf{bits}(j), \vec{u}_1) \cdot f_j(X) \\ & = \sum_{i = 0}^{b - 1} \tilde{eq}(\mathsf{bits}(i), \vec{u}_1) \cdot f_i(X) \end{align}
(16)

以 n=2n = 2 为例，下图表示了 h(X)h(X) 的分解过程。

那么 h(X)=∑i=0b−1eq~(bits(i),u⃗1)⋅fi(X)h(X)= \sum_{i = 0}^{b - 1} \tilde{eq}(\mathsf{bits}(i), \vec{u}_1) \cdot f_i(X) 对应的多元线性多项式就是 h~(X⃗)=f~(u⃗1,X⃗)\tilde{h}(\vec{X}) = \tilde{f}(\vec{u}_1, \vec{X}) 。这就相当于一次性替换了 f~\tilde{f} 中的前 tt 个变量。那么我们承诺与 f~(u⃗1,X⃗)\tilde{f}(\vec{u}_1, \vec{X}) 对应的一元多项式 cm(h(X))\mathsf{cm}(h(X)) ，再证明 h~(u⃗2)=v\tilde{h}(\vec{u}_2) = v 就完成了证明。也就是对应前一小节所说的证明分为两个部分：

  1. 证明 Mf⋅v⃗1=b⃗M_f \cdot \vec{v}_1 = \vec{b} ，对应于先计算一个多元线性多项式 h~(X⃗2):=f~(u⃗1,X⃗2)\tilde{h}(\vec{X}_2) := \tilde{f}(\vec{u}_1, \vec{X}_2)
  2. 证明 v⃗2⊺⋅b⃗=v\vec{v}_2^{\intercal} \cdot \vec{b} = v ，对应于计算 h~(u⃗2)=f~(u⃗1,u2⃗)\tilde{h}(\vec{u}_2) = \tilde{f}(\vec{u}_1, \vec{u_2}) ，证明其结果为 vv 。

第 2 部分其实是证明两个向量的内积，可以转换为内积的证明。

这样就完成证明了吗？那么怎么实现常数大小的 proof size 呢？这里面其实有一个关键的地方需要证明，那就是 Verifier 要去相信 h(X)h(X) 的构造是正确的，也就是

h(X)=∑i=0b−1eq~(bits(i),u⃗1)⋅fi(X)(3)h(X)= \sum_{i = 0}^{b - 1} \tilde{eq}(\mathsf{bits}(i), \vec{u}_1) \cdot f_i(X) \tag{3}
(17)

Prover 需要向 Verifier 证明其确实是按照这种方式构造的，而不是任意发送的一个多项式。要证明 (3)(3) 式构造正确，那么 Verifier 可以随机发起一个挑战值 rr ，Prover 要证明

h(rb)=∑i=0b−1eq~(bits(i),u⃗1)⋅fi(rb)(4)h(r^b)= \sum_{i = 0}^{b - 1} \tilde{eq}(\mathsf{bits}(i), \vec{u}_1) \cdot f_i(r^b) \tag{4}
(18)

fi(rb)f_i(r^b) 是和 ff 的值相关的，根据 f(X)f(X) 的分解式 (2)(2)

f(X)=f0(Xb)+X⋅f1(Xb)+…+Xb−1⋅fb−1(Xb),f(X) = f_0(X^b) + X \cdot f_1(X^b) + \ldots + X^{b-1} \cdot f_{b-1}(X^b) ,
(19)

令 ωb=1\omega^b = 1 ，可知

f(r)=f0(rb)+r⋅f1(rb)+…+rb−1⋅fb−1(rb)f(ωr)=f0(rb)+ωr⋅f1(rb)+…+(ωr)b−1⋅fb−1(rb)…f(ωb−1r)=f0(rb)+ωb−1r⋅f1(rb)+…+(ωb−1r)b−1⋅fb−1(rb)\begin{align} & f(r) = f_0(r^b) + r \cdot f_1(r^b) + \ldots + r^{b-1} \cdot f_{b-1}(r^b) \\ & f(\omega r) = f_0(r^b) + \omega r \cdot f_1(r^b) + \ldots + (\omega r)^{b-1} \cdot f_{b-1}(r^b) \\ & \ldots \\ & f(\omega^{b-1} r) = f_0(r^b) + \omega^{b-1} r \cdot f_1(r^b) + \ldots + (\omega^{b-1} r)^{b-1} \cdot f_{b-1}(r^b) \end{align}
(20)

上面相当于是一个有 bb 个未知数 fi(rb)f_i(r^b) ，以及有 bb 个方程的线性方程组，求解该线性方程组，就可以用 {f(r),f(ωr),…,f(ωb−1r)}\{f(r), f(\omega r), \ldots, f(\omega^{b - 1} r) \} 这些值计算得到 fi(rb)f_i(r^b) 的值。Prover 可以发送 h(rb)h(r^b) 以及 {f(r),f(ωr),…,f(ωb−1r)}\{f(r), f(\omega r), \ldots, f(\omega^{b - 1} r) \} 这些值及对应的打开证明，让 Verifier 自己计算出 fi(rb)f_i(r^b) 的值，进而验证 (4)(4) 式是否成立。这种方案的问题是发送的证明大小肯定是 O(b)O(b) 级别的，而不是常数。

有没有什么方法既可以实现常数大小的证明，又能证明 (4)(4) 式的正确性呢？mercury 巧妙的将证明 (4)(4) 式中一个在一元多项式的取值 h(rb)h(r^b) 转换为了证明在一个多元线性多项式处的取值。

实现常数证明尺寸

Prover 的目标是用常数证明尺寸来证明

h(rb)=∑i=0b−1eq~(bits(i),u⃗1)⋅fi(rb)(4)h(r^b)= \sum_{i = 0}^{b - 1} \tilde{eq}(\mathsf{bits}(i), \vec{u}_1) \cdot f_i(r^b) \tag{4}
(21)

不妨设 α=rb\alpha = r^b 。

令 g(X)=f(X)mod  Xb−αg(X) = f(X) \mod{X^b - \alpha} ，记商多项式为 q(X)q(X) ，那么有

f(X)=q(X)⋅(Xb−α)+g(X)(5)f(X) = q(X) \cdot (X^b - \alpha) + g(X) \tag{5}
(22)

在上式中代入 Xb=αX^b = \alpha 的条件，可以得到

g(X)=f(X)=∑i=0b−1fi(Xb)⋅Xi=∑i=0b−1fi(α)⋅Xig(X) = f(X) = \sum_{i = 0}^{b - 1} f_i(X^b) \cdot X^i = \sum_{i = 0}^{b - 1} f_i(\alpha) \cdot X^i
(23)

可以看到 g(X)g(X) 的系数为 fi(α)f_i(\alpha) ，与 g(X)g(X) 对应的多元线性多项式就应该为

g~(X0,…,Xb−1)=∑i=0b−1fi(α)⋅eq~(bits(i),(X0,…,Xb−1))\tilde{g}(X_0, \ldots , X_{b-1}) = \sum_{i = 0}^{b - 1} f_i(\alpha) \cdot \tilde{eq}(\mathsf{bits}(i), (X_0, \ldots , X_{b-1}))
(24)

那么 (4)(4) 式也就转换为

h(α)=∑i=0b−1eq~(bits(i),u⃗1)⋅fi(α)=g~(u⃗1)h(\alpha)= \sum_{i = 0}^{b - 1} \tilde{eq}(\mathsf{bits}(i), \vec{u}_1) \cdot f_i(\alpha) = \tilde{g}(\vec{u}_1)
(25)

此时要证明 (4)(4) 式正确，就转换成了证明

h(α)=g~(u⃗1)(6)h(\alpha) = \tilde{g}(\vec{u}_1) \tag{6}
(26)

以 n=2n = 2 为例，转换证明的过程如下图所示。

这样就将在一个一元多项式 h(α)h(\alpha) 处的值转换为了在一个多元线性多项式在某一个点处的值 g~(u⃗1)\tilde{g}(\vec{u}_1) 。这时我们就需要再证明与 g~\tilde{g} 对应的 g(X)g(X) 的构造是正确的，也就是 (5)(5) 式成立，Prover 可以承诺 q(X)q(X) 和 g(X)g(X) ，Verifier 再选取一个随机点 ζ\zeta ，来验证 (5)(5) 式成立，这只需要常数的证明大小，这就是 mercury 协议能实现常数证明大小的核心。

另外，为了防止 Prover 作弊，我们还需要限制 deg⁡(g)<b\deg(g) < b 。

至此，就将上一小节提到的两个证明：

  1. 证明 Mf⋅v⃗1=b⃗M_f \cdot \vec{v}_1 = \vec{b} ，对应于先计算一个多元线性多项式 h~(X⃗2):=f~(u⃗1,X⃗2)\tilde{h}(\vec{X}_2) := \tilde{f}(\vec{u}_1, \vec{X}_2)
  2. 证明 v⃗2⊺⋅b⃗=v\vec{v}_2^{\intercal} \cdot \vec{b} = v ，对应于计算 h~(u⃗2)=f~(u⃗1,u2⃗)\tilde{h}(\vec{u}_2) = \tilde{f}(\vec{u}_1, \vec{u_2}) ，证明其结果为 vv 。

转换为下面四个证明：

  1. f(X)=q(X)⋅(Xb−α)+g(X)f(X) = q(X) \cdot (X^b - \alpha) + g(X)
  2. deg⁡(g)<b\deg(g) < b
  3. g~(u⃗1)=h(α)\tilde{g}(\vec{u}_1) = h(\alpha)
  4. h~(u⃗2)=v\tilde{h}(\vec{u}_2) = v

第一项的证明，Prover 可以先发送 q(X)q(X) 和 g(X)g(X) 的承诺，Verifier 发送一个随机点 ζ\zeta ，让 Prover 在该随机点打开，发送 q(ζ),g(ζ)q(\zeta), g(\zeta) ，Prover 只要证明商多项式

f(X)−q(ζ)⋅(ζb−α)+g(ζ)X−ζ\frac{f(X) - q(\zeta) \cdot (\zeta^b - \alpha) + g(\zeta)}{X - \zeta}
(27)

存在，就证明了第 1 项中的式子是成立的，这一项的证明只需要常数的证明大小。

对于第二项，是 degree bound 的证明，也可以由常数的证明大小实现。

对于第三项和第四项，都是证明有 bb 个变量的多元线性多项式在某个点的打开值，这可以转换为内积证明，例如对于多元线性多项式 g~\tilde{g} ，

g~(u⃗1)=∑i=0b−1eq~(bits(i),u⃗1)⋅fi(α)\begin{align} \tilde{g}(\vec{u}_1) & = \sum_{i = 0}^{b - 1} \tilde{eq}(\mathsf{bits}(i), \vec{u}_1) \cdot f_i(\alpha) \\ \end{align}
(28)

上面其实计算的是向量 a⃗1=(eq~(bits(0),u⃗1),…,eq~(bits(b−1),u⃗1)\vec{a}_1 = (\tilde{eq}(\mathsf{bits}(0),\vec{u}_1),\ldots, \tilde{eq}(\mathsf{bits}(b-1), \vec{u}_1) 和 b⃗1=(f0(α),…,fb−1(α))\vec{b}_1 = (f_0(\alpha),\ldots, f_{b-1}(\alpha)) 的内积。对于 h~(u⃗2)\tilde{h}(\vec{u}_2) 也是类似的，这样第三项和第四项就能转换为两个内积证明，而这两个内积证明又能用随机数聚合成一个证明，也能达到常数的证明大小。

因此，mercury 的这四部分证明都是常数的证明大小，同时由于证明第三项和第四项的多元线性多项式的长度为 bb ，就算有些计算 Prover 需要 O(blog⁡b)O(b \log b) 的复杂度，这也是不超过 O(N)O(N) 的复杂度，依然能够保持 Prover 线性的计算复杂度。

本文介绍了 mercury 能在保持 Prover 线性复杂度下实现常数证明尺寸的原因，在下一篇文章中将详细介绍 mercury 是如何证明这四项的。

References

Zeromorph
Zeromroph-fri 协议复杂度分析
Mercury
Mercury 笔记：对接 KZG