缺失的协议 PH23-PCS（四）

• Jade Xie [email protected]
• Yu Guo [email protected]

本文给出 PH23 协议接一元多项式承诺 FRI-PCS 的方案。

对接 FRI¶

先回顾下 PH23 协议，对于一个 $n$ 元 MLE 多项式 $\tilde{f}(X_0,X_1, \ldots, X_{n - 1})$ ，其写成在 hypercube $\{0,1\}^n$ 上的点值形式：

其中 $N = 2^n$ 。当要证明该 MLE 多项式在一个点 $\vec{u} = (u_0, u_1, \ldots, u_{n-1})$ 的值为 $v$ 时，即

令 $c_i = \overset{\sim}{eq}(\mathsf{bits}(i), (u_0, u_1, \ldots, u_{n-1}))$ ，那么上面的求值证明就转换为证明一个内积

$\vec{c}$ 是 Prover 提供的，为了防止 Prover 作弊，需要证明 $\vec{c}$ 是正确构造的。PH23 协议的证明也就分为两部分：

1. 证明 $\vec{c}$ 是 Well-Formedness。
2. 证明内积 $\langle \vec{a}, \vec{c} \rangle = v$ 。

为了证明 1 的正确性，需要证明下面 $n + 1$ 个多项式在一个乘法子群 $H = \{\omega^0, \omega^1, \ldots, \omega^{N - 1}\}$ 上的值都为 0 。

为了证明 2 内积的正确性，采用 Grand Sum 方法来证明，构造出多项式 $z(X)$ ，用下面的多项式进行约束，这些多项式同样需要在 $H$ 上的取值为 0 ，

用 Verifier 给出的随机数 α 可以将上述 $n + 4$ 个多项式聚合成一个多项式 $h(X)$ ，

那么现在只需要说明 $h(X)$ 在 $H$ 上的取值都为 0 ，也就能完成 $\tilde{f}(u_0, u_1, \ldots, u_{n-1}) = v$ 的证明。取 $v_H(X)$ 为 $H$ 上的 Vanishing 多项式，那么存在一个商多项式 $t(X)$ ，满足

为了验证商多项式的存在性，Verifier 选取随机点 ζ ，似乎 Prover 发送 $t(\zeta), h(\zeta)$ 给 Verifier 就可以了，但其实，Prover 承诺的是 $a(X)$ ，$c(X)$ ，$z(X)$ ，$t(X)$ ，因此 Prover 发送的值

Verifier 拿着 Prover 发送的 $a(\zeta), c(\zeta), c(\zeta\cdot\omega), c(\zeta\cdot\omega^2), \ldots, c(\zeta\cdot\omega^{2^{n-1}}), z(\zeta), z(\zeta\cdot\omega^{-1})$ 可以自己计算出 $h(\zeta)$ ，$H$ 是公开的，因此 Verifier 可以自行计算出 $v_H(\zeta)$ ，然后验证

要让 Verifier 相信 Prover 发送过来的这些值没有问题，那么就要用一元多项式的 PCS 来实现。前面的文章已经介绍了用 KZG10 来实现，本文用 FRI-PCS 来进行证明。

通过上面多项式的构造过程，可以得知 $a(X), c(X), z(X), t(X)$ 的次数都为 $N - 1$ 。$a(X)$ 需要在 ζ 点打开，FRI-PCS 用到了 DEEP 技巧，记 Reed-Solomon 编码空间 $\mathsf{RS}_{k}[\mathbb{F},D]$ 表示

那么这里要求 Verifier 选取的随机数来自 $\zeta \stackrel{\$}{\leftarrow} \mathbb{F} \setminus D$ 。为了证明 $a(\zeta)$ 的正确性，需要证明商多项式

的次数小于 $N - 1$。

对于 $c(X)$ ，其要打开的点有 $n + 1$ 个，为 $H_{\zeta}' = \{\zeta, \zeta\cdot\omega, \zeta\cdot\omega^2, \ldots, \zeta\cdot\omega^{2^{n-1}} \}$ ，用 [H22] 论文在 Multi-point queries 小节介绍的方法同时打开多个点，令商多项式

这样转换为需要证明 $q_c(X)$ 的次数小于 $N - 1$ 。

对于 $z(X)$ ，类似地，证明商多项式

次数小于 $N - 1$ 。

对于 $t(X)$ ，证明商多项式

次数小于 $N - 1$ 。

