1. 引言

本文重点关注：

1）何为硬件加速？为何需要硬件加速？
2）ZKP的关键计算原语：
- Multiscalar Multiplication
- Number Theoretic Transformation
- Arithmetic Hashes
3）所需的硬件资源
4）加速的限制
5）硬件加速的当前现状
6）硬件加速的未来方向

2. 何为硬件加速？为何需要硬件加速？

2.1 何为硬件加速？

所谓硬件加速，是指使用专用硬件来加速某运算，使得该运算运行更快和（和）更高效。

硬件加速可包含：

使用现有硬件（COTS）来优化函数和代码
开发针对特定任务的新硬件

现有硬件包括CPU、GPU以及FPGA，而定制硬件通常是指ASIC。
使用定制硬件来加速具有昂贵计算任务的历史由来已久，如：

Floating Point（FPU）：科学计算
Digital Signals（DSP）：音频和视频
Graphic（GPU）：游戏、视频等
AI（TPU）：机器学习训练和推理
Networking（NPU/NIC）：网络处理
密码学

2.2 密码学的硬件加速

当前密码学的硬件加速有：

1）哈希运算：
- SHA-NI
- Bitcoin Miners
- Altcoin Miners
2）公钥密码学：
- 加密（如 AES-NI）
- 密钥交换（TLS Offload）
- 数字签名（Intel Quick-Assist）
3）全同态加密：
- GPU
- FPGA
4）VDF（Verifiable Delay Functions）
5）Zero Knowledge Proofs

2.3 为何需要硬件加速？

相比于直接计算，ZK（和non-ZK）proof生成具有很高的开销，这意味着：

相比于直接做witness checking，总的Prover开销要高100万倍到1000万倍。在笔记本电脑上只需一秒运行的程序，对SNARK Prover来说，若以单线程运行，可能需要数十数百天。
zkEVM：
- Scroll zkEVM：100万gas的链上Verifier，对应Prover在CPU上需要约40分钟来生成ZKP proof。比Polygon EVM的1000万+gas/second限制，开销要贵2.5万倍+。
zkVM：
- Risc0 zkVM评估为约50kHz，而现代CPU为5GHz，开销要大10万倍+。

目的不同，硬件加速的设计也不同：

1）吞吐量：增加单个系统处理的操作数。
2）开销：降低操作开销。如Bitcoin mining rig设计为减少资金成本（$/hash）和操作成本（watts/hash）。
3）延迟：降低某个操作的延迟。如zkBridge通过降低proof生成时长来实现更快的finality。

2.4 ZKP中需加速的内容

每种证明系统及其关联实现，可能具有不同的计算需求。
尽管如此，最贵的3大计算操作主要为：

Multiscalar Multiplication（MSM）
Number Theoretic Transformation（NTT）
Arithmetic Hashes（如Poseidon）

在这里插入图片描述
不同证明系统生成proof所需的运算类型主要由所采用的承诺方案决定：

SNARKs：通常约65%的事件用于MSM和NTT运算。
STARKs：约65%的时间用于NTT和哈希运算。

3. ZKP的关键计算原语

3.1 MSM及其加速

Multiscalar Multiplication（MSM）为：

对多个scalar multiplications求和的算法。
可将其看成是elliptic curve points与scalars做‘dot product’的运算。
基于该算法特性，很容易对每个或每组scalar multiplication进行并行化，可将其切分并在不同的硬件引擎上计算，最后再累加在一起。

可有多种优化方式来降低计算MSM所需的计算量，如：

对于larger sized MSM，Pippenger算法可将计算开销由linear降低为约 $O(n/\log(n))$ 。
更换point坐标表示（如Affine、Jacobian）以及更换曲线表示（如Edwards），也可降低单个曲线运算所需的field运算数。

MSM加速存在的问题为：

当将MSM计算转移出host device时，scalars和points必须已送给加速器。可用的通讯带宽会限制加速器的最大可能性能。

3.2 NTT及其加速

Number Theoretic Transformation（NTT）用于对两个多项式做乘法运算的算法：

可将其看成是对有限域元素的FFT/DFT
常用算法如Cooley-Tukey可将复杂度由 $O(N^2)$ 降低为 $O(N\log N)$

在这里插入图片描述
NTT加速存在的问题为：

