IOSG Weekly Brief ｜零知识证明 - FPGA vs GPU #177
2023.05.29 - 06.02
Part.1 Insight
零知识证明 - FPGA vs. GPU
作者：Star Li
本文仅做行业学习交流之用，不构成任何投资参考。如需引用，请注明来源，转载请联系 IOSG 团队获取授权及转载须知。特别感谢作者 Star Li 提供的内容！零知识证明技术应用越来越广，隐私证明，计算证明，共识证明等等。在寻找更多更好的应用场景的同时，很多人逐步发现零知识证明证明性能是个瓶颈。Trapdoor Tech 团队从 2019 年开始深入研究零知识证明技术，并一直探索高效的零知识证明加速方案。GPU 或者 FPGA 是目前市面上比较常见的加速平台。本文从 MSM 的计算入手，分析 FPGA 和 GPU加速零知识证明计算的优缺点。
TL;DR
ZKP是拥有未来广泛前景的技术。越来越多的应用开始采用零知识证明技术。但ZKP算法比较多，各种项目使用不同的ZKP算法。同时，ZKP证明的计算性能比较差。本文详细分析了MSM算法，椭圆曲线点加算法，蒙哥马利乘法算法等等，并对比了GPU和FPGA在BLS12_381曲线点加的性能差别。总的来说，在ZKP证明计算方面，短期GPU优势比较明显，Throughput高，性价比高，具有可编程性等等。FPGA相对来说，功耗有一定的优势。长期看，有可能出现适合ZKP计算的FPGA芯片，也可能为ZKP定制的ASIC芯片。
ZKP 算法复杂
ZKP是个零知识证明技术的统称（Zero Knowledge Proof）。主要由两种分类：zk-SNARK以及zk-STARK。zk-SNARK目前常见的算法是Groth16，PLONK，PLOOKUP，Marlin和Halo/Halo2。zk-SNARK算法的迭代主要是沿着两条方向：1/是否需要trusted setup 2/电路结构的性能。zk-STARK算法的优势是毋需trusted setup，但是验证计算量是对数线性的。
就zk-SNARK/zk-STARK算法的应用来看，不同项目使用的零知识证明算法相对分散。zk-SNARK算法应用中，因为PLONK/Halo2算法是universal（无需trusted setup），应用可能越来越多。
PLONK 证明计算量
以PLONK算法为例，剖析一下PLONK证明的计算量。
PLONK证明部分的计算量由四部分组成：
1/ MSM - Multiple Scalar Multiplication。MSM经常用来计算多项式承诺。
2/ NTT计算 - 多项式在点值和系数表示之间变换。
3/ Polynomial计算 - 多项式加减乘除。多项式求值（Evaluation）等等。
4/ Circuit Synthesize - 电路综合。这部分的计算和电路的规模/复杂度有关。
Circuit Synthesize部分的计算量一般来说判断和循环逻辑比较多，并行度比较低，更适合CPU计算。通常来讲，零知识证明加速一般指的是前三部分的计算加速。其中，MSM的计算量相对来说最大，NTT次之。
What's MSM
MSM（Multiple Scalar Multiplication）指的是给定一系列的椭圆曲线上的点和标量，计算出这些点加的结果对应的点。
比如说，给定一个椭圆曲线上的一系列的点：
Given a fixed set of Elliptic curve points from one specified curve:
[G_1, G_2, G_3, ..., G_n]
以及随机的系数：
and a randomly sampled finite field elements from specified scalar field:
[s_1, s_2, s_3, ..., s_n]
MSM is the calculation to get the Elliptic curve point Q:
Q = \sum_{i=1}^{n}s_i*G_i
行业普遍采用Pippenger算法对MSM计算进行优化。深入看看Pippenger算法的过程的示意图：
Pippenger算法的计算过程分成两步：
1/ Scalar切分为Windows。如果Scalar是256bits，并且一个Window是8bits，则所有的Scalar切分为256/8=32个Window。每一层的Window，采用一个“Buckets”临时存放中间结果。GW_x就是一层上的累加结果的点。计算GW_x也比较简单，依次遍历一层中的每个Scalar，根据Scalar这层的值作为Index，将对应的 G_x加到相应的Buckets的位上。其实原理也比较简单，如果两个点加的系数相同，则先将两个点相加后再做一次Scalar加，而不需要两个点做两次Scalar加后再累加。
2/ 每个Window计算出来的点，再通过double-add的方式进行累加，从而得到最后的结果。
Pippenger算法也有很多变形优化算法。不管怎么说，MSM算法的底层计算就是椭圆曲线上的点加。不同的优化算法，对应不同的点加个数。
椭圆曲线点加（Point Add）
你可以从这个网站看看具有“short Weierstrass”形式的椭圆曲线上点加的各种算法。
http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
假设两个点的Projective坐标分别为（x1, y1, z1) 和 （x2, y2, z2) ，则通过如下的计算公式可以计算出点加的结果(x3, y3, z3)。
详细给出计算过程的原因是想表明整个计算过程绝大部分是整数运算。整数的位宽取决于椭圆曲线的参数。给出一些常见的椭圆曲线的位宽：
BN256 - 256bits
BLS12_381 - 381bits
BLS12_377 - 377bits
特别注意的是，这些整数运算是在模域上的运算。模加/模减相对来说简单，重点看看模乘的原理和实现。
模乘（Modular Muliplication）
给定模域上的两个值：x和y。模乘计算指的是 x*y mod p。注意这些整数的位宽是椭圆曲线的位宽。模乘的经典算法是蒙哥马利乘法（Montgomery Muliplication)。在进行蒙哥马利乘法之前，被乘数需要转化为蒙哥马利表示：
蒙哥马利乘法计算公式如下：
蒙哥马利乘法实现算法又有很多：CIOS (Coarsely Integrated Operand Scanning)，FIOS（Finely Integrated Operand Scanning），以及 FIPS（Finely Integrated Product Scanning）等等。本文不深入介绍各种算法实现的细节，感兴趣的读者可以自行研究。
为了对比FPGA以及GPU的本身的性能差别，选择最基本的算法实现方法：
简单的说，模乘算法可以进一步分成两种计算：大数乘法和大数加法。理解了MSM的计算逻辑的基础上，可以选择模乘的性能（Throughput）来对比FPGA和GPU的性能。
观察和思考
在这样的FPGA设计下，可以估算出整个VU9P能提供的在BLS12_381椭圆曲线点加Throughput。一个点加（add_mix方式）大约需要12个模乘。FPGA的系统时钟为450M。
在同样的模乘/模加算法下，采用同样的点加算法，Nvidia 3090的点加Troughput（考虑到数据传输因素）超过500M/s。当然，整个计算涉及到多种算法，可能存在某些算法适合FPGA，有些算法适合GPU。采用一样的算法对比的原因，想对比FPGA和GPU的核心计算能力。
基于上述的结果，总结一下GPU和FPGA在ZKP证明性能方面的比较：
总结
越来越多的应用开始采用零知识证明技术。但ZKP算法比较多，各种项目使用不同的ZKP算法。从我们的实践工程经验来看，FPGA是个选项，但是目前GPU是个性价比高选项。FPGA偏好确定性计算，有latency以及功耗的优势。GPU可编程性高，有相对成熟的高性能计算的框架，开发迭代周期短，偏好需要throughput场景。
Transak 完成 2000 万美元 A 轮融资，CE Innovation Capital 领投
* 基础设施
据 Tech Funding News 报道， Web3 支付和法币聚合器 Transak 完成 2000 万美元 A 轮融资， CE Innovation Capital 领投，参投方包括 IOSG Ventures、SBI Ven Capital、Sygnum、Azimut、Third Kind Venture Capital、UOB Venture Management、Signum Capital、Animoca Brands、Genting Ventures、Istari Ventures、No Limit Holdings、Woodstock Fund、KX、Axelar、Tokentus 和 The Lao，以及天使投资人 Jan Hammer（Index Ventures）、Charles Delingpole（ComplyAdvantage）和 Sandeep Nailwal（Polygon）。
Web3 分发平台 MetaZone 完成 300 万美元融资
* Web3
Web3 数字内容和应用分发平台 MetaZone 宣布完成 300 万美元种子轮融资，专注于元宇宙领域投资的两家机构 Sfermion 和 CMT Digital 共同领投， IOSG Ventures、Tess Ventures、IVC (Infinity Ventures Crypto)、Polygon Studios、MHC Digital 和 LucidBlue Ventures 参投。
zkMe 完成 200 万美元融资
* 基础设施
零知识身份预言机 zkMe 完成 200 万美元 Pre-Seed 轮融资，Circle Venture、Spartan Group、CMS Holdings、Fenbushi Capital、NGC Ventures、Arkstream Capital 等参投，计划利用新资金加速开发，在一个月内完成主网测试并上线客户注册功能。
TomoChain 获得 Coin98 投资，将集成 Coin98 Wallet 作为官方钱包
* 基础设施
可扩展区块链 TomoChain 宣布获得了来自 Coin98 Labs 的投资，具体投资金额未披露，TomoChain 将使用新资金加强其基础设施、创新技术，并为将在其网络上开发的 DApp 的涌入做好准备。接下来 Coin98 Wallet 将作为官方钱包集成到 TomoChain 中。
zkEVM Kakarot 完成 Pre-Seed 轮融资
* 基础设施
基于 CairoVM 构建的模块化 zkEVM Kakarot 发推称，已完成 Pre-Seed 轮融资，具体融资金额未知，Vitalik Buterin、StarkWare、Node Guardians 联创兼 CEO Sam Benyakoub、LambdaClass、Zama CEO Rand Hindi、Starknet 联创 Fricoben、FuzzingLabs 等参投。
zkPass 获得 Binance Labs 的投资
* 基础设施
币安公布其 BuildTheBlock 总决赛活动的获胜者为 zkPass，同时，zkPass 将获得来自 Binance Labs 的投资。zkPass 正在开发一个开源协议，允许用户使用 MPC、ZKP 和 TLS 在 HTTPS 站点上证明私人数据，确保隐私，同时保持数据真实性、完整性和有效性。zkPass 此前入选币安孵化器第五季孵化计划的 12 个项目之一。
Demox Labs 完成 4500 万美元融资，HackVC 领投
* 基础设施
加密钱包开发平台 Demox Labs 完成 450 万美元融资， HackVC 领投。Demox Labs 将支持面向隐私区块链 Aleo 的各种产品的开发。Demox Labs 首个产品为隐私保护钱包 Leo Wallet。
DeFi 协议获得 Albus Protocol 获得 Solana 基金会资助
* DeFi
DeFi 协议 Albus Protocol 宣布已获得 Solana 基金会资助，具体金额暂未对外披露。Albus Protocol 旨在帮助 DeFi 协议在公共区块链上运行时遵守 KYC（了解你的客户）、AML（反洗钱）、GDPR（通用数据保护条例）、以及 CBDC（央行数字货币） 法规，新资金将推动该协议加速建立工具以构建基于零知识证明的合规公共区块链 DeFi 框架，具预计将在 8 月上线具有完整用户界面的 Web3 工具。
Prisma Finance 完成融资，Curve 创始人等参投
* DeFi
LSD 稳定币协议 Prisma Finance 完成一轮融资，具体金额未披露，Curve Finance 创始人 Michael Egorov、Convex Finance 创始人 C2tP、FRAX Finance、Conic Finance、Tetranode、Llama Airforce、CoinGecko 创始人、OKX Ventures、DeFiDad、MrBlock、Impossible Finance、0xMaki、GBV、Agnostic Fund、Swell Network 创始人、The Block 的 Eden 研究总监 Adam Cochran、Ankr Founders、MCEG、Eric Chen 等参投。
Web3 游戏公司 Fusionist 完成 660 万美元种子轮投资资
* GameFi
Binance Labs 于 2022 年 5 月与 Web2 游戏巨头 FunPlus 共同领投对 Web3 游戏公司 Fusionist 的 660 万美元种子轮投资，融资资金用于继续加快游戏的开发，并建立 2023 年 1 月推出的 Endurance 主网生态系统。此外 Fusionist 还计划加强用户增长，并招募顶级的游戏和 Web3 专业人士，以进一步加强其团队的能力。
DeGame 完成 650 万美元融资，并推出 Web3 贡献证明平台
* GameFi
链游发行平台 DeGame 宣布完成第二轮 650 万美元融资，此轮融资由 Folius Ventures、Kenetic Capital、A&T Capital 领投， NGC Ventures、Hack VC、Hashkey Capital、Avalanche、 Golden Bull、 Y2Z Ventures、Collingstar Capital、Sfermion、Bixin Ventures、Assembly Partners、FBG Capital、Lucid Blue、Ranger Protocol 等参投。
Illuvium 完成 1000 万美元融资，Framework Ventures 参投
* GameFi
RPG 链游 Illuvium 联合创始人 Kieran Warwick 在 Discord 社区中发布声明称，已从 Framework Ventures 额外筹集 1000 万美元资金。所筹资金将加速 Illuvium 游戏开发。这笔交易系通过代币完成，将锁仓两年，不列入质押，因此不会参与利益分配。
Hogwarts Labs 完成 Pre-A 轮融资， Hash Global 和经纬创投等领投
* Web3
聚焦 Web3+AI 的 DApps 研发公司 Hogwarts Labs 宣布完成 Pre-A 轮融资，累计融资 800 万美元，Hash Global、经纬创投、XIN Family 和 DHVC 领投，SevenX、Alliance、SKY9、NGC Ventures、EVG、No Limit Holdings、Stratified Capital、Old Fashion Research、North Beta Capital 和 Puzzle Ventures 等参投，其第二款服务 Web3 用户的 AI 助理产品将不早于今年第四季度发布。
Part.3 IOSG投后项目进展
Part.3 IOSG投后项目进展
zkSync：已完成 zkSync Era 网络优化升级
* ZK-Rollup
zkSync 表示，已完成针对 zkSync Era 网络的优化升级，系统按预期正常工作。昨日，zkSync 称 zkSync Era 网络的优化可能会导致短暂停机，交易仍然可以提交，但可能会遇到区块生成方面的小延迟。
StarkNet 主网已升级至 V0.11.2，正式激活 Cairo 1
* Layer 2
以太坊 Layer2 扩容解决方案 Starknet 主网已升级至 v0.11.2，正式激活 Cairo 1，开发者可在主网上部署 Cairo 1 智能合约，接下来 Starknet 主网将发布关于更高 TPS 的重大更新。
链游 Illuvium 完成 1000 万美元融资
* GameFi
RPG 链游 Illuvium 联合创始人 Kieran Warwick 在 Discord 社区中发布声明称，已从 Framework Ventures 额外筹集 1000 万美元资金。所筹资金将加速 Illuvium 游戏开发。这笔交易系通过代币完成，将锁仓两年，不列入质押，因此不会参与利益分配。
DefiLlama 的 ChatGPT 插件将进行 Beta 测试，允许通过语言提示查询数据
* DeFi 数据
DefiLlama 创始人 0xngmi 发推表示，DefiLlama 的 ChatGPT 插件将进行 Beta 测试，如果用户在 ChatGPT 上具有插件访问权限，并愿意就插件提供反馈，可以加入等待名单。它将允许用户通过语言提示查询 DefiLlama 的数据，包括询问「3 月后哪些 LSD 项目增长最快？」等与数据相关的问题。
Sui 成为甲骨文红牛车队的官方区块链合作伙伴
* 公链
Sui 宣布与一级方程式车队甲骨文红牛车队（Oracle Red Bull Racing）达成合作，成为甲骨文红牛车队的官方区块链合作伙伴。Sui 表示，将在接下来的几个月打造全球粉丝都能享受的身临其境的数字体验。
Circle 将于 6 月 8 日在 Arbitrum 推出原生 USDC
* DeFi
Circle 将于 2023 年 6 月 8 日开始在 Arbitrum 推出原生 USDC，Arbitrum 称该代币将成为 Arbitrum 生态系统内认可的 USDC 官方版本，并将最终取代目前流通的来自以太坊的 USDC 桥接版本。Arbitrum 宣布在 6 月 8 日原生 USDC 推出之前，Arbitrum 将在区块浏览器上将 USDC 的以太坊桥接版本重命名为「USDC.e」。
以太坊基金会开放 Fellowship 计划第四批申请，申请开放至 6 月 16 日
* 以太坊基金会
以太坊基金会宣布第四批以太坊协议奖学金（EPF）申请正式开放，用户可在 6 月 16 日前提交申请，该计划为研究员提供为期四个月的奖学金，以推进以太坊技术，包括从开发客户端实现、测试和规范，到参与最新的核心协议研究。第四批 EPF 从 2023 年 7 月持续到 2023 年 11 月，最后在伊斯坦布尔的 Devconnect 举行现场活动。
zkSync：zkSync Era 网络优化可能会导致今日短暂停机，交易仍可提交
* ZK-Rollup
zkSync 发推称，zkSync Era 网络的优化可能会导致今日短暂停机，交易仍然可以提交，但可能会遇到区块生成方面的小延迟，预计不会产生其他影响。zkSync 将在网络优化完成后分享更新。
Swell Network 已上线 Voyage 空投活动，并将分配 5000 万枚 SWELL
* DeFi 协议
以太坊质押协议 Swell Network 已上线 Voyage 空投计划，并将分配 5000 万枚 SWELL（5%），用户现在可通过抵押 swETH 和提供流动性来收集珍珠（pearls），然后在今年晚些时候的代币生成活动（Token Generation Event，TGE）上兑换成 SWELL。
Curve 发起支持 wstETH 抵押铸造 crvUSD 的社区投票，债务上限 1.5 亿 crvUSD
* DeFi
Curve 发起 #416 号社区投票，拟部署 1.5 亿 crvUSD 债务上限的 wstETH 市场，并将 PegKeepers 的限制提高到每个 2500 万 crvUSD。
dYdX：将推出多平台应用程序并开源前端代码库和相关部署脚本
* DeFi 协议
去中心化永续合约协议 dYdX 发文介绍 v4 架构和前端如何工作，称其 Web 前端为不希望以编程方式与 v4 交互的交易者提供直观 UI/UX，其正在构建三个前端：一个 Web 应用程序、一个 iOS 应用程序和一个 Android 应用程序，此外还将为高级用户 / 机构提供 Typescript 和 Python SDK。dYdX 表示，将开源所有前端代码库和相关部署脚本，允许任何人通过自己的域 / 托管解决方案轻松部署 dYdX 前端。