SNARK的构建流程是什么样的？

待证明的问题-算术电路-R1CS-多项式

为什么最终要转换成多项式？

因为多项式的特性有效的缩短了验证时间，实现了简洁性。

是如何实现零知识的？

简单来说，就是在推导多项式的过程中，多选取两个随机数，以此推导出的多项式能让验证者无法从中获取原多项式的系数，即证明者的秘密输入，以此实现ZK。

怎么实现非交互？

在证明开始前，引入了一个第三方，即可信设置，将原本验证者挑选随机数的任务交给了可信设置，从而实现验证者和证明者之间的非交互。

ZK技术近两年在Web3领域备受关注。从Rollup开始，越来越多不同赛道的项目都开始尝试使用ZK技术。在这之中，SNARK和STARK是大家最常听到的两个名词，为了后期更好地理解ZK技术的应用，本文将从非技术的角度简化阐述SNARK的证明逻辑，然后会以Scroll的zkRollup为例来说明zk证明系统的运行。

文章旨在阐述基本逻辑，便于阅读，会尽量避免术语使用，且不会深入探讨数学转换等细节，如有疏漏，敬请谅解。

2012年1月，加州大学伯克利分校教授AlessandroChiesa与人合作撰写了SNARK的论文，提出了术语zk-SNARK。

zk-SNARK，全称Zero-Knowledge-SuccinctNon-InteractiveArgumentofKnowledge，是使用了ZK技术的一种证明系统。需要注意的是，SNARK是一类方案的名称，有很多不同的组合方法都可以实现SNARK。

零知识（Zero-Knowledge）：只有证明者知道的内容将会被隐藏，除了证明者，其他任何人都无法看到。

简短（Succinct）：生成的证明小，验证时间快。

非交互性（Non-Interactive）：证明者和验证者之间交互很少，甚至没有。

论证（Argument）：验证者的验证只对计算能力受限的证明者有效，因为拥有超强计算能力的证明者可以伪造证明，也就是说，系统具备计算可靠性。

知识（Knowledge）：证明者只有知道一些验证者不知道的信息才能计算出证明。

zk-SNARK要解决的是“计算验证问题”，即验证者能否在不知道证明者隐私的情况下，高效地验证计算结果。

下面将以zk-SNARK的简化版构建流程来说明该系统是如何结合零知识达到高效验证的。

zk-SNARK的构建

将待证明问题转化为多项式

简单来说，SNARK的思路是将证明陈述是否成立转换成证明多项式等式是否成立。

整个转换过程：待求证的问题➡算术电路➡R1CS➡多项式➡多项式之间的转换

待求证的问题➡算术电路

要通过计算证明一个问题是否为真，首先就要将待证明的问题转化成一个计算问题，而任何计算都可以描述为一个算术电路。

算术电路通常由常数、“加法门”、“乘法门”组成，通过门的叠加，我们可以构建出复杂的多项式。

上图中的算术电路构建的多项式为：（Inp1+Inp2）*（-1）=Output

现实中的问题要转为算术电路极其复杂，我们可以将之简单理解为：输入一些内容，内容经过电路转化，最终输出一个结果。即：

基于算术电路的概念，我们构造一个用于生成证明的算术电路，即：

该电路中包含了两组输入，公开输入x和秘密输入w。公开输入x意味该内容是待证明问题的固定值，验证者和证明者都知晓，秘密输入w则意味着该内容只有证明者知晓。

我们构建的算术电路为C(x,w)=0，即通过电路输入x与w，最终的输出结果为0。证明者和验证者知道电路输出为0，且公有输入为x的情况下，证明者需要证明自己知道秘密输入w。

算术电路➡R1CS

我们最终需要一个多项式，但算术电路不能直接转化为多项式，需要R1CS作为二者间的媒介，故先将算术电路转换为R1CS。

R1CS，全名为Rank-1ConstraintsSystem（一阶约束系统），是一种描述电路的语言，本质上是一种矩阵向量方程。具体来说，R1CS是由三个向量(a,b,c)组成的序列，R1CS的解是一个向量s，其中s必须满足方程：

其中.代表内积运算。

此间具体的数学转换可以参见Vatalik：QuadraticArithmeticPrograms:fromZerotoHero

我们只需要知道，R1CS的作用是对算术电路中的每个门的描述进行限定，使得每个门之间的向量满足以上关系。

