Groth16

Ref

Arithmetization 算数化

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

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

记：

$$\begin{array}{rl}\omega & =[a_1,a_2,a_3,...,a_m]\\ u(x)& =L\cdot \omega =[u_1(x),u_2(x),u_3(x),...,u_n(x)]\cdot {\omega }^T\end{array}$$

这里的角标是指矩阵列插值得出的多项式。

其他同理。

QAP

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

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

其中：

$$\begin{array}{rl}u(x)& =L\cdot \omega =\sum _{i=1}^m{a}_i{u}_i(x)\\ v(x)& =R\cdot \omega =\sum _{i=1}^m{a}_i{v}_i(x)\\ w(x)& =O\cdot \omega =\sum _{i=1}^m{a}_i{w}_i(x)\end{array}$$

但是这里观察到左边的次数是 $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(x),v(x),w(x)]$, $n-1$ 次；$t(x)$ , $n$ 次；$h(x)$ , $n-2$ 次。故而 |左边 $2(n-1)=n+n-2$ 右边|。 这样就保证了等式在任意取值上成立而不是仅在 $n$ 个点上成立。

从而，通过公开的 $L,R,O$，验证者可以知道 Prover 的运算程序，而 $\omega$ （用户的输入和中间的运算轨迹）是私有的。但是， Verifier 仍然可以通过验证 $u(x)\cdot v(x)-w(x)=h(x)\cdot t(x)$ 来保证 Prover 的计算是正确的（可验证计算）。

这样，我们就有一个初步的 Sigma 协议雏形：

1. Prover 对自己的多项式做出承诺 $Commit$ 传输给 Verifier。
2. Verifie 发送随机值 $r$ 给 Prover.
3. Prover 计算出多项式 $u(x),v(x),\dots$ 给 Verifier。
4. Verifier 进行验证。

接下来，我们的目标就是如何确保 Provr 在第三部时确实是根据正确的多项式进行运算的。

利用SRS计算多项式

 

以下对于 $G_T$ 的加法都是乘法

这里我们使用可信设置(多方安全计算)生成一个秘密值 $\tau$, 再计算公共参考字符串(SRS)，这里需要确保 $\tau$ 在用后即销毁。

我们有：

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

Note that $[u(x),w(x),t(x),h(x)]\in {\mathbb{G}}_{\mathbb{1}}$, $v(x)\in {\mathbb{G}}_{\mathbb{2}}$

验证 SRS 的正确性

记住我们同时给出了 $[1{]}_1,[\tau {]}_1,[{\tau }^2{]}_1,...,[{\tau }^{m-1}{]}_1$ 和 $[1{]}_2,[\tau {]}_2$

证明生成 $\tau G_2=[\tau {]}_2$ 的正确性：e($[1{]}_1,[\tau {]}_2$) = e($[\tau {]}_1,[1{]}_2$)

证明生成 ${\tau }^i{G}_1=[{\tau }^i{]}_1$ 的正确性：e($[{\tau }^i{]}_1,[1{]}_2$) = e($[1{]}_1,[{\tau }^i{]}_2$)

这样，当我们删除 $\tau$ 后，我们就可以得到一个公共的参考字符串，任何人都可以使用这个字符串来计算多项式的评估值，同时还能保证没人能够知道计算评估值 $f(\tau )$ 时具体计算的是哪个点的取值，并且通过配对来验证多项式等式。

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

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

其中 $a_i$ 是多项式 $f(x)$ 的系数，对于在 $G_2$ 上的多项式评估同样适用：

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

使用SRS计算QAP多项式

我们的目标是计算：

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

此时的问题是，我们希望 rhs 是 $G_1$ 上的元素，但是计算 $h(x)t(x)$ 需要长度为 $2(n-1)$ 的SRS。

这里我们考虑到 $t(x)$ 是已知并且固定的，故而我们可以先计算 $t(\tau )$ 的评估值：

1. 由于我们预先知道 $t(x)$, 并且在可信设置我们可以提前先计算 $t(\tau )$ 再丢弃 $\tau$(这里是可信设置时直接计算的，不是低度扩展)，得到：

$${\overrightarrow{SRS}}_{t(\tau )}=(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}$$

此时我们有：

 

