Zeromorph-PCS : 对接 FRI

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

之前的文章介绍了 zeromorph 协议对接 KZG 做多元线性多项式的 PCS 协议，这里介绍 zeromorph 协议接 FRI 对应的 PCS 协议。

对接 FRI¶

在之前的文章中已经介绍过，zeromorph 协议最后转换为证明一个关键的等式

以及要求商多项式 $\hat{q}_k(X)$ 的次数都小于 $2^k$ ，来防止 Prover 作弊。

为了证明上面的等式成立，Verifier 可以随机选取一个点 $X = \zeta$ ，然后让 Prover 提供 $\hat{f}(\zeta)$ 和 $\hat{q}_k(\zeta)$ 的值，以便于 Verifier 验证下面的等式是否成立：

用 zeromorph 对接 FRI 协议时，可以用 FRI 协议实现的 PCS 来提供 $\hat{f}(\zeta)$ 和 $\hat{q}_k(\zeta)$ 的值，并用 FRI 协议的 low degree test 来证明 $\deg(\hat{q_k}) < 2^k$ 。

例如 Prover 要证明发送的 $\hat{f}(\zeta)$ 值的正确性。证明该值正确，等价于证明商多项式

存在。要证明该商多项式存在，就等价要证明其次数小于 $2^{n} - 1$ 。为了对接 FRI 协议来进行 low degree test ，这里次数需要对齐到 2 的幂次，因此还需要做 degree correction。这时可以向 Verifier 要一个随机数 $\lambda$ ，令

用 FRI 协议来证明该商多项式的次数小于 $2^n$ 。

Commit 阶段¶

要承诺一个有 $n$ 个未知数的 MLE 多项式，

首先直接将其在 hypercube 上的取值 $(a_0, \ldots, a_{N - 1})$ 映射到一元多项式 $\hat{f}(X)$ ，

对于 FRI 协议，选取 $\mathbb{F}$ 中的一个大小为 2 的幂次的乘法子群 $D = D_0$ ，并且有

其中 $|D_{i - 1}|/|D_{i}| = 2$ ，码率 $\rho = N / |D_0|$ 。下面的协议中以折叠 $n$ 次，即最后折叠到常数多项式来描述，实际中也可以折叠到一个次数比较小的多项式，协议流程会有细微差别。那么 FRI 协议对函数 $\hat{f}$ 的承诺为承诺 $\hat{f}(X)$ 在 $D$ 上的 Reed-Solomon 编码，即

实际实现中，一般用 Merkle 树来承诺 $[\hat{f}(x)|_{x \in D}]$ ，记为

Prover 发送的是这棵 Merkle 树的根哈希值，来作为 $[\hat{f}(x)|_{x \in D}]$ 的承诺。

Evaluation 证明协议¶

公共输入¶

• MLE 多项式 $\tilde{f}$ 的承诺 $\mathsf{cm}([[\tilde{f}]]_n)$
• 求值点 $\mathbf{u}=(u_0, u_1, \ldots, u_{n-1})$
• 求值结果 $v = \tilde{f}(\mathbf{u})$
• 码率参数：$\rho$
• FRI 协议中进行 low degree test 查询阶段的重复查询的次数参数: $l$ （实际中 $l$ 的取值与安全性参数，安全假设以及码率相关）
• FRI 协议中编码的乘法子群：$D, D^{(0)}, \ldots, D^{(n - 1)}$

Witness¶

• MLE 多项式 $\tilde{f}$ 在 $n$ 维 HyperCube 上的点值向量 $\mathbf{a} = (a_0, a_1, \ldots, a_{2^n-1})$

Round 1¶

Prover 发送余数多项式的承诺

• 计算 $n$ 个余数 MLE 多项式， $\{\tilde{q}_k\}_{k=0}^{n-1}$ ，其满足

