零知识证明学习(三)—— 非交互式零知识证明(zkSNARKs)

非交互式零知识证明

本节主要介绍一种新的零知识证明- z k S N A R K zkSNARK zkSNARK z k S N A R K : z e r o − k n o w l e d g e S u c c i n c t N o n − I n t e r a c t i v e A r g u m e n t s o f K n o w l e d g e zkSNARK:zero-knowledge Succinct Non-Interactive Arguments of Knowledge zkSNARKzeroknowledgeSuccinctNonInteractiveArgumentsofKnowledge

背景

z k S N A R K zkSNARK zkSNARK是零知识证明中最经典的加密算法体系。目前已经被应用在很多地方,特别是在区块链领域,包括实际生活中隐私保护相关的应用。

Z e r o − K n o w l e d g e Zero-Knowledge ZeroKnowledge: 零知识证明体系里有两个角色,一个是证明者(Prover), 一个是验证者(Verifier)。举个例子,比特币创始人中本聪身份不明,之前传出过很多人声称自己是中本聪最后都不了了之。那么一个人如何证明自己是中本聪呢?因为大家知道中本聪钱包的地址。因此他只需要用这个钱包的私钥对这句话签名 “我是XXX,我其实就是中本聪"。然后其他人(Verifier) 都可以用中本聪钱包的公钥对这个签名进行验证。这个就是一个零知识证明。首先只有私钥持有方的签名才能通过验证,其次这个签名没有泄漏私钥的任何信息,钱包不会被其他人盗用。因此零知识证明解决了两个问题,一个是信任问题,一个是隐私问题。

S u c c i n c t Succinct Succinct:是指对于一个很复杂的问题,验证者可能需要进行很长时间的计算才能提供出相应的证明,但是我们希望证明的大小不要太大 (比如实际应用中只有几十 k b kb kb),同时验证者只需要很少的时间(比如微秒级别的时间) 就能够验证计算是否正确。

N o n − I n t e r a c t i v e Non-Interactive NonInteractive:是指在证明的过程中双方不需要互相交换信息。有一些算法体系需要证明者和验证者之间互相对话几次,交换信息。这对于实际应用就很不方便,增加了系统特别是网络通讯的复杂度。因此最好的情况是证明者一次性地把证明发送给验证者,验证者直接验证即可。

A r g u m e n t o f K n o w l e d g e Argumentquad of quad Knowledge ArgumentofKnowledge:指的是证明者只有知道问题的答案才可能提供证明。这个比较绕口,另一个解释就是证明者造假成功的概率可以忽略不计。这里还有一个类似的概念 Proof of Knowledge。它们之间是有区别的。对于Argument来说,证明者的计算能力有限,也就是多项式的算力,而Proof of Knowledge则对证明者计算能力没有要求。比如一个验证者是从未来穿越回来,带着最先进的量子计算机,那么对于Proof of Knolwege的系统,他仍然没法造假。但是对于Argument of Knowledge的系统则有可能。简单的说就是:proof(证明)和argument(论证)在零知识证明里,是有区别的,在proof system中,即便是计算能力无限的prover也没法欺骗verifier去相信一个错误的陈述为真(统计可靠性),而在argument system中,只有多项式时间计算能力的没法欺骗(计算可靠性),假设能破解椭圆曲线离散对数问题,那么可能就不再安全。

多项式知识的证明(Proving Knowledge of a Polynomial)

我们从一个证明多项式知识的问题开始,然后使用一般方法。我们还会发现多项式的其他性质。

到目前为止,问题集中在一个薄弱的证明概念上,各方必须相互信任。例如,证明者不需要知道多项式,他可以使用任何其他可用的方法来得出正确的结果。而且,如果验证者多项式求值的范围并不大,她可能有概率会猜到一个数,这个概率是无法忽视的。接下来我们来处理这个缺陷,但首先要清楚的分析多项式的性质。一个多项式表达形式如下(n阶多项式):
c n x n + . . . + c 1 x 1 + c 0 x 0 c_nx^n+...+c_1x^1+c_0x^0 cnxn+...+c1x1+c0x0
如果证明者或者验证者知道是1阶多项式( c 1 x 1 + c 0 c_1x^1+c_0 c1x1+c0),那意味着他们知道该多项式系统为 c 1 , c 0 c_1,c_0 c1,c0,而且系数可能为任意值。代数基本定理指出,任何多项式都可以分解成线性多项式(即,1阶多项式代表一条直线),只要它是可解的。因此,我们可以将任何有效多项式表示为线性多项式的乘积:
( x − a 0 ) ( x − a 1 ) . . . ( x − a n ) = 0 (x-a_0)(x-a_1)...(x-a_n)=0 (xa0)(xa1)...(xan)=0
从上式看出一个多项式可以由多个1阶多项式组成。例如多项式 x 3 − 3 x 2 + 2 x x^3-3x^2+2x x33x2+2x分解为 ( x − 0 ) ( x − 1 ) ( x − 2 ) (x-0)(x-1)(x-2) (x0)(x1)(x2)。从分解的多项式可以明显的看出解为 0 , 1 , 2 0,1,2 0,1,2,你可以很容易地在多项式的任意一种形式上检查这个解,但是分解形式在表面上有所有以上的解(也称为根)。

