在可信设置中评估和二次算术程序

RareSkills
发布于 2023-08-30 15:53
阅读 14

本文详细介绍了如何在可信设置的基础上评估二次算术程序（QAP），并解释了如何在不泄露证据的情况下证明QAP的满足性，使用恒定大小的证明。同时还涉及了R1CS、椭圆曲线配对等技术的详细实现。

## 在可信设置下评估二次算术程序

在可信设置下评估 [二次算术程序 (QAP)](https://learnblockchain.cn/article/11314) 使得 prover 可以证明 QAP 被满足，而不泄露见证，同时使用固定大小的证明。

具体来说，QAP 多项式在一个未知点 $\tau$ 处被评估。QAP 方程

$$\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)$$

如果向量 $\mathbf{a}$ 满足该方程，则方程将是平衡的，否则以压倒性概率是不平衡的。

此处展示的方案不是安全的 ZK 证明，但它是展示 Groth16 如何工作的一个重要步骤。

### 具体示例

为了让这个概念不那么抽象，假设 [秩1约束系统 (R1CS)](https://learnblockchain.cn/article/11313) 的矩阵 $\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 具有 3 行和 4 列。

$$\mathbf{L}\mathbf{a} \circ \mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}$$

由于我们有 3 行，这意味着我们的插值多项式的度数将是 2。由于我们有 4 列，每个矩阵将生成 4 个多项式（总共 12 个多项式）。

我们的 QAP 将是

$$\sum_{i=1}^4a_iu_i(x)\sum_{i=1}^4a_iv_i(x) = \sum_{i=1}^4a_iw_i(x) + h(x)t(x)$$

### 记号和初步知识

