技术解读 AppliedZKP 的 zkEVM 方案设计思路

AppliedZKP 提出的 zkEVM 方案采用数据总线的思路，在正确的存储数据的基础上，State proof 证明数据的一致性，EVM proof 证明计算逻辑的正确性。

原文标题：《零知识证明 - zkEVM 解读》
撰文：Star Li

众所周知，ZK Rollup 是 L2 中安全等级最高的 Rollup 方案，但是 zkRollup 目前没有可编程性，更无从谈起可组合性。zkEVM 是用 zk-SNARK 技术将 EVM 的执行进行证明。zkRollup 支持了 zkEVM，在 L2 就能支持兼容 EVM 的智能合约。目前有几个团队都在研究 zkEVM 的实现。除了 AppliedZKP 公开了一些电路设计的思路和细节外，其他团队都没有详细的资料。AppliedZKP 有关 zkEVM 的设计资料如下：

点击 此处 阅读相关 资料。

本文详细分析 AppliedZKP 构想的 zkEVM 设计。本文中提到的 zkEVM 专指 AppliedZKP 提出的 zkEVM 方案。

背景

以太坊的每一个节点为了确保交易的正确性，需要针对每一个区块中的每一笔交易执行。也就是说，每一个节点需要验证以太坊的整个交易历史，并且要一笔笔的进行执行验证。zkEVM 利用零知识证明技术（zk-SNARK）证明：

这些证明都由两部分组成：State proof （状态证明）和 EVM proof （EVM 执行证明）。在一条交易执行过程中，State 包括 Storage，Memory 以及 Stack 的状态。

Bus-mapping 是设计的基础思想。一般的 PC 体系结构中，CPU 通过总线访问存储（内存 / 硬盘），也就是计算和存储分开。zkEVM 采用的同样的架构思想，状态的变化和指令的执行分开，并且分别由 State proof 和 EVM proof 进行证明。

State proof 负责 Bus Mapping 信息的一致性和正确性。一致性指的 Bus Mapping 和 State 之间的读写一致。正确性指的是 Bus Mapping 中的读写状态正确。EVM proof 负责 EVM 的 op code 的执行正确（如果涉及到 State 的 op code，保证存储相关的操作正确）。

EVM Execution 和存储之间好像有一条存储访问的总线一样：EVM Execution 通过 Bus Mapping 获取或者存储执行需要的相关状态。采用 Bus Mapping 的方式，需要证明 Bus Mapping 和 State 以及 EVM Execution 之间的「总线」操作的正确性。逻辑上分成如下的几步：读取状态，EVM 执行（修改状态），写回状态。Bus Mapping 包括了读取以及写回状态。

Bus Mapping

Bus Mapping 包括了两种状态，一种是读取老的状态，一种是写回生成新的状态。无论是老的状态和新的状态，Bus Mapping 都是「包含」关系。这种「包含」的 mapping 关系可以通过 Plookup 算法证明。

存储状态（Storage/Memory/Stack），采用 key-value 的格式进行表示。key-value 对的绑定关系可以实现为一个序列：

def build_mapping(): keys = [1,3,5] values = [2,4,6] randomness = hash(keys, values) mappings = [] for key , value in zip(keys,values): mappings.append(key + randomness*value) return(mappings)

想证明某个 key-value 对在一些 key-value 中，可以通过三个 Plookup 证明实现：

def open_mapping(mappings, keys, values): randomness = hash(keys,values) index = 1 # Prover can chose any mapping, key , value mapping = plookup(mappings) key = plookup(keys) value = plookup(values) # But it has to satisfy this check require(mappings[index] == key[index] + randomness*value[index]) # with overwhelming probability will not find an invalid mapping.

keys 和 values 是 State 相关的 key-value 对。mappings 是所有 key-value 对行程的 mapping 数组。通过三个 Plookup 证明：

