链眼社区:专注于区块链安全,区块链数据分析, 区块链信息整合,区块链技术服务和区块链技术咨询。

ZKP—zkEVM
shijiang
2022-06-10 09:25:23

众所周知,zkRollup 在所有 Rollup 解决方案中具有最高的安全级别;但是,目前 zkRollup 不支持可编程性,更不用说可组合性了。zkEVM 利用 zk-SNARK 技术来执行 EVM 以进行证明。zkRollup 支持 zkEVM,并且兼容 L2 的 EVM 智能合约。到目前为止,有几个团队正在致力于实现 zkEVM。除了发布了一些电路设计细节的AppliedZKP,其他团队还没有发布相关文档。以下是来自 AppliedZKP 的一些关于 zkEVM 的公开文档:

https://github.com/appliedzkp/zkevm-specs

https://hackmd.io/Hy_nqH4yTOmjjS9nbOArgw

本文将分析来自 AppliedZKP 团队的 zkEVM 设计。因此,请注意这里提到的 zkEVM 特指 AppliedZKP 的 zkEVM 解决方案。

一.背景

为了让以太坊保证每笔交易的正确性,每个区块都需要有对应的交易。也就是说,每个节点都需要证明整个交易历史并对每笔交易执行验证。zkEVM 使用零知识证明技术 (zk-SNARK) 进行验证:

  • 对于每个智能合约交易执行,生成交易证明。在 L2 上实现 zkRollup 支持可编程性。
  • 对于以太坊中的每个区块,生成区块证明。

这些证明由两部分组成:状态证明和 EVM 证明。在每个事务的执行过程中,State 包括 Storage、Memory 和 Stack 状态。

总线映射是设计的基本方法。在正常的PC系统结构中,CPU通过总线访问存储(RAM/硬盘),将执行与存储逻辑分离。zkEVM 建立在相同的结构方法上——状态更改和订单执行是分开的,并相应地通过状态证明和 EVM 证明来证明。

状态证明负责总线映射的一致性和正确性。一致性是指一致的总线映射和状态读/写。正确性是指总线映射中正确的读/写状态的正确性。EVM证明负责EVM操作码的正确执行(如果引用状态操作码,请确保有关存储的执行正确。

就像存储访问总线存在于 EVM Execution 和 storage 之间一样:EVM Execution 通过 Bus Mapping 获取/保存执行所需的相关状态。利用 Bus Mapping,我们需要证明 Bus Mapping State 和 EVM Execution 之间的“Bus”执行的正确性。它在逻辑上分解为以下步骤:读取状态、EVM 执行(修改状态)、写入状态。总线映射包括读取和写入状态。

二. Bus Mapping

Bus Mapping 包括两种状态:读取旧状态和写回新状态。无论新旧,Bus Mapping 都有“包容”的关系。这种映射关系的“包含”可以通过 Plookup 算法来证明。

存储状态(Storage/Memory/Stack)由键值对表示。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)

为了证明某个键值对存在于一组键值对中,我们可以使用 3 个 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.

键和值是与状态相关的对。mappings 是所有旅程映射键值对的数组。使用 3 个 Plookup 证明:

1/keys中存在一个映射key

2/ values 中存在一个映射值

3/映射中存在一个映射

同时mapping和key-value对要满足build_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 是证明逻辑的最小单位。一个事务由多个命令组成,每个命令可能由多个槽组成。op为操作类型,按逻辑由读和写组成。prog_counter 是 pc。可以通过 plookup 检查 bus_mapping 的所有读数是否“属于”电流。读取状态需要与旧状态保持一致,写入状态也需要与更新后的保存状态保持一致。

基于总线映射,我们使用状态证明和EVM证明来保证数据的读/写的正确性,以及它与操作码语义的一致性。

三. 状态证明

State Proof 证明“保存”相关的读/写与 Bus Mapping 数据一致,即与总线上的读/写数据一致。State Proof 有 3 种基于存储类型的证明。

Storage

下面列出了与存储相关的操作码:

操作码有两种类型:存储读取和存储写入。例如,SLOAD 从 Storage 读取数据到 Stack。存储相关的操作码对应于总线映射中的读/写数据。注意,在State Proof中,Storage proof只证明总线映射中是否存在Storage相关的读写操作。至于语义信息,通过EVM证明来证明。

Memory

从状态证明来看,所有 RAM 操作都按索引排序。index 是 RAM 地址。举个例子:

地址 0 和地址 1 相关的 RAM 操作一起列出。每个 RAM 地址在程序执行开始时初始化为 0。也就是说,当 global_counter 等于 0 时,索引 0/1 重置为 0。从 Bus Mapping 的角度来看,这些 RAM 操作如下所列:

每个地址的读/写数据需要保持一致。这种一致性通过以下约束来检查:

蓝色部分限制 RAM 只能读/写,而棕色部分限制每个地址 RAM 初始化为 0 并与读/写数据保持一致。橙色部分将相关的 RAM 操作限制为仅在总线映射中发生。

Stack

Stack 有 3 个功能:Push/Pop、Dup 和 Swap。它是用一个 1024 大小的数组实现的。ck 位置信息的检查由 EVM 证明完成,而 Stackdata 和与总线映射的关系由 Stack 证明完成。基本理论遵循类似的记忆方式。

四. EVM 证明

EVM Proof 是 EVM 执行相对约束的核心逻辑。EVM 证明需要证明流动的逻辑:

1/ EVM执行代码指定交易代码逻辑

2/存储相关语义的正确性,如Stack位置管理、SLoad数据与Stack数据的一致性等。

3/计算相关语义的正确性,例如算术计算。

4/ 跳转逻辑的正确性,如Call命令

5/ Gas 消耗计算的正确性

6/ 如果程序适当终止

插槽是电路的基本单元。多个插槽可以组合在一起以实现操作码语义。

算术计算

以加法为例,8位整数加法可以用Plookup证明。通过多次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 代表随机线性组合。

EVM 证明逻辑相对复杂。目前关于设计细节的文档不多。zkEVM 提供了整体逻辑的文档,但未来仍可以完善细节。

五. 结论

AppliedZKP 发布了 zkEVM 的设计文档。zkEVM 利用总线映射方法,将存储和执行逻辑分开。Bus Mapping 基于提取正确的存储数据,使用状态证明来保证数据的一致性,使用 EVM 证明来保证执行逻辑的正确性。