零知识证明硬件加速：过去、现在与未来

作者：Luke Pearson 及 Cysic 团队

要点：

• 在硬件加速 ZKP 方面，FPGA 的每瓦性能与 GPU 持平，但在每美元性能指标上无法与 GPU 竞争。
• ASIC 在上述两个指标上均优于 FPGA 和 GPU，但上市时间较长。

引言

近年来，零知识证明 (ZKP) 的重要性呈指数级增长，成为过去半个世纪计算机科学领域最关键的创新之一。这可以归因于 ZKP 有可能显著提高以太坊等区块链平台的可扩展性。ZKP 的一个关键方面是它们能够显著增加各种区块链平台上的每秒交易数 (tps)，仅依赖于数学原理而不是信任。通过使验证者能够将多个交易合并为一个简洁的证明，ZKP 确保了整个过程的准确性和完整性。ZKP 提供了许多其他功能，使其成为各种扩展和隐私解决方案的重要组成部分，包括像 StarkNet 这样的 ZK 聚合、像 Aztec 这样的私有 ZK 聚合，以及像 Mina、Filecoin、Manta 和 Aleo 这样的 Layer 1 链。尽管如此，ZKP 并非没有其局限性，因为生成证明的过程在时间和能源方面都可能非常耗费资源。由于需要大量的复杂数学运算，例如求幂、求逆和双线性配对计算，证明的创建常常会减慢速度。因此，优化 ZKP 解决方案以充分发挥其潜力仍然是一个挑战。为了克服所有提出的 ZKP 构造的这些问题，开发硬件加速方法至关重要。也就是说，它们可以通过使用专用硬件（如现场可编程门阵列 (FPGA) 和专用集成电路 (ASIC)）来加速 10 到 1000 倍。

在本文中，我们将概述与 ZKP 相关的计算挑战，然后讨论可能有助于解决这些问题并提高这些加密技术效率的潜在改进措施。

零知识证明：zkSNARKs 和 zkSTARKs

zkSNARK（零知识简洁非交互知识论证）方案是一种 ZKP，它允许证明者说服验证者，证明者知道一个 witness，而无需泄露关于该 witness 的任何信息。该方案由四个算法组成：Setup、KeyGen、Prove 和 Verify。setup 算法生成一些结构化的参考字符串，KeyGen 算法将使用它来为一些指定的电路生成证明密钥和验证密钥。证明者使用证明密钥和 statement/witness 对，可以通过指定的电路生成关于 statement/witness 对关系的 ZK 证明。验证者可以使用验证密钥和 statement 来检查 ZK 证明的有效性。

一个 zkSNARK 方案需要满足以下特点：

• 完备性：如果证明者拥有 witness，他们可以生成一个有效的证明，并且验证者总是会接受它。
• 零知识性：证明者可以提供证据表明它拥有秘密 witness，而无需向验证者或任何其他人泄露有关它的任何信息。
• 可靠性：对于不诚实的证明者来说，在不需要 witness 的情况下创建有效的证明是不可能的。

另一种变体称为 zkSTARK（零知识可扩展透明知识论证）。它可以有或没有零知识地运行，并且可以是交互式或非交互式协议。它们也可以替代 zkSNARK 作为交互式协议。与 zkSNARK 不同，交互式证明不需要可信设置阶段，这使得 STARK 系统成为更好的选择。STARK 系统通过利用交互式 Oracle 证明 (IOP) 域克服了这一缺点，该域依赖于快速 Reed-Solomon 码来提高可扩展性，从而导致了 zkSTARK 证明系统的开发。此外，基于 zkSTARK 的系统传统上以对数复杂度处理证明者和验证者，使其高效并防止一方执行拒绝服务 (DoS) 攻击，因为双方的计算量相似。zkSTARK 的另一个值得注意的特性是推测的后量子安全性，而 zkSNARK 则不具备，因为它受到 Shor 的量子算法的影响。zkSTARK 系统提供后量子安全性，前提是框架内使用的哈希函数本身能够抵抗量子计算攻击。

