通用zkRollup技术的核心——zkVM原理简介

Rollup是一类区块链二层网络扩容方案。在Rollup方案中，项目的运行方会在被扩容的主链（即Layer 1）链下运行一个相对独立的 Layer 2 平台。用户可以在Layer 2 平台上执行合约或与其他用户进行交易。

Layer 2 平台的安全性由其依赖的 Layer 1区块链保证。当Layer 2中产生一个新的区块时，区块中的Layer 2 交易信息以及这些交易处理后的Layer 2状态摘要会被打包为Rollup交易发布在Layer 1链上。具体的交易执行及状态变更在主链下的Layer 2平台上进行，L1只需要对L2状态转换的正确性进行验证。由于验证状态转换正确性的代价远小于在L1执行这些交易，因此L2可以实现对L1平台的扩容。L2平台可以在具有和L1同等安全性的前提下，提供相比于L1更高的交易吞吐量及更低廉的交易费用。

相比于其他的链下交易方案，Rollup有两个特点：

根据主链对 Layer 2 状态更新的验证方式来划分，目前主要有两类Rollup技术方案。

一类是Optimistic Rollup。在这类方案中，主链合约不直接对Layer 2 提交的新状态进行验证，而是为每个被提交的新状态准备一个挑战期。由于Rollup会将所有的交易信息提交到主链并公开，因此任何人都可以对该状态更新进行验证（特别是当该状态更新涉及到自己的钱包时）。如果新状态是错误的，那么验证者可以针对该错误状态产生一份欺诈证明，并在挑战期内提交，从而使该错误的状态更新被无效化。

另一类Rollup方案是zk Rollup。在这类方案中，Layer 2 的运行者在执行 Layer 2 状态更新后，要为状态更新的正确性提供一份零知识证明，并随着状态更新一同提交到主链上。主链上的合约会对该证明进行验证以确定状态更新的正确性。

相比于Optimistic Rollup方案，zk rollup不需要设置漫长的挑战期来最终确定Layer 2交易，可以更快的被确认。除此之外，zk Rollup也不需要依赖网络中存在诚实的验证者总会在欺诈发生时及时提交欺诈证明的假设。但同时zkRollup也存在着零知识证明技术计算成本较高、技术较为复杂、开发难度大等问题，阻碍着zkRollup技术在Rollup中的实际落地。而随着近两年零知识证明技术的进一步发展，这些阻碍正在被逐渐克服。zkRollup技术在Layer 2市场中开始占越来越大的份额。

如下图所示，在Rollup二层扩容领域里，zkRollup已经占据了一半多的江山，并且正在快速发展中。

图片来源：https://l2beat.com/scaling/summary

数据获取日期: 2024/01/18

zkRollup在发展过程中，主要有两个发展阶段。第一类是非通用的zkRollup，而第二类则是能够执行图灵完备的任意合约的通用zkRollup。

这两类zkRollup技术的区别主要在于Layer2平台在交易中执行的是由平台提供方编写的有限的专用逻辑还是由用户编写的任意的智能合约逻辑。

在非通用的zkRollup项目（如上图中第8位的zkSync Lite）中，用户只能进行少数几种交易操作，如进行FT转账、支付、swap以及NFT转移等。这些交易的交易逻辑也只能由项目方定义并实现。

通过这类zkRollup项目，我们可以通过比以太坊主网中低的多的手续费进行转账交易，并获得更高的交易吞吐量。但如果我们想要在链上尝试一下某个有趣的合约，那么我们将无法得偿所愿。

为什么专用zkRollup不能让用户部署并使用自己的智能合约呢? 这就要回到zkRollup本身的证明架构上来。

为了保证L2的状态转移是正确且可信的，在zkRollup中，所有的L2状态转移逻辑都需要编写为零知识证明电路，并在L1合约中进行验证。只有通过验证的状态才能被L1接受，并最终完成Rollup。这一过程要求zkRollup平台将所有的交易执行逻辑都在零知识证明电路中得到验证。然而，在零知识证明电路中支持任意的合约逻辑执行是一个难题（在后文中将解释为什么这是困难的）。因此，早期的zkRollup项目往往只能支持有限的几种逻辑较为简单的交易。

只能执行几种固定简单交易显然不能满足我们对与zkRollup的期待。幸运的是，zkVM技术解决了在零知识证明电路中证明一段任意的图灵完备的代码执行的难题，使得通用zkRollup平台成为了可能。接下来，本文将介绍zkVM的实现原理，让读者明白通用zkRollup技术中这最核心的部分是如何运转的。