• 构造余数 MLE 多项式所映射到的 Univariate 多项式 $\hat{q}_k=[[\tilde{q}_k]]_k, \quad 0 \leq k < n$
• 计算并发送它们的承诺：$\mathsf{cm}(\hat{q}_0), \mathsf{cm}(\hat{q}_1), \ldots, \mathsf{cm}(\hat{q}_{n-1})$ ，这里承诺 $\mathsf{cm}(\hat{q}_0), \mathsf{cm}(\hat{q}_1), \ldots, \mathsf{cm}(\hat{q}_{n-1})$ 为 $\hat{q}_0, \ldots, \hat{q}_{n - 1}$ 的 FRI 承诺，取 $\hat{q}_k$ 的乘法子群为 $D^{(k)} = D^{(k)}_0$ ，对应的承诺为

其中 $|D^{(k)}| = 2^k / \rho$ 。

Round 2¶

1. Verifier 发送随机数 $\zeta \stackrel{\$}{\leftarrow} \mathbb{F} \setminus D$
2. Prover 计算并发送 $\hat{f}(\zeta)$
3. Prover 计算并发送 $\hat{q}_k(\zeta), \, 0 \le k < n$ 。

Round 3¶

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

在 $D$ 上的值，即

3. 对于 $0 \le k < n$ ，Prover 计算

在 $D^{(k)}$ 上的值。

Round 4¶

Prover 与 Verifier 进行 FRI 协议的 low degree test 交互，证明 $q_{f_\zeta}(X)$ 的次数小于 $2^n$ ，

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

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

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

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

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

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

📝 Notes

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

Round 5¶

这一轮是接着 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 发送 $\hat{f}(s^{(0)}), \hat{f}(- s^{(0)})$ 的值，并附上 Merkle Path。

  $$\{(\hat{f}(s^{(0)}), \pi_{\hat{f}}(s^{(0)}))\} \leftarrow \mathsf{MT.open}([\hat{f}(x)|_{x \in D_0}], s^{(0)})$$

  (18)
  $$\{(\hat{f}(-s^{(0)}), \pi_{\hat{f}}(-s^{(0)}))\} \leftarrow \mathsf{MT.open}([\hat{f}(x)|_{x \in D_0}], -s^{(0)})$$

  (19)

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

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

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

  (20)
  $$\{(q_{f_\zeta}^{(i)}(-s^{(i)}), \pi_{q_{f_\zeta}}^{(i)}(-s^{(i)}))\} \leftarrow \mathsf{MT.open}([q_{f_\zeta}^{(i)}(x)|_{x \in D_i}], -s^{(i)})$$

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

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

Round 6¶

1. Prover 与 Verifier 进行 FRI 协议的 low degree test 交互，对于 $0 \le k < n$ ，证明 $q_{\hat{q}_k}(X)$ 的次数小于 $2^k$ ，

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

• 记 $q_{\hat{q}_k}^{(0)}(x)|_{x \in D^{(k)}} := q_{f_\zeta}(x)|_{x \in D^{(k)}}$

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

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

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

  (24)
  • 如果 $i = k$ ，任选 $y_0^{(k)} \in D_{n}$ ，Prover 发送 $q_{\hat{q}_k}^{(i)}(y_0^{(k)})$ 的值。

📝 Notes

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

Round 7¶

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

对于 $k = 0, \ldots, n - 1$， Verifier 重复查询 $l$ 次：

• Verifier 从 $D_0^{(k)}$ 中随机选取一个数 $s_k^{(0)} \stackrel{\$}{\leftarrow} D_0^{(k)}$

• Prover 发送 $\hat{q}_k(s_k^{(0)}), \hat{q}_k(- s_k^{(0)})$ 的值，并附上 Merkle Path。

  $$\{(\hat{q}_k(s_k^{(0)}), \pi_{\hat{q}_k}(s_k^{(0)}))\} \leftarrow \mathsf{MT.open}([\hat{q}_k(x)|_{x \in D_0^{(k)}}], s^{(0)})$$

  (25)
  $$\{(\hat{q}_k(-s_k^{(0)}), \pi_{\hat{q}_k}(-s_k^{(0)}))\} \leftarrow \mathsf{MT.open}([\hat{q}_k(x)|_{x \in D_0^{(k)}}], -s^{(0)})$$

  (26)

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

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

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

  (27)
  $$\{(q_{\hat{q}_k}^{(i)}(-s_k^{(i)}), \pi_{q_{\hat{q}_k}^{(i)}}(-s_k^{(i)}))\} \leftarrow \mathsf{MT.open}([q_{\hat{q}_k}^{(i)}(x)|_{x \in D_i^{(k)}}], -s_k^{(i)})$$

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

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

