NOVA系列之RecursiveSNARK

  • A+
所属分类:区块链

chatGPT账号

近期NOVA作为当前ZK领域热门的Folding Scheme解决方案,备受工业界追捧,该系列专题将逐一拆解它:

 

希望通过详尽且直白的逻辑能够把NOVA整个框架的设计理念传达到读者,最终落地到实际的crypto应用场景中。

其中前两个主题为crypto primitives,后四个主题为NOVA论文中的主线内容。本章节内容基本上是上两个章节NIFS 和Circuit的整合,在整个SNARK里面,这部分对应的是SNARK Prover,后面加入CompressedSNARK 后就是一套完整的zkSNARK了。

!建议:最好配合着paper去理解,paper上找不到的答案或许这里可以给你-_-


你可能已经知晓的

NOVA系列之RecursiveSNARK

上一章节中,我们把电路部分,也就是 Primary NIFS.Verifier 和 Secondary NIFS.Verifier 单独拎了出来。本章节我们会加入离线部分,也就是Primary NIFS.Prover和 Secondary NIFS.Prover,使得NOVA整个fold scheme更加完整。


宏观结构

先上一张完整版的交互逻辑图

NOVA系列之RecursiveSNARK

重点明确这么几点:

  • SNARK Prover 这边本质上就是一套NIFS 框架,分离线和线上(电路)两部分
  • 离线部分对应到图中的NIFS.Prover,它的输入为(�,�,�,�)(U,u,W,w)
  • 线上部分对应到图中的NIFS.Verifier,电路程序,它的输入为(�,�)(U,u)
  • 每个step 包含两个NIFS,Primary NIFS 和 Secondary NIFS

它们分别包含上面提到的分离线和线上两部分,Primary NIFS.Prover、Primary NIFS.Verifier 和 Secondary NIFS.Prover、Secondary NIFS.Verifier

 

  • Primary NIFS与 Secondary NIFS之间的唯一的交互就是从电路Constrain System 中抽离出来的(�,�)(u,w)

当前step 的Primary 电路CS中抽离出来的(�,�)(u,w) 交给当前step 的Secondary NIFS,当前step 的Secondary 电路CS中抽离出来的(�,�)(u,w) 交给下一个step 的Primary NIFS

 


NIFS Prover 与 NIFS Verifier

关于NIFS Prover 与 NIFS Verifier之间的关系,在上章节NIFS 中"为什么要有NIFS Verifier电路" 和 “谁来校验fold的结果” 已经表达得很清晰了,这里我们明确这么几点:

  • NIFS Verifier电路是离线NIFS Prover 的线上版本,只是fold的Instance,没有Witness而已
  • 当前step 的 NIFS Verifier电路在fold Instance 之前,会校验上一个step 离线NIFS Prover fold后的Instance �′U与 线上NIFS Verifier(电路)fold后的Instance �′′U′′ 是否相等
�������′==�������′′{if true we can say �������′′ is satisfiable only if �������′⟵satisfiable�������′if false we can say �������′′ is not satisfiable Uprmary==Uprmary′′{if true we can say Uprmary′′ is satisfiable only if Uprmaryif false we can say Uprmary′′ is not satisfiable satisfiableWprmary

Primary NIFS 与 Secondary NIFS

我们在上一章节NIFS中大概勾画出Primary NIFS Verifier 与 Secondary NIFS Verifier两个电路的交互逻辑,同样,这里我们补上离线部分,Primary NIFS Prover 与 Secondary NIFS Prover。

【Primary NIFS Prover】接收上一个step 中Secondary NIFS Verifier电路的吐出来的R1CS Instance,离线进行fold操作,被fold的relaxed R1CS Instance 为上一个step 中Primary NIFS Prover fold后的结果。同样(�,�)(W,w) 为对应的Witness。

(����������,����������)(����������,����������)}⟹Fold(2◯����������′,����������′)‾(Usecondary,Wsecondary)(usecondary,wsecondary)}Fold(2Usecondary,Wsecondary)

 

【Primary NIFS Verifier 电路】接收上一个step 中Secondary 电路的吐出来的R1CS Instance,线上进行fold 操作;被fold的relaxed R1CS Instance 为上一个step 中Primary NIFS Prover fold后的结果。

��������������������1◯����������.�[0]=?1◯�(����������)}⟹������+1=�(��){2◯����������.�[1]⟶��������′.�[0]3◯����������′′⟶Hash��������′.�[1]��������′Usecondaryusecondary1usecondary.x[0]=?1H(Usecondary)zi+1=F(zi)Fold2usecondary.x[1]uprimary.x[0]3Usecondary′′Hashuprimary.x[1]wprimary

 

【Secondary NIFS Prover】接收当前step中Primary NIFS Verifier电路的吐出来的R1CS Instance,离线进行fold操作;被fold的relaxed R1CS Instance 为上一个step 中Secondary NIFS Prover fold后的结果。同样(�,�)(W,w) 为对应的Witness。

(��������,��������)(��������′,��������′)}⟹Fold(2◯��������′,��������′)‾(Uprimary,Wprimary)(uprimary,wprimary)}Fold(2Uprimary,Wprimary)

 

