上一篇文章中我们提到零知识证明的精髓是 $f(x)=h(x)t(x)$ ，但直接使用那个证明和验证流程，漏洞百出：
- 虽然 $s$ 是 verifier 随机选择的一个值，prover 无法预测。但 prover 拿到 $s$ 值后，它就可以知道 verifier 将会计算出的 $t(s)$ 的值是多少；prover 根据 $t(s)$ 值，动态调整 $f(x)$ 和 $h(x)$ ，最终得到两个新的多项式并将 $s$ 代入后计算出值发给 verifier ，verifier 依然可以通过验证。
- prover 拿到 $s$ 后，甚至不用有多项式，随机选择两个值 $m$ 和 $n$ ，只要 $m = nt(s)$ 成立就可以了。
这些问题的根本原因是 prover 知道 $s$ 的值是多少。如果 prover 不知道 $s$ 的值， ta 就不会知道 verifier 计算出来的 $t(s)$ 值是多少，从而也就无法胡乱构造两个数来糊弄 verifier 了。
如何让 prover 无法知道 $s$ 呢？我们需要一个办法可以加密随机数 $s$ ，既可以向 prover 隐藏这个值，又可以让 prover 使用这个值进行计算；同时还可以让 verifier 使用 $s$ （或加密后的 $s$）进行验证。
有办法能实现这个目标吗？有的，那就是同态加密。
1. 同态加密
维基百科上对同态加密的定义如下：
同态加密（英语：Homomorphic encryption）是一种加密形式，它允许人们对密文进行特定形式的代数运算得到仍然是加密的结果，将其解密所得到的结果与对明文进行同样的运算结果一样。换言之，这项技术令人们可以在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无需对数据进行解密。其意义在于，真正从根本上解决将数据及其操作委托给第三方时的保密问题，例如对于各种云计算的应用。
可以看到同态加密有一个非常有个性的特点：可以直接操作加密后的数据，无需先对数据进行解密再操作。也就是说，同态加密可以基于密文进行运算，且与明文运算得到的结果是一样的。例如有三个数值 $a$ 、$b$ 和 $c$ ，加密前它们的关系是 $a+b=c$ ；使用某个同态加密算法 $E$ 和特定形式的运算 $\oplus$ ，那么 $E(a) \oplus E(b)=E(c)$ 依然是一定成立的。
同态加密的算法有很多，有加法同态，乘法同态，全同态，但这里我们就不详细介绍了，只介绍最简单的一种，我们的目的，还是为了理解零知识证明。
比如我们选择一个基数 $g$ ，那么可以定义一个同态加密算法 $E(x)=g^x$ 。假设 $g=10$ 的话，那么 $E(1)=10$ ，$E(2)=100$ ，$E(x)=10^x$ 。
那么如何使用这个同态加密算法进行运算呢？比如你想将 $x$ 乘以一个常数 $a$ ，那么 $E(ax)={E(x)}^a=(g^x)^a=g^{ax}$ ；你想将 $x$ 加上一个值 $y$ ，那么 $E(x+y)=E(x)E(y)=g^xg^y=g^{x+y}$ 。
但由于我们选择的基数 $g$ 和算法是必须公开的，所以在知道基数的情况下，很容易反推出加密前的值是什么：比如告诉你基数是 10 ，加密算法是 $E(x)=10^x$ ，加密后的值是 100 ，你很容易推算出来加密前的值是 2 。那怎么解决这个问题呢？这里非常巧妙的使用了取模运算。
2. 取模运算
严格来说，零知识证明中的取模运算是因为用到的一些算法只能在有限域上进行，所以只能取模；至于是不是有防止别人反推加密前的值的目的，我目前也不知道……
作为程序员，取模运算肯定很熟悉，在程序中我们通常用来确保一个值在某个范围内，比如在某数组有效索引的范围内。这里我们也可以利用取模运算，把同态加密的值限制在某个范围内（这通常叫做有限域），比如对于上面介绍的同态加密算法，我们可以改成 $E(x)=g^x\ mod\ p$ ，其中 $p$ 就是我们的模数。
如此一来，即使基数 $g$ 、算法 和 $p$ 的值全公开，别人也无法推算出加密之前的值。比如还是上面的例子，基数是 10 ，模数 $p=6$，加密算法是 $E(x)=10^x\ mod \ 6$ ，加密后的值是 4 。你无法推算出来加密前的值是 1 还是 2 还是其它值，因为有很多值可以得到加密值 4 。
这里你可能有一个疑惑，就是在零知识证明的过程中，我们肯定不是只使用一次同态加密算法 $E$ 进行计算，那如果使用多次的话，每次都把计算出来的值取模了，然后再参与别的运算，那算出来的值还是正确的吗？
别担心，答案当然是正确的。因为取模运算有一个性质，就是对于加、减、乘、指数这些运算（注意没有除法），先运算再取模与先取模再运算，结果是一样的：
\[\begin{align} (a+b)\ mod\ p &= (a\ mod\ p + b \ mod \ p)\ mod\ p \\ (a-b)\ mod\ p &= (a\ mod\ p - b \ mod \ p)\ mod\ p \\ (a*b)\ mod\ p &= (a\ mod\ p * b \ mod \ p)\ mod\ p \\ (a^b)\ mod\ p &= ((a\ mod\ p) ^ b)\ mod\ p \end{align}\]3. 加密后 prover 的计算
有了同态加密和取模运算，就可以解决文章开头提出来的问题了：让 prover 不知道 $s$ 值。首先，prover 使用同态加密对 $h(x)$ 和 $f(x)$ 进行计算，例如对于 $f(x)$（注意下式中的 $x$ 是未加密的值）：
\[E(f(x))=g^{f(x)}=g^{a_nx^n+a_{n-1}x^{n-1}+...+a_1x^1+a_0}={(g^{x^n})}^{a_n}{(g^{x^{n-1}})}^{a_{n-1}}...{(g^{x^1})}^{a_1}g^{a_0}\]等等，这里有一个问题。上面等式最右边用到了类似 $g^{x^n}$ 这样的值，但 verifier 产生随机数 $s$ 并使用同态加密后，给到 prover 的是 $r=g^s\ mod\ p$ 这样的值，prover 是无法用 $r$ 计算出 $g^{x^n}$ 这样的值的（注意这里是 $(g)^{x^n}$ 而不是 $(g^x)^n$）。
产生这个问题的原因，是因为我们的同态加密不支持对加密值进行指数运算。那怎么解决这个问题呢？很简单，verifier 知道未加密的 $s$ 值嘛，那让 verifier 生成加密值的时候，不要只生成 $g^s$ ，顺带着把 $g^{s^n}$ 这样的值也生成了一起给 prover 不就可以了嘛。如此一来，verifier 需要生成并给 prover 的值有： \(g^{s^n}, g^{s^{n-1}}, ..., g^{s}, g\) 然后 prover 在计算 $E(f(x))$ 和 $E(h(x))$ 时，只要从 verifier 中选择相应的 $g^{s^i}$ 值进行计算就可以了，不用自己计算了。
4. 加密后 prover 就不能计算 $t(s)$ 了吗
你可能会有个疑问，反正 verifier 验证时都是验证 $f(x)=h(x)t(x)$ ，prover 知道这一点，并且它也知道 $t(x)$ 是什么，那你即使把给 prover 的 $s$ 加密了，prover 不一样可以用加密后的 $s$ 来计算 $E(t(s))$ 吗？那 ta 不一样可以随便生成两个数 $m$ 和 $n$ ，只要让 $m=nE(t(s))$ 不就行了？
产生这个疑问的原因可能是认为 verifier 还是简单进行 $E(f(s))=E(h(s)E(t(s))$ 这样的验证。但是其实不是的，verifier 当然需要使用同态加密进行验证，但 ta 使用 $t(s)$ 时，用的却是未加密的值。所以 prover 虽然可以计算 $E(t(s))$ ，但 ta 不知道未加密的值是什么，也就无法推测出 verifier 使用什么值进行验证了。
具体来说，verifier 需要使用同态加密进行验证，所以 ta 的验证等式应该是： \(g^{f(s)}=g^{h(s)t(s)}\) 但 ta 使用的又是未加密的 $t(s)$ 值，所以上成的等式需要变换成： \(g^{f(s)}={(g^{h(s)})}^{t(s)}\) 其中 $g^{f(s)}$ 就是 prover 计算出来的 $E(f(s))$ ，$g^{h(s)}$ 就是 prover 计算出来的 $E(h(s))$ 。
5. 最终的验证过程
最后，我们总结一下 prover 和 verifier 的验证过程：
前提:
- prover 知道多项式 $f(x)$, $h(x)$, $t(x)$
- verifier 知道多项式 $t(x)$
verifier:
- verifier 生成一个随机数 $s$
- 计算 $s$ 的所有 $i$ 次方的加密值：$E(s^i)=g^{s^i}$ ，$i\in{0,1,…,n}$，$n$ 为多项式的最高次幂。
- 把所有 $E(s^i)$ 传给 prover
prover:
- 接收 $E(s^i)=g^{s^i}$， $i\in{0,1,…,n}$
- 计算使用接收到的值计算 $E(f(s))=(g^{s^n})^{a_n}(g^{s^{n-1}})^{a_{n-1}}…(g^{s^1})^{a_1}g^{a_0}=g^{f(s)}$
- 同样的使用接收到的值计算 $E(h(s))=g^{h(s)}$
- 将计算得出的值 $g^{f(s)}$ 和 $g^{h(s)}$ 传回给 verifier.
verifier:
- 使用未加密的值计算 $t(s)$
- 验证：$g^{f(s)}={(g^{h(s)})}^{t(s)}$ ，即 $g^{f(s)}=g^{h(s)t(s)}$
6. 总结
这篇文章里，我们解决了一个大问题，就是如何让 prover 猜不出 verifier 计算出来的 $t(s)$ 值，从而逼迫 prover 老老实实的计算。解决的方法，就是使用同态加密。
但是仅仅这样就可以让 prover 老老实实计算了吗？未必，prover 还是有漏洞可钻的，具体是什么，我们下篇再说。