Proof¶

Prover 发送的证明为

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

对于 $k = 0, \ldots, n - 1$，

Verification¶

Verifier

1. 验证 $q_{f_\zeta}(X)$ 的 low degree test 证明，

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

• 验证 $\hat{f}(s^{(0)}), \hat{f}(-s^{(0)})$ 的正确性

• Verifier 计算

  $$q_{f_\zeta}^{(0)}(s^{(0)}) = (1 + \lambda \cdot s^{(0)}) \cdot \frac{\hat{f}(s^{(0)}) - \hat{f}(\zeta)}{s^{(0)} - \zeta}$$

  (35)
  $$q_{f_\zeta}^{(0)}(- s^{(0)}) = (1 - \lambda \cdot s^{(0)}) \cdot\frac{\hat{f}(-s^{(0)}) - \hat{f}(\zeta)}{-s^{(0)} - \zeta}$$

  (36)

• 验证 $q_{f_\zeta}^{(1)}(s^{(1)}), q_{f_\zeta}^{(1)}(-s^{(1)})$ 的正确性

• 验证第 1 轮的折叠是否正确

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

  • 验证 $q_{f_\zeta}^{(i)}(s^{(i)}), q_{f_\zeta}^{(i)}(-s^{(i)})$ 的正确性
  $$\mathsf{MT.verify}(\mathsf{cm}(q_{f_\zeta}^{(i)}(X)), q_{f_\zeta}^{(i)}(s^{(i)}), \pi_{q_{f_\zeta}^{(i)}}(s^{(i)})) \stackrel{?}{=} 1$$

  (40)
  $$\mathsf{MT.verify}(\mathsf{cm}(q_{f_\zeta}^{(i)}(X)), q_{f_\zeta}^{(i)}(-s^{(i)}), \pi_{q_{f_\zeta}^{(i)}}(-s^{(i)})) \stackrel{?}{=} 1$$

  (41)
  • 验证第 $i$ 轮的折叠是否正确
    $$q_{f_\zeta}^{(i)}(s^{(i)}) \stackrel{?}{=} \frac{q_{f_\zeta}^{(i-1)}(s^{(i - 1)}) + q_{f_\zeta}^{(i - 1)}(- s^{(i - 1)})}{2} + \alpha^{(i)} \cdot \frac{q_{f_\zeta}^{(i - 1)}(s^{(i - 1)}) - q_{f_\zeta}^{(i - 1)}(- s^{(i - 1)})}{2 \cdot s^{(i - 1)}}$$

    (42)

• 验证最后是否折叠到常数多项式

  $$q_{f_\zeta}^{(n)}(x_0) \stackrel{?}{=} \frac{q_{f_\zeta}^{(n-1)}(s^{(n - 1)}) + q_{f_\zeta}^{(n - 1)}(- s^{(n - 1)})}{2} + \alpha^{(n)} \cdot \frac{q_{f_\zeta}^{(n - 1)}(s^{(n - 1)}) - q_{f_\zeta}^{(n - 1)}(- s^{(n - 1)})}{2 \cdot s^{(n - 1)}}$$

  (43)

2. 对于 $k = 0, \ldots, n - 1$ ，验证 $q_{\hat{q}_k}(X)$ 的 low degree test 证明，

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

• 验证 $\hat{q}_k(s_k^{(0)}), \hat{q}_k(-s_k^{(0)})$ 的正确性