• SRS：${\overrightarrow{SRS}}_1，{\overrightarrow{SRS}}_2，{\overrightarrow{SRS}}_{t(\tau )}$

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

• Verifier: 需要验证 $e([A{]}_1,[B{]}_2)=e([C{]}_1,[1{]}_2)$

NOTE HERE

引入随机性，保证QAP正确性

之后，我们需要在可信设置随机生成两个秘密标量，$\alpha \mathrm{\&}\beta$，并且投射到曲线上，有：

$$[\alpha {]}_1\mathrm{\&}[\beta {]}_2$$

这时我们修改 $[A{]}_1$ 和 $[B{]}_2$ 的计算方式，令:

$$\begin{array}{r}{}_1=[\alpha {]}_1+u(\tau )\\ [B{]}_1=[\beta {]}_2+v(\tau )\end{array}$$

并且为了同时使得上面的等式仍然成立 Here，修改 $[C{]}_1$ 为：

$$\alpha v(\tau )+\beta u(\tau )+w(\tau )+h(\tau )\cdot t(\tau )$$

需要验证的式子变为：

$$e([A{]}_1,[B{]}_2)=e([\alpha {]}_1,[\beta {]}_2)+e([C{]}_1,G_2)$$

易证：

$$\begin{array}{rl}e([A{]}_1,[B{]}_2)& \\ & =e([\alpha {]}_1+u(\tau ),[\beta {]}_2+v(\tau ))\\ & =e([\alpha {]}_1,[\beta {]}_2)+e([\alpha {]}_1,v(\tau ))+e(u(\tau ),[\beta {]}_2)+e(u(\tau ),v(\tau ))\\ & =e([\alpha {]}_1,[\beta {]}_2)+e([\alpha {]}_1,v(\tau ))+e(u(\tau ),[\beta {]}_2)+e(w(\tau )+h(\tau )\cdot t(\tau ),G_2)\\ & =e([\alpha {]}_1,[\beta {]}_2)+e([C{]}_1,G_2)\end{array}$$

这样变换 $[C{]}_1$ 的原因很显然，把配对操作从 4 次减少为了两次。

但是这里又出现了一个问题，计算 $[C{]}_1$ 时我们需要 $\alpha$ 和 $\beta$ 的值，故而方法也很显然，跟前面计算$h(\tau )v(\tau )$时一样，我们在进行可信设置时预计算。

这里先把多项式展开回上面的形式：

$$\begin{array}{rl}u(x)& =\sum _{i=1}^m{a}_i{u}_i(x)\\ v(x)& =\sum _{i=1}^m{a}_i{v}_i(x)\\ w(x)& =\sum _{i=1}^m{a}_i{w}_i(x)\end{array}$$

注意到对于 Prover 之外的人来说，$a_i$ 是不可见的（ $\omega =[a_1,a_2,a_3,...,a_m]$ 是私有数据），有且只有 $u_i(x),v_i(x),w_i(x)$ 可见。

再回顾一下我们的目标：计算 $[C{]}_1=\alpha v(\tau )+\beta u(\tau )+w(\tau )+h(\tau )\cdot t(\tau )$

故而在可信设置时，我们还需计算：

$$\sum _{i=1}^m[\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )]$$

然后再由 Prover 计算：

$$\sum _{i=1}^m{a}_i[\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )]$$

从而，通过可信设置（类似于承诺），我们可以确保 Prover 在生成证据时，使用的是正确的程序（QAP），这也解释了为什么在SnarkJS中Groth16要再Contribute一次，而Plonk不用。

说明

对于要验证的 $e([A{]}_1,[B{]}_2)=e([\alpha {]}_1,[\beta {]}_2)+e([C{]}_1,G_2)$，展开得到：

$$\begin{array}{rl}lhs& =e([\alpha {]}_1,[\beta {]}_2)+e([\alpha {]}_1,v(\tau ))+e(u(\tau ),[\beta {]}_2)+e(u(\tau ),v(\tau ))\\ rhs& =e([\alpha {]}_1,[\beta {]}_2)+e(\alpha v(\tau )+\beta u(\tau )+w(\tau )+h(\tau )\cdot t(\tau ),G_2)\end{array}$$

