缺失的协议 PH23-PCS（二）

本文给出 PH23-KZG10 的完整的优化协议。

1. 协议框架与优化¶

首先回顾下 PH23+KZG10 协议的 Evaluation Argument 的简单流程，然后我们看看有哪些可以优化的地方。

P: 发送 $c(X)$ 的承诺 $C_c$ V: 发送随机数 α 用来聚合多个多项式的约束等式 P: 计算公开的多项式集合 $\{s_i(X)\}$ P: 计算聚合的约束多项式 $h(X)$

P: 计算商多项式 $t(X)$ 的承诺 $C_t$, $z(X)$ 的承诺 $C_z$

V: 发送随机的求值点 ζ

P: 计算 $c(\zeta\cdot\omega), c(\zeta\cdot\omega^2), c(\zeta\cdot\omega^4), \ldots, c(\zeta\cdot\omega^{2^{n-1}})$, $c(\zeta)$ ，还有 $z(\zeta), z(\omega^{-1}\cdot\zeta)$ ，$t(\zeta), a(\zeta)$ ；发送上述多项式求值的 KZG10 Evaluation Arguments

V: 验证所有的 KZG10 Evaluation Arguments，然后验证下面的等式：

$c^*(X)$ 在多点求值的证明优化¶

在证明中，Prover 需要证明 $c(X)$ 多项式在 $n+1$ 个点上的 Evaluation，即

利用 [BDFG20] 论文中的技术，如果一个 $f(X)$ 在 $m$ 个点 $D=(z_0,z_1,\ldots,z_{m-1})$ 上的 Evaluation 为 $\vec{v}=(v_0, v_1, \ldots, v_{m-1})$，定义 $f^*(X)$ 是 $\vec{v}$ 在 $D$ 上的插值多项式，即 $\deg(f^*(X)) = m-1$，并且有 $f^*(z_i) = f(z_i), \forall i\in[0,m)$

那么 $f(X)$ 满足下面的等式：

上面等式这个很容易验证，因为当 $X=z_i$ 的时候，等式左边等于零，那么 $f(X)-f^*(X)$ 可以被 $(X-z_i)$ 整除。那么对于所有的 $i=0,1,\ldots,m-1$，$f(X)-f^*(X)$ 可以被 $v_D(X)$ 整除，

这样一来，Prover 只要向 Verifier 证明存在 $q(X)$，使得 $f(X) - f^*(X) = q(X)\cdot v_D(X)$，那么 $f(X)$ 在 $D$ 上的 Evaluation 就等于 $\vec{v}$。而这个等式又可以通过 Verifier 提供一个随机挑战点 $X=\xi$ 来验证，其中 $v_D(\xi)$ 与 $f^*(\xi)$ 可以由 Verifier 自行计算，而 $f(\xi)$ 与 $q(\xi)$ 可以通过 KZG10 的 Evaluation Argument 来证明。

$c^*(X)$ 多项式计算的优化¶

Prover 可以构造多项式 $c^*(X)$，它是下面向量在 $\zeta D$ 上的插值多项式。这样做的优势是可以让 Prover 一次证明 $c(X)$ 的多个不同点的 Evaluation，记为 $\vec{c^*}$：

我们引入 $D$ 满足 $|D|=n+1$ ，其定义为

那么 $c^*(X)$ 的 Evaluation 的 Domain 就可以表示为 $\zeta D$，

