'CryptoYC'
研究|零知识证明
🌿

研究|零知识证明

零知识证明由S.Goldwasser, S.Micali 和C. Rackoff在二十世纪80年代提出。此证明的意义在于不用向对方展示证明或解题的过程,使对方相信某个结论是正确的。零知识证明被大量地运用在密码学中,并且高度证明了此概念和应用可以解决很多问题。

本文将会详细举例并讲述“零知识证明”的概念,并且在文末附上笔者的推荐书单,欢迎阅读。

零知识证明定义

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

  • Succinct:证明的数据量比较小
  • Non-interactive:没有或者只有很少交互。
  • ARguments:验证者只对计算能力有限的证明者有效。拥有足够计算能力的证明者可以伪造证明。这也叫“计算可靠性"(相对的还有”完美可靠性")。
  • of Knowledge:对于证明者来说在不知道证据(Witness,比如一个哈希函数的输入或者一个确定 Merkle-tree 节点的路径)的情况下,构造出一组参数和证明是不可能的。

零知识证明示例———以数独为例

证明

有一天,小明出了一道非常难的数独题,小红花了很长时间尝试去解开这个数独,但是怎么都解不出结果。小红觉得小明在耍她,“这题压根就无解!小明你耍我!”,她跑到小明那抱怨。“我能证明给你看这题是有解的,而且我知道这个解”,小明淡定的回答道。“好啊”,小红暗自想着,“哼哼,等你证明给我看之后,我就把解记下来然后去戏耍下小刚,给他也做一下这题。”小明接着说:“我会用零知识证明的方法给你证明我会这题的解。也就是说我不会把解给你看,却能让你信服我确实有这题的解。”小红并不相信他能这样做到,还在想象小刚被耍的样子。小明拿出81(9x9)张空白的卡片放在桌上,在每张纸上写上1-9中的一个数字,他让小红转过身闭上眼,然后把这81张卡片小心翼翼地按照解的排列放在桌上,代表谜底的卡片,数字面朝下放在桌上;代表谜面的卡片,则数字面朝上放在桌上。

随机试验

小明放好卡片后,让小红睁开眼转过身。小红很激动,她觉得谜底就要揭晓了,很是开心。她可花了好几天时间都没能解出这题。小明对小红说:“小红,你不能偷看这些面朝下的卡片。”,明显能看出小红很失望,她以为能看到完整的一个解。“但是我能让你检验这些解:你可以随意选择按照行(row),或者按照列(column),或者按照3x3的九宫格(box) 来检验我的解。你挑一种吧” 小红告诉小明她决定选择按照行的方法来验证。小明接着把每一行的9张卡片收起来单独放到一个麻布袋里。所有卡片都被收完放在了9个麻布袋里。小明接着摇了摇每个麻布袋,把里面的卡片顺序都打散。最后把这9个麻布袋交给小红。

验证

“好了,你可以打开这些布袋了。“小明对小红说,“每个布袋里应该都有正好9张,没有重复数字的,分别是数字1-9的卡片。” 小红打开每个布袋一看,还果真是这样。

“可这啥都证明不了啊!我也可以这样做给你看。我只要保证每一行都是1-9这9张卡片,不去管纵列和九宫格里的数字是不是也都是没有重复的不就行了。“小红说道。小明解释说:“可是我事先也不知道你会选按照行来收集卡片,还是按照列,还是按照九宫格啊。我是按照题解来放置卡片的,你选啥我都没在怕的”

重复验证

小红还是不服气。觉得小明仍然有可能在骗她,所以要求小明再把卡片复原,按照原来的方法,重新选。这样接连试了几次,小红每次都选一个不一样的试验方法。试了好多次都是一样的结果。小红这下不得不承认,小明要么运气非常非常好,每次都能押中小红会选择哪种试验方式,要么就是他确实知道题解,(或者小明会读心术能预先知道小红会选什么试验方式)。小红很失望,这么多次试验下来,她还是不知道真正的题解,她只知道每次小明放置卡片的排列里很大几率每行每列每个九宫格确实都是没有重复的1-9,这就说明很大几率这题是有解的,而且小明很大几率确实知道这题的解。

零知识证明的本质就是在不揭晓我所知道或拥有的某样东西的前提下,向别人证明我有很大几率(这点很重要,零知识证明说到底是一个概率上的证明)确实知道或拥有这个东西。

故事里要证明的东西就是一个数独题的解,小明让小红每次随机抽取行,列,九宫格的卡片,并收集在一起随机打乱,小红通过拆开袋子并不能知道题解,但是却能相信小明很大几率确实知道题解。

这个故事里的zk-SNIPM也是半开玩笑地暗指了零知识证明现在最普遍的zk-SNARKs(Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)算法。故事中的zk-SNIPM虽然存在漏洞,但是他还有改进的余地,比如用一台扫描仪把第一次卡片的组合就全扫描下来,然后一次性同时验证所有的试验序列。这样就很难通过试错的方式来破解机器。

小明和小红之间最开始那种互动式的证明方法暗指的是交互式零知识证明(interactive zero-knowledge proof)。交互式零知识证明需要验证方(小红)在证明方(小明)放好答案(commitment)后,不断的发送随机试验。如果验证和证明双方事先串通好,那么他们就可以在不知道真实答案的情况下开挂(simulate/forge a proof)。

非交互式的证明则不需要这种互动。但是会额外需要一些机器或者程序,并且需要一串试验序列,这个试验序列不能被任何人知道。有了这么一个程序和试验序列,证明机就能自动算出一个证明,并且能防止任何一方作假。

零知识证明分析———问题拆解

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

多项式问题的转化 - 需要证明的问题转化为多项式问题 t(x)h(x) = w(x)v(x),证明者提交证明让验证者确认多项式成立。

随机挑选验证 - 随机选择验证的数值 s,验证 t(s)h(s) = w(s)v(s)。相对于验证多项式相等 t(x)h(x) = w(x)v(x),随机挑选验证,简单,验证数据少。随机挑选验证,安全性肯定不及多项式等式验证,但如果确实足够随机,安全性还是相当高的。

同态隐藏 - 同态隐藏指的是函数的一种特性。输入的计算和输出的计算保持“同态”。以加法同态为例,满足如下的三个条件的函数 E(x),称为加法同态:

1. 给定 E(x),很难推导出 x.

2. 不同的输入,对应不同输出 3. E(x+y) 可以由 E(x),E(y)计算出来。乘法同态类似。

零知识 - 证明者和验证者之间除了“问题证明与否”知识外,不知道其他任何知识(不知道随机挑选值,不知道挑选值的多项式计算结果等等)。

多项式问题转化

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 问题。布尔公式定义如下:

  • 假设变量 x1 , x2 , x3 , ... 是布尔公式
  • 假设 f 是布尔公式, ¬f 也是布尔公式(取反)
  • 假设 f 和 g 是布尔公式, f∧g 和 f∨g 也是布尔公式(与和或)

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

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

PolyZero(f):=1

f 满足输入是 0/1 的情况下,多项式输出为 0。

一个布尔表达式 f 可以通过如下的归约函数 r,转化为多项式:

  • r(xi ):=(1-xi )
  • r(¬f):=(1-r(f))
  • r(f∧g):=(1-(1-r(f))(1-r(g)))
  • r(f∨g):=r(f)r(g)

也就是说,一个 SAT 问题,通过归约函数 r,可以归约为一个 PolyZero 问题:f 是可满足的,当且仅当 r(f)输出为 0。

SAT(f)=PolyZero(r(f))

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

QSP 问题

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

给定一系列的多项式,以及给定一个目标多项式,找出多项式的组合能整除目标多项式。输入为 n 位的 QSP 问题定义如下:

给定多个多项式:v0 ,...,vm ,w0 ,...,wm

目标多项式:t

映射函数:f:{(i,j)∣1≤i≤n,j∈0,1}→{1,...m}

给定一个证据(Witness)u,满足如下条件,即可验证 u 是 QSP 问题的解:

ak ,bk =1  如果k=f(i,u[i])

ak ,bk =0  如果k=f(i,1-u[i])

va wb 能整除 t,其中va =v0 +a1 v1 +...+am vm ,wb =w0 +b1 w1 +...+bm wm

对一个证据 u,对每一位进行两次映射计算( u[i] 以及 1 -u[i] ),确定多项式之间的系数。因为针对证据 u 的每一位,计算两次,确定多项式之间的系数,如果 2n < m ,多项式的选择还是有很大的灵活性。

如果证明者知道 QSP 问题的解,需要提供证据(也就是 u)。验证者在获知证据 u 的情况下,按照上述的规则恢复出多项式的系数,验证 va vb  是否能整除 t :th=va wb  。为了方便验证者验证,证明者可以同时提供 h 。在多项式维度比较大的情况下,多项式的乘法还是比较复杂的。

有个简单的想法,与其验证者验证整个多项式是否相等,不如随机挑选数值进行验证。假设验证者随机挑选验证数值 s,验证者只需要验证 t(s)h(s)=va (s)wb (s) 。

多项式证明问题举例

多项式问题的证明过程

假设一个多项式

image

证明一个多项式,即给定一个输入 x ,提供 f(x) 的证明。

3.1 有线群论基础(椭圆曲线)

定一个有限群,生成元是 g ,阶为 n ,则该群包括如下的元素:g0,g1,g2,...,gn−1 。通过有限群加密的方式很简单:E(x):=gx 。也就是说,得知 gx 的情况下,不能反推出 x 。

3.2 选定随机数

验证者随机选择一个有限群中的元素,比如 s 。提供如下的计算结果( s 的不同阶的加密结果):

E(s0),E(s1),...,E(sd)

在生成这些计算结果后, s 就不需要了,可以忘记。

3.3E(f(s)) 计算

举个例子, f(x)=4+2x+4x2 , E(f(s))=E(s0)4E(s1)2E(s2)4 。显然, E(f(s)) 可以不知道 s 的情况下,通过验证者提供的数据计算出来。

多项式证明问题举例

多项式问题的证明过程

3.4α 对

注意的是,验证者是不知道待证明的多项式参数的,即使证明者提供了 E(f(s)) ,验证者也无法验证。 α 对的方法可以让验证者确认证明者是通过多项式计算出结果。在 3.2 的基础上,验证者还随机选择另外一个元素 α ,并提供额外的计算结果:

E(αs0),E(αs1),...,E(αsd)

证明者需要提供 E(f(s)) 和 E(αf(s)) 。

E(f(s))=E(s0)4E(s1)2E(s2)4

E(αf(s))=E(αs0)4E(αs1)2E(αs2)4

3.5 配对函数

配对函数e,满足如下定义:

e(gx,gy)=e(g,g)xy

验证者验证α对的方式很简单,检验如下的等式是否成立:

e(E(f(s)),gα)=e(E(αf(s)),g)

假设A=e(E(f(s)),B=E(αf(s))推导过程如下:

e(A,gα)=e(E(f(s)),gα)=e(gf(s),gα)=e(g,g)αf(s)

e(B,g)=e(E(αf(s)),g)=e(gαf(s),g)=e(g,g)αf(s)

到此为止,验证者提供α对的情况下,证明者可以证明通过某个多项式计算出某个结果,验证者不知道具体的多项式的参数

多项式证明问题举例

多项式问题的证明过程

3.6 δ 偏移

更进一步,证明者采用δ 偏移,甚至不想让验证者知道E(f(s))。采用δ 偏移,证明者不再提供A和B,而是随机一个δ参数,提供A′和B′。

image

很显然,验证者从A′无法推导出E(f(s)),但验证者一样能验证α对的配对函数是否成立:

image

多项式证明问题举例--整体过程

image

QSP 问题的 skSNARK 证明

skSNARK 证明过程分为两部分:

a) setup 阶段

b)证明阶段。QSP 问题就是给定一系列的多项式v0,...,vm,w0,...,wm以及目标多项式t,证明存在一个证据u。这些多项式中的最高阶为d。

4.1 setup 和 CRS