并且 mapping 和 key-value 满足 build_mapping 建立的关系。如上的这些证明，能够证明某个 key-value 对是 keys 和 values 的 mapping 中的部分。

在如上的基础上，可以定义出 bus_mapping 的数据结构：

bus_mapping[global_counter] = { mem: [op, key, value], stack: [op, index, value], storage: [op, key, value], index: opcode, call_id: call_id, prog_counter: prog_counter }

其中，global_counter 是 slot 的编号。slot 是一个证明逻辑的最小单元。一个交易的证明由多条指令组成，每个指令可能由多个 slot 组成。op 是操作类型，逻辑上由读和写组成。prog_counter 是 pc。所有的 bus_mapping 中的读取操作可以通过 plookup 确定是不是「属于」当前的 State。读取状态需要和老的存储状态一致，写入状态需要和更新后的存储状态一致。

在 Bus mapping 的基础上，采用 State Proof 和 EVM Proof 证明数据的读写正确以及和 opcode 的语义一致。

State Proof

State Proof 证明了和「存储」相关的读写和 Bus Mapping 的数据一致。也就是在「总线」上的读写数据的一致性。State Proof 根据存储类型分成三种证明。

Storage

和 Storage 相关的 op code 罗列如下：

相关的 op code 分为两种，一种是 Storage 读，一种是 Storage 写。比如 SLOAD 就是从 Storage 读取数据到 Stack 中。Storage 相关的 op code 对应的读写数据在 Bus mapping 中。注意，State Proof 中的 Storage 证明只单纯证明 Storage 相关的读写操作是否在 bus mapping 中。至于读写数据的语义信息是通过 EVM proof 进行证明的。

Memory

从 State Proof 证明的角度看，所有的内存操作按照 index 进行排序。index 是内存地址。举个例子：

地址 0 和地址 1 的相关内存操作罗列在一起。每个内存地址在程序开始执行时会初始化为 0。也就是 global_counter 为零时，index 0/1 初始为 0。从 Bus Mapping 的角度看，这些内存操作如下：

对于每个地址上的读写数据都需要保持一致性。这些一致性由如下的约束检查：

蓝色部分限制内存只有读写操作，褐色部分限制每个地址内存初始为零，并且读写数据一致，橘黄色部分限制相关的内存操作在 bus mapping 中。

Stack

Stack 的操作主要分为三类：Push/Pop，Dup 和 Swap。用 1024 大小的数组模拟 Stack 实现。Stack 的位置信息的检查由 EVM proof 完成。Stack 的数据和 bus mapping 的关系由 Stack proof 完成。基本思路和 Memory 一致。

EVM Proof

EVM Proof 是 EVM 执行相关约束的核心。EVM proof 需要证明如下的一些逻辑：

Slot 是电路的基本单元。多个 Slot 可以组合在一起实现一个 op code 的语义。

算术计算

以加法为例，通过 Plookup 可以证明 8bit 整数的计算。通过多个 8bit 的加法以及进位，可以实现任意长度的加法。

两个数的比较的实现原理和加法类似。

跳转逻辑

call_id 记录一个执行环境。为了绑定和跳转逻辑的关系，call_id 采用如下的计算逻辑：

call_id -> rlc(calldata_callid, call_data_start_addr, call_data_size, return_data_callid,return_data_start_addr, return_data_size, origin, caller, call_value, call_stack_depth)

rlc 是 random linear combination。

EVM proof 的逻辑相对来说比较复杂。当前公布的文档没有展开描述设计的细节。zkEVM 给出了大致的设计思路，细节的部分还需要进一步细化。

总结：

AppliedZKP 公开了 zkEVM 的设计思路。zkEVM 采用数据总线（Bus Mapping）的思路，将存储和计算分开。在 Bus Mapping 抽取了正确的存储数据的基础上，State proof 证明数据的一致性，EVM proof 证明计算逻辑的正确性。

—-

编译者/作者：区块链网络

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。