当将NTT运算自host device转移时，scalars也必须移送到加速器。可用的通讯带宽会限制加速器的最大可能性能。
基于NTT的算法属性，NTT并不容易并行化，每个元素必须与多个其它元素交互，意味着不容易切分。
此外，这些元素必须保存在内存中供操作，从而要求高内存。

3.3 Arithmetic hash及其加速

需要Arithmetic hash的原因在于：

许多ZKP用例中包含证明知道某哈希preimage，或使用哈希、Merkle roots 以及 Merkle inclusion paths来高效表示电路之外的数据。
在ZKP证明系统中，Arithmetic hash函数（如Poseidon、Rescue Prime）常用于替换传统哈希函数（如SHA）。
尽管Arithmetic hash原生计算更昂贵，但当用于电路中时，其效率更高，即Arithmetic hash具有更少的约束数。
可选择多种算法参数来对系统中的Arithmetic hash进行实例化，不同的选择会影响计算开销（如field size、prime、round数、MDS矩阵结构等）。
Arithmetic hash的高效实现主要受模乘运算驱动。

4. 所需的硬件资源

4.1 模乘运算

不过，MSM、NTT、Hash等运算的底层原语为：

有限域运算和曲线ECC运算
有限域运算和曲线ECC运算主要由模乘运算（ModMul）支配
Naively模乘运算为 $O(N^2)$ ，如384-bit曲线ECC运算，要比256-bit的贵约2.25倍。

高层运算的性能开销取决于不同的特性，如：
运算数量
field size
curve point size
point表示方式（如Affine vs. Jacobian）
Prime/Modulus特性
运算复杂度（如Poseidon的 $x^5$ vs. $x^7$ ）
等等

根据这些特性，通常可计算出高层运算所需的ModMul运算总数。

4.2 选择合适的硬件

已知所有的计算开销都有模乘运算支配，因此，选择的硬件平台应可快速且便宜地执行大量模乘运算。

评估硬件性能时，主要看：

硬件乘法器数量
硬件乘法器size
每个指令的速度/频率

如以下硬件资源示例：
在这里插入图片描述
其中Mul Power计算规则为：

乘法器数量 * 乘法器size * 频率 / 1000

5. 加速的限制

硬件加速的2个关键元素为：

1）算法：
- 应选择“硬件友好”的算法。如现有硬件（COTS）GPU具有数千个核，适于可高度并行化的算法。
- 此外，高效算法应致力于减少所需（如模乘）运算数量，来减少总的计算开销。
2）高效代码实现：
- 一旦找到了高效、“硬件友好”算法，该算法需调整为更好地适配硬件能力。
- 为改进性能，实际代码实现应尽可能多的使用硬件资源。这通常需要利用底层汇编原语。

加速的限制为：

乘法并不是唯一所需的资源
其它一些非计算资源也可能成为瓶颈，如：
- 内存：【如有时NTT会受限于内存访问速度。】
  - 内存容量（如12GB）
  - 快速内存（如DDR、HBM）
- 高速数据传输通讯（如PCIe v4）【如当前的GPU和FPGA用于NTT加速时，不受限于计算资源，而取决于host与加速器之间的数据移动能力。】
- 其它计算资源和算术单元

当前的加速陷阱主要为：

1）通讯。过去数年来，数据移动越来越成为‘big data’系统的瓶颈。高度并行化的算法计算通常比数据移动要更快。
2）Amdahl’s Law（阿姆达尔定律）：“当提升系统的一部分性能时，对整个系统性能的影响取决于：1、这一部分有多重要；2、这一部分性能提升了多少。”
- 若MSM/NTT/Arithmetic Hash运算占约65%，则完全移除这些运算将把证明生成速度提升3倍。

6. 硬件加速的当前现状

一个生产级别的ZKP硬件加速举例：

当前Filecoin为最大的生产级别的ZKP系统，每天处理100万+ ZKP。
Filecoin采用‘Proof-of-Replication’（PoRep）ZKP证明。
每个PoRep中包含：
- 470GB的Poseidon Hashing：在CPU上运行需要约100分钟，在GPU上需要1分钟。
- 10个具有约1300万约束的Groth16 Proofs：
  - 需要约45亿次MSM运算（约42亿次在G1的MSM运算，以及约3亿次在G2的MSM运算）
  - 在CPU上运行需要约60分钟，而在GPU上需要3分钟。

目前网上有GPU和FPGA的不同种类的硬件加速库和试验。ZPrize.io是超赞的资源库，可找到代码并学习优化以及当前性能。
在这里插入图片描述