最近整理了一下之前研究零知识证明搜集的一些资料，主要是自己感兴趣的一些领域，哪怕不做底层的理论研究，我们还是应该了解一下为什么要做这样的研究，它是为了解决什么问题，以及现有工具各自的优缺点是什么。
这篇文章的内容结合了我自己之前整理的部分材料，以及Mary Maller的一个speaking，总的来说适合对于零知识证明已经有一定了解的同学阅读。（如有纰漏，欢迎指正）
不同类型的零知识证明协议
几种不同类型的setup
- Trusted setup：生成的参数仅对当前的应用有效，若要证明的程序出现了修改需要重新进行setup（参与方之一必须是诚实的，对toxic进行销毁操作）
- Universal setup：整个证明系统仅需进行一次setup，生成的参数可以进行转化，被所有证明程序使用（参与方之一必须是诚实的，对toxic进行销毁操作）
- Transparent setup：setup无需可信第三方，只需确保系统参数是随机生成的，如使用指定数据的hash值
from Wiki
使用MPC进行可信设置
from Vitalik's Blog
💡 目前业内通常使用Powers of Tau协议进行可信设置，可支持数百人同时生成数据，该协议运行的结果作为CRS生成的第一阶段数据，在第二阶段再将这些数据转换到要证明的应用上，因此在信任已有的Powers of Tau协议运行结果的基础上，新的应用可以直接使用这些数据。
深入了解：
- https://vitalik.ca/general/2022/03/14/trustedsetup.html
- https://zkproof.org/2021/06/30/setup-ceremonies/
已完成的Powers of Tau协议的运行结果：
- https://github.com/weijiekoh/perpetualpowersoftau
- https://ceremony.tornado.cash/ （Tornado cash的可信设置，达到了1114名参与者）
使用可信硬件运行Powers of Tau协议：
完成setup后各power下CRS数据的大小：
抗量子的协议
基于Lattice
SNARGs
- Lattice-based SNARGs and their application to more efficient obfuscation
- Quasi-optimal SNARGs via linear multi-prover interactive proofs
SNARKs
基于collision resistant hash functions (CRHFs)
性能比较
💡 使用universal setup的协议有很多是基于KZG Polynomial Commitments来做的，打开承诺的开销很小，协议的证明生成时间和验证开销主要取决于要发送和打开的承诺数量。
from Vitalik's Blog，PLONK协议使用universal setup， DARK和STARKs使用Transparent setup
一般来说使用universal setup的协议proof size和验证时间等相对于使用trusted setup的协议开销会大一点，但比transparent setup要小。
💡 满足transparent setup的协议一般具有较大的开销，同时不同的协议具有不同的权衡，部分协议具有log级别的计算开销，但proof size较大，如STARKs，而其他协议如Bulletproofs则具有较小的proof size以及较大的计算开销。
from Sonic paper
from the slide of “An Evolution of Models for Zero-Knowledge Proofs” in eurocrypt 2021
💡在经过了多番努力后，目前对于使用几种不同setup的协议的性能优化上，基本上达成了几项共识
- 对于trusted setup，proof size和verifier time可能已经达到了最优，基本上达到了常数级别，verify部分仅包含几个固定的pairing运算以及public input添加的运算
- 对于prover time而言可能还有一定的优化空间，一方面很多协议大量使用FFT，复杂度为O(NlogN)，可以考虑FFT相关的加速及优化，另一方面可以想办法使用其他方法构建，避免使用FFT
- 对于universal setup和transparent setup而言，proof size和verifier time仍有优化空间，目前很多新协议也主要集中在这一方面
新的安全模型
The Algebraic Group Model(AGM)
AGM是一个理想化的模型，可用于很多零知识证明协议的安全证明，详情可参考原始论文
The Algebraic Group Model and its Applications（CRYPTO 2018)
💡 在该论文中提供了AGM下Groth16协议的安全证明，同时AGM对于基于KZG的协议的安全证明格外有效，很多universal setup的协议在AGM下证明了安全性
AGM也可以在标准模型下实现（On Instantiating the Algebraic Group Model fromFalsifiable Assumptions），目前还没有发现针对该模型的攻击
复杂应用的证明
对于一些复杂的应用，其证明电路的constraints数量可能高达数百万甚至上千万，对于一般的协议而言其prover开销是难以接受的，一方面证明时间很长，另一方面所需内存非常大（实际内存使用量因协议和相关实现而异，未优化前，一个参考数据是每百万constraints约5Gb内存）
关于这一问题，其实有很多不同方向的解决方案，目前对于它们的研究都在同步推进
相关学术研究
替换底层密码原语
考虑基于对称密码原语而非公钥密码原语来构建零知识证明协议，毕竟对称密码相比公钥密码的开销要小得多
- Mac’n’Cheese: Zero-Knowledge Proofs for Boolean and ArithmeticCircuits with Nested Disjunctions (基于MAC构建）
使用Garbled Circuits
可以使用乱码电路，这对于使用布尔电路构建的证明系统格外有效（虽然使用算术电路的协议更为常见）
递归证明
如果我们要证明的应用中包含很多重复的模块，某个问题被反复证明，那么可以使用递归的方式来构建证明
- Scalable Zero Knowledge via Cycles of Elliptic Curves
- Recursive Proof Composition without a TrustedSetup
- FRACTAL:Post-Quantum and Transparent Recursive Proofs from Holography
这种技术目前对于区块链的扩容而言很有用，对于以太坊这样的状态区块链来说，每次执行交易都是一次对状态的变更，基于零知识证明的扩容会证明每个区块中状态的变更都是有效的，每次要证明的都是同一个问题，因此可以使用递归证明来优化，很多基于Validity Rollup(zk-Rollups)的layer2项目都在研究添加递归证明的支持，此外还有像Mina这样的公链项目，应用递归证明构建了简洁区块链，将区块链状态缩小到22kb的大小
批量验证
对于要证明的应用的多个证明，可以对它们进行批量验证以进行加速，对于区块链应用而言比较有用，可以批量验证同一区块中的相关证明，缩短验证时间的同时在很大程度上减少gas的消耗
from Protocol Labs
聚合证明
对于SNARKs协议，我们也可以通过聚合证明来来达到批量验证的效果，同时缩小证明的大小，对于Groth16协议的证明聚合非常有效
from Protocol Labs
寻找SNARKs友好的密码原语
我们要证明的应用之所以有如此庞大的constraints数量，很大程度上是因为其中使用的算法在SNARKs中实现的成本过高，尤其是散列函数，目前用的比较多的sha256，sha3等算法需要数十万constraints才能构建，因此现在还有一个优化方向便是使用SNARKs友好的密码原语来构建应用
目前对于SNARKs友好的密码原语的研究基本上包含了各个方面：
- Hash functions
- Commitment schemes
- Pseudo-Random Functions (PRF)
- Message Authentication Codes (MAC)
- Signature schemes – both discrete-log-based (e.g. RedDSA) and bilinear pairing-based (e.g. BLS)
- Key Derivation Functions (KDF)
- Symmetric Encryption schemes (AEADs)
- Asymmetric Encryption schemes
- Key agreement protocols
其中对于hash函数的研究是最多的，因为其在目前常用的零知识应用中使用的非常广泛，很多应用都使用了merkle tree来构建累加器，导致hash函数使用的constraints数量几乎可以占到整体的90%
目前实际应用中用的较多的有MiMC系列hash函数以及poseidon hash和pedersen hash，它们的结构很多也都比较简单，比如MIMC的结构如下
在这一基础上这两年也有一些其他的hash函数被提出
对于这些hash函数的性能比较如下
可以看到下面以MIMC为首的这些SNARKs友好的hash函数都具有较小的电路，即使用较少的constraints，因此只需很短的prover time， 不过它们大部分都存在一个问题就是实际运算速度较慢，这导致在构建merkle tree的时候如果树的深度较大，则需要很长的时间，因此目前业内希望可以找到一些同时满足SNARKs友好以及运算速度较快这两个特性的hash函数
此外，对于区块链应用而言，实际上我们还需要关注另一个指标，即该算法在链上的gas消耗，因为以太坊的EVM目前仅提供对sha256，sha3以及RIPMD160函数的直接支持，因此这些新的hash算法的链上开销往往会比较大
当然，对于一些新算法，除了性能以外，我们还需要关心的是它们的安全性，毕竟这些算法并不在标准列表中，目前对于这些算法安全性的研究也正在进行之中
- https://starkware.co/hash-challenge/ starkware组织的对于STARK友好hash的相关研究，里面出具了一些对于部分hash算法安全性的报告
补充材料：
- https://ethresear.ch/t/cheap-hash-functions-for-zksnark-merkle-tree-proofs-which-can-be-calculated-on-chain/3176/6
- https://ethresear.ch/t/prover-time-comparison-of-gkr-groth16-vs-groth16-for-proving-mimc-hashes/8373
- https://medium.com/aztec-protocol/plonk-benchmarks-2-5x-faster-than-groth16-on-mimc-9e1009f96dfe
- https://medium.com/aztec-protocol/plonk-benchmarks-ii-5x-faster-than-groth16-on-pedersen-hashes-ea5285353db0
- SNARK友好签名协议 https://ethresear.ch/t/question-for-cryptographers-snark-friendly-signature-protocol/4645
工程加速
除开算法上的优化，使用硬件加速运算也是一种很有效的方法
GPU
from Protocol Labs
FPGA
使用分布式计算
补充阅读：
本文到此便告一段落了，不过零知识证明的研究脉络并没有在这里停下，精力所限就不再继续总结下去了，有兴趣的同学可以自己去各顶会上搜集整理下零知识证明相关的文章。而且文中目前也缺少对于很多新兴的零知识证明协议各自特点的分析与比较，像是PLONK和Halo等协议，随着生态的完善相信使用它们的项目也将越来越多，Zcash也计划在Orchard更新中切换到Halo2协议，后面有空了再深入一下。
其实还有一部分关于现有的zk工具包的介绍本来也想囊括进来，不过想了想准备再沉淀一下，作为上一篇关于零知识应用安全性文章的补充内容，可以一起聊聊在使用这些工具包构建应用时编写的密码算法的安全性，本身很多密码算法在实现时就存在不少陷阱的，在证明电路中实现同样可能受到威胁。