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

原文标题：ZK Hardware Acceleration: The Past, the Present and the Future
原文作者：Luke Pearson and the Cysic team
原文来源：hackmd
编译：Kate, Marsbit

摘要：

●FPGA在硬件加速ZKP中具有与GPU相同的每瓦性能水平，但在每美元性能指标上无法与GPU竞争。

●ASIC优于FPGA和GPU，但进入市场需要更长的时间。

介绍

近年来，零知识证明(ZKP)其重要性呈指数级增长，成为过去半个世纪计算机科学中最重要的创新之一。这是因为ZKP有可能大大提高区块链平台(如以太坊)的可扩展性。ZKP的一个关键方面是，它们可以显著提高各种区块链平台上的每秒交易量(TPS)，这完全取决于数学原理，而不是信任。ZKP保证了整个过程的准确性和完整性，使验证者能够将多个交易合并到一个单一而简洁的证明中。ZKP提供了许多其他功能，使它们成为各种扩展和隐私解决方案的重要组成部分，包括像Starknet这样的ZK聚合、像Aztec这样的私人ZK聚合和Mina、Filecoin、像Manta和Aleo这样的第一层链。尽管如此，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方案需要满足以下特点：

●完整性：如果证人有证人，他们可以产生有效的证人，并且证人将永远接受它。

●零知识：证人可以提供证据证明其拥有秘密证人，而无需向证人或其他任何人披露任何关于秘密证人的信息。

●可靠性：对于不诚实的证人来说，没有证人就不可能提供有效的证明。

另一种变体称为zkSTARKK (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在区块链背景下的上述用例如下:

●第二层扩展:第一层区块链可以将交易处理委托给链下的高性能系统，通常称为第二层。该方法提高了区块链的可扩展性，同时保持了强大的安全措施，在效率和安全之间取得了平衡。StarkWare开发了Starknet，这是一个可扩展的智能合同平台，使用特殊的虚拟机执行ZK友好代码，而Aztec允许他们的第二层程序私下运行，以保护用户的交易信息。

●私有第1层：Aleo， Mina， Manta和Zcash是第一层区块链，使用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或更少，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。MSM贡献了大约70%的证明生成时间，同时使用NTT和MSM的加密系统，而NTT控制了剩余时间。MSM虽然可以并行，但还是很慢，需要大量的内存资源，经常消耗设备上的大部分可用内存。另一方面，NTT严重依赖于频繁的数据混洗，这将使跨计算集群负载分配的加速变得复杂。此外，NTT在硬件上运行需要大量的带宽，因为尽管硬件本身运行得非常快，但通过网络加载和卸载数据会显著降低运行速度。然而，为了优化生成过程，有一些方法可以提高MSM和NTT的性能。

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

●组添加是一种静态操作（不依赖数据控制流），具有密集的计算和相对较小的输入/输出，非常适合全流水线的系统结构。这使得加速器能够实现几乎100%的硬件利用率，而在最佳GPU实现中只有20%的利用率。几十年的研究使组添加成为一种稳定的操作，因此不太可能在ASIC加速器的使用寿命内被取代。

●MSM 大规模并行硬件(如全局调度能力相对较弱的大规模并行硬件) GPU）通过向加速器添加额外的硬件调度器，可以轻松解决上述痛点。例如，这样可以更有效地处理一堆表的更新，避免写作冲突的风险。

总之，使用特殊硬件加速MSM是非常有益的。然而，主要问题是市场上缺乏这样的硬件。Cycis设计了Xilinx FPGAMSM加速器显示了迄今为止最好的系统性能(BN254曲线每26次方 约40毫秒的MSM)。不幸的是，专业用户的FPGA芯片成本高于为普通玩家设计的GPU，加上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系统直接证明了这一点。

ZKPASIC怎么样？

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(ZKASIC)编程，支持ZK系统的多功能性。

至于ASIC的其他问题，这是由市场决定的。目前，ZK相关项目的总估值超过100亿美元。我们认为建立ASIC来提高ZK证书的生成效率是值得的。所有ASIC设计都固有这种上市时间问题。幸运的是，ASIC的供应链问题比以前好多了。解决这个问题的唯一办法就是尽快开始，彻底预热供应链。当ASIC问世时，它可以摧毁任何其他形式的ZK硬件。

结论

ZKP有潜力促进可扩展、私人支付系统和智能合同平台，从而大大提高区块链技术的可用性和安全性。的确，ZKP引入了历史上阻碍其使用的管理费用。基于ZKP的系统的复杂性，如巨大的计算和验证成本，可能会给许多开发人员造成进入的障碍。尽管如此，ZKP领域的研发正在解决这些挑战，简化这些技术在实践中的实现和应用。

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