Abstract

最近关于交互式零知识（ZK）协议的工作提供了一种具有高效率和可扩展性的新范式，然而这些协议的通信开销很高，通常与电路大小呈线性关系

本文提出了两种新的ZK协议，通信开销为电路大小的亚线性阶，同时保持了较好的计算效率

  1. 本文设计了一个ZK协议，可以证明任意电路$C$上的$B$个求值，通信开销为$O(B+|C|)$个域元素（包含自由的加法门），之前最优的工作需要$O(B|C|)$个域元素
    本文的协议由一种称为信息论多项式认证码（Information-theoretic Poly Authentication Code）的工具实现
  2. 本文开发协议的优化实现，且具有较高的实用性，当$B=2048,|C|=2^{20}$，带宽为50Mbps，16线程时，基于VOLE的QuickSilver每秒可以证明包含78万个乘法门的电路，每秒发送域元素的数量为每个乘法门一个
    相同环境下，本文协议的优化实现每秒可以处理的乘法门数量可以达到QuickSilver的18倍，且每秒发送域元素的数量仅为每个乘法门0.0064个（QuickSilver的156倍）
  3. 本文构造的ZK协议可以为任意电路证明单次执行，通信量仅为$O(|C|^{3/4})$，是首个基于任意电路的基于VOLE的ZK方案中达到亚线性阶的协议

1 Introduction

本文的主要优化目标为ZK协议的通信量，之前的方案中，在安全参数$\lambda$下，每个与门需要的通信量为$\lambda$比特

最近提出了基于向量不经意线性求值方式（Vector Oblivious Linear Evaluation，VOLE）构建的方案，此类方案具有更好的计算效率，同时可以将通信量减少至每个乘法门一个域元素（布尔电路只需要单比特），部分协议尝试解决VOLE中庞大的通信开销，比如QuickSilver$[YSWW21]$协议提出一个方法来证明多个多项式的计算，其中通信开销仅与最大阶的多项式的阶数呈线性关系，LPZKv2$[DILO22]$协议在电路结构为任意时，可以达到两倍的效率，该改进可以更高

尽管各个协议对通信量改进很大，但是还有两个主要的问题没有解决

  1. 循环/SIMD电路的亚线性通信开销：循环在一般的statement中很常见，ZK协议中的循环通常与SIMD（Single Instruction Multiple Data，单指令多数据）电路相关联，因为Prover可以为循环的所有迭代输入输出提供扩展的witness（因此所有的迭代都可以并行而非顺序验证）
  2. 任意电路的亚线性通信开销：对于任意电路的单次执行的情况而言，之前的研究尚未能将通信量减少至每个门一个域元素一下（若达到的话则意味着亚线性通信量，LPZKv2协议中的每个乘法门需要0.5-1个域元素）

这两类方法都可以在NIZK中实现，比如Ligero和GKR风格的证明$[GKR08,ZLW+21]$，但是性能和可扩展性都不如交互式ZK

因此本文的研究旨在提出一个协议，在确保类似的计算效率的前提下达到亚线性通信开销，本文的主要贡献如下

  • Sublinear ZK proof for SIMD circuits：为SIMD电路的证明设计了一个亚线性通信量的交互式ZK协议，任意电路$C$上的$B$个求值需要的通信开销为$O(B+|C|)$个域元素（本文称为$B,|C|-SIMD$电路），计算复杂度为$O(B|C|\log B)$
    协议在加法门上无开销，且可以与现有的基于VOLE的ZK协议无缝集成，从而可以用本文的新协议来证明SIMD子电路，并用其他协议来证明电路中非SIMD的部分

本文提出的协议基于基于信息论多项式认证码（IT-MAC）的新承诺方案，该方案可以以恒定的通信成本对高阶多项式进行承诺，主ZK协议利用IT-MAC在电路的所有求值过程中对导线值承诺，并逐一证明承诺的正确性
此外，本文还实现了本文提出的协议，并对其进行了效率测试

  • Sublinear ZK Proof ofr Generic Circuits：本文设计的协议在证明任意电路的单次执行可达到亚线性阶通信开销，对于电路$C$，协议需要发送$O(|C|^{3/4})$个域元素，计算复杂度为$O(|C|\cdot \log |C|)$
    协议的主要思想是将电路分解为独立的门，并将其视为SIMD电路证明，本文设计一种机制来检查不同门之间的导线值的一致性

尽管IP-PAC可以以几乎无开销的的方式检查对应元素的相等性，但是任意电路中的导线可能比较复杂，需要一个新的交叉多项式一致性检查来解决此类问题，本文2.4节中介绍了此类检查方

‍

2 Technical Overview

2.1 VOLE-based ZK Proofs

基于VOLE的ZK协议利用VOLE作为交互承诺方案并构建承诺与证明协议，此类承诺方案又称为IT-MAC

Prover对$x\in \mathbb F$承诺时，令Prover获取一个MAC值$M\in \mathbb F$，然后令Verifier获取一个本地密钥$K\in \mathbb F$和一个全局密钥$\Delta \in \mathbb F$，满足$M=K+x'\cdot \Delta$（Prover对$\Delta$的猜测是困难的，具体的IT-MAC可以看3.1节）

基于VOLE的ZK分为两个阶段

  1. 首先双方需要为电路中的所有导线值获取IT-MAC，由于IT-MAC满足加法同态，Prvoer只需要对所有乘法门的输入与输出导线值进行承诺（对加法门输出的承诺可以本地计算）
  2. 之后双方运行一个子协议，检查所有的乘法门均被正确计算（比如输出承诺等于输入的乘积的承诺），该检查为协议的核心（目前最优的方案的通信开销与电路大小呈线性阶）

通信开销主要来自于第一阶段，因为Prover每承诺一个导线值需要发送一个域元素（包含$|C|$个乘法门的电路需要$|C|$个域元素），不过对于特定结构的电路（低度多项式和分支电路），存在一种方式来获得更好的通信开销，但目前没有任何工作可以用于证明任意电路的单个或多个执行（最好的方案需要的通信量仍然与电路大小呈线性关系）

2.2 A New Commitment for Sublinear ZK

为了解决上述通信开销问题，本文的第一步是设计一个多项式承诺方案，使通信开销与阶数呈亚线性关系，承诺方案可以利用随机预言机实现，或者在满足加法同态的前提下利用RS码实现，设计该多项式承诺方案的主要挑战在于实现其加法同态以满足亚线性通信开销的需求

