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