Zeromorph 系列协议复杂度分析

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

Evaluation 证明协议（朴素版）复杂度分析¶

协议描述文档：Evaluation 证明协议（朴素版）

下面我们先给出一个简单朴素的协议实现，方便理解。

公共输入¶

• MLE 多项式 $\tilde{f}$ 的承诺 $\mathsf{cm}([[\tilde{f}]]_n)$
• 求值点 $\mathbf{u}=(u_0, u_1, \ldots, u_{n-1})$
• 求值结果 $v = \tilde{f}(\mathbf{u})$

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})$

Prover 计算，$\pi_k=\mathsf{cm}(X^{D_{max}-2^k+1}\cdot \hat{q}_k), \quad 0\leq k<n$ ，作为 $\deg(\hat{q}_k)<2^k$ 的 Degree Bound 证明 ，一并发送给 Verifier

Prover:

• 直接用 Zeromorph 论文 Appendix A.2 的算法能计算出 $\tilde{q}_k$ 在 Hypercube 上的值，即可以得到 $Q_k$ 的系数，根据论文的结论，整个算法复杂度为 $(2^{n+1} - 3) ~ \mathbb{F}_{\mathsf{add}}$ 以及 $(2^{n} - 2) ~ \mathbb{F}_{\mathsf{mul}}$ 。这里不计入加法的复杂度，因此计算出 $\hat{q}_k=[[\tilde{q}_k]]_k, \quad 0 \leq k < n$ 的复杂度为 $(2^{n} - 2) ~ \mathbb{F}_{\mathsf{mul}}$ 。
• 计算 $\mathsf{cm}(\hat{q}_0), \mathsf{cm}(\hat{q}_1), \ldots, \mathsf{cm}(\hat{q}_{n-1})$ ，这里涉及 MSM 算法，对于每一个 $\mathsf{cm}(\hat{q}_{k})$ ，多项式 $q_{k}$ 的系数有 $2^k$ 个，复杂度为 $\mathsf{msm}(2^k,\mathbb{G}_1)$ ，因此这一步的总复杂度为
  $$\sum_{k=0}^{n-1} \mathsf{msm}(2^k,\mathbb{G}_1)$$

  (2)
• 计算 $\pi_k=\mathsf{cm}(X^{D_{max}-2^k+1}\cdot \hat{q}_k), \quad 0\leq k<n$ ，
  • 计算 $X^{D_{max}-2^k+1}\cdot \hat{q}_k$ ，这里涉及多项式的乘法，$\deg(\hat{q}_k) = 2^k - 1$ ，复杂度记为 $\mathsf{polymul}(D_{max} - 2^k + 1, 2^k - 1)$ ，因此总复杂度为
    $$\sum_{k=0}^{n-1} \mathsf{polymul}(D_{max} - 2^k + 1, 2^k - 1)$$

    (3)
  • 计算 $\pi_k=\mathsf{cm}(X^{D_{max}-2^k+1}\cdot \hat{q}_k), \quad 0\leq k<n$ ，复杂度为
    $$\sum_{k=0}^{n-1} \mathsf{msm}(D_{max} + 1,\mathbb{G}_1) = n ~ \mathsf{msm}(D_{max} + 1,\mathbb{G}_1)$$

    (4)
    因此这一步的总复杂度为
    $$\sum_{k=0}^{n-1} \mathsf{polymul}(D_{max} - 2^k + 1, 2^k - 1) + n ~ \mathsf{msm}(D_{max} + 1,\mathbb{G}_1)$$

    (5)

因此这一轮的总复杂度为

$$> (2^{n} - 2) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k=0}^{n-1} \mathsf{msm}(2^k,\mathbb{G}_1) + \sum_{k=0}^{n-1} \mathsf{polymul}(D_{max} - 2^k + 1, 2^k - 1) + n ~ \mathsf{msm}(D_{max} + 1,\mathbb{G}_1) >$$

(6)

💡 这里计算多项式的乘法，$X^{D_{max}-2^k+1}\cdot \hat{q}_k$ 应该可以优化，直接挪动 $\hat{q}_k$ 的系数就可以了。

