全面理解零知识证明

原文标题：《分析｜零知识证明》

原文作者： CryptoYC Tech，CryptoYC Labs

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

零知识证明定义

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

Succinct：证明的数据量比较小

Non-interactive：没有或者只有很少交互。

ARguments：验证者只对计算能力有限的证明者有效。拥有足够计算能力的证明者可以伪造证明。这也叫「计算可靠性"（相对的还有」完美可靠性"）。

ofKnowledge：对于证明者来说在不知道证据（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)。

多项式证明问题举例

多项式问题的证明过程

假设一个多项式

证明一个多项式，即给定一个输入 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 证明，由如下的几步组成：

问题转化：一个需要证明的 NP 问题转化为选定的 NP 问题（比如 QSP 问题）

设置参数（setup）：设置参数的过程也是挑选随机数的过程，并提供 CRS

证明者获取证据 u，通过 CRS 计算证据（proof）

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

原文链接