区块链上的零知识证明技术及其典型算法、工具

• 多标量乘法（MSM）优化。MSM是一种在椭圆曲线密码学中常见的操作，它涉及对多个标量和椭圆曲线点的乘法与求和运算。虽然MSM 可以通过并行处理来加速，但即使在多核心的系统上，对于复杂的应用MSM 的运算仍然需要消耗大量的资源与时间。MSM 算法需要处理大量的元素与重复执行相同的操作。
• 快速傅里叶变换（FFT）优化。以STARK为代表的零知识证明系统大量用到了快速傅里叶变换（FFT）。这个算法用于高效计算序列的离散傅里叶变换（DFT）及其逆变换。FFT 的运行过程严重依赖于数据的频繁交换，数据交换过程中需要从大数据集中“随机”地传输元素，这在硬件内存有限的情况下尤为困难。尽管硬件操作本身非常快，但传输数据的时间却显著降低了整体操作速度。除此之外，FFT 算法通常需要将输入数据重新排列成特定顺序以执行变换，这可能需要大量的数据移动，对于大型FFT算法规模来说，这可能成为性能瓶颈。FFT 虽然是一种强大且广泛应用的算法，但在大型数据处理和分布式计算环境中，其性能和效率受到数据交换、带宽限制的显著影响。

[2] Ben-Sasson E, Bentov I, Horesh Y, et al. Scalable zero knowledge with no trusted setup[C]//Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 39. Springer International Publishing, 2019: 701-732

[3] Schwartz J T. Fast probabilistic algorithms for verification of polynomial identities[J]. Journal of the ACM (JACM), 1980, 27(4): 701-717.

[4] Bootle J, Cerulli A, Chaidos P, et al. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting[C]//Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer Berlin Heidelberg, 2016: 327-357.

[5] https://github.com/scroll-tech

[6] https://github.com/starknet-io

[7] https://github.com/taikoxyz

[8] https://github.com/succinctlabs

[9] https://github.com/Electron-Labs

[10] https://www.zkibc.com/

[11] https://github.com/topics/polyhedra

[12] https://zkbridge.com/

[13] Setty S. Spartan: Efficient and general-purpose zkSNARKs without trusted setup[C]//Annual International Cryptology Conference. Cham: Springer International Publishing, 2020: 704-737.

[14] [63]Lu T, Wei C, Yu R, et al. Cuzk: Accelerating zero-knowledge proof with a faster parallel multi-scalar multiplication algorithm on gpus[J]. Cryptology ePrint Archive, 2022.