appliedzkp zkevm（8）中的Plookup Table

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