• 1. 思路
• 2. Trusted Setup
  • 2.1 什么是 trusted setup
  • 2.2 例子
  • 2.3 术语
  • 2.4 信任问题
    • 2.4.1 $s$ 和 $\alpha$ 的一致性
    • 2.4.2 丢弃之前的计算结果
  • 2.5 总结
• 3. 双线性配对
• 4. 非交互式证明
• 5. 总结

前面的文章里，我们从初接触零知识证明，到了解了如何证明拥有一个多项式，最后解决了互不信任的问题，弥补了可能被利用的「空子」。现在我们有了一个很健壮的交互式的零知识证明的过程，但交互式证明有一些限制，比如：

1. 它要求 prover 一直在线
2. 每证明一次，它就要计算一次，而这个计算是非常慢的
3. verifier 在验证 proof 之前，需要一直保存着 $s$ 和 $\alpha$ ，这可能会被攻击，导致 $s$ 和 $\alpha$ 泄露
4. 交互式证明只能让某一个 verifier 信服，无法让除 prover 和 verifier 之外的第三者信服

第 4 点有些不好理解，需要解释下。verifier 虽然可以按正常流程对 prover 进行验证，通过验证后 verifier 自己是相信 prover 的。但如果 verifier 对你说「我已经验证过 prover 了，ta 没问题，相信我」时，你会相信 verifier 吗？可能不会，因为你会想「ta 俩不会是串通好了骗我的吧」。

所以要想实际使用，我们要想办法把这个过程变成非交互式的。所谓的「非交互式」，是指 prover 只生成一次 proof ，然后把 proof 公开出来，然后 prover 就可以离线了。proof 可以通过邮件、短消息等任何方式传播，任何人在任何时间拿到这个 proof ，都可以马上对其进行验证，如果验证成功，就可以相信 prover 。

1. 思路

那怎么才能做到非交互式呢？我们可以回想一下，在交互式中，每个 verifier 利用值 $s$ 和 $\alpha$ 生成加密值序列 $g^{s_i}$ 和 $g^{ {\alpha}s_i}$ 给 prover 让其进行计算，而 $s$ 和 $\alpha$ 是需要 verifier 保密的，不能泄露。那么我们可以想，如果 $s$ 和 $\alpha$ 是真正的保密的、没有被泄露的，那 $g^{s_i}$ 和 $g^{ {\alpha}s_i}$ 是不是也应该可以给别的 verifier 用？反正 $s$ 和 $\alpha$ 是真正保密的嘛，prover 不可能知道这两个值，也就不可能作弊。这个思路是没错的，但这个解决方法随之会产生两个问题。

一个问题是如何能确保 $s$ 和 $\alpha$ 是真正保密的、没有被泄露的呢？某个人产生了随机数 $s$ 和 $\alpha$ ，然后生成了加密序列 $g^{s_i}$ 和 $g^{ {\alpha}s_i}$ ，最后 ta 声称 $s$ 和 $\alpha$ 被严格保密了，决不会泄露，甚至 ta 自己都忘了这俩值是什么了。你会相信 ta 吗？大概你会持怀疑态度（一个人想要证明自己泄露了某个秘密很容易，想要证明自己没有泄露某个秘密几乎是不可能的）。

另一个问题是， 在我们之前的验证过程中，verifier 是需要 $s$ 和 $\alpha$ 对 proof 进行验证的。所以即使 $s$ 和 $\alpha$ 真的被严格保密没有泄露，但连 verifier 都不知道这俩值是什么，ta 如何去进行验证呢？

总结一下问题就是：

1. 如何确信 $s$ 和 $\alpha$ 是真正保密的、没有被泄露的
2. 验证过程是要用到 $s$ 和 $\alpha$ 的，但连 verifier 都不知道 $s$ 和 $\alpha$ 的话，ta 要如何去验证 proof

当然，这俩问题都是有解决办法的，这篇文章后面的部分，我们就来解决这俩问题。

2. Trusted Setup

2.1 什么是 trusted setup

我们先来解决第一个问题，即如何让人们都相信，$s$ 和 $\alpha$ 是真的被保密、没有被泄露的。黑帮电影里经常有一句话，叫「只有死人才不会泄露秘密」。在计算机里也是这样的，最好的保密方式就是直接把值丢掉，而不是把值保存起来然后想尽办法如何不让别人发现。