CRS - Common Reference String,也就是预先 setup 的公开信息。在选定s和α的情况下,发布如下信息:

s和α的计算结果

image

多项式的α对的计算结果

image

多项式的βv,βw,γ 参数的计算结果

image

4.2 证明者提供证据

在 QSP 的映射函数中,如果 2n < m,1, ..., m 中有些数字没有映射到。这些没有映射到的数字组成Ifree,并定义(k为未映射到的数字):

image

证明者需提供的证据如下:

image

4.3 验证者验证

在 QSP 的映射函数中,如果 2n < m,1, ..., m 中所有映射到的数字作为组成系数组成的二项式定义为(和vfree互补):

image

验证者需要验证如下的等式是否成立:

image

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

image
  • 问题转化:一个需要证明的 NP 问题转化为选定的 NP 问题(比如 QSP 问题)
  • 设置参数(setup):设置参数的过程也是挑选随机数的过程,并提供 CRS
  • 证明者获取证据 u,通过 CRS 计算证据(proof)
  • 验证者验证证据以及响应的 proof

推荐文章

推荐文章一:一个数独引发的惨案:零知识证明(Zero-Knowledge Proof)

推荐值:❤️❤️❤️❤️❤️

难度值:⭐️

这篇文章的作者是著名的 Ghost 和 Spectre 这两个协议的创始团队的领队 Aviv Zohar。文章非常接地气且通俗易懂,通过三个好朋友一起玩数独游戏的故事介绍了什么是零知识证明。

原文链接:https://medium.com/qed-it/the-incredible-machine-4d1270d7363a

中文翻译:https://zhuanlan.zhihu.com/p/34072069 另外这篇文章中引用了两篇介绍零知识证明的论文,也值得看一看。

推荐文章二:How to explain zero-knowledge protocols to your children

推荐值:❤️❤️❤️

难度值:⭐️

这篇来自上个世纪的文章,正如它的标题一样,作者以给孩子讲故事的口吻,讲了一个阿里巴巴与四十大盗的故事,这个故事后来也成为了介绍零知识证明的经典故事。以故事的形式讲述零知识证明使得这篇文章理解起来也很简单。

原文链接:http://pages.cs.wisc.edu/~mkowalcz/628.pdf

推荐文章三:Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles

推荐值:❤️❤️❤️

难度值:⭐️⭐️⭐️

如何在不泄漏任何信息的前提下向别人证明你有一个数独问题的答案呢?同样这个问题也是介绍零知识证明的经典案例。论文中提出了使用一个零知识证明协议解决这个问题的方案,这篇论文相比较于前两篇文章,理论性更强一些,篇幅更长,协议的介绍更为详细,但总体来说还算比较好理解。

原文链接:http://www.wisdom.weizmann.ac.il/~naor/PAPERS/sudoku.pdf

推荐文章四:Zero knowledge proofs: a tale of two friends

推荐值:❤️❤️

难度值:⭐️⭐️

与前面几篇文章类似,这篇文章也是通过讲故事的形式来向读者介绍零知识证明的。文中 Prover 要向 Verifier 证明其知道魔法的解法。这篇文章篇幅较短,内容理解起来难度较小。

原文链接:https://medium.com/hackernoon/zero-knowledge-proofs-a-tale-of-two-friends-d7a0ffac3185

推荐文章五:Explain Like I’m 5: Zero Knowledge Proof (Halloween Edition)

推荐值:❤️❤️

难度值:⭐️⭐️

这同样是一篇讲故事的文章,哈哈~ 这篇文章讲述了一个糖果和百万富翁的故事(Candy bars and millionaires),文章同样篇幅较短,内容理解起来难度较小。

原文链接:https://medium.com/hackernoon/eli5-zero-knowledge-proof-78a276db9eff

推荐文章六:零知识证明: 抛砖引玉

推荐值:❤️❤️❤️❤️

难度值:⭐️⭐️⭐️

作者是 Zerocash 协议的创建者之一,密码学大神 Matthew Green[1]。这两篇文章几乎涵盖了学习零知识证明原理所有的基本概念,文章思路很清晰。