我们将群 $\mathbb{G}_1$ 和 $\mathbb{G}_2$ 中的生成椭圆曲线点称为 $G_1$ 和 $G_2$。群 $\mathbb{G}_1$ 中的元素表示为 $[X]_1$。群 $\mathbb{G}_2$ 中的元素表示为 $[X]_2$。如果下标可能和列表中的索引造成歧义，我们将说 $X \in \mathbb{G}_1$ 或 $X \in \mathbb{G}_2$。两个点之间的 [椭圆曲线配对](https://learnblockchain.cn/article/11321) 表示为 $[X]_1 \bullet [Y]_2$。

设 $\mathbf{L}_{(*,j)}$ 是 $\mathbf{L}$ 的第 $j$ 列。在我们的示例中，行将是 $(1,2,3)$ 和列将是 $(1,2,3,4)$。设 $\mathcal{L}(\mathbf{L}_{(*,j)})$ 是对 $\mathbf{L}$ 的第 $j$ 列运行拉格朗日插值得到的多项式，使用 $x$ 值 $(1,2,3)$ 和 $y$ 值为第 $j$ 列的值。

由于我们有 4 列，我们从 $\mathbf{L}$ 中得到四个多项式

$$ \begin{align*} u_1(x) = \mathcal{L}(\mathbf{L}_{(*,1)}) =u_{12}x^2 + u_{11}x+u_{10}\\\ u_2(x) = \mathcal{L}(\mathbf{L}_{(*,2)}) =u_{22}x^2 + u_{21}x+u_{20}\\\ u_3(x) = \mathcal{L}(\mathbf{L}_{(*,3)}) =u_{32}x^2 + u_{31}x+u_{30}\\\ u_4(x) = \mathcal{L}(\mathbf{L}_{(*,4)}) =u_{42}x^2 + u_{41}x+u_{40}\\\ \end{align*} $$

从 $\mathbf{R}$ 中得到四个多项式

$$ \begin{align*} v_1(x) = \mathcal{L}(\mathbf{R}_{(*,1)}) =v_{12}x^2 + v_{11}x+v_{10}\\\ v_2(x) = \mathcal{L}(\mathbf{R}_{(*,2)}) =v_{22}x^2 + v_{21}x+v_{20}\\\ v_3(x) = \mathcal{L}(\mathbf{R}_{(*,3)}) =v_{32}x^2 + v_{31}x+v_{30}\\\ v_4(x) = \mathcal{L}(\mathbf{R}_{(*,4)}) =v_{42}x^2 + v_{41}x+v_{40}\\\ \end{align*} $$

和从 $\mathbf{O}$ 中得到的四个多项式

$$ \begin{align*} v_1(x) = \mathcal{L}(\mathbf{O}_{(*,1)}) =v_{12}x^2 + v_{11}x+v_{10}\\\ v_2(x) = \mathcal{L}(\mathbf{O}_{(*,2)}) =v_{22}x^2 + v_{21}x+v_{20}\\\ v_3(x) = \mathcal{L}(\mathbf{O}_{(*,3)}) =v_{32}x^2 + v_{31}x+v_{30}\\\ v_4(x) = \mathcal{L}(\mathbf{O}_{(*,4)}) =v_{42}x^2 + v_{41}x+v_{40}\\\ \end{align*} $$

多项式 $p_{ij}$ 意味着第 $i$ 个多项式和第 $j$ 个系数（次方）。例如，$j=2$ 表示与 $x^2$ 相关的系数。

我们的示例 QAP 是

$$ \sum_{i=1}^4a_iu_i(x)\sum_{i=1}^4a_iv_i(x) = \sum_{i=1}^4a_iw_i(x) + h(x)t(x) $$ 其中 $t(x) = (x – 1)(x – 2)(x – 3)$，而 $h(x)$ 是

$$ h(x)=\frac{\sum_{i=1}^4a_iu_i(x)\sum_{i=1}^4a_iv_i(x) – \sum_{i=1}^4a_iw_i(x)}{t(x)} $$

#### QAP 中相对于 R1CS 大小的多项式的度数

关于一般情况下多项式的度数，有以下几点观察：

* $u(x)$ 和 $v(x)$ 的度数可能高达 $n – 1$，因为它们插值 $n$ 个点，其中 $n$ 是 R1CS 中的行数。
  * 如果多项式的总和 $\sum_{i=0}^m a_iw_i(x)$ 得到零多项式，则 $w(x)$ 的度数可能低至 0，即系数相互抵消。
  * $t(x)$ 按定义是度数 $n$。
  * 乘法多项式会把它们的度数相加，而除法多项式则会把它们的度数相减。

因此，$h(x)$ 的度数最多为 $n – 2$，因为

$$\underbrace{n – 1}_{ \deg{u(x)}} + \underbrace{n – 1}_{\deg{v(x)}} – \underbrace{n}_{\deg{t(x)}} = n – 2$$

### 扩展项

如果我们展开之前示例中的和，我们得到以下结果

$$ \begin{align*} \sum_{i=1}^4 a_iu_i(x) &= a_1(u_{12}x^2 + u_{11}x+u_{10}) + a_2(u_{22}x^2 + u_{21}x+u_{20}) + a_3(u_{32}x^2 + u_{31}x+u_{30}) + a_4(u_{42}x^2 + u_{41}x+u_{40})\\\ &= (a_1u_{12}+a_2u_{22}+a_3u_{32}+a_4u_{42})x^2 + (a_1u_{11}+a_2u_{21}+a_3u_{31}+a_4u_{41})x + (a_1u_{10}+a_2u_{20}+a_3u_{30}+a_4u_{40})\\\ &=u_{2a}x^2+u_{1a}x+u_{0a}\\\ \sum_{i=1}^4 a_iv_i(x) &= a_1(v_{12}x^2 + v_{11}x+v_{10}) + a_2(v_{22}x^2 + v_{21}x+v_{20}) + a_3(v_{32}x^2 + v_{31}x+v_{30}) + a_4(v_{42}x^2 + v_{41}x+v_{40})\\\ &= (a_1v_{12}+a_2v_{22}+a_3v_{32}+a_4v_{42})x^2 + (a_1v_{11}+a_2v_{21}+a_3v_{31}+a_4v_{41})x + (a_1v_{10}+a_2v_{20}+a_3v_{30}+a_4v_{40})\\\ &=v_{2a}x^2+v_{1a}x+v_{0a}\\\ \sum_{i=1}^4 a_iw_i(x) &= a_1(w_{12}x^2 + w_{11}x+w_{10}) + a_2(w_{22}x^2 + w_{21}x+w_{20}) + a_3(w_{32}x^2 + w_{31}x+w_{30}) + a_4(w_{42}x^2 + w_{41}x+w_{40})\\\ &= (a_1w_{12}+a_2w_{22}+a_3w_{32}+a_4w_{42})x^2 + (a_1w_{11}+a_2w_{21}+a_3w_{31}+a_4w_{41})x + (a_1w_{10}+a_2w_{20}+a_3w_{30}+a_4w_{40})\\\ &=w_{2a}x^2+w_{1a}x+w_{0a}\\\ \end{align*} $$

在每个情况下，由于我们在添加 4 个度数为 2 的多项式，所以我们得到的是一个度数为 2 的多项式。

通常表达式 $\sum_{i=1}^m a_ip_i(x)$ 产生的多项式最多与 $p(x)$ 具有相同的幂（如果，例如，$(a_1w_{12}+a_2w_{22}+a_3w_{32}+a_4w_{42})x^2$ 相加为 0，则可能更小）。为方便起见，我们引入了系数 $p_{ia}$，其中 $i$ 是系数的幂，而 $_a$ 表示我们将多项式与见证 $\mathbf{a}$ 结合。

经简化后，得到以下多项式：

$$ \begin{align*} \sum_{i=1}^4 a_iu_i(x) &= u_{2a}x^2+u_{1a}x+u_{0a}\\\ \sum_{i=1}^4 a_iv_i(x) &= v_{2a}x^2+v_{1a}x+v_{0a}\\\ \sum_{i=1}^4 a_iw_i(x) &= w_{2a}x^2+w_{1a}x+w_{0a}\\\ \end{align*} $$

### 将可信设置与 QAP 结合

我们现在可以应用可信设置中的结构化参考字符串来评估多项式。

即给定结构化参考字符串

$$[\Omega_2, \Omega_1, G_1], [\Theta_2, \Theta_1, G_2], \space\Omega_i \in \mathbb{G}_1, \space\Theta_i \in \mathbb{G}_2$$

该字符串是在可信设置中计算得到的

$$ \begin{align*} [\Omega_2, \Omega_1, G_1] &= [\tau^2G_1, \tau G_1, G_1], \space\Omega_i \in \mathbb{G}_1\\\ [\Theta_2, \Theta_1, G_2] &= [\tau^2G_2, \tau G_2, G_2], \space\Theta_i \in \mathbb{G}_2 \end{align*} $$

我们可以计算

$$ \begin{align*} [A]_1 &=\sum_{i=1}^4 a_iu_i(\tau) = \langle[u_{2a}, u_{1a}, u_{0a}],[\Omega_2, \Omega_1, G_1]\rangle\\\ [B]_2 &=\sum_{i=1}^4 a_iv_i(\tau) = \langle[v_{2a}, v_{1a}, v_{0a}],[\Theta_2, \Theta_1, G_2]\rangle\\\ [C]_1 &=\sum_{i=1}^4 a_iw_i(\tau) = \langle[v_{2a}, v_{1a}, v_{0a}],[\Omega_2, \Omega_1, G_1]\rangle \\\ \end{align*} $$

这里，$u_i(\tau), v_i(\tau), w_i(\tau)$ 意思是多项式是使用由可信设置中生成的 $\tau$ 的结构化参考字符串进行评估的，并不意味着“将 $\tau$ 插入并评估多项式”。由于 $\tau$ 在可信设置后被销毁，因此值 $\tau$ 是未知的。

我们已经使用结构化参考字符串计算了大部分 QAP，但还没有计算 $h(x)t(x)$：

$$ \underbrace{\sum_{i=1}^m a_iu_i(x)}_{[A]_1} \underbrace{\sum_{i=1}^m a_iv_i(x)}_{[B]_2} = \underbrace{\sum_{i=1}^m a_iw_i(x)}_{[C]_1} + \underbrace{h(x)t(x)}_{??} $$

### 计算 $h(x)t(x)$

回想一下，$t(x)$ 的度数是 3（通常为 $n$），而 $h(x)$ 的度数是 1（通常为 $n – 2$）。如果我们将它们相乘，我们可以得到高达度数为 3 的多项式，这比 $\tau$ 的权值仪式提供的要多。相反，$\tau$ 的权值仪式必须调整以提供 $h(x)t(x)$ 的结构化参考字符串。

进行可信设置的人知道 $t(x)$，它只是一系列 $(x – 1)(x – 2)…(x – n)$。然而，$h(x)$ 是由 prover 计算出来的多项式，并根据 $\mathbf{a}$ 的值变化，因此在进行可信设置时无法知道。

请注意，我们无法单独评估 $h(\tau)$ 和 $t(\tau)$（使用结构化参考字符串），然后将它们配对。这将不会导致我们所需的 $\mathbb{G}_1$ 元素。

#### 多项式乘积的 SRS

观察以下计算结果都得到了相同的值：

* 在 $u$ 处评估的多项式 $h(x)t(x)$，或 $(h(x)t(x))(u)$
  * $h(u)$ 乘以 $t(u)$，或 $h(u)t(u)$（$h$ 在 $u$ 处评估，$t$ 在 $u$ 处评估）
  * $h(x)$ 乘以评估 $t(u)$，然后在 $u$ 处评估，即 $(h(x)t(u))(u)$

我们将使用第三种方法来计算 $h(\tau)t(\tau)$。假设在不失一般性的情况下，$h(x)$ 为 $3x^2 + 6x + 2$，而 $t(u) = 4$。计算如下

$$h(x)t(u) = (3x^2 + 6x + 2) \cdot 4 = 12x^2 + 24x + 8$$

如果我们将 $u$ 插入 $12x^2 + 24x + 8$，这将是 $h(u)t(u)$。

然而，在 $\tau$ 处评估该多项式将需要 prover 知道 $\tau$。这里的关键见解是，上述计算可以结构化为：

$$h(u)t(u) = \langle[3, 6, 2], [4u^2, 4u, 4]\rangle=12u^2+24u+8$$

如果可信设置提供 $[4u^2, 4u, 4]$，而 prover 提供 $[3, 6, 2]$，那么 prover 可以在不知道 $u$ 的情况下计算 $h(u)t(u)$，因为涉及 $u$ 的任何内容都在内积的右向量中。

#### $h(\tau)t(\tau)$ 的结构化参考字符串

为了创建 $h(\tau)t(\tau)$ 的结构化参考字符串，我们创建 $n – 1$ 个 $t(\tau)$ 评估值与 $\tau$ 的连续幂相乘。

$$[\Upsilon_{n-2}, \Upsilon_{n-3}, …, \Upsilon_1, \Upsilon_0] = [\tau^{n-2}t(\tau)G_1, \tau^{n-3}t(\tau)G_1, …, \tau t(\tau)G_1, t(\tau)G_1]$$

（稍微令人困惑的是，度数为 $k$ 的多项式有 $k+1$ 项，因此我们为度数为 $k – 2$ 的多项式生成 $k – 1$ 个评估值。注意 Upsilon 从 ${n-1}$ 开始，到 0 结束）。

这里，$n$ 是 R1CS 中的行数，我们确定 $h$ 的度数不能大于 $n – 2$。

要使用结构化参考字符串计算 $h(\tau)t(\tau)$，prover 可以执行：

$$h(\tau)t(\tau) = \langle[h_{n-2}, h_{n-3}, …, h_1, h_0], [\Upsilon_{n-2}, \Upsilon_{n-3}, …, \Upsilon_1, \Upsilon_0] \rangle$$

### 在可信设置下评估 QAP

我们现在将一切整合在一起。假设我们有一个 R1CS，矩阵具有 $n$ 行和 $m$ 列。从中我们可以应用拉格朗日插值将其转换为 QAP

$$\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)$$