Round 2¶

1. Verifier 发送随机数 $\zeta\in \mathbb{F}_p^*$

2. Prover 计算辅助多项式 $r(X)$ 与商多项式 $h(X)$，并发送 $\mathsf{cm}(h)$

• 计算 $r(X)$ ，

• 计算 $h(X)$ 及其承诺 $\mathsf{cm}(h)$， 作为 $r(X)$ 在 $X=\zeta$ 点取值为零的证明

• 修改计算 $\Phi_n(\zeta)$ 的复杂度

Prover:

• 先根据随机数 $\zeta$ 计算出 $\zeta$ 的幂次，即 $\zeta^2, \ldots, \zeta^{2^{n}}$ ，涉及 $n$ 次有限域的乘法，复杂度为 $n ~ \mathbb{F}_{\mathsf{mul}}$ 。

• 计算 $r(X)$ ，

  • 计算 $\Phi_n(\zeta)$,
    $$\Phi_n(\zeta) = \sum_{i=0}^{n-1} \zeta^{2^i}$$

    (9)

  这里可以直接用前面计算出的 $\zeta$ 的幂次直接进行累加，涉及到的是有限域的加法，因此不做记录。

  • 计算 $v \cdot \Phi_n(\zeta)$ ，涉及一次有限域乘法，复杂度为 $\mathbb{F}_{\mathsf{mul}}$ 。
  • 计算 $\Phi_{n-k-1}(\zeta^{2^{k+1}})$ ，由于
    $$\Phi_{n-k-1}(X^{2^{k+1}}) = 1 + X^{2^{k + 1}} + X^{2 \cdot 2^{k + 1}} + \ldots + X^{(2^{n - k - 1} - 1) \cdot 2^{k + 1}}$$

    (10)
    因此
    $$\Phi_{n-k-1}(\zeta^{2^{k+1}}) = 1 + \zeta^{2^{k + 1}} + \zeta^{2 \cdot 2^{k + 1}} + \ldots + \zeta^{(2^{n - k - 1} - 1) \cdot 2^{k + 1}}$$

    (11)
    这里依然可以通过有限域的加法直接计算得到，同理对于计算 $\Phi_{n-k}(\zeta^{2^{k}})$ 也是一样的，通过有限域的加法得到。
  • 计算 $\zeta^{2^k}\cdot \Phi_{n-k-1}(\zeta^{2^{k+1}}) - u_k\cdot \Phi_{n-k}(\zeta^{2^{k}})$ 这里就涉及两次有限域的乘法，复杂度为 $2 ~ \mathbb{F}_{\mathsf{mul}}$ ， $k$ 次累加就为 $2n ~ \mathbb{F}_{\mathsf{mul}}$ 。
  • 计算 $\Big(\zeta^{2^k}\cdot \Phi_{n-k-1}(\zeta^{2^{k+1}}) - u_k\cdot \Phi_{n-k}(\zeta^{2^{k}})\Big)\cdot \hat{q}_k(X)$ ，涉及多项式的乘法，复杂度为 $\mathsf{polymul}(0, 2^k - 1)$ 。$k$ 经过累加之后，总复杂度为
    $$\sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1)$$

    (12)
    因此计算 $r(X)$ 的总复杂度为
  $$> \mathbb{F}_{\mathsf{mul}} + 2n ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) = (2n + 1) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) >$$

  (13)

• 计算 $\mathsf{cm}(h)$ ，先计算 $h(X)$ ，其可以用线性除法的方式得到，复杂度与 $r(X)$ 的次数相关，由于 $\deg(r) = 2^{n - 1} - 1$ ，因此这里多项式除法的复杂度为 $(2^{n - 1} - 1) ~ \mathbb{F}_{\mathsf{mul}}$ ，接着计算承诺，其复杂度为 $\mathsf{msm}(2^{n - 1} - 1, \mathbb{G}_1)$ 。 这里总复杂度为

  $$(2^{n - 1} - 1) ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{msm}(2^{n - 1} - 1, \mathbb{G}_1)$$

  (14)

