详细分析了AppliedZKP构思的ZkEVM设计

释放双眼,带上耳机,听听看~!

AppliedZKP提出的Zkevm方案采用了数据总线的思想。在正确存储数据的基础上,状态证明证明了数据的一致性,EVM证明了计算逻辑的正确性。

众所周知,ZK rollup是L2中安全级别最高的rollup方案,但ZK rollup没有可编程性,更不用说可组合性了。Zkevm使用ZK snark技术来证明EVM的执行。Zkrollup支持zkevm,并且可以支持L2中与EVM兼容的智能合约。目前,有几个团队正在研究zkevm的实现。除了AppliedZKP披露了电路设计的一些想法和细节外,其他团队没有详细的信息。Zkevm应用ZKP的设计资料如下:

本文详细分析了应用zkp构思的zkevm设计。本文中提到的zkevm是指AppliedZKP提出的zkevm方案。

背景

为了确保交易的正确性,以太坊的每个节点都需要执行每个块中的每个事务。换句话说,每个节点都需要验证以太坊的整个交易历史,并逐个执行验证。Zkevm使用零知识证明技术(ZKSnark)证明:

为智能合约的交易执行生成交易证明。zkrollup在L2中的实现支持可编程性。

为以太坊的每个块生成块证书。

这些证明由两部分组成:状态证明和EVM证明。在交易执行期间,状态包括存储、内存和堆栈的状态。

总线映射是设计的基本思想。在一般的PC体系结构中,CPU通过总线访问存储器(内存/硬盘),即计算和存储分离。Zkevm采用了相同的架构思想。将状态的变化与指令的执行分开,分别用状态证明和EVM证明进行证明。

状态证明负责总线映射信息的一致性和正确性。一致性是指总线映射和状态之间的读写一致性。正确性意味着总线映射中的读/写状态是正确的。EVM证明负责正确执行EVM操作代码(如果涉及状态操作代码,请确保与存储相关的操作正确)。

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

EVM执行和存储之间似乎有一条用于存储访问的总线:EVM执行通过总线映射获取或存储执行所需的相关状态。对于总线映射,需要证明总线映射、状态和EVM执行之间的“总线”操作的正确性。从逻辑上讲,它分为以下步骤:读取状态、EVM执行(修改状态)和写回状态。总线映射包括读写状态。

Bus Mapping

总线映射包括两种状态:一种是读取旧状态,另一种是写回以生成新状态。无论是旧状态还是新状态,总线映射都是一种“包含”关系。“包含”的映射关系可用plookup算法证明。

存储状态(存储/内存/堆栈)以键值格式表示,键值对的绑定关系可以实现为一个序列:

    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)

为了证明键值对,可以在某些键值中使用三种plookup证明:

    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)

键和值是与状态相关的键值对,Mappings是所有键值对的映射数组,由三个plookups证明:

  • 映射键位于键中
  • 映射的值以值为单位
  • 映射在映射中

并且映射和键值满足build_uuu映射的要求,映射建立了一种关系,上述证明可以证明键值对是键值映射的一部分。

基于以上,可以定义总线映射数据结构:

    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_uuucounter是插槽数。插槽是验证逻辑的最小单元。事务的验证由多条指令组成,每条指令可能由多个插槽组成。OP是一种逻辑上由读和写组成的操作类。prog_uuucounter是一台PC。映射中的所有总线读取操作都可以检测通过plookup判断是否属于当前状态,读取状态需要与旧存储状态一致,写入状态需要与更新后的存储状态一致。

在总线映射的基础上,使用状态证明和EVM证明来证明数据的读写正确,并且与操作码的语义一致。

State Proof

状态证明证明与“存储”相关的读/写与总线映射数据一致。即“总线”上读写数据的一致性。根据存储类,状态证明分为三种。

Storage

与存储相关的操作代码如下所示:

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

有两种类的相关操作码:存储器读取和存储器写入。例如,sload将数据从存储器读取到堆栈。与存储相关的操作代码对应的读写数据在总线映射中。请注意,状态证明中的存储证书仅证明与存储相关的读写操作是否在总线映射中。通过EVM证明证明了读写数据的语义信息。

Memory

从状态证明的角度来看,所有内存操作都是按索引排序的。索引是内存地址。例如:

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

地址0和地址1的相关内存操作一起列出。在程序执行开始时,每个内存地址都初始化为0。也就是说,当计数器为零时,索引0/1最初为0。从总线映射的角度来看,这些内存操作如下:

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

每个地址上的读写数据需要一致。通过以下约束检查这些一致性:

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

蓝色部分限制内存只进行读写操作,棕色部分限制每个地址的初始内存为零,读写数据一致,橙色部分限制总线映射中的相关内存操作。

Stack

堆栈操作主要分为三类:push/pop、DUP和swap。使用1024大小的数组来模拟堆栈实现。EVM验证检查堆栈的位置信息。堆栈数据和总线映射之间的关系通过堆栈验证来完成。基本思想与记忆是一致的。

EVM Proof

EVM证明是EVM实现相关约束的核心。EVM证明需要证明以下逻辑:

  • EVM执行的代码是指定交易的代码逻辑
  • 与存储相关的语义是否正确,如堆栈的位置管理,sload数据是否与堆栈数据一致
  • 与计算相关的语义是否正确,如算术计算等
  • 跳转逻辑是否正确,如调用指令
  • 耗气量计算正确
  • 程序是否正确终止

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

算术计算

以加法为例,8位整数的计算可以用plookup证明。通过多次8位加法进位,可实现任意长度的加法。

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

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

跳转逻辑

call_uid记录执行环境。对于绑定和跳转逻辑之间的关系,call_uid采用以下计算逻辑:

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使用总线映射的思想来分离存储和计算。在总线映射提取正确存储数据的基础上,状态证明证明了数据的一致性,EVM证明了计算逻辑的正确性。

给TA买糖
共{{data.count}}人
人已赞赏
头条资讯

聊聊Terra黎明计划:1.5亿美元只是一个开始,后续将每月投资9000万美元

2021-9-10 13:35:47

资讯

CCTV2报道元宇宙浪潮,IPFS胡按谈元宇宙或将是区块链经济介导的交易市场

2021-9-10 13:52:17

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索