Source: https://rareskills.io/zh-cn/post/elliptic-curve-qap
在可信设置 (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)$
<aside> 💡 💡 一句话理解这个方程在干什么：它把一整套约束条件压缩成了『一道多项式等式』。左边是两组多项式相乘，右边是第三组多项式加上一个余项 $h(x)t(x)$。只要证明者用的 witness $\mathbf{a}$ 是对的，左右两边就严丝合缝地相等；只要 $\mathbf{a}$ 是编的，两边几乎必然对不上。后面整篇文章都是在想办法：怎么让证明者在『不公开 $\mathbf{a}$』的前提下，向别人证明这个等式确实成立。
</aside>
将会是平衡的（等式两边相等）；否则，它以压倒性的概率是不平衡的。
此处展示的方案并不是一个安全的 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}$
<aside> 💡 💡 这里的小圈 $\circ$ 是『逐项相乘』，不是矩阵乘法。打个比方：$\mathbf{L}\mathbf{a}$ 和 $\mathbf{R}\mathbf{a}$ 各算出一列数，比如 $[2,3,5]$ 和 $[4,1,2]$，逐项相乘就是 $[2\times4,\,3\times1,\,5\times2]=[8,3,10]$，这必须正好等于 $\mathbf{O}\mathbf{a}$。每一行就是电路里的一条乘法约束（一个『左输入 × 右输入 = 输出』），整个矩阵等式就是『所有约束同时成立』。
</aside>
由于我们有 3 行，这意味着我们的插值多项式的最高次数将是 2。因为我们有 4 列，每个矩阵将产生 4 个多项式（总共 12 个多项式）。
<aside> 💡 💡 为什么行数决定次数、列数决定个数？把每一列看成几个散点：3 行就是 3 个点，穿过 3 个点的曲线最低用一条 2 次抛物线就能画出（点数减一），所以多项式最高 2 次。而每一列代表一个变量，4 列就是 4 个变量，于是 $\mathbf{L},\mathbf{R},\mathbf{O}$ 各产出 4 条曲线，$3\times4=12$ 条。
</aside>
我们的 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$ 列进行拉格朗日插值计算所得到的多项式。
<aside> 💡 💡 拉格朗日插值 $\mathcal{L}(\cdot)$ 就是『连点成线』。给你几个点的坐标，它帮你找出一条唯一穿过这些点的多项式曲线。这里把矩阵某一列的数字当成 $y$ 值，配上固定的 $x=(1,2,3)$，连成一条曲线 $u_j(x)$。好处是：原来一堆离散的约束数字，从此可以用一个连续的多项式来统一处理。
</aside>
因为我们有 4 列，所以我们从 $\mathbf{L}$ 中获得了四个多项式：