
[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证明计算逻辑的正确性。
比推快讯
更多 >>- OpenEden 已于昨日完成积分(Bills)快照,空投最低门槛为 10 万积分
- 联合国机构明年将设立“政府区块链学院”,传授加密技术等知识
- The Smarter Web Company 引入 Coinbase Institutional 作为其比特币托管方
- Camp Network 将于 9 月 24 日举办 “AI 创作者峰会”
- Capital B 已募集 5810 万欧元,以加速比特币储备战略
- pump.fun 过去 24 小时协议收入达 338 万美元,再次超越 Hyperliquid
- Tom Lee:若美联储降息,比特币和以太坊未来 3 个月或迎来大幅上涨
- 华检医疗与仁和国际达成合作,共建专注于非处方药领域的垂直 RWA 交易平台
- 铁头空军巨鲸持续减仓 PUMP 空单,账户总持仓约 1.37 亿美元
- Pantera Capital 创始人:比特币四五年内将达 75 万美元
- OpenAI 已聘请前 xAI 首席财务官
- 以色列没收 187 个疑似伊朗革命卫队相关钱包,钱包持有约 150 万美元
- 数据:过去 1 小时 Binance 净流出 3,164.35 万 USDT
- 数据:当前加密恐慌贪婪指数为 51,处于中性状态
- 特朗普对纽约时报提起 150 亿美元诽谤诉讼,怒斥其沦为民主党“传声筒”
- 1confirmation 创始人评Base 考虑发币:若运营得当,BASE 可成为市值前五加密货币
- 全球首个 AI Agent 交易市场“MuleRun”正式上线
- 数据:欧元兑美元升至 1.1784,为 7 月 24 日以来最高水平
- Polymarket 上预测 9 月美联储决策交易量已超 1.3 亿美元
- Bitmine 增持后,以太坊财库实体持有 ETH 占总流通量比例已超 4%
- 币安稳定币储备达 400 亿美元,创历史新高
- Yala:新方案实施前应避免进行任何与 YU 和 YBTC 相关的交易或操作
- Talus 将于 9 月 18 日上线测试网
- 日经 225 指数受科技股推动一度飙升至历史新高
- 星展香港完成基于意向货币技术的数码港元+项目测试
- 美股上市公司 Reliance Global 将分阶段共投资 1.2 亿美元购买加密货币
- Avalon Labs 上线 BTCtreasuries,位列私营企业比特币持仓前五
- 鲸鱼在 PUMP 交易中扭亏为盈,获利 386 万美元
- RootData:BID 将于一周后解锁价值约 117 万美元的代币
- Project Hunt:固定利率协议 Flashstake 为过去 7 天被 Top 人物取关最多的项目
- Polymarket 与 Stocktwits 合作,提供实时盈利预测
- 观点:比特币卖压指标显示当前或已局部触底
- 港股上市公司比特策略增持 33.41 枚 BTC,目前比特币持仓量约为 43.41 枚
- Jito 转移价值 800 万美元 JTO 代币,或将交易卖出
- 鲸鱼交易员General Gordon James做多 BTC、ETH、SOL、SUI 等主流币,持仓价值达 1.45 亿美元
- 数据:昨日美国比特币现货 ETF 净流入 2.5892 亿美元
- 分析:当前市场投资者持谨慎观望态度,后续走势可参考鲸鱼群体动向
- 某鲸鱼解质押 53,194 枚 SOL 并全部卖出,获利约 320 万美元
- 上海法院首次成功处置刑事案件中的虚拟货币,9 万余枚 FIL 币完成变价处置
- pump.fun:昨日支付超 400 万美元奖励,大部分发给了首次创作者
- 德林控股拟从 Fortune Peak 处收购 2200 台比特币矿机
- 针对 NPM 供应链的攻击事件再次发生
- Web3 动作角色扮演游戏 RuneSoul 完成 400 万美元新一轮融资
- dAPP 基础设施 Epoch Protocol 完成 120 万美元融资,Alphemy Capital 等参投
- OpenSea:TGE 前的最后奖励阶段现已上线
- 某单一实体通过超 300 个地址在 AVNT 空投中获利 400 万美元
- Strategy 创始人等加密高管将参加华盛顿圆桌会议,推进美国战略比特币储备法案
- 云锋金融配售发行新股集资公约 11.7 亿港元,以支持推出全面虚拟资产交易服务
- 投行杰富瑞报告:比特币挖矿盈利下滑 5%
- The Fellowship PAC 承诺投入超 1 亿美元支持亲创新、亲加密货币的政治候选人
比推专栏
更多 >>观点
比推热门文章
- The Smarter Web Company 引入 Coinbase Institutional 作为其比特币托管方
- Camp Network 将于 9 月 24 日举办 “AI 创作者峰会”
- 发币传闻升温,带你看懂Polymarket的10个生态布局
- Capital B 已募集 5810 万欧元,以加速比特币储备战略
- pump.fun 过去 24 小时协议收入达 338 万美元,再次超越 Hyperliquid
- Tom Lee:若美联储降息,比特币和以太坊未来 3 个月或迎来大幅上涨
- 华检医疗与仁和国际达成合作,共建专注于非处方药领域的垂直 RWA 交易平台
- 铁头空军巨鲸持续减仓 PUMP 空单,账户总持仓约 1.37 亿美元
- Pantera Capital 创始人:比特币四五年内将达 75 万美元
- OpenAI 已聘请前 xAI 首席财务官