R1CS➡多项式

在得到R1CS这个媒介后，我们就可以将其等价转换成多项式。

矩阵和多项式之间可以进行如下图所示的等价转换：

多项式

转化为矩阵

根据上述等价转换的性质，对于满足R1CS的矩阵，我们可以使用拉格朗日插值法，还原出多项式每一项系数，基于这个关系，我们可以将R1CS矩阵推导为多项式关系，即：

注：A,B,C分别代表一个多项式

一个多项式对应我们想要证明的问题所对应的一个R1CS矩阵约束，通过以上转化，我们可以知道，多项式之间满足以上关系，就说明我们的R1CS矩阵是正确的，从而说明证明者在算术电路中的秘密输入也是正确的。

到这我们的问题就简化为：验证者随机挑选一个数x，让证明者证明A(x)*B(x)=C(x)成立，如果成立，说明证明者的秘密输入正确。

多项式之间的转换

复杂的算术电路中，有成千上万个门，我们需要对每个门验证其是否满足R1CS约束。换句话说，我们需要验证数次A(x)*B(x)=C(x)等式成立，但是逐次单独验证的效率太低，如何能做到一次性验证所有门的约束的正确性？

为了方便理解，我们引入一个P(x)，令P(x)=A(x)*B(x)–C(x)

我们知道，任意的一个多项式只要它有解，就可以将它分解成线性多项式。故我们将P(x)拆分为F(x)和H(x)，即：

然后将F(x)公开，这就意味着存在一个H(x)=P(x)/F(x)，从而我们要验证的多项式最终转变为：

A(x)*B(x)–C(x)：包含多项式的系数，只有证明者知，即秘密输入。

F(x)：一个公开的多项式，验证者和证明者皆知，即公开输入。

H(x)：证明者通过计算得知，验证者不可知。

而最终要证明的问题为：多项式等式A(x)*B(x)–C(x)=F(x)*H(x)，在所有x上都成立。

现在只需要验证一次多项式就可以验证所有约束是否满足矩阵关系。

到这里我们就完成了将待证明的问题转化成只需要验证一次的多项式，实现了系统的简洁性。

但是这个实现的简洁性是让验证者的验证时间缩短，那证明大小呢？

简单来说，在证明协议中，使用的是Merkle树的结构，这有效的降低了证明的大小。

整个转换过程完成以后，自然而然的会产生两个问题：

为什么要转换成多项式？

因为多项式实现了证明的简洁性。零知识证明的问题就是验证计算满足多个约束的问题，而多项式可以一个点验证多个约束。换句话说，验证者本来要验证n次才能确认的问题，现在只需要验证一次就能极大概率地确认证明的正确性。

为什么验证多项式上的一个点，就能确定两个多项式A(x)*B(x)–C(x)=F(x)*H(x)成立？

这是由多项式的特性决定的，即：一个多项式在任意点的计算结果都可以看做是其唯一身份的表示。对于两个多项式，它们只会在有限的点上相交。

对于上述的两个d阶多项式：A(x)*B(x)–C(x)和F(x)*H(x)，如果它们不相等，它们最多只会在d个点上相交，也就是在d个点上的解相同。

完成了多项式的转换，我们就要进入多项式证明阶段。

证明多项式成立

为了便于阐述，我们采用多项式P(x)=F(x)*H(x)。

现在，证明者要证明的问题是：在所有x上，P(x)=F(x)*H(x)。

证明者和验证者对以上多项式的验证过程如下：

验证者选择随机挑战点x，假设x=s；

证明者收到s后，计算P(s)和H(s)，并把这两个值给验证者；

验证者先计算F(s)，再计算F(s)*H(s)，并判断F(s)*H(s)=P(s)是否成立，若成立则验证通过。

但是我们仔细思考就会发现以上流程存在一些问题：

证明者能够知道整个等式的信息，如果收到随机点s，他能计算出F(s)，然后构造出一对假的P(x)和H(x)，使得P(s)=F(s)*H(s)，以此欺骗验证者。

证明者不使用验证者给出的s计算F(s)和H(s)，而是用其他值计算，以此欺骗验证者。

验证者收到的值是由公共输入和证明者的隐私输入一起计算出来的，如果验证者算力极大，可以破解证明者的隐私输入。

针对上述问题，我们进行以下优化：

验证者在选取了随机点s后，对s进行同态加密，同态加密意味着加密后计算的解=计算后加密的解；在这种加密形式下，证明者能够计算出解，但不能构造假的P(x)和H(x)。

在验证者选择挑战点s时，再选取一个随机参数λ，额外生成一个s和λ之间的线性关系。验证者把同态加密后的s和λ都发给证明者。待证明者将证明发回，验证者除了验证证明是否为真，还需要验证随机参数λ与s之间的关系。

针对验证者可破解秘密输入的问题，我们就可以引入ZK。纵览整个证明，我们可以发现在验证过程中，证明者发给验证者的只有计算出的多项式的值，验证者可以通过值倒推出多项式的系数，即证明者的秘密输入。为了防止验证者倒推，我们可以从R1CS推出多项式A、B、C的时候，多选取两个随机数并增加一组取值，这样还原出来的多项式比原来的多项式多1阶，从而让验证者无法从加密后的多项式中获取原多项式的信息，以此实现ZK。

优化以后我们发现证明系统依旧需要验证者和证明者之间进行交互，如何才能实现非交互？

实现非交互

为了实现非交互，SNARK引入了可信设置（Setup）。

换句话说，在证明开始前，将原本属于验证者的选择随机挑战点的权力交给一个可信的第三方，第三方选择了随机参数λ后，将加密后的λ放在R1CS电路中，以此生成CRS（CommonReferenceString，公共参考字串）。验证方能从CRS中获取属于自己的Sv，证明方能从CRS中获取属于自己的Sp。

需要注意的是，λ在生成Sv和Sp后，需要被销毁，若λ被泄露，可能被用来通过虚假验证伪造交易。

zk-SNARK工作流程

在明白SNARK的构建流程后，基于我们构造的可生成证明的算术电路，zk-SNARK的证明流程如下：

Setup:(Ccircuit,λ)=(Sv,Sp)

通过电路C和随机参数λ，生成后续证明者和验证者使用的随机参数Sv、Sp。

Prove(Sp,x,w)=Π

证明者通过随机参数Sp，公共输入x，秘密输入w，计算出证明Π。

Verify(Sv,x,Π)==(∃ws.t.C(x,w))

验证者通过随机参数Sv，公共输入x和证明Π来验证是否存在C（x,w）=0。同时，验证证明是否是通过电路C计算得出。

到此，我们就完成了整个zk-SNARK的讲解，下面来看看实际运用的案例。

案例：以Scroll的zkRollup为例

证明系统的作用是让证明者说服验证者相信一件事；

对于zk证明系统而言，是要让验证者相信由zk算法计算出的Zero-KnowledgeProof（零知识证明）为真。

我们以Scroll的zkRollup为例来说明zk证明系统的运行。

Rollup是指链下计算，链上验证。对zkRollup而言，交易在链下执行后，证明者需要对交易执行后产生的新的状态根生成zk证明，再将证明传到L1Rollup合约进行链上验证。

需要注意的是，在zkRollup中存在两类区块：

L1Rollup区块：提交到以太坊的区块

L2区块：用户在L2上提交的交易打包而成的区块

以下是Scroll的zkRollup的工作流程：

用户在L2发起交易，Sequencer检索到交易，在链下执行交易并生成L2区块和新的状态根；同时将交易数据和新的状态根提交给以太坊上的Rollup合约（提交交易数据是为了实现数据可用性）；

当L2区块生成时，Coordinator会从Sequencer那收到该区块的执行轨迹，然后将该轨迹随机分配给任意一个Roller；

Roller将接收到的执行轨迹转换为电路，且为每个电路生成有效性证明，然后将该证明发回给Coordinator；

每生成k个L2块，Coordinator就会发送一个聚合任务给另一个Roller，以将k个块的证明聚合为单个聚合证明；

Coordinator将单个聚合证明提交给Rollup合约，Rollup合约结合之前提交的状态根和交易数据一起验证聚合证明，验证通过则相应的区块就被视为在Scroll上最终确定。

从以上流程可以看到，Roller是该系统中的证明者，Rollup合约是验证者。Roller对在链下执行的交易生成一个zk证明；Rollup合约验证该证明，若验证通过，Rollup合约就会直接采纳提交的状态根作为自己新状态根。