我不告诉你答案，你怎么知道我知道答案

你问我一个问题，如果我给你正确答案，你给我付一笔费用。但是，我不能直接告诉你答案，因为，如果我告诉了你答案，你可能不付费。

对于这种两难场景，怎么解决？

这种解决办法就是密码学中的零知识证明。

今天，我就用一个简单的例子，以浅显易懂的方式，以手稿的形式和大家分享零知识证明。

假设我们生活在一个非常原始的社会，算术就是一种很高深的学问，没有几个人懂。我是当时的一个算术家，别人有算术问题都会来付费问我。

这时，你有一个算术问题问我：3x5=?

我当然知道答案，3x5=15，但是由于我担心你知道我给你答案后不付费，所以，我不能直接告诉你答案，而是通过零知识证明来向你证明我确实知道答案。你验证证明之后，付费给我。那么我才会告诉你答案。

那我们看零知识证明是如何工作来解决这个两难问题的。

首先，如上图，把3x5=15，表示成计算机的门电路的形式。为了通用性的说明，用代数的形式再画一遍门电路，这时，a1=3，a2=5，a3=15。

进一步，把左边的输入想象成一个多项式A(x)，右边的输入为一个多项式B(x)，输出为另一个多项式C(x)，整个这个乘法门电路，用P(x)来表达。这个就是零知识证明神奇的地方，最早想到这个的人，真是天才！怎么神奇，听慢慢道来。

既然P(x)是一个多项式，那么总可以让x等于某个数，这时P(x)=0。由于P(x)是一个开放的多项式，那么不妨设x=1时，P(x)=0。当然，你也可以设x=2时，P(x)=0，自由选择。

如上图，使用x=1，P(x)=0。由于A1(x), A2(x), A3(x), B1(x), B2(x), B3(x), C1(x), C2(x), C3(x)都是开放多项式。那么，假定如上图， A1(1)=1, B2(1)=1, C3(1)=1，其它的都为0。

这时，神奇的事情就发生了，P(1)=A(1)xB(1)-C(1)=a1xa2-a3=0。

啊哈，这就是要证明问题的答案。

a1xa2=a3

即

3x5=15

问题的答案包含在了多项式的系数中了！！！

问题的证明变成了只要证明这个多项式P(x)在x=1时，P(x)=0！！！

那么，这个多项式是什么呢？

为了满足以上条件，假设为最低阶的一次多项式。

分别求出：

A(x)=23x-20

B(x)=23x-18

C(x)=23x-8

接着可以算出P(x)：

由于P(x)有1这个零根，所以可以分解成h(x)*t(x)的形式，并设t(x)=x-1，那么h(x)=529x-368。如下图。

到此，问题就变成了：

我如果知道3x5=15，那么我就必须能推出这个多项式，那么我就要向你证明我知道这个多项式P(x)=h(x)*t(x)=(529x-368)*(x-1)！这个多项式有x=1这个零根！

怎么证明我知道这个多项式？

有x=1这个零根，双方都知道，因为需要靠它来验证！那么，可以验证当x等于别的值时，P(x)是不是正确？假设你设x=2，这时，如下图。

这时，你（图中角色B），计算出t(2)=2-1=1, P(2)=690。你把P(2)的值保留，告诉我（图中角色A）x=2，t(2)=1，让我计算h(2)且把结果告诉你。你拿到h(2)，就可以检查h(2)*t(2)是不是等于你保留的P(2)。如果等于，证明我知道这个P(x)多项式，证明我知道3x5=15！

零知识问题到此就基本解决了，当然，其中有些安全漏洞的问题，就需要用传统的密码学，离散对数算法，和同态加密算法来解决了。

比如，你告诉我的是明文的x=2，t(2)=1，这时我可能能通过这些明文猜出h(2)，而不是通过计算h(x)来得到h(2)。这时，你可以加密那些明文，比如2变成E(2)，t(2)变成E(t(2))，x^r变成E(x^r)（r=0,1,...)，然后你把这些加密数值告诉我，我根据加密数值，计算出E(h(2))，传给你，你就可以使用同态加密算法验证E(h(2))*E(t(2))=E(p(2))。

以上是假定你知道多项式P(x)，能算出x等于任何值时的P(x)，比如P(2)。但是，现实的情况是你不知道P(x)，只知道t(x)，因为有哪些零根是双方都知道的验证点。

这时，你可以对原来的加密数值进行“偏移”，然后再将偏移后的数值加密，将原数值的密文和原数值偏移后加密的密文都发送给我，我需要在这两个密文上进行同样的操作，你在收到结果后可以检查两个结果之间是否还是存在原先的偏移量。这种方法称为“Knowledge-of-Exponent Assumption”（KEA）。这样只有我用知道的多项式h(x)，是的，必须知道多项式h(x)，才能算出两个结果，别无他法。而你拿到我发给你的两个结果就可以检验偏移量，而不是P(x)来验证我确实知道多项式，而且是用多项式来计算的两个结果。

到此为止，我给你证明了我知道隐含答案3x5=15的多项式P(x)，从多项式P(x)，你是反推不出3x5=15这个答案的（是的，类似hash，单向的）！

这就是关于这个问题的零知识证明，这种证明机制，可以推广到任何问题的证明。