你问我一个问题,如果我给你正确答案,你给我付一笔费用。但是,我不能直接告诉你答案,因为,如果我告诉了你答案,你可能不付费。
对于这种两难场景,怎么解决?
这种解决办法就是密码学中的零知识证明。

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

假设我们生活在一个非常原始的社会,算术就是一种很高深的学问,没有几个人懂。我是当时的一个算术家,别人有算术问题都会来付费问我。
这时,你有一个算术问题问我: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,单向的)!
这就是关于这个问题的零知识证明,这种证明机制,可以推广到任何问题的证明。
继续阅读
阅读原文