zkRollup原理与架构

进阶5/7/2024, 9:53:40 AM
随着zk虚拟机的发展和成熟,支持任意智能合约的图灵完备执行已经成为可能。zkRollup的潜力将被真正释放,实现打破区块链三难困境的愿景。

Rollup 概述

Rollup 是一类区块链 Layer 2 扩展解决方案。在 Rollup 方案中,项目运营商在扩展的主链(即 Layer 1)之下运行一个相对独立的 Layer 2 平台。用户可以在 Layer 2 平台上执行合约或划转代币。

Layer 2 平台的安全性由其所依赖的 Layer 1 区块链来保证。当 Layer 2 中生成新的区块时,来自 Layer 2 区块的交易信息以及 Layer 2 的交易后状态根将被捆绑为 Rollup 交易并发布在 Layer 1 链上。实际的交易执行和状态变化都是在主链下面的 Layer 2 平台上处理的,Layer 1 只需要验证 Layer 2 状态转换的正确性。由于验证状态转换正确性的成本远低于执行这些Layer 1,Layer 2上的交易可以实现Layer 1平台的扩展。与 Layer 1 相比,Layer 2 平台可以提供更高的交易吞吐量和更低的交易成本,同时保持同等的安全性。

相比其他链下交易方案,Rollups 有两大特点:

  • Layer 2 状态数据的可用性是通过将其存储在主链上来解决的。Layer 2 平台在主链上的区块中记录所有交易信息或完整的 Layer 2 状态变化。如果 Layer 2 状态丢失,任何人都可以从主链上存储的信息中恢复丢失的状态。
  • Rollup方案中,打包存储在主链上的 Layer 2 状态根变化需要通过某种方式在主链上进行验证。经过验证后,Layer 2 的状态将被锁定在 Layer 1 主链上。因此,在安全验证方案的条件下,Layer 2 可以享受与 Layer 1 相同级别的安全性。

基于主链对 Layer 2 状态更新的验证方式,目前Rollup技术方案主要有两类。一是乐观汇总(Optimistic Rollup)。在此类方案中,主链合约不会直接验证 Layer 2 提交的新状态,而是为每个提交的新状态准备一个质疑期。由于Rollup将所有交易信息提交到主链并公开,因此任何人都可以验证状态更新(尤其是当更新涉及自己的钱包时)。如果新状态不正确,验证者可以针对该错误状态生成欺诈证明并在质疑期内提交,从而使不正确的状态更新无效。

另一种 Rollup 解决方案是 zk Rollup。在此类方案中,执行 Layer 2 状态更新后,Layer 2 的操作者必须提供状态更新正确性的零知识证明,并将其与状态更新一起提交到主链。主链上的合约将验证证明以确定状态更新的正确性。

与乐观汇总方案相比,zk Rollup 不需要漫长的质疑期来最终确认Layer 2 上的交易,并且可以更快地得到确认。此外,zk Rollup 并不依赖于这样的假设:网络中总会有诚实的验证者,当欺诈发生时,他们会及时提交欺诈证明。但同时,zk Rollup也面临着零知识证明技术计算成本高、复杂度高、开发难度大等问题,这些阻碍了zk Rollup技术在Rollups中的实际落地。随着近两年零知识证明技术的进一步发展,人们正逐渐克服这些障碍。zk Rollup 技术开始在 Layer 2 市场占据越来越大的份额。

如下图所示,在 Rollup Layer 2 扩展领域,zkRollup已经占据了一半以上的领地,并且正在快速发展。

来源https://l2beat.com/scaling/summary

数据检索日期:2024年1月18日

从专业化 zkRollup 到通用化 zkRollup

zkRollup的发展过程主要经历了两个阶段。第一种是非通用的 zkRollup,第二种是能够执行图灵完备任意合约的通用 zkRollup。

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

在非通用的 zkRollup 项目中(如上图中排名第 8 的 zkSync Lite),用户只能进行少数类型的交易操作,如 FT(可替代代币)转账、支付、互换和 NFT(不可替代代币)转账。这些操作的事务逻辑只能由项目所有者定义和实现。

通过这样的zkRollup项目,我们能以比以太坊主网低得多的费用进行转账,并获得更高的交易吞吐量。然而,如果我们想在链上尝试一些有趣的合约,我们将无法做到。

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