【Secondary NIFS Verifier 电路】接收Primary 电路吐出来的R1CS Instance,线上进行fold 操作。

����������������′1◯��������′.�[0]=?1◯�(��������)}⟹Fold{2◯��������′.�[1]⟶?����������′.�[0]3◯��������′′⟶Hash����������′.�[1]����������′Uprimaryuprimary1uprimary.x[0]=?1H(Uprimary)Fold2uprimary.x[1]?usecondary.x[0]3Uprimary′′Hashusecondary.x[1]wsecondary

NIFS 验证的细节

NIFS 验证就是校验离线NIFS.Prover old后的Instance �′U与 线上NIFS.Verifier 电路fold后的Instance �′′U′′是否相等,即

�′==�′′U==U′′

在上一章节NIFS中电路验证逻辑有详细地trace过等式左边部分,上面我们已经补上离线NIFS.Prover部分,这里我们再review一下trace的逻辑,看看究竟是不是那么回事儿。

trace主要解决两个问题:

  1. 为什么R1CS instance u中藏着的是上一个step 的线上NIFS.Verifier(电路)fold后的结果�′′U′′?
  2. 为什么被fold的relaxed R1CS instance U是上一个step的离线NIFS.Prover fold后的结果�′U?

所以,

��}⟹fold��.�0=?���ℎ(�)  ⟺  �′=?�′′uU}foldUu.x0=?Hash(U)U=?U′′

Primary NIFS Verifier 电路trace 的过程

  • 先trace 等式左边的值
1◯⟶last step of 2◯⟶last step of 3◯1last step of 2last step of 3

得到的是上一个step 的Primary NIFS Verifier 电路中fold Secondary 电路吐出来的u之后的结果����������′′Usecondary′′

  • 再trace 等式右边的值
1◯⟶last step of 2◯1last step of 2

得到的是上一个step 的Primary NIFS Prover 离线fold Secondary电路吐出来的u之后的结果����������′Usecondary

  • 判断两者是否相等
if ����������′=����������′′ we can say ����������′ is satisfiableif and only if ����������′⟵satisfiable�′if Usecondary=Usecondary′′ we can say Usecondary is satisfiableif and only if UsecondarysatisfiableW

Secondary NIFS Verifier 电路trace 的过程

  • 先trace 等式左边的值
1◯⟶last step of 2◯⟶last step of 3◯1last step of 2last step of 3

得到的是上一个step 的Secondary NIFS Verifier 电路中fold Primary电路吐出来的u之后的结果��������′′Uprimary′′

  • 再trace 等式右边的值
1◯⟶last step of 2◯1last step of 2

得到的是上一个step 的Secondary NIFS Prover 离线fold Primary电路吐出来的u之后的结果��������′Uprimary

  • 判断两者是否相等
if ��������′=��������′′ we can say ��������′ is satisfiableif and only if ��������′⟵satisfiable��������′if Uprimary=Uprimary′′ we can say Uprimary is satisfiableif and only if UprimarysatisfiableWprimary

总结与后续

到目前为止,NOVA的核心内容,也就是SNARK Prover部分就已经完整了。

免责声明

发文时比特币价格:$27249

当前比特币价格:[crypto coins=”BTC” type=”text” show=”price”]

当前比特币涨幅:[crypto coins=”BTC” type=”text” show=”percent”]

免责声明:

本文不代表路远网立场,且不构成投资建议,请谨慎对待。用户由此造成的损失由用户自行承担,与路远网没有任何关系;

路远网不对网站所发布内容的准确性,真实性等任何方面做任何形式的承诺和保障;

网站内所有涉及到的区块链(衍生)项目,路远网对项目的真实性,准确性等任何方面均不做任何形式的承诺和保障;

网站内所有涉及到的区块链(衍生)项目,路远网不对其构成任何投资建议,用户由此造成的损失由用户自行承担,与路远网没有任何关系;

路远区块链研究院声明:路远区块链研究院内容由路远网发布,部分来源于互联网和行业分析师投稿收录,内容为路远区块链研究院加盟专职分析师独立观点,不代表路远网立场。

本文是全系列中第193 / 223篇:行业技术

  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的电报
  • 这是我的电报扫一扫
  • weinxin
chatGPT账号
路远

发表评论

您必须登录才能发表评论!