原文：《IOSG Weekly Brief | 为什么我们看好零知识证明硬件加速 #150》
作者：Bryan, IOSG Ventures
本文将主要讨论ZKP作为扩容方案的发展现状，从理论层面描述产生证明过程中主要需要优化的几个维度，并引深到不同扩容方案对于加速的需求。然后再围绕硬件方案着重展开，展望zk硬件加速领域的摩尔定律。最后，关于硬件zk加速领域的一些机会和现状，会在文末阐述。首先，影响证明速度的主要有三个维度：证明系统，待证明电路规模，和算法软硬件优化。（推荐阅读：《算力硬件的下一个蓝海：ZK证明计算》）
对于证明系统来说，凡是使用椭圆曲线（EC）的算法，也就是市面上主流的Groth 16（Zcash), Galo2(Scroll), Plonk(Aztec, Zksync)这些zk-snark算法，产生多项式承诺的过程中涉及的大数点乘（MSM），目前都有时间长（算力要求高）的瓶颈。对于FRI-based算法，如ZK-Stark，其多项式承诺产生方式是Hash Function，不牵扯EC，所以并不涉及MSM运算。
证明系统是基础，待证明电路的规模也是核心的硬件优化的需求之一。近期讨论很火的ZKEVM据对以太坊的兼容程度不同，导致了电路的复杂程度的不同，比如Zksync/Starkware构建了与原生以太坊不同的虚拟机，从而绕开了一些以太坊原生的不适合利用zk处理的底层代码，缩小了电路的复杂长度，而Scroll/Hermez这样目标从最底端兼容的zkevm的电路自然也会更复杂。（一个方便理解的比方是，电路的复杂性可以理解为一辆巴士上的座位，比如普通日子下需要搭载的乘客数在30人以下，有些巴士选择了30人的座位，这些巴士就是Zksync/StarkWare，而一年中也有一些日子有特别多的乘客，一般的巴士坐不下，所以有一些巴士设计的座位更多（Scroll）。但是这些日子可能比较少，会导致平时会有很多空余的座位。）硬件加速对于这些电路设计更复杂的电路更迫切，不过这更多是一个Specturm的事情，对于ZKEVM也同样有利无弊。
不同证明系统优化的需求/侧重点:
基本：
当一个待证明事物经过电路（如R1CS/QAP）处理之后，会得到一组标量和向量，之后被用来产生多项式或者其他形式的代数形式如inner product argument (groth16)。这个多项式依然很冗长，如果直接生成证明那么无论是证明大小或是验证时常都很大。所以我们需要将这个多项式进一步简化。这里的优化方式叫做多项式承诺，可以理解为多项式的一种特殊的哈希值。以代数为基础的多项式承诺有KZG, IPA，DARK，这些都是利用椭圆曲线产生承诺。
FRI是以Hash Function为产生承诺的主要途径。多项式承诺的选择主要是围绕几点 - 安全性，Performance。安全性在这里主要是考虑到在set up阶段。如果产生secret所使用的randomness是公开的，比如FRI，那么我们就说这个set up是透明的。如果产生secret所利用的randomness是私密的，需要Prover在使用之后就销毁，那么这个set up是需要被信任的。MPC是一种解决这里需要信任的手段，但是实际应用中发现这个是需要用户来承担一定的成本。
而上述提到的在安全性方面相对卓越的FRI在Performance并不理想，同时，虽然Pairing-friendly椭圆曲线的Performance比较卓越，但是当考虑将recursion加入时，因适合的曲线并不多，所以也是相当大的存在相当大的overhead。
图片来源：https://hackernoon.com
Justin Drake on Polynomial commitment, Part 1
行业现状：
当前不管是的基于Plonk(matterlabs) 或者基于Ultra-Plonk(Scroll, PSE)，他们最后的多项式commitment都是基于KZG，故而Prover的大部分工作都会涉及到大量的FFT计算(产生多项式）和ECC 点乘MSM运算（产生多项式承诺）。在纯plonk模式下，由于需要commit的point数量不大，MSM运算所占的Prove时间比重不高，所以优化FFT性能能够短期带来更大的性能提升。但是在UltraPlonk（halo2）框架下，由于引入了customer gate，prover阶段设计的commit的point数量变多，使得MSM运算的性能优化也变得非常重要。（目前MSM运算进行pippenger优化之后，依然需要log(P(logB)) (B 是exp的上界，p是参与MSM的point的数量)。
目前新一代Plonky2证明系统由于所采用的多项式commitment不再是KZG而是STARK系统中常见的FRI，使得Plonky2的prover不需要再考虑MSM，从而理论上该系统的性能提升不再依赖MSM相关的算法优化。plonky2的作者Mir(目前的 Polygon Zero)正在大力推广该系统。不过由于plonky2采用的数域Goldilocks Field对于编写elliptic 相关的hash算法相关的电路（例如ECDSA）不是特别友好，所以尽管Goldilocks Field在机器word运算方面优势明显，但是依然难以判断Mir 和PSE/Scroll方案谁是更好的方案。
基于对Plonk,Ultraplonk, Plonky2的Prove算法的综合考量，需要硬件加速的模块大概率还是会集中在FFT，MSM，HASH 三个方向。
Prover的另一个瓶颈是witness的生成，通常普通非zk计算会略去大量的中间变量，但是在ZK prove的过程中，所有witness都需要被记录，并且会参与之后的FFT计算，所以如何高效的并行witness计算也会是prover矿机需要潜在考虑的方向。
加速ZKP方面的尝试: recursive proof - StarkNet的fractal L3概念基于recursive proof的概念，Zksync的fractal hyperscaling，Scroll也有类似的优化。
> Recursive zkSNARK 概念是对一个 Proof A 的验证过程进行证明，从而产生另一个 Proof B。只要 Verifier 能接受 B，那么相当于也接受了 A。递归 SNARK 可以也可以把多个 证明聚合在一起，比如把 A1 A2 A3 A4 的验证过程聚合为 B；递归 SNARK也可以把一段很长的计算过程拆解为若干步，每一步的计算证明 S1 都要在下一步的计算证明中得到验证，即计算一步，验证一步，再计算下一步，这样会让 Verifier 只需要验证最后一步即可，并避免构造一个不定长的大电路的难度。
理论上 zkSNARK 都支持递归，有些 zkSNARK 方案可以直接将 Verifier 用电路实现，另一些 zkSNARK 需要把 Verifier 算法拆分成易于电路化的部分和不易电路化的部分，后者采用滞后聚合验证的策略，把验证过程放到最后一步的验证过程中。
在L2的未来应用上，递归的优势可以通过对于带证明事物的归纳而进一步将成本与性能等要求进一步降低。
第一种情况(application-agnostic)是针对不同的待证明的事物，比如一个是state update另一个是Merkle Tree，这两个待证明事物的proof可以合并成一个proof但是依旧存在两个输出结果（用来分别验证的public key)
第二种情况(applicative recursion) 是针对同类的待证明的事物，比如两个都是state update, 那么这两个事物可以在生成proof前进行聚合，且仅有一个输出结果，该结果就是经历了两次update的state difference。（Zksync的方法也类似，user cost仅对state difference负责）
除了recursive proof以及下文主要讨论的硬件加速之外，还有其他的加速ZKP的方式，比如custom gates, 移除FFT（OlaVM的理论基础）等，但本文因篇幅原因不予讨论。
硬件加速
硬件加速在密码学中一直是一种普遍的加速密码学证明的方式，无论是对于RSA（RSA的底层数学逻辑与椭圆曲线有类似之处，同样涉及了很多复杂的大数运算），还是早期对于zcash/filecoin的zk-snark的GPU-based的优化方式。
硬件选择
在以太坊The Merge发生之后，不可避免将会有大量的GPU算力冗余（部分受到以太坊共识改变的影响，GPU巨头英伟达股价距年初已经跌去50%，同时库存冗余也在不断增加），下图是英伟达GPU旗舰产品RTX 3090的成交价格，也显示买方势力较为薄弱。
在GPU价格处于低点，同时大量GPU算力闲置，一个自然的问题就是，是否GPU是合适的加速zk的硬件呢？硬件端主要有三个选择，GPU/FPGA/ASIC.
FPGA vs GPU:
先看总结：以下是trapdoor-tech关于GPU（以Nvidia 3090为例）以及 FPGA（Xilinx VU9P为例）在几个维度的总结，非常重要的一点是：GPU在性能（生成证明的速度）方面要高于FPGA, 而FPGA在能源消耗则更具有优势。
一个更直观的来自于Ingoyama的具体的运行结果：
尤其是对于比特宽度更高（2^20）的运算，GPU是FPGA运算速度的五倍，而消耗的电量同时也高很多。
对于普通矿工来说，性价比也是一个衡量到底使用哪一个硬件的重要的因素。无论是U55C ($4795) 还是 VU9P ($8394) 来说，相比于GPU (RTX 3090：$1860)，价格都要高出很多。
理论层面，GPU适合并行运算，FPGA追求可编程性，而在零知识证明生成的环境下，这些优势并不能完美适用。比如，GPU适用的并行计算是针对大规模图形处理，虽然逻辑上和MSM的处理方式类似，但是适用的范围（floating number）与zkp针对的特定的有限域并不一致。对于FPGA来说，可编程性在多个L2的存在的应用场景并不明朗，因为考虑到L2的矿工奖励与单个L2承接的需求挂钩（与pow不一样），有可能在细分赛道出现winner takes all的局面，导致矿工需要频繁更换算法的情景出现的可能性不高。
ASIC是在性能与成本方面上权衡表现较优的方案（包括吞吐量、延迟等），但是否是最好的方案仍然没有定论，其存在的问题是：
开发时间长- 需经历完整的芯片设计到芯片生产的过程，即使目前已经设计好了芯片，芯片生产也是一个冗长、烧钱并且良片率不一的过程。代工资源方面，台积电和三星是最好的芯片代工工厂，目前台积电的订单已经排到了两年后，与ZK芯片竞争代工资源的是AI芯片、电动车芯片这类web2早早做好芯片设计的已经被需求证明的产品，相比之下ZK芯片的需求并不明朗。
其次，整颗芯片的性能和单个芯片的大小，也就是人们常说的20nm,18nm是成负相关的，也就是说单个芯片越小，晶片可以容纳的芯片的数量越多，即整颗的性能越高，而目前的制造高端芯片的的技术是被垄断的（比如芯片制造中最复杂的一环，光刻技术，是被荷兰的ASML公司垄断），对于一些中小型的代工厂（如国内的中芯国际）这类技术方面落后顶尖一到两代，也就意味着从良品率以及芯片大小方面是落后于最好的代工厂的。这会导致对于ZK芯片来说，只能寻求一些次优的解决方案，当然也是在需求端不那么明朗的情况下基于成本的考虑，选择28nm左右的非高端芯片。
目前的ASIC解决方案主要处理的是FFT以及MSM两个常见的ZK电路中算力需求比较高的算子，并不是针对具体的一个项目设计的，所以具体运行的效率并不是理论上最高的。比如，目前Scroll的prover的逻辑电路还没百分百实现，自然也不存在与之一一匹配的硬件电路。并且，ASIC是application-specific，并不支持后续的调整，当逻辑电路发生了变化，比如节点的客户端需要升级，是否存在一个方案也可以兼容，也是目前不确定的。
同时，人才缺失也是ZK芯片的一个行业现状，理解密码学和硬件的人才并不好找，合适的人选是有同时具备较深的数学造诣以及多年的硬件产品设计以及维护经验。
Closing thoughts - prover发展趋势EigenDA
以上都是行业对于加速ZKP的思考与尝试，最终意义就是运行prover的门槛会越来越低。周期性来讲prover需要经历大致的如下三个阶段：
Phase I: Cloud-based prover
基于云的prover可以大大提高第三方prover（非用户/项目方）的准入门门槛，类似于web2的aws/google cloud。商业模式上来讲，项目方会流失一部分奖励，但是从去中心化的叙事讲这是一种经济以及执行层面吸引更多参与者的方式。而云计算/云服务是web2现有的技术栈，已有成熟的开发环境可供开发者使用，并且可以发挥云所特有的低门槛/高集群效应，对于短期内的proof outsource是一种选择。目前，Ingoyama也有在这一方面的实现（最新的F1版甚至达到了pipeMSM的基准速度的两倍）。但是，这依然是一个单个prover运行整个proof的方式，而在phase II中proof可以是一种可拆分的形式存在，参与者数量会更多。
Phase II: Prover marketplace
proof生成的过程中包含不同的运算，有的运算对于效率有偏好，有的运算则对成本/能源消耗有要求。比如MSM计算涉及pre-computation，这需要一定的memory支持不同的pre-computation上的标量颗粒，而如果所有的标量都存在一个计算机上的话对于该计算机的memory要求较高，而如果将不同的标量存储在多个服务器上，那么不仅该类的计算的速度会提高，并且参与者的数量也会增加。
Marketplace是一种针对上述外包计算的一种商业模式上的大胆的思考。但其实在Crypto圈子里也有先例 - Chainlink的预言机服务，不同链上的不同交易对的价格喂送也是以一种marketplace的形式存在。同时，Aleo的创始人Howard Wu曾经合作撰写过一篇DIZK，是一个分布式账本的零知识证明生成方法论，理论上是可行的。
话说回来，商业模式上讲这是一种非常有意思的思考，但是可能在实际落地时一些执行上的困难也是巨大的，比如这类运算之间如何协调生成完整的proof，至少需要在时间以及成本上不落后于Phase I。
Phase III: Everyone runs prover
未来Prover会运行在用户本地（网页端或者移动端），如Zprize有基于webassembly/andriod执行环境的ZKP加速相关的竞赛和奖励，意味着一定层面上用户的隐私会得到确保（目前的中心化prover只是为了扩容，并不保证用户隐私），最重要的上 - 这里的隐私不仅局限于链上行为，也包括链下行为。
一个必须要考虑的问题是关于网页端的安全性，网页端的执行环境相比硬件来说对于安全性的先决条件更高（一个industry witness是metmask这样的网页端钱包相比于硬件钱包，安全性更低）。
除了链上数据链下证明外，以ZKP的形式将链下数据上传到链上，同时百分百保护用户隐私，也只有在这个Phase可能成立。目前的解决方案都难免面临两个问题 - 1. 中心化，也就是说用户的信息依然有被审查的风险 2. 可验证的数据形式单一。因为链下数据形式多样且不规范化，可验证的数据形式需要经过大量的清洗/筛查，同时依旧形式单一。这里的挑战甚至不只是证明生成的环境，对于算法层面是否有能够兼容（首先必须使用transparent的算法），以及成本/时间/效率都是需要思考的。但是同样需求也是无与伦比的，想象可以以去中心化的方式抵押现实生活的信用在链上进行借贷，并且不会有被审查的风险。
