迄今的故事
零常识证明(ZKP)关于去中心化体系的重要性日益增加。ZK最初是因为在ZCash等项目中大放异彩而走入公众视界的,但今日ZK是作为以太坊的一种扩容处理方案而为人们所熟知。
运用ZK,Layer 2(例如Scroll和Polygon)也被称为Rollups,正在开发zkEVMs(zk以太坊虚拟机)。这些zkEVMs处理一批买卖,并生成一个小型的证明(以KB为单位的巨细)。此证明能够用来向整个网络验证该批买卖都是有效且正确的。
但是,它们的用途并不止于此。ZK答应各种风趣的运用。
私有的Layer 1 - 例如Mina,它躲藏了其区块链上的买卖和数据的细节,答运用户仅证明其买卖的有效性,而无需泄漏买卖本身的详细信息。neptune.cash 和Aleo也是十分风趣的项目。
去中心化的云渠道 - FedML和together.xyz答应以去中心化的办法练习机器学习(ML)模型,将核算外包给网络,并运用ZKP验证核算的正确性。Druglike正在运用类似的技能构建一个愈加敞开的药物发现渠道。
去中心化存储 - Filecoin正在为云存储带来革命性的改变,而ZK正是其间心,答应存储供给商证明他们在一段时刻内存储了正确的数据。
游戏 - 更高档的Darkforest版别或许会出现,这需求实时证明。ZK或许还会扩展游戏,削减作弊的或许性。或许还能与去中心化的云渠道配合,使游戏能够付出自己的托管费用!
身份 - 现在也能够经过ZK完结去中心化的身份认证。环绕这个想法,正在建立许多风趣的项目。比如notebook和zkemail(推荐了解一下)。
ZK和去中心化体系的影响十分巨大,但是,故事的开展并非一无是处,现现在依然存在许多障碍和应战。包括生成证明的进程十分耗费资源,需求进行屡次杂乱的数学运算。跟着开发者们寻求运用ZK技能构建更为雄心壮志且杂乱的协议和体系,无论是关于证明的生成仍是验证进程,开发者们会要求更小的证明巨细、更快的功能和更好的优化。
在本文中,咱们将讨论硬件加快的现状,以及它将如安在推动ZK运用方面发挥要害作用。
Snark vs Stark
现在有两种盛行的零常识技能,即zk-STARK和zk-SNARK(在本文中咱们疏忽了Bulletproofs)。
zk-STARK | zk-SNARK | |
Complexity - Prover | O(N * poly-log(N)) | O(N * log(N)) |
Complexity - Verifier | O(poly-log(N)) | O(1) |
Proof size | 45KB-200KB | ~ 288 Bytes |
抗量子 | Yes (hash function based) | No |
Trusted setup | No | Yes |
Zero Knowledge | Yes | Yes |
Interactivity |
Interactive or |
Non interactive |
开发者文档 | 有限,但正在扩展 | 良好 |
表1:Snark VS Stark
如上所述,两者之间存在不同之处和权衡。最重要的一点是,依据zk-SNARK的体系的可信设置依赖于至少有一个诚实的参与者参与了可信设置进程并在进程完毕后销毁了他们的密钥。在链上验证方面,zk-SNARK在gas费方面要廉价得多。此外zk-SNARK的证明也显着更小,使其在链上存储更为廉价。
现在,zk-SNARKs比zk-STARKs更受欢迎。最或许的原因是zk-SNARKs的前史更为悠长。另一个或许的原因是Zcash——最早的ZK区块链之一运用了zk-SNARKs,因而现在大多数开发工具和文档都环绕zk-SNARK生态体系展开。
How to build a ZK Application
开发人员或许需求两个组件来完结ZK运用的开发
一种 ZK-friendly 表达核算的办法(DSL或底层库)。
一个证明体系,该体系应完结两个功能:Prove(证明)和Verify(验证)。
DSLs (domain-specific language) 和 底层库
在DSL方面,挑选十分多,例如Circom、Halo2、Noir等等。现在Circom或许是最受欢迎的。
在底层库方面,一个盛行的例子是Arkworks;还有一些正在开发中的库,如ICICLE,它是一个CUDA加快库。
这些DSL被规划用来输出束缚体系。与一般的程序不同(一般以x := y * z的方式进行求值),在束缚方式中的相同程序看起来更像x - y * z = 0。经过将程序表明为束缚体系,咱们发现比如加法或乘法之类的操作能够用单个束缚来表明。但是,更杂乱的操作,如位操作,或许需求数百个束缚!
因而,将某些哈希函数完结为ZK友爱程序变得杂乱。在零常识证明中,哈希函数一般用于确保数据的完好性和/或验证数据的特定特点,但因为位操作的束缚数量较多,使得某些哈希函数难以适应零常识证明的环境。这种杂乱性或许会影响到证明生成和验证的功率,然后成为开发者在构建依据ZK的运用时需求考虑和处理的问题
因而,将某些哈希函数完结为ZK友爱的,就会变得杂乱。
Proving System
能够将证明体系类比为一种软件,首要完结两项使命:生成证明和验证证明。证明体系一般接受电路、依据和公共/私有参数作为输入。
两个最盛行的证明体系是Groth16和PLONK系列(Plonk,HyperPlonk, UltraPlonk)
Trusted Setup | Proof size |
Prover |
Verifier 杂乱度 | 灵活性 | |
Groth16 | Circuit specific | small | Low | Low | Low |
Plonk | Universal | Large | High | 常数 | High |
表2:Groth16 vs Plonk
如表2所示Groth16需求一个可信设置进程,但Groth16为咱们供给了更快的证明和验证时刻,以及恒定的证明巨细。
Plonk供给了一个通用的设置,每次生成证明时,都会为你运转的电路履行一个预处理阶段。虽然支持许多电路,Plonk的验证时刻是恒定的。
在束缚方面,两者也存在差异。Groth16的束缚巨细呈线性增加,缺乏灵活性,而Plonk则愈加灵活。
总的来说,要了解功能直接与你的ZK运用程序的束缚数量相关。束缚越多,证明者有必要核算的操作就越多。
瓶颈
证明体系包括两个首要的数学运算:多标量乘法(MSM)和快速傅里叶改换(FFT)。今日咱们将讨论两者都存在的体系,在这样的体系中,MSM或许占用约60%的运转时刻,而FFT占用约30%。
MSM需求很多的内存拜访,这在大多数状况下会耗费机器的很多内存,一起还要履行许多标量乘法运算。
FFT算法一般需求将输入数据从头排列成特定次序以履行改换。这或许需求很多的数据移动,并或许成为瓶颈,特别是关于大的输入巨细。如果内存拜访模式不适合缓存层次结构,缓存运用率也或许成为问题。
在这种状况下,硬件加快是全面优化ZKP功能的必由之路。
硬件加快
谈起硬件加快,这让人回想起ASICs和GPUs是怎么主宰比特币和以太坊的挖矿。
虽然软件优化相同十分重要且有价值,但它们有其局限性。而硬件优化能够经过规划带有多个处理单元的FPGAs来进步并行性,例如削减线程同步或向量化。经过改善内存层次结构和拜访模式,内存拜访也能更有效地得到优化。
现在在ZKP领域,首要趋势似乎转向了:GPU和FPGA。
短期内,GPU在价格上具有优势,特别是在ETH转向权益证明(POS)后,使得很多的GPU矿机闲置,处于待命状况。此外GPU还具有开发周期短的长处,并为开发者供给很多”即插即用“的并行性。
但是,FPGA应在迎头追赶,特别是在比较外形尺寸和功耗时。FPGA也为高速数据流供给了更低的推迟。当多个FPGAs集合在一起时,它们与GPU集群比较供给了更好的功能。
GPU VS FPGA
GPU:
开发时刻:GPU供给了快速的开发时刻。像CUDA和OpenCL这样的框架开发者文档完善且受欢迎。
功耗:GPU十分“耗电”。即使开发者在运用数据级并行性和线程级并行性时,GPU依然耗费很多的电力。
可用性:现在消费级的GPU价格廉价且简单取得。
FPGA:
开发周期:FPGA有一个更杂乱的开发周期,并需求更专业的工程师。FPGAs答应工程师完结许多GPU无法完结的“底层”优化。
推迟:FPGAs特别是在处理大数据流时供给了较低的推迟。
成本与可用性:FPGA比GPU更贵重,并且不如GPU那样简单取得。
ZPRIZE
现在提到硬件优化与ZKP的瓶颈,那就绕不开一个比赛-ZPRIZE
ZPrize是当时ZK领域中最重要的行动之一。ZPrize是一个比赛,鼓舞团队为ZKP的要害瓶颈(如MSM、NTT、Poseidon等)在多种渠道(如FPGA、GPU、移动设备和浏览器)上开发硬件加快,评判标准为推迟、吞吐量和功率。
成果十分风趣。例如,GPU的改善十分巨大:
degree为2^26下的MSM从5.86秒进步到2.52秒,进步了131%。另一方面,与GPU的成果比较,FPGA处理方案往往没有任何基准测验,GPU成果有先前的基准测验可供比较,而大多数FPGA处理方案都是首次开源这样的算法,预计未来会有所改善。
这些成果表明了大多数开发者在开发他们的硬件加快处理方案时所感到舒适的方向。许多团队为GPU类别竞赛,但只要很少一部分团队为FPGA类别竞赛。我不确定这是因为在为FPGA开发时缺乏经验,仍是大部分FPGA公司/团队挑选隐秘开发以商业化出售他们的处理方案。
ZPrize向社区供给了一些十分风趣的研究成果。跟着ZPrize更多轮次的开始,咱们将看到越来越多风趣的处理方案和问题的出现。
硬件加快的实际例子
以Groth16为例,如果咱们查看rapidsnark对Groth16的完结,能够观察到首要履行了两个操作:FFT(快速傅立叶改换)和MSM(多标量乘法);这两种基本运算在许多证明体系中都是常见的。它们的履行时刻直接与电路的束缚数量相关。自然地,跟着编写更杂乱的电路,束缚的数量会增加。
为了直观地了解与感受FFT与MSM操作到底占据了多大的核算量,咱们能够查看Ingonyama对Groth16电路(在32GB扇区上履行的Filecoin的Vanilla C2进程)进行的基准测验,成果如下
如上图所示,关于许多证明者来说,MSM(多标量乘法)或许会占用很多的运转时刻,并成为一个严峻的功能瓶颈,这就使得MSM成为需求加快的重要密码学算子之一。
那么MSM在其他ZK证明体系中又会占据证明者多少的核算量呢?如下图所示
在Plonk中,MSM的开支占比来到了85%以上,图片来自Ingonyama最新论文Pipe MSM。
所以硬件加快应当怎么加快MSM?
MSM
在谈怎么加快MSM之前,咱们需求了解什么是MSM
多标量乘法(MSM, Multi-Scalar Multiplication)是一种用于核算多个标量乘法之和的算法,方式如下
其间G是椭圆曲线群中一点,a是标量,MSM的成果也会是一个椭圆曲线点
咱们能够将MSM分解为两个首要的子组件:
模乘法(Modular Multiplication)
椭圆曲线点加法(Elliptic Curve Point Addition)
咱们以Affine(x,y)类型的点为例,进行朴素的P+Q运算。
当咱们想要核算P + Q=R时,咱们需求核算一个值k,经过k与P,Q的横坐标然后
取得R的坐标.核算进程如上,在这个进程里边咱们进行了2次乘法,1次平方,1次求逆运算,以及若干次加法 减法运算。值得注意的是,上述运算都是在有限域傍边进行的,也就是mod P下的运算。实际傍边,P会十分的大。
上述运算的开支为 求逆>>乘法 >平方,加减法的开支可疏忽。
所以咱们期望尽量避免求逆运算,因为一次求逆的开支至少是乘法的百倍。经过拓宽坐标系咱们就能够做到这一点,但是代价是进程的乘法数量会相应增加一些,如 Jacobian坐标: XYZ += XYZ,乘法会增加到10次以上,详细取决于加法算法。
GPU VS FPGA 加快MSM
本节将比较两个抢先的MSM完结,PipeMSM和Sppark,其间PipeMSM在FPGA上完结,而Sppark在GPU上完结。
Sppark和PipeMSM运用最先进的Pippenger算法 完结MSM,也被称为bucket算法;
Sppark运用CUDA完结;它们的版别具有高度的并行性,并在最新的GPU上运转时取得了令人印象深刻的成果。
但是,PipeMSM不仅优化了算法,还为模数乘法(Modular Multiplication)和椭圆曲线点加法(EC Addition)的数学基元供给了优化。PipeMSM处理了整个“MSM堆栈”,完结了一系列的数学技巧和优化,旨在使MSM更适合硬件,并规划了一种旨在下降推迟以及重点关注并行化的硬件规划。
下面让咱们快速回顾一下PipeMSM的完结。
低推迟
PipeMSM旨在在对很多输入履行多个MSM时供给低推迟。因为动态频率缩放的原因,GPU不能供给确定性的低推迟,GPU会依据工作负载调整其时钟速度。
但是因为优化的硬件规划,FPGA完结能够为特定工作负载供给确定的功能和推迟。
EC加法完结
椭圆曲线点加法(EC Addition)被完结为低推迟、高度并行且完好的公式(完好意味着它正确核算了椭圆曲线群中任何两点的和). 椭圆曲线点加法在EC加法模块中以流水线办法运用,以削减推迟。
咱们挑选将坐标表明为射影坐标,在加法算法上咱们运用一个Complete椭圆曲线点加法公式。首要长处是咱们不用处理边际状况。完好的公式;
咱们以流水线和并行的办法完结了这个加法公式,咱们的FPGA椭圆曲线加法器电路只需12次乘法、17次加法和就能履行这个公式。而原始公式需求15次模乘法、13次加法。FPGA规划如下
模乘完结(multi mod)
咱们运用了Barrett Reduction和 Karatsuba 算法。
Barrett Reduction是一种有效核算 r≡ab mod p (其间 p 是固定的)的算法。Barrett Reduction企图经过近似除法来替换除法(一种贵重的操作)。能够挑选一个差错容限来描述咱们寻找正确成果的范围。咱们发现,较大的差错容限答应运用较小的约化常数;这减小了模约化操作中运用的中心值的巨细,然后削减了核算最终成果所需的乘法次数。
在下面的蓝色方框中,咱们能够看到,因为咱们的高差错容限,咱们有必要进行屡次查看以找到准确的成果。
简而言之,Karatsuba算法用于优化咱们在Barrett Reduction中履行的乘法。Karatsuba算法将两个n位数的乘法简化为三个n/2位数的乘法;这些乘法能够将位数简化到满足窄,直到能够直接由硬件核算。细节能够阅览Ingo的paper:Pipe MSM
运用上述算子,咱们开发了一个低推迟、高度并行的MSM完结。
中心思想是:不是一次核算整个MSM,而是并行地将每个chunk传递到EC加法器中。EC加法器的成果累积到最终的MSM中。
最终成果
上图展现了Sppark和PipeMSM之间的比较。
最突出的是FPGA供给的明显节能作用,关于未来大规模证明生成操作来说,这或许极为重要。值得注意的是,咱们的完结是在@125MHz下进行原型规划和基准测验的,将时钟速度进步到@500MHz或许会将核算时刻进步4倍或更多。
运用咱们的FPGA的另一个优势是,因为它们耗费的能量较少,产生的热量也较少,因而能够将它们安装在小型机箱服务器中。
咱们正处于用于ZKP的FPGA工程的初期阶段,应该期待算法的进一步改善。此外,FPGA在核算MSM的时分,CPU正处于闲暇状况,经过将FPGA与体系资源(CPU/GPU)结合运用,或许能够完结更快的时刻。
总结
ZKP已成为分布式体系的要害技能。
ZKP的运用将远远超越仅仅扩展以太坊这个层面,而是答应将核算外包给不受信赖的第三方,答应开发以前不或许的体系,例如分布式云核算、身份体系等等。
传统上,ZKP的优化首要会集在软件等级的改善上,但跟着对更卓越功能的需求增加,咱们将看到更多触及硬件和软件的先进加快处理方案。
现在咱们首要看到的加快方案运用的是GPU,这是因为运用CUDA的开发时刻短,并且现在消费级GPU十分廉价且丰厚。GPU还供给了令人难以置信的功能。所以GPU不太或许在短期内从这个领域消失。
跟着更多杂乱的开发团队进入该领域,咱们很或许会看到FPGA在功耗功率和功能方面处于抢先地位。与GPU比较,FPGA供给了更多底层定制以及更多装备选项。与ASIC比较,FPGA具有更快的开发速度和灵活性。跟着ZKP国际的快速开展,FPGA能够运用不同的程序从头刷写以适应不同的体系和更新处理方案。
但是,要生成挨近实时的证明,或许需求依据咱们为其生成证明的体系,将GPU/FPGA/ASIC装备组合在一起。
ZPU也或许会开展,为大规模证明生成器和低功耗设备供给极为高效的处理方案(详情见之前的文章)。
此时快讯
【以太坊L2 TVL上升至118.6亿美元,7日涨幅10.86%】金色财经报道,据L2BEAT数据显示,当前以太坊Layer2总锁仓量(TVL)暂报118.6亿美元,7日涨幅达10.86%。
其中,锁仓量前五分别为:Arbitrum One(65.4亿美元,7日涨幅11.76%);OP Mainnet(29.7亿美元,7日涨幅12.09%);Base(5.73亿美元,7日涨幅3.97%);zkSync Era(4.47亿美元,7日涨幅3.69%);dYdX(3.52亿美元,7日涨幅64.726%)。