Plookup table in appliedzkp zkevm (8)

1. introduction

appliedzkp zkevm use Halo2 Of lookup table As a primitive, Come on check table One of the lines in is really some adviced values.

Such as , following table Of a、b、c Column , among a、b As a “0,1,2” The possible combination of ,c To be right a、b Column logic AND operation ：

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

You can use this table To check circuit Some of them x、y Variable AND Operational constraints , To prove "x"、“y”、"x & y" In response to table One of the lines .

zkevm There is 2 Types of table：

• 1）Fixed Table
  So-called Fixed Table, Means the fixed table Rows in proving time“ Before ” It has been determined that .
  above AND operation table Namely fixed table.
• 2）Variable Table（Dynamic Table）
  So-called Variable Table, Means the variable table Rows in proving time " when " determine .
  Variable Table bring Prover You can create your own table, Such as Prover can witness a key-value mapping by a variable table. Be careful , Additional checks are required to ensure that mapping key Uniqueness .

2. zkevm EVM circuit Medium tables

zkevm Of EVM circuit A variety of dynamic and fixed tables, among dynamic table The validity of the content is determined by the circuit To prove .
zkevm Medium dynamic tables Yes ：

• 1）tx_table： from tx circuit prove .
• 2）rw_table： from state circuit prove .
• 3）bytecode_table： from bytecode circuit prove .
• 4）block_table： from block circuit prove .
• 5）mpt_table： from MPT（Merkle Particia Trie）circuit Provide .

zkevm Medium fixed tables Yes ：

• 1）execution_state.responsible_opcode()： take execution_state mapping （map） To Generate this execution state Of opcode. So-called execution_state, Is when opcode Status of successful operation . This mapping may combine multiple similar opcode Merge into one execution state, Such as LT/GT/EQ All corresponding CMP state .
• 2）invalid_opcode()： by invalid opcodes set.
• 3）state_write_opcode()： For the meeting write state A group of opcodes.
• 4）stack_underflow_pairs： It will cause underflow Of opcodes set and stack pointer value.
• 5）stack_overflow_pairs： It will cause overflow Of opcodes set and stack pointer value.

Reference material

[1] zkevm-specs plookup table
[2] zkevm-specs tables