Groth16 详解

Groth16算法使得证明者可以在可信设置中利用椭圆曲线点计算二次算术程序，并由验证者快速检查。它使用来自可信设置的辅助椭圆曲线点来防止伪造证明。

前提条件

本文是RareSkills Book of Zero Knowledge Proofs中的一章。假设你已熟悉之前的章节。

表示法

我们将属于$\mathbb{G}_1$椭圆曲线群的一个椭圆曲线点表示为$[x]_1$，属于$\mathbb{G}_2$椭圆曲线群的椭圆曲线点表示为$[x]_2$。$[x]_1$和$[x]_2$之间的一个 pairing 表示为 $[x]_1\bullet[x]2$，并在 $\mathbb{G}{12}$ 中生成一个元素。粗体字母变量如$\mathbf{a}$表示向量，粗体大写字母如$\mathbf{L}$表示矩阵，字段元素（有时非正式地称为“标量”）是小写字母，如$d$。所有算术运算都发生在一个有限域中，特征等于椭圆曲线群的阶。

给定一个算术电路 (ZK Circuit)，我们将其转换为秩 1约束系统(R1CS) $\mathbf{L}\mathbf{a}\circ \mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}$，其中矩阵的维度为$n$行和$m$列，见证向量为$\mathbf{a}$。然后，我们可以通过将矩阵的列插值为在$x$值$[1,2,…,n]$上的$y$值，从R1CS转换为二次算术程序(QAP)。由于$\mathbf{L}$，$\mathbf{R}$，和$\mathbf{O}$有$m$列，我们将得到三组$m$个多项式：

$$ \begin{array}{} u_1(x),…,u_m(x) & m \text{ 个在 } m \text{ 列的 } \mathbf{L} \text{ 上插值的多项式}\ v_1(x),…,v_m(x)& m \text{ 个在 } m \text{ 列的 } \mathbf{R} \text{ 上插值的多项式}\ w_1(x),…,w_m(x)& m \text{ 个在 } m \text{ 列的 } \mathbf{O} \text{ 上插值的多项式}\ \end{array} $$

从这个多项式中，我们可以构造一个二次算术程序(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) $$

其中 $$ t(x) = (x – 1)(x – 2)\dots(x – n) $$

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

如果一个第三方通过tau挤压仪创建结构化参考字符串(srs)，那么证明者可以在隐藏点$\tau$上计算和项 （$\sum a_if_i(x)$项）在QAP中。假设结构化参考字符串的计算如下：

$$ \begin{align} [\Omega{n-1}, \Omega{n-2},\dots,\Omega_2,\Omega_1,G_1] &= [\tau^nG_1,\tau^{n-1}G_1,\dots,\tau G_1,G_1] && \text{对于 } G1 \\ [\Theta{n-1}, \Theta_{n-2},\dots,\Theta_2,\Theta_2,G_2] &= [\tau^nG_2,\tau^{n-1}G_2,\dots,\tau G_2,G_2] && \text{对于 } G2\\ [\Upsilon{n-2},\Upsilon_{n-3},\dots,\Upsilon_1,\Upsilon_0]&=[\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] && \text{对于 }h(\tau)t(\tau)\\ \end{align} $$

我们将$f(\tau)$称为在结构化参考字符串$[\tau^dG_1,…,\tau^2G_1,\tau G_1,G_1]$上评估的多项式，通过内积获取：

$$ f(\tau) = \sum_{i=1}^d f_i\Omega_i=\langle[fd, f{d-1},…,f_1,f_0],[\Omegad,\Omega{d-1},…,G_1]\rangle $$

或者对于 $\mathbb{G}_2$的srs：

$$ f(\tau) = \sum_{i=1}^d f_i\Theta_i=\langle[fd, f{d-1},…,f_1,f_0],[\Thetad,\Theta{d-1},…,G_1]\rangle $$

$f(\tau)$是上述表达式的简写，生成一个椭圆曲线点。这并不意味着证明者知道$\tau$。

证明者可以通过计算来评估其QAP在可信设置：

$$ \begin{align} [A]1 &= \sum{i=1}^m a_iu_i(\tau)\ [B]2 &= \sum{i=1}^m a_iv_i(\tau)\ [C]1 &= \sum{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau) \end{align} $$

此计算的详细信息在我们的教程在椭圆曲线上进行二次算术程序中讨论。

如果QAP是平衡的，则以下等式成立：

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

动机

仅仅提供$([A]_1, [B]_2, [C]_1)$并不能令人信服地证明证明者知道$\mathbf{a}$使得QAP是平衡的。

