Halo2 Lookup Argument

Source: The Halo2 Book - Lookup argument

To show that $A\subseteq B$, we let the prover compute columns $A^{\prime }$ and $B^{\prime }$ such that:

• $A^{\prime }$ is a permutation of $A$
• $B^{\prime }$ is a permutation of $B$
• In each row:
  • $A_{i+1}^{\prime }=A_i^{\prime }$, OR
  • $A_{i+1}^{\prime }=B_i^{\prime }$

Example:

A	B	A’	B’
1	4	1	1
1	3	1	2
4	2	4	4
4	1	4	3
For the permutation argument, they do a Permutation Check via Product Check, using a single accumulator column $Z$ for both permutations.