{"content":{"title":"【二】NOVA 系列之circuit","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]()\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论文中的主线内容。本章节主题可能是论文中最令人费解的地方，我们先从宏观上去把握它的脉络，再从细节上去扣它的设计理念。\r\n\r\n\r\n> !建议：最好配合着paper去理解，paper上找不到的答案或许这里可以给你-_-\r\n\r\n本章节内容涉及到NOVA一些非常巧妙的设计理念，内容有些干，所以多喝水-）\r\n\r\n---\r\n\r\n\r\n# 需要了解的一些术语\r\n* relaxed R1CS 是NOVA中为方便folding而对标准R1CS的拓展，细节部分在后面章节会展开，这里大致了解一下它的等式：\r\n \r\n$$\r\n\\begin{aligned} \r\n\r\nAZ \\circ BZ &= u* CZ + E \\\\\r\n\r\nZ &= (W, u, X) \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n* SAT，是R1CS 或者 relaxed R1CS Instance-Witness pair对$(U', W') $ satisfactory 的简单表述，包含两部分，R1CS 等式验证和commitment验证，具体的验证逻辑如下：\r\n \r\n$$\r\n\\begin{aligned}\r\n\r\nZ &= [W'.W, U'.u, U'.X] \\\\\r\n\r\n&\\begin{cases}\r\n\r\nAZ \\circ BZ &\\stackrel{?} = U'.u * CZ + W'.E \\\\\r\n\r\nU'.\\widetilde{W} &\\stackrel{?}= commit(W'.W) \\\\\r\n\r\n\\end{cases}\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n-----------\r\n\r\n# 可能已经知晓的\r\n\r\n上一章节[NIFS](https://learnblockchain.cn/article/5978)的整个逻辑中有三个重要角色，NIFS Prover 、NIFS Verifier和除它们之外的第三者，它们的任务分别是：\r\n\r\n* **NIFS Prover** (离线进行) 每个step 需要分别对两个R1CS Instance 进行fold，生成一个relaxed R1CS Instance，和两个R1CS Witness 进行fold，生成一个relaxed R1CS Witness\r\n
\r\n\r\n* **NIFS Verifier** (线上进行) 每个step 只需要对两个R1CS Instance进行fold，生成一个relaxed R1CS Instance\r\n
\r\n\r\n* **第三者**负责对两者每个step fold后的relaxed R1CS Instance 进行匹配验证是否相等，以及一系列step fold之后最后生成的R1CS Instance-Witness pair对进行SAT校验\r\n
\r\n\r\n*我们总结一下：NIFS要做的就是，SNARK Prover对业务电路经过N次step 迭代后生成的proof进行fold，最终只生成一个proof，并递交给SNARK Verifier 进行验证。前提是，SNARK Prover 它自己要保证fold的正确性，而且fold 与 不fold效果一致。本系列专题的核心就是为了解决这两个问题。*\r\n\r\n-----------\r\n\r\n# circuit 的由来和目标\r\n\r\n一句话，这里的circuit 就是**NIFS Verifier**的电路。那么问题来了：\r\n1. 为什么是**NIFS Verifier**电路？\r\n2. 这里的**NIFS Verifier**电路与上节[NIFS](https://learnblockchain.cn/article/5978)的逻辑有什么关系？\r\n3. 业务电路呢？\r\n
\r\n\r\n这里我们把整个逻辑再梳理一遍，尽量弄清楚NIFS Verifier出现的原委，排除一切障碍。\r\n\r\n\r\n## 为什么要有NIFS Verifier 电路\r\n\r\n其实我们最终的目的是要fold 两个标准的R1CS Witness\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n\\begin{rcases}\r\n\r\nAZ_1 \\circ BZ_1 = CZ_1 \\\\\r\n\r\nAZ_2 \\circ BZ_2 = CZ_2 \\\\\r\n\r\n\\end{rcases} \\stackrel{fold} \\Longrightarrow AZ \\circ BZ = CZ\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n但如何保证Prover 不做假，保证fold的正确性？所以就出现了Verifier，需要对Prover fold之后的R1CS Witness进行验证。\r\n
\r\n\r\n但为了保证privacy 需要对Witness进行commit，所以就有与R1CS Witness匹配的R1CS Instance。Verifier 表面上只fold Instance，本质上跟Prover fold Witness是等效的，前提是它们之间满足**R1CS SAT**。为了保证验证逻辑的完备性，Prover 同样也要fold Instance，然后把二者fold的Instance 放在一起比对，看它们是否相等。\r\n
\r\n\r\n到这儿，fold 的正确与否的校验逻辑就通了。\r\n\r\n\r\n## 谁来校验fold的结果\r\n\r\n在上一章节[NIFS](https://learnblockchain.cn/article/5978)中我们提到，判定Prover 与 Verifier fold的Instance 是否相等是由第三方来完成的，这确实是make sense的，由第三方来做鉴定保证公平公正。但是，\r\n
\r\n\r\nNOVA的设计理念是想实现SNARK Prover 自证，这个校验过程不会与第三方有交互。那么 NOVA是如何做到的？这也是circuit 的电路设计非常巧妙的地方，值得研究学习！这里先把答案写出来，我们后面再剖析它：\r\n
\r\n\r\n\r\n**当前step 对应的电路会校验前一个step NIFS Prover 离线fold的Instance 与 NIFS Verifier 线上fold的Instance 是否相等**。\r\n
\r\n\r\n为什么可以这样？因为当前step 的NIFS Verifier电路对于上一个step NIFS Verifier电路和离线的NIFS Prover 来说就是第三方，所以这么设计逻辑上是走得通的。\r\n
\r\n\r\n细心的读者可能还会存在一个疑虑，既然是当前step 校验上一个step，那最后一个step谁来校验？答案很简单，在电路的外面执行。**在最后一个step后，电路外面会check 一下最后一个step Primary/Secondary 电路fold的结果是否分别与离线fold的结果相等**。\r\n\r\n## 回答上面的三个问题\r\n\r\n1. 因为NIFS Prover 本来就是离线进行的，线上验证交给电路的Verifier\r\n2. 跟上一章节的[NIFS](https://learnblockchain.cn/article/5978) 关系，到这儿应该比较清晰了，就是把线上fold的任务 和 校验的任务全部放在NIFS Verifier 电路里做了\r\n3. 业务电路，其实也是放在NIFS Verifier 电路里了，会在适当的时候触发业务逻辑，这个后面会展开\r\n
\r\n\r\n\r\n## NIFS Verifier 电路的任务\r\n\r\nNIFS Verifier 电路的任务有两个：**其一，完成当前step 既定的fold工作，其二，完成上一个step的验证工作**。\r\n\r\n---\r\n\r\n# 双簧电路\r\n所谓双簧，就是为了同一全局目标由两个互相搭档的Primary-Secondary 电路。\r\n
\r\n\r\n如果你去看NOVA的原始论文，其中会提到通过Fiat-Shamir Transform 实现non-interactive，然后把当前step fold后的Instance 进行hash，并输出...... 估计有一大批读者都会倒在这个地方，怎么输出，输出后怎么接上，后面怎么验证上面说的两个Instance 是否相等？\r\n
\r\n\r\n先帖一张双簧电路最简单的逻辑结构图：\r\n\r\n\r\n\r\n\r\n**本章节重点在梳理电路的设计逻辑，图中relaxed R1CS Instance是离线产出的，我们会在后面的章节中详细展开**。\r\n
\r\n\r\n这是一个简洁版的两个step的逻辑流图，到目前为止我们大概明确这么几点：\r\n1. Primary 电路的核心任务是触发业务电路$F $的forward 计算\r\n
\r\n\r\n2. 业务电路$F $forward 计算产出的R1CS Witness 经过commit 之后变成R1CS Instance，传递给Secondary 电路\r\n
\r\n\r\n3. Secondary 电路的核心任务是fold 当前step业务电路的R1CS Instance 和 上一次fold后的relaxed R1CS Instance\r\n
\r\n\r\n4. Secondary 电路的业务电路是一个空的$Trivial $电路，所以触发它结果仍然为空，但它仍然会把当前step fold后的relaxed R1CS Instance以hash的形式向后面传递，保证下一个step 的Secondary 能够接收到\r\n
\r\n\r\n下面部分会尽可能详尽地勾画出电路设计的巧妙之处。\r\n\r\n----\r\n# 双簧电路的宏观描述\r\n\r\n【Primary NIFS Verifier 电路】接收Secondary 电路的吐出来的R1CS Instance，线上进行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 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\r\n# 双簧电路更多的细节\r\n\r\n\r\n## 验证逻辑\r\n\r\n我们可以看到在fold 的左边(之前)需对即将进行fold的两个Instance 进行校验，判断R1CS Instance中是否包含relaxed R1CS Instance的Hash值。\r\n\r\n**这一步的校验就是上面反复提到的如何验证离线fold的Instance 与电路里fold的 Instance是否相等**。\r\n
\r\n\r\n**注意，这里的trace逻辑比较耐人寻味，拿Primary NIFS Verifier 电路，我们可以展开看一下。**\r\n
\r\n\r\n---\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_{secondary}′′$\r\n
\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_{secondary}′$\r\n\r\n----\r\n\r\n所以最终它要验证上一个step 中离线fold Secondary 的结果与线上或者电路中fold Secondary 的结果是否相等，从而保证电路中fold Secondary的结果是satisfiable的：\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## 业务电路forward计算\r\n这个是在fold之后被触发的\r\n$$\r\nz_{i + 1} = F(z_i)\r\n$$\r\n它的触发会伴随着相应的Witness 输出\r\n\r\n## 输出与接收\r\n\r\n1. 上一个step 中Primary Fold后的relaxed R1CS Instance的Hash值\r\n
\r\n\r\n2. 当前Secondary Fold后的relaxed R1CS Instance的Hash值\r\n
\r\n\r\n3. 当前电路的所有Witness 包括业务电路的Witness全部输出，生成一个新的R1CS Witness\r\n
\r\n\r\n4. 对新生成的R1CS Witness 进行commit 得到新的R1CS Instance\r\n
\r\n\r\n5. 其中这个新的R1CS Instance 会接收上面的两个hash值，作为public variable 丢到$x$中\r\n
\r\n\r\n\r\nSecondary 电路的逻辑跟上面的类似，只是它的业务电路为空的而已，这里就不再展开。 目前为止，我们明确一点就好，**Primary 核心任务是业务电路的forward 计算，Secondary的核心任务才是真正的fold操作**。\r\n\r\n---\r\n# 总结与后续\r\n\r\n到目前为止，我们已经把电路在NOVA 整个scheme中的定位，以及它具体的任务，还有设计的技巧都尽可能地表达清楚了，希望能给读者带来paper 之外更多的干货。\r\n
\r\n\r\n接下来的章节，会把NIFS 离线fold的部分添加进来，使得整个逻辑更加完整，对电路设计的理解会更透彻。"},"author":{"user":"https://learnblockchain.cn/people/15677","address":null},"history":"Qmd5RPGPncpPo13FNEYry7YoA5AKCF9onZtXTDLD9gAKKM","timestamp":1687187629,"version":1}