所有求和项将产生度数为 $n – 1$ 的多项式（拉格朗日多项式的度数比它插值的点数少1），而 $h(x)$ 多项式的度数最多为 $n – 2$，$t(x)$ 的度数为 $n$。

可信设置生成一个随机字段元素 $\tau$ 并计算：

$$ \begin{align*} [\Omega_{n-1},\Omega_{n-2},…, \Omega_1, G_1] &= [\tau^{n-1}G_1, \tau^{n-2}G_1,\dots, \tau G_1, G_1]\\\ [\Theta_{n-1}, \Theta_{n-2}, …, \Theta_1, G_2] &= [\tau^{n-1}G_2, \tau^{n-2}G_2,\dots, \tau G_2, G_2]\\\ [\Upsilon_{n-2}, \Upsilon_{n-3}, …, \Upsilon_1, \Upsilon_0] &= [\tau^{n-2}t(\tau)G_1, \tau^{n-3}t(\tau)G_1, …, \tau t(\tau)G_1, t(\tau)G_1] \end{align*} $$

注意，结构化参考字符串需要有足够的项以适应 QAP 中的多项式。

然后，可信设置销毁 $\tau$ 并发布结构化参考字符串：

$$([\Omega_2, \Omega_1, G_1], [\Theta_2, \Theta_1, G_2], [\Upsilon_{n-2}, \Upsilon_{n-3}, …, \Upsilon_1, \Upsilon_0])$$