但直接把值丢掉也不解决根本上的信任问题：你说丢掉就丢掉了，我怎么信你？确实，别人的话我们没法信，但我自己总是相信我自己的吧。如果是我自己生成 $s$ 和 $\alpha$ ，然后计算生成 $g^{s_i}$ 和 $g^{ {\alpha}s_i}$ ，最后我自己把 $s$ 和 $\alpha$ 丢掉，我肯定相信 $s$ 和 $\alpha$ 没有被泄露，并且真的被丢掉了。

每个人都会这个想，每个人都 100% 相信自己，那有没有一种办法，让大家去计算加密同一个东西，只要相信至少其中一个人把 $s$ 和 $\alpha$ 保密并且丢弃了（这个令你相信的「其中一个人」肯定是你自己），就可以相信没有人可以得到原始的 $s$ 和 $\alpha$ 了呢？当然有的，这就是 trusted setup 的基本思想。

trusted setup 的思路就是，每个人在别人生成的 $g^{s^i}$ 和 $g^{ {\alpha}s^i}$ 的基础之上进行加密运算，只要有一个人不泄露自己的 $s$ 和 $\alpha$ ，生成的 $g^{s^i}$ 和 $g^{ {\alpha}s^i}$ 就是可信的，prover 就无法知道原始的 $s$ 和 $\alpha$ 。这么说可能还是会令你迷惑，看一个例子就马上明白了。

2.2 例子

假设现在有 Alice 、Bob 、Carol 三个人，ta 们要合作生成一串加密值，ta 们的做法是（注意下面所有的 A 、B、C 都是下标，页面渲染效果不太好，很容易搞错；比如 $g^{\alpha_A}$ 的指数部分代表的是有下标 A 的 alpha ）：

1. Alice 生成随机数 $s_A$ 和 ${\alpha}_A$ ，然后计算得到 $(g^{ {\alpha}_A}, g^{ {s_A}^i}, g^{ {\alpha}_A{s_A}^i})$ ，然后丢弃 $s_A$ 和 ${\alpha}_A$
2. Bob 生成随机数 $s_B$ 和 ${\alpha}_B$ ，然后在 Alice 计算的基础上继续计算： $({(g^{ {\alpha}_A})}^{ {\alpha}_B}, {(g^{ {s_A}^i})}^{ {s_B}^i}, {(g^{ {\alpha}_A{s_A}^i})}^{ { {\alpha}_B}{s_B}^i})$ ，即 $(g^{ {\alpha}_A{\alpha}_B}, g^{({s_As_B})^i}, g^{ {\alpha}_A{\alpha}_B{(s_As_B)}^i})$ ，然后丢弃 $s_B$ 和 ${\alpha}_B$
3. Carol 生成随机数 $s_C$ 和 ${\alpha}_C$ ，然后在 Bob 计算的基础上继续计算：$({(g^{ {\alpha}_A{\alpha}_B})}^{ {\alpha}_C}, {(g^{({s_As_B})^i})}^{ {s_C}^i}, {(g^{ {\alpha}_A{\alpha}_B{(s_As_B)}^i})}^{ {\alpha}_C{s_C}^i})$ ，即 $(g^{ {\alpha}_A{\alpha}_B{\alpha}_C}, g^{ {(s_As_Bs_C)}^i}, g^{ {\alpha}_A{\alpha}_B{\alpha}_C{(s_As_Bs_C)}^i})$

可以看到，如果令 $s=s_As_Bs_C$, $\alpha={\alpha}_A{\alpha}_B{\alpha}_C$ ，那么Carol 最终产生的 $(g^{ {\alpha}_A{\alpha}_B{\alpha}_C}, g^{ {(s_As_Bs_C)}^i}, g^{ {\alpha}_A{\alpha}_B{\alpha}_C{(s_As_Bs_C)}^i})$ 正是 $g^{\alpha}, g^{s^i}, g^{ {\alpha}s^i}$ 。但只要至少有一个人、比如 Alice 把 $s_A$ 和 ${\alpha}_A$ 保密并丢弃了，那么即使 Bob 和 Carol 泄露它们的 $s$ 和 $\alpha$ ，也没人能计算出来最终的 $s_As_Bs_C$ 和 ${\alpha}_A{\alpha}_B{\alpha}_C$ ，因此最终的 $s$ 和 $\alpha$ 依然是保密的。

