零知识证明 – 说说Nova
前段时间在翻译一本零知识证明技术的书。上个月底基本内容已经翻译完成。翻译时间比我预想的长得多。目前正在和作者讨论书中的一些笔误,准备最后的定稿。
anyway,终于有点时间看看新鲜东西。先从Nova算法开始~
三份资料可以帮助理解Nova算法:
-
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(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。
直觉上来说,一个关系R的折叠方案就是将两个符合关系R的实例“折叠成”一个新的复合关系R的实例。松弛R1CS/松弛承诺R1CS就能进行类似的折叠。两者的折叠过程类似。松弛承诺R1CS的折叠方案如下:
整个折叠方案由4步组成。第一步,证明者P发送一个交叉项T的承诺\bar{T}给验证者。第二步,验证者发送随机挑战r给证明者。第三步是证明者和验证者都需要执行的,承诺的折叠。第四步,证明者独自执行,将两个实例的E和W向量进行折叠。
折叠方案,折叠的是松弛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在某个迭代正确计算,逻辑上需要证明如下信息:
除了证明四个实例可满足外,还需要证明两个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的基本思想是通过折叠方案折叠电路实例。逻辑比较绕,需要仔细地思考电路折叠过程以及实现电路中的绑定关系。
一个字形容:绝~
比推快讯
更多 >>- 小罗伯特·肯尼迪:若当选总统将要求美国建立 400 万枚比特币储备,美元和比特币间的转账无需报告和交税
- Michael Saylor:比特币到 2045 年将达到 1300 万美元,牛市情况下可能达到 4900 万美元
- 美SEC批准灰度比特币迷你信托的19b-4 表格
- 前 FTX 高管 Ryan Salame 因被德国牧羊犬咬伤而要求推迟入狱日期
- 以太坊团队负责人:以太坊正在失去其“主线”,研究团队似乎接受了将一切中心化的想法
- BTC突破68000美元
- 美国法官批准推迟没收 FTX 的 PAC 政治捐款
- CryptoQuant创始人:本轮比特币牛市可能持续到 2025 年中期
- 美国泽西市市长:比特币是“通胀对冲工具”,个人还持有ETH
- Gemini调查:73% 的美国加密持有者计划在总统投票中考虑候选人对加密货币的立场
- 美参议员Bill Hagerty:正在努力推动通过支持比特币的立法
- EigenLayer:将推出AVS奖励和EIGEN程序化激励
- 瑞士金融市场监管机构:稳定币发行商会给与其合作的银行带来风险
- “木头姐”旗下 ARK Invest 于Q2减持Coinbase和特斯拉
- 比特币扩容网络Mezo完成750万美元战略轮融资,Ledger Cathay Fund领投
- Fortune:哈里斯或于未来几周分享比特币立场,据悉她的丈夫是一位“加密货币爱好者”
- Ledger 推出其最新系列硬件钱包 Ledger Flex
- 美国密歇根州养老基金第二季度买入660万美元的现货比特币ETF
- 今日美国以太坊ETF减持37044枚ETH,比特币ETF增持630枚BTC
- 消息人士:哈里斯竞选团队希望了解更多加密行业的相关信息
- Bitstamp:已完成Mt. Gox债权人的BTC与BCH分配,英国客户将有单独分配计划
- 野村证券旗下加密部门将于9月推出收益更高的以太坊ETF替代品
- VanEck CEO个人净资产中 30% 以上是比特币
- 量化基金 Kbit:尽管 ETF 带来快速回报,但仍应继续投资加密货币
- 比特币突破 67000 美元后,逾 75% 短期持有者已实现盈利
- Glassnode:当前比特币周期已经历两次 20%-30% 间的回撤
- 灰度向 Coinbase Prime 地址转入 11 万枚 ETH
- 以太坊ETF上市三天总资产已接近90亿美元
- GMX 社区发起将收入分配模式改为回购并分发 GMX 提案投票
- BlockFi 获得美国法院批准偿还 100% 客户资金
- BitForex 用户仍然无法提取其资金,总损失约5700万美元
- Jack Dorsey 正对 Block 进行重组
- 参议员 Elizabeth Warren:国外运营的加密挖矿机构可能被用来“监视美国的军事行动”
- 8480枚 ETH 从 Cumberland 转入 Coinbase Institutional
- Polymarket:哈里斯成为2024民主党总统候选人概率升至97%创新高
- 彭博分析师:以太坊 ETF 在抵消灰度资金流出方面不如比特币ETF
- 美国国务院承认比特币对萨尔瓦多旅游业产生积极影响,但对其经济影响“微乎其微”
- TON 生态 DeFi 解决方案 LayerPixel 完成 200 万美元种子轮融资,Kenetic Capital 领投
- 分析:若灰度 ETHE 按当前速度抛售,则其所持以太坊资产或于几周内耗尽
- 美国6月核心PCE物价指数月率0.2%,预期0.1%,前值0.10%
- Michael Saylor:美国政府应该拥有大多数比特币
- 香港立法会议员呼吁与内地有关单位深入合作加快推进数码港元进程,积极研究推进数字货币经济
- BRN 分析师:即将公布的 PCE 数据、特朗普比特币大会发言等因素或推动比特币创新高
- 渣打银行:预计 2034 年代币化市场规模将达到约 30 万亿美元
- 比特币大会今日将有众多政客发表演讲,参议员 Cynthia Lummis、小罗伯特·肯尼迪均将出席
- CeDeFi 收益平台 BitFi 宣布启动种子轮融资,估值为 5000 万美元
- 某鲸鱼从 Binance 提取 143 万 UNI 存入 AAVE 并借入 550 万 USDC
- 慢雾创始人余弦:警惕针对加密资产的假冒视频会议软件新型骗局
- Meme 推广平台 STIX 完成 180 万美元融资,Presto Labs 等参投
比推专栏
更多 >>观点
项目
比推热门文章
- 比特币必将进入国家储备时代
- Bitcoin 2024第二日:1BTC涨到4900万美元的多头号角;小肯尼迪承诺在美国建立比特币战略储备
- 【比推每日新闻精选】美SEC批准灰度比特币迷你信托的19b-4 表格;CryptoQuant创始人:本轮比特币牛市可能持续到 2025 年中期;Michael Saylor:比特币到 2045 年将达到 1300 万美元,牛市情况下可能达到 4900 万美元
- 小罗伯特·肯尼迪:若当选总统将要求美国建立 400 万枚比特币储备,美元和比特币间的转账无需报告和交税
- Michael Saylor:比特币到 2045 年将达到 1300 万美元,牛市情况下可能达到 4900 万美元
- 美SEC批准灰度比特币迷你信托的19b-4 表格
- Bitcoin 2024:大咖齐聚,行业拐点将至?
- 前 FTX 高管 Ryan Salame 因被德国牧羊犬咬伤而要求推迟入狱日期
- 以太坊团队负责人:以太坊正在失去其“主线”,研究团队似乎接受了将一切中心化的想法
- BTC突破68000美元