这一轮的总复杂度为：

$$(3n + 2^{n - 1}) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) + \mathsf{msm}(2^{n - 1} - 1, \mathbb{G}_1)$$

(15)

Verification¶

Verifier 验证下面的等式

• 构造 $\mathsf{cm}(r)$ 的承诺：

• 验证 $r(\zeta) = 0$

• 验证 $(\pi_0, \pi_1, \ldots, \pi_{n-1})$ 是否正确，即验证所有的余数多项式的 Degree Bound： $\deg(\hat{q}_i)<2^i$ ，对于 $0\leq i<n$

Verifier:

• 构造 $\mathsf{cm}(r)$ 的承诺

  • 先根据随机数 $\zeta$ 计算出 $\zeta$ 的幂次，即 $\zeta^2, \ldots, \zeta^{2^{n}}$ ，涉及 $n$ 次有限域的乘法，复杂度为 $n ~ \mathbb{F}_{\mathsf{mul}}$ 。
  • $\mathsf{cm}(v\cdot \Phi_{n}(\zeta))$ ，复杂度为 $\mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1}$
  • 计算 $\sum_{i=0}^{n-1} \Big(\zeta^{2^i}\cdot \Phi_{n-i-1}(\zeta^{2^{i+1}}) - u_i\cdot \Phi_{n-i}(\zeta^{2^{i}})\Big)\cdot \mathsf{cm}(\hat{q}_i)$ ，复杂度为
    $$n( 2 ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1}) + (n - 1) ~ \mathsf{EccAdd}^{\mathbb{G}_1} = 2n ~ \mathbb{F}_{\mathsf{mul}} + n ~ \mathsf{EccMul}^{\mathbb{G}_1} + (n - 1) ~ \mathsf{EccAdd}^{\mathbb{G}_1}$$

    (19)
  • 计算 $\mathsf{cm}([[\tilde{f}]]_{n}) - \mathsf{cm}(v\cdot \Phi_{n}(\zeta)) - \sum_{i=0}^{n-1} \Big(\zeta^{2^i}\cdot \Phi_{n-i-1}(\zeta^{2^{i+1}}) - u_i\cdot \Phi_{n-i}(\zeta^{2^{i}})\Big)\cdot \mathsf{cm}(\hat{q}_i)$ ，就是三个椭圆曲线上的点相加，复杂度为 $2 ~ \mathsf{EccAdd}^{\mathbb{G}_1}$ 。

  构造 $r$ 的承诺的总复杂度为

  $$(3n + 1)~ \mathbb{F}_{\mathsf{mul}} + (n + 1) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (n + 1) ~ \mathsf{EccAdd}^{\mathbb{G}_1}$$

  (20)

• 验证 $r(\zeta) = 0$

  • 计算 $[\tau]_2 - \zeta\cdot [1]_2$ ，复杂度为 $\mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2}$
  • 计算 $e(\mathsf{cm}(r), \ [1]_2)$ 与 $e(\mathsf{cm}(h), [\tau]_2 - \zeta\cdot [1]_2)$ ，涉及两个椭圆曲线上的配对操作，记为 $2~P$ 。

  这一步的总复杂度为

  $$\mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2} + 2~P$$

  (21)

• 验证 $(\pi_0, \pi_1, \ldots, \pi_{n-1})$ 是否正确，

  $$e(\mathsf{cm}(\hat{q}_i), [\tau^{D_{max}-2^i+1}]_2) = e(\pi_i, [1]_2), \quad 0\leq i<n$$

  (22)

  这里每一次涉及的复杂度为 $2 ~ P$ ，因此总复杂度为 $2n ~ P$ 。

这一轮的总复杂度为

$$> (3n + 1)~ \mathbb{F}_{\mathsf{mul}} + (n + 1) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (n + 1) ~ \mathsf{EccAdd}^{\mathbb{G}_1} + \mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2} + (2n + 2)~P >$$

(23)

汇总¶

Prover 计算复杂度：

