TECH

零知识证明系列(三):极致的简洁


前言

上两篇我们分别介绍了zkSNARK和椭圆曲线的基本原理,在将一个证明问题转成多项式后,如何结合椭圆曲线做到简洁的验证?这就是本篇文章要为大家解答的问题。zkSNARK的全称是zero-knowledge succint non-interactive arguments of knowledge,其中简洁性succint和零交互non-interactive是zkSNARK相对其他算法最大的亮点,相信读完本篇的你也会被这两个特性的巧妙处理惊艳到。

本篇提纲

  1. 抽样实现简洁
  2. 同态隐藏抽样点
  3. KCA锁定原方程
  4. 双线性映射完成验证
  5. 总结

抽样实现简洁

在系列第一篇,我们了解了如何将一个证明问题转为多项式,这样做的目的是为了能够零知识证明,即不泄露原方程的解并证明我们知道这个解。转成多项式后我们能实现比较粗糙的零知识证明,说粗糙是因为证明者和验证者之间要传输的数据太大,甚至会导致无法实际应用,接下来看看zkSNARK从哪里解决这个问题。

简单回顾一下我们第一篇构造的多项式:A(x) * B(x) - C(x) = H * Z(x)。根据我们推导的结果,实际的表达式应该为:s.A(n) * s.B(n) - s.C(n) = H(n) * Z(n),其中s为解向量(1, 3, 35, 9, 27, 30),这个解向量只有知道解x=3可以得到。所以证明过程就是证明者Prover用解向量计算P(n)和H(n),验证者知道公开的Z(n),进行验证:

我们举的例子很简单所以P(n)不会很大,实际应用中的问题要复杂得多,所以P(n)的项数会在百万以上,这就导致这样证明效率特别低。解决这个效率问题最简单的办法是抽样,即选一个随机数t,将几百万项的P(n)=a0+a1n+a2n2+...转成一个数P(t)=T,这就变成了一个O(1)的算法,即不管问题多复杂,最后证明的大小都是固定的,这就是为什么我把zkSNARK的succint称为极致的简洁。

显而易见通过抽样对效率的提升是巨大的,但我们也应该能想到,事情不会这么简单。极致的简洁也带来了新的问题:

1. Prover不知道解但是可以针对随机数t临时构造出假的证明,满足验证条件。因为Z(n)是公开的,如果Prover不知道解向量s,那他可以通过Verifier发过来的t精心构造一个H'(t),使得在仅在抽样点t满足P'(t)= H'(t)* Z(t),然后将P'(t)和H'(t)发给Verifier,Verifier也能验证通过,Prover作弊成功。

2. Prover不知道解但是可以构造另一个方程和对应另一个解,满足验证条件。如果Prover不知道解向量,但是知道另一个方程的解s' 和方程的系数向量A'(n)、B'(n)、C'(n),则可以计算出P'(n)和H'(t),使得任意的t都满足P'(t)= H'(t)* Z(t),Prover作弊成功。

那我们就针对这两个漏洞继续进行优化,要让Prover证明的解是正确的解,同时保证证明的方程还是原来的方程,即题目和答案都不能偷梁换柱。

同态隐藏抽样点

系列第二篇有简单介绍,基于离散对数难题,已知h=E(x)=gx,只知道h、g我们无法得到x的值。加法同态指的是就是 E(ax1+bx2)=aE(x1)+bE(x2),即结果映射后x1和x2的加法计算仍然保留。同理,E(x1a * x2b)=E(x1)a * E(x2)b 就是指映射函数E满足乘法同态。

对于上面的抽样可以通过E(P(t))和E(H(t))进行验证,从而让Prover不知道t的值,也就无法临时构造假的P(t)和H(t)去通过验证。因为P(n)=a0+a1n+a2n2+...,根据加法同态有E(P(t)) = a0+a1E(t)+a2E(t2)+...anE(tn),因为Z(t)是一个可以计算出来的具体值,所以E(H(t))也是关于{E(t), E(t2), ..., E(tn)}的线性组合,将E(P(t))和E(H(t))发给Verifier就可以进行验证了。这样Prover就不能通过t临时构造证明了,因为离散对数难题保证了无法通过E(t)得到t。

通过KCA锁定原方程

Verifier确定Prover使用的是不是原方程的对应的多项式A(n)、B(n)、C(n)的过程称为KCA(Knowledge of Coefficient Test and Assumption)。

同样基于离散对数难题,有b=α*a,知道b和a无法计算出α,我们将这样的(a, b)称为一个α对,现在要求你提供另一个α对,即b'=α*a',不知道α如何提供呢?可以令(a', b')=(λa, λb),也就是说如果你不知道α就只能通过(a, b)去构造新的α对。同理如果是提供给你一组α对(a1, b1)、(a2, b2)、(an, bn),让你返回一个不一样的α对,就可以给出这样一对数(c1a1+c2a2+...+cnan , c1b1+c2b2+...+cnbn),然后只需要验证你返回的数对满足α对就可以基本确定这对(a', b')是与提供的两组系列值相同的线性组合。

我们所说的第二个问题,就是Prover可以使用任意P'(n)=A'(n)+B'(n)-C'(n)去回答Verifier,这可以与原方程对应的A(n)、B(n)、C(n)完全不一样。所以可以让Verifier只提供A(t)、B(t)、C(t),强迫Prover基于此构建应答。

于是有,Verifier发送下面三组α对给Prover,其中M是多项式阶数:

