1. 引言
appliedzkp zkevm采用 Halo2的lookup table 作为a primitive,来check table中的某一行确实是某些adviced values。
如,以下table的a、b、c
列,其中a、b
列为“0,1,2”的可能组合,c
为对a、b
列的逻辑AND运算:
a | b | c |
---|
0 | 0 | 0 |
0 | 1 | 0 |
0 | 2 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
1 | 2 | 0 |
2 | 0 | 0 |
2 | 1 | 0 |
2 | 2 | 2 |
可使用该table来检查circuit中的某些x、y
变量的AND运算约束,以证明"x"、“y”、"x & y"为对应该table中的某一行。
zkevm中有2种类型的table:
- 1)Fixed Table
所谓Fixed Table,是指该fixed table中的行在proving time“之前”就已确定。
上面的AND运算table就是fixed table。 - 2)Variable Table(Dynamic Table)
所谓Variable Table,是指该variable table中的行在proving time "时"确定。
Variable Table使得Prover可创建自己的table,如Prover可witness a key-value mapping为a variable table。注意,此时需要做额外检查来确保mapping key的唯一性。
2. zkevm EVM circuit中的tables
zkevm的EVM circuit中使用了多种dynamic和fixed tables,其中dynamic table内容的有效性由其自身关联的circuit来证明。
zkevm中的dynamic tables有:
- 1)tx_table:由tx circuit证明。
- 2)rw_table:由state circuit证明。
- 3)bytecode_table:由bytecode circuit证明。
- 4)block_table:由block circuit证明。
- 5)mpt_table:由MPT(Merkle Particia Trie)circuit提供。
zkevm中的fixed tables有:
- 1)execution_state.responsible_opcode():将execution_state 映射(map)到 生成该execution state的opcode。所谓execution_state,是指当opcode运行成功的状态。这种映射可能会将多个相似的opcode合并到一个execution state,如LT/GT/EQ都对应CMP状态。
- 2)invalid_opcode():为invalid opcodes set。
- 3)state_write_opcode():为会write state的一组opcodes。
- 4)stack_underflow_pairs:在执行时会引起underflow的opcodes set和stack pointer value。
- 5)stack_overflow_pairs:在执行时会引起overflow的opcodes set和stack pointer value。
参考资料
[1] zkevm-specs plookup table
[2] zkevm-specs tables