prover 按如下方式评估 QAP 的组件：

$$\underbrace{\sum_{i=1}^m a_iu_i(x)}_{A}\underbrace{\sum_{i=1}^m a_iv_i(x)}_B = \underbrace{\sum_{i=1}^m a_iw_i(x) + h(x)t(x)}_{C}$$

$$ \begin{align*} [A]_1 &=\sum_{i=1}^m a_iu_i(\tau) = \langle[u_{{n-1}a}, u_{{n-2}a}, \dots, u_{1a}, u_{0a}],[\Omega_{n-1}, \Omega_{n-2}, \dots, \Omega_1, G_1]\rangle\\\ [B]_2 &=\sum_{i=1}^m a_iv_i(\tau) = \langle[v_{{n-1}a}, v_{{n-2}a}, \dots, v_{1a}, v_{0a}],[\Theta_{n-1}, \Theta_{n-2}, \dots, \Theta_1, G_2]\rangle\\\ [C]_1 &=\sum_{i=0}^m a_iw_i(\tau) + h(\tau)t(\tau) = \langle[w_{{n-1}a}, w_{{n-2}a}, \dots, w_{1a}, w_{0a}],[\Omega_{n-1}, \Omega_{n-2}, \dots, \Omega_1, G_1]\rangle \\\ &+\langle[h_{n-2}, h_{n-3}, \dots, h_1, h_0], [\Upsilon_{n-2}, \Upsilon_{n-3}, \dots, \Upsilon_1, \Upsilon_0] \rangle\\\ \end{align*} $$