这就是一个简单的 trusted setup 的过程，这个过程可以一直重覆做下去，感兴趣的人都可以参与。如果你想确保最终 trusted setup 结果的可信性，你就可以亲自参与计算一下，然后立即把自己的 $s$ 和 $\alpha$ 丢弃。这样你就可以相信，没有人会知道最终的 $s$ 和 $\alpha$ 了。

2.3 术语

上面的例子里，最终产生的 $(g^{ {\alpha}_A{\alpha}_B{\alpha}_C}, g^{ {(s_As_Bs_C)}^i}, g^{ {\alpha}_A{\alpha}_B{\alpha}_C{(s_As_Bs_C)}^i})$, $i\in{0…d}$ （其中 $d$ 是多项式的高幂值 ），就是所谓的 CRS （common reference string）。

有时候，trusted setup 也被叫做 CRS setup ；有时候也叫做 ceremony 。

2.4 信任问题

上面的例子中其实隐含了一个假设，即所有参与的人都会老老实实去计算。但现实世界（尤其是区块链世界）充满了不信任，只要有漏洞，别人就有理由去怀疑数据是否可信。上面的例子中有两个问题：

1. 参与计算的人可能捣乱，ta 可能使用不同的 $s$ 或 $\alpha$ 去进行计算（比如使用 $s$ 计算 $g^{s^i}$ ，却使用 $s’$ 计算 $g^{s^{i+1}}$）；或者不按规则去进行计算（比如本来要进行指数运算，ta 却做了个乘法运算，把生成的 $s$ 乘在了原来数据上）。这样一来经过 ta 计算出的结果是无法应用于我们前面介绍的零知识证明的验证过程的。
2. 参与计算的人可能直接丢弃之前的计算结果，自己从头重新计算，那之前的人就都白忙活了。比如上面例子中 Carol 作为最后一个参与计算的人，ta 完全可以不使用 Bob 产生的结果，直接自己像 Alice 那样从头计算。这样一来，最终的 $s$ 和 $\alpha$ 就是 Carol 的 $s_C$ 和 ${\alpha}_C$ ，显然 Carol 拥有了最终秘密。

解决这两个问题，我们都要用到双线性配对。我们一个一个来解决。

双线性配对将在下一小节进行介绍，这里你只要记住，双线性配对的表示方式为 $e(x,y)$ ，并且它有一个性质，就是 $e(g^a,g^b)={e(g,g)}^{ab}$ ，就可以了。

2.4.1 $s$ 和 $\alpha$ 的一致性

第一个问题是参与计算的人可能用不同的 $s$ 和 $\alpha$ 进行计算，或不进行指数运算。很自然的，我们可以想到解决方法就是把这个人的计算结果进行逐个验证，看是否是用相同的值、按预期的运算方式进行计算。我们先来验证 $s$ ，再来验证 $\alpha$ 。

刚才我们提到对结果进行逐个验证，也就是看 $g^{s^i}={(g^{s^{i-1}})}^s$ 是否成立，但我们不可能知道 $s$ 的具体值，所以是无法直接这么验证的。但别忘了我们有双线性配对，可以在加密域上进行验证，所以验证方式就变成以下等式（等式中使用到的 $g$ 是公开的、所有人都知道的）： \(e(g^{s^i},g)=e(g^{s^1}, g^{s^{i-1}}), i\in\{2,...,d\}\) 这个等式中，所有用到的值都是已知的，并且根据双线性配对的性质可以知道，这个等式就等价于 $e(g,g)^{s^i}=e(g,g)^{s^1s^{i-1}}$ ，很显然可以验证 $s$ 的一致性，同时也可以验证进行的是指数运算。

下面我们再来验证 $\alpha$ 的一致性。与 $s$ 的验证类似，我们也只能能过双线性配对来进行验证： \(e(g^{s^i},g^{\alpha})=e(g^{ {\alpha}s^i},g), i\in\{1,...,d\}\) 这个也很好理解，就不多说了。

