Paradigm 对 ZKP 的研报

[Whisker17]

Hardware Acceleration for Zero Knowledge Proofs

[Whisker17]

ZKP 现存的弊端

• 由于大量昂贵的数学运算，ZKP 的生产速度慢且成本高。但是，通过使用现场可编程门阵列 (FPGA) 和专用集成电路 (ASIC) 等专用硬件，它们可以加速 10-1000 倍。
• 随着用户寻求更具表现力、高性能和私密性的计算，使用 ZKP 证明的语句的复杂性将会增加。这将导致证明生成速度变慢，需要使用专门的硬件才能及时生成证明。

[Whisker17]

ZKP 现存的用例

• 外包可验证计算
• 隐私计算

如果细分为小类的可以分为：

• L2 扩展 zkp 的可验证计算允许 L1 将交易处理外包给链外高性能系统(又名第 2 层)。这可以在不影响安全性的情况下实现区块链扩展。例如，StarkWare 正在构建一个可扩展的智能合约平台 StarkNet ，使用一个运行 zk 友好代码的专用虚拟机。Aztec 还允许他们的第二层程序私下运行，而不会泄露用户交易的任何信息。
• L1链 Aleo、Mina和Zcash，允许交易人员使用zkp隐藏发件人、收件人或金额，默认情况下(Aleo)或作为选择加入(Mina和Zcash)
• 去中心化存储 Filecoin 使用 ZKP（在 GPU 上运行）来证明网络中的节点正确存储数据。
• 区块链压缩 Mina 和 Celo 使用 ZKP 将同步到链上最新状态所需的区块链数据压缩成一个小证明。

[Whisker17]

ZK 慢的原因

• 证明计算需要首先将其从经典程序转换为 ZK 友好格式。这可以通过手动重写代码以使用像Arkworks这样的低级库来完成，或者通过使用像Cairo或Circom这样编译成必要的原语来生成证明的领域特定语言来完成。

• 更昂贵和更复杂的操作会导致更长的证明生成时间。某些操作对 ZK 不友好也很常见（例如，SHA 或 Keccak 中使用的按位操作），导致在经典计算机上可能是廉价操作的证明生成时间较长。

• 一旦您的计算采用 ZK 友好的形式，您就可以选择一些输入并将其发送到证明系统。证明系统的共同点是都是采用 ZK 友好格式表示的计算以及一些输入并输出证明。

• 根据证明系统的不同，证明生成过程可能会有所不同，但瓶颈始终是：

  • 对大型数字向量（字段或组元素）的乘法，特别是可变基数和固定基数多标量乘法 (MSM)
  • 快速傅里叶变换 (FFT) 和逆 FFT（尽管有用于无 FFT 证明系统的技术）。

[Whisker17]

如何加速

• 在同时存在 FFT 和 MSM 的系统中，大约 70% 的时间生成证明花费在 MSM 上，其余时间则由 FFT 主导。

• MSM 和 FFT 都很慢，但都有提高性能的方法：

  • MSM 具有令人尴尬的并行性，可以通过在多个线程上运行它们来加速。然而，即使在数百个内核上，如果每个元素向量是 2^25长（即 3300 万个元素，对于像zkEVM这样的应用程序来说，这是一个保守的复杂度范围），乘法最终仍然会花费大量时间。这意味着经常重复相同的操作，并且会耗尽设备上的大部分可用内存。简而言之，MSM 需要大量内存并且即使在高度并行化时仍然很慢。
  • FFT 严重依赖算法运行时数据的频繁洗牌。这使得它们很难通过跨计算集群分配负载来加速，如DIZK所示。此外，它们在硬件上运行时需要大量带宽。改组意味着您需要“随机”加载和卸载元素，例如，具有 16GB 或更少内存的硬件芯片上的 >100GB 数据集。虽然硬件上的操作非常快，但通过网络加载和卸载数据的时间最终会显着减慢操作速度。

• 简而言之：

  • MSM 具有可预测的内存访问，允许大量并行化，但由于所需的原始计算量和内存量，它们的成本仍然很高。
  • FFT 具有随机内存访问，这使得它们对硬件不友好，而且自然难以在分布式基础设施上运行。

• 在解决大型 MSM 和 FFT 的缓慢问题方面，我们看到的最有希望的工作是 PipeZK。在他们的论文中，作者描述了一种使用Pippenger 算法跳过重复计算来使 MSM 更便宜的方法。他们还描述了一种“展开”FFT 的方法，这样它们就可以在没有显着改组的情况下执行，由于现在可预测的内存访问模式，这可以提高硬件的速度。

[Whisker17]

硬件选择

• FPGA 有两个核心特性使其在 ZK 环境中优于 ASIC：

  • “多次写入”与“一次写入”：ASIC 上的业务逻辑是一次写入。如果任何 ZKP 逻辑发生变化，您需要从头开始。FPGA 可以在 1 秒内重新刷新任意次数，这意味着它们可以在具有不兼容证明系统的多个链上重复使用相同的硬件（例如，因为他们想要跨链提取 MEV），并灵活地适应 ZK “元”的变化。
  • 更健康的供应链： ASIC 设计、制造和部署通常需要 12 到 18 个月或更长时间。相反，FPGA 供应链是健康的