零知识证明: 抛砖引玉 第一篇文章主要从零知识证明的起源开始讲起,然后同样借助了地图三染色和 “时光机”来对零知识证明进行介绍。

原文链接:https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

来自 ETHFANS 的中文翻译版本:https://ethfans.org/posts/zero-knowledge-proofs-illustrated-primer

零知识证明:抛砖引玉,Part-2 这篇文章在第一篇的基础上,进一步对零知识证明的三个性质:可靠性,完整性和零知识,展开介绍。另外还结合 Schnorr 协议介绍了交互式和非交互式的概念。

原文链接:https://blog.cryptographyengineering.com/2017/01/21/zero-knowledge-proofs-an-illustrated-primer-part-2/

中文翻译版本:https://ethfans.org/posts/zero-knowledge-proofs-an-illustrated-primer-part-2

推荐文章七:安比实验室零知识证明介绍系列文章

推荐值:❤️❤️❤️❤️❤️

难度值:⭐️⭐️⭐️

这个系列的作者是安比实验室创始人郭宇,文章与以往的零知识证明科普文章的不同之处就是它没有单独去讲解零知识的基本原理。而且结合更多的概念和原理,更透彻得将零知识证明技术涉及得诸多原理逐一进行讲解,文章专业性较强,还包含了作者大量的思考,但理解起来也较为直观易懂,非常适合想要深入理解零知识证明的小伙伴。另外这个系列的文章还在持续更新中。

探索零知识证明系列一:初识「零知识」与「证明」 作为系列的第一篇,这篇文章首先介绍了「证明」的发展历程和「零知识」的作用,并举了一个地图三染色的例子,然后又对「信息」、「知识」和可满足电路的概念展开了介绍。

探索零知识证明系列二:从「模拟」理解零知识证明:平行宇宙与时光倒流 这篇文章介绍了零知识证明中的一个非常重要的概念——模拟(Simulator),「模拟」可以说是安全协议中核心的核心。文章中借助 “平行世界” 的假设去理解零知识读起来也非常有意思。

探索零知识证明系列三:读心术:从零知识证明中提取「知识」 零知识证明有三个重要的性质:可靠性,完整性和零知识。这篇文章探讨了可靠性。文章解释了如何借助「抽取器」和时间倒流的超能力把 Alice 的「知识」完整地「抽取」出来,并可给出了一个与之相关攻击实例 —— ECDSA 签名攻击。

探索零知识证明系列四:亚瑟王的「随机」挑战:从交互到非交互式零知识证明 这篇文章主要在讲零知识证明的信任根基——随机挑战。文章对零知识证明协议在两种不同的形式(交互式和非交互式)下随机挑战的方式进行了介绍。另外文章还对交互和非交互形式展开了介绍。

原文链接:https://mp.weixin.qq.com/s/FPHkqwiHX8UVIIbu_PXSQw

推荐文章八:零知识证明:一个略微严肃的科普

推荐值:❤️❤️❤️

难度值:⭐️⭐️⭐️⭐️

邓老师这篇“略微严肃”的科普,主要涉及两部分:

1. 交互式证明的巨大威力;

2. 零知识证明的定义和那些广泛流传的错误的例子

原文链接:https://zhuanlan.zhihu.com/p/29491567

推荐文章九:Zero-Knowledge Proofs: A Layman’s Introduction

推荐值:❤️❤️

难度值:⭐️⭐️ 这篇文章首先介绍了零知识证明协议中的三个参与者(Creator,Prover,Verifier)以及 Proofs 和 Verification的概念,并对 zkSNARK (一类零知识证明协议)和椭圆曲线的相关资料进行了介绍。

原文链接:https://blog.aventus.io/zero-knowledge-proofs-a-laymans-introduction-7020b93beeda

推荐文章十:白话零知识证明(一)

推荐值:❤️❤️

难度值:⭐️⭐️ 这篇来自秘猿科技的文章通过阿里巴巴的故事引出了零知识证明的一些概念,并对其进行了介绍。

原文链接:https://zhuanlan.zhihu.com/p/33189921

