区块链 > 技术 > 正文

理解零知识证明算法之Zk-stark

区块链数字货币板块文章「理解零知识证明算法之Zk-stark」,本文约有1047个文字,大小约为5KB,预计阅读时间3分钟请您欣赏。樱花区块链门户资讯网荟萃众多优秀文章精选,如果想要浏览更多相关区块链数字货币,可以关注本文结尾推荐的优秀文章内容。本站区块链资讯虽然不乏优秀之作,但仅为大家参考使用,希望能对关注区块链的人有所帮助。

Concept:zk-stark vs zk-snark

谈到ZKP算法,大伙可能听过一些,比如zk-snark,zk-stark, bulletproof, aztec, plonk等等。今天,咱就给大伙聊聊这一对“表面兄弟”,zk-stark和zk-snark算法的异同之处。

不如,先让我们从名称说起?毕竟,两个看起来都很厉害的亚子^_^ !



如下图所示,我们将名称zk-stark 和 zk-snark根据功能特点分别分成四个部分,然后逐个比较分析。

理解零知识证明算法之Zk-stark
「零知识证明」

Zk-stark => zk - s t ark

· zk:零知识,表明隐私的输入将会被隐藏,除了证明者,其他任何人不会看见;


· s:可扩展的,和Replay Computation的验证耗时相比,zk-stark的证明和验证耗时分别与之呈拟线性关系和对数关系;


· t:透明的,zk-stark算法没有CRS setup by Trusted party;


· arg:知识论证,只有知道private input的prover,才能生成有效的proof;

Zk-snark => zk - s n ark

· zk:零知识,表明隐私的输入将会被隐藏,除了证明者,其他任何人不会看见;


· s:简洁的,指的是生成的proof足够小和验证时间足够短;


· n:非交互式的,Prover生成证明的过程中和verifier没有交互;


· arg:知识论证,只有知道private input的prover,才能生成有效的proof;

Compare

· 相同点

1. 都实现了将隐私的输入可靠隐藏;


2. 都是基于知识论证,不知道private input的prover生成不了有效的proof;


3. 都可以实现交互式与非交互式式的算法,只是取决于randomness是由谁来生成的;

· 不同点

1. zk-stark具有可扩展性,即证明和验证的耗时与原始计算的耗时分别呈拟线性关系(且线性因子为常量)和对数关系,这意味着,如果原始输入的数据集增大1000000倍,zk-stark的证明耗时增加线性倍数的时间,但验证时间仅仅增加21*log1000000 =~ 420倍。证明耗时呈线性关系基本满足所有的ZKP算法,但是验证时间呈对数关系,仅此一家,因此在扩展性上,zk-stark要胜一筹。

2. zk-stark同样具有简洁性,但是是验证简洁性。所谓简洁性,通常是指即使验证程序很大,生成的proof size也不会很大,同时又能很快的完成验证(比native computation快很多)。相比对zk-snark,zk-stark的proof size要大的多,因此在简洁性上,zk-snark要胜一筹。

ALG compare

前面从概念上对zk-stark 和 zk-snark算法做了比较,其异同点可以笼统的概括为:

· 都是基于知识论证的ZKP算法;


· zk-stark不需要zk-snark的Trusted party 设置CRS,因此是Transparent;


· zk-stark的验证耗时与native computation 耗时呈对数关系,因此是Scalable;

下面,我们将从算法层面,去做相对更深入一些的比较分析:

· zk-snark ALG 【4】

1. 算法思想:将证明CI statement成立问题转换成证明多项式等式成立问题,转换过程用到了算术环路和QAP方法;

2. 多项式等式成立意味着什么?(图中黄色部分)

a. 等式两边可以看作两个度相等的多项式,假设为n,其交点最多有n个,假如在一个很大的域范围内随机选一个点,如果的两个多项式在此点的值相等,则证明两个多项式是相等的。

b. 我们可以看到,等式右边的多项式因子Z是目标多项式,它的零点就是右边整体多项式的零点,也就是等式左边整体多项式的零点,而等式左边的多项式在这些零点的取值,就转换成了一个个的算术电路里每个乘法门对应的一阶线性约束等式(R1CS)成立,即原始计算等式成立(注:R1CS由原始计算等式分解得到);

3. 算法分为三个步骤,CRS生成;证明者证明;验证者验证;

4. 可以看到prover生成证明过程中,没有与验证者交互,因此是non-interative;

5.如何保证prover用于生成证明的A/B/C/H是多项式且是小于某个度数呢?

a.通过trusted party 来保证,因为它是可信任的,因此它生成pk,vk用到的A/B/C等肯定是多项式并且是小于某个度的;


b. 如果证明者作恶,那么验证者将会很大概率验证失败;


c. 主要用到了同态加密HH和系数知识假设KCA和椭圆曲线双线性配对等数学知识;


理解零知识证明算法之Zk-stark
「零知识证明」

以上便是樱花区块链给大家分享的关于「理解零知识证明算法之Zk-stark」http://www.0797jjw.cn/qkljs/jishu_26437.html的相关信息了,希望能帮助到大家,更多区块链相关内容,敬请关注樱花区块链!

猜你喜欢

全球稳定币与金融稳定

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

原文地址: