zkMove 第一次公开亮相

前段时间应 Move 核心开发者 zrt 之邀,在 Move 社区的周会上做了一个分享,介绍了 zkMove 的整体架构并演示了其命令行工具的使用,这应该算是 zkMove 第一次公开亮相。我整理了一下相关内容,欢迎感兴趣的朋友一起探讨。

概况

zkMove 是一个面向零知识证明的 Move 语言运行环境。它最初的构想是提升零知识证明的可编程性和可组合性,用户可以基于 zkMove 运行安全、可扩展、隐私的智能合约。关于 zkMove 的设计初衷我曾经在《聊一聊 zkMove》系列文章中介绍过,这里不再赘述。整体而言,zkMove 具有以下三个特点:

  • 一个零知识证明友好的 Move 字节码虚拟机。作为新一代面向数字资产的编程语言,Move 在语言层面保证了资产的安全性。zkMove 的设计目标是在字节码层面与 Move 规范兼容,这使得它除了可以构建扩容方案和隐私方案外,还可以作为区块有效性证明,提升 Move 区块链的同步性能。
  • 采用 Halo2 零知识证明系统。Halo2 提供了 Plonkish 算术化工具,支持自定义门和查找表,非常适合构建大规模复杂电路,而且不需要可信设置。
  • 兼顾图灵完备和性能。zkMove 提供两种类型的电路,VM 电路可以处理条件和循环语句,用来实现图灵完备;Move 电路则具有更小的 proof 和更短的证明时间。

整体架构

我们先来看一下 zkMove 的整体架构。在执行交易 (txn) 之前,我们假定智能合约已经在 zkMove 上发布,proving key 和 verification key 也已经生成。这两个 Key 是零知识证明系统中的专业术语,感兴趣的朋友可以参考 Halo2 文档,里面对相关术语的来龙去脉做了解释。

zkmove-arch.png

在 zkMove 上,完成一个交易需要三个步骤。第一步是在客户端执行交易并生成一个见证。见证包括全局状态、交易本身和交易的执行轨迹。这里的全局状态并不需要完整的状态树,只需要新旧状态树树根、交易中涉及的账户和相关的 Merkle 证明即可。

第二步,zkMove 根据用户配置选择 VM 电路或者 Move 电路,新状态树树根被传递给电路作为公共输入。然后,见证、公共输入和电路被发送给 Prover 生成本次交易的零知识证明。

最后,零知识证明和公共输入被发送给 Verifier,即链上的一个智能合约,来验证零知识证明是否有效。如果通过了验证,新的状态树树根将被更新到链上。

Move 电路和 VM 电路

正如上面提到的,zkMove 兼顾了图灵完备和性能。VM 电路提供了图灵完备性,而 Move 电路提供了更小的 proof 和更短的证明时间。Move 电路是智能合约特定的电路。智能合约的字节码在执行的过程中被虚拟机自动"翻译"成电路。

move-circuit.png

例如下面这个函数

fun main(x: u64, y: u64, z: u64) {
    (x + y) * z;
    ...
}

对应的字节码如下:

MoveLoc(0); //将变量 x 从 Locals 移到栈上
MoveLoc(1); //将变量 y 从 Locals 移到栈上
Add; //取出栈顶的 y 和 x,相加后将结果写入栈顶
MoveLoc(2); //将变量 z 从 Locals 移到栈上
Mul; //取出 z 和 x+y 的结果,相乘后将最终结果写入栈顶
...

自动生成的 Move 电路包含两个门:一个加法门,用来约束 x + y,其输出记作 out;另一个是乘法门,用来约束 out * z。

gate.png

从这个例子可以看出,Move 电路是由字节码直接生成的,实现非常简洁。但是如果程序中包含条件或者循环语句,处理起来就会比较麻烦。

