对于一个合格的生产算法，我们需要关注两个点：1. 算法解决了什么问题，算法逻辑的正确性。2. 算法性能临界点是否符合预期。目前，在 zkp 领域，虽然统一公认的 protocol 还没有出现，但是在隐私计算、Rollup等诸多方面已经产生的实际应用；于此同时，zkp 算法的性能问题也暴漏出来，本文就 zkp 算法的主要逻辑、性能瓶颈从protocol与计算两个方面介绍可能的发展方向。

主要算法元素

通常一个零知识证明算法包含3个关键元素：

1. 同态函数，可以椭圆曲线（计算安全）、随机函数（理论安全）等
2. 将任意计算转化为门电路继而转化证明有某个多项式约束的解，这个多项式约束对应了任意计算的条件约束。多项式转化方法有比较常见的 Groth16、PlonK 等
3. 根据不同的多项式承诺方案，证明多项式的解确实是由该多项式生成的。常见的多项式承诺有 Kate、Bulletproofs、FRI

比如 zk-SNARKs 广泛流传的 Groth16 算法使用了 KCA 来验证多项式，如果把多项式验证部分改为 Kate，则它演化成了 PlonK 算法，Marlin（ALEO使用），同属 zk-SNARKs，但是将 CMS 生成转化为了 SMS，不必每次改动算法就重新做 trusted setup。如果使用 FRI 做多项式验证，那么这个证明转化为了一个 zk-STARKs 算法，STARKs 场景下不需要做 trusted setup。他们所对应的安全性等级与 proof 大小如下图所示：

算法加速

目前时间点上，zkp 领域算法繁多、且复杂，仍然有很多算法虽然有应用在测试，但依然还处于理论验证阶段。具体性能优化更多的可以针对不同项目从工程性上下手。

而到 zkp 算法本身，大多需要 zk 友好的描述方式，比如上面的 Groth16、PlonK、STARKs算法都是 zk 友好的。不同的证明系统，具体的证明生成逻辑可能不一样，但是他们都会强依赖下面两个运算：

1. Trapdoor函数的大数乘法 MSM，https://www.youtube.com/watch?v=Bl5mQA7UL2I。对于一个zkEVM 应用来说， $2^{25}$ （3300w）个元素的向量属于是保守估计。由于数据集非常大，所以即使并行后耗费的计算与内存资源依然非常大
2. 快速傅立叶变换和反傅立叶变换 FFT。FFT 的问题在于算法中会不停的 shuffling，计算设备的IO会变成性能瓶颈，大概问题的规则在比如 16G RAM的设备上不停的随机读写 100G 数据。

在一个同时存在着两种运算的系统中，MSM 大概占了 70% 的时间，剩下的大部分时间在做 FFT。这两种运算都很慢，但是有可能的办法做性能优化：

幸运的是 PipeZK 在解决 MSM、FFT 这两个算法性能问题上是很有希望的，作者使用 Pippenger算法 缓存与跳过重复计算，从而加快运算速度。同时，在PipeZK论文中，描述了一种“unroll” FFT的算法，使得可大幅减少shuffling的数量，由于采用了now-predictable内存访问模式，大幅改进了硬件上的运行速度。

硬件选择

现在 zkp 算法的发展仍属于非常早期的阶段，没有系统的标准化参数，比如 FFT 的width定多少，大数向量元素的位宽等。而且甚至对 zk 系统本身的选型也没有明确的方案，在这种情况下 ASIC 方案周期长，自定义参数少，显然是不划算的。

至于 FPGA 对比 GPU，FPGA 在获取成本和能耗方面有一定优势，但是在开发上 GPU有着比较明显的优势。这两种硬件预计将会在比较长的时间内主导 zkp 领域的计算，当然如果将来 zkp 领域在 L1、L2 只有一个或少量几个方案实现，那么 ASIC 可能会显示出更多优势从而超过 FPGA。