在区块链技术领域，缩写词 SNARK 和 STARK 通常用于代替 zkSNARK 和 zkSTARK，因为当隐私未实施或区块链用例不同时，也会使用它们。因此，在本文中，我们将在讨论和解释中也采用简化的术语“zk”。ZKP 有两个重要的用例：

• 外包可验证计算：假设我们需要进行一项计算，由于底层平台的限制（例如，智能手机、树莓派、笔记本电脑，甚至以太坊等区块链网络），该计算要么成本高昂，要么无法运行。在这种情况下，我们可能需要在第三方服务上运行计算，该服务可以快速且廉价地返回计算的输出（例如，Chainlink 等 oracle 服务或 AWS Lambda 函数）。然而，在许多情况下，我们必须依赖于计算已正确执行的假设，从而使服务提供商有可能生成不准确的结果。这种结果可能会导致严重的后果并损害系统的完整性。
• 私有计算：在本地执行计算成本不高但某些部分需要保密的情况下，ZKP 也可以发挥作用。换句话说，ZKP 可以确保计算已正确执行，甚至无需向外包提供商披露私有值。例如，如果我们想证明我们知道第 1000 个斐波那契数，而不泄露实际数字，或者证明我们进行了有效的支付，而不泄露我们的身份或支付金额，ZKP 可以轻松地帮助实现这一目标。更进一步，我们可以有选择地披露一些私有值，同时通过 ZKP 隐藏其他部分（这也称为选择性披露）

在区块链的背景下，ZKP 的上述用例呈现为：

• Layer 2 扩展：通过将 ZKP 纳入可验证计算中，Layer 1 区块链可以将交易处理委托给链下高性能系统，通常称为 Layer 2。这种方法增强了区块链的可扩展性，同时保持了强大的安全措施，从而在效率和安全性之间取得了平衡。StarkWare 和 Scroll 开发了可扩展的智能合约平台，这些平台采用专门的虚拟机来执行 ZK 友好的代码，而 Aztec 允许其 layer 2 程序私下运行，从而保护用户交易的信息。
• 私有 layer 1：Aleo、Mina、Manta 和 Zcash 是 layer 1 区块链，它们使用 ZKP 来使交易者能够隐藏发送者、接收者或金额，无论是默认情况下（如 Aleo）还是通过选择加入过程（如 Mina 和 Zcash）。
• 数据压缩：ZKP 被 Mina 和 Celo 用于压缩区块链数据，这些数据是同步到链的最新状态所需的，并将其压缩为简短的证明。
• 去中心化存储：Filecoin 还使用 ZKP（在 GPU 上运行）来证明网络中的节点正确存储数据。

因此，随着加密货币的采用持续扩展，对增强的性能和隐私的需求预计也会增加，从而推动对更复杂的 ZKP 应用的需求。随着开发人员创建新的应用程序和协议，ZKP 有望在促进安全高效的去中心化系统中发挥关键作用。这些系统将能够处理大规模的交易处理，同时保护用户隐私，满足数字货币领域不断发展的要求。

为什么 ZKP 速度慢，以及可以做些什么来提高其速度？

要使用 ZKP 证明计算，有必要将计算从经典程序转换为 ZK 友好的格式。有两种方法可以做到这一点：要么使用以某种现有语言（如 Rust 中的 Arkworks）编写的库，要么使用领域专用语言 (DSL)（如 Cairo 或 Circom），该语言会编译为生成证明所需的基元。操作越复杂，生成证明所需的时间就越长。此外，某些操作本质上不是 ZK 友好的，需要额外的工作才能使其如此。例如，在 SHA 或 Keccak 中使用的按位函数等操作可能与 ZKP 不友好，从而导致延长的证明生成时间。即使对于在经典计算机上执行时相对便宜的操作，也可能发生这种情况。在将计算转换为 ZK 友好的格式后，你可以选择一些输入并将其提交给证明系统。有许多证明系统，例如 Groth16、PLONK、HyperPlonk、UltraPlonk、Sonic、Spartan 和 STARK。所有这些系统都共享接受带有输入的 ZK 友好计算并生成证明作为输出的相同基本功能。根据证明系统的不同，证明生成过程可能会有所不同，但瓶颈最终是相似的。

