零知识证明技术应用越来越广，隐私证明，计算证明，共识证明等等。在寻找更多更好的应用场景的同时，很多人逐步发现零知识证明证明性能是个瓶颈。Trapdoor Tech 团队从 2019 年开始深入研究零知识证明技术，并一直探索高效的零知识证明加速方案。GPU 或者 FPGA 是目前市面上比较常见的加速平台。本文从 MSM 的计算入手，分析 FPGA 和  GPU加速零知识证明计算的优缺点。

TL;DR

ZKP是拥有未来广泛前景的技术。越来越多的应用开始采用零知识证明技术。但ZKP算法比较多，各种项目使用不同的ZKP算法。同时，ZKP证明的计算性能比较差。本文详细分析了MSM算法，椭圆曲线点加算法，蒙哥马利乘法算法等等，并对比了GPU和FPGA在BLS12_381曲线点加的性能差别。总的来说，在ZKP证明计算方面，短期GPU优势比较明显，Throughput高，性价比高，具有可编程性等等。FPGA相对来说，功耗有一定的优势。长期看，有可能出现适合ZKP计算的FPGA芯片，也可能为ZKP定制的ASIC芯片。

ZKP 算法复杂

ZKP是个零知识证明技术的统称（Zero Knowledge Proof）。主要由两种分类：zk-SNARK以及zk-STARK。zk-SNARK目前常见的算法是Groth16，PLONK，PLOOKUP，Marlin和Halo/Halo2。zk-SNARK算法的迭代主要是沿着两条方向：1/是否需要trusted setup 2/电路结构的性能。zk-STARK算法的优势是毋需trusted setup，但是验证计算量是对数线性的。

就zk-SNARK/zk-STARK算法的应用来看，不同项目使用的零知识证明算法相对分散。zk-SNARK算法应用中，因为PLONK/Halo2算法是universal（无需trusted setup），应用可能越来越多。

PLONK 证明计算量

以PLONK算法为例，剖析一下PLONK证明的计算量。

PLONK证明部分的计算量由四部分组成：

1/ MSM - Multiple Scalar Multiplication。MSM经常用来计算多项式承诺。

2/ NTT计算 - 多项式在点值和系数表示之间变换。

3/ Polynomial计算 - 多项式加减乘除。多项式求值（Evaluation）等等。

4/ Circuit Synthesize - 电路综合。这部分的计算和电路的规模/复杂度有关。

Circuit Synthesize部分的计算量一般来说判断和循环逻辑比较多，并行度比较低，更适合CPU计算。通常来讲，零知识证明加速一般指的是前三部分的计算加速。其中，MSM的计算量相对来说最大，NTT次之。

What's MSM

MSM（Multiple Scalar Multiplication）指的是给定一系列的椭圆曲线上的点和标量，计算出这些点加的结果对应的点。