<E(A1(t)), E(αAA1(t))>, <E(A2(t)), E(αAA2(t))>...<E(AM(t)), E(αAAM(t))>

<E(B1(t)), E(αBB1(t))>, <E(B2(t)), E(αBB2(t))>...<E(BM(t)), E(αBBM(t))>

<E(C1(t)), E(αCC1(t))>, <E(C2(t)), E(αCC2(t))>...<E(CM(t)), E(αCCM(t))>

要求Prover返回三个新的α对,由于Prover不知道这三个α的值,所以只能选三组随机数(a1...aM)(b1...bM)(c1...cM)计算这样三组α对<E(A(t)), E(αAA(t))>、<E(B(t)), E(αBB(t))>、<E(C(t)), E(αCC(t))>:

E(A(t))=E(a1*A1(t)+...+aM*AM(t))=a1*E(A1(t))+a2*E(A2(t))+...+aM*E(AM(t))

E(αAA(t))=a1*E(αAA1(t))+a2*E(αAA2(t))+...+aM*E(αAAM(t))

E(B(t))=b1*E(B1(t))+b2*E(B2(t))+...+bM*E(BM(t))

E(αBB(t))=b1*E(αBB1(t))+b2*E(αBB2(t))+...+bM*E(αBBM(t))

E(C(t))=c1*E(C1(t))+c2*E(C2(t))+...+cM*E(CM(t))

E(αCC(t))=c1*E(αCC1(t))+c2*E(αCC2(t))+...+cM*E(αCCM(t))

要进一步限制A(n)、B(n)和C(n),可以引入Li(n)=Ai(n)+Bi(n)+Ci(n),于是当li=ai=bi=ci时有:L(n)=A(n)+B(n)+C(n),那么Verifier选一个随机数β,对于任意t,有:

V计算:E(βL(t))=E(β(A(t)+B(t)+C(t)))=β(E(A(t))+E(B(t))+E(C(t)))

P计算:E(βL(t))=l1*E(βL1(t))+l2*E(βL2(t))+...lM*E(βLM(t))

只需要比较Verifier和Prover计算的结果是否相等就可以确定Prover是否使用了相同的系数。所以Verifier还需要提供E(βL1(t))...E(βLM(t))。

由此可见,为了解决这两个问题,Verifier需要给Prover提供大量的数据(阶数M达到百万以上),但是从上面可以看出来,这些数据都是关于随机数t的多项式的映射,所以我们可以将这些随机数的计算结果放到一个公共数据集里,我们称为CRS(Common Reference String),只需要保证这个t不会被任何人知道,那么每一次使用zkSNARK都可以直接拿这个CRS去计算,而不需要Verifier选随机数计算然后提供给Prover。除了上面提到的提供四组数据,加上需要做同态隐藏的一组数,CRS一共包含五组数据:

CRS:

E(A1(t)), E(αAA1(t)) | E(A2(t)), E(αAA2(t)) | ... | E(AM(t)), E(αAAM(t))

E(B1(t)), E(αBB1(t)) | E(B2(t)), E(αBB2(t)) | ... | E(BM(t)), E(αBBM(t))

E(C1(t)), E(αCC1(t)) | E(C2(t)), E(αCC2(t)) | ... | E(CM(t)), E(αCCM(t))

E(βL1(t)) | E(βL2(t)) | ... | E(βLM(t))

E(t) | E(t2) | ... | E(tn)

这里可以看出来,证明过程已经由交互式变为非交互式了,P要证明一个问题的解,只需要直接将证明发给V,V验证通过就可以相信P了。 这里可能看起来有点抽象:为什么发过去几个数据就能证明我知道一个问题的解,是什么样的问题?其实假设我们需要P证明问题y的答案x,因为问题y是公开的,我们都可以将问题y的证明转为多项式格式(通用过程参考系列一),然后通过CRS里的基本数据E(A1(t))等构造出对应问题y的多项式的映射E(A(t)),所以实际上P提供的数据中就带了需要证明的问题,然后V做完这些验证,就可以确定P确实解x并且x确实是关于问题y的解。

双线性映射完成验证

上面的验证过程还是有一个问题:我们用的E一直是满足加法同态的,但是E(C(t)-A(t)*B(t)) = E(H(t)*Z(t))中有乘法计算,需要函数E满足乘法同态才能进行验证。这里就到双线性映射函数登场了。我们在本系列上一篇文章中讲到,双线性映射函数(又叫配对函数)是满足乘法同态的:e(g1a, g2b) = e(g1,g2ab) = e(g1, g2)ab,我们只需要将上面函数E改为双线性映射函数就可以对乘法计算的映射进行验证。具体过程读者可以自行推导,比较简单这里就不展开了。

总结

到这里完成了本系列的前三篇文章,主要是对目前应用最广的零知识证明方案zkSNARK做了比较详细的讲解。其实除了zkSNARK,还有很多其他的证明方案也得到了很好的应用,不同方案有不同优点,适应不同应用场景,但是在区块链上对效率和计算费用有一定要求,所以zkSNARK的零交互和简洁性更受欢迎。本系列并未完结哦,后面会开始做一些零知识证明代码的讲解和实战演示,敬请期待吧。

附录

[But17] - Vitalik Buterin. zk-SNARKs: Under the Hood. 2017. url:medium.com/@VitalikButerin...
[Ben19] - Daniel Benarroch. Diving into the zk-SNARKs Setup Phase. 2019. url:medium.com/qed-it...

Author image

About Kang Gao

Blockchain Developer & Researcher