在 ZKP 的上下文中，主要使用两种计算任务：

• 大数向量的乘法，它们可以是字段或群元素。在这种情况下，还有两种特定类型的乘法：变基和定基多标量乘法 (MSM)。
• 数论变换 (NTT) 和逆 NTT。然而，也有可用于无 NTT 证明系统的技术，例如最近的 HyperPlonk 系统。

在 NTT 和 MSM 都存在的证明系统中，生成证明的时间大约 60% 花在 MSM 上，其余时间由 NTT 主导。MSM 和 NTT 都有可以通过以下方式解决的性能挑战：

• MSM 可以在多个线程上执行，从而实现并行处理。然而，当处理大量元素向量（例如 6700 万个元素）时，乘法可能仍然很慢，并且需要大量的内存资源。此外，MSM 提出了可扩展性挑战，即使在广泛并行化时也可能仍然缓慢。
• 算法中频繁的数据混洗使得 NTT 难以在计算集群中分发，并且由于需要从大型数据集中加载和卸载元素，因此在硬件上运行时需要大量的带宽。即使硬件操作很快，这也会导致速度减慢。例如，如果硬件芯片具有 16GB 或更少的内存，则在 >100GB 数据集上运行 NTT 将需要在网络上加载和卸载数据，这会显着降低操作速度。

我们认为，硬件加速是使区块链协议能够实现实际应用所需的可扩展性的重要组成部分。目前，区块链协议受到其链上计算和存储容量以及其网络带宽的限制。通过优化链下硬件和证明生成，我们相信我们可以大幅提高区块链网络的性能，使其更有效率。

零知识工具的 ZPrize 竞赛

ZPrize 是区块链行业内的一项集体倡议，包含超过 32 个合作伙伴和赞助商，他们贡献自己的时间、资源和努力来确保其成功。该计划提供了一系列挑战和计划，以激发参与者开发创新解决方案，以促进可持续性并减少碳排放。他们以实现这两个目标而自豪，这标志着零知识密码学领域的重大进步。ZPrize 的结果超出了他们的预期，如下面的图表所示。对于他们收到提交的大多数奖项，从基线的平均增强超过五倍。值得注意的是，一些涉及 FPGA 的奖项缺乏公开基准测试，这使得这些提交成为算法实现以开源形式的首次公开展示。以下是一些值得注意的成就：

• 用于大规模问题实例的多标量乘法（

226 个元素）显示从 5.8 秒到 2.5 秒的改进，从而可以更复杂地使用 zkSNARK。

• Poseidon 零知识友好哈希函数实现将约束计数减少了一半，从而显着降低了在 SNARK 中创建 Merkle 树的成本。
• 用于小规模问题实例的 Android 移动设备上的多标量乘法从 2.4 秒提高到大约半秒，从而促进了基于 ZK 的移动支付。

在接下来的几个月中，他们计划展示所有参与此倡议的团队的工作。随着零知识密码学领域的发展，新的方法和障碍将会出现。他们渴望定期组织 ZPrize 竞赛，以促进这项技术的进步，并通过一系列开源资料向公众提供。

加速 ZKP 的技术方法

证明生成中的瓶颈通常源于大数向量的乘法，包括字段或群元素、变量或固定基数的多标量乘法，以及 NTT 和逆 NTT。在使用 NTT 和 MSM 的证明系统中，MSM 贡献了大约 60% 的证明生成时间，而 NTT 占据了剩余的时间。尽管 MSM 是可并行化的，但它仍然很慢，需要大量的内存资源，并且经常消耗设备上的大部分可用内存。另一方面，NTT 严重依赖于频繁的数据混洗，这使得通过在计算集群中分配负载来加速变得复杂。此外，NTT 需要大量的带宽才能在硬件上运行，因为通过网络加载和卸载数据会显着降低操作速度，尽管硬件操作本身非常快。然而，有一些方法可以提高 MSM 和 NTT 的性能，以便优化证明生成过程。

