位置:首页 - IPFS咨讯
零知识证明 - zkSNARK入门
发布日期:2019/5/28     阅读:140 次

网络上讲解零知识证明的文章就不多,这些文章要不太浅显,要不太学术,很少有能给入门者整体框架上的认识。

比如,阿里巴巴零知识证明就是一个非常好的通俗理解零知识证明的例子:

阿里巴巴被强盗抓住,为了保命,他需要向强盗证明自己拥有打开石门的密码,同时又不能把密码告诉强盗。他想出一个解决办法,先让强盗离开自己一箭之地,距离足够远让强盗无法听到口令,足够近让阿里巴巴无法在强盗的弓箭下逃生。阿里巴巴就在这个距离下向强盗展示了石门的打开和关闭。

太原ipfs矿机为您解答这个整个过程就是零知识证明,证明者能够在不向验证者提供任何有用信息(石门的口令)的情况下,使验证者相信某个论断(阿里巴巴知道打开石门的方法)是正确的。

技术人除了通俗的理解零知识证明外,还需要对零知识的理论和推导过程深入理解运用。以太坊的一篇blog,比较适合零知识证明入门的小伙伴。

https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/

这篇文章也是这篇blog的翻译和我自己的理解。通过这篇文章,能快速建立零知识证明的逻辑框架。虽然这篇文章有些推导公式,但是相对简单,小伙伴需要耐心阅读。

先给出零知识证明的逻辑框架:

0.png


00  零知识证明的基本概念太原filecoin矿机为您解答


零知识证明,zkSNARKzero-knowledge Succint Non-interactive ARguments of Knowledge的简称:


零知识证明大体由四部分组成:

在了解零知识的基础概念上,慢慢推导整个零知识证明过程,先从NP问题说起。

01  NP问题以及约化


解决一个问题需要花费时间。如果解决问题需要的时间与问题的规模之间是多项式关系,则可以称该问题具有多项式复杂度。一般问题可分成两类:P问题NP问题。P问题指的是在多项式时间内可解的问题。NP问题(Non-Deterministic Polynomial Problem,非确定性多项式问题),指不能在多项式内可解,但是可以在多项式时间内验证的问题。


很显然,P问题也是NP问题,但是是否NP问题是P问题,NP=P?,目前为止还没有人能证明。一般认为,NP问题不等于P问题,也就是说,NP问题不存在多项式解法。

约化(Reduction),可以理解成问题的转化。对任意一个程序A的输入,都能按某种法则变换成程序B的输入,使两程序的输出相同,那么,可以说,问题A可约化为问题B。

NPC问题,是一个NP问题,并且,其他所有的NP问题都能归约到它。简单的说,NP问题之间可以相互归约,一个NP问题求解,其他NP问题一样能求解。

举例说明,NP问题以及NP问题的归约。

布尔公式满足性问题(SAT问题,boolean formula satisfiability) 就是一个NP问题。布尔公式定义如下:

1.png

一个布尔公式可满足,指输入是0/1的情况下,存在输出为真。SAT问题指,找出所有可满足的布尔公式。SAT问题看上去,除了枚举一个个可能的布尔公式外,没有更好的办法,也就是多项式时间内不可解。如果知道一个可满足的布尔公式,验证非常方便(输入是0/1的情况下,看看输出是否为真)。SAT问题是NP问题。

再看看另外一个NP问题:PolyZero问题。PolyZero问题指某个多项式满足:多项式输入是0或1的情况下,多项式输出为0。

2.png

总结一下,NP问题是在多项式时间内无解,但是可以多项式时间验证的问题。NP问题可以相互归约。


02  QSP问题


需要证明的问题,肯定是NP问题,如果是P问题,不存在问题解的”寻找“,也就不存在证明。简单的说,zkSNARK问题处理的都是NP问题。既然NP问题相互可以归约,首先需要确定一个NP问题,其他NP问题都可以归约到这个NP问题,再进行证明。也就是,证明了一个NP问题,就可以证明所有NP问题。


3.png

4.png

山西ipfs矿机以上是基础知识,下面开始介绍zkSNARK的证明过程。在继续深入一个QSP问题证明细节之前,先看看一个多项式问题的证明过程。

03  多项式问题的证明过程

5.png


6.png

多项式的整个证明过程如下图所示:


04  QSP问题的skSNARK证明山西filecoin矿机

8.png

9.png


11.png

至此,zkSNARK的推导逻辑就基本完成。使用zkSNARK证明,由如下的几步组成:

1/ 问题转化:  一个需要证明的NP问题转化为选定的NP问题(比如QSP问题)

2/ 设置参数(setup):设置参数的过程也是挑选随机数的过程,并提供CRS

3/ 证明者获取证据u,通过CRS计算证据(proof)

4/ 验证者验证证据以及响应的proof

总结:零知识证明由四部分组成:多项式问题的转化,随机挑选验证,同态隐藏以及零知识。需要零知识证明的问题先转化为特定的NP问题,挑选随机数,设置参数,公布CRS。证明者,在求得证据的情况下,通过CRS计算出证据。验证者再无需其他知识的情况下可以进行验证。


DAC的网站是如何建立的,eosDAC也正在试验IPFS
IPFS创始人Juan Benet首次与中国互动 并声明没有和中国任何个人或组织合作