• Verifier 计算

  $$q_{\hat{q}_k}^{(0)}(s_k^{(0)}) = (1 + \lambda \cdot s_k^{(0)}) \cdot \frac{\hat{q}_k(s_k^{(0)})- \hat{q}_k(\zeta)}{s_k^{(0)} - \zeta}$$

  (47)
  $$q_{\hat{q}_k}^{(0)}(-s_k^{(0)}) = (1 - \lambda \cdot s_k^{(0)}) \cdot \frac{\hat{q}_k(-s_k^{(0)})- \hat{q}_k(\zeta)}{-s_k^{(0)} - \zeta}$$

  (48)

• 验证 $q_{\hat{q}_k}^{(1)}(s_k^{(1)}),q_{\hat{q}_k}^{(1)}(-s_k^{(1)}),$ 的正确性

• 验证第 1 轮的折叠是否正确

• 对于 $i = 2, \ldots, k - 1$

  • 验证 $q_{\hat{q}_k}^{(i)}(s_k^{(i)}), q_{\hat{q}_k}^{(i)}(-s_k^{(i)})$ 的正确性
  $$\mathsf{MT.verify}(\mathsf{cm}(q_{\hat{q}_k}^{(i)}(X)), q_{\hat{q}_k}^{(i)}(s_k^{(i)}), \pi_{q_{\hat{q}_k}^{(i)}}(s_k^{(i)})) \stackrel{?}{=} 1$$

  (52)
  $$\mathsf{MT.verify}(\mathsf{cm}(q_{\hat{q}_k}^{(i)}(X)), q_{\hat{q}_k}^{(i)}(-s_k^{(i)}), \pi_{q_{\hat{q}_k}^{(i)}}(-s_k^{(i)})) \stackrel{?}{=} 1$$

  (53)
  • 验证第 $i$ 轮的折叠是否正确
    $$q_{\hat{q}_k}^{(i)}(s_k^{(i)}) \stackrel{?}{=} \frac{q_{\hat{q}_k}^{(i - 1)}(s_k^{(i - 1)}) + q_{\hat{q}_k}^{(i - 1)}(- s_k^{(i - 1)})}{2} + \beta_k^{(i)} \cdot \frac{q_{\hat{q}_k}^{(i - 1)}(s_k^{(i - 1)}) - q_{\hat{q}_k}^{(i - 1)}(- s_k^{(i - 1)})}{2 \cdot s_k^{(i - 1)}}$$

    (54)

• 验证最后是否折叠到常数多项式

  $$q_{\hat{q}_k}^{(k)}(y_0^{(k)}) \stackrel{?}{=} \frac{q_{\hat{q}_k}^{(k - 1)}(s_k^{(k - 1)}) + q_{\hat{q}_k}^{(k - 1)}(- s_k^{(k - 1)})}{2} + \beta_k^{(k)} \cdot \frac{q_{\hat{q}_k}^{(k - 1)}(s_k^{(k - 1)}) - q_{\hat{q}_k}^{(k - 1)}(- s_k^{(k - 1)})}{2 \cdot s_k^{(k - 1)}}$$

  (55)

3. 计算 $\Phi_n(\zeta)$ 以及 $\Phi_{n - k}(\zeta^{2^k})(0 \le k < n)$ ，满足

4. 验证下述等式的正确性

Zeromorph 对接 FRI 优化协议¶

在上述的协议中，会对 $n$ 个一元多项式 $\hat{q}_k(X)$ 进行承诺以及用 FRI 协议分别进行 low degree test 的证明，实际上，由于要证明的 $\hat{q}_{k}(X)$ 与 $\hat{q}_{k - 1}(X)$ 之间的 degree bound 刚好相差 2 倍，因此可以用 rolling batch 的技巧对这 $n$ 个多项式只进行一次 low degree test。另外注意到，$\hat{f}(X)$ 与 $\hat{q}_{n-1}(X)$ 之间的 degree bound 也刚好相差 2 倍，因此还可以用 rolling batch [ZLGSCLD24] 的技巧对 $\hat{f}(X), \hat{q}_{n-1}(X), \ldots, \hat{q}_{0}(X)$ 这 $n + 1$ 个多项式只进行一次 low degree test。