MSM 通常使用 Pippenger 算法来实现，以最大限度地减少群加法运算的数量。此方法具有直接的硬件实现，其中包括一个群加法单元和一个桶表作为其基本组件。从系统设计的角度来看，MSM 因以下原因而非常适合加速器：

• 群加法是一种静态运算（没有数据相关的控制流），具有密集的计算和相对较小的输入/输出，使其非常适合完全流水线化的架构。与最佳 GPU 实现中看到的 20% 的利用率相比，这使加速器能够实现接近 100% 的硬件利用率。数十年的研究使群加法成为一种稳定的运算，因此它不太可能在 ASIC 加速器的寿命内被替换。
• 通过向加速器添加额外的硬件调度器，可以轻松解决在具有相对较弱的全局调度能力的大规模并行硬件（如 GPU）上 MSM 实现的痛点。例如，以这种方式可以更有效地处理更新桶表，从而避免了写入冲突的风险。

总之，使用专用硬件加速 MSM 非常有利。然而，主要问题是市场上缺乏此类硬件。Cysic 设计了一个使用 Xilinx FPGA 的 MSM 加速器，这展示了迄今为止最佳的系统级性能（大约 40 毫秒/

226 在 BN254 曲线上的 MSM）。不幸的是，与为普通游戏玩家设计的 GPU 相比，FPGA 芯片对于专业用户来说成本很高，加上 FPGA 的工艺滞后（FPGA 的 14 纳米与 GPU 的增强型 5 纳米相比），这两个显着的缺点抵消了基于 FPGA 的加速器的利用优势。

NTT 由多个蝴蝶算子层组成。虽然教科书式的逐层 NTT 实现可能会因内存带宽利用率（由于步长访问）而很快成为瓶颈，但可以通过同时执行一批层并在计算期间正确地重新排序 NTT 数据来解决此问题。根据经验，内存访问可以重组为块访问，其粒度约为（片上内存容量的大小）/（

NTT 点的 k 次方根），其中

k 是表示层组数量的可调参数。通过使用这种方法，GPU 和加速器都可以实现出色的性能。

硬件加速可以通过在各种硬件技术（例如 GPU、FPGA 或 ASIC）上部署优化的算法来支持区块链协议的性能。增强软件和算法实现，以更有效地利用现有资源（如 CPU 和 GPU），以及结合为特定硬件配置量身定制的新颖算法，开发定制硬件，可以促进硬件加速。通过这样做，可以显着提高区块链网络的性能，这些网络目前受到其链上计算和存储容量以及网络带宽的限制。

使用哪种硬件是最好的：现在和将来？

为了确定实现上述加速技术的最佳硬件技术，我们需要考虑到 ZKP 仍处于开发的早期阶段。因此，系统参数和证明系统的选择（例如 FFT 宽度或元素的位大小）的标准化有限。此外，我们还需要考虑两个因素：

• 每美元性能：这衡量了你需要为硬件性能支付多少资本。根据我们的经验，FPGA 在此指标上无法与 GPU 竞争。根据 ZPrize 竞赛提交和我们的内部基准测试结果，单个 RTX3090 GPU 可以产生大约 2.5 倍于单个高端 FPGA 的性能。并且高端 FPGA 和高端 GPU 的价格大致相同，这意味着最终 FPGA 将比 GPU 系统贵大约 2.5 倍。
• 每瓦性能：此指标是关于你必须花费多少费用来维护硬件，这基本上就是电费。FPGA 在此指标上与 GPU 大致处于同一水平。