其 Vanishing 多项式 $v_{D'}(X)$ 定义如下：

对于 $D'$ 上的 Lagrange 多项式 可以定义如下：

其中 $\hat{d}_j$ 是 $D'$ 上的 Bary-Centric Weights，定义为

这里 $\hat{w}_j$ 是 $D$ 上的 Bary-Centric Weights，并且它的定义只与 $D$ 相关，和 ζ 无关。因此，我们可以事先预计算 $\hat{w}_j$ ，然后利用 $\hat{w}_j$ 来计算 $c^*(X)$：

上面的等式可以进一步优化，等式右边除以一个常数项多项式 $g(X)=1$

可以得到：

展开 $g(X)$ 与 $L^{D'}_i(X)$ ，可以得到：

分子分母同时消去 $z_{D'}(X)$，可以得到

再展开 $\hat{d}_i$ 的定义，并且分子分母同时消去 $\frac{1}{\zeta^n}$ ，可以得到

Prover 可以利用事先预计算的 $D$ 上的Bary-Centric Weights $\{\hat{w}_i\}$ 来快速计算 $c^*(X)$，如果 $n$ 是固定的。 尽管如此，$c^*(X)$ 的计算复杂度仍为 $O(n\log^2(n))$。不过考虑到 $n=\log(N)$，所以 $c^*(X)$ 的计算复杂度是对数级别的。

预计算的 $\hat{w}_j$ 的定义为

不仅如此，Verifier 需要计算 $c^*(X)$ 在某个挑战点上的取值 ，比如 $X=\xi$， Verifier 可以通过上面的等式，以 $O(\log{N})$ 时间复杂度根据 Prover 提供的 $\vec{c^*}$ 来计算 $c^*(\xi)$。

2. PH23+KZG10 协议（优化版）¶

对于 KZG10 协议，因为其 Commitment 具有加法同态性。

Precomputation¶

1. 预计算 $s_0(X),\ldots, s_{n-1}(X)$ and $v_H(X)$

2. 预计算 $D=(1, \omega, \omega^2, \ldots, \omega^{2^{n-1}})$ 上的 Bary-Centric Weights $\{\hat{w}_i\}$。这个可以加速

3. 预计算 Lagrange Basis 的 KZG10 SRS $A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1$

Common inputs¶

1. $C_a=[\hat{f}(\tau)]_1$: the (uni-variate) commitment of $\tilde{f}(X_0, X_1, \ldots, X_{n-1})$
2. $\vec{u}=(u_0, u_1, \ldots, u_{n-1})$: 求值点
3. $v=\tilde{f}(u_0,u_1,\ldots, u_{n-1})$: MLE 多项式 $\tilde{f}$ 在 $\vec{X}=\vec{u}$ 处的运算值

Commit 计算过程¶

1. Prover 构造一元多项式 $a(X)$，使其 Evaluation form 等于 $\vec{a}=(a_0, a_1, \ldots, a_{N-1})$，其中 $a_i = \tilde{f}(\mathsf{bits}(i))$, 为 $\tilde{f}$ 在 Boolean Hypercube $\{0,1\}^n$ 上的取值。

2. Prover 计算 $\hat{f}(X)$ 的承诺 $C_a$，并发送 $C_a$

其中 $A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1$ ，在预计算过程中已经得到。

Evaluation 证明协议¶

回忆下证明的多项式运算的约束：

这里 $\vec{u}=(u_0, u_1, u_2, \ldots, u_{n-1})$ 是一个公开的挑战点。

Round 1.¶

Prover:

1. 计算向量 $\vec{c}$，其中每个元素 $c_i=\overset{\sim}{eq}(\mathsf{bits}(i), \vec{u})$

2. 构造多项式 $c(X)$，其在 $H$ 上的运算结果恰好是 $\vec{c}$ 。

3. 计算 $c(X)$ 的承诺 $C_c= [c(\tau)]_1$，并发送 $C_c$

Round 2.¶

Verifier: 发送挑战数 $\alpha\leftarrow_{\$}\mathbb{F}_p$

Prover:

1. 构造关于 $\vec{c}$ 的约束多项式 $p_0(X),\ldots, p_{n}(X)$

2. 把 $\{p_i(X)\}$ 聚合为一个多项式 $p(X)$

3. 构造累加多项式 $z(X)$，满足

4. 构造约束多项式 $h_0(X), h_1(X), h_2(X)$，满足

5. 把 $p(X)$ 和 $h_0(X), h_1(X), h_2(X)$ 聚合为一个多项式 $h(X)$，满足

6. 计算 Quotient 多项式 $t(X)$，满足

7. 计算 $C_t=[t(\tau)]_1$， $C_z=[z(\tau)]_1$，并发送 $C_t$ 和 $C_z$

Round 3.¶

Verifier: 发送随机求值点 $\zeta\leftarrow_{\$}\mathbb{F}_p$

Prover:

1. 计算 $s_i(X)$ 在 ζ 处的取值：

这里 Prover 可以高效计算 $s_i(\zeta)$ ，由 $s_i(X)$ 的公式得

因此 $s_i(\zeta)$ 的值可以通过 $s_{i + 1}(\zeta)$ 计算得到，而

因此可以得到一个 $O(n)$ 的算法来计算 $s_i(\zeta)$ ，并且这里不含除法运算。计算过程是：$s_{n-1}(\zeta) \rightarrow s_{n-2}(\zeta) \rightarrow \cdots \rightarrow s_0(\zeta)$ 。

2. 定义求值 Domain $D'$，包含 $n+1$ 个元素：

3. 计算并发送 $c(X)$ 在 $D'$ 上的取值

4. 计算并发送 $z(\omega^{-1}\cdot\zeta)$

5. 计算 Linearized Polynomial $l_\zeta(X)$

显然，$l_\zeta(\zeta)= 0$，因此这个运算值不需要发给 Verifier，并且 $[l_\zeta(\tau)]_1$ 可以由 Verifier 自行构造。

6. 构造多项式 $c^*(X)$，它是下面向量在 $D\zeta$ 上的插值多项式

Prover 可以利用事先预计算的 $D$ 上的Bary-Centric Weights $\{\hat{w}_i\}$ 来快速计算 $c^*(X)$，

这里 $\hat{w}_j$ 为预计算的值：

7. 因为 $l_\zeta(\zeta)= 0$，所以存在 Quotient 多项式 $q_\zeta(X)$ 满足

8. 构造 $D\zeta$ 上的消失多项式 $z_{D_{\zeta}}(X)$

9. 构造 Quotient 多项式 $q_c(X)$ :

10. 构造 Quotient 多项式 $q_{\omega\zeta}(X)$

11. 发送 $\big(Q_c = [q_c(\tau)]_1, Q_\zeta=[q_\zeta(\tau)]_1, Q_{\omega\zeta}=[q_{\omega\zeta}(\tau)]_1, \big)$

Round 4.¶

1. Verifier 发送第二个随机挑战点 $\xi\leftarrow_{\$}\mathbb{F}_p$

2. Prover 构造第三个 Quotient 多项式 $q_\xi(X)$

3. Prover 计算并发送 $Q_\xi$

证明表示¶

$7\cdot\mathbb{G}_1$, $(n+1)\cdot\mathbb{F}$

验证过程¶

1. Verifier 计算 $c^*(\xi)$ 使用预计算的 Barycentric Weights $\{\hat{w}_i\}$

再计算对应的承诺 $C^*(\xi)=[c^*(\xi)]_1$ 。

2. Verifier 计算 $v_H(\zeta), L_0(\zeta), L_{N-1}(\zeta)$

3. Verifier 计算 $s_0(\zeta), \ldots, s_{n-1}(\zeta)$ ，其计算方法可以采用前文提到的递推方式进行计算。

4. Verifier 计算 $z_{D_\zeta}(\xi)$ ，

5. Verifier 计算线性化多项式的承诺 $C_l$

6. Verifier 产生随机数 η 来合并下面的 Pairing 验证：

合并后的验证只需要两个 Pairing 运算。

3. 优化性能分析¶

Proof size: $7~\mathbb{G}_1 + (n+1)~\mathbb{F}$

Prover’s cost

• Commit 阶段：$O(N\log N)~\mathbb{F}$ + $\mathbb{G}_1$
• Evaluation 阶段：$O(N\log N)~\mathbb{F}$ + $7~\mathbb{G}_1$

Verifier’s cost: $4~\mathbb{F} + O(n)~\mathbb{F}+ 3~\mathbb{G}_1 + 2~P$

References¶

• [BDFG20] Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. “Efficient polynomial commitment schemes for multiple points and polynomials”. Cryptology {ePrint} Archive, Paper 2020/081. https://eprint.iacr.org/2020/081.