证明者可以随意虚构值$a$，$b$，$c$使得$ab = c$，计算

$$ \begin{align} [A]_1 &= aG_1\ [B]_2 &= bG_2\ [C]_1 &= cG_1 \end{align} $$

并将这些作为椭圆曲线点$[A]_1$，$[B]_2$，$[C]_1$呈现给验证者。

因此，验证者无法得知$([A]_1, [B]_2, [C]_1)$是否是满足的QAP的结果。

我们需要迫使证明者诚实，而不会引入太多的计算开销。第一个能做到这一点的算法是“Pinocchio: Nearly Practical Verifiable Computation”。这个算法足够可用，使得ZCash能基于其第一个版本的区块链。

然而，Groth16能够在更少的步骤中完成同样的事情，并且该算法至今仍被广泛使用，因为自其之后没有其他算法能够为验证步骤提供如此高效的算法（尽管其他算法已消除了可信设置或显著减少了证明者的计算量）。

2024更新： 一篇题为“Polymath: Groth16 is not the limit”的论文在《密码学》中发布，展示了一种算法，其所需的验证者步骤少于Groth16。然而，目前尚无已知的该算法的实现。

防止伪造第 1 部分：引入 $\alpha$ 和 $\beta$

一个“不可解决”的验证公式

假设我们将验证公式更新为以下内容：

$$[A]_1 \bullet [B]2 \stackrel{?}= [D]{12} + [C]_1\bullet G_2$$

注意我们为方便起见使用了$G{12}$群的加法符号。_

这里，$[D]{12}$是来自$G{12}$的一个元素，并且有一个未知的离散对数。

我们现在展示，验证者在不知道$[D]_{12}$的离散对数的情况下，不可能提供方程$([A]_1, [B]_2, [C]_1)$的解。

攻击 1：伪造A和B并推导出C

假设证明者随机选择$a’$和$b’$生成$[A]{1}$和$[B]{2}$，并试图推导出一个与验证者公式兼容的值$[C’]$。

$$[A]_1 \bullet [B]2 \stackrel{?}= [D]{12} + [C]_1\bullet G_2$$

知道$[A]{1}$和$[B]{2}$的离散对数，恶意证明者尝试通过以下方式解出$[C’]$：

$$ \begin{align} \underbrace{[A]_1\bullet [B]2 – [D]{12}}{\chi{12}}=[C’]_1\bullet G2\ [\chi]{12}=[C’]_1\bullet G_2 \end{align} $$

最后一行要求证明者解决$\chi_{12}$的离散对数，因此他们不能计算出$[C’]_1$的有效离散对数。

攻击 2：伪造C并推导出A和B

这里证明者选择一个随机点$c’$并计算$[C’]_1$。因为他们知道$c’$，他们可以尝试发现$A’$和$B’$的兼容组合，使得

$$ \begin{align} [A]_1 \bullet [B]2 &\stackrel{?}= \underbrace{[D]{12} + [C]_1\bullet G2}{[\zeta]_{12}}\ [A]_1 \bullet [B]2 &\stackrel{?}=[\zeta]{12} \end{align} $$

这要求证明者在给定$[\zeta]{12}$的情况下想出一个$[A]{1}$和$[B]{2}$以生成$[\zeta]{12}$。

与离散对数问题类似，我们依赖未经证明的加密假设，即该计算（将$\mathbb{G}_{12}$中的一个元素分解成$\mathbb{G}_1$和$\mathbb{G}2$元素）是不可行的。在这种情况下，我们无法将$[\zeta]{12}$分解为$[A]{1}$和$[B]{2}$的假设称为双线性Diffie-Hellman假设。感兴趣的读者可以参见关于决策Diffie-Hellman假设 的相关讨论。

（未经证明并不意味着不可靠。如果你能找到证明或反驳该假设的方法，将会赢得名声和财富！在实践中，目前没有已知的方法将$[\zeta]{12}$分解为$[A]{1}$和$[B]_{2}$，并且相信这是计算上不可行的。）

$\alpha$和$\beta$的用法

实际上，Groth16不使用项$[D]_{12}$。相反，可信设置生成两个随机标量$\alpha$和$\beta$，并发布计算出的椭圆曲线点$([\alpha]_1,[\beta]_2)$：

$$ \begin{align} [α]_1 &= α G_1 \ [β]_2 &= β G_2 \end{align} $$

我们之前所称的$[D]_{12}$实际上就是$[\alpha]_1 \bullet [\beta]_2$。

重新推导证明和验证公式

