零知识证明技术的革命性进展:深入探讨Nova算法

    前段时间在翻译一本零知识证明技术的书。上个月底基本内容已经翻译完成。翻译时间比我预想的长得多。目前正在和作者讨论书中的一些笔误,准备最后的定稿。anyway,终于有点时间看看新鲜东西。先从Nova算法开始~Nova算法相关资料三份资料可以帮助理解Nova算法:Nova论文:https://eprint.iacr.org/2021/370.pdfNova潜在攻击和相应修正:https://eprint.iacr.org/2023/969.pdfNova潜在攻击的理解总结:https://www.zksecurity.xyz/blog/posts/nova-attack/本文是上述资料的理解和总结。本文中的一些图来自于上述资料,在本文中不再一一标注。从IVC开始Nova算法是一种针对IVC(增量可验证计算,IncrementallyVerifiableComputation)的新型的零知识证明算法。IVC,即同一个函数把前一个输出作为下一个输入迭代计算。F函数的迭代计算过程如下图:z0是最初的输入,通过F函数计算生成的结果,作为下一个F函数的输入。松弛R1CS以及松弛承诺R1CS众所周知,R1CS是零知识证明技术中电路约束表示形式。松弛R1CS(RelaxedR1CS)可以看成是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。折叠方案(FoldingScheme)直觉上来说,一个关系R的折叠方案就是将两个符合关系R的实例“折叠成”一个新的复合关系R的实例。松弛R1CS/松弛承诺R1CS就能进行类似的折叠。两者的折叠过程类似。松弛承诺R1CS的折叠方案如下:整个折叠方案由4步组成。第一步,证明者P发送一个交叉项T的承诺bar{T}给验证者。第二步,验证者发送随机挑战r给证明者。第三步是证明者和验证者都需要执行的,承诺的折叠。第四步,证明者独自执行,将两个实例的E和W向量进行折叠。增广函数F'(ArgumentedFunction)折叠方案,折叠的是松弛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域相同。采用这样的椭圆曲线循环,可以将“理想中的样子”实现:整个折叠过程,拆分成两个电路进行折叠。上部分可以称为Circuit1的折叠,下部分可以称为Circuit2的折叠。两个电路的关系的形式化表示在论文“Nova潜在攻击和相应修正”的第8页。U表示的是折叠后的实例,u表示的是一个R1CS实例对应的松弛实例。注意的是,Circuit1折叠的是Circuit2对应的松弛承诺R1CS实例,而Circuit2折叠的才是Circuit1对应的松弛承诺R1CS实例。Circuit2的主要目的就是折叠Circuit1对应的松弛承诺R1CS实例,其电路中的函数计算没有意义。相反,F函数实现在Circuit1中。结合“理想中的样子”,大致可以猜到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作为下半部分电路的输入时,经过Circuit2,其输出u{i+1}^2.x0=u{i+1}^1.x1,这样,再输入到上半部分电路时,如果u{i+1}^2可满足的话,则其的x_0应该等于U_{i+1}^2的H1的结果。这在Circuit1电路中会进行检查。

    这样,就保证了正确的实例,在两个电路之间传递。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实例不满足。虽然它不满足,但是Circuit2的电路还是可以满足的,只是输出U{i+1}^1实例不满足而已。成功构造了u{i+1}^2的话,Circuit1就可以构造出可满足的u{i+2}^1以及U_{i+2}^2,并且满足x1的绑定关系。这样就先构造出了最终伪造证明的一半内容。通过对称性,可以构造出下面一半的输出实例。通过两次构造的结果的“拼接”,可以伪造出IVC计算的证明。修正后的检查逻辑如下:“Nova潜在攻击和相应修正”论文的第6章给出了详细的安全性分析。感兴趣的小伙伴,可以自行查看原论文。Nova的基本思想是通过折叠方案折叠电路实例。逻辑比较绕,需要仔细地思考电路折叠过程以及实现电路中的绑定关系。一个字形容:绝~

Pixel Artist Pixel Artist
Happy Kittens Puzzle Happy Kittens Puzzle
Penguin Cafe Penguin Cafe
Animal Connection Animal Connection
Snakes N Ladders Snakes N Ladders
Pixel Skate Pixel Skate
BeeLine BeeLine
Draw Parking Draw Parking
Draw Racing Draw Racing
Soccer Balls Soccer Balls
Happy Fishing Happy Fishing
Crashy Cat Crashy Cat

FREE GAMES FOR KIDS ONLINE