零知识证明涉及很多很有意思的思想和原理,都很值得探讨。在此不得不感叹于数学与密码学的精妙之处,也不得不钦佩密码学家们的厉害。

推荐文章十一:区块链学习笔记 (1):零知识证明的江湖

推荐值:❤️❤️❤️

难度值:⭐️⭐️

这篇文章讲了自 1895 年提出以来,零知识证明理论研究的发展过程,以及 zk-SNARKs 与零知识证明技术结合起来的发展过程。推荐给想了解零知识理论研究的发展过程的小伙伴。

原文链接:https://zhuanlan.zhihu.com/p/31651393

推荐文章十二:Efficient Cryptographic Arguments and Proofs – Or How I Became a Fractional Monetary Unit

推荐值:❤️❤️❤️

难度值:⭐️⭐️

这篇文章来自UCL信息安全研究人员的博客 Bentham’s Gaze[2],文章介绍了自零知识证明提出以来,这群研究人员在理论研究上的研究历程及成果,包括知名的 bulletProof 和 zk-STARK 等。读完这篇文章相信会对大家深入理解零知识证明的诸多协议有所帮助。

原文链接:https://www.benthamsgaze.org/2019/05/22/efficient-cryptographic-arguments-and-proofs-or-how-i-became-a-fractional-monetary-unit/

零知识证明迄今为止发展了三十多年,早期一直停留在理论层面,直到近十年才逐渐取得突破。随着越来越多研究人员的进场,相信这个领域未来还会有更多令人惊喜的成果。

推荐文章十三:V 神的 zk-SNARKs 科普文章

推荐值:❤❤❤❤

难度值:⭐⭐⭐⭐

V 神的这几篇文章应该算得上是流传最为广泛的 zk-SNARK 科普文了。不用多说,推荐阅读。

Quadratic Arithmetic Programs: from Zero to Hero 这篇文章详细介绍了 zk-SNARKs 的实现过程。文中将 zk-SNARKs 的实现分为以下几个步骤:

原文链接:https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Exploring Elliptic Curve Pairings

这篇文章介绍了椭圆曲线配对:

原文链接:https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

Zk-SNARKs: Under the Hood 这篇文章主要介绍了匹诺曹协议。

原文链接:https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

computational problem —> 电路

电路 —> R1CS

R1CS —> QAP

QAP —> Linear PCP

Linear PCP —> Linear Interactive Proof

Linear Interactive Proof —> zkSNARK

推荐文章十四:zcash 官方科普文

推荐值:❤️❤️❤️❤️

难度值:⭐️⭐️⭐️⭐️

这个系列的文章来自 zCash 官方博客。首先介绍了零知识的基本概念以及其应用到 zcash 中的大致思路。随后 7 篇文章分别对 7 个关键点进行了详细介绍(同态隐藏,多项式盲验证,KCA,完整的多项式盲验证,计算到多项式的转换,匹诺曹协议以及椭圆曲线配对),推荐给想深入了解 zk-SNARKs 实现原理的小伙伴。

原文链接:What are zk-SNARKs?:https://z.cash/technology/zksnarks/

Explaining SNARKs Part I: Homomorphic Hidings https://electriccoin.co/blog/snark-explain/

Explaining SNARKs Part II: Blind Evaluation of Polynomials https://electriccoin.co/blog/snark-explain2/

Explaining SNARKs Part III: The Knowledge of Coefficient Test and Assumption https://electriccoin.co/blog/snark-explain3/

Explaining SNARKs Part IV: How to make Blind Evaluation of Polynomials Verifiable https://electriccoin.co/blog/snark-explain4/

Explaining SNARKs Part V: From Computations to Polynomials https://electriccoin.co/blog/snark-explain5/

Explaining SNARKs Part VI: The Pinocchio Protocol https://electriccoin.co/blog/snark-explain6/

Explaining SNARKs Part VII: Pairings of Elliptic Curves https://electriccoin.co/blog/snark-explain7/

中文翻译版本链接:https://www.jianshu.com/p/b6a14c472cc1、https://www.jianshu.com/p/92f54fc08d58