
[Star Li]零知识证明 – zkEVM解读
众所周知,zkRollup是L2中安全等级最高的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支持可编程性。
-
针对以太坊的每一个区块,生成区块证明。
这些证明都由两部分组成: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都是“包含”关系。这种“包含”的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证明:
1/ 某个mapping的key在keys中
2/ 某个mapping的value在values中
3/ 某个mapping在mappings中
并且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证明了和“存储”相关的读写和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执行相关约束的核心。EVM proof需要证明如下的一些逻辑:
1/ EVM执行的代码是指定的transaction的代码逻辑
2/ 和存储相关的语义是否正确,比如Stack的位置管理,SLoad数据和Stack的数据是否一致等等
3/ 和计算相关的语义是否正确,比如算术计算等等
4/ 跳转逻辑是否正确,比如Call指令
5/ Gas消耗计算正确
6/ 程序终止是否正确
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证明计算逻辑的正确性。
比推快讯
更多 >>- DeFi 应用 Finnt 完成 350 万美元种子轮融资,Y Combinator 等参投
- Web3音频流媒体平台Tamago完成100万美元种子轮融资,Block0等参投
- 葡萄牙国会否决了两项寻求对加密货币征税的法案
- 去中心化内容发布平台Mirror 推出将文章铸造为 NFT 的功能
- 巴拉圭众议院通过了一项规范加密采矿和交易的法案
- Jack Dorsey 卸任 Twitter 董事会成员职位
- 美联储会议纪要显示准备继续加息50个基点,加息速度快于市场预期
- CryptoPunks 地板价跌破 10 万美元,与上个月相比下跌 50%
- Cosmos 生态系统核心开发团队 Ignite 拆分为两个独立实体「Ignite」和「NewTendermint」
- CoinMetrics:以太坊上持有超过 100 万美元 USDC 的钱包地址数量超过持有同等规模 USDT 的钱包数量
- Coinbase将上线The Sandbox (SAND)
- Layer 1区块链 Celestia 启动其“Mamaki”测试网
- NGC Ventures 为其新的Web 3基金筹集 1 亿美元,将支持 DeFi、NFT 和 GameFi 的早期项目
- 币安与哈萨克斯坦共和国数字发展部签署谅解备忘录
- 价值 150 万美元的 Moonbirds NFT 在网络钓鱼攻击中被盗
- Ripple 将在与美 SEC 的诉讼案结束后考虑 IPO
- 艺术家 Refik Anadol 基于人工智能的 NFT 收藏品以 620 万美元的价格卖出
- 摩根士丹利:清晰的加密货币监管对行业发展很重要
- StarkWare 融资 1 亿美元,估值 80 亿美元
- 跨链桥 Wormhole 将扩展到 Cosmos 生态系统
- ZenLedger 筹款 1500 万美元将进一步扩展加密税收产品
- 跨链互操作性协议LayerZero Labs 正以 30 亿美元估值进行融资谈判,FTX Ventures 已承诺领投
- 达沃斯论坛中有关 NFT 市场的观点
- Terra 新链提案 1623 投票通过
- Babel Finance 融资 8000 万美元,估值 20 亿美元
- Web3 游戏工作室 MetaKings 完成 1500 万美元种子轮融资
- a16z 推出第四支加密基金,规模达45亿美元
- 亿万富翁 Alan Howard:投资整个加密生态才能明确挑战和机遇
- KuCoin Ventures 宣布投资 Web3 游戏开发平台 Joyride
- 加密税收报告平台 CoinTracker 宣布进军印度
- 雅虎已为 AOL 提交元宇宙及 NFT 相关商标申请
- 21Shares 推出全球首个美元收益 ETP 产品 USDY
- Do Kwon 请求韩国加密交易所重新上线 Luna 代币并支持新代币空投
- 谷歌正寻求全球 Web3 团队的负责人
- 韩国金融监管局将实施对虚拟资产的风险评估工作
- 加密浏览器 Opera 推出 VPN Pro 服务的桌面端开发者版本
- 音乐NFT初创公司ArtistFirst完成550万美元种子轮融资,Multicoin Capital领投
- 元宇宙服务商MetaEstate完成数百万美元战略轮融资
- Web3初创公司Stan完成250万美元种子轮融资,General Catalyst领投
- Coinbase Pay 上线,MetaMask 将在几周内集成 Coinbase Pay
- DeFi支付服务提供商Spritz Finance完成250万美元pre-seed轮融资
比推专题
更多 >>观点
项目
比推热门文章
- 风险管理和仓位控制
- 马斯克将收购推特的股权承诺总额提高至335亿美元
- 【比推每日精选】美联储会议纪要显示将继续加息50个基点,加息速度快于市场预期;摩根大通:比特币的公允价格是3.8万美元,加密货币已取代房地产成为首选的“另类投资”;Ripple 将在与美 SEC 的诉讼案结束后考虑 IPO
- 美联储会议纪要显示6月和7月继续加息50个基点,分析师预计波动走势将加剧
- 经济学教授 Steve H. Hanke:是时候停止溺爱加密货币了
- 价值投资者 Bill Miller 十大金句:比特币是唯一一个供应不受需求影响的经济实体,是应对金融灾难的保险单
- 比特币价格触底信号闪现,恐惧和贪婪指数跌至2020年3月低点
- 美联储会议纪要显示准备继续加息50个基点,加息速度快于市场预期
- 摩根大通:比特币的公允价格是3.8万美元,加密货币已取代房地产成为首选的“另类投资”
- Terra 2.0 时代即将到来,将空投新的 Luna 代币