本部分主要从一些计算理论和证明系统的范式出发，来介绍自底向上构建一个ZKP系统的大致流程
Abstract
现阶段有许多种不同的ZKP系统，在通信量、计算开销和密码学假设之间平衡，其中一些系统可被分解为信息论证明系统（Information Theoretic Proof System，ITPS），然后利用一个密码学编译器（Cryptographic Compiler）将IT系统编译为真正的ZKP系统
- Information Theoretic Proof System：对于信息论证明系统而言，可以利用其来在某些较为极端的情况下提供证明，即使Prover和Verifier在计算上是无界的，该证明系统也能提供可靠性和ZK保证
不过ITPS使用了一种理想化的交互模型，通过某种理想的方式，限制、结构化或增强了Prover和/或Verifier的能力，一种常见的理想化模型提供了对一些黑匣子通信功能的访问，这些功能将由密码编译器具体实现
例如可以让Prover生成一个很长的证明向量，然后只允许Verifier对该向量进行有限的访问，比如只限制Verifier查询向量中的几个元素，不查看其余元素，也不让Prover根据查询更改（提前对整个向量承诺）
另一个常见的例子是理想承诺，其中一方可以通过将某个值发送到受信任的预言机（同时将其隐藏）来承诺该值，然后允许另一方检索该值（通过承诺方案来确保该值没有更改）
理想化的模式也会对参与方施加限制：例如受限的Prover可以由多个单独的多个参与方组成，这些参与方在协议开始前可以相互协调，但在协议执行期间不能相互通信，然后允许Verifier分别对这些参与方发起挑战，并比较每个挑战收到的的答案是否一致，在这种情况下，密码编译器展示了如何将理想化的方转换为不受人为限制（但可能在计算上有界）的真实的参与方方
- Cryptographic Compiler：密码学编译器的目的是将ITPS统转换为真实世界协议，该协议涉及Prover和Verifier之间的直接交互，此时前面提到的关于互动模型和各方能力的理想化假设会被消除了（通常是通过强制执行这些假设，这样就不再需要公理化假设了）
上述方法通常依赖于更简单的加密构建块的协议来完成的，密码编译器使用某些密码学原语然后通过（可能是启发式的）将该原语具体实例化来实现（比如Hash函数或配对友好的椭圆曲线），从而可以得到一个可以在现实应用中实现和使用的具体方案
底层构建块可以是密码原语（比如抗碰撞Hash函数或同态承诺方案），在这种情况下，ITPS与编译器组合的安全性取决于这些原语实现中的密码假设（目前而言，这些假设通常仅适用于计算有界的参与方）
或者编译器可以通过引入新的理想化原语（旨在捕获更细粒度的局部假设，比如随机预言机模型或者通用双线性群），以此来消除ITPS假设中的高级理想模型，在这种情况下，系统的安全性在一些理想的模型假设下是成立的（例如，限制对随机预言机的查询数量）
而现实世界的实现要么使用进一步的编译器（例如，在明确定义的假设下实现细粒度模型的必要属性），要么是启发式的（直觉上可信，但没有正式证明的转换方式），此类情况下由CC得到的方案仍然仅适用于计算有界的参与方
密码编译器还可以提供额外的期望属性，例如消除交互、缩小某些消息的大小，甚至为没有ZK功能的ITPS添加ZK功能
无论是ITPS还是CC，一定会牵扯到效率的问题，由于不同系统的软硬件不同，通常在协议设计时不考虑实际执行结果（不考虑具体需要的时间和内存等实际参数），而是通过复杂度的方式来描述
复杂度描述了系统的计算属性，包括证明长度，轮复杂度，查询复杂度（查询次数和查询长度），域（字母表）大小，V的决策谓词的复杂度（验证复杂度）
以证明的简洁性为例（proof succinctness），其区分为如下几个等级
- Fully succinct：只需要$O(1)$个密码学元素，证明长度与statement大小独立
- Polylog succinct：证明元素与电路大小呈对数多项式关系
- Sqrt succinct：与电路大小呈平方根关系
- Depth succinct：取决于表示statement的电路的深度
- Non succinct：证明长度和电路大小之间的关系不为亚线性的（sublinear）
SNARK$[BCCGLRT17]$中提出了一种简洁的非交互式知识论证的表示方式，除此之外，还有一些相关的名词
- Complexity reference：复杂度的度量应当考虑上下文，是否只考虑statement和instance，或者witness的复杂度也很重要，证明长度的复杂度是否与statement有关等等
以及其他一些感兴趣的特性
- setup trust：所有非交互式的ZKP需要一系列的全局公共参数，这些参数需要所有的参与方均认可，若这些参数是随机选择的（比如通过hash某些名人说的话），则此时我们称该系统具有公共掷币（public coin）的初始设置（或无信任的初始设置，trustless setup），此类情况是最理想的
若全局公共参数室友可信参与方或通过多方计算得到的，则此时称为可信设置（trusted setup）或秘密掷币设置（private coin setup），在这种情况下，参与多方计算的可信方或所有各方的联盟都能够伪造证据
可信设置可以是通用的，也可以是针对特定语言的，通用设置允许一次设置用于多个不同的语言，且可以提供比依赖于语言的设置更强大的灵活性
- Types of primitives：比如对称密码算法，抗碰撞hash函数，随机预言机，公钥密码等等
第三节介绍一些主流的信息论证明系统，第四节介绍密码学编译器，第五节介绍证明系统的一些其他性质
3 Information-Theoretic Proof System
ITPS本质上是一种不依赖于密码学假设的证明系统，且可以产生易于理解的构造
先看一下ITPS的大致结构
上面这个图里面的大部分名词在上一篇博客的第二节中都有介绍，那里给出了所有名词的论文出处，这里补充几个没提到的
- Fast RS IOPP（Fast Reed-Solomon IOP of Proximity）：典中典，STARK用了这个
- ILC（Ideal Linear Commitment）：
- QSP（Quadratic Span Program）：
- SSP（Square Span Program）：
这些证明系统大部分都会涉及下列三种查询类型，如下
- 若V向证明$\Pi$发起一个点查询(point query)，则表示其访问预言机$O^\Pi$，并以$i$为输入，获取证明的第$i$个符号$\Pi(i)$
- 若V向证明$\Pi\in \mathbb F^m$发起一次内积查询（inner-product queries），则表示其以向量$q\in \mathbb F^m$为输入，并返回一个域上的值$<\Pi,q>\in \mathbb F$
- 若V向证明$\Pi\in \mathbb F^{m\cdot k}$发起一次矩阵-向量查询（matrix-vector queries），则表示其以向量$q\in \mathbb F^k$为输入，并返回一个矩阵与向量的乘积$(\Pi.q)\in \mathbb F^m$
总结一下，在statement的经典证明中，P发送一个字符串$\pi$以供V读取，然后V当且仅当该串传递了statement的有效性和可验证性时，V接受该证明串（最简单的例子是P直接给V发送witness）
对证明的检查也有不同的方向，比如基于交互的（证明来自于交互，而不是对证明串的分析），基于论证（argument）的（论证中的确定性不是绝对的，但是是压倒性的），这些方向通常也都具有ZK的性质
本节主要介绍一些证明系统经常使用的理想组件，但不一定是满足ZK的IT系统，不过可以利用CC编译为满足简洁性和ZK性的证明，大致如下
- PCP：P向V发送一个（很可能非常长的）证明串$\pi$，V对该证明串发起线性数量的请求，并结合statement来判断是否接受
- Linear PCP：P向V发送一个（很可能非常长的）证明串$\pi$，该证明串位于向量空间$\mathbb F^m$中，V对该证明串发起线性数量的请求，并结合statement来判断是否接受
- MPC in the head：证明可以有具有半诚实安全性的模拟多方安全计算执行的视角组成，witness为模拟方之间的秘密共享，之后模拟方安全的计算ZKP predicate
此类组件中，部分交互脚本同时确保了合理性和ZK性
- IOP：属于一种广义化的PCP
考虑交互设置，每一轮交互中，V向P发送挑战串$C_i$，然后P响应一个PCP证明$\pi_i$，V可以发起多次点查询，然后判断是否接受P
- Linear IOP：线性PCP的广义化，每轮交互中P发送一个证明向量$\pi_i$，然后由V发起先行次数的（内积）查询
- ILC：和线性IOP比较相似，但是每一轮中P向V发送一个证明矩阵（而不是证明向量），V可以知道该矩阵和请求向量的乘积
每个ILC证明矩阵的输出可能是与输入和V的消息相关的任意函数（不局限于线性函数）
3.1 Probabilistic Checkable Proof（PCP）
P发送第一条消息，若存在合法的witness，则P可以在随后的消息中说服V
这里举一个PCP证明经典例子——3COL问题来解释PCP，之后再对PCP信息论范式和PCP定理提供更精确的解释
Classical 3-coloring proof
来自$[GMW91]$，instance为一个无向图$G=(V,E)$，statement为图$G$可三染色，witness为一个三染色方案（染色表示为$c=\{1,2,3\}$，关系表示为$R_{3COL}$（该关系为NPC关系，其存在一个ZKP证明意味着其他所有NP语言均有ZKP证明），具体证明协议如下
- P输入$(G,c)$，选择一个随机置换$\phi:\{1,2,3\} \rarr \{1,2,3\}$，然后令$c'(v)=c(\phi(v))$表示打乱后的染色
- 对于所有的结点$v\in V$，P对该节点打乱后的染色$c'(v)$进行承诺（真实协议执行中P需要向V发送该承诺值）
- V随机选择一条边$(u,v)\in E$，请求P打开该边
- P揭示对应边的承诺$c'(u),c'(v)$
- V当且仅当揭示的两条边的颜色不同时接受P
安全性分析：分析上述协议的三个安全性
- 完备性：若染色$c$为合法的，则其置换$c'$也是合法的，因此诚实的P总是可以说服诚实的V（因为P总是会揭示一条不同颜色的边）
- 零知识性：P只揭示了置换后的染色方案（可以通过模拟来选择任意一条具有不同颜色的边来展示给V），该性质在针对选择任意的$u,v$的V时也成立
- 合理性：若$G$不可三染色，则恶意的P无论如何选择$c$的置换$c^*$，都会有至少一条边，满足$c^*(u)=c^*(v)$，此时V拒绝P的概率为$\frac{1}{|E|}$，该合理性可以通过独立多次执行该协议来增强其合理性（同时不会损失零知识性），不过不能并行执行（并行会损失其零知识性）
Form PCP theorem
通常而言，一个关系的PCP要求P在概率多项式时间内将statement-witness对$(x,w)$映射到证明串$\pi\in \Sigma^m$中，V请求$\pi$的一个随机字节（字符），并决定是否接受P
PCP的关键点在于P生成证明时，不知道V会发起哪个请求，具体而言，V需要将instance随机映射到一个请求符号子集$Q\subset [m]$和决定谓词$D(x,Q,\pi_Q)$，并基于该谓词决定是否接受P
具体的PCP定理$[Mic00,Kil92]$如下
对于所有NP预压均存在一个高效的PCP，通信复杂度为对数阶
零知识PCP（zk-PCP）表示满足零知识性的PCP证明系统
3.2 Linear PCP
PCP及其相关定理很强大，但是开销也不小：因为P需要生成一个很长的证明，且其中的大部分可能都不会被V读取
不过这些开销可以通过改变理想模型来减少，比如可以构造一个更具有代表性的查询来代替原来的查询，此时P只需要生成一个更短的证明，V以一个更大的查询空间完成查询
标准PCP中限制V发起一定数量的点查询来读取证明串中每个独立的符号，而线性PCP允许V每次查询$\pi$的任意一个线性组合，具体而言，域$\mathbb F$上的线性PCP证明为一个向量$\pi \in \mathbb F^m$，V的每个查询是一个向量$q_i\in \mathbb F^m$，查询返回的结果为证明向量与查询向量的内积结果$<\pi,q_i>$
与标准PCP相比，除了查询方式不同以外，线性PCP中还要求查询$q_i$为输入忽略的（input-oblivious），意思是查询与instance无关
对于LPCP的构造，可以从任意NP关系构建LPCP，得到的证明系统的证明大小为$m$，合理性错误为$O(\frac{1}{\mathbb F})$，查询次数为某一常数（查询复杂度为$O(1)$）
线性PCP的主要开销在于密码学编译器，因为其需要来自公钥密码学中的强大原语来满足LPCP的高效率，不过$[IKO07]$给出了一个低通信量的LPCP的实现，方式是利用更简单的PCP来代替复杂的PCP，但是代价是其依赖于更强的密码学假设
然而除了简单性之外，这种新方法还可以带来传统的基于PCP的方法无法实现的效率特征：P到V的通信只包括恒定数量的“密文”或群元素，与$R$的复杂性无关，下面描述两种类型的线性PCP：基于Hadamard的和二次算术程序（QAP），这些是当前文献中最常用的线性PCP，此外还有一些其他类型的线性PCP，包括二次跨度程序（QSP）、平方跨度程序（SSP）和基于线点（Line Point）的PCP，这里不再展开讨论
3.2.1 Hadamard based
在基于哈达玛的LPCP中，可以将NP关系视为一个域$\mathbb F$上的算术电路，其中电路中的门为域上的加法和乘法，此类证明中P可以向V证明其知道一个witness $w\in \mathbb F^m$，满足$C(x,w)=0$
这里的$C,x$作为公共输入，首先会被转化为一个包含$s$个等式的系统，每个等式满足$Q_i(Y)=0$，且每个等式均为$s$个变量$Y_1,...,Y_s$的多项式，度小于等于2，若有$w$满足$C(x,w)=0$，则意味着存在一个$y\in \mathbb F^s$，满足$\forall i,Q_i(y)=0$
基于哈达玛的LPCP中，P首先利用$(x,w)$，为电路中所有$s$个门计算一个向量$y\in \mathbb F^s$，然后计算一个二次大小的向量$\hat y\in \mathbb F^{s^2}$，其中$\hat y_{jk}=y_i\cdot y_k$，然后P输出证明串$\pi =(y,\hat y)$，此时$y$中所有度为2的多项式都可以通过一次对$\pi$的线性查询来得到
此时V的请求需要完成两个检查：
- 用张量关系检查$\pi$两个部分的一致性
- 对于所有的$Q_i$，检查其是否满足条件$Q_i(Y)=0$
第一个检查可以通过计算$y$的两个随机线性组合$(\sum_{j=1}^sr_jy_j)^2$，并比较这两个之间的差异来完成：首先直接查询$y$，然后查询对应的线性组合$r_jr_ky_jy_k$
第二个通过请求$Q_i(y)$并验证其是否等于0来实现，上述过程的合理性由Schwartz-Zippel引理保证
这里有两个概念需要注意
- Fast Verification：快速验证是一种与输入独立的预处理过程
这个性质很重要，因为生成查询$q_i$的开销会随着验证电路的增大而增大，若V可以在输入$x$之前就生成对应的查询$r_1,...,r_n$，并在稍后的协议执行中使用的话会很方便
一旦知道了$x$，V就可以在线性复杂度内计算$\alpha = \sum_i r_ix_i$，在随后的LPCP响应中，V只需要常量次数的域运算就可以判断是否接受
快速验证的性质非常适用于重复使用相同的查询来检查多个不同的证明语句
- Reusable soundness：基于哈达玛的LPCP的另一性质为可重用合理性，其要求同一个查询在验证多个不同的证明时可重用
举个例子，对于任意的$x,\pi^*$，P可以基于$x,\pi^*$来预测V是否接受，错误概率为$O(\frac{1}{|\mathbb F|})$（此类情况下V会使用未知的随机查询），这意味着当域$\mathbb F$足够大时（比如大于$2^{80}$），P猜测V以查询$q_j$接受$\pi^*$的概率可忽略
该特性可用于构造基于LPCP的SNARG，其可重用性在P知道V接受每个instance的情况下仍然成立
3.2.2 From QAP (R1CS)
约束系统通常被称为电路，可以以布尔电路或算术电路表示，部分场景中算术电路会直接编译为ZKP$[CD98]$，但是有些时候转变为QAP也比较方便
QAP是一个域上的双线性约束系统（Bilinear Constraint System，BCS），每个约束允许两个输入的二次组合（标量乘法，加法和乘法），实际上BCS和Rank-1 quadratic equations考虑的内容相同（符号不同，但是表达的内容是同一个东西）$[BCGTV13,Appendix E]$，这一概念也和libsnark中的R1CS内容相同，等效公式可以表示为QAP（Quadratic Arithmetic Programs）$[GGPR13,PHGR13,BCGTV13,BCTV14b,etc.]$
BCS处理两个向量：包含$n_x$个元素的instance向量$\vec x=(x_1,...,x_{n_x})$和包含$w$个元素的witness向量$\vec w=(w_1,...,w_{n_w})$，约束系统描述了这两个向量之间存在$n_c$个约束关系，其中每一个约束都为特定形式的二次方程
所有这些元素及其对应的操作都是基于一个很大的素数域$\mathbb F_p$（模数为素数$p$），使用的素数、域元素的表示与使用的的椭圆曲线有关，具体的BCS定义如下
令$n_x,n_w,n_c$为三个整数，$n_z=n_x+n_w+1$，基于域$\mathbb F_q$的双线性约束系统为一个元组$\mathcal S=((\vec a_j,\vec b_j,\vec c_j)_{j=1}^{n_c},n_x)$，其中$\vec a_j,\vec b_j,\vec c_j\in \mathbb F_q^{n_z}$
若对于一个输入$\vec x\in \mathbb F_q^{n_x}$，其满足下列条件，则称该BCS为可满足的
存在witness $\vec w$，令$\vec z=(1,\vec x,\vec w)$使得对于所有的$j\in [n_c]$，满足$<\vec a_j,\vec z>\cdot <\vec b_j,\vec z>=<\vec c_j,\vec z>$
上述内积和点乘均为域$\mathbb F_q$上的运算
举个例子，一个简单的BCS如下
其可被表示为下列两个双线性约束（其中$\vec z=(1,x,w_1,w_2)$
或者简单一点，可以表示为下列两个等式
根据BCS的定义，若存在$x_1$，使得上述两个等式成立，则称该BCS为可满足的
采用zk-SNARK来证明该NP statement时，该instance会作为公开输入，所有V均可见，而witness作为P的额外输入，仅P可知，用于P的证明生成过程
生成一个zk-SNARK的（时间和内存）开销主要取决于约束的数量$n_c$，注意到变量之间相乘的开销是很大的（每个双线性惩罚都需要一个 新的约束，从而增加$n_c$的值），相比之下每个约束之间的线性组合需要的开销可忽略不计
因此QAP考虑下面这个矩阵等式
其中$A,B,C$为公开的三个矩阵，$z$为一个由公共输入和私密输入组成的向量
为了编码这个约束系统，首先从域$\kappa_i$上选择不同的点集，$\kappa_i$上的评估点通常被设置为统一的根（以确保系统的效率）
然后定义三个多项式$u_j(X),v_j(X),w_j(X)$，满足$\forall j,u_j(\kappa_i)=A_{ij},v_j(\kappa_i)=B_{ij},w_j(\kappa_i)=C_{ij}$（通过拉式插值法来找到这些满足条件的多项式），此时上述的矩阵等式就转化为了下面这个
这里有一个数学基础，对于一个多项式$f(X)$，若$f(\alpha)=0$，则意味着$(X-\alpha)$可以整除该多项式，因此根据这个性质，上述问题就转化为了对于所有的$\kappa_i$，都有$(X-\kappa_i)$整除下面这个多项式
然后我们定一个目标多项式$t(X)=\prod_i(X-\kappa_i)$，上述问题就转化为了下面这个
其中$h(X)$为某个多项式
此时一个IOP Prover发送一个证明串$\pi=a(X),h(X)$，满足$a(\kappa_i)=z_j$且$h(X)$满足上述等式，此时Verifier选择一个随机的域元素$r$，并验证是否有下列等式成立
根据SZ引理，对于随机选择的域元素$r$，若给定的BCS不可满足，则上述等式成立的概率为$\frac{1}{|\mathbb F_p|}$，当域足够大时此概率可忽略不计，从而使得V相信P的证明
3.2.3 Fully LPCP
暂时不介绍，因为Fully LPCP需要LIOP的概念，这里放到后面和LIOP一起介绍（3.5.3）
3.3 MPC-int-the-head
安全安全多方计算（Secure Multi-Party Computation）协议$[Lin20]$允许$n$个参与方计算一个给定的函数，该函数将$n$个本地输入映射至$n$个输出，且确保输入的隐藏性
MPC in the head范式在$[IKOS09]$提出，可以将简单的（满足完美正确性）MPC协议编译为zk-PCP
From an MPC protocol to a zk-PCP
给定一个NP关系$R(x,w)$，定义一个$n$方的MPC函数$f(x;w_1,...,w_n)=R(x,w_1\oplus w_2\oplus...\oplus w_n)$，其中每个参与方$P_i$的输入为$x$和$w_i$，若$(x,w)\in R$则该函数输出1，否则输出0，记$\Pi_f$表示实现函数$f$的MPC协议
$w_i$可以通过对$w$进行秘密共享得到，函数$f$的输出对所有参与方可见
zk-PCP的Prover对于输入$(x,w)$，生成证明串$\pi$的过程如下：首先随机将$w$拆分为$n$个部分，满足$w=w_1\oplus w_2\oplus...\oplus w_n$，然后P在“脑中”对公共输入$x$和所有的$w_i$虚拟的执行$\Pi_f$协议，该过程包含了参与方$P_i$所使用的秘密随机输入$r_i$以及计算交换的消息，直到所有各方以输出结束
然后证明串表示为$\pi = (V_1,...,V_n)$，其中$V_i$为参与方$P_i$在虚拟执行中的视角（view），$V_i$包含了$w_i,r_i$，以及$P_i$接收到的所有消息
zk-PCP的Verifier随机发起一对请求$V_i,V_j$，并进行如下检查
- 这两个请求具有一致的视角
- 视角中隐含的$P_i,P_j$的输出均为1
V当且仅当两个检查均通过时接受P，为了增强合理性（降低合理性错误），可以通过发起多个不同的对来完成
上述zk-PCP协议的安全性分析如下
- 完备性：取决于MPC协议$\Pi_f$的完美正确性
- ZK：对于上述的第一个条件，witness份额$w_i,w_j$并未暴露完整的$w$，根据MPC协议的安全性，其对于相互串通的两个参与方而言是私有的
合理性：若不存在满足$R(x,w)=1$的witness，分为下列两种情况
- 若$V_i$的视角对应于$\Pi_f$关于输入$(w_1^*,...,w_n^*)$的一个合法执行，则根据MPC协议的完美正确下，此时所有输出均为0，因此V拒绝
- 若这些视角不对应一个合法执行，则意味着至少存在一对$(i,j)$，其对应的一对视角$(V_i,V_j)$不一致，V选中这一对视角的概率为$\frac{1}{C_n^2}$，且V选中后会拒绝（也即V拒绝的概率为$\frac{1}{C_n^2}$），可以通过$O(k)$次执行来将该合理性错误降低至$2^{-k}$
对于zk-PCP的效率而言，其非常适用于一些规模比较小的问题，或者适用于一些Prover的setup过程作为效率主要瓶颈的系统中，不过zk-PCP好处在于其可以用基本的对称密码原语进行实例化
注意到MPC协议本身是为了分布式执行所涉及的，因此任何一个参与方都无法获得完整的信息，但是证明系统中的P可以获得完整的信息，这意味着基于MPC的zk-PCP无法达到其他证明系统的简洁性
对于zk-PCP的适用性而言，其比较适用于函数$f$的MPC协议，可以通过安全的点对点信道来提供针对两个半诚实参与方的安全性，这意味着任何一对参与方的联合视角都可以通过其对应的输入来模拟其输出，且该过程与其他参与方的输入独立
部分paper给出了参与方$n\geq 5$的简单协议$[BGW88,CCD88,Mau06]$，而且可以通过扩展协议来使得协议更有用，比如：
- 可以以zk-PCP交互为代价来放宽对MPC协议完美正确性的要求
- MPC模型可以通过独立于输入的预处理过程来增强$[KKW18]$
- 对于大量参与方的情况，可以利用MPC协议来实现对抗恶意参与方时的可忽略的合理性错误
3.4 Interactive Oracle Proof（IOP）
IOP实际上是交互式PCP概念的广义化，与PCP相比，IOP证明系统更为强有力，因为他不像PCP那样单纯的由V发起查询然后由P响应，IOP中允许P和V之间进行额外的交互，从而获取到更多的信息
交互过程中会包含V的一些随机挑战，因为这些挑战都是V随机选择的，因此P无法控制其将要响应的随机挑战，不过利用这些额外的信息可以在协议中提高P的效率
交互式zk-PCP通过传递恶意Prover的问题来实现统计正确性保证，恶意的Prover可以以违反MPC正确性的方式选择MPC方的随机性，从而攻破zk-PCP的可靠性
Interactive PCP and IOP
在3.1中介绍了经典的PCP，经典PCP若希望做到很低的通信开销，则需要生成一个比电路大小大得多的证明串$[FS11]$，如果此时允许P和V之间交互的话可以将证明大小降低至和witness差不多大，且仍然保持经典PCP中较低的通信开销，交互式PCP的一些早期应用比如$[KR08]$，可以用于证明深度为常数的电路
此类允许交互的PCP中有一个证明串$\pi$，V除了和P交互之外还可以查询该串上的符号，我们可以将PCP中的交互发挥到极致，因此引入IOP模型$[BCS16,RRR16]$
IOP模型允许存在多个证明串$\pi_i$，由P生成并供V查询，更具体而言，（公开掷币变体的）IOP模型的每个证明串$\pi_i$均可视为对一个随机挑战$r_i$的响应，V可以在交互结束时查询$\pi_i$
IOP中额外的交互行为使得该模型中的完全简洁证明的设计比经典PCP模型甚至比交互式PCP模型中的更简单，不仅简单还可以提高效率
- Fully Succint IOP：若V读取所有$\pi_i$的比特数与instance大小呈对数多项式关系，则IOP为完全简洁的
3.5 Linear IOP
经典PCP模型有两种正交松弛
- 增加交互
- 采用线性查询来代替原本的点查询
线性IOP$[BBCGI19]$自然的结合了上述两种情况，此类IOP模型中，P生成一些列的证明向量$\pi_i\in \mathbb F^{m_i}$，其中每个证明串$\pi_i$均可视为对一个随机挑战$r_i$的响应，在每次交互结束后，V可以发起一次对$\pi_i$的线性查询（LIOP的概念和$[BCGGHJ17]$所提的交互式线性承诺（Interactive Linear Commitment）概念类似）
LIOP也有很多种，目前主要研究的有三种，分别为基于IP的LIOP、多项式IOP和完全线性的IOP
3.5.1 IP based
构造LIOP的方式有很多，经典的方式是GKR协议$[GKR08]$，其是一个双高效（Double Efficient）的协议（意思是P和V都很高效），该协议基于和校验协议$[LFKN92,Tha20]$构建，和校验协议可用于NP的LIOP，且具有下列特殊的性质
- 若$R(x,w)$由一个层级的算术电路计算（电路大小$s$，深度$d$，计算域$\mathbb F$，输入数量$m$），则大约需要$d$轮来生成证明串$\pi_i$，每个证明串都是域$\mathbb F$上大小约为$\log s$的向量，每一轮的证明向量大小约为$m$
- V对每个证明发起常数次的线性查询，合理性错误约为$\frac{d}{|\mathbb F|}$，此外若电路可被简洁表示，V的运行时间可以缩短至大约为$d+m$
这里的大约指的是系数与$s$的对数多项式相关
更具体而言，电路大小应当是对数空间中均匀的，其可以在对数空间内计算门信息，而后一个一致性特征在GKR协议的原始情况中至关重要，其可以在无需witness的情况下快速验证浅多项式大小确定性的电路
然而，在NP的证明系统的情况下（不考虑有没有零知识），如上所述的LIOP即使对于没有简洁描述的一般验证电路也是有意义的，使用独立于statement的预处理也可以在非均匀情况下实现快速在线验证
不过适用于空间有限计算的更复杂的相关协议也可以转换为（常数轮的）LIOP
稍加修改，GKR协议可以获得很好的并发性$[CMT12,VSBW13,Tha13,XZZPS19]$，对于大的域上的层级电路，Libra协议$[XZZPS19]$可以在算术设置中做到P的恒定开销，Virgo++$[ZLWZSXZ21]$将GKR协议推广到任意算术电路，P上的恒定计算开销与分层电路协议相同
这可以与上面讨论的用于NP的更简单的恒定开销zk-LPCP进行比较，后者适用于任意验证电路（具有任意结构、深度和witness长度），但不提供任何形式的简洁性，为了有效地验证确定性低深度计算（即没有ZK或甚至没有witness情况下）GKR变体可以在没有密码编译器的情况下使用，当通信的代价足够小时，此类方法是可行的$[WJBSTWW17]$
3.5.2 Polynomial IOP
多项式IOP为经典IOP的广义化，在协议的每个子轮中，允许P向V发送一个多项式，V可以请求计算该多项式上的少数几个点$[BFS20,CHMMVW20]$
PIOP可以利用多项式承诺方案编译为简洁论证，因为本质上在PIOP中，P发送的任意多项式$p$均可被一个简洁承诺代替，且V对$p$在某点的评估值也可以用多项式承诺方案实现
文献中的许多协议可以被视为PIOP，即使它们最初不是用语言表达的，比如vSQL$[ZGKPP17]$隐式地将用于电路评估的GKR交互式证明$[GKR08]$适配为用于电路可满足性的PIOP
此外还有许多PIOP$[ZXZS20,ZLWZSXZ21,WTTW18,XZZPS19]$，以$[BTVW14]$举例，关于电路可满足性的2-Prover交互式证明可以得到一个PIOP，此外Spartan协议$[Set20]$将该PIOP由电路可满足性扩展至R1CS，Marlin$[CHMMVW20]$、Aurora$[BCRSVW19]$和Fractal$[COS20]$都基于单变量和校验协议的针对R1CS的PIOP
3.5.3 Fully Linear IOP
部分设置中不允许V完全访问statement，对于instance而言，输入可以被两个或以上的参与方划分，此类分布式设置中，若对输入$x$执行的查询可以通过对各方所持有的共享的本地查询来实现，则仍然可以用于构造证明系统（举个例子，若$x$是通过线性秘密共享的方式构造，则可以通过将查询分别作用域每个共享，从而完成对$x$的线性查询）
上述设置需要LPCP和LIOP模型的更强变体，因为线性查询共同作用于输入$x$和证明$\pi$，这意味着V不可以直接访问输入，只能通过查询来访问
$[BBCGI19]$研究了此类IT证明系统（称为完全线性证明系统，fully linear），该概念可以扩展并加入ZK性质，不过根据ZK的定义，模拟器无法直接访问输入$x$，这使得具有低查询复杂度的完全线性证明系统即便在证明多项式时间语言也是有意义的（也即P=NP成立时也有意义）
完全线性的证明系统由高效分布式零知识证明所驱动的，其中P完全知道输入statement $x$，但是该statement会分布于多个V之间（需要注意，这一概念要与分布式ZKP区分开来$[WZCPS18]$，分布式ZKP允许多个机器并行执行计算）
因此，此类证明系统的目标是设计一个短证明长度和低请求复杂度的完全线性PCP，最好可以做到与输入长度成亚线性关系
事实上前面讨论的一些具体的LPCP和LIOP可以在相同的查询次数下做到完全线性，但是诸如基于哈达玛的LPCP和GGPR的LPCP的证明长度会达到$n$的线性阶，而GKR协议的FLIOP可以做到$O(\log^2n)$，类似的诸如RRR协议$[RRR16]$可以做到低空间开销的常数轮亚线性FLIOP
对于由低度多项式识别的语言而言，有更高效的完全线性证明系统$[BBCGI19]$，举个例子，一个非交互式zk-FLIOP需要在$O(\sqrt n)$的证明大小和查询次数下证明$x$满足一个度为2的等式（$[Kla03]$中表明此类情况下为最优），该协议是通信复杂度达到上界方案的ZK变体$[AW09]$
对于度为常量的等式的系统识别的语言而言，证明大小和请求复杂度可以降低至$O(\log n)$，且交互轮数为$O(\log n)$，这些构造从GGPR风格的zk-LPCP的泛化开始，它利用了重复的结构，然后通过平衡和递归来提高效率
3.6 Ideal Linear Commitment
理想线性承诺（ILC）模型提供了LIOP的另一个视角$[BCGGHJ17]$
ILC模型中的证明可以被视为一个LIOP，不过每个证明向量$\pi_i$会被视为一个$n_i\times m_i$的矩阵$\Pi$，每个对$\pi_i$的查询均为一个长度为$m_i$的向量$q$，查询会返回矩阵与该向量相乘的结果$\Pi q$，或者可以将ILC视为采用域向量的标准LIOP
ILC模型放松了LIP模型$[BCIOP13]$，因为每个ILC证明矩阵可以是输入和验证者消息的任意函数的输出，而每个LIP证明矩阵必须是验证者的消息的线性函数
用线性时间可编码纠错码$[Spi96]$和线性时间可计算哈希函数$[AHIIKV17]$实例化，编译器不会影响底层ILC证明的渐近计算复杂性
上述工作还展示了算术电路可满足性的zk-ILC，具体而言，对于一个由算术电路计算的NP关系$R(x,w)$（电路域为$\mathbb F$，大小为$s$），其通信量大约为$\sqrt s$，轮复杂度约为$O(\log{\log s})$，且双方均可实现一个运行时间为$O(s)$次域运算的RAM程序，对应的合理性错误在$|\mathbb F|$上可忽略
将上述ILC域线性时间密码学编译器相组合，可以得到一个关于算术电路可满足性的平方根简洁的ZK论证，其具有恒定的计算开销
该ILC方法获得具有恒定计算开销的ZKP系统，它比简单的基于LPCP的方法具有更好的渐近简洁性，它与基于GKR的方法是无法比拟的：它的简洁性通常更差（除非电路相对较深），但它实现了任意电路和见证长度的恒定开销
与其他两种方法不同，基于ILC的系统的隐藏乘法常数似乎相当大，并且尚不清楚它是否可以被优化以具有竞争性的具体效率特征，但是对于具有恒定计算开销的零知识，所有三种方法（GKR、ILC、LPCP）只能在超多项式大小的域上实现算术计算时达到可忽略的合理性误差
并行RAM模型中，在SPARKS系统$[EFKP20]$中提出了一种以处理器数量少量增加为代价来分摊（并行）证明程序计算开销的方法，但是当考虑布尔电路大小或RAM机器上的（顺序）运行时间的标准度量时，是否存在恒定开销的零知识仍然是一个开放的问题，目前在任何密码假设下还未出现候选结构
4 Cryptographic Compilers (CC)
本节描述了前面介绍的几种IT系统的密码编译器（CC），CC将IT证明系统转换为真实世界协议，该协议涉及P和V之间的直接交互
CC使用的原语通过（可能是启发式的）具体实例化来实现，例如具体的哈希函数或配对友好的椭圆曲线，从而得到一个可以在现实应用中实现和使用的具体方案
CC还可以提供额外的特性，例如消除交互、缩小某些消息的大小，甚至在没有ZK特性的IT验证系统中添加ZK特性
虽然IT证明系统和密码编译器的概念比较分离，但是部分方案中这个分离比较模糊，对于一些具体的ZKP方案，没有简单的方法将它们分解成这样的组件
4.1 CC for zk-PCP
以3COL问题为例，假设承诺可用，为了实现该协议，利用依赖于（在某些计算假设下是安全的）密码学承诺的CC
CC具体的工作如下，给定$(x,w)$，P利用zk-PCP中的P生成一个证明$\pi \in \Sigma^m$，然后用承诺方案对$\pi$中的$m$个符号进行承诺，V利用zk-PCP中的V，选择这些符号中的一个子集$Q$，并作为挑战发送给P，P检查$Q$合法后揭示$\pi_Q$（检查合法确保$Q$来自于诚实的V），然后V利用决策谓词来判断是否接受P
看起来似乎很简单，但当使用标准的计算隐藏承诺方案$[Gol01]$时，上述编译器的分析比看起来更为复杂，尤其是有效的模拟要求$Q$的分布具有多项式大小，这仅适用于$R_{3COL}$的zk-PCP的基本版本，不适用于增强合理性的版本
这样一来，通过编译器我们可以得到一个（恒定循环）零知识协议，尽管其合理性不足以达到期望的要求，不过可以通过顺序重复执行来增强其合理性
另一种密码编译器，通过使用统计隐藏承诺来避免多项式大小限制，该编译器隐含在NP$[GK96]$的常数轮零知识证明方案中
不过上述两种编译器得到的ZKP中，通信复杂度会比直接发送$\pi$还大，理想状态下，我们想要达到$\pi_Q$
当用统计绑定（和计算隐藏）承诺实例化时，上述编译器可以得到统计上合理的证明，不过这些编译器得到的方案具有较高的通信开销（根据复杂性理论证明$[GH97,GVW02]$，关于NP难的证明系统中，P至V的通信开销不会小于witness的大小），另一方面，不同的密码编译器$[IMSX15]$可以使用任何抗冲突哈希函数来获得零知识论证，该论证的通信复杂度接近$\pi_Q$大小
对于某些zk-PCP，其大小可能远小于witness大小，这种类型的第一个编译器（Kilian$[Kil92]$的工作中隐含的）可以从任何PCP获得类似的ZK论证（无ZK要求的ZK-PCP）然而，与基于zk-PCP的编译器相比，Kilian的编译器以非黑盒方式使用底层加密原语$[RTV04]$，这使得它在实践中效率较差
- 随机预言模型中的实用NIZK编译器：如果底层的“对称”密码原语被抽象为一个随机预言机，那么可以无条件地分析所有以前的黑盒编译器，但实际上可以更进一步，通过FS变换使这些交互式公开掷币协议转化为非交互式$[FS87]$
结合这两个步骤，我们得到了随机预言机模型中从任何zk-PCP到NIZK的具体高效编译器，然后使用基于SHA-256或AES的实用哈希函数对后者进行启发式实例化（有关此方法的更多讨论，请参见背景部分）
不过即便在随机预言模型中，NIZK也不完全主导它所基于的交互协议，因为移除交互可能会付出代价
例如，考虑一个合理性误差为$2^{-\sigma}$的交互协议，其中$\sigma$可能为40或64，在通过Fiat-Shamir变换获得的NIZK中，P可以通过生成大约$2^\sigma$的随机脚本，直到找到一个使得V接受的副本，这意味着非交互式变体应依赖于具有相当小的合理性误差的zk-PCP（即$\sigma$等于计算安全参数$k$的较高值），这将增加具体的通信和计算成本，但会增加一个较小的因子（约为$\kappa/\sigma$）
- 来自标准密码假设的NIZK：最近的一系列工作展示了如何在标准密码假设下，通过FS变换获得的NIZK证明中实例化随机预言，这些工作依赖于一种特殊类型的相关难处理哈希函数$[CGH04]$以及一种特殊的Sigma协议$[Dam10]$，即满足某些附加属性的3消息诚实验证器（计算）零知识证明系统，后者又隐含地依赖于一种特殊的zk-PCP，它可以用Blum的图哈密顿协议$[Blu87]$实例化，但仍有待更系统地研究
与这些最近的NIZK协议相比，与NP问题相关的基于标准密码假设的NIZK的经典方法$[FLS99]$使用了一种非常不同的信息论证明系统，称为隐藏比特模型（Hidden Bit）中的零知识证明，这种类型的已知证明比zk-PCP证明更复杂，且效率更低
然而，从隐藏比特模型到NIZK的密码编译器需要依赖于因子分解的难处理性（依赖于一种合适的陷门置换$[CL18]$）
目前有一个开放的问题：是否可以从zk-PCP获得类似的密码编译器
4.2 CC for Linear PCP (LPCP)
目前研究出了可以用于线性PCP的密码编译器，但是代价为较昂贵的可信设置和“不可有效证伪”的密码假设$[Nao03]$，好处就是可信设置可重复使用
这些编译器可以产生证明非常短的zk-SNARK（大约1KB，在某些设置中甚至更少），这种类型的编译器的使用在一些初始方案中是隐含的$[Gro10,Lip12]$，后来被明确考虑$[BCIOP13,GGPR13]$
考虑这么个情况：将LPCP编译为具有可重用结构化的引用字符串（Reusable Structured Ref. Str.，SRS），记为$\sigma$，V生成一系列的LPCP查询$q_1,...,q_d$（以基于哈达玛的LPCP为例，$d=3$），然后让$\sigma$包含V的查询的一个线性同态加密，记为$\sigma = (E(q_1),...,E(q_d))$，V需要确保密钥$k_V$保密以用于后续对密文的解密
接下来，给定$(x,w)$和$\sigma$，P需要计算一个LPCP的证明向量$\pi$，然后利用线性同态加密$E$来计算一个短的SNARG证明$\hat \pi$，其中包含$d$个密文$\hat \pi = (E(<\pi,q_1>),...,E(<\pi,q_d>))$，然后P将$\hat \pi$发送给V，V利用$k_V$解密得到LPCP的回答$a_1=<\pi,q_1>,...,a_d=<\pi,q_d>$，利用LPCP决策谓词来判断是否接受P
此类基于同态加密实现的LPCP显然满足了完整性要求，此外，由于加密隐藏了查询，所以证明$\pi$独立于查询，因此也满足合理性，不过这种过于简单的合理性论证是有缺陷的，原因如下
- 虽然标准线性同态加密方案$E$支持对加密输入来计算线性函数，但它不能保证只能计算线性函数，事实上，线性同态加密可以是完全同态的$[Gen09]$
在这种情况下，方案的合理性完全失效，解决方案本质上是通过依赖加密方案$E$来“假定它不存在”，该加密方案$E$被推测为仅支持加密输入的线性计算（或者可以扩展到包括常数项的仿射计算），后续会更详细地讨论“仅线性加密”$[BCIOP13]$的这个强大概念
- 第二个问题在于上述解决方案中没有任何方式可以阻止恶意的P在处理每个加密请求$E(q_i)$中使用不同的证明向量$\pi^*_i$，此类情况会超出了LPCP模型中恶意P的能力，因此会攻破方案的合理性
解决方案是让V向LPCP中添加一个随机的线性组合作为附加查询，形式为$q_{d+1}=\rho_1 \cdot q_1+...+\rho_d \cdot q_d$，然后V检查对该查询的回答$a_{d+1}=\rho_1 \cdot a_1+...+\rho_d \cdot a_d$
上述过程可以视为一个简单的IT编译器，从LPCP到一轮线性交互证明（LIP）$[BCIOP13]$，这是一个更强的信息论证明系统，可以被视为通过允许P（诚实和恶意）仅计算V消息的线性函数来限制标准交互证明
总结一下：修改后的编译器分两步进行
- 首先将LPCP转换为LIP，如果LPCP的证明大小为$m$，包含$d$个查询，则由上述简单编译器生成的LIP具有由$(d+1)\cdot m$个域元素组成的Verifier消息和由$d+1$个域元素构成的Prover消息
- 然后使用纯线性加密将LIP编译为指定验证器SNARG，SRS由$(d+1)\cdot m$个密文组成，证明由$d+1$个密文构成
这种转换满足我们在Hadamard LPCP那一节中讨论的LPCP的所有附加特性：零知识、快速验证和可重用的合理性，可重用的合理性意味着生成的SNARG的SRS可以安全地用于多次证明
最后，当LPCP也是“知识证明”（这是所有自然构造的情况），并且当仅线性加密是“可提取的”（对于具体实例化来说是一个似是而非的假设）时，得到的zk-SNARG也是知识证明（zk-SNARK）
不过这里还有一个的问题：上述方法局限于指定的Verifier，因为只有Verifier能够解密加密的LIP回答，此类情况下对于部分应用程序来说已经足够好了，但SNARG的许多应用程序都需要满足公共验证，解决方案是再次依赖LPCP的一个特殊属性，这在向LIP的转换中得到了保留，具体如下
假设LIP验证器的决策谓词在以下意义上是二次的：为了决定是否接受，Verifier测试形式为$p_x(\boldsymbol u,\boldsymbol a)=0$的等式，其中$p_x$是由输入语句$x$确定的二次多项式，向量$\boldsymbol u$包含由LIP查询确定的状态信息，向量$\boldsymbol a$包含LIP回答，本质上这就是基于哈达玛的LIP，接下来可以通过使用加密方案来实现公开验证，该加密方案允许在不知道解密密钥的情况下对加密输入执行这种二次测试
利用基于配对的加密技术可以做到这一点，如果SRS $\sigma$包括LIP查询的“配对友好加密”以及状态信息$\boldsymbol u$（可以使用双线性群实现），则输入$(x,w)$上的证明者可以计算LIP答案$\boldsymbol a$的加密，然后每个人都可以检查加密的$(\boldsymbol u,\boldsymbol a)$是否满足$x$定义的二次关系
几种基于QAP的构造$[GGPR13,Gro16]$可以在线性PCP模型中粗略地重铸为IT证明系统，然后以导致不同证明系统的方式进行密码编译（例如使用$[BCIOP13]$）
4.3 CC for MPC-in-the-head
待补充
4.4 CC for IOP
使用基于单向函数的密码编译器$[BGGHKMR90]$，交互式PCP可以把低深度（或空间有界）NP关系做到通信复杂度与witness长度相当的统计上可靠的ZKP协议
与经典PCP的情况一样，部分密码编译器通过扩展了经典PCP的编译器，并使用抗冲突哈希函数（分别为经典或甚至量子随机预言机）$[CMS19]$将完全简洁的IOP转换为NP的交互式（分别为非交互式和透明）完全简洁的论证
在交互式变体中，P使用Merkle树承诺每个证明，然后V生成并发送下一个证明的随机挑战，最后V要求P揭示其想要查询的证明符号子集，P通过揭示Merkle树上的少量相关信息进行响应
非交互式变量是通过Fiat-Shamir启发式从交互式变体中获得的（交互式情况下，随机预言模型中的分析更具挑战性，并且需要对基础IOP进行一些额外假设）
实践中，透明SNARK（如STARK$[BBHR18b]$、Aurora$[BCRSVW19]$和Fractal$[COS20]$）依赖于具体有效的IOP，这些IOP具有透明、后量子合理性以及完全避免使用公钥密码的优点（Fracttal还可以实现更高效的Verifier），但是缺点在于其难以做到基于群的SNARK那么简洁（前者的典型证明大小为100-200kB，后者为1-2 kB），
这些实用IOP中的一个关键技术成分是FRI协议$[BBHR18a]$：一种交互式测试，用于测试预言机的响应与里德-所罗门码的接近程度，FRI协议的一个有用特征是它可以使用严格线性的算术运算来实现，然而建立在其之上的IOP仍然需要Verifier的准线性时间开销
实践情况下可能会存在不少局限性，但是在理论方面，IOP模型产生了经典PCP无法实现的渐近效率特征（参考最小化IOP验证大小的最新进展$[BCGGRS19,RR20]$），尽管证明大小不是IOP密码应用中感兴趣的主要参数，因为它只是Prover运行时间的下限，但构建IOP的新技术可能会导致基于IOP的证明系统的具体效率的进步，与IOP的具体效率更直接相关的是改进其合理性误差分析的工作$[BKS18,BGKS20,BCIKS20]$
4.4.1 CC for IPCP
待补充
4.5 CC for LIOP
待补充
4.5.1 CC for Fully LIOP
通过使证明者秘密共享每个证明向量，可以将完全线性证明系统$[BBCGI19]$编译为分布式零知识证明，其中通信复杂性由IT证明者生成的证明的总长度（要线性查询的$\pi$）和线性查询的答案决定
分布式零知识的编译器可以是信息论的，并且不能利用多项式IOP提供的额外结构或验证器决策谓词的低代数度
与完全线性IOP不同，在纯LIOP中，主要的通信成本与IT Prover的证明长度没有太大关系（证明长度不太影响通信，因为证明可以通过散列或同态加密进行“压缩”）
4.5.2 CC for PIOP: Polynomial Commitments
更好的密码编译器的关键是基于GKR的LIOP的以下附加特性：每个证明向量$\pi_i$可以被看作是在少量变量中定义多项式的系数，其中每个对$\pi_i$的线性查询都在单个点上评估多项式
更具体地说，基于GKR的LIOP中的长证明向量在$\log m$个变量中定义了一个多线性多项式，该多项式会编码$(x,w)$，这可以通过更精细的LIOP概念来理解，其中证明被解释为次数有界的多项式的系数向量，通常在少量变量中（上界为对数），将查询解释为求值点
LIOP的这种改进，称为多项式IOP（PIOP，$[BFS20]$），其利用了具有额外结构的密码编译器（密切相关模型的另一个名称是“代数全息证明”$[CHMMVW20]$）PIOP的密码编译器依赖于多项式承诺的有效实现，这是一种函数承诺方案，它允许证明者以支持对给定点的有效评估证明的方式承诺多项式
(zk)-vSQL$[ZGKPP17]$和Hyrax$[WTTW18]$首次将GKR协议和多项式承诺结合在了一起，Hyrax利用满足透明性的基于DLOG的多项式承诺，得到的证明大小约为$d+\sqrt m$，vSQL方案利用Kate多项式承诺的变体$[KZG10]$（依赖于配对友好的群，但是需要可信设置），消除了Hyrax方案证明大小中$\sqrt m$的项
之后又有了改进版Libra$[XZPS19]$，将类似的多项式承诺和基于GKR的PIOP的改进ZKP变体结合在一起，Virgo$[ZXZS20]$是Libra的变体，但是采用了一个高效的基于对称密码学的透明多项式承诺，并将基于IOP的FRI协议和基于GKR的LIOP相结合，达到$m=O(\log s)$，类似的多项式承诺方案还有RedShift$[KPV19]$
另一个方案$[BF20]$同样采用透明的多项式承诺，利用未知阶群可以做到更好的简洁性，但是具体的Prover复杂度较高，且不满足后量子安全，$[Lee20]$给出了一个相关的多项式承诺方案，可以避免采用类群（Class Group，一种基于对称外部DH假设的群），同时可以减少Prover的开销
此外，还有一些工作将PIOP和多项式承诺方案相结合，得到简洁论证：Kopis和Xiphos$[SL20]$将Spartan$[Set20]$中隐含的R1CS的PIOP与多项式承诺Dory$[Lee20]$和变体相结合，Cerebrus$[LSTW21]$从Ligero$[AHIV17]$中给出的IOP中提取多项式承诺方案，并将其与Spartan$[Set20]$中的相同PIOP相结合
4.6 CC for ILC
利用抗碰撞Hash函数可以将ILC编译为普通模型中公共掷币的论证，通信复杂度大约为$\sum_i(n_i+m_i)$，具体可以看$[BCGGHJ17]$这篇文献
5 Others Properties
本节讨论一些ZKP的其他性质，同时比较这些性质的优缺点
5.1 Proof Composition
通过递归合成，可以证明存在证明的证明等
递归证明的ZKP具有多个优点，从提高效率、改进功能到证明机器计算的能力$[BCTV14a]$，例如使用递归零知识证明，理论上可以证明机器计算中未指定大小的while循环得到满足，并且可以随着计算的进行而增量更新证明（增量可验证计算的概念$[Val08]$）
递归证明还可以证明正在进行的分布式计算的完整性（证明携带数据的概念$[CT10,CTV15]$），以确保中间节点以及最终验证者计算的所有前面部分（由其他方完成）都是正确的
在区块链领域还有更广泛的应用，比如区块链当前状态的有效性可以通过将其视为增量可验证的计算来简洁地证明，任何新加入系统的人都可以通过检查一个递归证明来确定状态是正确的，如Mina（nee Coda）$[BMRS20]$
其次，即使在单个事务中，也可以递归地组合多个证明以实现简洁性（在事务大小和验证时间上），如Zcash Orchard$[HGBNL21]$，构建递归证明的方法包括zk-SNARKs的递归组合$[Val08,CT10,BCCT13,BCTV14a]$，以及它对累加/分裂累加方案的推广$[BGH19,BCMS20,COS20,BDFG20]$
5.2 Interactivity
第三节中描述的几个证明系统是交互式的，包括经典交互式证明（IP）、IOP和线性IOP，这意味着Verifier需要向Prover者发送多个查询消息，证明者在接收第$i+1$个查询之前需要响应第$i$个查询，可靠性则依赖于Prover在对第$i$个挑战作出响应前无法预测第$i+1$个挑战
其他证明系统是非交互式的，即经典PCP和线性PCP，所有这些证明系统都可以与密码编译器相结合），以产生需要交互或无需交互的论证系统（具体取决于密码学编译器）
5.2.1 Advantages of Interactive Proof and Argument Systems
直觉上而言不需要交互的情况更好，但是存在交互的系统也有不少优点，接下来从几个角度分析一下
- Efficiency and Simplicity：交互式证明系统可以比非交互式证明系统更简单或更有效
例如$[BCS16,RRR16]$引入了IOP模型，该模型是交互式的，部分原因是交互可以一定程度上规避现有PCP构造中出现的效率瓶颈$[BCGT13]$
部分研究表明，从IP$[WTTW18,XZZPS19]$导出的一些论证系统对于Prover来说具有比现有技术PCP$[BCGT13]$或线性PCP$[GGPR13,Gro16]$更好的空间复杂度（关键的可扩展性瓶颈），利用FS变换可以在大多数情况下呈现为非交互式和公开可验证的，且通常不会带来效率上的损失，这意味着协议设计者可以自由地利用交互性作为“资源”来简化协议设计、提高效率、削弱或删除可信设置等，并且仍然可以选择使用FS变换来获得非交互性论证
不过将FS启发式应用于交互式协议以获得非交互式论证可能会增加合理性错误，并可能将统计安全性转化为计算安全性，不过最近的工作$[BCS16,CCHLRRW19]$表明，当将变换应用于具有实际和理论意义的特定IP、IOP和线性IOP协议时，合理性误差的放大仅与交互循环次数的多项式相关
- Setup：线性PCP的密码编译器目前需要一个结构化参考字符串（SRS），SRS是一个结构化字符串，必须由可信第三方在设置阶段生成，并且要求SRS在生效期间内，不能泄露SRS生成过程中使用的任何陷门，否则会攻破方案的合理性
相比之下，一些适用于IP、IOP（以及PCP）和线性IP的编译器会得到论证系统，其中Prover和Verifier只需要访问一个统一的随机字符串（URS），该字符串可以从共同的随机性获得，这种设置在文献中被称为透明设置
- Cryptographic Primitives：从IP、IOP或线性IOP派生的论证系统有时也依赖于更理想的密码原语
例如，IP本身在理论上是安全的信息，不依赖于密码假设，与从线性PCP导出的论证系统相反，从IOP导出的那些论证系统仅依赖于对称密钥密码原语（例如$[BCS16]$）
目前的研究表明，可以在基于可证伪假设（如抗碰撞哈希族$[Kil95]$）的普通模型中获得简洁的交互式论证，但简洁的非交互式论证并非如此
- Non-transferability：某些应用中，证明必须是可否认或不可传递的（不可传递意味着验证者不能向第三方证明某个证明的有效性）
虽然这些属性并非交互协议所独有，但存在交互的方案提供了一种使证明不可传递的方式
- Interactivity May Limit Adversaries' Abilities：交互式协议可能会以更低的安全性运行，因此通常具有更高的效率
例如，存在交互的系统可以限制一个协议执行时间，超过这个时间会强制终止协议，从而限制敌手执行攻击的时间
或者在交互式环境中，限制敌手只能发起一次或少数几次的通信，从而限制敌手攻击的次数，这样的方式在许多非交互式环境中几乎不可能做到
- Interactivity May Be Inherent to Applications：许多应用程序天生就是交互式的
例如，现实世界的网络协议涉及多条消息，这些消息主要是用于建立连接（比如TCP三握手）
此外，零知识协议通常与应用程序中的其他密码原语相结合（例如不经意传输），如果其他原语是交互式的，那么无论零知识协议是否是交互时的，最终的密码协议必然也是交互式的
如果一个应用程序本身就是交互的，且交互可以使协议更简单、更高效，或者具备其他更好的性质，那么交互的确是一种更合理利用资源的方式
5.2.2 Disadvantages of Interactive Proof and Argument Systems
有优点必然就有缺点，有些便捷的实现方式通常是非交互式固有的，交互式基本不可能做到
- Interactive protocols must occur online：非交互式协议发布证明无需同步Verifier，而在交互式协议中不可以，交互式需要在Verifier方便的情况下才能发布、发布和检查证明（需要V在线或需要同步V的状态）
- Public Verifiability：许多应用程序要求证明在任何时候都可以由任何一方验证
对于交互式协议而言，往往难以实现公共验证，因为交互协议的合理性依赖于Prover无法预测其在协议中接收的下一个挑战，除非存在公开可信的不可预测的随机性来源（例如随机信标）以及Prover记录消息的时间戳的方式，否则尚不清楚发送挑战的一方以外的任何一方如何能够确信挑战是正确生成的
此外，由于Prover在收到第$i+1$个挑战之前必须对第$i$个挑战进行了回复，因此若Prover希望作弊，则其只能以极低的概率成功（协议的合理性）
- Network latency can make interactive protocols slow：若交互式协议包含很多条消息，这些消息都需要通过网络传输，网络延迟可能会显著影响协议的总执行时间
- Timing or Side Channel Attacks：由于交互式协议要求Prover发送多条消息，因此与非交互式协议相比，可能更容易受到测信道或时间攻击
对于公共硬币协议，时间攻击只会影响零知识，而不会影响合理性，因为Verifier的消息只是随机掷币，在这种情况下，时间攻击不应将信息泄露给Verifier
在私有掷币协议中，零知识和合理性都可能受到这些攻击的影响
- Concurrent Security：如果交互协议不是单独使用的，而是在可以同时执行多个交互协议的环境中使用的，那么应该非常小心地确保协议保持安全（参考$[Gol13, Section 2.1]$及其参考文献）
非交互协议$[GOS06]$大大缓解了并发执行安全问题
- Proof Length：目前已知证明最短的零知识协议是基于非交互式的线性PCP，这些证明仅包含几个群元素
虽然基于IP或IOP的（公共掷币）零知识协议可以与FS启发式算法进行非交互排序，但它们目前产生的证明更长，更长的证明意味着这些协议不适用于某些应用程序（例如，公共区块链），但它们可能仍然适用于其他应用程序（甚至相关应用程序，如企业区块链应用程序）
5.3 Nuances on transferability vs. interactivity
互动性和可转移性/可否认性之间的关系并非没有细微差别，这里简单描述一下若干种可能的组合
- Non-interactive and deniable：非交互式ZKP可能是不可传递的（可能是，而非一定是）
例如：本地CRS本身是可拒绝的，在这种情况下，恶意Verifier无法向外部方证明CRS是真实协议执行中使用的CRS，从而导致外部方合理怀疑Verifier可能模拟了CRS，以便能够在没有合法证明者实际参与的情况下模拟协议执行的脚本
不可传递性的另一个例子是，利用ZKP证明两个陈述的析取：（1）(成员属性或知识）的断言和（2）指定验证者的私钥，Prover需要证明（1）和（2）的析取，这种方式可以使原始Verifier相信（1）是正确的，因为Verifier知道Prover实际上并不知道密钥（因此2不成立，且析取结果为真，因此必然有1成立）
上述交互式证明中，因为（1）为真，所以P可以向V完成证明，但对于任何外部方来说，可以考虑原始指定的Verifier可能已经制作了证明的副本，从而P和V可以在知道密钥的情况下简单地进行验证（2），从这个意义上讲，指定的Verifier将无法说服其他人，使得其他人相信一个合法证明的脚本不是Verifier模拟的
- Non-interactive and transferable：若满足可传递性，则意味着可以实现非交互式协议
比如使用公共（不可否认）CRS，如果CRS来源于可信的随机beacon，此时合理性基于Prover无法控制CRS，则任何外部方（即使是在证明生成时与Prover无关的一方）都可以在一段时间后验证证明脚本可能仅由合法Prover生成
- Interactive and deniable：可以通过（独立Setup，无并发执行）交互式ZKP协议获得否认属性，该协议在rewind下可被证明是安全的
此时可否认性来自于对任何恶意Verifier的脚本的可模拟性，对于每个交互步骤，模拟器学习恶意的Verifier可能发出的查询，然后rewind以重新选择Prover的先前消息，使其能够回答后续查询
有些技术需要使用承诺和/或陷门，如果有适当的可信设置，甚至可以在直接模拟（无需rewind）中满足此属性
- Interactive and transferable：在某些情况下，即使通过交互式ZKP协议执行，也可以生成构成可传递的证明脚本
当（可能是恶意的）Verifier能够令人信服地向外部方表明：协议执行期间Verifier选择的挑战在收到Prover先前的消息时是不可预测的时，可以实现可传递性，然后可传递的证明脚本由Prover发送的消息和来自恶意Verifier内部状态的附加信息组成（包括生成挑战的相关信息）
例如，（由Verifier）作为先前消息的加密散列输出（或作为密钥伪随机函数）产生的查询稍后可以用于提供只有合法Prover能够生成有效后续消息（响应）的保证
或者，交互式ZKP协议由一个通信协议组成，其中Prover对所有发送的消息进行认证（例如在PKI中签名，由可信服务加上时间戳），那么这些认证消息的整个序列在Verifier手中就变成了一个可传递的证明
此外，从可传递的脚本中，实际的传递也可以通过交互的方式进行：拥有证明脚本的Verifier在可传递的ZKP中作为可传递脚本知识的Prover，从而将新的可传递脚本转移给外部Verifier
5.4 (Non)-Transferability/Deniability of Zero-Knowledge Proofs
可传递性和可否认性也存在相互制约的关系
- Off-line non-transferability (deniability) of ZK proofs：零知识证明通常是交互式的，即便没有Setup时，交互属性也是ZKP固有的（Goldreich和Oren表明，对于非平凡语言，零知识证明至少需要3轮）
通过消除Setup，ZP属性保证了离线不可传递性的属性（又称为否认性）
不过Verifier总是可以通过运行模拟器来计算等效的脚本，这意味着Verifier此时并没有收到来自Prover的接受证明的证据，因此在将收到的证明传递给其他人时没有优势
- On-line non-transferability of ZK proofs：在线不可传递的情况更为复杂一些
考虑这样一种情况：恶意Verifier在零知识证明系统中与诚实的Prover玩游戏，同时恶意Verifier扮演Prover与其他人玩游戏，试图传递他从诚实Prover那里收到的脚本（类似于MITM）
对于上述情况，协议的不可传递性是防止中间人攻击的一种安全形式，当敌手使用相同的零知识证明系统试图将证明传递给诚实的Verifier时，针对此类攻击的安全性通常被称为不可延展性
相反，当不同的协议作为敌手活动的一部分时，需要一些更强的概念来建模此类攻击下的安全性（通用可组合性可以做到）
- Transferability of a NIZK proof: publicly verifiable ZK：可公开验证的ZK
当考虑某些形式的设置时，零知识证明的可传递性可能变得不可避免，并且零知识证明对其进行了一些关键的使用
事实上，在通用参考字符串模型和可编程随机预言机模型中，都可以构造非交互式零知识证明，Verifier不能用相同的设置或随机预言机的相同实例化来模拟这种证明
更具体地说，非交互式零知识证明是在没有任何Verifier贡献的情况下构建的，因此它们是可以在Verifier之间自然传递的可公开验证的证明
- Designated-verifier NIZK proofs：此类情况需要更复杂的设置
考虑一个拥有通过公钥实现身份认证的Verifier，在这种情况下，Prover可以计算一个非交互式零知识证明，该证明在使用相应密钥的Verifier可以计算出无法区分的证明时关键地使用验证者的公钥（？）
在这种情况下，我们认为该证明是一个非交互式的指定Verifier零知识证明，并且是不可传递的，因为接收该证明的Verifier可以自己计算出一个等价的证明，因此没有证据可以与其他人分享该证明来自诚实的Prover这一事实
- Transferability of interactive ZK proofs：通过公钥实现的身份认证的使用在交互式情况下也会产生影响
例如，可以设计一个具有可传递性的交互式ZKP系统，如果Prover在脚本上签字，那么Verifier可以将“证明”转交给任何相信原始Prover的诚实的人
Reference
$[1]$ ZKProof Community Reference
$[2]$ GitHub Repo
$[3]$ 李威翰,张宗洋,周子博,邓燚.简洁非交互零知识证明综述$[J]$.密码学报,2022,9(03):379-447.DOI:10.13868/j.cnki.jcr.000525.