回到我们上面的例子中，Carol 要如何验证 Bob 是否使用了一致的 $s$ 和 $\alpha$ 呢？ ta 需要这样验证 $s$ ： \(e(g^{(s_As_B)^i},g)=e(g^{s_As_B},g^{(s_As_B)^{i-1}})\) 也需要这样验证 $\alpha$ ： \(e(g^{ {(s_As_B)}^i},g^{ {\alpha}_A{\alpha}_B})=e(g^{ {\alpha}_A{\alpha}_B{(s_As_B)}^i},g)\) 全部通过验证， Carol 就可以确认，Bob 并没有捣乱。

2.4.2 丢弃之前的计算结果

第二个问题是，参与计算的人可能会丢弃之前人的计算结果，直接自己从头开始计算，尤其是最后一个人非常有动机这样做。那要如何避免这种作恶方式呢？我们需要一种方法，来验证当前这个人的计算确实是基于前一个人的结果进行的。

比如在前面的例子中，Alice 产生的数据是 $(g^{ {\alpha}_A}, g^{ {s_A}^i}, g^{ {\alpha}_A{s_A}^i})$ 。假设 Bob 使用自己的随机数 $s_B$ 和 ${\alpha}_B$ 参与运算后，产生的数据记为 $(g^{\alpha}, g^{s^i}, g^{ {\alpha}s^i})$ 。如果 Carol 要相信 Bob 诚实的做了计算，Carol 需要验证：

可以看到，如果要验证以上三个等式成立，Carol 需要知道 ${\alpha}_B$ 、${s_B}^i$ ，但这正是 Bob 要保密的东西，不可能让别人知道。不过明文的 ${\alpha}_B$ 、$s_B$ 不能公开，加密后的肯定是可以的。所以我们可以换个思路，让 Bob 公开 $(g^{ {\alpha}_B}, g^{ {s_B}^i}, g^{ {\alpha}_B{s_B}^i})$ 。虽然这样公开数据后，Carol 仍然无法直接利用刚才的三个等式进行验证，但使用双线性配对是可以验证的：

所以，解决这个问题的办法是，让参与的人除了生成要计算的值 ，还要把自己的随机数（如 $s_B$ 和 ${\alpha}_B$ ）加密后公开出来（如 $(g^{ {\alpha}_B}, g^{ {s_B}^i}, g^{ {\alpha}_B{s_B}^i})$ ） 。这样一来，别人就可以通过使用双线性配对的方式对结果进行验证，完美解决了我们的验证问题。

2.5 总结

总得来说，trusted setup 就是一个让每个人都可以参与的计算方式，特点就是你可以相信只要至少 有一个人保守了秘密，最终的计算结果就是加密的、不能被别人破解的；而通常这个可以让你相信的人就是你自己。

在进行 trusted setup 过程中，每个人基于前一个人的计算。我们假设当前要参与计算的人是 C ，ta 之前的人是 B ，B 之前的人是 A 。所以 C 的具体过程为（随着零知识证明过程变得更复杂，会需要更多的随机数，但道理都是一样的，这里我们只使用 $s$ 和 $\alpha$ 进行说明）：

1. 验证前一个人 B 的 $s$ 和 $\alpha$ 的一致性：
   \(\begin{align}e(g^{s_B^i},g)&=e(g^{s_B},g^{s_B^{i-1}})\\e(g^{ {s_B}^i},g^{ {\alpha}_B})&=e(g^{ {\alpha}_B{s_B}^i},g)\end{align}\)
2. 利用前一个人 B 的加密后的公开数据 $(g^{ {\alpha}_B}, g^{s_B^i}, g^{ {\alpha}_Bs_B^i})$ ，验证 B 是在 A 产生的数据的基础上进行的计算（不带下标的 $s$ 和 $\alpha$ 代表的是 B 计算完成后产生的值，即 $s=s_As_B, \alpha={\alpha}_A{\alpha}_B$）：
   \(\begin{align} e(g^{\alpha}, g)&=e(g^{ {\alpha}_A}, g^{ {\alpha}_B})\\ e(g^{s^i}, g)&=e(g^{ {s_A}^i},g^{ {s_B}^i})\\ e(g^{ {\alpha}s^i},g)&=e(g^{ {\alpha}_A{ {s_A}}^i},g^{ {\alpha}_B{s_B}^i}) \end{align}\)
3. 产生随机的 $s_C$ 和 ${\alpha}_C$
4. 在 B 的基本上，计算得出一系列的值 $(g^{\alpha}, g^{s^i}, g^{ {\alpha}s^i})$ 和 $(g^{ {\alpha}_C}, g^{s. C^i}, g^{ {\alpha}_Cs_C^i})$ ，其中 $i\in{0,…,d}$ ， $d$ 是多项式需要的最大维度（实际情况中这个值通常不会根据某个多项式来确定，而是定得相对大一些，这样适用范围更广）。

3. 双线性配对

接下来我们解决第二个问题，即我们已经通过 trusted setup 将 $s$ 和 $\alpha$ 加密了，现在没人知道它们的值是什么了，包括 verifier 也不知道。但在我们之前的验证过程中，verifier 是需要这两个值的明文进行验证的，现在没有这俩值的明文了，verifier 要如何验证呢？

首先想到的是，能不能使用加密后的值进行验证，因为同态加密不就是支持加密后运算吗？不幸的是，还真不行。我们先把上一篇文章中 verifier 最终的验证等式拷贝过来，即 verifier 要：

1. 验证 \({(E'_f)}^{\alpha}=E'_{f'}\) 。即 ${({(g^f)}^\delta)}^{\alpha}={(g^{ {\alpha}f})}^\delta$
2. 验证 \({(E'_h)}^{\alpha}=E'_{h'}\) 。即 ${({(g^h)}^\delta)}^{\alpha}={(g^{ {\alpha}h})}^\delta$
3. 验证：$E’_f={(E’_h)}^t$ 。即 ${(g^f)}^\delta={({(g^h)}^\delta)}^t$

可以看到如果把 $\alpha$ 变成了 $g^{\alpha}$ ，那么 ${({(g^f)}^\delta)}^{g^{\alpha}}={(g^{ {g^{\alpha}}f})}^\delta$ 这个等式无论如何也不会成立的；同样的把 $s$ 变成 $g^{s^i}$ 的话，$t$ 就变成了 $g^t$ ，${(g^f)}^\delta={({(g^h)}^\delta)}^{g^t}$ 也是无论如何不会成立的。

同态加密只支持一个未加密的值和加密值的乘法运算；但不支持两个加密值的乘法运算，以及两个值的指数运算。 这里所谓的「支持」是指，有一种方法可以对加密后的值进行运算，这也是同态加密的特点。比如

1. 对于 \(a\times b\) ，如果只对 $b$ 加密变成了 $b’=g^b$ ，那么在加密域可以通过 ${(b’)}^a$ 的方式计算，并通过 $g^{ab}={(b’)}^a$ 的方式验证。
2. 对于 \(a\times b\) ，如果对 $a$ 和 $b$ 都加密变成了 $a’=g^a$ ，$b’=g^b$ ，那么是找不到一种运算 $\cdot$ ，可以让 $g^{ab}=a’{\cdot}b’$ 成立的。
3. 对于 $a^b$ ，无论是同时对 $a$ 和 $b$ 加密（ $a’=g^a$ ，$b’=g^b$ ），还是只对其中一个值加密，都是找不到一种运算 $\cdot$ ，可以让加密后的值可验证成立。

既然同态加密不支持这种运算，我们只能另想办法。幸运的是，双线性配对（或叫双线性映射）正好支持这种运算。

这里我们不会介绍双线性配对的详细理论，只介绍一下它有什么性质，我们如何在零知识证明中使用它就可以了。

所谓的双线性配对，其实是一种运算，用 \(e(g^*, g^*)\) 表示。 这里我们只需要记住我们要用到的它的重要性质就行了，其中最重要的是以下等式：

另一个重要的性质是，经过双线性配对计算生成的值，不能再参与双线性配对的计算。即你不能做这样的运算：$e(e(g^a,g^b), g)$ 。这是因为，双线性配对利用了椭圆区线来实现这些性质，而输入和输出不在同一个椭圆曲线上（相当于输入集合和输出集合不相交），因此把输入再次当作输入时，算法会发现输入值不在集合范围内。这一性质是零知识证明安全的保证，后面我们还会提到。

既然双线性配对利用的是椭圆曲线，那么 \(e(g^*,g^*)\) 中的 $g$ 就是椭圆曲线的生成元（generator point）。所以以后出现的 $g$ 我们都会把它作为「椭圆曲线生成元」来理解（不过多数情况下对于理解零知识证明来说，也没啥区别）。

椭圆曲线相信大家或多或少都听说过，这里不需要比「听说过」知道更多的关于椭圆曲线的知识，但我们要简单解释一下所谓的生成元，你可以理解为椭圆区线的单位元素，所有的值都是经由这个「元值」生成的。举个例子，比如正整数里单位元素是 1 ，就相当于一个「生成元」，所有的正整数都是加 1 得到的。

在论文或很多正式的文章里，通常使用 $e:\mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ 来表示双线性配对，用 $[g]_1$ 表示 $\mathbb{G}_1$ 的生成元；椭圆区线上的点 $x$ 也可能会用 $[x]$ 或 $x\cdot{g_1}$ 来表示，比如 $[x]_1$ 表示 $\mathbb{G}_1$ 上的点。但为了好理解，我们后面的文章仍然多数情况下使用 $g^x$ 这种表示方式。

现在有了双线性配对，我们就可以使用加密的 $g^s$ 和 $g^{\alpha}$ 进行验证了：

1. 原来是验证 \({(E'_f)}^{\alpha}=E'_{f'}\) ，即 ${({(g^f)}^\delta)}^{\alpha}={(g^{ {\alpha}f})}^\delta$ ；变为验证 \(e(E'_f, g^{\alpha})=e(E'_{f'}, g)\), 即 $e({(g^f)}^{\delta}, g^{\alpha})=e({(g^{ {\alpha}f})^{\delta}}, g)$，它们都等于 $e(g,g)^{ {\alpha}f{\delta}}$
2. 原来是验证 \({(E'_h)}^{\alpha}=E'_{h'}\) 。即 ${({(g^h)}^\delta)}^{\alpha}={(g^{ {\alpha}h})}^\delta$；变为验证 \(e(E'_h, g^{\alpha})=e(E'_{h'},g)\)，即 $e({(g^h)}^{\delta}, g^{\alpha})=e({(g^{ {\alpha}h})}^{\delta}, g)$，它们都等于 $e(g,g)^{ {\alpha}h{\delta}}$
3. 原来是验证：$E’_f={(E’_h)}^t$ 。即 ${(g^f)}^\delta={({(g^h)}^\delta)}^t$；变为验证 $e(E’_f,g)=e(E’_h,g^t)$，即 $e({(g^f)}^{\delta},g)=e({(g^h)}^{\delta}, g^t)$ ，即 $e(g,g)^{f{\delta}}=e(g,g)^{ht{\delta}}$

第 3 步中，由于 $s$ 被加密了，所以 verifier 也只能和 prover 那样，计算多项式 $t(x)$ 加密后的值，即 $g^t$

4. 非交互式证明

现在，我们有了可以令每个人信服的加密 $s$ 和 $\alpha$ 的方式，也可以用双线性配对使用加密后的 $s$ 和 $\alpha$ 对 prover 进行验证，从而将原来的交互式证明修改为非交互式：

setup:

1. prover 知道多项式 $f(x)$, $h(x)$, $t(x)$
2. verifier 知道多项式 $t(x)$
3. 多方参与 trusted setup ，得到 $(g^{\alpha}, g^{s^i}, g^{ {\alpha}s^i})$ ，其中 $i\in{0,…,d}$
4. 由于 $(g^{s^i}, g^{ {\alpha}s^i})$ 由 prover 用到，所以我们可以把它们称为 proving key.
5. 使用 $g^{s^i}$ 计算 $g^t$ ，所以得到 verification key: $(g^{\alpha},g^t)$

prover:

1. 使用 proving key 中的 $g^{s^i}$ 计算：
   \(\begin{align} E_f&=(g^{s^n})^{a_n}(g^{s^{n-1}})^{a_{n-1}}...(g^{s^1})^{a_1}g^{a_0}=g^f\\ E_h&=g^h \end{align}\)
2. 同样使用 proving key 中的 $g^{ {\alpha}s^i}$ 计算 ：
   \(\begin{align} E_{f'}&={(g^{ {\alpha}s^n})}^{a_n}{(g^{ {\alpha}s^{n-1}})}^{a_{n-1}}...{(g^{ {\alpha}s^1})}^{a_1}{(g^{\alpha})}^{a_0}={({(g^{s^n})}^{a_n}{(g^{s^{n-1}})}^{a_{n-1}}...{(g^{s^1})}^{a_1}g^{a_0})}^{\alpha}={g^f}^\alpha=g^{ {\alpha}f}\\ E_{h'}&=g^{ {\alpha}h} \end{align}\)
3. 取随机数 $\delta$ ，分别加密 $(E_f, E_{f’}, E_h, E_{h’})$ ，得到：
   \(\begin{align} E'_f&={(E_f)}^\delta\\ E'_{f'}&={(E_{f'})}^\delta\\ E'_h&={(E_h)}^\delta\\ E'_{h'}&={(E_{h'})}^\delta\\ \end{align}\)
4. 将计算得出的值 \(({E'_f}, E'_{f'}, E'_h, E'_{h'})\) 传回给 verifier.

verifier: 使用 verification key $(g^{\alpha}, g^t)$ 进行如下验证：

1. 验证 \(e(E'_f, g^{\alpha})=e(E'_{f'}, g)\), 即 $e({(g^f)}^{\delta}, g^{\alpha})=e({(g^{ {\alpha}f})^{\delta}}, g)$ （它们都等于 $e(g,g)^{ {\alpha}f{\delta}}$）
2. 验证 \(e(E'_h, g^{\alpha})=e(E'_{h'},g)\)，即 $e({(g^h)}^{\delta}, g^{\alpha})=e({(g^{ {\alpha}h})}^{\delta}, g)$，（它们都等于 $e(g,g)^{ {\alpha}h{\delta}}$）
3. 验证 $e(E’_f,g)=e(E’_h,g^t)$，即 $e({(g^f)}^{\delta},g)=e({(g^h)}^{\delta}, g^t)$ ，即 $e(g,g)^{f{\delta}}=e(g,g)^{ht{\delta}}$

看出来这里与交互式证明的区别了么？由于 trusted setup 是一个提前的步步骤，是提交产生好的、所有人都知道的，所以：

1. prover 不用再等着 verifier 提交证明请求才能产生证明了，ta 可以随时拿 proving key 来用于产生证明
2. prover 产生的证明，也不再是只有当初提交证明请求的那个 verifier 才能验证了，而是每个人都可以验证，因为每个人都可以拿到 verification key ，每个人也都相信 trusted setup 的过程

可以看到，verifier 现在使用的值都是 trusted setup 阶段产生的 verification key ，ta 自己本身已经不知道任何秘密了。

verfier 使用双线性配对进行验证是可信的一个重要原因，是我们前面提到的双线性配对的一个性质，即双线性配对计算得出来的值，不能再次作为双线性配对的输入值。如果没有这个性质的限制的话，prover 依然可以作弊：ta 使用 $g^{s^i}$ 计算得到 $E_f=g^f$ 后，并不需要再老老实实的使用 $g^{ {\alpha}s^i}$ 计算 $E_{f’}=g^{ {\alpha}f}$ ，而只需要令 $E_{f’}=g^{f’}=e(g^f,g)$ ；然后 verifier 验证 \(e(E'_f, g^{\alpha})=e(E'_{f'},g)\) 时仍然可以通过验证，因为上式中将 $E_{f’}=e(g^f,g)$ 代入后，就等于 $e({e(g^f,g)}^{\delta},g^{\alpha})=e({(g^{ {\alpha}f})}^{\delta},g)$ ，显然这个等式是成立的。（幸运的是，双线性配对并不允许这么做）

5. 总结

这篇文章里，我们把之前的交互式证明改进成了非交互式的。这种转变就要用到了 trusted setup 和双性线配对。

至此，我们拥有了一个非常健壮的非交互式零知识证明的过程（而我们只用了 5 篇文章就做到了，真是太棒了）。但目前为止，我们都是假设我们已经拥有了一个多项式，然后直接就开始了证明。但如何拥有一个多项式，或者说如何把要证明的问题等价转换成一个多项式，我们还一点也没涉及到。不过别着急，这正是我们后面的文章要解决的事情。