$$> \begin{aligned} > & (2^{n} - 2) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k=0}^{n-1} \mathsf{msm}(2^k,\mathbb{G}_1) + \sum_{k=0}^{n-1} \mathsf{polymul}(D_{max} - 2^k + 1, 2^k - 1) + n ~ \mathsf{msm}(D_{max} + 1,\mathbb{G}_1) \\ > & + (3n + 2^{n - 1}) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) + \mathsf{msm}(2^{n - 1} - 1, \mathbb{G}_1) \\ > = & ( 3 \cdot 2^{n - 1} + 3n - 2) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k=0}^{n-1} \mathsf{polymul}(D_{max} - 2^k + 1, 2^k - 1) + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) \\ > & + \sum_{k=0}^{n-1} \mathsf{msm}(2^k,\mathbb{G}_1) + n ~ \mathsf{msm}(D_{max} + 1,\mathbb{G}_1) + \mathsf{msm}(2^{n - 1} - 1, \mathbb{G}_1) > \end{aligned} >$$

(24)

Verifier 计算复杂度：

$$> (3n + 1)~ \mathbb{F}_{\mathsf{mul}} + (n + 1) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (n + 1) ~ \mathsf{EccAdd}^{\mathbb{G}_1} + \mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2} + (2n + 2)~P >$$

(25)

证明大小：

Prover 发送的证明有

$$> (\mathsf{cm}(\hat{q}_0), \mathsf{cm}(\hat{q}_1), \ldots, \mathsf{cm}(\hat{q}_{n-1}), \pi_0, \ldots, \pi_{n - 1}, \mathsf{cm}(h)) >$$

(26)

总计为 $(2n + 1) \mathbb{G}_1$ .

代入多项式相乘的复杂度 $\mathsf{polymul}(a, b) = (a + 1) (b + 1) ~ \mathbb{F}_{\mathsf{mul}} = (ab + a + b + 1) ~ \mathbb{F}_{\mathsf{mul}}$ ，得到

Prover 复杂度：

Verifier 复杂度：

Proof size:

Evaluation 证明协议（优化版-Degree Bound 聚合）¶

协议描述文档：Evaluation 证明协议（优化版）

公共输入¶

• MLE 多项式 $\tilde{f}$ 映射到 Univariate 多项式 $f(X)=[[\tilde{f}]]_n$ 的承诺 $\mathsf{cm}([[\tilde{f}]]_n)$
• 求值点 $\mathbf{u}=(u_0, u_1, \ldots, u_{n-1})$
• 求值结果 $v = \tilde{f}(\mathbf{u})$

Witness¶

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

Round 1¶

第一轮：Prover 发送余数多项式的承诺

• 计算 $n$ 个余数 MLE 多项式， $\{q_i\}_{i=0}^{n-1}$
• 构造余数 MLE 多项式所映射到的 Univariate 多项式 $\hat{q}_i=[[q_i]]_i, \quad 0 \leq i < n$
• 计算并发送它们的承诺：$\mathsf{cm}(\hat{q}_0), \mathsf{cm}(\hat{q}_1), \ldots, \mathsf{cm}(\hat{q}_{n-1})$

Prover:

• 直接用 Zeromorph 论文 Appendix A.2 的算法能计算出 $q_i$ 在 Hypercube 上的值，即可以得到 $Q_i$ 的系数，根据论文的结论，整个算法复杂度为 $(2^{n+1} - 3) ~ \mathbb{F}_{\mathsf{add}}$ 以及 $(2^{n} - 2) ~ \mathbb{F}_{\mathsf{mul}}$ 。这里不计入加法的复杂度，因此计算出 $Q_i=[[q_i]]_i, \quad 0 \leq i < n$ 的复杂度为 $(2^{n} - 2) ~ \mathbb{F}_{\mathsf{mul}}$ 。
• 计算 $\mathsf{cm}(q_0), \mathsf{cm}(q_1), \ldots, \mathsf{cm}(q_{n-1})$ ，这里涉及 MSM 算法，对于每一个 $\mathsf{cm}(q_{k})$ ，多项式 $q_{k}$ 的系数有 $2^k$ 个，复杂度为 $\mathsf{msm}(2^k,\mathbb{G}_1)$ ，因此这一步的总复杂度为