因此本文的主要思想是将基于VOLE的承诺方案扩展至线性关系之外，但是问题在于如何将多项式与IT-MAC组合起来

比如Prover希望承诺一个度数至多为$k$的多项式$f(\cdot)\in \mathbb F [X]$，Verifier随机选择一个密钥$\Lambda \in \mathbb F$，并以某种特殊的方式计算$f(\Lambda)$（计算方式后续介绍），此时Verifier知道$\Lambda,f(\Lambda)$，因此只要Prover不知道$\Lambda$，多项式$f$满足统计绑定性

这一承诺方式与基于VOLE的承诺方式类似，且满足加法同态，Verifier在不同的多项式$f,g$中使用相同的$\Lambda$，则Verifier可以计算$h(\Lambda)=f(\Lambda)+g(\Lambda)$，不过此时方案不再满足隐藏性，因为Verifier知道多项式在点$\Lambda$的值

这里有一个点很重要：除了Verifier之外，$f(\Lambda)$对于Prover而言也应当是隐藏的，因为如果Prover知道了足够多的求值，则Prover是可以本地还原$\Lambda$的值，解决这个问题的方式是通过引入一个掩码来隐藏$f(\Lambda)$的值，然后再提高$f$的度数（令Prover和Verifier分别获取$M\in \mathbb F,K\in \mathbb F$，满足$M=K+\Lambda \cdot f(\Lambda)$）

不过本文的提出的协议要求Verifier在某一时刻向Prover揭示$\Lambda$，然后Prover零知识证明关于$f(\Lambda)$的statement（注意：$\Lambda$向Prover揭示之后，就不再满足绑定性）

结合上述讨论的问题，本文的想法是在多项式的基础上组合IT-MAC：使用一个具有独立全局密钥$\Delta$的VOLE来认证$f(\Lambda)$，当Prover对一个多项式$f$承诺时，Prover选择$M\in \mathbb F$，Verifier选择$K\in \mathbb F$，满足$M=K+\Delta \cdot f(\Lambda)$，其中IT-MAC全局密钥$\Delta$仅由Verifier知道，且任意一方不知道$f(\Lambda)$，此时得到的承诺方案满足绑定性和隐藏性：当Prover揭示$(M,f(\cdot ))\neq (M',f'(\cdot ))$时，等式$M-M'=\Delta\cdot (f(\Lambda)-f'(\Lambda))$成立的概率为$O(\frac{1}{|\mathbb F|})$，因此恶意的Prover需要猜中$\Lambda$和$\Delta$中的至少其中一个才可以在两个不同的点揭示该多项式

上述提到的承诺方案与IT-MAC类似，本文将该承诺方案称为IT-PAC（IT-Poly Authentication Code），由于将$M,K$分配给双方后，IT-PAC满足完美隐藏性和统计绑定性，因此该方案为信息论的（不过IT-PAC和IT-MAC一样需要一个计算假设）

‍

2.3 Sublinear ZK Proof for SIMD Circuits

对于SIMD电路的亚线性ZK证明，本文的主要思想是将电路$C$中导线的$B$次求值编码为一个多项式，并用IT-PAC对该多项式承诺

给定任意一组$B$的坐标，可以将向量$x\in \mathbb F^B$编码为一个度为$B-1$的多项式$f(\cdot )\in \mathbb F[X]$，Prover需要证明所有的门都被正确计算，根据IT-PAC的加法同态性，计算加法门显然是正确，最大的挑战是在亚线性通信开销下证明乘法门的正确计算，下面详细介绍方法

对于电路$C$中的$B$个乘法门求值，Prover拥有导线值向量$x,y,z\in \mathbb F^B$，满足$x_i\cdot y_i=z_i(i\in [1,B])$，三个导线值向量均可以编码为多项式$f,g,h\in \mathbb F[X]$，Prover和Verifier分别拥有IT-PAC多项式$f,g,h$，且满足如下等式

$$ M_u=K_u+\Delta\cdot u(\Lambda) ,u\in \{f,g,h\} $$

这里有一个点：Prover可以在不知道多项式的情况下分两步证明该关系，首先Prover计算一个度为$2B-2$的多项式$\tilde h=f\cdot g\in \mathbb F[X]$，然后利用IT-PAC对该多项式承诺，此时Prover可以利用这四个多项式证明下列两个点，且通信成本几乎可以忽略

  1. $\tilde h$的承诺为输入多项式$f,g$的乘积
  2. 多项式$h,\tilde h$在前$B$个求值中具有相同的值，也即对于给定的$\alpha_1,\dots\alpha_B\in \mathbb F$，有$h(\alpha_i)=\tilde h(\alpha_i),i\in [1,B]$

不过为了证明多项式的乘积，需要证明$\tilde h(\Lambda)=f(\Lambda)\cdot g(\Lambda)$（Prover不知道$\Lambda$），Prover和Verifier都拥有上述IT-MAC的三个多项式$f(\Lambda),g(\Lambda),\tilde h(\Lambda)$，但是Prover不知道被MAC的值，此外如果Prover知道足够多的多项式，则其可以通过本地计算$\Lambda$来攻破承诺方案的绑定性

因此需要重新考虑$\Lambda$的作用，由于$\Lambda$中的随机性确保了方案的绑定性，若Prover知道了$\Lambda$则意味着其可以将承诺揭示至另一个不同的值，不过如果Prover不会揭示更多的值，则让Prover知道$\Lambda$也无所谓（前提是需要确保Prover不会揭示更多的值，或者Prover在知道$\Lambda$之前已经揭示了所有的值，这样也可以），为了防止此类情况发生，可以通过下列方式检查多项式乘法的正确性

  1. 令Prover用IT-PAC承诺所有需要揭示的值
  2. Verifer向Prover揭示$\Lambda$（若Verifier发送错误的$\Lambda$，则Prover可以用协议的其他部分来发现Verifier的错误）
  3. 双方利用QuickSilver，对的所有多项式乘法检查上述关系

之前提到Prover有两个多项式$h,\tilde h$，Prover和Verifier有这两个多项式的IT-PAC，且需要证明$h(\alpha_i)=\tilde h(\alpha_i),i\in [1,B]$，这一特性是sacrificable的$[DPSZ12]$：任意两对多项式$(h_1,\tilde h_1),(h_2,\tilde h_2)$，若这两对多项式是sacrificable的，当且仅当它们的随机线性组合也是sacrificable的（不满足的概率为$O(\frac{1}{|\mathbb F|})$）

