零知识证明原理

2023-11-08

零知识证明

定义：证明（Prover）向验证者（Verifier）证明一个命题成立，同时不泄露其他任何知识，这种就被称为零知识证明。

应该具备以下三个性质：

1.完备性：若一个证明方确实掌握了某论断的答案，则他肯定能找到方法向验证方证明他手中掌握的数据的正确性，即真的假不了。

2.可靠性：若一证明方根本不掌握某论断的答案，则他无法（或只能以极低概率）说服验证方他手中所谓答案的准确性，即假的真不了。

3.零知识性（Zero-knowledgeness）：验证方除了知道证明的结果外，对其他信息一无所知。

可以从两个方面判断是否是zk：第一是否是零知识，第二是证明可靠。

npc问题无法在多项式时间内求解，但可以在多项式时间内被验证。

schnorr协议

G是阶素数q的有限循环群：
Alice生成随机数r，根据椭圆曲线基点G，计算R=r*G，将R发送给Bob；
Bob生成随机数c（称作挑战challenge），将c发送给Alice；
Alice计算z=r+c*a，将z发送给Bob；
Bob验证z*G，即(r+c*a)*G是否等于R+c*(a*G)。

上面是交互式零知识证明，存在一定的缺陷：

他也有非交互式的零知识证明：简称IZK

NIZK版本取消了Bob人工的随机challenge，而是使用Hash(PK, R)来表示随机challenge，相当于引入了一个虚拟的第三方（数学之神）来产生随机数 c，并且证明者和验证者都认可这个第三方生成的随机数（Hash 值）。

值得一提的是，在「禁忌」中明确写有「验证者不随机」。换句话说，在NIZK中，我们需要challenge c是由一个完全随机的预言机生成的，而这个理想中的「随机预言机」和上图中的Hash(PK, R)还是有很大区别：

随机预言机每次对于新字符串返回的是一个具有一致性分布的「真」随机数
Hash 函数计算的结果并不是一个真正具有一致性分布的随机数

既然Hash 函数并不是我们理想中的随即预言机，那我们为什么还信任使用Hash 函数的Schnorr NIZK协议呢？这是因为我们假设「一个具有密码学安全强度的Hash 函数能够近似地模拟随机预言机」，默认这个假设的模型被称为「标准模型」，不默认这个假设的模型称为「非标准模型」。这种使用Hash 函数将IZK变成NIZK的方法，被称为「Fiat-Shamir 变换」。

公共参考串

除了随机预言机，NIZK还能采用「公共参考串」（Common Reference String），简称「CRS」来生成随机challenge c。如果说「随机预言机」是隐式地引入了第三方，那么「公共参考串」就是直接显式引入第三方。

任何NP问题都能在多项式时间内规约到哈密尔顿回路问题，所以基于NP问题的IZK都能通过使用CRS变成NIZK形式了。

zk-Snark

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

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

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

1.多项式问题转化

2.随机挑选验证

3.同态隐藏

4.零知识

1.NP问题以及约化

NP问题指的是不能在多项式内可解，但是可以验证。

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

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

QSP问题

需要确定一个NP问题，如果解决这个NP问题，其他NP问题也都能解决，因为可以进行一个约化。

QSP问题是一个NP问题。

多项式问题的证明过程

1.有限群论基础

有限群，生成元是g，阶是n，群里面有如下元素，g0，g1,…,gn-1;有限群的加密方式很简单，E(x)=g^x,知道gx,不能计算出x;

2.选定随机数

验证者随机选择有限群里面的一个随机述s，提供如下的计算结果：

E(s^0),E(s1),…,E(s^d);生成这些计算结果之后，s就可以丢弃了。

3.E（f(s)）计算

在这里插入图片描述

4.a对

验证者并不知道多项式的参数，即使证明者E(f(s)),验证者并不知道，无法验证，a对可以解决这个问题，a对可以让验证者确认证明者是通过多项式产生的。在2的基础上，还需要选择另外一个a，计算出：

在这里插入图片描述

证明者需要提供E(f(S))和E(af(s)):
在这里插入图片描述

6.配对函数

配对函数也叫双映射函数，满足：
在这里插入图片描述

验证者验证a对方式很简单：

在这里插入图片描述

到目前为止，验证者在不知道多项式系数的情况下，证明者可以证明通过某个多项式计算出某个结果。

7.偏移

更进一步的话，采用偏移量，甚至不想让验证者知道E(f(s)),证明者随机一个参数，提供A‘和B’,验证过程如下所示：

在这里插入图片描述

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

QSP问题的skSNARK证明

证明分为两个部分：1）setup部分 2）证明阶段

QSP问题就是给定一系列的多项式v0…vm,w0…wm，以及目标多项式t，证明存在一个证据，多项式中最高的阶是d。

1）setup和CRS：

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

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oGMFkSqr-1688803833657)(C:\Users\32219\AppData\Roaming\Typora\typora-user-images\image-20230708160543153.png)]$

在这里插入图片描述

2）证明部分：

这里面还是有一点没看太懂，着急面试稍后再继续更新。

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

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

笔记