prover 发布 $([A]_1, [B]_2, [C]_1)$，并且验证者可以检查

$$[A]_1 \bullet [B]_2 \stackrel{?}= [C]_1 \bullet G_2$$

如果见证 $\mathbf{a}$ 满足 QAP，则上述方程将是平衡的。但是方程的平衡并不确保 prover 知道一个满足的 $\mathbf{a}$，因为 prover 可以发布任意的椭圆曲线点，而验证者并不知道它们是否实际来自 QAP。

### 证明非常小

观察到证明仅由三个椭圆曲线点组成。如果一个 $\mathbb{G}_1$ 元素为 64 字节大，而一个 $\mathbb{G}_2$ 元素为 128 字节大，则证明仅为 256 字节。这一点是真正的 _无论_ R1CS 的大小如何！

R1CS 越大，prover 要做的工作越多，但验证者的工作保持不变。

此问题的解决方案在下一章关于 [Groth16 协议](https://learnblockchain.cn/article/11324) 中描述。

在 Groth16 中，证明仍然保持为固定大小，可以在 [struct](https://github.com/tornadocash/tornado-core/blob/master/contracts/Verifier.sol#L167-L171) 看到名为 `Proof`。

_原文发布于 2023 年 8 月 28 日_

>- 原文链接： [rareskills.io/post/ellip...](https://www.rareskills.io/post/elliptic-curve-qap)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

在可信设置下评估二次算术程序

在可信设置下评估二次算术程序 (QAP) 使得 prover 可以证明 QAP 被满足，而不泄露见证，同时使用固定大小的证明。

具体来说，QAP 多项式在一个未知点 $\tau$ 处被评估。QAP 方程

$$\sum_{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(x) = \sum{i=1}^m a_iw_i(x) + h(x)t(x)$$

如果向量 $\mathbf{a}$ 满足该方程，则方程将是平衡的，否则以压倒性概率是不平衡的。

此处展示的方案不是安全的 ZK 证明，但它是展示 Groth16 如何工作的一个重要步骤。

具体示例

为了让这个概念不那么抽象，假设秩1约束系统 (R1CS) 的矩阵 $\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 具有 3 行和 4 列。

$$\mathbf{L}\mathbf{a} \circ \mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}$$

由于我们有 3 行，这意味着我们的插值多项式的度数将是 2。由于我们有 4 列，每个矩阵将生成 4 个多项式（总共 12 个多项式）。

我们的 QAP 将是

$$\sum_{i=1}^4a_iui(x)\sum{i=1}^4a_ivi(x) = \sum{i=1}^4a_iw_i(x) + h(x)t(x)$$

记号和初步知识

设 $\mathbf{L}{(*,j)}$ 是 $\mathbf{L}$ 的第 $j$ 列。在我们的示例中，行将是 $(1,2,3)$ 和列将是 $(1,2,3,4)$。设 $\mathcal{L}(\mathbf{L}{(*,j)})$ 是对 $\mathbf{L}$ 的第 $j$ 列运行拉格朗日插值得到的多项式，使用 $x$ 值 $(1,2,3)$ 和 $y$ 值为第 $j$ 列的值。

由于我们有 4 列，我们从 $\mathbf{L}$ 中得到四个多项式

$$ \begin{align} u1(x) = \mathcal{L}(\mathbf{L}{(,1)}) =u{12}x^2 + u{11}x+u_{10}\\ u2(x) = \mathcal{L}(\mathbf{L}{(,2)}) =u{22}x^2 + u{21}x+u_{20}\\ u3(x) = \mathcal{L}(\mathbf{L}{(,3)}) =u{32}x^2 + u{31}x+u_{30}\\ u4(x) = \mathcal{L}(\mathbf{L}{(,4)}) =u{42}x^2 + u{41}x+u_{40}\\ \end{align} $$

从 $\mathbf{R}$ 中得到四个多项式

$$ \begin{align} v1(x) = \mathcal{L}(\mathbf{R}{(,1)}) =v{12}x^2 + v{11}x+v_{10}\\ v2(x) = \mathcal{L}(\mathbf{R}{(,2)}) =v{22}x^2 + v{21}x+v_{20}\\ v3(x) = \mathcal{L}(\mathbf{R}{(,3)}) =v{32}x^2 + v{31}x+v_{30}\\ v4(x) = \mathcal{L}(\mathbf{R}{(,4)}) =v{42}x^2 + v{41}x+v_{40}\\ \end{align} $$

和从 $\mathbf{O}$ 中得到的四个多项式

$$ \begin{align} v1(x) = \mathcal{L}(\mathbf{O}{(,1)}) =v{12}x^2 + v{11}x+v_{10}\\ v2(x) = \mathcal{L}(\mathbf{O}{(,2)}) =v{22}x^2 + v{21}x+v_{20}\\ v3(x) = \mathcal{L}(\mathbf{O}{(,3)}) =v{32}x^2 + v{31}x+v_{30}\\ v4(x) = \mathcal{L}(\mathbf{O}{(,4)}) =v{42}x^2 + v{41}x+v_{40}\\ \end{align} $$

多项式 $p_{ij}$ 意味着第 $i$ 个多项式和第 $j$ 个系数（次方）。例如，$j=2$ 表示与 $x^2$ 相关的系数。

我们的示例 QAP 是

$$ \sum_{i=1}^4a_iui(x)\sum{i=1}^4a_ivi(x) = \sum{i=1}^4a_iw_i(x) + h(x)t(x) $$ 其中 $t(x) = (x – 1)(x – 2)(x – 3)$，而 $h(x)$ 是

$$ h(x)=\frac{\sum_{i=1}^4a_iui(x)\sum{i=1}^4a_ivi(x) – \sum{i=1}^4a_iw_i(x)}{t(x)} $$

QAP 中相对于 R1CS 大小的多项式的度数

关于一般情况下多项式的度数，有以下几点观察：

$u(x)$ 和 $v(x)$ 的度数可能高达 $n – 1$，因为它们插值 $n$ 个点，其中 $n$ 是 R1CS 中的行数。
如果多项式的总和 $\sum_{i=0}^m a_iw_i(x)$ 得到零多项式，则 $w(x)$ 的度数可能低至 0，即系数相互抵消。
$t(x)$ 按定义是度数 $n$。
乘法多项式会把它们的度数相加，而除法多项式则会把它们的度数相减。

因此，$h(x)$ 的度数最多为 $n – 2$，因为

$$\underbrace{n – 1}{ \deg{u(x)}} + \underbrace{n – 1}{\deg{v(x)}} – \underbrace{n}_{\deg{t(x)}} = n – 2$$

扩展项

如果我们展开之前示例中的和，我们得到以下结果

$$ \begin{align} \sum_{i=1}^4 a_iu_i(x) &= a1(u{12}x^2 + u{11}x+u{10}) + a2(u{22}x^2 + u{21}x+u{20}) + a3(u{32}x^2 + u{31}x+u{30}) + a4(u{42}x^2 + u{41}x+u{40})\\ &= (a1u{12}+a2u{22}+a3u{32}+a4u{42})x^2 + (a1u{11}+a2u{21}+a3u{31}+a4u{41})x + (a1u{10}+a2u{20}+a3u{30}+a4u{40})\\ &=u{2a}x^2+u{1a}x+u{0a}\\ \sum{i=1}^4 a_iv_i(x) &= a1(v{12}x^2 + v{11}x+v{10}) + a2(v{22}x^2 + v{21}x+v{20}) + a3(v{32}x^2 + v{31}x+v{30}) + a4(v{42}x^2 + v{41}x+v{40})\\ &= (a1v{12}+a2v{22}+a3v{32}+a4v{42})x^2 + (a1v{11}+a2v{21}+a3v{31}+a4v{41})x + (a1v{10}+a2v{20}+a3v{30}+a4v{40})\\ &=v{2a}x^2+v{1a}x+v{0a}\\ \sum{i=1}^4 a_iw_i(x) &= a1(w{12}x^2 + w{11}x+w{10}) + a2(w{22}x^2 + w{21}x+w{20}) + a3(w{32}x^2 + w{31}x+w{30}) + a4(w{42}x^2 + w{41}x+w{40})\\ &= (a1w{12}+a2w{22}+a3w{32}+a4w{42})x^2 + (a1w{11}+a2w{21}+a3w{31}+a4w{41})x + (a1w{10}+a2w{20}+a3w{30}+a4w{40})\\ &=w{2a}x^2+w{1a}x+w_{0a}\\ \end{align} $$

在每个情况下，由于我们在添加 4 个度数为 2 的多项式，所以我们得到的是一个度数为 2 的多项式。

通常表达式 $\sum_{i=1}^m a_ip_i(x)$ 产生的多项式最多与 $p(x)$ 具有相同的幂（如果，例如，$(a1w{12}+a2w{22}+a3w{32}+a4w{42})x^2$ 相加为 0，则可能更小）。为方便起见，我们引入了系数 $p_{ia}$，其中 $i$ 是系数的幂，而 $_a$ 表示我们将多项式与见证 $\mathbf{a}$ 结合。

经简化后，得到以下多项式：

$$ \begin{align} \sum_{i=1}^4 a_iui(x) &= u{2a}x^2+u{1a}x+u{0a}\\ \sum_{i=1}^4 a_ivi(x) &= v{2a}x^2+v{1a}x+v{0a}\\ \sum_{i=1}^4 a_iwi(x) &= w{2a}x^2+w{1a}x+w{0a}\\ \end{align} $$

将可信设置与 QAP 结合

我们现在可以应用可信设置中的结构化参考字符串来评估多项式。

即给定结构化参考字符串

$$[\Omega_2, \Omega_1, G_1], [\Theta_2, \Theta_1, G_2], \space\Omega_i \in \mathbb{G}_1, \space\Theta_i \in \mathbb{G}_2$$

该字符串是在可信设置中计算得到的

$$ \begin{align} [\Omega_2, \Omega_1, G_1] &= [\tau^2G_1, \tau G_1, G_1], \space\Omega_i \in \mathbb{G}_1\\ [\Theta_2, \Theta_1, G_2] &= [\tau^2G_2, \tau G_2, G_2], \space\Theta_i \in \mathbb{G}_2 \end{align} $$

我们可以计算

$$ \begin{align} [A]1 &=\sum{i=1}^4 a_iui(\tau) = \langle[u{2a}, u{1a}, u{0a}],[\Omega_2, \Omega_1, G_1]\rangle\\ [B]2 &=\sum{i=1}^4 a_ivi(\tau) = \langle[v{2a}, v{1a}, v{0a}],[\Theta_2, \Theta_1, G_2]\rangle\\ [C]1 &=\sum{i=1}^4 a_iwi(\tau) = \langle[v{2a}, v{1a}, v{0a}],[\Omega_2, \Omega_1, G_1]\rangle \\ \end{align} $$

我们已经使用结构化参考字符串计算了大部分 QAP，但还没有计算 $h(x)t(x)$：

$$ \underbrace{\sum_{i=1}^m a_iui(x)}{[A]1} \underbrace{\sum{i=1}^m a_ivi(x)}{[B]2} = \underbrace{\sum{i=1}^m a_iwi(x)}{[C]1} + \underbrace{h(x)t(x)}{??} $$

计算 $h(x)t(x)$

请注意，我们无法单独评估 $h(\tau)$ 和 $t(\tau)$（使用结构化参考字符串），然后将它们配对。这将不会导致我们所需的 $\mathbb{G}_1$ 元素。

多项式乘积的 SRS

观察以下计算结果都得到了相同的值：

在 $u$ 处评估的多项式 $h(x)t(x)$，或 $(h(x)t(x))(u)$
$h(u)$ 乘以 $t(u)$，或 $h(u)t(u)$（$h$ 在 $u$ 处评估，$t$ 在 $u$ 处评估）
$h(x)$ 乘以评估 $t(u)$，然后在 $u$ 处评估，即 $(h(x)t(u))(u)$

我们将使用第三种方法来计算 $h(\tau)t(\tau)$。假设在不失一般性的情况下，$h(x)$ 为 $3x^2 + 6x + 2$，而 $t(u) = 4$。计算如下

$$h(x)t(u) = (3x^2 + 6x + 2) \cdot 4 = 12x^2 + 24x + 8$$

如果我们将 $u$ 插入 $12x^2 + 24x + 8$，这将是 $h(u)t(u)$。

然而，在 $\tau$ 处评估该多项式将需要 prover 知道 $\tau$。这里的关键见解是，上述计算可以结构化为：

$$h(u)t(u) = \langle[3, 6, 2], [4u^2, 4u, 4]\rangle=12u^2+24u+8$$

$h(\tau)t(\tau)$ 的结构化参考字符串

为了创建 $h(\tau)t(\tau)$ 的结构化参考字符串，我们创建 $n – 1$ 个 $t(\tau)$ 评估值与 $\tau$ 的连续幂相乘。

$$[\Upsilon{n-2}, \Upsilon{n-3}, …, \Upsilon_1, \Upsilon_0] = [\tau^{n-2}t(\tau)G_1, \tau^{n-3}t(\tau)G_1, …, \tau t(\tau)G_1, t(\tau)G_1]$$

这里，$n$ 是 R1CS 中的行数，我们确定 $h$ 的度数不能大于 $n – 2$。

要使用结构化参考字符串计算 $h(\tau)t(\tau)$，prover 可以执行：

$$h(\tau)t(\tau) = \langle[h{n-2}, h{n-3}, …, h_1, h0], [\Upsilon{n-2}, \Upsilon_{n-3}, …, \Upsilon_1, \Upsilon_0] \rangle$$

在可信设置下评估 QAP

我们现在将一切整合在一起。假设我们有一个 R1CS，矩阵具有 $n$ 行和 $m$ 列。从中我们可以应用拉格朗日插值将其转换为 QAP

$$\sum_{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(x) = \sum{i=1}^m a_iw_i(x) + h(x)t(x)$$

所有求和项将产生度数为 $n – 1$ 的多项式（拉格朗日多项式的度数比它插值的点数少1），而 $h(x)$ 多项式的度数最多为 $n – 2$，$t(x)$ 的度数为 $n$。

可信设置生成一个随机字段元素 $\tau$ 并计算：

$$ \begin{align} [\Omega{n-1},\Omega{n-2},…, \Omega_1, G_1] &= [\tau^{n-1}G_1, \tau^{n-2}G_1,\dots, \tau G_1, G1]\\ [\Theta{n-1}, \Theta_{n-2}, …, \Theta_1, G_2] &= [\tau^{n-1}G_2, \tau^{n-2}G_2,\dots, \tau G_2, G2]\\ [\Upsilon{n-2}, \Upsilon_{n-3}, …, \Upsilon_1, \Upsilon_0] &= [\tau^{n-2}t(\tau)G_1, \tau^{n-3}t(\tau)G_1, …, \tau t(\tau)G_1, t(\tau)G_1] \end{align} $$

注意，结构化参考字符串需要有足够的项以适应 QAP 中的多项式。

然后，可信设置销毁 $\tau$ 并发布结构化参考字符串：

$$([\Omega_2, \Omega_1, G_1], [\Theta_2, \Theta_1, G2], [\Upsilon{n-2}, \Upsilon_{n-3}, …, \Upsilon_1, \Upsilon_0])$$

prover 按如下方式评估 QAP 的组件：

$$\underbrace{\sum_{i=1}^m a_iui(x)}{A}\underbrace{\sum_{i=1}^m a_iv_i(x)}B = \underbrace{\sum{i=1}^m a_iwi(x) + h(x)t(x)}{C}$$

$$ \begin{align} [A]1 &=\sum{i=1}^m a_iui(\tau) = \langle[u{{n-1}a}, u{{n-2}a}, \dots, u{1a}, u{0a}],[\Omega{n-1}, \Omega_{n-2}, \dots, \Omega_1, G_1]\rangle\\ [B]2 &=\sum{i=1}^m a_ivi(\tau) = \langle[v{{n-1}a}, v{{n-2}a}, \dots, v{1a}, v{0a}],[\Theta{n-1}, \Theta_{n-2}, \dots, \Theta_1, G_2]\rangle\\ [C]1 &=\sum{i=0}^m a_iwi(\tau) + h(\tau)t(\tau) = \langle[w{{n-1}a}, w{{n-2}a}, \dots, w{1a}, w{0a}],[\Omega{n-1}, \Omega_{n-2}, \dots, \Omega_1, G1]\rangle \\ &+\langle[h{n-2}, h_{n-3}, \dots, h_1, h0], [\Upsilon{n-2}, \Upsilon_{n-3}, \dots, \Upsilon_1, \Upsilon_0] \rangle\\ \end{align} $$

prover 发布 $([A]_1, [B]_2, [C]_1)$，并且验证者可以检查

$$[A]_1 \bullet [B]_2 \stackrel{?}= [C]_1 \bullet G_2$$

证明非常小

观察到证明仅由三个椭圆曲线点组成。如果一个 $\mathbb{G}_1$ 元素为 64 字节大，而一个 $\mathbb{G}_2$ 元素为 128 字节大，则证明仅为 256 字节。这一点是真正的无论 R1CS 的大小如何！

R1CS 越大，prover 要做的工作越多，但验证者的工作保持不变。

此问题的解决方案在下一章关于 Groth16 协议中描述。

在 Groth16 中，证明仍然保持为固定大小，可以在 struct 看到名为 Proof。

原文发布于 2023 年 8 月 28 日

原文链接： rareskills.io/post/ellip...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。