Abstract
本文旨在对基于circom实现的一些签名方案和Hash函数进行一系列的性能测试，包括Prover Time、Verifier Time和证明大小，测试的算法包括Poseidon、Pedersen、MiMC、SHA-256、ECDSA、EdDSA、Sparse Merkle Tree、Keccak-256和Schnorr
此外，本文还为Schnorr签名方案引入了一个新的circom电路和对应的JS测试套件
本文的研究结果可为不同方案和框架提供效率参考
1 Introduction
本文的工作是ZK-Harness项目的一部分，该项目基于Python编写，允许任何人参与
本文通过对circom电路的一些常用算法进行定量测试，并将结果贡献至ZK-Harness项目中
Related Works
- Benchmark results - HackMD：基于circom、Halo2、Plonky2实现的Poseidon Hash的Benchmark
- Sladuca/sha256-prover-comparison: Some very rough benchmarks between sha256 circuits in different proving systems (github.com)：基于circom、Halo2、Plonky2实现的SHA256，重点比较了Prover Time，结果在该项目仓库的README文件里面
- Benchmarking ZKP Development Frameworks: the Pantheon of ZKP - Ethereum Research (ethresear.ch)：基于circom、Halo2、Plonky2、Gnark、Arkworks、Starky实现的SHA256，重点比较了Prover Time，约束数量和证明大小
不过这些都只比较了个别算法的实现，不够全面
本文重点关注circom实现的电路（因为circom用的比较多），然后关注circom开源实现的大部分算法，个别算法采用其他开源实现（具体在下面的表里面，没有备注的表示采用circom lib的实现）
| 算法 | 类型 | 备注 |
|---|---|---|
| Poseidon | Hash | |
| Pedersen | Commitment | |
| MiMC | Hash | |
| SHA256 | Hash | |
| ECDSA | Signature | 0xPARC |
| EdDSA | Signature | |
| Sparse Merkle Tree | Commitment | |
| Keccak256 | Hash | Vocdoni |
| Schnorr | Signature | 本文没找着开源实现 所以本文自己写了一个 |
2 Approach
本文实现了ZK-Harness中的9个算法，Blake2 Hash和BLS签名没有实现
由于circom没有实现Schnorr签名，所以本文自己设计并实现了Schnorr签名的验证电路实现，本文采用的是Baby-Jub曲线，签名过程中的Hash函数采用Poseidon Hash
对于Hash算法而言，本文测试结果表明，SHA256的验证最快，Poseidon Hash的内存开销最少，尽管所有Hash算法的证明大小大致相同，但是zk-friendly的电路包含的约束数量要更少
对于签名方案而言，与EdDSA相比，本文实现的Schnorr在证明生成和验证时间上都比EdDSA快两倍，其他维度（内存开销，证明大小，约束数量）基本一致
具体的比较结果如下，数据来自于原文的附录，测试采用AMD Ryzen 7 4700U，曲线如若未声明则采用bn128，ZKP算法采用Groth16
首先是Hash算法系列，可以看到SHA256的证明生成和验证效率都是最高的，但是论内存开销来说，Poseidon Hash的内存开销最小
笔者前段时间也自己写过一些相关的circom电路，效率和内存开销方面与本文的结果基本一致
尤其是需要进行迭代计算的时候，由于SHA系列包含大量的约束条件，因此构造证明时需要大量的内存来构造约束，迭代次数稍微大一些就会导致内存爆炸
而Poseidon Hash对ZKP和曲线做出了针对性的优化，因此约束条件比SHA系列要少得多，适用于迭代计算
下图是笔者之前写circom电路时的一点测试结果
此外，图3也可以看出来Hash函数的证明大小与约束数量的关系，尽管五个Hash函数的证明大小都在0.8KB左右（因为用的Groth16，只有三个群元素，不会很大），但是SHA256和Keccak256的约束数量远超前三个算法，这还是因为SHA系列和Keccak系列中包含大量的位运算，每一步的位运算都需要构造一个约束条件，所以最终的约束数量超过了其他三个算法至少两个数量级（这也是为什么学界需要研究Lookup Argument的原因）
签名方面，无论是证明时间还是验证时间，本文自己实现的Schnorr验证电路都是EdDSA三倍左右，而且内存开销只比EdDSA多一点点，约束数量也多一点点
Others
$[1]$是原文，eprint收录
$[2]$中可以找到大部分的测试数据，包括电路的，算术的，以及曲线的Benchmark
$[3]$是ZK-Harness的项目地址，里面有相关的测试数据，如果需要本地跑的话需要circom和snarkjs环境，具体安装可以参考之前的博客$[4]$
References
$[1]$ Benchmarking ZK-Circuits in Circom (iacr.org)
$[2]$ zk-Harness Benchmark (zk-bench.org)
$[4]$ snarkjs初探 - 三两老友杂的小岛 (snowolf0620.xyz)