利用这一特性可以完成批量检查：双方首先生成两个满足上述性质的IT-PAC多项式$(r,s)$（Prover诚实），然后双方计算待检查的输入多项式和新生成的随机多项式之间的IT-PAC的一个随机线性组合，由于系数是公共的且IT-PAC满足加法同态，因此可以本地计算随机线性组合，此时Prover可以揭示生成的多项式，并由Verifier本地检查

协议可以在相同的通信开销下检查任意数量的多项式对，因此检查一对$(B-1,2B-2)$的多项式需要的通信开销为$O(B)$

对于协议的通信开销而言，在随机预言机模型中，上述两种检查的通信开销至多为$O(B)$，在检查之前还需要承诺$2|C|$个多项式，每个多项式的度数至多为$B-1$或$2B-2$，下文中介绍如何构造此类IT-PAC，总体通信开销为$O(B+|C|)$，可以通过调整协议的参数来将通信量进一步的降低：可以将$k$个电路整合为一个更大的电路，并将SIMD电路视为$B'=B/k$个子电路，每个电路的大小为$C'=k|C|$，此时通信开销为$O(B'+C')=O(B/k+k|C|)$，当$B\geq |C|$时，可以令$k=\sqrt{B/|C|}$，此时通信开销为$O(\sqrt{B|C|})$

2.4 Sublinear ZK Proof for Generic Circuits

现在需要在SIMD电路中推广上述思想，以证明对任意电路的单一求值，将电路分解为门，从而在所有门上执行SIMD思想，但是由于电路的布线是任意的，电路中的一个门的输出可能是另一个门的输入，因此需要一个确保门之间一致性的方法

假设电路的加法门与乘法门数量分别为$C_A,C_M$，可以将电路的加法门与乘法门表示为$\{a_i,b_i,c_i\}_{i\in [C_A]},\{a'_i,b'_i,c'_i\}_{i\in [C_M]}$，对应的承诺值为$\{w_{a_i}\}_{i\in [1,C_A]},\{w_{b_i}\}_{i\in [1,C_A]},\{w_{c_i}\}_{i\in [1,C_A]},\{w_{a'_i}\}_{i\in [1,C_M]},\{w_{b'_i}\}_{i\in [1,C_M]},\{w_{c'_i}\}_{i\in [1,C_M]}$