在介绍zkVM的原理前，我们将首先对零知识证明技术进行一个简要的介绍。在这里我们不需要对零知识证明的底层数学原理有详细的了解，只需了解零知识证明能够做什么，是如何被使用的，以及零知识证明特殊的证明电路带来的限制。

零知识证明在zkRollup中的作用是证明Layer 2交易被正确的执行，并正确的更新了Layer 2的状态。

为了实现这个目的，zkVM电路需要证明部署在Layer 2上的任意智能合约被正确的执行了。在介绍zkVM的原理前，首先需要介绍一下零知识证明作用及的工作过程。

1、为什么需要零知识证明

零知识证明这一密码学原语指一类可以使证明者能够在不向验证者提供任何额外的信息的情况下，使验证者相信某个论断是正确的协议。

零知识证明具有三个核心性质：

根据零知识证明的完备性，当证明者完成一段复杂的运算后，他可以生成一个证明使验证者相信，输入数据经过得到的结果是执行者提供的结果。而零知识证明的可靠性则保证了当执行者提供错误的执行结果时，无法生成有效的证明。

因此，通过零知识证明的完备性和可靠性，我们可以放心的将这些复杂的计算过程交给其他人计算，并通过相对较为简单的验证过程来验证计算是否正确，而无需对计算外包者的信任。

在零知识证明的三个核心性质之外，目前广泛应用的zk-SNARK类零知识证明算法还具有简洁的特点。这一特性意味着对于任意复杂的逻辑进行零知识证明，生成的证明大小及证明验证时间均为一个较小的固定值。这使得zk-Rollup将状态更新计算移至链下进行，链上只对运算正确性进行验证的扩容路线成为了可能。

2、零知识证明的过程

接下来本文将以下面这个简单的运算作为例子说明零知识证明的过程。

为了方便说明零知识证明中零知识性，我们将变量a和c设置为此次零知识证明的公开值，b为只有证明者知道的秘密输入。由于我们的运算十分简单，验证者可以很容易的从公开值中推算出秘密输入的值。这不影响零知识证明方法本身的零知识性，因为零知识证明只保证验证者无法从证明过程中获得秘密输入的信息。

证明者在进行证明时，首先要为a,b各自选择一个值作为输入，计算出c的值。在这里，我们设a = 3, b = 2，则c = 16。在完成所有的计算后，证明者就可以为这些值和运算生成零知识证明。

在完成证明后，证明者会将证明的公开输入（即a和c的取值）以及零知识证明交给验证者。

验证者在得到证明后，通过对零知识证明的验证，可以相信证明者使用了一个秘密输入b，使上面的式子在a = 3，c = 16（即公开输入值）的情况下成立，且无法获得公开输入（a = 3，c = 16）以外的任何信息。

接下来本文将介绍具体的证明过程。当我们需要通过零知识证明方法证明自己所需的运算时，首先需要将运算表示为零知识证明算法所能接受的算术电路形式。算术电路是一种图灵完备的计算表示方式。就如同其名字所说，算术电路是由进行算术运算的运算门构成的运算电路。在我们的例子中，转化的结果如图所示。你可能注意到在展开的算术电路中，除了我们提到的公开输入a,c以及秘密输入b以外，还多了两个值d和e。它是运算过程中的中间变量。

我们可以认为算术电路中的每一条线都是一个值，它可能是电路的公开输入，秘密输入或者中间变量。在将运算展开为算术电路后，每一个中间变量都将有其自身的一席之地，并被用在证明的过程中。它们与输入的唯一区别是它们的值不会由证明者直接输入，而是由算术电路中的其他输入值确定。

我们可以将算术电路看作两部分，一部分是电路中出现的所有数值，另一部分是这些值之间的关系（即约束）。

我们通常将电路中的公开输入称为statement（在我们的例子中是a和c），而将其他所有的值，包括秘密输入（b）以及中间变量（d和e）称作witness。

根据电路的逻辑，当我们拥有作为公开输入的statement和作为秘密输入的witness后，就可以计算出电路中全部的witness。

因此算术电路的门电路也可以表示为下面的形式：

statement:a,cwitness:b,d,econstraint:d = a * ae = b + 5c = d + e

在需要证明的电路被算数化后，零知识证明算法需要对电路的约束进行处理，其转化为算法所需的形式以进行证明的生成与验证。处理完成后，电路就会产生一个与电路大小无关的固定长度的VK（Verify Key）验证密钥。验证者通过验证密钥就可以对对应电路的零知识证明进行验证。验证密钥在一定程度上有些类似于对电路的承诺。如果约束发生任何变化，对应的验证密钥也会发生变化。

