{"content":{"title":"【三】NOVA系列之RecursiveSNARK","body":"近期[NOVA](https://eprint.iacr.org/2021/370.pdf)作为当前ZK领域热门的Folding Scheme解决方案，备受工业界追捧，该系列专题将逐一拆解它：\r\n* [Pederson and Poseidon]()\r\n* [R1CS and relaxed R1CS]()\r\n* [NIFS](https://learnblockchain.cn/article/5978)\r\n* [Circuit](https://learnblockchain.cn/article/5993)\r\n* [RecursiveSNARK]()\r\n* [CompressedSNARK]()\r\n\r\n
\r\n\r\n希望通过**详尽且直白的逻辑**能够把NOVA整个框架的设计理念传达到读者，最终落地到实际的crypto应用场景中。\r\n
\r\n\r\n其中前两个主题为crypto primitives，后四个主题为NOVA论文中的主线内容。本章节内容基本上是上两个章节[NIFS](https://learnblockchain.cn/article/5978) 和[Circuit](https://learnblockchain.cn/article/5993)的整合，在整个SNARK里面，这部分对应的是**SNARK Prover**，后面加入CompressedSNARK 后就是一套完整的zkSNARK了。\r\n\r\n\r\n> !建议：最好配合着paper去理解，paper上找不到的答案或许这里可以给你-_-\r\n\r\n---\r\n# 你可能已经知晓的\r\n\r\n\r\n\r\n上一章节中，我们把电路部分，也就是 Primary NIFS.Verifier 和 Secondary NIFS.Verifier 单独拎了出来。本章节我们会加入离线部分，也就是**Primary NIFS.Prover**和 **Secondary NIFS.Prover**，使得NOVA整个fold scheme更加完整。\r\n
\r\n\r\n---\r\n# 宏观结构\r\n\r\n先上一张完整版的交互逻辑图\r\n\r\n\r\n\r\n\r\n\r\n重点明确这么几点：\r\n- SNARK Prover 这边本质上就是一套NIFS 框架，分离线和线上(电路)两部分\r\n
\r\n\r\n- 离线部分对应到图中的NIFS.Prover，它的输入为$(U, u, W, w)$\r\n
\r\n\r\n- 线上部分对应到图中的NIFS.Verifier，电路程序，它的输入为$(U, u)$\r\n
\r\n\r\n- 每个step 包含两个NIFS，Primary NIFS 和 Secondary NIFS\r\n\r\n> 它们分别包含上面提到的分离线和线上两部分，Primary NIFS.Prover、Primary NIFS.Verifier 和 Secondary NIFS.Prover、Secondary NIFS.Verifier\r\n\r\n
\r\n\r\n- Primary NIFS与 Secondary NIFS之间的唯一的交互就是从电路**Constrain System** 中抽离出来的$(u, w)$\r\n\r\n> 当前step 的Primary 电路CS中抽离出来的$(u, w)$ 交给当前step 的Secondary NIFS，当前step 的Secondary 电路CS中抽离出来的$(u, w)$ 交给下一个step 的Primary NIFS\r\n\r\n
\r\n\r\n----\r\n# NIFS Prover 与 NIFS Verifier\r\n\r\n关于NIFS Prover 与 NIFS Verifier之间的关系，在上章节[NIFS](https://learnblockchain.cn/article/5993) 中\"[为什么要有NIFS Verifier电路](https://learnblockchain.cn/article/5993#为什么要有NIFS%20Verifier%20电路)\" 和 “[谁来校验fold的结果](https://learnblockchain.cn/article/5993#谁来校验fold的结果)” 已经表达得很清晰了，这里我们明确这么几点：\r\n
\r\n\r\n- **NIFS Verifier电路是离线NIFS Prover 的线上版本**，只是fold的Instance，没有Witness而已\r\n
\r\n\r\n- 当前step 的 NIFS Verifier电路在fold Instance 之前，会校验上一个step 离线NIFS Prover fold后的Instance $U'$与 线上NIFS Verifier(电路)fold后的Instance $U''$ 是否相等\r\n
\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\nU_{prmary}' &== U_{prmary}'' \r\n\r\n\\begin{cases}\r\n\r\n\\text{if true we can say } U_{prmary}'' \\text{ is satisfiable only if } U_{prmary}' &\\stackrel{satisfiable}\\longleftarrow W_{prmary}' \\\\\r\n\r\n\\text{if false we can say } U_{prmary}'' \\text{ is not satisfiable } \\\\\r\n\r\n\\end{cases}\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n---\r\n# Primary NIFS 与 Secondary NIFS\r\n\r\n我们在上一章节NIFS中大概勾画出[Primary NIFS Verifier 与 Secondary NIFS Verifier两个电路的交互逻辑](https://learnblockchain.cn/article/5993#双簧电路的宏观描述)，同样，这里我们补上离线部分，Primary NIFS Prover 与 Secondary NIFS Prover。\r\n
\r\n\r\n【Primary NIFS Prover】接收上一个step 中Secondary NIFS Verifier电路的吐出来的R1CS Instance，离线进行fold操作，被fold的relaxed R1CS Instance 为上一个step 中Primary NIFS Prover fold后的结果。同样$(W, w)$ 为对应的Witness。\r\n\r\n$$\r\n\\begin{rcases}\r\n\r\n(U_{secondary}, W_{secondary}) \\\\\r\n\r\n(u_{secondary}, w_{secondary}) \\\\\r\n\r\n\\end{rcases}\r\n\r\n\\stackrel{Fold}\\Longrightarrow \r\n\r\n\\underline{(\\textcolor{red}{\\text{\\textcircled 2}U_{secondary}'}, W_{secondary}')}\r\n$$\r\n
\r\n\r\n【Primary NIFS Verifier 电路】接收上一个step 中Secondary 电路的吐出来的R1CS Instance，线上进行fold 操作；被fold的relaxed R1CS Instance 为上一个step 中Primary NIFS Prover fold后的结果。\r\n
\r\n\r\n$$\r\n\\begin{rcases}\r\n\r\nU_{secondary} \\\\\r\n\r\nu_{secondary} \\\\\r\n\r\n\\textcolor{green}{\\text{\\textcircled 1} u_{secondary}.x[0]} \\stackrel{?} = \\textcolor{red}{\\text{\\textcircled 1} H(U_{secondary})} \\\\\r\n\r\n\\end{rcases}\r\n\r\n\\underset{z_{i+1} = F(z_i)} {\\overset{Fold}\\Longrightarrow }\r\n\r\n\\begin{cases}\r\n\r\n\\textcolor{blue}{\\text{\\textcircled 2} u_{secondary}.x[1]} \\longrightarrow \\textcolor{blue}{u_{primary}'.x[0]} \\\\\r\n\r\n\\textcolor{green}{\\text{\\textcircled 3} U_{secondary}''} \\stackrel{Hash} \\longrightarrow \\textcolor{green}{u_{primary}'.x[1]} \\\\\r\n\r\nw_{primary}' \\\\\r\n\r\n\\end{cases}\r\n$$\r\n
\r\n\r\n【Secondary NIFS Prover】接收当前step中Primary NIFS Verifier电路的吐出来的R1CS Instance，离线进行fold操作；被fold的relaxed R1CS Instance 为上一个step 中Secondary NIFS Prover fold后的结果。同样$(W, w)$ 为对应的Witness。\r\n\r\n$$\r\n\\begin{rcases}\r\n\r\n(U_{primary}, W_{primary}) \\\\\r\n\r\n(u_{primary}', w_{primary}') \\\\\r\n\r\n\\end{rcases}\r\n\r\n\\overset{Fold} {\\Longrightarrow}\r\n\r\n\\underline{(\\textcolor{teal}{\\text{\\textcircled 2} U_{primary}'}, W_{primary}')}\r\n$$\r\n
\r\n\r\n【Secondary NIFS Verifier 电路】接收Primary 电路吐出来的R1CS Instance，线上进行fold 操作。\r\n
\r\n\r\n$$\r\n\\begin{rcases}\r\n\r\nU_{primary} \\\\\r\n\r\nu_{primary}' \\\\\r\n\r\n\\textcolor{blue}{\\text{\\textcircled 1} u_{primary}'.x[0]} \\stackrel{?} = \\textcolor{teal}{\\text{\\textcircled 1} H(U_{primary})} \\\\\r\n\r\n\\end{rcases}\r\n\r\n\\stackrel{Fold}\\Longrightarrow \r\n\r\n\\begin{cases}\r\n\r\n\\textcolor{green}{\\text{\\textcircled 2} u_{primary}'.x[1] \\stackrel{?} \\longrightarrow u_{secondary}'.x[0]} \\\\\r\n\r\n\\textcolor{blue}{\\text{\\textcircled 3} U_{primary}''} \\stackrel{Hash}\\longrightarrow \\textcolor{blue}{u_{secondary}'.x[1]} \\\\\r\n\r\nw_{secondary}'\r\n\r\n\\end{cases}\r\n$$\r\n\r\n---\r\n# NIFS 验证的细节\r\n\r\nNIFS 验证就是校验离线NIFS.Prover old后的Instance $U'$与 线上NIFS.Verifier 电路fold后的Instance $U''$是否相等，即\r\n$$\r\nU' == U''\r\n$$\r\n\r\n在上一章节NIFS中[电路验证逻辑](https://learnblockchain.cn/article/5993#验证逻辑)有详细地trace过等式左边部分，上面我们已经补上离线NIFS.Prover部分，这里我们再review一下trace的逻辑，看看究竟是不是那么回事儿。\r\n
\r\n\r\ntrace主要解决两个问题：\r\n1. 为什么R1CS instance $u$中藏着的是上一个step 的线上NIFS.Verifier(电路)fold后的结果$U''$?\r\n
\r\n\r\n2. 为什么被fold的relaxed R1CS instance $U$是上一个step的离线NIFS.Prover fold后的结果$U'$?\r\n\r\n所以，\r\n\r\n$$\r\n\r\n\\begin{rcases}\r\nu \\\\\r\nU\r\n\r\n\\end{rcases} \\stackrel{fold} \\Longrightarrow U \\\\\r\n\r\nu.x_0 \\stackrel{?}= Hash(U) \\iff U' \\stackrel{?}= U''\r\n\r\n$$\r\n\r\n---\r\n## Primary NIFS Verifier 电路trace 的过程\r\n- 先trace 等式左边的值\r\n\r\n$$\r\n\\textcolor{green}{\\text{\\textcircled 1}} \\longrightarrow \\text{last step of } \\textcolor{green}{\\text{\\textcircled 2}} \\longrightarrow \\text{last step of } \\textcolor{green}{\\text{\\textcircled 3}}\r\n$$\r\n\r\n\r\n得到的是上一个step 的Primary NIFS Verifier 电路中fold Secondary 电路吐出来的$u$之后的结果$U_{secondary}′′$\r\n
\r\n\r\n- 再trace 等式右边的值\r\n\r\n$$\r\n\\textcolor{red}{\\text{\\textcircled 1}} \\longrightarrow \\text{last step of } \\textcolor{red}{\\text{\\textcircled 2}}\r\n$$\r\n\r\n\r\n得到的是上一个step 的Primary NIFS Prover 离线fold Secondary电路吐出来的$u$之后的结果$U_{secondary}′$\r\n\r\n- 判断两者是否相等\r\n\r\n$$\r\n\\text{if }U_{secondary}′ = U_{secondary}′′ \\text{ we can say } U_{secondary}' \\text{ is satisfiable} \\\\\r\n\\text{if and only if } U_{secondary}′ \\stackrel{satisfiable} \\longleftarrow W'\r\n$$\r\n\r\n---\r\n\r\n## Secondary NIFS Verifier 电路trace 的过程\r\n- 先trace 等式左边的值\r\n\r\n$$\r\n\\textcolor{blue}{\\text{\\textcircled 1}} \\longrightarrow \\text{last step of } \\textcolor{blue}{\\text{\\textcircled 2}} \\longrightarrow \\text{last step of } \\textcolor{blue}{\\text{\\textcircled 3}}\r\n$$\r\n\r\n\r\n得到的是上一个step 的Secondary NIFS Verifier 电路中fold Primary电路吐出来的$u$之后的结果$U_{primary}′′$\r\n
\r\n\r\n- 再trace 等式右边的值\r\n\r\n$$\r\n\\textcolor{teal}{\\text{\\textcircled 1}} \\longrightarrow \\text{last step of } \\textcolor{teal}{\\text{\\textcircled 2}}\r\n$$\r\n\r\n\r\n得到的是上一个step 的Secondary NIFS Prover 离线fold Primary电路吐出来的$u$之后的结果$U_{primary}′$\r\n\r\n- 判断两者是否相等\r\n\r\n$$\r\n\\text{if }U_{primary}′ = U_{primary}′′ \\text{ we can say } U_{primary}' \\text{ is satisfiable} \\\\\r\n\\text{if and only if } U_{primary}′ \\stackrel{satisfiable} \\longleftarrow W_{primary}'\r\n$$\r\n\r\n---\r\n# 总结与后续\r\n\r\n到目前为止，NOVA的核心内容，也就是SNARK Prover部分就已经完整了。\r\n
"},"author":{"user":"https://learnblockchain.cn/people/15677","address":null},"history":"QmbqJNGJMeS9uVFwQ4zyYGfUeqvTXSdURLgyvy1vDCyuJQ","timestamp":1687356253,"version":1}