Source: https://rareskills.io/zh-cn/post/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电路） ，我们将其转换为 秩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$ 个的多项式：
<aside> 💡 💡 一句话理解：R1CS 是一张『竖着写』的检查表——矩阵 $\mathbf{L}$、$\mathbf{R}$、$\mathbf{O}$ 的每一行是一条约束，每一列对应见证里的一个变量。『把列插值成多项式』就是把这一列散落的几个数（比如第 1、2、3 行的值 $[2,0,5]$）当成几个点，连成一条平滑曲线 $u_i(x)$。这样原本 $n$ 行约束就被打包进了一条多项式里，以后只需在一个点上抽查，而不必逐行核对。
</aside>
$\begin{array}{} u_1(x),...,u_m(x) & 对 \mathbf{L} 的 m 列进行插值得到的 m 个多项式\\ v_1(x),...,v_m(x)& 对 \mathbf{R} 的 m 列进行插值得到的 m 个多项式\\ w_1(x),...,w_m(x)& 对 \mathbf{O} 的 m 列进行插值得到的 m 个多项式\\ \end{array}$
由此，我们可以构造一个二次算术程序 (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)$
<aside> 💡 💡 这就是整篇文章的『主等式』：左边两个求和相乘，对应原电路里『左输入 × 右输入』；右边是『输出』再加上一个 $h(x)t(x)$ 的修正项。$\sum a_iu_i(x)$ 的意思是『把见证 $a_i$ 当权重，对每条曲线 $u_i(x)$ 加权求和』，得到一条总曲线。只要见证 $\mathbf{a}$ 是真的，这个等式在每个检查点上都成立。
</aside>
其中
$t(x) = (x - 1)(x - 2)\dots(x - n)$
<aside> 💡 💡 $t(x)=(x-1)(x-2)\dots(x-n)$ 是一把精心设计的『锁』：它在 $x=1,2,\dots,n$ 这些检查点上恰好全等于 0。为什么需要它？因为左减右不一定处处为零，但只要见证正确，它在所有检查点必为零，所以一定能被 $t(x)$ 整除。它的作用就是『把检查点上的误差合法地吸收掉』。
</aside>
且
$h(x) = \frac{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) - \sum_{i=1}^m a_iw_i(x)}{t(x)}$
<aside> 💡 💡 别被分式吓到：$h(x)$ 不过是『左乘右减去输出，再除以那把锁 $t(x)$ 的商』。打个比方——如果你声称 $15$ 能被 $3$ 整除，商就是 $5$；这里若见证作弊，分子在某个检查点不为 0，就除不尽、得不到干净的 $h(x)$，作弊立刻暴露。所以能算出 $h(x)$ 本身就是『我没作弊』的证据。
</aside>
如果第三方通过 powers of tau 仪式创建了一个结构化参考字符串 (srs)，那么证明者就可以在一个隐藏点 $\tau$ 处计算 QAP 中的求和项（即 $\sum a_if_i(x)$ 项）。假设结构化参考字符串如下计算：
<aside> 💡 💡 这里最绕的是『隐藏点 $\tau$』：可信设置随机选一个秘密数 $\tau$，算完 $\tau, \tau^2, \tau^3,\dots$ 各自『锁进』椭圆曲线点里就把 $\tau$ 销毁。好比有人把 $\tau$ 的各次幂封进一排上锁的保险箱后烧掉钥匙：你能用箱子做加法、配对，却永远打不开看到里面的数。证明者就靠这排箱子，在『谁都不知道的点 $\tau$』上给多项式求值。
</aside>