假设证明者声明,他知道一个3次多项式的根是1和2,这意味着他的多项式具有这种形式: ( x − 1 ) ( x − 2 ) . . . (x-1)(x-2)... (x1)(x2)...,换句话说, ( x − 1 ) (x-1) (x1) ( x − 2 ) (x-2) (x2)可以看作多项式 x 3 − 3 x 2 + 2 x x^3-3x^2+2x x33x2+2x的余子式。因此,如果证明者想要证明他声明的多项式有这些根,但又不想揭露多项式本身,他需要证明他的多项式 p ( x ) p(x) p(x)是这些余子式 t ( x ) = ( x − 1 ) ( x − 2 ) t(x)=(x-1)(x-2) t(x)=(x1)(x2)的乘积,所以存在任意多项式 h ( x ) h(x) h(x)有以下形式:
p ( x ) = t ( x ) h ( x ) p(x) = t(x)h(x) p(x)=t(x)h(x)
因此,多项式多项式 p ( x ) p(x) p(x)是由多项式 t ( x ) t(x) t(x)和多项式 h ( x ) h(x) h(x)乘积等到,多项式 p ( x ) p(x) p(x)包含多项式 t ( x ) t(x) t(x)

如何得到多项式 h ( x ) h(x) h(x),这里我们很自然想到 h ( x ) = p ( x ) t ( x ) h(x)=frac{p(x)}{t(x)} h(x)=t(x)p(x),如果证明者不能找到多项式 h ( x ) h(x) h(x),这意味着多项式 p ( x ) p(x) p(x)并没有多项式 t ( x ) t(x) t(x)余子式,这也以为多项式除法有余数。这里举个小例子: p ( x ) = x 3 − 3 x 2 + 2 x p(x)=x^3-3x^2+2x p(x)=x33x2+2x t ( x ) = ( x − 1 ) ( x − 2 ) = x 2 − 3 x + 2 t(x)=(x-1)(x-2)=x^2-3x+2 t(x)=(x1)(x2)=x23x+2,这里很容易得到 h ( x ) = x h(x)=x h(x)=x

证明者和验证者具体验证协议如下:

  • 验证者随机选取一个值 r r r,计算 t = t ( r ) t=t(r) t=t(r),并把 r r r发送给证明者
  • 证明者计算 h ( x ) = p ( x ) t ( x ) h(x)=frac{p(x)}{t(x)} h(x)=t(x)p(x),将 p ( r ) p(r) p(r) h ( r ) h(r) h(r)值发送给验证者
  • 验证者检查 p = t × h p=ttimes h p=t×h,如果多项式相等,意味着多项式 p ( x ) p(x) p(x) t ( x ) t(x) t(x)余子式

这里还需要介绍一种情况,如果证明者使用不同的 p ′ ( x ) pprime (x) p(x),它没有必要的代数余子式,,例如: p ′ ( x ) = 2 x 3 − 3 x 2 + 2 x pprime (x)=2x^3-3x^2+2x p(x)=2x33x2+2x,这里我们可以得到 p ′ ( x ) = t ( x ) × ( 2 x + 3 ) + 7 x − 6 pprime (x)=t(x)times (2x+3) +7x-6 p(x)=t(x)×(2x+3)+7x6。因此证明者整除将会有余数,所以我们将式子 p ′ ( x ) = t ( x ) × ( 2 x + 3 ) + 7 x − 6 pprime (x)=t(x)times (2x+3) +7x-6 p(x)=t(x)×(2x+3)+7x6整除 t ( x ) t(x) t(x)得到 h ( x ) = 2 x + 3 + 7 x − 6 t ( x ) h(x)=2x+3+frac{7x-6}{t(x)} h(x)=2x+3+t(x)7x6。因为x是由验证者随机选择的,有一个低概率概率余数 7 x − 6 7x-6 7x6 t ( x ) t(x) t(x)整除,如果验证者检查 p ( x ) , h ( x ) p(x),h(x) p(x),h(x)必须是整数,这样的证明将被拒绝。但是,该检查要求多项式系数也是整数,这对协议造成了很大的限制。因此,这就是引入密码原语的原因,这使得这种除法不可能实现,即使原始的计算结果碰巧是可除的。

问题(issues)

  • 证明者可能不知道声明的多项式 p ( x ) p(x) p(x),他可以计算 t = t ( r ) t=t(r) t=t(r),并选择一个随机数 h h h,计算 p = t × h p=t times h p=t×h,验证者接收到值是正确的。
  • 证明者知道随机点 x = r x=r x=r,他能构造任意多项式在 r r r处有一个共享点与 t ( r ) × h ( r ) t(r) times h(r) t(r)×h(r)
  • 在初始情况下,证明者声称知道一个特定次数的多项式,在当前的协议中没有阶数的强调。因此,证明者可以利用一个满足余子式检查的高次多项式进行欺骗。

这里说明一下,零知识证明的研究方向,本文主要一环扣一环的讲解,希望有兴趣的朋友能耐心读下去。