$$> \sum_{k=0}^{n-1} \mathsf{msm}(2^k,\mathbb{G}_1) >$$

(31)

因此这一轮的总复杂度为

$$> (2^{n} - 2) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k=0}^{n-1} \mathsf{msm}(2^k,\mathbb{G}_1) >$$

(32)

• 计算 $Q_i$ 的算法及代码细节

Round 2¶

1. Verifier 发送随机数 $\beta\in \mathbb{F}_p^*$ 用来聚合多个 Degree Bound 证明

2. Prover 构造 $\bar{q}(X)$ 作为聚合商多项式 $\{\hat{q}_i(X)\}$ 的多项式，并发送其承诺 $\mathsf{cm}(\bar{q})$

Prover：

• 可以先由随机数 $\beta$ 计算得到 $\beta^2, \ldots, \beta^{n - 1}$ ，复杂度为 $(n - 2) ~ \mathbb{F}_{\mathsf{mul}}$
• 计算 $\beta^i \cdot X^{2^n-2^i}\hat{q}_i(X)$ ，为多项式的乘法，复杂度为 $\mathsf{polymul}(2^n - 2^i, 2^i - 1) + \mathsf{polymul}(0, 2^n - 1)$ ，因此求和相加的复杂度为
  $$\begin{aligned} & \sum_{i = 0}^{n - 1} \big( \mathsf{polymul}(2^n - 2^i, 2^i - 1) + \mathsf{polymul}(0, 2^n - 1) \big) \\ = & n ~ \mathsf{polymul}(0, 2^n - 1) + \sum_{i = 0}^{n - 1} \mathsf{polymul}(2^n - 2^i, 2^i - 1) \end{aligned}$$

  (34)
• 计算 $\mathsf{cm}(\bar{q})$ ，复杂度为 $\mathsf{msm}(2^n , \mathbb{G}_1)$

这一轮的总复杂度为

$$> (n - 2) ~ \mathbb{F}_{\mathsf{mul}} + n ~ \mathsf{polymul}(0, 2^n - 1) + \sum_{i = 0}^{n - 1} \mathsf{polymul}(2^n - 2^i, 2^i - 1) + \mathsf{msm}(2^n , \mathbb{G}_1) >$$

(35)

Round 3¶

1. Verifier 发送随机数 $\zeta\in \mathbb{F}_p^*$ ，用来挑战多项式在 $X=\zeta$ 处的取值

2. Prover 计算 $h_0(X)$ 与 $h_1(X)$

• 计算 $r(X)$ ，

• 计算 $s(X)$ ，

• 计算商多项式 $h_0(X)$ 与 $h_1(X)$

Prover：

• 先根据随机数 $\zeta$ 计算出 $\zeta$ 的幂次，即 $\zeta^2, \ldots, \zeta^{2^{n}}$ ，涉及 $n$ 次有限域的乘法，复杂度为 $n ~ \mathbb{F}_{\mathsf{mul}}$ 。

• 计算 $r(X)$ 复杂度与上面朴素协议的分析一致，复杂度为

  $$> (2n + 1) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) >$$

  (39)

• 计算 $s(X)$

  • $\beta^k \cdot \zeta^{2^n-2^k}$ ，复杂度为 $\mathbb{F}_{\mathsf{mul}}$
  • $\beta^k \cdot \zeta^{2^n-2^k}\cdot \hat{q}_k(X)$ ，复杂度为 $\mathsf{polymul}(0, 2^k - 1)$

  因此 计算 $s(X) = \bar{q}(X) - \sum_{k=0}^{n-1} \beta^k \cdot \zeta^{2^n-2^k}\cdot \hat{q}_k(X)$ 复杂度为

  $$> n ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) >$$

  (40)

• 计算商多项式 $h_0(X)$ 与 $h_1(X)$ ，这里可以用线性除法进行计算，由于 $\deg(r) = 2^n - 1$ ，$\deg(s(X)) = 2^n - 1$ ，因此这里的复杂度为

  $$> (2^{n + 1} - 2) ~ \mathbb{F}_{\mathsf{mul}} >$$

  (41)

