原文:《ZK Hardware Acceleration: The Past, the Present and the Future》by Luke Pearson、the Cysic team

编译:Kate

TL;DR:

  • 在硬件加速 ZKP 中,FPGA 具有与 GPU 相同的每瓦性能水平,但在每美元性能指标上无法与 GPU 竞争。
  • ASIC 在上述两个指标上优于 FPGA 和 GPU,但需要更长的时间才能进入市场。

介绍

近年来,零知识证明 (ZKP) 的重要性呈指数级增长,成为过去半个世纪计算机科学中最重要的创新之一。这可以归因于 ZKP 有可能极大地增强区块链平台 ( 如以太坊 ) 的可扩展性。

ZKP 的一个关键方面是它们能够显著提高各种区块链平台上的每秒交易量 (TPS),这完全依赖于数学原理而不是信任。通过使验证者能够将多个交易合并到一个单一的、简洁的证明中,ZKP 确保了整个过程的准确性和完整性。ZKP 提供了许多其他功能,使它们成为各种扩展和隐私解决方案的重要组成部分,包括像 StarkNet 这样的 ZK 聚合,像 Aztec 这样的私有 ZK 聚合,以及像 Mina、Filecoin、Manta 和 Aleo 这样的第 1 层链。尽管如此,ZKP 也不是没有局限性,因为生成证明的过程在时间和精力方面都是非常耗费资源的。由于需要许多复杂的数学运算,例如幂运算、倒数运算和双线性配对计算,证明的创建通常会减慢速度。因此,优化 ZKP 解决方案以充分利用其潜力仍然是一项挑战。为了克服所有提出的 ZKP 构造的这些问题,开发硬件加速方法是至关重要的。也就是说,通过使用专用硬件,如现场可编程门阵列 (FPGA) 和专用集成电路 (ASIC),它们可以加速 10-1000 倍。

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

零知识证明:zkSNARKs 和 zkSTARKs

zkSNARK (Zero-Knowledge Succinct Non-Interactive ARgument of Knowledge) 方案是一种 ZKP,它允许证明者说服验证者,证明者知道一个证人,而不透露有关该证人的任何信息。该方案包括四种算法:Setup、KeyGen、Prove 和 Verify。Setup 算法生成一些结构化的参考字符串,KeyGen 算法将使用该字符串为某些指定电路生成证明密钥和验证密钥。证明者拥有证明密钥和陈述 / 见证对,可以通过指定的电路对陈述 / 见证对的关系生成 ZK 证明。验证者可以使用验证密钥和声明来检查 ZK 证明的有效性。

zkSNARK 方案需要满足以下特点:

  • 完整性:如果证明者拥有证人,他们可以产生有效的证明,并且验证者将始终接受它。
  • 零知识:证明方可以提供证据,证明其拥有秘密证人,而无需向验证方或其他任何人披露有关秘密证人的任何信息。
  • 可靠性:对于不诚实的证明者来说,不需要证人就能提出有效的证明是不可能的。

另一种变体称为 zkSTARK (Zero-Knowledge Scalable and Transparent ARgument of Knowledge)。它可以在零知识的情况下运行,也可以在没有零知识的情况下运行,并且可以是交互式或非交互式协议。它们也可以取代 zkSNARK 作为交互协议。与 zkSNARK 不同,交互式证明不需要可信的 Setup 设置阶段,这使 STARK 系统成为更好的选择。STARK 系统通过利用交互式 Oracle 证明 (IOP) 域克服了这一缺点,该域依赖于快速 Reed-Solomon 代码来提高可扩展性,从而开发了 zkSTARK 证明系统。此外,基于 zkSTARK 的系统对于证明者和验证者来说都具有对数复杂度,使它们变得高效,并防止一方执行拒绝服务 (DoS) 攻击,因为每一方的计算需要相似的时间。zkSTARK 的另一个值得注意的特性是推测的后量子安全性,而 zkSNARK 则不是由于 Shor 的量子算法。zkSTARK 系统提供后量子安全,前提是框架内使用的哈希函数本身能够抵抗量子计算攻击。

在区块链技术领域,通常使用缩写 SNARK 和 STARK 来代替 zkSNARK 和 zkSTARK,因为某些区块链平台可能并不总是需要隐私功能。因此,在本文中,我们也将在讨论和解释中采用简化的术语「zk」。ZKP 有两个重要的用例:

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

在区块链的背景中,ZKP 的上述用例如下:

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

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

为什么 ZKP 这么慢,怎样才能提高它们的速度?

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

