简单介绍一下zk-SNARKs，主要按照论文的思路，之前的文章也都大致介绍了一下，可以参考零知识分类下前几期的文章，关于zk-SNARKs的正式定义在$[BCI+13]$，感兴趣的可以看一下

2.1 Informal definition

对于域$\mathbb F$，$\mathbb F$-算术电路以域上元素作为输入，其电路门的输出也为域上元素，此时将电路及其计算的函数关联起来

由于不确定性，考虑具有输入$x\in \mathbb F^n$和额外输入$a\in \mathbb F^h$的电路（此时$a$称为证据），且该电路仅涉及双线性门

双线性门指的是，对于给定的$m$个输入$y_1,...,y_m\in \mathbb F$，当对于向量$\vec a,\vec b\in \mathbb F^{m+1}$，若有门输出 $<\vec a,(1,y_1,...,y_m)> \cdot <\vec b,(1,y_1,...,y_m)>$时，称门是双线性的，通常包括加法门，乘法门，取负门和常数门

此时算术电路可满足性的定义类似于布尔电路的情况

算术电路可满足性问题：对于一个$\mathbb F$-算术电路C：$\mathbb F^n\times \mathbb F^h\rightarrow \mathbb F^l$，由关系定义$\mathcal R_C=\{(x,a)\in \mathbb F^n\times \mathbb F^h\rightarrow \mathbb F^l:C(x,a)=0^l \}$，对应的语言为$\mathcal L_C = \{x\in \mathbb F^n:\exist a\in \mathbb F^h \ s.t. C(x,a)=0^l\}$

对于给定的域$\mathbb F$，关于$\mathbb F$-算术电路的（公开可验证的）zk-SNARK为下列三个多项式时间的算法

  • $KeyGen(1^\lambda,C)\rightarrow (pk,vk)$：输入安全参数为$\lambda$和一个域$\mathbb F$-算术电路$C$，KeyGen算法概率性的确定证明密钥$pk$和验证密钥$vk$，这两个密钥都会做为公开参数公布并可以对语言$\mathcal L_C$使用任意次数
  • $Prove(pk,x,a)\rightarrow\pi$：对于输入$pk$和任意的$(x,a)\in \mathcal R_C$，Prove算法输出一个非交互式的证明串$\pi$，满足$x \in \mathcal L_C$
  • $Verify(vk,x,\pi)\rightarrow b$：对于输入$vk$，$x$和证明串$\pi$，若有$x \in \mathcal L_C$，则Verify算法输出$b=1$

当然，作为零知识证明，zk-SNARK也需要满足下列特性

  • 完备性：对于任意的安全参数$\lambda$，任意的$\mathbb F$-算术电路$C$，任意的$(x,a)\in \mathcal R_C$，诚实的Prover总是可以使Verifier相信，也即$b=1$的概率为$1-negl(\lambda)$
  • 简洁性：诚实生成的证明$\pi$的大小为$O_\lambda(1)$比特，Verify算法运行时间为$O_\lambda(|x|)$（$O_\lambda$表示关于$\lambda$的多项式）
  • 知识证明（以及合理性）：若Verifier接受一个由有界Prover生成的证明，则该Prover确实有一个关于给定陈述的证据，具体而言，合理性仅对有界Prover成立，也即对于一个关于$\lambda$的多项式大小的敌手$\mathcal A$，存在一个关于$\lambda$的多项式大小抽取器$\boldsymbol\epsilon$，满足$Verify(vk,x,\pi)=1$且$(x,a)\notin \mathcal R_C$的概率为$negl(\lambda)$
  • 完美零知识性：诚实生成的证明$\pi$为完美零知识的，也即存在一个多项式时间的模拟器Sim，对于所有有状态的区分器$\mathcal D$，下列两个概率相等

