Abstract
本文构造了一种无需FFT的SNARK，称为Testudo，具有接近线性时间的Prover，恒定时间的Verifier，恒定的证明大小和平方根阶的通用初始设置
Testudo基于Spartan协议，无需FFT，且采用了一种新的快速多元多项式承诺方案（来自于PST$[2]$和IPP$[3]$）
为了在Testudo中实现恒定大小的SNATK证明，本文递归组合了多项式承诺的揭示与Groth16协议
此外，本文还评估了Testudo及其构建模块，计算大小为$2^{25}$的多项式，本文的方案比PST快110倍，比Gemini快3倍，对于大小为$2^{30}$（大约1GB）的witness，本文只需要$2^{15}$（大约是几十KB）的初始设置
最后本文证明了用于证明数据并行计算的Testudo的变体，在验证$2^{10}$个基于Poseidon Hash的Merkle Tree时，比之前的常规版本快大约10倍
1 Introduction
之前的需要可信设置的SNARK方案都存在一个问题：这些可信设置都需要生成一个具有线性阶大小的CRS，这对于证明电路很大的场景来说问题很大，因为这些CRS必须下载到本地（甚至载入内存）
比如Filecoin使用的Groth16的CRS规模为$2^{30}$，很大
总而言之，具有可信设置的SNARK面临的问题为：是否可以设计一个具有较小通用可信设置、恒定证明大小和Verifier Time，可以快速验证的SNAKR
本文的主要贡献如下
- Testudo协议：本文基于Spartan协议和Groth16协议设计Testudo协议，主要思想是利用Groth16的Prover来证明Spartan
- Testudo-Comm：为了降低多项式承诺的揭示大小，本文基于PST和内积配对设计了新的多项式承诺方案，且该方案避免使用FFT
和Spartan类似，Testudo考虑规模为$N=2^n$的电路，其中电路的多项式表示包含$n$个变量，然后将Spartan的witness的多元多项式系数表示为大小为$\sqrt N$的仿真，然后利用PST对该方阵的每一行进行承诺，得到大小为$\sqrt N$的承诺向量$\vec A$
之后Prover在利用MIPP对$\vec A$进行承诺，得到最终承诺$T$（$T$为单个群元素）
此时揭示证明只需要反向执行PST和MIPP协议的揭示即可
- 双椭圆曲线验证：这个主要是解决兼容性问题，使用了可以进行配对的曲线BLS12-377
- 聚合：Testudo的外层采用Groth16，可以使用聚合工具SnarkPack来将多个Groth16聚合在一起
另一种方式是在内部进行聚合，然后再用单个Groth16证明
2 Preliminaries
这里需要R1CS、多项式承诺方案、SNARK的相关背景知识及其定义，具体可以看原文附录
然后看一下本文需要用到的记法
- $(\mathbb G_1,\mathbb G_2,\mathbb G_T,q,e,g)$：双线性配对，生成元为$g$，群的阶为$q$
- $p(x_1,\dots,x_n)$：$n$个变量的多线性多项式
本文用到的假设基于GGM，主要依赖下列两个假设
- 对于PST，要求$(\mu+1)\delta$-DH假设和$(\delta,\mu)$-扩展PKE假设
- 对于MIPP，要求$(q,m)$-ASSGP假设（这个假设可以看$[3]$）
其他前置知识包括：PST多项式承诺，Spartan协议，和校验协议，PST多项式承诺如下图所示，其他两个协议可以看之前的系列博客
3 A Generalized MIPP Protocol
本节先看一下如何获得具有平方根阶可信设置的多线性PCS方案
本文的做法是先将MIPP推广到多变量多项式（原来是单变量多项式），然后证明了当多项式以拉氏基多项式表示时，此类方法也有效（具体可以看原文的附录C.4）
其次是构造推广的MIPP协议，具体如下：对于群$\mathbb G_1$元素的向量$\vec A=[A_1,\dots,A_M]$，IPP利用CRS串$\vec h=[h_1,\dots,h_M]$对该向量承诺（$\vec h$中的元素来自于$\mathbb G_2$），承诺方式如下
$$ T=CM(\vec A,\vec h)=\prod_ie(A_i,h_i) $$
这里记$m=\log M$，本文中令$h_i=h^{\chi_i(\vec t)},i\in \{0,1\}^m$，其中$\vec t=[t_1,\dots,t_m]$，$h$为$\mathbb G_2$的生成元，$\chi_i$为第$i$个拉氏基多项式
$$ \chi_i(X_1,\dots,X_m)=\prod_{j:i_j=1}X_j\cdot \prod_{j:i_j=0}(1-X_j) $$
意思是将元素$h_i$表示为$h$的某个秘密次幂
本文的广义化MIPP协议允许Prover证明：对于一个域元素公共向量$\vec b=[b_1,\dots,b_m]$，记$U$如下
$$ U=\lang \vec A,\vec y\rang=\vec A^{\vec y}=\prod _iA_i^{y_i} $$
其中$\vec y=[y_1,\dots,y_m],y_i=\chi_i(\vec b),i\in\{0,1\}^m$
这样一来的Prover Time和Verifier Time都是$O(m)$，Verifier也只需要读取$\vec b$即可完成验证，无需完全读取$\vec y$，因为$\vec y',\vec h'$都是结构化的，递归结束时的最终的这两个向量可以通过如下方式计算
$$ \vec y'=[(1-b_1+x_1^{-1}b_1),\dots,(1-b_m+x_m^{-1}b_m)]\\ \vec h'=h^{\prod_i(1-t_i+x_i^{-1}t_i} $$
这样一来，Verfifier只需要利用$\vec b$就可以完成这两个向量的计算，复杂度为$O(m)$
具体协议如下图所示
这里可以看到，协议和Bulletproof有些类似，会递归执行$m$层，不过递归过程中涉及到的中间向量$\vec A',\vec y',\vec h'$都由Prover计算，因为太大了，Verifier无法肚子计算，Prover会在协议结束时向Verifier提供这些值
协议中的$T',U'$由Verifier计算
$$ T'=CM(\vec A',\vec h')\\U'=\lang \vec A',\vec y' \rang $$
4 Testudo-Comm: Our PCS with Square Root Trusted Setup
接下来看一下如何用广义化饿MIPP，将PST可信设置的大小减小到平方根阶
Testudo承诺方案如下图所示
5 Testudo: Our Construction
基于上述方案，构建本文的Testudo，记$A,B,C$为大小为$N$的R1CS实例矩阵
首先是可信设置，本文假设可信方为Testudo-Comm生成了初始可信设置，同时为R1CS生成了Groth16的可信设置（这里是通用可信设置，与R1CS实例大小无关）
然后是计算承诺，Spartan中需要将$A,B,C$转换为三个稀疏多项式$\tilde A,\tilde B,\tilde C$，然后计算这三个多项式的承诺，本文注意到，在均匀电路中（数据并行电路等包含重复子电路的电路），这个转换过程不是必要的，因为Verifier可以自己计算这三个稀疏多项式（或者只需要计算子电路的承诺即可），这样就可以降低方案的复杂性
第三步是计算witness的承诺，将$w$进行多线性扩展，得到$\tilde w$并用Testudo-Comm进行承诺
最后是证明和验证，Prover和Verifier的工作如下
Prover首先执行Spartan协议，证明$A,B,C$的可满足性，不过区别于Spartan协议，Testudo用Testudo-Comm来做承诺
然后Prover构造承诺的揭示，构造并生成上述Spartan协议的Groth16证明
Verifier的工作为验证这个最终的Groth16证明就可以了
6 Practical considerations
最后看一下一些实现时的问题
Spartan的原始版本采用的时curve25519-dalek这个曲线，提供了素数阶Ristretto群的有效实现，但是问题在于这个曲线不支持配对，因此不能结合Groth16来使用
本文的做法是用BLS12-377和BW6-761这两条曲线相结合，因为这两条曲线可以构造非常高效的配对，具体的细节可以看原文的附录D
对于数据并行计算而言，如果电路形如下列形式，Testudo就可以很好的均摊计算开销
$$ R(\vec x^{(1)},\vec w^{(1)})\wedge \dots\wedge R(\vec x^{(K)},\vec w^{(K)}) $$
Parallelization and aggregation of Testudo proofs
经过本文的研究，Testudo可以聚合不同级别的证明，每个级别都有各自的优缺点，但是都是可以相互兼容的，因此可以在实践中扩展到大规模的实例，从而实现并行生成证明
对于Spartan而言，假设Prover在不同的机器上，使用不同的witness并行运行多个和校验协议与揭示多项式承诺，此时聚合的和校验协议的验证可以通过下列两种方式进行
- 使用类似Snarkpack的构造，将不同的Groth16-和校验Verifier聚合在一起
- 通过单个Groth16来证明多个和校验协议的实例
References
$[1]$ Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, Justin Thaler:
Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup. IACR Cryptol. ePrint Arch. 2023: 961 (2023)
$[2]$ C. Papamanthou, E. Shi, and R. Tamassia. Signatures of correct computation. In TCC 2013, LNCS. Springer,Heidelberg, Mar. 2013
$[3]$ B. Bunz, M. Maller, P. Mishra, N. Tyagi, and P. Vesely. Proofs for inner pairing products and applications. InASIACRYPT 2021, Part III, LNCS. Springer, Heidelberg, Dec. 2021.
$[4]$ Spartan：满足透明性的通用高效zkSNARK方案 - 三两老友杂的小岛 (snowolf0620.xyz)
$[5]$ 多项式扩展与和校验协议 - 三两老友杂的小岛 (snowolf0620.xyz)