在 ZKP 的背景中,主要有两个计算任务:

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

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

  • MSM 可以在多个线程上执行,从而支持并行处理。然而,当处理大型元素向量时,例如 6700 万个元素,乘法运算可能仍然很慢,并且需要大量的内存资源。此外,MSM 存在可扩展性方面的挑战,即使在广泛并行化的情况下也可能保持缓慢。
  • 在算法过程中频繁的数据混洗使得 NTT 难以在计算集群中分布,并且由于需要从大型数据集中加载和卸载元素,它们在硬件上运行时需要大量带宽。即使硬件操作很快,这可能也会导致速度变慢。例如,如果硬件芯片的内存为 16GB 或更少,那么在 100GB 的数据集上运行 NTT 将需要通过网络加载和卸载数据,这可能会大大降低操作速度。

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

ZPrize 零知识工具竞赛

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

  • 对于大规模问题实例,GPU 上的多标量乘法(2 的 26 次方元素)从 5.8 秒提高到 2.5 秒,从而支持更复杂的 zkSNARKs 使用。
  • Poseidon 零知识友好哈希函数实现将约束计数减少了一半,从而显著降低了在 SNARK 中创建 Merkle 树的成本。
  • 针对小规模问题实例,Android 移动设备上的多标量乘法从 2.4 秒改进到大约半秒,从而促进了基于 ZK 的移动支付。

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

加速 ZKP 的技术方法

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

MSM 通常使用 Pippenger 算法来实现,以最小化组添加操作的数量。该方法有一个简单的硬件实现,其中包括一个组添加单元和一堆表作为其基本组件。从系统设计的角度来看,MSM 是对加速器非常友好的,原因如下:

  • 组添加是一种静态操作 ( 没有依赖于数据的控制流 ),具有密集的计算和相对较小的输入 / 输出,使其非常适合全流水线的体系结构。这使得加速器可以实现几乎 100% 的硬件利用率,而在最好的 GPU 实现中只有 20% 的利用率。几十年的研究已经使组添加成为一种稳定的操作,因此它不太可能在 ASIC 加速器的寿命内被取代。
  • MSM 在全局调度能力相对较弱的大规模并行硬件(如 GPU)上实现的痛点可以通过向加速器添加额外的硬件调度器轻松解决。例如,以这种方式更有效地处理一堆表的更新,避免了写冲突的风险。

总之,使用专用硬件加速 MSM 是非常有利的。然而,主要问题是市场上缺乏这样的硬件。Cycis 设计了一个使用 Xilinx FPGA 的 MSM 加速器,它展示了迄今为止最好的系统性能 ( 在 BN254 曲线上每 2 的 26 次方 MSM 约 40 毫秒 )。不幸的是,与为普通玩家设计的 GPU 相比,专业用户的 FPGA 芯片成本高,加上 FPGA 的处理滞后 (FPGA 为 14nm, GPU 为 5nm),这是两个显著的缺点,这两个重大缺点抵消了基于 FPGA 的加速器的利用优势。

NTT 由多层蝶式操作器组成。虽然教科书上逐层的 NTT 实现可能很快就会因为内存带宽利用率 ( 由于跨行访问 ) 而成为瓶颈,但这个问题可以通过同时执行一批层并在计算期间适当地重新排序 NTT 数据来解决。根据经验,内存访问可以重组为块访问,其粒度大约为 ( 片上内存容量的大小 )/ (NTT 点的 k 次方根 ),其中 k 是表示层组数量的可调参数。通过这种方法,GPU 和加速器都能获得出色的性能。

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

现在和将来,什么是最好的硬件?

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

  • 每美元的性能:这衡量你需要为硬件性能支付多少资金。根据我们的经验,FPGA 在这个指标上无法与 GPU 竞争。根据 ZPrize 竞赛提交和我们的内部基准测试结果,单个 RTX3090 GPU 可以产生比单个高端 FPGA 高约 2.5 倍的性能。高端 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 是一个资本密集型的游戏。20 名工程师的全掩模 28nm ASIC 芯片设计通常需要花费 800 万美元,而 30 名工程师的全掩模 5nm/4nm ASIC 设计通常需要花费 2500 万美元。
  • 上市时间。ASIC 的设计、生产和部署通常需要 12 到 18 个月甚至更长时间,这比 FPGA/GPU 要长得多。

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

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

ZK硬件加速展望:当前挑战及潜在改进方案

这个 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 有望在未来实现越来越先进和安全的区块链系统中发挥关键作用。