Add circuit helpers to calculate min k

[ed255]

For each circuit, based on specific inputs we want to use a minimum k value is required. It would be nice to have uniform function helpers for each circuit to calculate this minimum k.

As an example, here's how the SuperCircuit calculates the k value for tests by using hard-coded formulas that could be moved to each circuit: https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/1f30ed6f332fa4bd50f2bbd6c69c0b509dbc81e4/zkevm-circuits/src/super_circuit.rs#L330-L342

[han0110]

Recently I got a satisfied solution for myself (while refactoring halo2wrong), here is the helper implementation:

First we implement trait Assignment to count maximum offset of each kind of column of circuit, and output the dimension:

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Dimension {
    blinding_factor: u64,
    instance: u64,
    advice: u64,
    fixed: u64,
}

impl Dimension {
    fn k(&self) -> u32 {
        u64::BITS
            - ([self.instance, self.advice, self.fixed]
                .into_iter()
                .max_by(Ord::cmp)
                .unwrap()
                + self.blinding_factor)
                .next_power_of_two()
                .leading_zeros()
            - 1
    }

    fn advice_range(&self) -> RangeInclusive<usize> {
        0..=self.advice as usize
    }
}

#[derive(Default)]
pub struct DimensionMeasurement {
    instance: RefCell<u64>,
    advice: RefCell<u64>,
    fixed: RefCell<u64>,
}

impl DimensionMeasurement {
    fn update<C: Into<Any>>(&self, column: C, offset: usize) {
        let mut target = match column.into() {
            Any::Instance => self.instance.borrow_mut(),
            Any::Advice(_) => self.advice.borrow_mut(),
            Any::Fixed => self.fixed.borrow_mut(),
        };
        if offset as u64 > *target {
            *target = offset as u64;
        }
    }

    pub fn measure<F: FieldExt, C: Circuit<F>>(circuit: &C) -> Result<Dimension, Error> {
        let mut cs = ConstraintSystem::default();
        let config = C::configure(&mut cs);
        let mut measurement = Self::default();
        C::FloorPlanner::synthesize(&mut measurement, circuit, config, cs.constants().to_vec())?;
        Ok(Dimension {
            blinding_factor: cs.blinding_factors() as u64,
            instance: measurement.instance.take(),
            advice: measurement.advice.take(),
            fixed: measurement.fixed.take(),
        })
    }
}

impl<F: FieldExt> Assignment<F> for DimensionMeasurement {
    fn enable_selector<A, AR>(&mut self, _: A, _: &Selector, offset: usize) -> Result<(), Error> where A: FnOnce() -> AR, AR: Into<String>, {
        self.update(Fixed, offset);
        Ok(())
    }

    fn query_instance(&self, _: Column<Instance>, offset: usize) -> Result<Value<F>, Error> {
        self.update(Instance, offset);
        Ok(Value::unknown())
    }

    fn assign_advice<V, VR, A, AR>(&mut self, _: A, _: Column<Advice>, offset: usize, _: V) -> Result<(), Error> where V: FnOnce() -> Value<VR>, VR: Into<Assigned<F>>, A: FnOnce() -> AR, AR: Into<String> {
        self.update(Advice, offset);
        Ok(())
    }

    fn assign_fixed<V, VR, A, AR>(&mut self, _: A, _: Column<Fixed>, offset: usize, _: V) -> Result<(), Error> where V: FnOnce() -> Value<VR>, VR: Into<Assigned<F>>, A: FnOnce() -> AR, AR: Into<String> {
        self.update(Fixed, offset);
        Ok(())
    }

    fn copy(&mut self, lhs: Column<Any>, offset_lhs: usize, rhs: Column<Any>, offset_rhs: usize) -> Result<(), Error> {
        self.update(*lhs.column_type(), offset_lhs);
        self.update(*rhs.column_type(), offset_rhs);
        Ok(())
    }

    fn fill_from_row(&mut self, _: Column<Fixed>, offset: usize, _: Value<Assigned<F>>) -> Result<(), Error> {
        self.update(Fixed, offset);
        Ok(())
    }

    fn enter_region<NR, N>(&mut self, _: N) where NR: Into<String>, N: FnOnce() -> NR {}
    fn exit_region(&mut self) {}
    fn push_namespace<NR, N>(&mut self, _: N) where NR: Into<String>, N: FnOnce() -> NR {}
    fn pop_namespace(&mut self, _: Option<String>) {}
}

Next we can wrap MockProver like:

pub fn mock_prover_verify<F: FieldExt, C: Circuit<F>>(
    circuit: &C,
    instance: Vec<Vec<F>>,
) -> Result<(), Vec<VerifyFailure>> {
    let dimension = DimensionMeasurement::measure(circuit).unwrap();
    let prover = MockProver::run(dimension.k(), circuit, instance)
        .unwrap_or_else(|err| panic!("{:#?}", err));
    prover.verify_at_rows_par(dimension.advice_range(), dimension.advice_range())
}

Then we never need to estimate the k manually anymore!

But there comes with a cost of going through an extra round of FloorPlanner::synthesize, tho it should be negligible compared to MockProver::verify