为了确保 Layer 2 的状态转换正确且可信,在zkRollup中,所有 Layer 2 状态转换逻辑都需要编写为零知识证明电路并由 Layer 1 合约进行验证。只有通过验证才能被 Layer 1 接受并最终完成Rollup。这个过程需要zkRollup平台的所有交易执行逻辑都在零知识证明电路中得到验证。然而,在零知识证明电路中支持任意合约逻辑的执行是一个挑战(造成这种困难的原因将在本文后面解释)。因此,早期的 zkRollup 项目往往只支持有限数量的相对简单的交易。

只能执行固定数量的简单交易显然不符合我们对 zkRollup 的期望。幸运的是,zkVM(零知识虚拟机)技术解决了在零知识证明电路内证明任意图灵完备代码执行的困难,使得通用的 zkRollup 平台成为可能。接下来,本文将介绍zkVM的实现原理,让读者了解通用zkRollup技术中最核心的部分是如何运作的。

zkVM的实现原理

在介绍zkVM原理之前,我们先简单介绍一下零知识证明技术。在这里,我们不需要详细了解零知识证明的底层数学原理,而是只需了解零知识证明可以做什么、如何使用它们以及其专用证明电路所施加的限制就足够了。

零知识证明简介

zkRollup 中的零知识证明用于证明 Layer 2 上交易已正确执行以及 Layer 2 状态已正确更新。

为了实现这一目的,zkVM电路需要证明部署在 Layer 2 上的任何智能合约都已正确执行。在介绍zkVM的原理之前,我们需要先讨论一下零知识证明的作用及其工作原理。

为什么需要零知识证明

零知识证明是一种密码学原语,它允许证明者让验证者相信陈述的正确性,而无需向验证者透露任何其他信息。

零知识证明具有三个核心属性:

  • 完整性:如果要证明的陈述是正确的,诚实的验证者(即正确遵循协议的验证者)将被诚实的证明者确信这一事实。
  • 可靠性:如果要证明的陈述是错误的,则不诚实的证明者只有微乎其微的机会让诚实的验证者相信该陈述是正确的。
  • 零知识:除了陈述真实外,验证者无法从验证过程中获得任何其他信息。

凭借零知识证明的完备性,当证明者完成复杂的计算时,他们可以产生一个证明,使验证者相信从输入数据得到的输出数据是执行者提供的结果。零知识证明的健全性确保当执行者提供错误结果时,他们无法生成有效的证明。

因此,凭借零知识证明的完整性和健全性,我们可以放心地将这些复杂的计算外包给其他人,并通过相对简单的验证过程来验证计算是否正确,而不需要信任外包方。

广泛使用的zk-SNARK方案除了具备零知识证明的三大核心特性外,还具有简洁性的特点。这意味着对于使用零知识证明证明的任何复杂逻辑,生成的证明的大小和验证证明所需的时间都是固定的并且相对较小。这使得 zk-Rollup 能够将状态更新计算卸载到链下,只验证链上操作的正确性,从而使扩容解决方案变得可行。

零知识证明的过程

接下来,本文将以下面的简单计算为例,讲解零知识证明的过程。

c=a²+b+5

为了解释零知识证明中的零知识方面,我们将变量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。这些是计算过程中使用的中间变量。

我们可以将算术电路中的每条线视为一个值,它可以是公共输入、秘密输入或中间变量。将计算扩展为算术电路后,每个中间变量将有其位置并用于证明过程。它们与输入之间的唯一区别是它们的值不是由证明者直接输入,而是由算术电路中的其他输入值确定。

我们可以把算术电路看成两部分:一部分是电路中出现的所有数值,另一部分是这些值之间的关系(约束)。我们通常将电路中的公共输入称为陈述(在我们的示例中为 a 和 c),并将所有其他值,包括秘密输入 (b) 和中间变量(d 和 e)称为见证。

根据电路的逻辑,当我们有公共输入作为陈述,秘密输入作为见证时,我们就可以计算出电路中所有的见证值。

因此,运算电路的门电路也可以表示为以下形式:

陈述:

一个,c

证人:

乙、丁、乙

约束:

d = a * a

e = b + 5

c = d + e

当待证明的电路被算术化后,零知识证明算法需要处理电路的约束,并将其转换为算法所需的形式,以生成和验证证明。经过处理后,电路产生一个与电路大小无关的固定长度的验证密钥(VK, Verification Key)。验证者可以通过验证密钥来验证相应电路的零知识证明。验证密钥有点类似于对电路的承诺。如果约束条件发生变化,相应的验证密钥也会发生变化。