• 注意到可信设置确保了 $e([\alpha {]}_1,v(\tau ))+e(u(\tau ),[\beta {]}_2)=e(\alpha v(\tau )+\beta u(\tau ),G_2)$ 的不可伪造性，对于 rhs 来说 Prover 不可能在使用错误的 $v(\tau )||u(\tau )$ 下计算得出目标
• 而对于：$e(u(\tau ),v(\tau ))=e(w(\tau )+h(\tau )\cdot t(\tau ),G_2)$ 来说，确保了计算的正确性

此时我们有

 

• SRS:

• • random $\to \alpha ,\beta ,\tau$
• • ${\overrightarrow{SRS}}_1\to ([1{]}_1,[\tau {]}_1,[{\tau }^2{]}_1,...,[{\tau }^{m-1}{]}_1)$
• • ${\overrightarrow{SRS}}_2\to ([1{]}_2,[\tau {]}_2,[{\tau }^2{]}_2,...,[{\tau }^{m-1}{]}_2)$
• • ${\overrightarrow{SRS}}_{t(\tau )}\to (t(\tau )[1{]}_1,t(\tau )[\tau {]}_1,t(\tau )[{\tau }^2{]}_1,...,t(\tau )[{\tau }^{n-2}{]}_1)$
• • $[{\psi }_i{]}_1=[\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau ){]}_1$

• Public

• • $[\alpha {]}_1,[\beta {]}_2,{\overrightarrow{SRS}}_1,{\overrightarrow{SRS}}_2,{\overrightarrow{SRS}}_{t(\tau )},[{\psi }_i{]}_1$

• Prover

• • $[A{]}_1=[\alpha {]}_1+u(\tau )[B{]}_1=[\beta {]}_2+v(\tau )$
• • $[C{]}_1=\sum _{i=1}^m{a}_i[{\psi }_i{]}_1+h(\tau )t(\tau )$

• Verifier

• • $e([A{]}_1,[B{]}_2)=e([\alpha {]}_1,[\beta {]}_2)+e([C{]}_1,G_2)$

支持公开输入

在Circom中，我们可以通过 signal public 来声明公开输入，例如下面的Hash代码：

template Hash() {
    signal input a;
    signal input b;
    signal input value;
    signal output c;
    signal 

    conponent hasher = Poseidon(2);
    hasher.inputs[0] <== a;
    hasher.inputs[1] <== b;
    c <== hasher.out;
    value === c;

    log("hash: ", c);
}

component main{ public [a, value] } = Hash();

目前为止，我们所有的 $\omega$（witness）都是私有的，但是我们可以在计算 $[C{]}_1$ 时把公开输入的部分单独拿出来计算，这里假设我们只公开前 $\mathcal{l}$ 个元素，那么我们可以把 $[C{]}_1$ 的计算方式修改为：

$$[C_1]=\sum _{i=\mathcal{l}+1}^m{a}_i[{\psi }_i{]}_1+h(\tau )\cdot t(\tau )$$

注意这里的角标变了，既不隐藏 $\omega$ 的前 $\mathcal{l}$ 个元素

然后由验证者计算：

$$[X{]}_1=\sum _{i=1}^{\mathcal{l}}{a}_i[{\psi }_i{]}_1$$

这时候，验证的公式变为：

$$e([A{]}_1,[B{]}_2)=e([\alpha {]}_1,[\beta {]}_2)+e([X{]}_1,G_2)++e([C{]}_1,G_2)$$

 

但是，我们该如何限制Prover只使用私有变量计算 $[C{]}_1$，而不使用 $[X{]}_1$ 中的公开变量呢？ For example: 这里我们设置 $\mathcal{l}=5$，既前五个元素是可见的，Prover原本的计算方式应该是:

$$e(a_1{\psi }_1+a_2{\psi }_2+...+a_5{\psi }_5,G_2)+(a_6{\psi }_6+a_7{\psi }_7+h(\tau )\cdot t(\tau ),G_2)$$

但是如果 Prover 想要作弊的话，假设这里把sym2给隐藏，既使得 Verifier 彻底无法知道程序的正确性，可以把 $[C{]}_1$ 的计算方式修改为：