这时，向 Verifier 要一个随机数 $r \stackrel{\$}{\leftarrow} \mathbb{F}$ ，可以将上面要证明的四个商多项式 batch 在一起，令

这样只需要调用一次 FRI 的 low degree test 就可以了，证明 $\deg(q'(X)) < N - 1$ 。最后为了对接 FRI low degree test 协议，需要将 $q'(X)$ 的次数对齐到 2 的幂次，即向 Verifier 要一个随机数 λ ，证明

的次数小于 $N$ 。

📝 Remark: 上面 batch 不同多项式时也可以从 $\mathbb{F}$ 中选取三个不同的随机数 $r_1, r_2,r_3$ ，令

$$> q'(X) = q_a(X) + r_1 \cdot q_c(X) + r_2 \cdot q_z(X) + r_3 \cdot q_t(X) >$$

(17)

这种方式会比上面用一个随机数的幂次进行 batch 有更高一点的安全性。([BCIKS20])

还有一点需要说明，由于我们用 DEEP 方法来构造商多项式，因此这里要求选取的随机数 ζ 构成打开点的集合与 Reed-Solomon 编码的群不能相交，即

PH23 + FRI 协议¶

证明目标：对于一个有 $n$ 个变量的 MLE 多项式 $\tilde{f}(X_0, X_1, \ldots, X_{n - 1})$ ，其表示为点值形式：

证明的目标是证明 $\tilde{f}(X_0, X_1, \ldots, X_{n - 1})$ 在点 $\vec{u} = (u_0,u_1, \ldots, u_{n - 1})$ 处的值为 $v = \tilde{f}(u_0,u_1, \ldots, u_{n - 1})$ 。

Commit 阶段¶

对于 FRI 协议，对多项式的承诺就是计算其 Reed-Solomon 编码，并对编码进行承诺。在 PCS 的 Commit 阶段需要对原 MLE 多项式进行承诺，即

$\vec{a}$ 就唯一确定了一个 $n$ 元 MLE 多项式，要对 MLE 多项式 $\tilde{f}$ 承诺其实就是对 $\vec{a}$ 进行承诺，若用 FRI 协议，那么就先要将 $\vec{a}$ 转换成多项式 $a(X)$ ，再对其在 $D$ 上的 Reed-Solomon 编码进行承诺。

1. Prover 构造一元多项式 $a(X)$ ，使其在 $H$ 上的求值为 $\vec{a} = (a_{0,}a_{1},\ldots, a_{N-1})$ 。

2. Prover 计算多项式 $a(X)$ 的承诺 $C_a$ ，并将 $C_a$ 发送给 Verifier

公共输入¶

1. FRI 协议参数：Reed Solomon 编码选取的区域 $D_n \subset D_{n-1} \subset \cdots \subset D_0 = D$ ，码率 ρ ，查询阶段的次数 $l$ 。
2. 承诺 $C_a$

3. 求值点 $\vec{u} = (u_0,u_1, \ldots, u_{n - 1})$
4. $v = \tilde{f}(u_0,u_1, \ldots, u_{n - 1})$

Witness¶

• 多元多项式 $\tilde{f}(X_0, X_1, \ldots, X_{n - 1})$ 的在 Boolean Hypercube 上的取值 $\vec{a} = (a_0,a_1, \ldots, a_{N-1})$

Evaluation 证明协议¶

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_c$

Round 2¶

Verifier: 发送挑战数 $\alpha \stackrel{\$}{\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. 计算 $t(X)$ 和 $z(X)$ 的承诺 $C_t, C_z$ ，并发送给 Verifier

Round 3¶

Verifier: 发送随机求值点 $\zeta \stackrel{\$}{\leftarrow} \mathbb{F}_p^* \setminus D$

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 $H_\zeta'$，包含 $n+1$ 个元素：

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

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

Round 4¶

Verifier: 发送随机数 $r \stackrel{\$}{\leftarrow} \mathbb{F}_p$

Prover:

1. 计算商多项式 $q_a(X)$

2. 计算商多项式 $q_c(X)$

3. 计算商多项式 $q_z(X)$

4. 计算商多项式 $q_t(X)$

5. 将上面的四个商多项式用随机数 $r$ 的幂次 batch 成一个多项式

Round 5¶

这一轮将商多项式 $q'(X)$ 对齐到 2 的幂次，以对接 FRI 协议。

1. Verifier 发送随机数 $\lambda \stackrel{\$}{\leftarrow} \mathbb{F}$
2. Prover 计算

在 $D$ 上的值。

Round 6¶

Prover 和 Verifier 进行 FRI 的 low degree test 证明交互，证明 $q(X)$ 的次数小于 $2^n$ 。

这里包含 $n$ 轮的交互，直到最后将原来的多项式折叠为常数多项式。下面用 $i$ 表示第 $i$ 轮，具体交互过程如下：

• 记 $q^{(0)}(x)|_{x \in D} := q(x)|_{x \in D}$

• 对于 $i = 1,\ldots, n$ ，

  • Verifier 发送随机数 $\alpha^{(i)}$
  • 对于任意的 $y \in D_i$ ，在 $D_{i - 1}$ 中找到 $x$ 满足 $x^2 = y$，Prover 计算
  $$q^{(i)}(y) = \frac{q^{(i - 1)}(x) + q^{(i - 1)}(-x)}{2} + \alpha^{(i)} \cdot \frac{q^{(i - 1)}(x) - q^{(i - 1)}(-x)}{2x}$$

  (45)
  • 如果 $i < n$ ，Prover 发送 $[q^{(i)}(x)|_{x \in D_{i}}]$ 的 Merkle Tree 承诺，
  $$\mathsf{cm}(q^{(i)}(X)) = \mathsf{cm}([q^{(i)}(x)|_{x \in D_{i}}]) = \mathsf{MT.commit}([q^{(i)}(x)|_{x \in D_{i}}])$$

  (46)
  • 如果 $i = n$ ，任选 $x_0 \in D_{n}$ ，Prover 发送 $q^{(i)}(x_0)$ 的值。

📝 Notes

如果折叠次数 $r < n$ ，那么最后不会折叠到常数多项式，因此 Prover 在第 $r$ 轮时会发送一个 Merkle Tree 承诺，而不是发送一个值。

Round 7¶

这一轮是接着 Prover 与 Verifier 进行 FRI 协议的 low degree test 交互的查询阶段，Verifier 重复查询 $l$ 次，每一次 Verifier 都会从 $D_0$ 中选取一个随机数，让 Prover 发送在第 $i$ 轮折叠的值及对应的 Merkle Path，用来让 Verifier 验证每一轮折叠的正确性。

重复 $l$ 次：

• Verifier 从 $D_0$ 中随机选取一个数 $s^{(0)} \stackrel{\$}{\leftarrow} D_0$
• Prover 打开 $a(s^{(0)}), a(-s^{(0)},c(s^{(0)}),c(-s^{(0)}),z(s^{(0)}),z(-s^{(0)}),t(s^{(0)}),t(-s^{(0)})$ 的承诺，即这些点的值与对应的 Merkle Path，并发送给 Verifier

• Prover 计算 $s^{(1)} = (s^{(0)})^2$

• 对于 $i = 1, \ldots, n - 1$

  • Prover 发送 $q^{(i)}(s^{(i)}), q^{(i)}(-s^{(i)})$ 的值，并附上 Merkle Path。
  $$\{(q^{(i)}(s^{(i)}), \pi_{q^{(i)}}(s^{(i)}))\} \leftarrow \mathsf{MT.open}([q^{(i)}(x)|_{x \in D_i}], s^{(i)})$$

  (55)

• Prover 计算 $s^{(i + 1)} = (s^{(i)})^2$

如果折叠次数 $r < n$ ，那么最后一步就要发送 $q^{(r)}(s^{(r)})$ 的值，并附上 Merkle Path。

Proof¶

Prover 发送的证明为

用符号 $\{\cdot\}^l$ 表示在 FRI low degree test 的查询阶段重复查询 $l$ 次产生的证明，由于每次查询是随机选取的，因此花括号中的证明也是随机的。那么 FRI 进行 low degree test 的证明为

Verification¶

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

3. Verifier 计算 $p(\zeta)$

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

5. Verifier 计算 $h_0(\zeta), h_1(\zeta), h_2(\zeta)$

6. Verifier 计算 $h(\zeta)$

7. Verifier 验证商多项式的正确性

8. Verifier 验证 $q(X)$ 的 low degree test 证明，

具体验证过程为，重复 $l$ 次：

• 验证 $a(s^{(0)}), a(-s^{(0)},c(s^{(0)}),c(-s^{(0)}),z(s^{(0)}),z(-s^{(0)}),t(s^{(0)}),t(-s^{(0)})$ 的正确性 ，验证