range check fuzzing

[teddav]

I fuzzed the RangeCheck chip in order to make sure I couldn't find any bug. Did it in 2 steps: first re-write the logic to rust and fuzzed, then wrote a test circuit for the range check chip and fuzzed it.

cargo fuzz

Install, init and run cargo fuzz

cargo --locked install cargo-fuzz
cargo fuzz init
cargo fuzz add range_test
cargo fuzz run range_test

range check logic

pub fn range_test(value: u64, bytes: usize) {
    let mut value = Fp::from(value);
    let bytes = decompose_fp_to_bytes(value, bytes);

    let two_pow_k_inv = Fp::from(1 << 8).invert().unwrap();
    for byte in bytes {
        value = (value - Fp::from(byte as u64)) * two_pow_k_inv;
    }
    assert_eq!(value, Fp::zero());
}

And write the fuzz target

#![no_main]

use libfuzzer_sys::fuzz_target;
use summa_solvency::chips::range::range_check;

fuzz_target!(|data: u64| {
    println!("data: {data:#?}");
    range_check::range_test((data as u8) as u64, 1);
    range_check::range_test((data as u16) as u64, 2);
    range_check::range_test((data as u32) as u64, 4);
    range_check::range_test(data, 8);
});

fuzz the chip

Here's a test circuit for the RangeChip

pub mod rangechip_testing {
    use super::*;
    use crate::circuits::traits::CircuitBase;
    use halo2_proofs::{circuit::SimpleFloorPlanner, plonk::Circuit};

    #[derive(Debug, Clone)]
    pub struct RangeChipTestConfig<const N_BYTES: usize> {
        pub values: Column<Advice>,
        pub range_check_config: RangeCheckConfig<N_BYTES>,
        pub lookup_u8_table: Column<Fixed>,
    }

    #[derive(Default, Clone, Debug)]
    pub struct RangeChipTestCircuit<const N_BYTES: usize> {
        pub a: Fp,
    }

    impl<const N_BYTES: usize> CircuitBase for RangeChipTestCircuit<N_BYTES> {}

    impl<const N_BYTES: usize> Circuit<Fp> for RangeChipTestCircuit<N_BYTES> {
        type Config = RangeChipTestConfig<N_BYTES>;
        type FloorPlanner = SimpleFloorPlanner;

        fn without_witnesses(&self) -> Self {
            Self::default()
        }

        fn configure(meta: &mut ConstraintSystem<Fp>) -> Self::Config {
            let vals = meta.advice_column();
            let z = meta.advice_column();
            meta.enable_equality(z);
            meta.enable_equality(vals);

            let constants = meta.fixed_column();
            meta.enable_constant(constants);

            let lookup_u8_table = meta.fixed_column();
            let lookup_enable_selector = meta.complex_selector();

            RangeChipTestConfig {
                values: vals,
                range_check_config: RangeCheckChip::<N_BYTES>::configure(
                    meta,
                    z,
                    lookup_u8_table,
                    lookup_enable_selector,
                ),
                lookup_u8_table,
            }
        }

        fn synthesize(
            &self,
            config: Self::Config,
            mut layouter: impl Layouter<Fp>,
        ) -> Result<(), Error> {
            self.load(&mut layouter, config.lookup_u8_table)?;
            let range_chip = RangeCheckChip::construct(config.range_check_config);

            let a = self.assign_value_to_witness(
                layouter.namespace(|| "assign value a"),
                self.a,
                "value a",
                config.values,
            )?;
            range_chip.assign(layouter.namespace(|| "checking value a is in range"), &a)?;

            Ok(())
        }
    }
}

and a helper test function

pub fn rangechip_test<const N_BYTES: usize>(
    circuit: rangechip_testing::RangeChipTestCircuit<N_BYTES>,
) {
        println!("a: {:?}", circuit.a);
    let prover = MockProver::run(11, &circuit, vec![]).unwrap();
    assert!(prover.verify().is_ok());
}

mod tests {
    use super::*;

    #[test]
    fn test_rangechipcircuit() {
        let circuit = rangechip_testing::RangeChipTestCircuit::<1> { a: Fp::from(0xff) };
        rangechip_test(circuit);

        let circuit = rangechip_testing::RangeChipTestCircuit::<1> { a: Fp::from(0x100) };
        rangechip_test(circuit);
    }
}

and the fuzz target

#![no_main]

use libfuzzer_sys::fuzz_target;
use summa_solvency::chips::range::range_check::{
    rangechip_test,
    rangechip_testing::{BigUint, Fp, PrimeField, RangeChipTestCircuit},
};

fuzz_target!(|data: u128| {
    println!("data: {data:#?}");

    let circuit1 = RangeChipTestCircuit::<1> {
        a: Fp::from((data as u8) as u64),
    };
    rangechip_test(circuit1);

    let circuit2 = RangeChipTestCircuit::<2> {
        a: Fp::from((data as u16) as u64),
    };
    rangechip_test(circuit2);

    let circuit3 = RangeChipTestCircuit::<4> {
        a: Fp::from((data as u32) as u64),
    };
    rangechip_test(circuit3);

    let circuit4 = RangeChipTestCircuit::<8> {
        a: Fp::from(data as u64),
    };
    rangechip_test(circuit4);

    let big = BigUint::from(data);
    let circuit5 = RangeChipTestCircuit::<16> {
        a: Fp::from_str_vartime(&big.to_str_radix(10)[..]).unwrap(),
    };
    rangechip_test(circuit5);
});