基于上述两个指标，这是否意味着 FPGA 无法胜过 GPU？答案是否定的。虽然单个 FPGA 芯片无法与单个 GPU 竞争，但大规模互连的 FPGA 系统可以击败大规模互连的 GPU 系统。由于 PCIe 插槽的限制，顶级 GPU 系统最多只能有 10 个 GPU 卡。然而，数十个 FPGA 芯片可以通过定制的、可编程的、高带宽的互连连接在一起，从而达到可以击败 GPU 系统的性能水平。Cysic 的大规模互连 FPGA 系统直接证明了这一见解。

用于 ZKP 的 ASIC 怎么样？

ASIC 普遍被认为是 ZKP 的理想硬件。然而，对于构建用于 ZKP 的 ASIC 存在三个主要问题。

• 可编程性：就 ZKP 逻辑修改而言，ASIC 具有一次写入的业务逻辑，这需要从头开始重建整个系统。相反，FPGA 或 GPU 可以重新编程多次，从而可以在具有不同证明系统或潜在更新的各种项目中使用相同的硬件。与 ASIC 相比，此属性使 FPGA 成为更通用的替代方案。
• 高成本：构建 ASIC 是一项资本密集型游戏。通常需要花费 800 万美元用于具有 20 名工程师的全掩模 28 纳米 ASIC 芯片设计，或花费 2500 万美元用于具有 30 名工程师的全掩模 5 纳米/4 纳米 ASIC 设计。
• 上市时间。ASIC 设计、生产和部署所需的时间通常为 12 到 18 个月或更长时间，这比 FPGA/GPU 要长得多。

第一个问题可以使用硬件中的框架来解决，该框架称为指令集架构 (ISA)。ISA 是指硬件系统（例如 CPU 和硬件加速器）的抽象框架和设计。它表示处理器可以执行的基本指令和操作集。这些指令包括算术运算、数据移动、逻辑运算、控制流和其他低级函数。使用 ISA，硬件加速 ZKP 可以分为三个层：

• 方案层：各种 ZK 证明系统都在这一层中，例如 Groth16 和 Plonk。顶层调用内核层来完成计算。
• 内核层：内核层的工作是计算顶层使用的不同函数。这些函数包括多标量乘法、数论传递、多项式评估和各种哈希函数。它依赖于指令层来执行计算。
• 指令层：这一层是 ISA，它涵盖了最基本的操作，包括算术运算、数据移动、逻辑运算和控制流。上述结构如下图所示：

此 ISA 结构提供了一个支持多个 ZK 系统和潜在更新的解决方案。可以使用 ZK-ISA 对 AZK（用于 ZK 的 ASIC）进行编程，以支持 ZK 系统的多功能性。

对于关于做 ASIC 的其他担忧，这取决于市场。目前，与 ZK 相关的项目的估值加起来超过 100 亿美元，我们认为花费大约 1000 万美元来构建 ASIC 以提高 ZK 证明生成的效率是值得的。这个上市时间问题是所有 ASIC 设计中固有的。幸运的是，ASIC 的供应链问题现在比以前好多了。解决此问题的唯一方法是尽早启动并彻底预热供应链。到 ASIC 问世时，它可以摧毁任何其他形式的 ZK 硬件。

结论

ZKP 具有促进可扩展和私有的支付系统以及智能合约平台的潜力，从而大大增强区块链技术的可用性和安全性。ZKP 确实引入了开销，这些开销在历史上阻碍了它们的采用。诸如显着的计算和验证成本以及实施基于 ZKP 的系统的复杂性等因素可能会为许多开发人员设置进入壁垒。然而，ZKP 领域的持续研究和开发正在解决这些挑战，从而简化这些技术在实践中的实施和应用。

考虑到 GPU 在灵活性、易于部署和预期性能方面的优势，我们认为，在 ASIC 技术出现之前的未来几个月内，专注于 GPU 解决方案的公司更有可能蓬勃发展。如果 ASIC 达到主导规模和稳定性，它们可能会成为优化算法的首选硬件。因此，ZKP 有望在未来继续在实现日益先进和安全的区块链系统中发挥关键作用。

• 原文链接： hackmd.io/@Cysic/BJQcpVb...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～