$$ Pr[(x,a)\in \mathcal R_C,\mathcal D(\pi)=1|(pk,vk)\leftarrow KeyGen(1^\lambda,C),(x,a)\leftarrow\mathcal D(pk,vk),\pi\leftarrow Prove(pk,x,a)] \\ Pr[(x,a)\in \mathcal R_C,\mathcal D(\pi)=1|(pk,vk,trap)\leftarrow KeyGen(1^\lambda,C),(x,a)\leftarrow\mathcal D(pk,vk),\pi\leftarrow Sim(trap,x)] $$

前者为诚实生成的证明$\pi$，后者为模拟器生成的证明，区分器输出的概率相同

这里有两点需要注意

  1. 考虑到验证密码原语断言的电路$C$，知识证明和零知识对于zk-SNARK的使用都是必不可少的（例如将知道SHA256前像这一知识作为绑定承诺），因此对于给定的输入$x$，仅仅知道证据$x\in\mathcal L_C$存在是不够的，相反，只要Verifier接受证据，知识证明就可以确保有效地找到证据（通过抽取器从Prover那里抽取证据），而零知识确保除了$x\in\mathcal L_C$以外，证明不会泄露关于证据的任何信息
  2. 在安全证明中，将Prover产生输入的向量$\vec x$和证明向量$\vec \pi$一起处理（参见原文附录D）

2.2 Comparison with NIZKs

zk-SNARK与非交互式零知识知识证明（NIZK）有些相似

  1. 两者都需要进行一次性的可信公共设置（Trusted Setup，zk-SNARKs中为证明/验证密钥对，NIZK为CRS）
  2. 两者都提供完整性、知识证明、零知识性

区别在于两者效率，NIZK的证明长度和验证时间取决于被证明的NP语言，以电路可满足性举例，NIZK的证明长度和验证时间与电路大小的关系是线性的

zk-SNARK的证明长度仅与安全参数相关，而验证时间取决于实例大小和安全参数，与电路大小或证据大小都无关，因此zk-SNARK可以被认为是“简洁的NIZK”，不仅证明时间短，验证时间快

不过zk-SNARKs的结构依赖于比NIZK更强的密码学假设

2.3 Known constructions and security

zk-SNARK结构有很多，本文主要关注基于QAP的zk-SNARK的构造，因为此类构造可以提供线性时间的密钥生成，亚线性时间内生成，线性时间内完成验证

zk-SNARK的安全性基于双线性群中的指数知识假设和Diffie–Hellman假设变体的知识，虽然指数假设的知识相当丰富，但目前的研究表明这种假设可能是构造zk-SNARK的固有条件

完全简洁的zk-SNARKs：之前提到的KenGen算法以电路C作为输入，因此KeyGen运行时间至少为电路大小的线性阶，不过可以做到不将整个电路作为KeyGen的输入，而是将其输出适用于任意（多项式大小的）电路，此时KeyGen算法的运行时间与电路大小独立

若zk-SNARK满足上述性质，则称为完全简洁的zk-SNARK，目前已知的理论构造完全简洁的zk-SNARKs基于一些密码学假设，详情可以看$[Mic00, Val08, BCCT13]$

2.4 zk-SNARK implementations

关于zk-SNARK的实现，主要有三种方式（2014年），如$[PGHR13]$中可以为没有数据依赖关系的程序提供zk-SNARK

没有数据依赖指的是数组索引必须是编译期已知的常量，且循环或迭代的次数或上界也是编译期已知的

$[BCG+13]$提出了一种针对任意程序（具有数据依赖性）的zk-SNARK实现，$[BCTV14]$提出了一种zk-SNARK的实现，它支持修改自己代码的程序（例如，用于生成运行时代码），该方案中还极大降低了大型程序的时空成本，还可以使用通用密钥对

本文基于$[BCTV14]$来实现zk-SNARK，其提供的128位的安全性

后记

这个方案毕竟是14年的，用的zk-SNARKs方案也都是旧的，近些年也有不少的zk-SNARK的优化，现在有更好的更快的算法了，比如之前文章提到的Groth16，还有19年的Sonic、SupoerSonic、Plonk等算法，后续有时间的话再慢慢介绍

本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正

参考文章

$[1]$[Zerocash: Decentralized Anonymous Payments from Bitcoin
(extended version)](http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf)