IOSG Weekly Brief ｜ 为什么零知识证明的Nova算法具备潜力？#191
The following article is from 星想法 Author Star Li
2023.09.04 - 09.10
Part.1 Insight
为什么零知识证明的Nova算法具备潜力？
Nova论文： https://eprint.iacr.org/2021/370.pdf Nova潜在攻击和相应修正： https://eprint.iacr.org/2023/969.pdf Nova潜在攻击的理解总结： https://www.zksecurity.xyz/blog/posts/nova-attack/
Nova算法是一种针对IVC（增量可验证计算，Incrementally Verifiable Computation）的新型的零知识证明算法。IVC，即同一个函数把前一个输出作为下一个输入迭代计算。F函数的迭代计算过程如下图：
z0是最初的输入，通过F函数计算生成的结果，作为下一个F函数的输入。
松弛R1CS以及松弛承诺R1CS
众所周知，R1CS是零知识证明技术中电路约束表示形式。松弛R1CS（Relaxed R1CS)可以看成是R1CS的扩展形式。在R1CS的基础上，增加一个标量u以及一个错误向量E。松弛R1CS的实例用(E, u, x)表示。
松弛承诺R1CS在松弛R1CS的基础上，将E以及W向量承诺。松弛承诺R1CS的实例用（\bar{E}, u, \bar{W}, x)表示，其中x和u是公开变量。
从R1CS扩展到松弛R1CS，是为了折叠方案。注意的是，从松弛R1CS的角度看，R1CS是其的一种特例。也就是说，R1CS也是一种“特别“的松弛R1CS。
折叠方案（Folding Scheme）
直觉上来说，一个关系R的折叠方案就是将两个符合关系R的实例“折叠成”一个新的复合关系R的实例。松弛R1CS/松弛承诺R1CS就能进行类似的折叠。两者的折叠过程类似。松弛承诺R1CS的折叠方案如下：
整个折叠方案由4步组成。第一步，证明者P发送一个交叉项T的承诺\bar{T}给验证者。第二步，验证者发送随机挑战r给证明者。第三步是证明者和验证者都需要执行的，承诺的折叠。第四步，证明者独自执行，将两个实例的E和W向量进行折叠。
增广函数F'（Argumented Function）
折叠方案，折叠的是松弛R1CS实例。那这些松弛R1CS实例证明的计算是什么？显然，这些计算要包括折叠的计算。这些计算不仅仅是IVC计算中的F函数了，也就被称为增广函数F‘。增广函数F’的计算主要由两部分组成：
1/ IVC中的F函数
2/ R1CS实例的折叠计算
理想中的样子
有了上述的这些理解，可以想象出折叠的过程：
其中，circuit就是增广函数F’对应的电路。acc{1,2,3,4,5,6}是松弛承诺R1CS实例。circuit有两个计算：1/松弛承诺R1CS实例的折叠，比如acc1+acc2->acc3。2/计算F函数，将状态state1变为state2，再从state2变为state3等等。
注意的是，增广函数F’对应的circuit，本身也是一个R1CS实例，其可以表示成松弛R1CS实例。也就是图中的acc4和acc6。“summarize”是将松弛R1CS实例转换为松弛承诺R1CS实例。
仔细观察第二个电路的输入，acc3是折叠后的松弛承诺R1CS实例，acc4是证明acc3是正确折叠结果的松弛承诺R1CS实例。这两个实例会进入下一次的折叠，生成acc5。你可以试想一下，如果acc3以及acc4是可满足的松弛承诺R1CS实例，意味着，acc3是由两个可满足的松弛承诺R1CS实例折叠而来，也就是说，acc1以及acc2是可满足的松弛承诺R1CS实例。这样的可靠性也就可以一步步“向”前推导，从而也证明了每一次circuit中的F函数计算是正确的。总的来说，就是通过某一个circuit对应的两个松弛承诺R1CS实例的可满足性，可以证明之前所有的IVC计算是正确的。
真实的样子
熟悉零知识证明的朋友，都知道多项式承诺方案中经常采用椭圆曲线。scalar域上对应的多项式的承诺是用椭圆曲线的base域表示。R1CS电路通常是采用scalar域来表示。仔细看，上图中的“summarize”的前后涉及到域的转换。也就是，要将circuit对应的松弛承诺R1CS实例进行折叠的话，必须在另外一个电路中去“折叠”。这时，需要引入椭圆曲线循环，两个或者多个椭圆曲线，其中一个曲线的scalar域，和另外一个曲线的base域相同，巧的是，该曲线的scalar域和之前曲线的base域相同。采用这样的椭圆曲线循环，可以将“理想中的样子”实现：
整个折叠过程，拆分成两个电路进行折叠。上部分可以称为Circuit 1的折叠，下部分可以称为Circuit 2的折叠。两个电路的关系的形式化表示在论文“Nova潜在攻击和相应修正”的第8页。U表示的是折叠后的实例，u表示的是一个R1CS实例对应的松弛实例。注意的是，Circuit 1折叠的是Circuit 2对应的松弛承诺R1CS实例，而Circuit 2折叠的才是Circuit 1对应的松弛承诺R1CS实例。Circuit 2的主要目的就是折叠Circuit1对应的松弛承诺R1CS实例，其电路中的函数计算没有意义。相反，F函数实现在Circuit 1中。结合“理想中的样子”，大致可以猜到U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1可满足性是证明的重要部分。
因为“电路”切割成两部分，并且各自的电路在另外的电路中进行折叠。存在几个实例之间的绑定问题：u和U实例之间的绑定以及u实例在两个电路之间传递的绑定。为了解决这些绑定问题，在电路中引入了x_0/x_1公开变量，其中x_1指定了和u实例绑定的电路输出U实例和当前的F函数的输出（为了简化电路结构，在图中未体现）。你想，在电路中引入了U实例的H_1结果的话，如果u实例是可满足的，x_0/x_1既是真实可靠的，即和U进行了“绑定”。x_0建立的是输入的u和U的绑定关系，x_1建立的是输出的u和U的绑定关系。
举个例子，u{i+1}^1作为下半部分电路的输入时，经过Circuit 2，其输出u{i+1}^2.x0 = u{i+1}^1.x1，这样，再输入到上半部分电路时，如果u{i+1}^2可满足的话，则其的x_0应该等于U_{i+1}^2的H1的结果。这在Circuit 1电路中会进行检查。这样，就保证了正确的实例，在两个电路之间传递。
IVC的证明
为了证明IVC在某个迭代正确计算，逻辑上需要证明如下信息：
除了证明四个实例可满足外，还需要证明两个x1的绑定关系，示意如下图：
这些信息是否正确，需要额外的证明电路实现。也就是说，IVC计算的证明是该电路的证明。可想而知，如果是很多次迭代的计算，原本需要将这些迭代一个个地在电路中展开，现在只需要对4个电路实例进行可满足性以及绑定关系的验证即可。性能提升非常大。
攻击以及算法修正
看到上面的图，有个直觉，怎么感觉上下电路的实例是“割裂“的，没有什么绑定性。事实上，攻击就是这样构造的。
伪造U_i^1和U{i+1}^2，虽然是伪造的，但是是可满足的实例。伪造u{i+1}^1，修改x_0和x_1和伪造的U实例对应。显然，u{i+1}^1实例不满足。虽然它不满足，但是Circuit 2的电路还是可以满足的，只是输出U{i+1}^1实例不满足而已。成功构造了u{i+1}^2的话，Circuit 1就可以构造出可满足的u{i+2}^1以及U_{i+2}^2，并且满足x1的绑定关系。这样就先构造出了最终伪造证明的一半内容。通过对称性，可以构造出下面一半的输出实例。通过两次构造的结果的“拼接”，可以伪造出IVC计算的证明。
修正后的检查逻辑如下：
“Nova潜在攻击和相应修正”论文的第6章给出了详细的安全性分析。感兴趣的小伙伴，可以自行查看原论文。
Nova的基本思想是通过折叠方案折叠电路实例。逻辑比较绕，需要仔细地思考电路折叠过程以及实现电路中的绑定关系。
Nova具备长期爆发潜力！
加密支付初创公司 Kotani 完成 200 万美元 Pre-Seed 轮融资
* 加密支付
据 TechCrunch 报道，加密支付初创公司 Kotani 完成 200 万美元 Pre-Seed 轮融资，P1 Ventures 领投，DCG/Luno、Flori Ventures 等参投，计划进一步将业务扩展到卢旺达、塞内加尔、科特迪瓦、坦桑尼亚和尼日利亚。
金融科技平台 GenTwo 完成 1500 万美元 A 轮融资，Point72 Ventures 领投
* 金融科技
据 CoinDesk 报道，金融科技平台 GenTwo 完成 1500 万美元 A 轮融资，Point72 Ventures 领投。本轮融资将于国际扩张并开发其金融工程平台。
聊天机器人服务提供商 Gleen 完成 490 万美元超额认购融资，Coinshares 等参投
* 聊天机器人
聊天机器人服务提供商 Gleen 完成 490 万美元超额认购融资，Slow Ventures、6th Man Ventures、South Park Commons、Spartan Group 和 Coinshares 等参投，天使投资人包括 Solana 联合创始人 Anatoly Yakovenko、Chainlink 前首席运营官 Mike Derezin、去中心化投资协议 Syndicate 联合创始人 Will Papper 与 ISM Angels。本轮资金将用于建设、推动销售与市场营销。
Web3 域名和 TLD 提供商 Freename 完成 250 万美元种子轮融资，Sparkle Ventures 领投
* Web3
Web3 域名和 TLD 提供商 Freename 宣布完成 250 万美元种子轮融资，Sparkle Ventures 领投，Blockchain Founders Fund、Golden Record Ventures、Abalone Asset Management 和 Sheikh Mayed Al Qasimi 参投。
链上 IP 协议 Story 完成 a16z 领投的 2500 万美元 A 轮融资，总融资额超 5400 万美元
*链上产权协议
链上知识产权协议 Story Protocol 宣布完成 2500 万美元 A 轮融资，a16z crypto 领投，加上今年 5 月完成的 2930 万美元融资，Story Protocol 的融资总额超过 5400 万美元，其他参投方包括 Hashed、Endeavor、Samsung Next、Foresight Ventures、Dao5、Insignia Venture Partners、Alliance DAO、Mirana Ventures 以及天使投资人 TPG Capital 创始人兼董事长 David Bonderman、Dapper Labs 创始人兼首席执行官 Roham Gharegozlou 等。
Web3 艺术初创公司 TRLab 完成 500 万美元融资
*Web3艺术初创公司
据 The Block 报道，Web3 艺术初创公司 TRLab 完成 500 万美元融资，Hivemind Capital Partners 和 OKX Ventures 领投，HashKey Capital 参投。本轮融资将用于吸引艺术家和文化机构参与数字艺术。TRLab 表示，TRLab 已与《Vogue》、Calder 基金会、蔡国强以及纽约新博物馆专注于数字艺术的附属机构 Rhizome 合作举办项目。
加密借贷公司 Trident Digital Group 完成 800 万美元种子轮融资
*加密借贷
加密借贷公司 Trident Digital Group 完成 800 万美元种子轮融资，White Star Capital 和 New Form 领投，CMT Digital、Joint Effects 和 Permit Ventures 参投，Trident 首席执行官 Anthony DeMartino 曾担任 Coinbase 风险策略主管，专注于 DeFi 和衍生品交易。后续 Trident 计划推出一款收益产品，将收益与无风险利率挂钩，同时确保以国债支持任何存款。
Socket Protocol 完成 500 万美元融资，Coinbase Ventures 等参投
*区块链互操作协议
据 CoinDesk 报道，区块链互操作协议 Socket Protocol 完成 500 万美元融资，Coinbase Ventures 与 Framework Ventures 参投。本轮融资将扩大 Socket 与 Coinbase 的合作，为 Coinbase Wallet 与 Base 开发者与用户提供桥梁机会。
Web3 游戏信息平台 GAM3S.GG 完成 200 万美元种子轮融资，Mechanism Capital 领投
*Web3游戏信息平台
Polkastarter Gaming 宣布正式更名为 GAM3S.GG，并完成了 200 万美元种子轮融资，Mechanism Capital 领投，Polygon、Double Peak、ArkStream Capital、LD Capital、ROK Capital、Hyperithm、Snackclub 和 Emurgo Ventures 等参投。
Web3 初创公司 Nestcoin 完成 190 万美元融资，将构建非托管加密钱包 Onboard
*加密钱包
总部位于尼日利亚的 Web3 初创公司 Nestcoin 宣布完成 190 万美元新一轮融资，Adaverse、Base Ecosystem Fund、Alter World、CMT Digital、Magic Fund、4DX Ventures 以及一批天使投资人参投。
Web3 初创公司 Helix 完成 200 万美元融资
*Web3
据 The Block 报道，新加坡私人信贷公司 Helicap 孵化的初创公司 Helix 完成 200 万美元融资，Saison Capital 和 Superscrypt 领投，参投方包括 Emurgo Ventures、Comma3 Ventures、Outlier Ventures、Emoote 等。Helix 旨在为东南亚各地的企业提供基于区块链的贷款，预计于今年第四季度在以太坊上推出。
Pop Social 完成 400 万美元种子轮和战略轮融资，Chainlink 等参投
*基础设施
Web3 AI 社交基础设施平台 Pop Social 完成 400 万美元种子轮和战略轮融资，Fundamental Labs、Ceras Ventures、Prysm Group、Chainlink、Cointelegraph、Fusion Labs、Promatrix Capital、以及 Binance 和 OKX 前高管团队的天使投资人等参投。
Part.3 IOSG投后项目进展
Part.3 IOSG投后项目进展
Arbitrum DAO已在 Snapshot 上开启赠款 Domain 分配者投票
* Layer2
Arbitrum DAO 已在 Snapshot 上开启赠款 Domain 分配者的提名投票，分配者角色将负责审查和寻找资助申请，主要涉及游戏、开发者工具、新协议理念、教育、社区发展和活动四个领域，投票将于 9 月 14 日结束，当前获得票数最高的 Arbitrum 社区提名者分别是：Jeremy（游戏）、Shreddy（教育、社区发展和活动）、Matt（StableLabs）（新协议理念）、以及 Hiko（开发者工具）。
zkSync已开启针对编号、时间戳和哈希值的主网升级计划
* Layer2
zkSync 宣布已于今日 18:00 对 block.number、block.timestamp 和 blockhash 在 zkSync Era 上的行为方式进行升级，升级后 block.number、block.timestamp 和 blockhash 将分别返回 L2 区块的编号、时间戳和哈希值。升级预计持续 40-60 天，在此期间出块率和时间戳刷新时间将逐渐增加。
Starknet核心堆栈已全部开源
* Layer2
以太坊二层扩容解决方案 Starknet 在 X 上表示其核心堆栈已全部开源，包括 Full Node、Execution Engine、Sequencer 和 Prover。
MetaMask推出 Sell 功能，允许将加密货币换成法币并汇入银行账户
* 钱包
MetaMask 发推称，已推出新功能 Sell，用户可使用该钱包将加密货币换成法币，并将资金汇入银行账户。目前，该功能仅在美国、英国与欧洲部分地区可用，最初支持以太坊主网上的 ETH，计划很快扩展至 Layer2 上的原生 Gas 代币。
LayerZero 已上线 Zora Network 主网，现可免费铸造纪念版 NFT LayerZero Zorb
* 基础设施/项目主网上线
LayerZero Labs 发推称，LayerZero 已在 Zora Network 主网上线，用户可以免费铸造纪念版 NFT LayerZero Zorb。同时，在 LayerZero 上构建的应用程序可扩展至 Zora Network，Zora Network 开发者也可与 LayerZero 网络其他部分集成。
dYdX 将于 9 月 11 日关闭测试网 2 并于 13 日启动测试网 3
* DeFi
dYdX 将于北京时间 9 月 11 日 23:00 关闭测试网 2，并于 9 月 13 日启动测试网 3。测试网 3 的更新包括条件订单、MEV 节点、延迟消息模块、支持使用治理代币支付 Gas 费等。
Coinbase、Circle 和 Aave 等联合发起代币化资产联盟
* DeFi
Coinbase、Circle 和 Aave 等联合发起代币化资产联盟（TAC），该联盟其它成员包括 Base、Centrifuge、Credix、Goldfinch、RWA.xyz 。该联盟认为 RWA 代币化是加密行业的未来，旨在帮助教育行业，倡导标准化和创新公司，并共同构建 RWA 采用所需基础设施。TAC 将于 9 月 19 日在纽约举行首届现实世界资产峰会。
韩国上市游戏发行商 Neowiz 将在 Avalanche 上开发游戏
* GameFi
据 CoinDesk 报道，韩国上市游戏发行商 Neowiz 将在 Avalanche 上开发游戏，计划通过其 Web3 部门 intela X 加入 Avalanche Arcad3，以推出区块链游戏。
Google 从 9 月 15 日起允许广告商使用广告服务来推广与赌博无关的 NFT 游戏
* NFT
Google 更新广告政策，表示自 9 月 15 日起，允许广告商使用广告服务来推广 NFT 游戏，但不能兜售与赌博相关的内容，其中允许玩家购买「增强」用户体验的游戏内资产（例如角色服装、武器和盔甲）的 NFT 游戏广告将符合 Google 的更新政策，但想要推广带有赌博成分的 NFT 游戏的公司将不会被允许这样做。
Osmosis 创始人：绝地求生开发商 KRAFTON 将推出一条基于 Cosmos 的 Settlus 链
* GameFi
Osmosis 创始人 Josh Lee 发推称，游戏《绝地求生》开发商 KRAFTON 将推出一条基于 Cosmos 的 Settlus 链，旨在为创作者提供透明的结算系统，测试网将于 2024 年初启动。
Coinbase 创始人提出第十一个「创业想法」，Web3 版本的 LinkedIn
* 其他
Coinbase 创始人 Brian Armstrong 发推表示，针对其此前提出的看好的加密领域 10 个创业想法，已经收到超过 150 份项目申请。Armstrong 宣称将添加第 11 个创业想法， Web3 版本的 LinkedIn，即通过公司发行的灵魂绑定 NFT 来验证就业或证书；建立一个前端平台来查验员工和雇主的档案资料；开发一种引导网络效应的方法，若用户可以验证来自公司的 .com 电子邮件等，可以让用户创建自己的网络效应。