Groth16

Ref

Arithmetization 算数化

对于经过算数化的电路，我们可以表示为 $O\omega =L\omega \cdot R\omega$。

其中，$O,L,R$ 是 $n\times m$ 的矩阵，$\omega$ 是一个 $m\times 1$ 的约束向量，表示电路的输入和中间变量。$n$ 是约束的数量, $m$ 是所有变量的数量。($\omega$, witness)

QAP

对于验证矩阵的正确性，我们可以很自然地想到把矩阵通过插值计算为多项式形式，然后通过 Schwartz-Zippel 引理 来验证其正确性。这里有 $n$ 个约束，故而可以构造出三个 $n-1$ 次的多项式：

$$u(x)\cdot v(x)=w(x)$$

但是这里观察到左边的次数是 $2(n-1)$，而右边的次数是 $n-1$，两边次数不匹配,使得等式只能在 $n$ 个点上成立（Schwartz-Zippel）。为了解决这个问题，我们引入了一个特殊的多项式 $t(x)=(x-1)(x-2)(x-3)...(x-n)$, 称为目标多项式(target polynomial), 这个等式在 $x\in (0,n)$时为0不影响计算，在范围之外可以约束等式使其相等，最终可以使得：

$$u(x)\cdot v(x)-w(x)=h(x)\cdot t(x)$$

$[u,v,w]$, $n-1$ 次；$t$ , $n$ 次；$h$ , $n-2$ 次。故而 |左边 $2(n-1)=n+n-2$ 右边|。 这样就保证了等式 在任意取值上成立而不是仅在 $n$ 个点上成立。

利用SRS计算多项式

已知：

$$\overrightarrow{SRS}=([1{]}_1,[\tau {]}_1,[{\tau }^2{]}_1,...,[{\tau }^{m-1}{]}_1,[1{]}_2,[\tau {]}_2)$$

并且 $(u,w,t,h)\in {\mathbb{G}}_{\mathbb{1}}$, $v\in {\mathbb{G}}_{\mathbb{2}}$

对于多项式的计算，例如对于点 $\tau$ 的评估，可以写为：

$$f(\tau )=a_0[1{]}_1+a_1[\tau {]}_1+a_2[{\tau }^2{]}_1+...+a_d[{\tau }^d{]}_1$$

然后，我们就可以通过配对来验证多项式等式：

$$e(u(\tau ),v(\tau ))=e(w(\tau ),[1{]}_2)\cdot e(h(\tau ),t(\tau )[1{]}_2)$$

对于 $h(\tau )$ 的计算，如下：

1. 由于我们预先知道 $t(x)$, 并且在电路生成时我们可以提前先计算 $t(\tau )$ 再丢弃 $\tau$(这就是为什么Snarkjs里对于Groth电路需要再贡献一次，而Plonk不用的原因)，得到：

$$(Y_0,Y_1,...,Y_{n-2})=(t(\tau )[1{]}_1,t(\tau )[\tau {]}_1,t(\tau )[{\tau }^2{]}_1,...,t(\tau )[{\tau }^{n-2}{]}_1)$$

2. 从而有如下等式关系可以容易得到 $h(\tau )$ ：（这里的 $h_{\ast }$ 是 $h$ 的系数）

$$h(\tau )\cdot t(\tau )=(h_0,h_1,h_2,...,h_{n-2})\cdot (Y_0,Y_1,Y_2,...,Y_{n-2})$$

证明：

$$\begin{array}{rl}h(\tau )\cdot t(\tau )& =(h_0,h_1,h_2,...,h_{n-2})\cdot (t(\tau )[1{]}_1,t(\tau )[\tau {]}_1,t(\tau )[{\tau }^2{]}_1,...,t(\tau )[{\tau }^{n-2}{]}_1)\\ & =(h_0,h_1,h_2,...,h_{n-2})\cdot ([1{]}_1,[\tau {]}_1,[{\tau }^2{]}_1,...,[{\tau }^{n-2}{]}_1)\cdot t(\tau )\\ & =h(\tau )\cdot t(\tau )\end{array}$$

TIP

此时我们有：

P: $[A{]}_1=u(\tau ),[B{]}_2=v(\tau ),[C{]}_1=w(\tau )+h(\tau )t(\tau )$

V: 验证 $e([A{]}_1,[B{]}_2)=e([C{]}_1,[1{]}_2)$