为了使验证公式 $[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1\bullet[\beta]_2 + [C]_1\bullet G_2$“可解”，我们需要修改我们的QAP公式，以包含$\alpha$和$\beta$。

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

现在考虑我们如果将项$\theta$和$\eta$引入到方程的左侧会发生什么：

$$(\boxed{\theta}+\sum_{i=1}^m a_iui(x))(\boxed{\eta} +\sum{i=1}^m a_iv_i(x)) =$$

$$=\boxed{\theta\eta} + \boxed{\theta}\sum_{i=1}^m a_ivi(x) + \boxed{\eta}\sum{i=1}^m a_iui(x) + \sum{i=1}^m a_iui(x)\sum{i=1}^m a_iv_i(x)$$

我们可以使用原始QAP定义来替换右侧的最后项： $$=\theta\eta + \theta\sum_{i=1}^m a_ivi(x) + \eta\sum{i=1}^m a_iui(x) + \boxed{\sum{i=1}^m a_iui(x)\sum{i=1}^m a_iv_i(x)}$$

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

现在我们可以引入一个“扩展”QAP，其定义如下：

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

作为我们正在进行的概述，如果我们用$[\alpha]_1$替换$\theta$，用$[\beta]_2$替换$\eta$，我们得到早期的更新验证公式：

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

其中

$$ \underbrace{([\alpha]1+\sum{i=1}^m a_iui(\tau))}{[A]_1}\underbrace{([\beta]2 +\sum{i=1}^m a_ivi(\tau))}{[B]_2} =[\alpha]_1\bullet[\beta]2 + (\underbrace{\alpha\sum{i=1}^m a_ivi(\tau) + \beta\sum{i=1}^m a_iui(\tau) + \sum{i=1}^m a_iwi(\tau) + h(\tau)t(\tau)}{[C]_1}) \bullet G_2 $$

证明者可以在不知$\tau$，$\alpha$，或$\beta$的情况下计算$[A]_1$和$[B]_2$。Given the structured reference string (powers of $\tau$) and the elliptic curve points $([\alpha]_1,[\beta]_2)$, the prover computes $[A]_1$ and $[B]_2$ as

$$ \begin{align} [A]_1 &= [\alpha]1 + \sum{i=1}^m a_iu_i(\tau)\ [B]_2 &= [\beta]2 + \sum{i=1}^m a_iv_i(\tau)\ \end{align} $$

这里$a_iu_i(\tau)$并不意味着证明者知道$\tau$。证明者使用结构化参考字符串$[\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1]$来计算$u_i(\tau)$，其中$i=1,2,\dots,m$以及$G_2$的srs用于$[B]_2$。

然而，目前不可能在不知道$\alpha$和$\beta$的情况下计算$[C]_1$。证明者不能将$[\alpha]_1$与$\sum a_iu_i(\tau)$以及$[\beta]_2$与$\sum a_ivi(\tau)$配对，因为那会生成一个$\mathbb{G}{12}$点，而证明者需要一个$\mathbb{G}_1$点来计算$[C]_1$。

相反，可信设置需要预先计算用于扩展QAP中有问题的$C$项的$m$个多项式。

$$\alpha\sum_{i=1}^m a_ivi(\tau) + \beta\sum{i=1}^m a_iui(\tau) + \sum{i=1}^m a_iw_i(\tau)$$

通过一些代数运算，我们将和项组合为一个单一的和：

$$=\sum_{i=1}^m (\alpha a_iv_i(\tau)+\beta a_iu_i(\tau) + a_iw_i(\tau))$$

并将$a_i$提取出来：

$$=\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))}$$

可信设置可以从上面框起来的项创建$m$个在$\tau$上评估的多项式，证明者可以用它来计算该和。确切的细节将在下一部分中显示。

目前算法的总结

可信设置步骤

具体来说，可信设置计算如下： $$ \begin{align} \alpha,\beta,\tau &\leftarrow \text{随机标量}\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs for } \mathbb{G}_1\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs for } \mathbb{G}_2\ [\tau^{n-2}t(\tau),\tau^{n-3}t(\tau),\dots,\tau t(\tau),t(\tau)] &\leftarrow \text{srs for }h(\tau)t(\tau)\ [\Psi_1]_1 &= (\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau))G_1\ [\Psi_2]_1 &= (\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau))G_1\ &\vdots\ [\Psi_m]_1 &= (\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau))G_1\ \end{align} $$

可信设置发布

$$([\alpha]_1,[\beta]2,\text{srs}{G1},\text{srs}{G_2},...