因此这一轮的总复杂度为

$$> \begin{aligned} > & n ~ \mathbb{F}_{\mathsf{mul}} + (2n + 1) ~ \mathbb{F}_{\mathsf{mul}} \\ > & + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) + n ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) + (2^{n + 1} - 2) ~ \mathbb{F}_{\mathsf{mul}} \\ > = & (4n + 2^{n + 1} - 1) ~ \mathbb{F}_{\mathsf{mul}} + 2 \sum_{k = 0}^{n - 1} \mathsf{polymul}(0, 2^k - 1) > \end{aligned} >$$

(42)

Round 4¶

1. Verifier 发送随机数 $\alpha\in \mathbb{F}_p^*$ ，用来聚合 $h_0(X)$ 与 $h_1(X)$

2. Prover 计算 $h(X)$ 并发送其承诺 $\mathsf{cm}(h)$

Prover:

• 计算 $h_0(X) + \alpha\cdot h_1(X)$ ，复杂度为 $\mathsf{polymul}(0, 2^n - 2)$ 。
• $(h_0(X) + \alpha\cdot h_1(X))\cdot X^{D_{max}-2^n+1}$ 复杂度为 $\mathsf{polymul}(2^n - 2, D_{max}-2^n+1)$ 。
• 计算 $\mathsf{cm}(h)$ 复杂度为 $\mathsf{msm}(D_{max} + 1, {\mathbb{G}_1})$

这一轮的总复杂度为

$$> \mathsf{polymul}(0, 2^n - 2) + \mathsf{polymul}(2^n - 2, D_{max}-2^n+1) + \mathsf{msm}(D_{max} + 1, {\mathbb{G}_1}) >$$

(44)

Verification¶

Verifier

• 构造 $\mathsf{cm}(r)$ 的承诺：

• 构造 $\mathsf{cm}(s)$ 的承诺：

• 验证 $r(\zeta) = 0$ 与 $s(\zeta) = 0$

证明大小：

在 Verifier 进行验证前，其收到的证明为

$$> \pi = (\mathsf{cm}(\hat{q}_0), \mathsf{cm}(\hat{q}_1), \ldots, \mathsf{cm}(\hat{q}_{n-1}), \mathsf{cm}(\bar{q}), \mathsf{cm}(h)) >$$

(48)

因此证明的大小为 $(n + 2) ~ \mathbb{G}_1$ 。

Verifier:

• 构造 $\mathsf{cm}(r)$ 的承诺

  • 计算 $\zeta^2, \zeta^4, \ldots, \zeta^{2^n}$ ，复杂度为 $n ~ \mathbb{F}_{\mathsf{mul}}$ 。

  • 计算 $\mathsf{cm}(v\cdot \Phi_{n}(\zeta))$ 复杂度： $\mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1}$

  • 计算 $\sum_{i=0}^{n-1} \Big(\zeta^{2^i}\cdot \Phi_{n-i-1}(\zeta^{2^{i+1}}) - u_i\cdot \Phi_{n-i}(\zeta^{2^{i}})\Big)\cdot \mathsf{cm}(\hat{q}_i)$

    • $\Big(\zeta^{2^i}\cdot \Phi_{n-i-1}(\zeta^{2^{i+1}}) - u_i\cdot \Phi_{n-i}(\zeta^{2^{i}})\Big)\cdot \mathsf{cm}(\hat{q}_i)$ 复杂度为：$2 ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1}$

    得到的 $n$ 个 $\mathbb{G}_1$ 上的点还要相加，因此这步计算的总复杂为 $2n ~ \mathbb{F}_{\mathsf{mul}} + n ~\mathsf{EccMul}^{\mathbb{G}_1} + (n - 1) ~\mathsf{EccAdd}^{\mathbb{G}_1}$

  • 将上边得到的三个 $\mathbb{G}_1$ 上的点相加，复杂度为 $2~\mathsf{EccAdd}^{\mathbb{G}_1}$ 。

  因此计算出 $\mathsf{cm}(r)$ 的复杂度为

  $$> \begin{aligned} > & n ~ \mathbb{F}_{\mathsf{mul}} + \mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1} + 2n ~ \mathbb{F}_{\mathsf{mul}} + n ~\mathsf{EccMul}^{\mathbb{G}_1} + (n - 1) ~\mathsf{EccAdd}^{\mathbb{G}_1} + 2~\mathsf{EccAdd}^{\mathbb{G}_1} \\ > = & (3n + 1) ~ \mathbb{F}_{\mathsf{mul}} + (n + 1) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (n + 1) ~ \mathsf{EccAdd}^{\mathbb{G}_1} > \end{aligned} >$$

  (49)

