Hardware Acceleration of ZKP

请注意，本文编写于 540 天前，最后修改于 505 天前，其中某些信息可能已经过时。

‍硬件加速顾名思义，是在硬件层面对协议进行优化并提高协议效率的方式，比如针对FPU的加速以处理各类高精度的科学运算，针对数字信号的加速以处理流媒体，针对机器学习的算法进行优化，针对图形的（GPU），以及针对密码学协议的优化等等

本文主要讨论针对密码学的硬件加速，包括公钥密码、全同态加密、VDF、Hashing和ZKP协议

Why HW Acceleration for ZKP

总所周知，ZKP的大部分计算开销都来自于本地计算，而且现代SNARK的简洁性通常要求验证时间是亚线性阶（甚至对数阶），这意味着Prover在生成证明过程中的时间开销非常的大，所以现代zkSNARK协议中经常会出现这样一种情况：Verifier只需要一秒就可以验证证明，但是证明生成时间可能需要花费Prover半天甚至一天的时间

比如说zkEVM，Gas开销为1M的交易可能需要40分钟来生成对应的证明，而EVM每秒可以处理10M Gas的的交易，这可比zkEVM快太多了

或者看看zkVM，他的频率只有大约50kHz，而现代CPU主频一般在2-3GHz之间，还可以睿频到5G，这都差了四五个数量级了

所以硬件加速主要有下列几个目标

提高吞吐量：最直接的办法，就是提高每秒执行的操作数
降低开销：降低计算开销，比如比特币挖矿，降低每次计算Hash所需要的成本（硬件成本，电力成本）
降低延迟：降低独立运算之间的延迟

结合上述几个目标，再结合现代zkSNARK的构建方式，主要需要针对下列几个算法进行优化：MSM、NTT和算术Hash（比如Poseidon Hash）

MSM算法概述可以看$[2]$，优化的方式也有很多，对于大规模的MSM而言，可以采用Pippenger之类的算法来降低计算复杂度（原来是线性阶，可以降低至$O(n/\log n)$），或者采用特殊的点或曲线来减少每次域运算的计算开销

而对于NTT而言，现在比较好的算法时Cooley-Tukey，复杂度为$O(n\log n)$，但是由于NTT这个算法存在一些特点，导致其无法很好的进行并行计算（NTT在计算过程中具有一定的依赖性，难以分割为多个子问题再合并），此外NTT在计算时必须确保需要操作的元素都保存在内存中，这也意味着越大规模的NTT计算需要越大的内存开销

算术Hash在ZKP中也是一个应用广泛的密码学原语，主要用在基于Merkle Tree的构造中，或者用于证明对某个Hash的原像的知识，由于Hash一般都非常短，因此很适用于表达大规模的数据

ZKP中常用的算术Hash为Poseidon Hash，当然也有用SHA系列的，但是这些Hash在本地计算时开销也不小（参见$[3]$的效率评估），而且Hash的计算效率还会与域的大小、使用的素数、协议的轮数、MDS矩阵结构等参数相关

讨论完了需要优化的算法，再看看需要优化的协议，这里分为SNARK和STARK来看，给一张Amber做的表

表中越靠上意味着需要越多的FFT运算，越靠下则需要越多的MSM运算，从之前的博客中也可以看出，Plonkish结构都是基于各种各样的循环咨询构建的，在这些群上面进行MSM算法的开销都不小（大约占全部计算开销的六至七成），而STARK的开销主要在NTT和Hash的计算上（也至少占了六成以上的开销）

Optimize Problems

经过上面的分析，可以看到ZKP协议的效率问题主要是各种算术运算，为了解决这些效率问题，需要从ZKP协议的框架触发

这里回顾一下ZKP的框架，首先是通过ZKP的前端，将一个计算问题转化为有限域上的约束计算，然后再到椭圆曲线群，最后再附加上零知识性

这样看来，ZKP的效率优化也是如此，需要从前端开始，自底向上的解决每一层中的效率问题，从而加速ZKP的证明生成

上述是从分层的角度来看ZKP的效率优化，不过其实归纳一下可以发现，需要考虑的问题无非都是下面这些：计算的数量、域的大小、曲线点的大小（256/384）、点的表示方式（Affine/Jacobian）、模数的大小（素数的大小）、计算复杂度、计算位宽等等

还有就是这些计算（尤其是乘法）不仅仅需要大量的内存（内存频率也要，越高越好），还需要高效的数据总线（比如PCIe v4或以上），否则也会限制硬件的计算速率，其他还有一些算术计算单元的高效实现与效率优化

这里高效的数据总线其实很重要，经过这么多年发展，大数据计算其实已经非常成熟了，针对算法的各种并行优化和专用优化的方案有很多，在计算的效率上非常高，而限制系统效率的往往是数据的传输部分，可能数据要传很久，但是一下子就算完了，导致系统效率上不去
这里还有一个对应的定律，称为阿姆达尔定律（Amdahl's Law），该定律表明提升系统中某个部分的性能时，对系统整体性能的影响主要取决于两点：（1）这个部分在系统中有多重要（可以简单理解为在系统中占的比重）；（2）这部分的性能提升了多少
前面提到了无论是SNARK还是STARK，算术计算的开销都至少占了整个协议的六成，如果把算术计算的效率提高为原来的三倍，此时根据Amadhl's Law公式$[4]$计算，可以知道方案整体的效率提升只有1.67倍左右
这里再极端化一点，如果不是提高三倍，而是提高无穷倍，计算出来的整体效率提升其实也只有2.5倍，而不是直观感受的无穷倍的效率提升
个人感觉这个有点类似于木桶效应，虽然增加木桶的长板可以增加木桶的装水量，但是这个提升仍然是有限的，提高木桶装水量的短板才有可能显著提高木桶的装水量

分析了问题，接下来是硬件，这里给出几个例子（这里只是通用硬件，没有针对上述任何算法进行特定优化）

回到ZKP的优化，上述分析了ZKP优化的需求，这里有两个提高效率的关键点

算法：对硬件友好的算法（HW Friendly）确实不错，比如COTS硬件（GPU之类的）包含成千上万的计算核心，可以很好的进行并行计算，此外此类算法的主要优化目标可以集中在降低运算数量上，因为算法本身是对硬件友好的，通常不需要考虑太多算法层面的事情
高效实现：如果真的有一个对硬件非常友好的算法，那么就需要重构这个算法来适配硬件，简单来说就是需要协调硬件上的所有资源来尽可能地提高算法的效率（比如说用汇编或者更低层的方式来实现算法）

所以找到适合的算法和高效实现都很重要