ZK硬件加速：过去，现在和未来

原文标题：ZK Hardware Acceleration: The Past, the Present and the Future

原文作者：Luke Pearson and the Cysic team

原文来源：hackmd

编译：Kate, Marsbit

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，涵盖了最基本的操作，包括算术运算、数据移动、逻辑运算和控制流。上述结构如下图所示：

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