• 计算 $\mathsf{cm}(s)$ 的承诺

  • 先计算出 $\beta^2, \ldots, \beta^{n - 1}$ ，复杂度为 $(n - 2) ~ \mathbb{F}_{\mathsf{mul}}$

  • 计算 $\beta^i \cdot \zeta^{2^n-2^i}\cdot \mathsf{cm}(\hat{q}_i)$ 复杂度为： $\mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1}$， 因此求和计算的复杂度不仅有每一项的计算，同时计算完椭圆曲线上的点之后，还要将这 $n$ 个点相加，因此计算 $\sum_{i=0}^{n-1} \beta^i \cdot \zeta^{2^n-2^i}\cdot \mathsf{cm}(\hat{q}_i)$ 的总复杂度为

    $$> n ~ \mathbb{F}_{\mathsf{mul}} + n ~ \mathsf{EccMul}^{\mathbb{G}_1} + (n - 1) ~ \mathsf{EccAdd}^{\mathbb{G}_1} >$$

    (50)

  • 计算 $\mathsf{cm}(\bar{q}) - \sum_{i=0}^{n-1} \beta^i \cdot \zeta^{2^n-2^i}\cdot \mathsf{cm}(\hat{q}_i)$ 的复杂度为两个椭圆曲线 $\mathbb{G}_1$ 上的点相加，为 $\mathsf{EccAdd}^{\mathbb{G}_1}$ 。

  因此计算出 $\mathsf{cm}(s)$ 的复杂度为

  $$> (2n - 2) ~ \mathbb{F}_{\mathsf{mul}} + n ~ \mathsf{EccMul}^{\mathbb{G}_1} + n ~ \mathsf{EccAdd}^{\mathbb{G}_1} >$$

  (51)

• 验证 $r(\zeta) = 0$ 与 $s(\zeta) = 0$

  • 计算 $\mathsf{cm}(r) + \alpha\cdot \mathsf{cm}(s)$ 和 $[\tau]_2 - \zeta\cdot [1]_2$ 的复杂度为 $\mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} + \mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2}$
  • 计算 $e(\mathsf{cm}(r) + \alpha\cdot \mathsf{cm}(s), \ [\tau^{D-2^n+2}]_2)$ 与 $e(\mathsf{cm}(h),\ [\tau]_2 - \zeta\cdot [1]_2)$ ，涉及两个椭圆曲线上的配对操作，记为 $2~P$ 。

  因此这一步的总复杂度为

  $$> \mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} + \mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2} + 2~P >$$

  (52)

因此在 Verification 阶段的总复杂度为

$$> \begin{aligned} > & (3n + 1) ~ \mathbb{F}_{\mathsf{mul}} + (n + 1) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (n + 1) ~ \mathsf{EccAdd}^{\mathbb{G}_1} \\ > & + (2n - 2) ~ \mathbb{F}_{\mathsf{mul}} + n ~ \mathsf{EccMul}^{\mathbb{G}_1} + n ~ \mathsf{EccAdd}^{\mathbb{G}_1} \\ > & + \mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} + \mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2} + 2~P \\ > = & (5n - 1) ~ \mathbb{F}_{\mathsf{mul}} + (2n + 2) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (2n + 2) ~ \mathsf{EccAdd}^{\mathbb{G}_1} + \mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2} + 2~P > \end{aligned} >$$

(53)