在实际应用中,零知识证明的使用者需要将自己需要的逻辑写入zk电路源代码中,并通过审计生成相应的VK。这个VK交给验证者。证明者证明的公共输入以及生成的证明一起被提交,验证者可以验证这些公共输入是否满足约束。在此示例中,证明者可以使用 a、b 和 c 的值生成证明。验证者无需执行此操作即可验证a2 + b是否等于C。

零知识证明电路的局限性

虽然zk电路是图灵完备的并且可以表示任何计算,但由于需要将计算转换为算术电路的特殊表示形式,因此在编写算术电路时存在一些额外的限制。

在我们比较熟悉的计算机程序中,我们可以通过if-else陈述来控制程序执行的分支。仅执行程序中选定的分支。然而,在零知识证明过程中,计算被扁平化为电路,并且不存在执行路径或控制流的概念。因此,我们无法选择在算术电路中执行的特定分支。

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

以下面操作为例:

If (flag) {

c = x + x

}else {

c = x * x

}

当这个运算转换成运算电路时,就会转换成如下所示的约束条件。显然,两个新见证人 temp1 和 temp2 将添加到电路中。此外,值x+x 和价值x*x 都会被计算。

也就是说,在 zk 电路中,所有分支和逻辑都将被计算,无论它们是否被执行。

temp1 = x + x

temp2 = x * x

c = 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 是一种状态机,在处理指令时转换状态。让我们用一个非常简单的状态机示例来说明如何通过零知识电路来证明虚拟机。

我们假设这个通用状态机具有通用寄存器(A 和 B),此外还有一个存储当前指令号的程序计数器寄存器。

执行指令前寄存器的状态

下图展示了ZK虚拟机证明电路的基本工作流程:

状态0可以认为是这个虚拟机运行前的初始状态。初始状态经过总共 m 条指令后,达到最终状态 m。除了初始状态之外,这个虚拟机还有两个常规输入表:

  • 字节码表:存储状态机中执行的程序。
  • I/O表:存储虚拟机执行过程中产生的所有输入和输出。

图中,第n条指令的执行过程被抽象出来并显示在左侧。执行第 n 条指令后,状态机的状态(状态 n)转换为状态 n+1。同样的电路,经过m次迭代,实现了vm中m条指令的执行。

这里有两个问题。

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

第二是如何证明要执行的指令数不是m?

对于第一个问题,解决方案是实现电路中所有可能指令的逻辑。然后使用选择器,根据指令选择其中一个作为下一个状态,类似于前面提到的专用电路中的 if-else。

对于第二个问题,我们不能直接改变电路中的指令数量。这是因为电路中的每条指令都需要独立的电路段来实现。如果指令数量增加或减少,电路就会改变,相应的验证密钥也会改变。这使得无法满足验证固定电路中任何逻辑的要求。

为了解决这个问题,可以在指令集中添加一条不会改变状态的noop指令。因此,每个固定电路可以执行的指令数量是有上限的。zkVM 的电路可以看作是一个具有固定数量指令槽的容器。如果需要更多指令,则需要更大的电路。实际证明中,可根据需要选择合适尺寸的电路。

证明一条基本指令

下面以一些基本的计算指令为例,说明电路中的基本指令是如何被证明的:

图片来源

上图为指令验证电路的流程图。下面的公式是证明的电路约束。

这两个约束可以证明右上角列出的通用寄存器A和B的几个基本指令。这些证明可以将输入表中的值或指令中的立即值加载到寄存器中,或者将寄存器 A 和 B 中的值相加并将它们写回到寄存器中。

从图中我们可以看到,为了构建状态变化的约束,电路引入了一些辅助控制状态:

这些辅助寄存器和通用寄存器之间的计算逻辑通过以下公式实现。有兴趣的读者可以将相应的值代入约束公式中进行验证。可见,有了这两个约束,就可以实现基本的算术加法指令了。如果需要更多的操作,则必须添加更多的指令约束。

回到基本流程图,我们可以将本节的计算电路看成是整个流程中的一条指令。选择器将选择它产生的结果是否是状态机要采用的下一个状态。本节电路所需的辅助状态由PC寄存器指向的指令产生。

指令检索是通过专门的查找电路实现的,可以证明通过索引从固定表中检索到一段数据。因此,zkVM电路可以证明PC指定的虚拟机执行的状态转换。

证明条件判断和控制流跳转

状态机执行复杂逻辑的能力依赖于条件和跳转指令。在实际合约中,我们经常需要处理根据条件改变执行路径的逻辑,所以这样的电路是必要的。

这里需要注意的是,zkVM 电路并不是真正执行合约逻辑并计算结果的模块。zkVM电路实际上所做的就是证明合约逻辑的计算过程。因此,在证明时,需要将实际执行的指令序列过程填充到电路中,通过电路验证是否满足本次跳转的条件,进而证明执行的指令流程做出了正确的跳转。

首先我们介绍一下条件判断的证明:

以判断第i条指令中的操作数是否为零为例。我们为判断结果添加一个辅助状态isZero。如果判断值为0,则辅助状态isZero的值为1;如果判断的值为0以外的任何其他值,则isZero为0。

这个过程受到图中两个公式的约束。

该约束的有效性与零知识证明中使用的椭圆曲线的数学特性有关。零知识证明电路中的每个值都是椭圆曲线上有限域内的元素。如果它的值不为 0,则必须存在一个逆元素,该元素与自身相乘时结果为 1。使用此属性,结合图中的两个约束,可以验证一个值是否为零并将其转换为辅助状态。

一旦我们有了这个 isZero 条件辅助状态,我们就可以继续条件跳转指令的证明:

回到基本流程图,如果当前指令是条件跳转指令。它首先进行isZero检查,判断是否满足跳转条件,然后修改PC的值。更新PC的值后,执行下一条指令首先会根据PC进行查找,找到跳转后的指令。

I/O 和复杂操作

当使用通用状态机证明电路时,为了正确处理状态转换,需要在单个状态转换期间为每个支持的指令添加相应的控制状态和约束。这些状态值和约束的数量还必须乘以 zkVM 支持的指令数量。即使zkVM执行的实际程序(都是NOP)中没有执行任何操作,这些状态值和约束检查也不能省略。

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

为了解决这个问题,zkVM 的实际实现通常使用通用状态机电路和专用证明电路的组合来分别证明程序的各个部分,然后将证明聚合到一个解决方案中。

图片来源:1 2

左图是Scroll项目的电路架构,右下角的图是Polygon的电路架构。它们都采用类似的方法,如顶角的图表所示。

通用状态机负责证明程序的执行逻辑控制。在大多数合约中,这部分逻辑的实际执行时间很小,因此用低效的通用状态机来证明从效率上来说还是可以接受的。

更固定的复杂计算,如哈希、MPT树运算、外部输入数据等,都是通过专门的电路来证明的。

通用状态机和专用证明电路使用查找表进行交互。每次状态机电路调用这些操作时,生成证明见证的模块都会将调用参数和计算结果写入查找表中。因此,状态机电路中对这些操作的调用被简化为查找操作。

查找表中的每个调用和返回值的正确性都由专门的电路来约束和证明。

最后,电路中的复制约束连接状态机电路、专用电路和查找表,检查查找表中的每一项是否被相应的专用电路证明,最终生成完整块的证明。

Layer 1 合约只需要验证这个聚合证明即可确认整个虚拟机执行过程的正确性。

结语

零知识证明技术使得简单、快速地证明计算成为可能,为在不信任的环境中外包计算过程打开了大门。这项技术运用在区块链中,可以将执行从链上解放出来,让主区块链能够专注于去中心化和安全问题。但专门的零知识证明电路仅执行固定逻辑的特性限制了区块链上零知识证明的潜力,将早期 zkRollup 的功能限制在少数类型的交易上。

但随着zk虚拟机的发展和成熟,支持任意智能合约的图灵完备执行已经成为可能。 zkRollup的潜力将被真正释放,实现打破区块链三难困境的愿景。

声明:

  1. 本文转载自[ZAN],著作权归属原作者[ZAN and AntChain Open Labs],如对转载有异议,请联系Gate Learn团队,团队会根据相关流程尽速处理。
  2. 免责声明:本文所表达的观点和意见仅代表作者个人观点,不构成任何投资建议。
  3. 文章其他语言版本由Gate Learn团队翻译, 在未提及Gate.io的情况下不得复制、传播或抄袭经翻译文章。

zkRollup原理与架构

进阶5/7/2024, 9:53:40 AM
随着zk虚拟机的发展和成熟,支持任意智能合约的图灵完备执行已经成为可能。zkRollup的潜力将被真正释放,实现打破区块链三难困境的愿景。

Rollup 概述

Rollup 是一类区块链 Layer 2 扩展解决方案。在 Rollup 方案中,项目运营商在扩展的主链(即 Layer 1)之下运行一个相对独立的 Layer 2 平台。用户可以在 Layer 2 平台上执行合约或划转代币。

Layer 2 平台的安全性由其所依赖的 Layer 1 区块链来保证。当 Layer 2 中生成新的区块时,来自 Layer 2 区块的交易信息以及 Layer 2 的交易后状态根将被捆绑为 Rollup 交易并发布在 Layer 1 链上。实际的交易执行和状态变化都是在主链下面的 Layer 2 平台上处理的,Layer 1 只需要验证 Layer 2 状态转换的正确性。由于验证状态转换正确性的成本远低于执行这些Layer 1,Layer 2上的交易可以实现Layer 1平台的扩展。与 Layer 1 相比,Layer 2 平台可以提供更高的交易吞吐量和更低的交易成本,同时保持同等的安全性。

相比其他链下交易方案,Rollups 有两大特点:

  • Layer 2 状态数据的可用性是通过将其存储在主链上来解决的。Layer 2 平台在主链上的区块中记录所有交易信息或完整的 Layer 2 状态变化。如果 Layer 2 状态丢失,任何人都可以从主链上存储的信息中恢复丢失的状态。
  • Rollup方案中,打包存储在主链上的 Layer 2 状态根变化需要通过某种方式在主链上进行验证。经过验证后,Layer 2 的状态将被锁定在 Layer 1 主链上。因此,在安全验证方案的条件下,Layer 2 可以享受与 Layer 1 相同级别的安全性。

基于主链对 Layer 2 状态更新的验证方式,目前Rollup技术方案主要有两类。一是乐观汇总(Optimistic Rollup)。在此类方案中,主链合约不会直接验证 Layer 2 提交的新状态,而是为每个提交的新状态准备一个质疑期。由于Rollup将所有交易信息提交到主链并公开,因此任何人都可以验证状态更新(尤其是当更新涉及自己的钱包时)。如果新状态不正确,验证者可以针对该错误状态生成欺诈证明并在质疑期内提交,从而使不正确的状态更新无效。

另一种 Rollup 解决方案是 zk Rollup。在此类方案中,执行 Layer 2 状态更新后,Layer 2 的操作者必须提供状态更新正确性的零知识证明,并将其与状态更新一起提交到主链。主链上的合约将验证证明以确定状态更新的正确性。

与乐观汇总方案相比,zk Rollup 不需要漫长的质疑期来最终确认Layer 2 上的交易,并且可以更快地得到确认。此外,zk Rollup 并不依赖于这样的假设:网络中总会有诚实的验证者,当欺诈发生时,他们会及时提交欺诈证明。但同时,zk Rollup也面临着零知识证明技术计算成本高、复杂度高、开发难度大等问题,这些阻碍了zk Rollup技术在Rollups中的实际落地。随着近两年零知识证明技术的进一步发展,人们正逐渐克服这些障碍。zk Rollup 技术开始在 Layer 2 市场占据越来越大的份额。

如下图所示,在 Rollup Layer 2 扩展领域,zkRollup已经占据了一半以上的领地,并且正在快速发展。

来源https://l2beat.com/scaling/summary

数据检索日期:2024年1月18日

从专业化 zkRollup 到通用化 zkRollup

zkRollup的发展过程主要经历了两个阶段。第一种是非通用的 zkRollup,第二种是能够执行图灵完备任意合约的通用 zkRollup。

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

在非通用的 zkRollup 项目中(如上图中排名第 8 的 zkSync Lite),用户只能进行少数类型的交易操作,如 FT(可替代代币)转账、支付、互换和 NFT(不可替代代币)转账。这些操作的事务逻辑只能由项目所有者定义和实现。

通过这样的zkRollup项目,我们能以比以太坊主网低得多的费用进行转账,并获得更高的交易吞吐量。然而,如果我们想在链上尝试一些有趣的合约,我们将无法做到。

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

为了确保 Layer 2 的状态转换正确且可信,在zkRollup中,所有 Layer 2 状态转换逻辑都需要编写为零知识证明电路并由 Layer 1 合约进行验证。只有通过验证才能被 Layer 1 接受并最终完成Rollup。这个过程需要zkRollup平台的所有交易执行逻辑都在零知识证明电路中得到验证。然而,在零知识证明电路中支持任意合约逻辑的执行是一个挑战(造成这种困难的原因将在本文后面解释)。因此,早期的 zkRollup 项目往往只支持有限数量的相对简单的交易。

只能执行固定数量的简单交易显然不符合我们对 zkRollup 的期望。幸运的是,zkVM(零知识虚拟机)技术解决了在零知识证明电路内证明任意图灵完备代码执行的困难,使得通用的 zkRollup 平台成为可能。接下来,本文将介绍zkVM的实现原理,让读者了解通用zkRollup技术中最核心的部分是如何运作的。

zkVM的实现原理

在介绍zkVM原理之前,我们先简单介绍一下零知识证明技术。在这里,我们不需要详细了解零知识证明的底层数学原理,而是只需了解零知识证明可以做什么、如何使用它们以及其专用证明电路所施加的限制就足够了。

零知识证明简介

zkRollup 中的零知识证明用于证明 Layer 2 上交易已正确执行以及 Layer 2 状态已正确更新。

为了实现这一目的,zkVM电路需要证明部署在 Layer 2 上的任何智能合约都已正确执行。在介绍zkVM的原理之前,我们需要先讨论一下零知识证明的作用及其工作原理。

为什么需要零知识证明

零知识证明是一种密码学原语,它允许证明者让验证者相信陈述的正确性,而无需向验证者透露任何其他信息。

零知识证明具有三个核心属性:

  • 完整性:如果要证明的陈述是正确的,诚实的验证者(即正确遵循协议的验证者)将被诚实的证明者确信这一事实。
  • 可靠性:如果要证明的陈述是错误的,则不诚实的证明者只有微乎其微的机会让诚实的验证者相信该陈述是正确的。
  • 零知识:除了陈述真实外,验证者无法从验证过程中获得任何其他信息。

凭借零知识证明的完备性,当证明者完成复杂的计算时,他们可以产生一个证明,使验证者相信从输入数据得到的输出数据是执行者提供的结果。零知识证明的健全性确保当执行者提供错误结果时,他们无法生成有效的证明。

因此,凭借零知识证明的完整性和健全性,我们可以放心地将这些复杂的计算外包给其他人,并通过相对简单的验证过程来验证计算是否正确,而不需要信任外包方。

广泛使用的zk-SNARK方案除了具备零知识证明的三大核心特性外,还具有简洁性的特点。这意味着对于使用零知识证明证明的任何复杂逻辑,生成的证明的大小和验证证明所需的时间都是固定的并且相对较小。这使得 zk-Rollup 能够将状态更新计算卸载到链下,只验证链上操作的正确性,从而使扩容解决方案变得可行。

零知识证明的过程

接下来,本文将以下面的简单计算为例,讲解零知识证明的过程。

c=a²+b+5

为了解释零知识证明中的零知识方面,我们将变量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。这些是计算过程中使用的中间变量。

我们可以将算术电路中的每条线视为一个值,它可以是公共输入、秘密输入或中间变量。将计算扩展为算术电路后,每个中间变量将有其位置并用于证明过程。它们与输入之间的唯一区别是它们的值不是由证明者直接输入,而是由算术电路中的其他输入值确定。

我们可以把算术电路看成两部分:一部分是电路中出现的所有数值,另一部分是这些值之间的关系(约束)。我们通常将电路中的公共输入称为陈述(在我们的示例中为 a 和 c),并将所有其他值,包括秘密输入 (b) 和中间变量(d 和 e)称为见证。

根据电路的逻辑,当我们有公共输入作为陈述,秘密输入作为见证时,我们就可以计算出电路中所有的见证值。

因此,运算电路的门电路也可以表示为以下形式:

陈述:

一个,c

证人:

乙、丁、乙

约束:

d = a * a

e = b + 5

c = d + e

当待证明的电路被算术化后,零知识证明算法需要处理电路的约束,并将其转换为算法所需的形式,以生成和验证证明。经过处理后,电路产生一个与电路大小无关的固定长度的验证密钥(VK, Verification Key)。验证者可以通过验证密钥来验证相应电路的零知识证明。验证密钥有点类似于对电路的承诺。如果约束条件发生变化,相应的验证密钥也会发生变化。

在实际应用中,零知识证明的使用者需要将自己需要的逻辑写入zk电路源代码中,并通过审计生成相应的VK。这个VK交给验证者。证明者证明的公共输入以及生成的证明一起被提交,验证者可以验证这些公共输入是否满足约束。在此示例中,证明者可以使用 a、b 和 c 的值生成证明。验证者无需执行此操作即可验证a2 + b是否等于C。

零知识证明电路的局限性

虽然zk电路是图灵完备的并且可以表示任何计算,但由于需要将计算转换为算术电路的特殊表示形式,因此在编写算术电路时存在一些额外的限制。

在我们比较熟悉的计算机程序中,我们可以通过if-else陈述来控制程序执行的分支。仅执行程序中选定的分支。然而,在零知识证明过程中,计算被扁平化为电路,并且不存在执行路径或控制流的概念。因此,我们无法选择在算术电路中执行的特定分支。

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

以下面操作为例:

If (flag) {

c = x + x

}else {

c = x * x

}

当这个运算转换成运算电路时,就会转换成如下所示的约束条件。显然,两个新见证人 temp1 和 temp2 将添加到电路中。此外,值x+x 和价值x*x 都会被计算。

也就是说,在 zk 电路中,所有分支和逻辑都将被计算,无论它们是否被执行。

temp1 = x + x

temp2 = x * x

c = 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 是一种状态机,在处理指令时转换状态。让我们用一个非常简单的状态机示例来说明如何通过零知识电路来证明虚拟机。

我们假设这个通用状态机具有通用寄存器(A 和 B),此外还有一个存储当前指令号的程序计数器寄存器。

执行指令前寄存器的状态

下图展示了ZK虚拟机证明电路的基本工作流程:

状态0可以认为是这个虚拟机运行前的初始状态。初始状态经过总共 m 条指令后,达到最终状态 m。除了初始状态之外,这个虚拟机还有两个常规输入表:

  • 字节码表:存储状态机中执行的程序。
  • I/O表:存储虚拟机执行过程中产生的所有输入和输出。

图中,第n条指令的执行过程被抽象出来并显示在左侧。执行第 n 条指令后,状态机的状态(状态 n)转换为状态 n+1。同样的电路,经过m次迭代,实现了vm中m条指令的执行。

这里有两个问题。

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

第二是如何证明要执行的指令数不是m?

对于第一个问题,解决方案是实现电路中所有可能指令的逻辑。然后使用选择器,根据指令选择其中一个作为下一个状态,类似于前面提到的专用电路中的 if-else。

对于第二个问题,我们不能直接改变电路中的指令数量。这是因为电路中的每条指令都需要独立的电路段来实现。如果指令数量增加或减少,电路就会改变,相应的验证密钥也会改变。这使得无法满足验证固定电路中任何逻辑的要求。

为了解决这个问题,可以在指令集中添加一条不会改变状态的noop指令。因此,每个固定电路可以执行的指令数量是有上限的。zkVM 的电路可以看作是一个具有固定数量指令槽的容器。如果需要更多指令,则需要更大的电路。实际证明中,可根据需要选择合适尺寸的电路。

证明一条基本指令

下面以一些基本的计算指令为例,说明电路中的基本指令是如何被证明的:

图片来源

上图为指令验证电路的流程图。下面的公式是证明的电路约束。

这两个约束可以证明右上角列出的通用寄存器A和B的几个基本指令。这些证明可以将输入表中的值或指令中的立即值加载到寄存器中,或者将寄存器 A 和 B 中的值相加并将它们写回到寄存器中。

从图中我们可以看到,为了构建状态变化的约束,电路引入了一些辅助控制状态:

这些辅助寄存器和通用寄存器之间的计算逻辑通过以下公式实现。有兴趣的读者可以将相应的值代入约束公式中进行验证。可见,有了这两个约束,就可以实现基本的算术加法指令了。如果需要更多的操作,则必须添加更多的指令约束。

回到基本流程图,我们可以将本节的计算电路看成是整个流程中的一条指令。选择器将选择它产生的结果是否是状态机要采用的下一个状态。本节电路所需的辅助状态由PC寄存器指向的指令产生。

指令检索是通过专门的查找电路实现的,可以证明通过索引从固定表中检索到一段数据。因此,zkVM电路可以证明PC指定的虚拟机执行的状态转换。

证明条件判断和控制流跳转

状态机执行复杂逻辑的能力依赖于条件和跳转指令。在实际合约中,我们经常需要处理根据条件改变执行路径的逻辑,所以这样的电路是必要的。

这里需要注意的是,zkVM 电路并不是真正执行合约逻辑并计算结果的模块。zkVM电路实际上所做的就是证明合约逻辑的计算过程。因此,在证明时,需要将实际执行的指令序列过程填充到电路中,通过电路验证是否满足本次跳转的条件,进而证明执行的指令流程做出了正确的跳转。

首先我们介绍一下条件判断的证明:

以判断第i条指令中的操作数是否为零为例。我们为判断结果添加一个辅助状态isZero。如果判断值为0,则辅助状态isZero的值为1;如果判断的值为0以外的任何其他值,则isZero为0。

这个过程受到图中两个公式的约束。

该约束的有效性与零知识证明中使用的椭圆曲线的数学特性有关。零知识证明电路中的每个值都是椭圆曲线上有限域内的元素。如果它的值不为 0,则必须存在一个逆元素,该元素与自身相乘时结果为 1。使用此属性,结合图中的两个约束,可以验证一个值是否为零并将其转换为辅助状态。

一旦我们有了这个 isZero 条件辅助状态,我们就可以继续条件跳转指令的证明:

回到基本流程图,如果当前指令是条件跳转指令。它首先进行isZero检查,判断是否满足跳转条件,然后修改PC的值。更新PC的值后,执行下一条指令首先会根据PC进行查找,找到跳转后的指令。

I/O 和复杂操作

当使用通用状态机证明电路时,为了正确处理状态转换,需要在单个状态转换期间为每个支持的指令添加相应的控制状态和约束。这些状态值和约束的数量还必须乘以 zkVM 支持的指令数量。即使zkVM执行的实际程序(都是NOP)中没有执行任何操作,这些状态值和约束检查也不能省略。

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

为了解决这个问题,zkVM 的实际实现通常使用通用状态机电路和专用证明电路的组合来分别证明程序的各个部分,然后将证明聚合到一个解决方案中。

图片来源:1 2

左图是Scroll项目的电路架构,右下角的图是Polygon的电路架构。它们都采用类似的方法,如顶角的图表所示。

通用状态机负责证明程序的执行逻辑控制。在大多数合约中,这部分逻辑的实际执行时间很小,因此用低效的通用状态机来证明从效率上来说还是可以接受的。

更固定的复杂计算,如哈希、MPT树运算、外部输入数据等,都是通过专门的电路来证明的。

通用状态机和专用证明电路使用查找表进行交互。每次状态机电路调用这些操作时,生成证明见证的模块都会将调用参数和计算结果写入查找表中。因此,状态机电路中对这些操作的调用被简化为查找操作。

查找表中的每个调用和返回值的正确性都由专门的电路来约束和证明。

最后,电路中的复制约束连接状态机电路、专用电路和查找表,检查查找表中的每一项是否被相应的专用电路证明,最终生成完整块的证明。

Layer 1 合约只需要验证这个聚合证明即可确认整个虚拟机执行过程的正确性。

结语

零知识证明技术使得简单、快速地证明计算成为可能,为在不信任的环境中外包计算过程打开了大门。这项技术运用在区块链中,可以将执行从链上解放出来,让主区块链能够专注于去中心化和安全问题。但专门的零知识证明电路仅执行固定逻辑的特性限制了区块链上零知识证明的潜力,将早期 zkRollup 的功能限制在少数类型的交易上。

但随着zk虚拟机的发展和成熟,支持任意智能合约的图灵完备执行已经成为可能。 zkRollup的潜力将被真正释放,实现打破区块链三难困境的愿景。

声明:

  1. 本文转载自[ZAN],著作权归属原作者[ZAN and AntChain Open Labs],如对转载有异议,请联系Gate Learn团队,团队会根据相关流程尽速处理。
  2. 免责声明:本文所表达的观点和意见仅代表作者个人观点,不构成任何投资建议。
  3. 文章其他语言版本由Gate Learn团队翻译, 在未提及Gate.io的情况下不得复制、传播或抄袭经翻译文章。
Empieza ahora
¡Regístrate y recibe un bono de
$100
!
It seems that you are attempting to access our services from a Restricted Location where Gate.io is unable to provide services. We apologize for any inconvenience this may cause. Currently, the Restricted Locations include but not limited to: the United States of America, Canada, Cambodia, Cuba, Iran, North Korea and so on. For more information regarding the Restricted Locations, please refer to the User Agreement. Should you have any other questions, please contact our Customer Support Team.