在实际应用中，零知识证明的使用者想需要的逻辑编写为zk电路源代码，经过审计产生一个对应的VK。这个VK会被交给验证者。证明方证明的公开输入以及产生的证明一起提交，验证者就能够验证这些公开输入是否符合这些约束。在本例中，证明者可以可以拿a、b和c值产生一个证明。验证者可以在不进行这个运算的情况下去验证a2 + b 是否等于C的这个值。

3、零知识证明电路的限制

虽然zk电路是图灵完备的，能够表示任意运算，但由于需要将运算转换为算术电路这一特殊的表示形式，算术电路的编写会有一些额外的限制。

在我们更为熟悉的计算机程序中，我们可以通过if else来控制程序运行的分支。程序中只有被选中的分支会被执行。而在零知识证明过程中，运算被展平为电路，并不存在执行路径及控制流的概念。因此我们无法在算术电路中选择某一条分支来执行。

当然这不意味着我们不能在电路中使用分支和选择。只是在电路中，所有的分支，不论是否被选择都将被执行，并参与证明的产生。分支的选择只影响哪一个分支的结果会被输出到下一个变量中。

以下面的运算为例：

if (flag) {  c = x + x} else {  c = x * x}

当该运算被转换为算术电路时，会被转化成下面的约束。很明显，电路中会增加两个新的witness temp1及temp2。此外x+x的值与x*x的值都将被运算。

即，zk电路中所有的分支及逻辑，不论是否被执行都会被运算。

temp1 = x + xtemp2 = x * xc = flag * temp1 + (1-flag) * temp2

因为这些限制，要在零知识证明电路中支持条件选择是较为困难的。如何在零知识证明中证明执行路径多变的智能合约逻辑是一zk虚拟机的主要挑战。

零证明任意程序的执行——在电路中证明通用状态机

图片来源：

https://github.com/0xPolygonHermez/zkevm-doc/blob/main/mkdocs/docs/zkEVM/zkProver/Verifiable-Computations/figures/simple-state-machine-overview-PC.pdf.png

我们通过一个通用状态机的模型来描述VM。一个VM是一个会随着指令的进行进行状态转换的状态机。我们以一个十分简单的状态机例子来说明虚拟机是如何被零知识电路证明的。

我们设这个通用状态机有通用状态寄存器（A和B），此外还有一个Program Counter寄存器存储当前指令的序号。

下图是一个ZK虚拟机证明电路的基本流程：

States 0可认为是这个虚拟机在运行之前的最初的状态。初状态在经过总共m条指令之后，达到了最终的状态m。除了初状态外，这个虚拟机还有两个制度的输入表：

• Bytecode Table: 存储里状态机中执行的程序。

• I/O Table: 存储了虚拟机执行过程中会产生的所有输入及输出。

在图中，我们将第n条指令的执行过程抽出展示在左边。状态机中的状态States n在执行第n条指令后转换为States n+1。同样的电路经过m次重复后就实现了对vm中m条指令的执行。

这里有两个问题：

一是如何在一段固定的电路中执行不同的指令？在执行合约的字节码时，无法确定被执行的第n条指令是什么，因此无法确定这里的实际电路逻辑。

二是如果需要执行的指令数量不为m时应如何证明？

对于第一个问题，解决方法是在电路中将所有可能的指令执行逻辑都实现出来。随后使用一个Selector，根据指令选择其中的一个作为下一个状态。类似于前面介绍的专用电路中的if-else。

对于第二个问题，我们不能直接通过改变电路中的指令数量。因为电路中的每一条指令都需要增加一段独立的电路来实现。如果增减指令的数量，那么电路就会发生变化，对应的验证密钥也会发生变化。这就无法实现在一个固定电路中实现对仍以逻辑验证的要求。

为了解决这个问题，可以向指令集中增加一个空指令。也因此，在每一个固定电路能够执行的指令的条数是有上限的。可以将zkVM的电路看作是一个有固定数量指令槽位的容器。如果需要执行的指令更多，就需要一个更大的电路。在实际证明中，可以根据需要，去选择一个合适大小的电路。

1、证明一条基本指令

这里以几个基本的运算指令为例，介绍电路中基本的指令是怎么证明的？

图片来源：

https://github.com/0xPolygonHermez/zkevm-doc/blob/main/mkdocs/docs/zkEVM/zkProver/Verifiable-Computations/figures/simple-state-machine.pdf.png

图中是这个指令证明电路的流程图。下面的公式是实现证明的电路约束。

这两条约束可以为通用寄存器A和B实现对右上角列表中的几条基本指令进行证明。这几条证明可以将输入表或指令立即数中的值载入到寄存器中，或者将A B寄存器中的值相加并写到寄存器里。

通过这个图我们可以看出，为了构建对状态变化的约束，电路引入了一些辅助控制的状态：

这些辅助寄存器和通用寄存器间的计算逻辑被下面的公式实现。有兴趣的读者可以将对应的值代入约束公式中检验。可以看出，通过这两条约束，就可以实现基本的加法算数指令。如果需要更多的运算，就需要增加更多的指令约束。

回到基本流程的图，我们可以将这一小节中的运算电路看作总流程图中的一个指令。Selector会选择是否将它产生的结果作为状态机下一个被采用的状态。这一小节中的电路需要的辅助状态则通过PC寄存器指向的指令产生。

指令读取由一个专用的查表电路实现，这个查表电路能对通过index从一个固定表中取出一段数据做出证明。因此zkVM的电路能够对虚拟机执行了PC指定的指令的状态转移做出证明。

2、证明条件判断与控制流跳转

状态机能够执行复杂逻辑离不开条件与跳转指令。在实际的合约中，我们需要经常处理根据条件改变执行路径的逻辑，因此需要这样的电路。

在这需要说明的是，zkVM电路并不是一个实际执行合约逻辑并计算产生结果的模块。zkVM电路做的事实际上是对合约逻辑计算过程进行的证明。因此在进行证明时需要将实际执行的指令序列流程填充在电路中，通过电路去验证这个跳转发生的条件是否成立，随后证明执行的指令流是否进行了正确的跳转。

这里首先介绍条件判断的证明：

以判断第i条指令中的操作数是否等于0为例。我们为判断的结果增加一个辅助状态isZero。如果被判断的值为0，那么辅助状态isZero的值就为1，如果被判断的值是0以外的任何的值，那么isZero就为0。

这一过程通过图上的两条式子约束。

这一约束的成立与零知识证明中使用的椭圆曲线的数学特性有关。零知识证明电路中的每一个值都是椭圆曲线上一个有限域中的元素。如果其值不为0，必然存在一个逆元与其本身相乘得到1。使用这个性质，通过上图的两个约束，就可以验证某个值是否为零，并将其转换为一个辅助状态。

当有了这个isZero这个条件的辅助状态之后，就可以进行对条件跳转指令的证明:

再回到基本流程图，如果目前的指令是是一条条件跳转指令。它首先会进行isZero的检查，确定是否符合跳转条件，随后会对PC的值做修改。在更新完PC的值后，下一条指令执行时首先会根据PC做一次查表，并找出跳转后的指令执行。

3、IO及复杂操作

在使用通用状态机证明电路时，为了能够正确处理状态转换，需要在一次状态转换中为每一个支持的指令增加对应的控制状态与约束。这些状态值与约束的数量还需要乘上zkVM中支持的指令数目。即使在zkVM实际执行的程序中没有进行任何操作（全是NOOP），这些状态值及约束的检查也无法省去。

因此使用本文前半部分的通用状态机电路来执行复杂运算是非常低效的。如果用这些方法实现复杂运算，其性能是很难接受的。此外，用通用状态机电路来执行复杂的指令或直接与外部交互也是很难做到的。

为了解决这个问题，在实际的zkVM实现中，都采用了通用状态机电路与专用证明电路分别证明程序的一部分，最后再进行聚合证明的解决方案。

图片来源:

https://trapdoortech.medium.com/zero-knowledge-proof-deep-into-zkevm-source-code-evm-circuit-21d0a47f63aa

https://github.com/0xPolygonHermez/zkevm-doc/blob/main/mkdocs/docs/zkEVM/zkProver/State-Machines/Overview/figures/plook-ops-mainSM-copy.png

上图中左侧是scroll项目的电路架构图，右下角是polygon的电路架构图。他们都采用了类似由上角的图中所展示的思路。

通用状态机负责证明程序的执行逻辑控制。在大部分合约中，这一部分逻辑的实际执行时间很小，因此通过低效的通用状态机来实现证明，其效率也可以接受。

类似哈希，MPT树运算，外部输入数据等较为固定的复杂运算则由专用电路生成证明。

通用状态机及专用证明电路间使用查找表进行交互。状态机电路每一次调用这些运算，为证明生成witness的模块都会将调用的参数以及计算结果写在查找表里。因此状态机电路对这些运算的调用在其证明中简化为一次查表证明。

在查找表中的每一次调用与返回值的正确性都通过专用电路约束并证明。

最后，电路中的复制约束会连接状态机电路，专用电路及查找表，检验查找表中的每一项是否都由对应的专用电路证明，并最终生成一个对完整区块的证明。

L1合约只需对这个聚合证明进行检验，就可以确认整个虚拟机执行过程的正确性。