ZKP入门

交互式证明是可验证计算概念的核心概念。最重要的是，交互式证明理论为非交互式零知识证明 (NIZK)、简洁非交互式知识论证 (SNARK) 或简洁透明知识论证 (STARK) 奠定了基础。

简介

什么是证明系统

交互式证明系统是一种抽象的机器，它将通过计算建模为双方之间交换信息，分别称为证明者$P$和验证者$V$。

证明者无所不能，拥有无限的计算资源，但不可信任。

验证者的计算能力有限。

验证者和证明者之间会不断发送消息，直到验证者能够验证或伪造某个陈述。

所有交互式证明系统都具有两个关键属性：

完整性：当陈述是真实的，诚实的验证者可以通过诚实的证明者确认这一事实。

健全性：当陈述是错误的，除去可忽略不计的概率，没有恶意的证明者可以欺骗验证者。

零知识保护隐私

证明系统的第三个属性：

**零知识：**如果陈述为真，那么没有任何作弊验证者会了解除此事实之外的任何其他信息。

零知识的阿里巴巴洞穴：

有一个洞穴，它的路径一分为二。这两条路径由一扇门连接，这扇门只能用密码打开。一个人叫爱丽丝，想向另一个人鲍勃证明她知道密码，而不会泄露它。为此，双方首先将自己置于洞穴的入口处。然后爱丽丝进入洞穴，沿着两条路径中的一条走——这取决于她自己。鲍勃从入口无法判断爱丽丝选择了哪条路。

然后鲍勃进入洞穴，跑到岔路口。他选择两条路径中的一条，并称这条路径进入洞穴。爱丽丝的任务是通过这条路径找到鲍勃。如果她成功了，她就离向鲍勃证明她知道秘密单词的目标更近了一步。

如果 Alice 选择了 Bob 选择的路径，她就不需要密码。只有当她选择相反的路径时，她才必须通过门才能走上正确的路径。这意味着，一个心怀恶意的 Alice（她不知道密码）在一次运行该协议时只能说服 Bob 50%。（这就是为什么 Alice 和 Bob 必须重复执行该协议以降低健全性错误概率的原因。）该协议是一个零知识证明，因为无论 Alice 和 Bob 重复该过程多少次，如果 Alice 知道密码，她将始终遵循 Bob 选择的路径。与此同时，Bob 对秘密一无所知。

识别方案

身份识别方案的根本思想是，Alice 知道一些秘密（与她的身份直接相关），并且她向 Bob 证明自己知道这些秘密。为了防止将来有恶意的 Bob 冒充 Alice，协议要求 Bob 不得了解有关 Alice 秘密的任何部分信息。反之亦然。

正式定义

我们用图灵机来正式定义这个证明系统。

交互式图灵机

交互式图灵机 (ITM) 是一种（确定性）多磁带图灵机。

磁带包括一盘只读输入磁带、一盘只读随机磁带、一盘读写工作磁带、一盘只写输出磁带、一对通信磁带，以及由单个单元组成的读写切换磁带。一盘通信磁带是只读的，另一盘是只写的。

输入磁带的内容称为输入，随机磁带的内容称为随机输入，终止时输出磁带的内容称为输出。

两台交互式图灵机

我们称交互式图灵机$M_1$为证明者$P$，$M_2$为验证者$V$，所使用的语言为$L$。

正确陈述：$(x,w)\in L$，错误陈述：$(x,w)\notin L$

其中，值$x$是公开的，$P,V$都知道，参数$w$（见证）是私有的，只有证明者知道。

语言$L$被定义为某个有限字母表上的一组字符串，并根据一组特定的规则形成。

例如$\Sigma=\{0,1,2,-,=\}$上的语言$L$具有以下语法：

• 所有不包含-和=且不以0开头的非空字符串都在$L$
• 包含“=”的字符串在$L$中当且仅当存在一个“=”，并且它将L中的两个有效字符串分隔开

交互式证明系统

一对交互式图灵机$(P,V)$被称为语言$L$的交互式证明系统，应当满足以下条件：

• 完整性：对于语言$L,(x,w)$，证明者$P$能够说服验证者$V$的概率十分大：

$\forall (x,w)\in L,Pr[<P(x,w).V(x)>=1] \le 1-negl$

• 健全性，对于所有不属于语言$L,(x,w)$，证明者$P^\prime$通过作弊的手段说服验证者$V$的概率可以忽略不计。

$forall (x,w)\notin L, Pr[<P^\prime(x),V(x)>=1] \le negl$

• 特殊健全性，对于$L,(x,w)$，都能在一个多项式时间算法$E$，使得可以从$P,V$的有效对话中提取出证据$w$

$\forall (x,w)\in L, \exist E:Pr[E<P(x,w),V(x)>=w]\le 1-negl$

• 零知识：对于$L,(x,w)$，对于所有验证者，都存在一个模拟器$S$，使得没有多项式时间区分器$D$可以区分模拟协议的执行与$P,V$之间的真实交互的执行。

$forall (x,w)\in L, \forall V \exist S,Pr[D(P(x,w),V(x))=1]-Pr[D(S(x))=]$

Schnorr协议

Schnorr协议有三轮，定义在$q$阶循环群$G$上，生成器$g$，语言$L=\{(x,w):x=g^w\}$

Schnorr协议

Setting

• $P$有秘密输入$w$和公开输入$x=g^w$
• $V$只有公开输入$x=g^w$
• $P,V$都有公共参数$g,q$

Protocol

• $P$生成一个随机群元素$h$并且采样一个随机数$r$，然后发送$a=g^r$给$V$
• $V$选择一个随机挑战$e\in {0,...,q-1}$并发送给$P$
• $P$回应挑战$z=r+ew$
• 当且仅当$g^z=ax^e$，$V$才接收响应。

安全性分析

完整性

$\forall r,e: g^z=g^{x+ew}=g^zg^{we}=a$