由于IT-PAC可以批量承诺值，因此每个集合中可以每次承诺$B$个值来批量承诺，之后双方可以用SIMD证明证明$\{w_{a_i}+w_{b_i}=w_{c_i}\}_{i\in [1,C_A]},\{w_{a'_i}\cdot w_{b'_i}=w_{c'_i}\}_{i\in [1,C_M]}$

对于给定的电路，这一过程需要承诺$3(C_A+C_M)$个导线值，但电路中只有至多$C_A+C_M+I$个不同的导线在不同的IT-PAC的不同槽中出现超过一次，此时只需要证明不同的IT-PAC承诺值之间的一致性

具体而言，Prover拥有$(M_f,f),(M_g,g)$，Verifier拥有$K_f,K_g$，满足$M_u=K_u+\Delta\cdot u(\Lambda),u\in\{f,g\}$，Prover需要对于$i,j\in [1,B]$，证明$f(\alpha_i)=g(\alpha_j)$，注意到这个检查过程具有sacrificable性质，因此可以让Prover先用IT-PAC对两个随机多项式$r,s$在约束$r(\alpha_i)=s(\alpha_j)$进行承诺，之后双方可以通过揭示$\chi \cdot f+r$和$\chi \cdot g+s$来检查多项式$f,g$的承诺的一致性（$\chi \in \mathbb F$为公共系数），然后Verifier可以本地检查第$i$个和第$j$个位置是否具有相同的值，对于阶数至多为$B$的多项式，上述检查的通信开销为$O(B)$，对于给定的索引对$(i,j)$，上述检查可以很容易的扩展到检查多项式对的列表，且不会增加通信开销

尽管电路中有至多$2(|C|/B)$个一致性检查，每一个都属于$B^2$个一致性检查中的一个，因此导线值的一致性检查的总的通信开销为$O(B^3)$，因此需要$O(|C|/B+B)$的通信量来完成承诺和证明，以及$O(B^3)$来检查输入与输出导线之间的一致性，为了达到预期的通信量，本文令$B=O(|C|^{1/4})$

2.5 Efficiently Generating IT-PAs

本节介绍一种有效分配IT-PAC的协议，分摊的通信开销与多项式次数无关

注意到在此类约束条件下预处理的IT-PAC不太有用：给定随机多项式上的IT-PAC仍然需要与多项式次数呈线性阶的通信量来获得该多项式上的IT-PAC，且因为IT-PAC为信息论的，这一预处理过程最大的挑战在于承诺的可抽取性

不过这里有个关键的点：除了电路的输入导线以外，其余导线均无需抽取承诺，对于电路中的导线，独立定义足以证明底层ZK协议中的知识，因此可以设计一个更有效地IT-PAC来生成协议，具体如下

假设Prover需要承诺一个度至多为$k$的多项式$f$，首先由Verifier选择一个随机值$\Lambda\in \mathbb F$，并利用加法同态计算一个幂列表$<\Lambda^i>,i\in [1,k]$的密文，Verifier将该密文列表发送给Prover，之后双方获取一个随机的IT-PAC，Prover获取$r,M^*\in \mathbb F$，Verifier获取$K^*\in \mathbb F$，以及一个全局密钥$\Delta\in \mathbb F$，满足$M^*=K^*+r\cdot \Delta$，此时Prover可以本地计算$f(\Lambda)-r$，并将结果发送给Verifier，之后Verifier可以解密得到$s=f(\Lambda)-r$，最后Prover输出$M=M^*$，Verifier输出$K=K^*-s\cdot \Delta$（由于$M-K=M^*-K^*+(f(\Lambda)-r)\cdot \Delta=f(\Lambda)\cdot \Delta$，因此正确）

利用最近的基于LPN的VOLE协议，生成随机IT-MAC的成本可以忽略不计，在Verifier发送$\Lambda$的所有幂的密文之后，Prover只需要为每个多项式发送一个域元素的密文即可，因此承诺$l$个度为$k$的多项式需要的通信复杂度为$O(l+k)$个域元素，此外基于LWE的AHE还可以确保计算不会太重（因为只需要满足加法同态即可，乘法同态的计算开销太大所以不考虑使用），注意到协议只在半诚实模型中是安全的，不过足以适用于本文的ZK协议

接下来是如何利用一个更弱的IT-PAC来构造协议，前面提到了Verifier需要向Prover揭示$\Lambda$，而此时Verifier的秘密值只有$\Delta$，为了确保这一过程的合理性，需要有一个协议来建立一些秘密值并随后揭示该值的协议流程：比如基于姚电路的ZK协议$[JKO13]$中，Verifier向Prover发送混淆电路，Prover对电路进行求值并对输出导线密钥进行承诺后，Verifier揭示混淆电路中所有的秘密值，从而Prover可以在揭示输出导线密钥之前检查其正确性

本文的协议中，加密$\Lambda$的所有幂次的作用与混淆电路的功能相同，因此可以利用延迟揭示与检查技术（delayed open and check），令Verifier对一个种子值进行承诺，种子将用于导出$\Lambda$和随机性以加密其幂次，所有Prover的消息都以承诺的方式出现，只有在Verifier揭示种子，Prover获取到$\Lambda$后才会揭示其消息，若Verifier发送的密文未被正确计算，Prover将会终止且不会揭示消息（隐式的防止了恶意的Verifier），这一方法实质上可以将针对半诚实Verifier模型的任意IT-PAC提升为恶意Verifier模型

而对于恶意的Prover而言，考虑一个点：如果忽略承诺的揭示阶段，则协议是两轮的，因此恶意的Prover唯一可以做的就是向Verifier发送错误的密文，此时Verifier解密后会得到不同的值，若出现此类情况，则意味着Prover使用了不同的多项式，必然会被Verifier发现，因此并不会攻破合理性

之后就是为协议增加可抽取的性质，如前面所述，$f$上的IT-PAC非常接近于$f(\Lambda)$上的IT-MAC（Verifier已知$\Lambda$），根据IT-PAC的特殊结构，可以抽取$\Lambda$，但是需要额外的开销，不过本文的方式可以利用IT-MAC承诺多项式的所有系数，之后只需要证明两个表示中承诺的值的一致性即可

比如双方都具有多项式$f=\sum_{i\in [0,k]}f_i\cdot X^i$的IT-PAC及其系数的IT-MAC，满足

$$ M=K+\Delta\cdot f(\Lambda)\\ M_i=K_i+\Delta\cdot f_i,i\in [0,k] $$

由于$f(\Lambda)$是$f_i$的线性组合，因此在Prover知道$\Lambda$后，双方可以计算$f(\Lambda)-\sum_{i\in[0,k]}f_i\cdot \Lambda^i$的IT-MAC，但是Prover知道$\Lambda$意味着攻破了协议的合理性，因此必须限制Prover对所有的消息进行承诺，并在Verifier向Prover发送$\Lambda$之前揭示这些消息

本质上，通过使用不同的$\Lambda$和$\Delta$，可以为Prover提供一些不损害协议安全性的优势，但是实现可抽取性需要通信成本与多项式的度成线性关系，不过本文的ZK协议中只需要在电路的输入层使用它，电路中的其他导线仍然使用不可抽取的IT-MAC，所以不会对整体的通信量有较大的影响

‍

3 Preliminaries

  • $\lambda,\rho$：分别表示计算与统计安全参数
  • $a\larr S$：表示从集合$S$中随机选择一个值赋给$a$
  • $\boldsymbol x$：表示列向量，$x_i$表示第$i$个元素
  • $[a,b]$：$a,b\in \N,a<b$，表示集合$\{a,\dots,b\}$
  • $y\larr A(x)$：表示算法$A$的输入为$x$，输出为$y$
  • $y\larr A(x;r)$：使用随机性$r$作为算法的输入
  • $f$：表示域$\mathbb F$上度为$k$的多项式
  • $negl(\cdot )$：$negl(\lambda)=o(\lambda^{-c})$，其中$c$为常数
  • $|C|$：电路$C$中包含的门的数量
  • $B$：假设电路以不同的输入计算$B$次

若$B>1$，则表示$C$的$B$个拷贝构成一个SIMD电路，简写为$B-|C|$-SIMD电路，否则认为$C$为单一普通电路

本文协议在UC框架中$[Can01]$UC实现了ZK函数$\mathcal F^B_{ZK}$（如图1所示），若$B=1$，则$\mathcal F^B_{ZK}$表示标准ZK功能，若$B>1$，则$\mathcal F^B_{ZK}$捕获了$B-|C|$-SIMD电路的可满足性的情况，具体可以看原文的附录A

3.1 Information-Theoretic MAC

信息理论消息认证码（IT-MAC）最初是在安全多方计算的背景下提出的$[BDOZ11,NNOB12]$，本文的ZK协议将IT-MAC视为承诺

  • Commitments with IT-MACs：对消息$x$的承诺记为$[x]$，表示Prover拥有消息$x\in \mathbb F$和MAC $M\in \mathbb F$，Verifier拥有本地密钥$K\in \mathbb F$，双方拥有固定的的全局密钥$\Delta\in \mathbb F$，其中$K,\Delta$为随机的
  • Opening：揭示$[x]$过程如下，Prover向Verifier发送$(x,M)$，同时检查是否有等式$M=K+\Delta\cdot x$成立，若恶意的Prover尝试将$[x]$揭示至一个不同的值$x'\neq x$，则其必须伪造MAC $M'=K'+\Delta\cdot x'$，这意味着Prover知道全局密钥$\Delta=(M-M')/(K-K')$，根据假设，Prover成功的概率为$\frac{1}{|\mathbb F|}$（假设$|\mathbb F\geq 2^\rho|$）
  • Linear Combination：IT-MAC满足加法同态性，给定公共系数$c_0,\dots,c_l\in \mathbb F$和承诺值$[x_1],\dots,[x_l]$，双方均可本地计算$[y]=\sum_{i\in[1,l]}c_i\cdot x_i+c_0$

对于公共值$c\in \mathbb F$，Prover和Verifier可以无需交互的直接定义IT-MAC值$[c]$（令$M=0,K=-c\cdot \Delta$即可），附录A.2介绍了VOLE生成IT-MAC和标准VOLE的方式

揭示承诺包含两个步骤，首先Prover需要将$x_1,\dots,x_l$发送给Verifier，然后Verifier利用CheckZero对所有的$i\in [1,n]$，检查$[y_i]=[x_i]-x_i$是否为0的承诺，CheckZero的总体通信量为$\lambda$比特，且为非交互式的，令$H:\{0,1\}^*\rarr \{0,1\}^\lambda$为随机预言机，CheckZero需要Prover向Verifier发送$M=H(M_1,\dots,M_n)$，Verifier检查是否有$M=H(K_1,\dots,K_n)$，若等式成立则意味着对于每个承诺值$[y_i]$，均有$M_i=K_i$，根据$[DNNR17]$的结论，若检查通过，且存在$i\in [1,n]$使得$y_i\neq0$的概率至多为$\frac{1}{|\mathbb F|}+\frac{1}{2^\lambda}$

3.2 VOLE-Based Zero-Knowledge Proofs

矢量不经意线性评估（VOLE）是密码协议设计常用的原语，具有亚线性通信的VOLE协议的研究可用于构造可流式指定验证者零知识（DVZK）证明，证明时间快，内存占用小

具体而言，给定一个域$\mathbb F$上基于VOLE承诺的集合$\{([x_i],[yi],[z_i])\}_{i\in [1,l]}$，DVZK证明可以让Prover使得Verifier相信$z_i=x_i\cdot y_i \in \mathbb F$，且需要的通信开销很小（QuickSilver只需要$\lambda+2|\mathbb F|$比特），本文将此类DVZK记为元组$\{([x_i],[yi],[z_i])_{i\in [1,l]}|\forall i\in [1,l],z_i=x_i\cdot y_i\}$

在随机预言模型中，使用Fiat-Shamir启发式算法可以将轮复杂度降低到仅一轮，此类情况下为了确保安全性，$\mathbb F$的大小至少为$2^\lambda$，DVZK证明在$\mathcal F_{VOLE}$-hybrid模型中实现了$\mathcal F^1_{ZK}$

本文记$\epsilon_{dvzk}$表示DVZK的合理性错误，对于两轮通信的情况下，$\epsilon_{dvzk}=3/|\mathbb F|+q/2^\lambda=3/|\mathbb F|+negl(\lambda)$，$q$为请求随机预言机的数量（用于生成随机种子）

3.3 Additively Homomorphic Encryption

本节描述私钥设置中加法同态加密（AHE）方案的定义，它指定了我们的IT-PAC生成协议所需的性质

假设明文在域$\mathbb F$中，AHE方案包含四个算法，分别是生成公共参数的$Setup$算法，生成密钥的$KeyGen$算法，加密与解密算法$Enc$和$Dec$

在本文的IT-PAC中，将加密表示为$<m>=Enc(sk,m;r)$，并默认要求AHE方案满足CPA安全和电路隐私（circuit privacy）$[IP07]$，同时还要求AHE方案提供度限制性（degree restriction）：对于整数$k\geq 1$，给定公共参数集合$par$和密文序列$<\Lambda>,\dots<\Lambda^k>,\Lambda\in \mathbb F$，对于一个度至少为$k+1$的多项式$f$，难以计算$<f(\Lambda)>$

本文使用单个级别的BGV同态加密来实例化AHE方案$[BGV12]$（附录A.3中提供了AHE的定义和BGV-AHE的简要介绍）

‍

4 Information-Theoretic Polynimial authentication Codes

本节介绍了信息论多项式认证码（IT-PAC）的概念，本文的协议将IT-PAC用于多项式承诺，此外本文还描述了一种在多个点检查两组多项式求值一致性的方式，同时提出了一种生成一批IT-PAC的具体有效的协议

4.1 Definition of IT-PAC

为了简单起见，在一个大的域$\mathbb F$上定义IT-PAC，当然也可以以简单的方式将IT-PAC的定义扩展至一般情况（比如在一个小的域$\mathbb F=\mathbb F_2$上定义，并在大的扩域$\mathbb K$上验证）

具体而言，在域$\mathbb F$上定义IT-PAC如下

  • Commitments with IT-PAC：Verifier拥有一个全局密钥$\Delta\in \mathbb F$和多项式密钥$\Lambda\in \mathbb F$，这两个密钥可以在不同的IT-PAC之间复用
    将度为$k$的多项式$f=\sum_{i=0}^kc_i\cdot X_i\in\mathbb F[X]$的IT-PAC承诺记为$[f]$，Prover拥有多项式$f$和MAC值$M\in \mathbb F$，Verifier拥有$K,\Lambda,\Delta\in \mathbb F$，满足$M=K+\Delta\cdot f(\Lambda)$

在IT-PAC中，密钥$K$称为本地密钥，并且可以将$f$的IT-PAC承诺视为$f(\Lambda)$的IT-MAC承诺

  • Opening：Prover向Verifier发送$(f,M)$，Verifier检查$M=K+\Delta\cdot f(\Lambda)$是否成立，若Prover作弊，则其必须伪造一个MAC值$M'=K+\Delta\cdot f'(\Lambda)$，且$f'(\Lambda)\neq f(\Lambda)$（成功的概率为$\frac{1}{|\mathbb F|}$），或者Prover伪造一个多项式$f'\neq f$，满足$f'(\Lambda)=f(\Lambda)$
    若Prover成功实现了上述第二种情况，则表明$f'-f$为非零多项式，且该多项式的度至多为$k$，根据SZ引理，该多项式在一个随机点$\Lambda$上求值为0的概率至多为$k/|\mathbb F|$

综上，恶意的Prover成功的概率不超过$(k+1)/|\mathbb F|$

  • Linear Combination：与IT-MAC类似，IT-PAC同样满足加法同态
    对于给定的公共系数$c_0,\dots,c_l\in \mathbb F$和IT-PAC$[f_1(\cdot)],\dots,[f_l(\cdot)]$，Prover和Verifier可以对多项式$f$本地计算下列两个等式

$$ \begin{aligned} [g(\cdot)] &=\sum_{i=1}^l c_i\cdot [f_i(\cdot )]\\ M_g&=\sum^l_{i=1}c_i\cdot M_{f_i}\\ K_g&=\sum^l_{i=1}c_i\cdot K_{f_i}-c_0\cdot \Delta \end{aligned} $$

其中$g(\cdot )=\sum^l_{i=1}c_i\cdot f_i(\cdot)+c_0$

从而Prover和Verifier可以无需交互的直接定义MAC为IT-PAC$[f(\cdot)]$，密钥为$-\Delta\cdot f(\Lambda)$

对于给定的$k+1$个不同的元素$\alpha_1,\dots,\alpha_{k+1}\in \mathbb F$，IT-PAC同样对值$f(\alpha_1),\dots,f(\alpha_{k+1})$进行承诺，因为$k+1$个值可以唯一确定一个$k$阶多项式（反之亦然）

‍

4.2 Batch Check of Poly. Eval.

提出了一个交互式方式来检查两组IT-PAC在单个点或多个点上的多项式求值的一致性，一致性检查在批处理中进行，通信与IT-PAC的数量无关

具体而言，给定两个公共域元素集合$\{\alpha_i\}_{i\in[1,t]},\{\beta_i\}_{i\in[1,t]}$和两个IT-PAC集合$\{[f_j(\cdot)]\}_{j\in[1,l]},\{[g_j(\cdot)]\}_{j\in[1,l]}$，批量检查可以对所有的$i\in [1,t],j\in[1,l]$，检查是否有$f_j(\alpha_i)=g_j(\beta_i)$，其中$f,g$的度分别为$m,k$，除非等式成立，否则不会泄露关于多项式的任何秘密信息，协议如图2所示

上述过程中，Prover首先生成两个多项式$r,s$（度分别为$k,m$），满足对于所有的$i\in [1,t]$，有$r(\alpha_i)=s(\beta_i)$成立，之后双方计算这两个多项式IT-PAC承诺$[r(\cdot)],[s(\cdot)]$，之后对于Verifier选择的公共系数$\chi_1,\dots,\chi_l$，双方本地计算$[f(\cdot)]=\sum^l_{i=1}\chi_i\cdot [f_i(\cdot)]+[r(\cdot)],[g(\cdot)]=\sum^l_{i=1}\chi_i\cdot [g_i(\cdot)]+[s(\cdot)]$，Prover将多项式$f,g$发送给Verifier，Verifier检查$f,g$的度分别为$k,m$，且对于$i\in[1,t]$，有$f(\alpha_i)=g(\beta_i)$

最后双方本地计算$[\mu]=[f(\Lambda)]-f(\Lambda),[\nu]=[g(\Lambda)]-g(\Lambda)$，并运行CheckZero协议来检查$\mu=0,\nu=0$，若检查不通过则Verifier终止

为了进一步减少通信开销，可以利用随机预言机来生成一致性检查中步骤2公共系数$\chi_1,\dots,\chi_l$，此时通信开销为$O(k+m)$

这里给出一个重要引理，用于ZK协议的安全性证明，引理的证明在原文的附录B

不难看出，可以扩展图2中的Batch Check过程，使其在$t$个不同的点上检查$l$个度为$k$的多项式求值的正确性，具体而言，Prover向Verifier发送$f_j(\alpha_1),\dots,f_j(\alpha_t),j\in [1,t]$，之后双方对于所有的$j\in [1,l]$，本地计算一个IT-PAC值$[g_j(\cdot)]$，这里$g_j$为一个由$f_j(\alpha_1),\dots,f_j(\alpha_t)$构建的度为$t-1$的多项式，之后Prover和Verifier执行$BatchCheck_{k,(t-1),t}$来检查对于所有的$i\in[1,t],j\in[1,l]$，是否有等式$f_j(\alpha_i)=g_j(\alpha_i)$成立

对于$t=k+1$的特例，上述过程是检查揭示整个多项式的承诺的正确性，无需利用随机的IT-PAC来掩盖输入$[f_1(\cdot)],\dots,[f_l(\cdot)]$之间的线性组合，上述扩展过程在其他ZK协议和应用中可能有用

4.3 Efficient Protocol to Generate IT-PACs

下面介绍生成IT-PAC的具体有效协议，协议在$\mathcal F_{VOLE},\mathcal F_{Com}$混合模型中工作，并采用AHE来在秘密点$\Lambda$处生成多项式求值的加法份额，利用这些加法份额，VOLE相关性可以局部转换为批量IT-PAC

对于Verifier发送的AHE的密文，可以利用ZK协议来证明密文的正确性，但是这样会引入更多的通信量，因此本文利用承诺-揭示的方式来代替ZK协议

具体而言，Verifier密文的正确性通过承诺来确保，并在后续的某个时间点通过揭示随机性来验证，可以利用PRNG来生成随机性以进一步降低通信开销，但是Verifier发送的密文在随机性揭示之前可能是不正确的，因此可以让Prover先对同态计算的密文进行承诺，并在检查Verifier的密文的正确性后揭示这个密文，这样一来，通过对错误的密文执行一个多项式求值，可以消除秘密多项式泄露的可能性，因为在协议的后续阶段需要揭示密钥，因此承诺-揭示的方式足以解决上述问题

基于承诺-揭示的方法，图3描述了生成IT-PAC的具体协议，生成全局密钥$\Delta$的初始化阶段只需要运行一次，但是其他阶段需要执行多次，每次执行都会生成新的多项式密钥$\Lambda$和该密钥下对应的一批IT-PAC，对于生成度为$k$的$l$个IT-PAC，需要的总通信量为$O(k+l)$（其中用于生成VOLE相关性的通信是亚线性阶的）

5 Zero-Knowledge Proofs with Sublinear Communication

5.1 Sublinear ZK Proof for SIMD Circuits

图4展示了本文的ZK协议$\Pi^{SIMD}_{ZK}$如何在$\mathcal F_{VOLE}$混合模型中证明SIMD电路的可满足性，协议包含另一个子协议$\Pi_{PAC}^{(2B-2)}$，因此需要调用承诺函数$\mathcal F_{Com}$，在执行这个子协议来生成IT-PAC时，Verifier的本地密钥的生成事件被延迟到多项式密钥揭示之后，因此加法门输出的IT-PAC上的本地密钥也会被推迟

尽管Prover可以在$\Lambda$揭示之前执行BatchCheck基础过程的检查，但在揭示$\Lambda$并计算IT-PAC上的本地密钥后，Verifier可以检查Prover发送的值

若$\mathcal F_{VOLE}$以基于LPN的VOLE协议实例化时，通信量可达到亚线性阶，而协议$\Pi^{SIMD}_{ZK}$在证明$(B,|C|)$-SIMD电路时，通信复杂度为$O(B+|C|)$（加法门不影响开销），若DVZK证明至多为两轮时，$\Pi^{SIMD}_{ZK}$在$\mathcal F_{VOLE}$混合模型中有6轮

注意到子协议$\Pi_{PAC}^{(2B-2)}$的所有调用可以并行执行，CheckZero执行可以合并为一次，基于LPN的VOLE协议的实现只有常数轮，因此本文的ZK协议也具有常数轮

$\Pi^{SIMD}_{ZK}$的安全性由下述定理证明，定理假设合理性错误$\epsilon_{dvzk}$至多为$3/|\mathbb F|+negl(\lambda)$，定理的证明在原文的附录C

Streaming ZK proofs.

对于非常大的电路，需要一批一批的对其证明（一次证明一批门），此时对于$\Pi^{SIMD}_{ZK}$的每次执行，$\Lambda$都会被揭示，因此在$\Lambda$揭示后生成的IT-PAC承诺不再具有绑定性

为了确保协议的绑定性，在下一次执行前，Verifier需要利用子协议$\Pi_{PAC}^{(2B-2)}$生成一个新的密钥$\Lambda'$，之后双方需要将原来的IT-PAC承诺转换为新密钥下的IT-PAC承诺（多项式不变），新的多项式承诺将用于下一批次的证明

为了实现在新密钥下的转换，双方需要在密钥$\Lambda$和$\Lambda'$揭示前调用子协议$\Pi_{PAC}^{(2B-2)}$生成新密钥下的IT-PAC，具体而言，IT-PAC的多项式密钥转换的一致性检查如下

  • 线性组合阶段：在新旧密钥解释之前，双方需要执行下列步骤

    1. 双方利用不同的多项式密钥，调用子协议$\Pi_{PAC}^{(2B-2)}$生成两个随机的IT-PAC $[r(\cdot)]_{\Lambda},[r(\cdot)]_{\Lambda'}$，其中$r$为一随机多项式，度与多项式$v_i$相等
    2. Verifier选择一个随机种子$seed$发送给Prover，之后双方计算$(\chi_1,\dots,\chi_l)=H(seed)\in \mathbb F^l$
    3. 双方本地计算两个承诺$[v(\cdot)]_{\Lambda}=\sum^l_{i=1}\chi_i\cdot [v_i(\cdot)]_{\Lambda}+[r(\cdot)],[v(\cdot)]_{\Lambda'}=\sum^l_{i=1}\chi_i\cdot [v_i(\cdot)]_{\Lambda'}+[r(\cdot)]_{\Lambda’}$，之后Prover将多项式$v=\sum^l_{i=1}\chi_i\cdot v_i+r$发送给Verifier
  • 检查阶段：双方本地计算承诺$[\epsilon]=[v(\Lambda)]-v(\Lambda)，[\sigma]=[v(\Lambda')]-v(\Lambda')$，然后调用$CheckZero([\epsilon],[\sigma])$，检查这两个承诺是否均为0，若检查不通过则Verifier终止

Verifier在密钥$\Lambda$和$\Lambda'$揭示后执行上述检查

由于$v_1,\dots,v_l$的线性组合由随机多项式$r$隐藏，从而可以提供零知识性质，根据Thm1，由于所有的IT-PAC都在公共系数$(\chi_1,\dots,\chi_l)$被确定前，两个多项式密钥揭示后才生成的，且单多项式$v$揭示确保了一致性，因此上述过程的合理性错误至多为$2B/|\mathbb F|+negl(\lambda)$

Integrating AntMan with VOLE-based ZK proofs

基于VOLE的ZK证明在证明单个通用电路的通信量与电路大小成线性关系，但图4所示的ZK协议$\Pi^{SIMD}_{ZK}$实现了证明SIMD电路的次线性通信，可以将$\Pi^{SIMD}_{ZK}$集成到基于VOLE的ZK协议中来获得证明单个通用电路的更好通信效率，$\Pi^{SIMD}_{ZK}$还可以用于证明具有SIMD结构的子电路，电路的其余部分采用基于VOLE的ZK协议来完成证明

当$\Pi^{SIMD}_{ZK}$协议使用IT-PAC评估电路时，基于VOLE的ZK协议使用IT-MAC来求值电路，此类情况需要有一个高效的方式在IT-PAC和IT-MAC之间转换，简单来说如下：$\Pi^{SIMD}_{ZK}$生成的IT-PAC为$[v_1(\cdot )],\dots,[v_l(\cdot )]$，$y_{j,i}=v_j(\alpha_i),i\in[1,B],i\in [1,l]$表示需要进行IT-MAC承诺的输出值，对于所有的$i\in[1,B],i\in [1,l]$，双方可以在密钥$\Lambda$揭示之前生成一个IT-MAC$[y_{j,i}]$

具体而言，对于所有的$i\in[1,B],i\in [1,l]$，调用$\mathcal F_{VOLE}$生成一个随机的IT-MAC值$[r_{j,i}]$，之后Prover向Verifier发送$d_{j,i}=y_{j,i}-r_{j,i}$，双方计算$[y_{j,i}]=[r_{j,i}]+d_{j,i}$

在揭示之后，双方可以执行图4中的验证程序来检查IT-PAC $[v_j(\cdot)]$和IT-MAC $([y_{j,1}],\dots,[y_{j,B}])$的一致性，也即双方本地计算IT-MAC值$[y_j]=\sum_{i\in [1,B]}\delta_i(\Lambda)\cdot[y_{j,i}]$，并检查$CheckZero([v_j(\Lambda)]-[y_j])$

5.2 Sublinear ZK Proof for Generic Circuits

本节介绍如何将SIMD电路上的ZK协议（图4）扩展为具有亚线性通信量的单个通用电路可满足性的ZK协议，首先需要做的是将通用电路$C$编译为一个等价电路$C'$，其中$|C'|=|C|+O(B)$，$B$为单个IT-PAC承诺的导线值的数量，此外，新的等价电路还需要满足下列性质

  1. 对于每个输入$w$，均有$C(w)=C'(w)$
  2. 输入门、加法门、乘法门的数量均要求为$B$的倍数，且至少有$B$个输出门
  3. 每$B$个相同类型的门分为一组，其中每个组中的$B$个相关导线值由IT-PAC承诺

利用$[YW22]$中添加伪导线和伪门的方法可以实现上述编译过程，其中伪线上的值置0，本文的附录D详细表述了此类预处理的电路

之后还需要处理$B$个门的输入导线与前一层任意一组$B$个门的输出导线不匹配的情况，此时这些输入导线尚未被承诺至IT-PAC，因此需要双方利用子协议$\Pi_{PAC}^{(2B-2)}$为这些值生成承诺至，但是对于恶意的Prover，IT-PAC承诺的值可能与前一层中不同组的$B$个门上的输出导线不一致，因此需要有一个高效的一致性检查来发现Prover的恶意行为（图2中的BatchCheck）

具体而言，对于每个输入IT-PAC $[\hat g(\cdot)]$，若第$j$个导线的值$\hat g(\alpha_j)$是来自第$i$个导线值$\hat f (\alpha_i)$（对应于输出IT-PAC承诺值$[\hat f(\cdot)]$），则有$\hat f(\alpha_i)=\hat g(\alpha_j)$，这里将$([\hat f(\cdot)],[\hat g(\cdot)],i,j)$视为一个元组，本文的2.4节中介绍了如何在批处理中检查导线元组的一致性的方法，下文中给出了混合结构

用于证明单个通用电路的亚线性ZK子协议$\Pi^{generic}_{ZK}$可以通过下列方式在SIMD电路上扩展协议$\Pi^{SIMD}_{ZK}$（如图4所示）

  1. 预处理电路：双方依照图8对电路电路进行预处理，得到一个等价电路$C'$（与原始电路输出相同），令$w\in \mathbb F^{mB}$表示电路$C'$的输入（包含实际witness和伪零值）

  2. 电路求值：输入预处理过程与协议$\Pi^{SIMD}_{ZK}$基本相同，区别如下

    • 将$w$解析为$(w_1,\dots,w_B)$，其中$w_{1,j},\dots,w_{B,j}(j\in [1,m])$（这些值对应于第$j$组中的$B$个门的输入）为被打包在一组内的值，并由IT-PAC承诺，此外，$w$还会被$mB$ IT-MAC承诺
    • 若$w_{i,j}(i\in[1,B],j\in[1,m])$对应于一个伪零值，则其IT-MAC值$[w_{i,j}]=0$可以由双反本地生成，若$w_{1,j},\dots,w_{B,j}(j\in [1,m])$对应于$B$个伪零值，则IT-PAC值$[u_j(\cdot)](u_j(\alpha_i)=w_{i,j}=0)$也可以由双方在本地生成

按照预定的拓扑顺序，双方可以计算协议$\Pi^{SIMD}_{ZK}$中的加法门和乘法门，但是有两点例外

    • 若同一组内的$B$个门的输入线不对应于上一层中任意一个组的$B$个输出线，则Prover计算一个度为$B-1$的多项式$\hat g$，满足$\hat g(\alpha_i)=z_i(i\in [1,B])$，其中$\{z_i\}_{i\in [1,B]}$为这些输入导线值
    • 之后双方执行图3中的$\Pi_{PAC}^{(2B-2)}$协议来为该多项式生成IT-PAC值$[\hat g(\cdot)]$

    1. 导线元组的一致性检查：令$L(i,j)$表示所有的导线元组$\{([\hat f(\cdot)],[\hat g(\cdot)],i,j)\}$的集合，满足$\hat f_h(\alpha_i)=\hat g_h(\alpha_j)$，对于所有的$i,j\in [1,B]$，双方依照如下步骤对$L(i,j)$执行一致性检查

      • 令$l$表示$L$的大小，$([\hat f_1(\cdot)],[\hat g_1(\cdot)],i,j),\dots,([\hat f_h(\cdot)],[\hat g_h(\cdot)],i,j)$为$L$中的导线元组，双方在密钥$\Lambda$揭示之前，执行$BatchCheck_{(B-1),(B-1),1}$中的线性组合阶段（图2），以检查是否有$\hat f_h(\alpha_i)=\hat g_h(\alpha_j)(h\in [1,l])$
      • 之后双方执行$BatchCheck_{(B-1),(B-1),1}$d的检查阶段来完成上述检查，其中Verifier可以在密钥揭示并计算本地密钥的IT-PAC后执行上述过程，若检查不通过，则Verifier终止

    如上所述，一致性检查的一个直接优化如下：对于BatchCheck的所有$B^2$次执行，Verifier只向Prover发送一个随机种子，之后双方可以使用随机种子和预言机生成所有BatchCheck执行中需要的公共系数

    注意到所有的$B^2$次执行可以并行执行，上述一致性检查可以与乘法门的正确性检查并行执行，因此协议$\Pi^{generic}_{ZK}$执行的轮数与协议$\Pi^{SIMD}_{ZK}$相同，均为常数轮

    对于通信量，协议$\Pi^{generic}_{ZK}$需要的通信量为$O(|C|/B+B^3)$，若有$B=|C|^{1/4}$，则通信量可降低至$O(|C|^{3/4})$，当这些门的输入线上的值不由任何现有的IT-PAC承诺时，加法门的通信仅来自可能的IT-PAC生成（取决于电路结构）

    协议$\Pi^{generic}_{ZK}$的安全性与$\Pi^{SIMD}_{ZK}$类似，用于生成IT-PAC值$[\hat g(\cdot)]$的子协议$\Pi_{PAC}^{(2B-2)}$的模拟与生成$\{[h_j(\cdot)],[\tilde h(\cdot)]\}$的IT-PAC的$\Pi_{PAC}^{(2B-2)}$协议相同，此外，通过调用定理1证明中涉及的BatchCheck过程的模拟器，可以很容易地模拟线元组的一致性检查过程

    因此在协议$\Pi^{generic}_{ZK}$的安全性中，只需要分析导线元组一致性检查过程的合理性错误，协议的其它部分的安全性与定理1相同，也即下面这个引理2

    基于附录C的引理1和引理4，上述引理的证明是直接的，具体而言，若存在某个$h\in[1,l]$，使得存在某一对$(i,j)$，有$\hat f_h(\alpha_i)\neq \hat g_h(\alpha_j)$成立，则BatchCheck过程会以$2B/|\mathbb F|+negl(\lambda)$的概率终止，结合定理1和引理2，我们可以得到下面这个推论

    6 Implementation and Benchmarking

    看原文，这没啥好讲的

    7 Conclusion

    本文为基于VOLE的ZK证明的次线性通信迈出了第一步，并实现了SIMD电路的高具体效率，后续还有许多开放的问题值得进一步研究

    1. 设计一个具有相似效率的生成IT-PAC的协议，以实现可在ZK协议中使用的一些弱功能，并使ZK协议的设计模块化
    2. 通过$O(|C|^{3/4})$的通信提高了ZK协议的渐近和具体效率，以证明任意电路的单个执行
    3. 将协议的计算复杂性提高到与电路大小成线性的程度
    4. 开发自动工具，以采用不同的技术证明零知识陈述的不同部分

    References

    $[1]$ Chenkai Weng, Kang Yang, Zhaomin Yang, Xiang Xie, Xiao Wang:AntMan: Interactive Zero-Knowledge Proofs with Sublinear Communication. CCS 2022: 2901-2914

    ‍