为了处理条件语句,zkMove 引入了 ProgramBlock 来表达控制流。ProgramBlock 可以简单理解成简化了的 BasicBlock。执行过程中 zkMove 会动态识别 ProgramBlock,如果 ProgramBlock 中包含分支 Block,就会对分支分别进行处理。目前 Move 电路的实现还仅仅是一个原型,不支持嵌套的分支语句,不支持循环,无法做到图灵完备,仅适合简单交易。

受 Tinyram 和 zkEVMs 的启发,zkMove 构建了 VM 电路,它通过验证交易执行轨迹中每一步的正确性和完整性来实现对条件和循环语句的支持。它可以分解成三部分:

  • 正确的字节码被加载。
  • 每个字节码都被正确执行。
  • 内存一致性:每次从栈、局部变量和全局状态读取到的值,就是上次写入的值。

显然,实现这样一个电路是非常复杂的,幸好 Halo2 提供了自定义门和查找表这两把利器。当一个电路遇到一些昂贵的操作时,可以通过自定义门和查找表将部分工作外包给其他电路,一个复杂的电路就可以分解为多个相对简单的电路。这使得实现 VM 电路成为可能。

zkMove 的 VM 电路由多个子电路组装而成,其中包括执行电路、字节码电路和内存电路。执行电路用来约束每个字节码被正确执行,字节码电路验证正确的字节码被加载,内存电路保证内存一致性。具体而言,为了验证正确的字节码被加载,我们在执行电路中查找字节码表,并使用字节码电路来约束字节码表与智能合约的字节码相同。为了验证内存的一致性,我们在执行电路中查找读/写表,并使用内存电路来约束读/写表,保证每次从栈、局部变量和全局状态读取到的值,就是上次写入的值。

功能演示

电路的实现有点复杂,我会单独写文章介绍,现在是 Demo 时刻!我们通过一个 CLI 和一些例子来演示 zkMove 的功能,相关代码可以到 github 的 young-rocks/zkmove 项目下下载。

下面的命令首先会把 add.move 编译成字节码,执行字节码的同时创建电路并生成 proving key 和 verification key。然后用 proving key 生成零知识证明,最后用 verification key 验证证明。

bin/zkmove run -s examples/scripts/add.move

Move 程序由 script 和 module 组成。可以在 script 源文件中通过控制指令 'mods' 导入一个 module。另外,我们还可以用指令 'args' 向 script 传递参数。例如:

/// call_u8.move

//! mods: arith.move
//! args: 1u8, 2u8
script {
    use 0x1::M;
    fun main(x: u8, y: u8) {
        M::add_u8(x, y);
    }
}

VM 电路和 Move 电路 CLI 都支持,默认使用 Move 电路,如果要切换成 VM 电路可以使用命令选项"--vm-circuit":

bin/zkmove run -s examples/scripts/add.move --vm-circuit

详细的使用说明请参考代码目录下的 README。

性能和限制

zkMove 仍在大力开发当中,现在分享性能数据可能会产生误导。但是为了给大家一个整体印象,我还是在 Macbook上收集了一些数据。从这些数据可以看出,Move 电路比 VM 电路快了大约 40 倍。需要强调的是,这些数据仅代表当前开发状态,在支持了全局状态和复杂数据结构之后,Move 电路和 VM 电路之间的差距可能还会进一步拉大。

data.png

注:环境配置是 MacOS Catalina,2GHz四核英特尔酷睿i5,16GB内存

zkMove 仍处于早期阶段,还存在很多限制和问题。例如,缺乏对全局状态的支持,只支持简单的数据类型,电路和底层证明系统的性能都需要进一步优化。目前 zkMove 整个框架和 Move 电路已经开源,源码可以从 github 上 young-rocks/zkmove-lite 项目下载。希望感兴趣的朋友多多交流!

谢谢关注!

本文参与2022世界杯预选赛赛程直播社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2022-07-15 15:25
  • 阅读 ( 431 )
  • 学分 ( 22 )
  • 分类:零知识证明

0 条评论

请先 登录 后评论
Young Rocks
Young Rocks

4 篇文章, 55 学分