Dynamic lookup table does not contain fixed/selector columns

[kcharbo3]

The dynamic lookup table functionality provided in /halo2-base/src/virtual_region/lookups/basic.rs -

halo2-lib/halo2-base/src/virtual_region/lookups/basic.rs

Lines 39 to 63 in 267123f

	pub fn new<P: Phase, F: Field>(
	meta: &mut ConstraintSystem<F>,
	phase: impl Fn() -> P,
	num_lu_sets: usize,
	) -> Self {
	let mut make_columns = || {
	[(); KEY_COL].map(|_| {
	let advice = meta.advice_column_in(phase());
	meta.enable_equality(advice);
	advice
	})
	};
	let table = make_columns();
	let to_lookup: Vec<_> = (0..num_lu_sets).map(|_| make_columns()).collect();
	for to_lookup in &to_lookup {
	meta.lookup_any("dynamic lookup table", |meta| {
	let table = table.map(|c| meta.query_advice(c, Rotation::cur()));
	let to_lu = to_lookup.map(|c| meta.query_advice(c, Rotation::cur()));
	to_lu.into_iter().zip(table).collect()
	});
	}
	Self { table, to_lookup }
	}

does not include any fixed/selector columns for the table columns. So all table columns are advice columns. This can easily lead to bugs when all rows of these advice columns are not constrained. The unconstrained rows can have any input value by the attacker, allowing them to include a false lookup.

This bug was originally seen in the Scroll/PSE zkevm circuits - privacy-scaling-explorations/zkevm-circuits#866

Adding a fixed/selector column to the lookup table allows lookups to succeed only for rows where the selector is 1. This selector should be enabled only on rows where the lookup table's advice values are set.

[jonathanpwang]

Resolved in #206