零知识证明定义
零知识证明：zkSNARK，zero-knowledge Succint Non-interactive ARguments of Knowledge 的简称：
零知识证明示例———以数独为例
证明
有一天，小明出了一道非常难的数独题，小红花了很长时间尝试去解开这个数独，但是怎么都解不出结果。小红觉得小明在耍她，“这题压根就无解！小明你耍我！”，她跑到小明那抱怨。“我能证明给你看这题是有解的，而且我知道这个解”，小明淡定的回答道。“好啊”，小红暗自想着，“哼哼，等你证明给我看之后，我就把解记下来然后去戏耍下小刚，给他也做一下这题。”小明接着说：“我会用零知识证明的方法给你证明我会这题的解。也就是说我不会把解给你看，却能让你信服我确实有这题的解。”小红并不相信他能这样做到，还在想象小刚被耍的样子。小明拿出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)，称为加法同态：
零知识 - 证明者和验证者之间除了“问题证明与否”知识外，不知道其他任何知识（不知道随机挑选值，不知道挑选值的多项式计算结果等等）。
多项式问题转化
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 问题。布尔公式定义如下：
一个布尔公式可满足，指输入是 0/1 的情况下，存在输出为真。SAT 问题指，找出所有可满足的布尔公式。SAT 问题看上去，除了枚举一个个可能的布尔公式外，没有更好的办法，也就是多项式时间内不可解。如果知道一个可满足的布尔公式，验证非常方便（输入是 0/1 的情况下，看看输出是否为真）。SAT 问题是 NP 问题。
再看看另外一个 NP 问题：PolyZero 问题。PolyZero 问题指某个多项式满足：多项式输入是 0 或 1 的情况下，多项式输出为 0。
PolyZero(f):=1
f 满足输入是 0/1 的情况下，多项式输出为 0。
一个布尔表达式 f 可以通过如下的归约函数 r，转化为多项式：
也就是说，一个 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) 。
多项式证明问题举例
多项式问题的证明过程
假设一个多项式
证明一个多项式，即给定一个输入 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′。
很显然，验证者从A′无法推导出E(f(s))，但验证者一样能验证α对的配对函数是否成立：
多项式证明问题举例--整体过程
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和α的计算结果
多项式的α对的计算结果
多项式的βv,βw,γ 参数的计算结果
4.2 证明者提供证据
在 QSP 的映射函数中，如果 2n < m，1, ..., m 中有些数字没有映射到。这些没有映射到的数字组成Ifree，并定义（k为未映射到的数字）：
证明者需提供的证据如下
4.3 验证者验证
在 QSP 的映射函数中，如果 2n < m，1, ..., m 中所有映射到的数字作为组成系数组成的二项式定义为（和vfree互补）：
验证者需要验证如下的等式是否成立：
至此，zkSNARK 的推导逻辑就基本完整。使用 zkSNARK 证明，由如下的几步组成：
推荐文章
推荐文章一：一个数独引发的惨案：零知识证明（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://ethfans.org/posts/zero-knowledge-proofs-an-illustrated-primer-part-2