$$e(a_1{\psi }_1+a_2{\psi }_2+...+0{\psi }_5,G_2)+(a_5{\psi }_5+a_6{\psi }_6+a_7{\psi }_7+h(\tau )\cdot t(\tau ),G_2)$$

这样，把公开变量从 $[a_1,a_2,...a_5]$ 变为了 $[a_1,a_2,...,0]$, 但是仍然使得验证通过了，这就导致了 Prover 可以在不使用公开输入的情况下计算出正确的证明，造成了安全隐患。

为了解决这个问题，我们继续在可信设置时引入两个变量 $\gamma$ 和 $\delta$，我们把 ${\overrightarrow{SRS}}_{t(\tau )}$ 变为：

$${\overrightarrow{SRS}}_{t(\tau )}=(\frac{(t(\tau )[1{]}_1}{\delta },\frac{(t(\tau )[\tau {]}_1}{\delta },\frac{(t(\tau )[{\tau }^2{]}_1}{\delta },...,\frac{(t(\tau )[{\tau }^{n-2}{]}_1}{\delta })$$

再把 $[{\psi }_{i=1\dots \mathcal{l}}{]}_1\to [\frac{\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )}{\gamma }{]}_1$, $[{\psi }_{i=(l+1)\dots \mathcal{m}}{]}_1\to [\frac{\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )}{\delta }{]}_1$

同时修改验证的计算方式

$$[X{]}_1=\sum _{i=1}^{\mathcal{l}}{a}_i[{\psi }_i{]}_1$$$$e([A{]}_1,[B{]}_2)=e([\alpha {]}_1,[\beta {]}_2)+[X{]}_1\cdot [\gamma {]}_2+e([C{]}_1,G_2)\cdot [\delta {]}_2$$

这里的原因也是显然的，把 $[C{]}_1$ 的计算和 $\delta$ 进行绑定， 把 $[X{]}_1$ 的计算和 $\gamma$ 进行绑定，这样 Prover 就无法在不使用公开输入的情况下计算出正确的证明了。

此时我们有

 

• SRS:

• • random $\to \alpha ,\beta ,\tau ,\gamma ,\delta$
• • ${\overrightarrow{SRS}}_1\to ([1{]}_1,[\tau {]}_1,[{\tau }^2{]}_1,...,[{\tau }^{m-1}{]}_1)$
• • ${\overrightarrow{SRS}}_2\to ([1{]}_2,[\tau {]}_2,[{\tau }^2{]}_2,...,[{\tau }^{m-1}{]}_2)$
• • ${\overrightarrow{SRS}}_{t(\tau )}=(\frac{(t(\tau )[1{]}_1}{\delta },\frac{(t(\tau )[\tau {]}_1}{\delta },\frac{(t(\tau )[{\tau }^2{]}_1}{\delta },...,\frac{(t(\tau )[{\tau }^{n-2}{]}_1}{\delta })$
• • $[{\psi }_i{]}_{1\to \mathcal{l}}\to [\frac{\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )}{\gamma }{]}_1$ \ $[{\psi }_i{]}_{(l+1)\to \mathcal{m}}\to [\frac{\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )}{\delta }{]}_1$

• Public

• • $[\alpha {]}_1,[\beta {]}_2,[\gamma {]}_2,[\delta {]}_2,{\overrightarrow{SRS}}_1,{\overrightarrow{SRS}}_2,{\overrightarrow{SRS}}_{t(\tau )},[{\psi }_i{]}_1$

• Prover

• • $[A{]}_1=[\alpha {]}_1+u(\tau )[B{]}_1=[\beta {]}_2+v(\tau )$
• • $[C{]}_1=\sum _{i=\mathcal{l}+1}^m{a}_i[{\psi }_i{]}_1+h(\tau )t(\tau )$

• Verifier

• • $[X{]}_1=\sum _{i=1}^{\mathcal{l}}{a}_i[{\psi }_i{]}_1$
• • $e([A{]}_1,[B{]}_2)=e([\alpha {]}_1,[\beta {]}_2)+e([X{]}_1,[\gamma {]}_2)+e([C{]}_1,[\delta {]}_2)$

实现零知识

由于运算程序是已知的，并且当前对于证明者，我们没有引入任何的随机性，故而攻击者可以通过遍历所有的输入可能从而获得证明者的输入和中间变量的值，造成隐私泄露。

为了保障零知识性质，Prover 在生成证据 $\pi$ 时 可以生成两个随机数 $\mathcal{r}$ 和 $\mathcal{s}$，并且把 $[A{]}_1$ 、$[B{]}_2$ 和 $[C{]}_3$ 的计算方式修改为：

$$\begin{array}{r}\\ [A{]}_1=& [\alpha {]}_1+u(\tau )+\mathcal{r}\cdot [\delta {]}_1\\ [B{]}_1=& [\beta {]}_1+v(\tau )+\mathcal{s}\cdot [\delta {]}_1\\ [B{]}_2=& [\beta {]}_2+v(\tau )+\mathcal{s}\cdot [\delta {]}_2\\ [C{]}_1=& \sum _{i=\mathcal{l}+1}^m{a}_i[{\psi }_i{]}_1+h(\tau )t(\tau )+s[A{]}_1+r[B{]}_1-rs[\delta {]}_1\end{array}$$

这样，通过引入随机性，我们就可以保证 Prover 的输入和中间变量的值是不可预测的，从而保障了零知识性质。

推导

$$\begin{array}{rl}e([A{]}_1,[B{]}_2)=& e([\alpha {]}_1+u(\tau )+\mathcal{r}\cdot [\delta {]}_1,[\beta {]}_2+v(\tau )+\mathcal{s}\cdot [\delta {]}_2)\\ & \text{以下的 }\cdot \text{ 为配对操作:}\\ =& [\alpha {]}_1\cdot [\beta {]}_2+[\alpha {]}_1\cdot v(\tau )+u(\tau )\cdot [\beta {]}_2+u(\tau )\cdot t(\tau )+\\ & [\alpha {]}_1\cdot s[\delta {]}_2+u(\tau )\cdot s[\delta {]}_2+r[\delta {]}_1\cdot [\beta {]}_2+r[\delta {]}_1\cdot v(\tau )+rs[\delta {]}_1\cdot [\delta {]}_2(\mathrm{\Delta })\\ & \text{可以看到第一行就是最开始引入 }\alpha \text{ 和 }\beta \text{ 时的结果，}\\ & \text{我们把 }\mathrm{\Delta }\text{ 单独提取出来:}\\ =& [\alpha {]}_1\cdot s[\delta {]}_2+u(\tau )\cdot s[\delta {]}_2+r[\delta {]}_1\cdot [\beta {]}_2+r[\delta {]}_1\cdot v(\tau )+rs[\delta {]}_1\cdot [\delta {]}_2(\mathrm{\Delta })\\ & \text{变换一下:}\\ =& [\alpha {]}_1\cdot s[\delta {]}_2+u(\tau )\cdot s[\delta {]}_2+\widetilde{rs[\delta {]}_1\cdot [\delta {]}_2}+r[\delta {]}_1\cdot [\beta {]}_2+\\ & r[\delta {]}_1\cdot v(\tau )+\widetilde{rs[\delta {]}_1\cdot [\delta {]}_2}-\widetilde{rs[\delta {]}_1\cdot [\delta {]}_2}\\ =& ([\alpha {]}_1+u(\tau )+r[\delta {]}_1)\cdot s[\delta {]}_2+(r[\delta {]}_1)\cdot ([\beta {]}_2+v(\tau )+s[\delta {]}_2)-rs[\delta {]}_1\cdot [\delta {]}_2\\ =& s[A{]}_1\cdot [\delta {]}_2+r[\delta {]}_1\cdot [B{]}_2-rs[\delta {]}_1\cdot [\delta {]}_2\\ =& s[A{]}_1\cdot [\delta {]}_2+r[B{]}_1\cdot [\delta {]}_2-rs[\delta {]}_1\cdot [\delta {]}_2\\ =& (s[A{]}_1+r[B{]}_1-rs[\delta {]}_1)\cdot [\delta {]}_2\\ & \text{这样就得了 }[C{]}_1\text{ 的后半部分}\end{array}$$

这时候我们的验证公式：

$$\begin{array}{rl}e([A{]}_1,[B{]}_2)& =\\ & =e([\alpha ]+u(\tau )+\mathcal{r}\cdot [\delta {]}_1,[\beta ]+v(\tau )+\mathcal{s}\cdot [\delta {]}_2)\\ e([\alpha {]}_1,[\beta {]}_2)+e([X{]}_1,[\gamma {]}_2)+e([C{]}_1,[\delta {]}_2)& =\\ & =e([\alpha {]}_1,[\beta {]}_2)+e([X{]}_1,[\gamma {]}_2)+e(\sum _{i=\mathcal{l}+1}^m{a}_i[{\psi }_i{]}_1+h(\tau )t(\tau )+s[A{]}_1+r[B{]}_1-rs[\delta {]}_1,[\delta {]}_2)\end{array}$$

这时候，我们发现：

$$\begin{array}{rl}e([X{]}_1,[\gamma {]}_2)& =e(\sum _{i=1}^{\mathcal{l}}{a}_i[\frac{\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )}{\gamma }{]}_1,[\gamma {]}_2)\\ e(\sum _{i=\mathcal{l}+1}^m{a}_i[{\psi }_i{]}_1,[\delta {]}_2)& =e(\sum _{i=\mathcal{l}+1}^m{a}_i[\frac{\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )}{\delta }{]}_1,[\delta {]}_2)\\ e(h(\tau )t(\tau ),[\delta {]}_2)& =e(\sum _{i=0}^{n-2}{h}_i[\frac{t(\tau )[{\tau }^i{]}_1}{\delta }{]}_1,[\delta {]}_2)\end{array}$$

这样分母就被消掉了。

这样，我们就得到最终的Groth16

对于 $G_T$ 的加法实际上是乘法(

 

• SRS:

• • random $\to \alpha ,\beta ,\tau ,\gamma ,\delta$
• • ${\overrightarrow{SRS}}_1\to ([1{]}_1,[\tau {]}_1,[{\tau }^2{]}_1,...,[{\tau }^{m-1}{]}_1)$
• • ${\overrightarrow{SRS}}_2\to ([1{]}_2,[\tau {]}_2,[{\tau }^2{]}_2,...,[{\tau }^{m-1}{]}_2)$
• • ${\overrightarrow{SRS}}_{t(\tau )}=(\frac{(t(\tau )[1{]}_1}{\delta },\frac{(t(\tau )[\tau {]}_1}{\delta },\frac{(t(\tau )[{\tau }^2{]}_1}{\delta },...,\frac{(t(\tau )[{\tau }^{n-2}{]}_1}{\delta })$
• • $[{\psi }_i{]}_{1\to \mathcal{l}}\to [\frac{\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )}{\gamma }{]}_1$
• • $[{\psi }_i{]}_{(l+1)\to \mathcal{m}}\to [\frac{\alpha v_i(\tau )+\beta u_i(\tau )+w_i(\tau )}{\delta }{]}_1$

• Public

• • $[\alpha {]}_1,[\beta {]}_1,[\beta {]}_2,[\gamma {]}_2,[\delta {]}_1,[\delta {]}_2,{\overrightarrow{SRS}}_1,{\overrightarrow{SRS}}_2,{\overrightarrow{SRS}}_{t(\tau )},[{\psi }_i{]}_1$

• Prover

• • $[A{]}_1=[\alpha {]}_1+u(\tau )+\mathcal{r}[\delta {]}_1$
• • $[B{]}_1=[\beta {]}_1+v(\tau )+\mathcal{s}[\delta {]}_1$
• • $[B{]}_2=[\beta {]}_2+v(\tau )+\mathcal{s}[\delta {]}_2$
• • $[C{]}_1=\sum _{i=\mathcal{l}+1}^m{a}_i[{\psi }_i{]}_1+h(\tau )t(\tau )+s[A{]}_1+r[B{]}_1-rs[\delta {]}_1$

• Verifier

• • $[X{]}_1=\sum _{i=1}^{\mathcal{l}}{a}_i[{\psi }_i{]}_1$
• • $e([A{]}_1,[B{]}_2)=e([\alpha {]}_1,[\beta {]}_2)+e([X{]}_1,[\gamma {]}_2)+e([C{]}_1,[\delta {]}_2)$