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

Last updated on Jan 5, 2026

在可信设置 (trusted setup) 上评估 Quadratic Arithmetic Program (QAP) 使得证明者能够在不泄露 witness 的情况下，使用固定大小的证明来证明 QAP 已被满足。

具体来说，QAP 多项式在一个未知点 $\tau$ 处进行评估。如果向量 $\mathbf{a}$ 满足方程，则 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)

将会是平衡的（等式两边相等）；否则，它以压倒性的概率是不平衡的。

此处展示的方案并不是一个安全的 ZK Proof，但它是展示 Groth16 工作原理的垫脚石。

一个具体示例

为了让这不那么抽象，假设 Rank 1 Constraint System (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_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$ 。两点之间的椭圆曲线配对记作 $[X]_1 \bullet [Y]_2$ 。

设 $\mathbf{L}_{(*,j)}$ 为 $\mathbf{L}$ 的第 $j$ 列。在我们的示例中，行是 $(1,2,3)$ ，列是 $(1,2,3,4)$ 。设 $\mathcal{L}(\mathbf{L}_{(*,j)})$ 为使用 $x$ 值 $(1,2,3)$ 以及作为第 $j$ 列的 $y$ 值，对 $\mathbf{L}$ 的第 $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*} w_1(x) = \mathcal{L}(\mathbf{O}_{(*,1)}) =w_{12}x^2 + w_{11}x+w_{10}\\ w_2(x) = \mathcal{L}(\mathbf{O}_{(*,2)}) =w_{22}x^2 + w_{21}x+w_{20}\\ w_3(x) = \mathcal{L}(\mathbf{O}_{(*,3)}) =w_{32}x^2 + w_{31}x+w_{30}\\ w_4(x) = \mathcal{L}(\mathbf{O}_{(*,4)}) =w_{42}x^2 + w_{41}x+w_{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$ 表示我们将这些多项式与 witness $\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 结合

我们现在可以应用从可信设置中获取的结构化参考字符串 (structured reference string) 来评估这些多项式。

也就是说，给定一个结构化参考字符串

[\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$ 的值是未知的。

我们已经使用 srs 计算了 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 的多项式，这超过了 powers of tau 仪式所提供的项数。因此，必须对 powers of tau 仪式进行调整，以为 $h(x)t(x)$ 提供结构化参考字符串。

执行可信设置的人知道 $t(x)$ ，它仅仅是 $(x - 1)(x - 2)...(x - n)$ 。然而， $h(x)$ 是由证明者计算出的多项式，并且会根据 $\mathbf{a}$ 的值而变化，因此它在可信设置期间是未知的。

请注意，我们不能分别评估 $h(\tau)$ 和 $t(\tau)$ （使用结构化参考字符串），然后再将它们配对在一起。那样做不会产生我们所需要的 $\mathbb{G}_1$ 元素。

多项式乘积的 SRS

观察到以下计算都会得出相同的值：

多项式 $h(x)t(x)$ 在 $u$ 处求值，即 $(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$ 处评估此多项式将需要证明者知道 $\tau$ 。这里的关键见解是，上述计算可以构造为：

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

如果可信设置提供 $[4u^2, 4u, 4]$ ，而证明者提供 $[3, 6, 2]$ ，那么证明者可以在不知道 $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)$ ，证明者执行以下操作：

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$ 的多项式（拉格朗日多项式的次数比其插值的点数少一）， $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])

证明者对 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=1}^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*}

证明者发布 $([A]_1, [B]_2, [C]_1)$ ，验证者可以检查以下等式：

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

如果 witness $\mathbf{a}$ 满足 QAP，那么上述方程将是平衡的。但是，方程平衡并不能确保证明者知道一个令人满意的 $\mathbf{a}$ ，因为证明者可以发布任意的椭圆曲线点，而验证者并不知道它们是否真正推导自 QAP。

证明非常小

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

R1CS 越大，证明者的工作量就越大，但验证者的工作量保持不变。

解决此问题的方法在下一章关于 Groth16 protocol 中有描述。

在 Groth16 中，证明仍然保持固定大小，这可以从 Tornado Cash 源代码中名为 Proof 的 struct 处看到。

最初发布于 2023 年 8 月 28 日