use std::fmt::Debug;
use midnight_proofs::{
circuit::{Layouter, Value},
plonk::Error,
};
use super::AssertionInstructions;
use crate::{
ecc::curves::CircuitCurve,
instructions::DecompositionInstructions,
types::{InnerConstants, InnerValue, Instantiable},
CircuitField,
};
pub trait EccInstructions<F: CircuitField, C: CircuitCurve>:
AssertionInstructions<F, Self::Point>
where
Self::Point: InnerValue<Element = C::CryptographicGroup>,
Self::Coordinate: Instantiable<F> + InnerValue<Element = C::Base> + InnerConstants,
Self::Scalar: InnerValue<Element = C::ScalarField>,
{
type Point: Clone + Debug;
type Coordinate: Clone + Debug;
type Scalar: InnerValue;
fn add(
&self,
layouter: &mut impl Layouter<F>,
p: &Self::Point,
q: &Self::Point,
) -> Result<Self::Point, Error>;
fn double(
&self,
layouter: &mut impl Layouter<F>,
p: &Self::Point,
) -> Result<Self::Point, Error>;
fn negate(
&self,
layouter: &mut impl Layouter<F>,
p: &Self::Point,
) -> Result<Self::Point, Error>;
fn msm(
&self,
layouter: &mut impl Layouter<F>,
scalars: &[Self::Scalar],
bases: &[Self::Point],
) -> Result<Self::Point, Error>;
fn msm_by_bounded_scalars(
&self,
layouter: &mut impl Layouter<F>,
scalars: &[(Self::Scalar, usize)],
bases: &[Self::Point],
) -> Result<Self::Point, Error> {
let scalars = scalars.iter().map(|s| s.0.clone()).collect::<Vec<_>>();
self.msm(layouter, &scalars, bases)
}
fn mul_by_constant(
&self,
layouter: &mut impl Layouter<F>,
scalar: C::ScalarField,
base: &Self::Point,
) -> Result<Self::Point, Error>;
fn point_from_coordinates(
&self,
layouter: &mut impl Layouter<F>,
x: &Self::Coordinate,
y: &Self::Coordinate,
) -> Result<Self::Point, Error>;
fn assign_without_subgroup_check(
&self,
layouter: &mut impl Layouter<F>,
value: Value<C::CryptographicGroup>,
) -> Result<Self::Point, Error>;
fn x_coordinate(&self, point: &Self::Point) -> Self::Coordinate;
fn y_coordinate(&self, point: &Self::Point) -> Self::Coordinate;
fn base_field(&self) -> &impl DecompositionInstructions<F, Self::Coordinate>;
}
#[cfg(test)]
pub(crate) mod tests {
use std::{cmp::min, marker::PhantomData};
use ff::{Field, FromUniformBytes, PrimeField};
use group::Group;
use midnight_proofs::{
circuit::{Chip, Layouter, SimpleFloorPlanner, Value},
dev::MockProver,
plonk::{Circuit, ConstraintSystem},
};
use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;
use super::*;
use crate::{
instructions::{AssertionInstructions, AssignmentInstructions},
testing_utils::FromScratch,
utils::circuit_modeling::{circuit_to_json, cost_measure_end, cost_measure_start},
};
#[derive(Clone, Copy, Debug)]
enum Operation {
Assign,
AssignWithoutSubgroupCheck,
Add,
Double,
Neg,
Msm,
MsmBounded,
MulByConstant,
Coordinates,
}
#[derive(Clone, Debug)]
struct TestCircuit<F, C, EccChip>
where
F: CircuitField,
C: CircuitCurve,
{
inputs: Vec<C::CryptographicGroup>,
scalars: Option<Vec<(C::ScalarField, usize)>>,
expected: C::CryptographicGroup,
operation: Operation,
_marker: PhantomData<(F, EccChip)>,
}
impl<F, C, EccChip> Circuit<F> for TestCircuit<F, C, EccChip>
where
F: CircuitField,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
type Config = <EccChip as FromScratch<F>>::Config;
type FloorPlanner = SimpleFloorPlanner;
type Params = ();
fn without_witnesses(&self) -> Self {
unreachable!()
}
fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
let committed_instance_column = meta.instance_column();
let instance_column = meta.instance_column();
EccChip::configure_from_scratch(
meta,
&mut vec![],
&mut vec![],
&[committed_instance_column, instance_column],
)
}
fn synthesize(
&self,
config: Self::Config,
mut layouter: impl Layouter<F>,
) -> Result<(), Error> {
let ecc_chip = EccChip::new_from_scratch(&config);
let y_idx = min(self.inputs.len() - 1, 1);
let p: EccChip::Point = ecc_chip
.assign_without_subgroup_check(&mut layouter, Value::known(self.inputs[0]))?;
let q: EccChip::Point = ecc_chip.assign_fixed(&mut layouter, self.inputs[y_idx])?;
cost_measure_start(&mut layouter);
let res = match self.operation {
Operation::Assign => ecc_chip.assign(&mut layouter, Value::known(self.inputs[0])),
Operation::AssignWithoutSubgroupCheck => ecc_chip
.assign_without_subgroup_check(&mut layouter, Value::known(self.inputs[0])),
Operation::Add => ecc_chip.add(&mut layouter, &p, &q),
Operation::Double => ecc_chip.double(&mut layouter, &p),
Operation::Neg => ecc_chip.negate(&mut layouter, &p),
Operation::Msm => {
let scalars = self
.scalars
.clone()
.unwrap()
.iter()
.map(|s| ecc_chip.assign(&mut layouter, Value::known(s.0)))
.collect::<Result<Vec<_>, Error>>()?;
let bases = self
.inputs
.iter()
.map(|p| ecc_chip.assign_fixed(&mut layouter, *p))
.collect::<Result<Vec<_>, Error>>()?;
ecc_chip.msm(&mut layouter, &scalars, &bases)
}
Operation::MsmBounded => {
let scalars = self
.scalars
.clone()
.unwrap()
.iter()
.map(|s| {
let assigned_s = ecc_chip.assign(&mut layouter, Value::known(s.0))?;
Ok((assigned_s, s.1))
})
.collect::<Result<Vec<_>, Error>>()?;
let bases = self
.inputs
.iter()
.map(|p| ecc_chip.assign_fixed(&mut layouter, *p))
.collect::<Result<Vec<_>, Error>>()?;
ecc_chip.msm_by_bounded_scalars(&mut layouter, &scalars, &bases)
}
Operation::MulByConstant => {
let s = self.scalars.clone().unwrap()[0].0;
ecc_chip.mul_by_constant(&mut layouter, s, &p)
}
Operation::Coordinates => {
let px = ecc_chip.x_coordinate(&p);
let py = ecc_chip.y_coordinate(&p);
ecc_chip.point_from_coordinates(&mut layouter, &px, &py)
}
}?;
cost_measure_end(&mut layouter);
ecc_chip.assert_equal_to_fixed(&mut layouter, &res, self.expected)?;
ecc_chip.load_from_scratch(&mut layouter)
}
}
#[allow(clippy::too_many_arguments)]
fn run<F, C, EccChip>(
inputs: &[C::CryptographicGroup],
scalars: Option<&[(C::ScalarField, usize)]>,
expected: &C::CryptographicGroup,
operation: Operation,
must_pass: bool,
cost_model: bool,
chip_name: &str,
op_name: &str,
) where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let circuit = TestCircuit::<F, C, EccChip> {
inputs: inputs.to_vec(),
scalars: scalars.map(|v| v.to_vec()),
expected: *expected,
operation,
_marker: PhantomData,
};
let public_inputs = vec![vec![], vec![]];
match MockProver::run(&circuit, public_inputs) {
Ok(prover) => match prover.verify() {
Ok(()) => assert!(must_pass),
Err(e) => assert!(!must_pass, "Failed verifier with error {e:?}"),
},
Err(e) => assert!(!must_pass, "Failed prover with error {e:?}"),
}
if cost_model {
circuit_to_json(chip_name, op_name, circuit);
}
}
pub fn test_assign<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let p = C::CryptographicGroup::random(&mut rng);
let wrong = C::CryptographicGroup::random(&mut rng);
run::<F, C, EccChip>(
&[p],
None,
&p,
Operation::Assign,
true,
true,
name,
"assign_with_subgroup_check",
);
run::<F, C, EccChip>(&[p], None, &wrong, Operation::Assign, false, false, "", "");
}
pub fn test_assign_without_subgroup_check<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let p = C::CryptographicGroup::random(&mut rng);
let wrong = C::CryptographicGroup::random(&mut rng);
run::<F, C, EccChip>(
&[p],
None,
&p,
Operation::AssignWithoutSubgroupCheck,
true,
true,
name,
"assign_without_subgroup_check",
);
run::<F, C, EccChip>(
&[p],
None,
&wrong,
Operation::AssignWithoutSubgroupCheck,
false,
false,
"",
"",
);
}
pub fn test_add<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let id = C::CryptographicGroup::identity();
let g = C::CryptographicGroup::generator();
let r = C::CryptographicGroup::random(&mut rng);
let s = C::CryptographicGroup::random(&mut rng);
let wrong = C::CryptographicGroup::random(&mut rng);
let mut cost_model = true;
[
(&id, &r),
(&r, &id),
(&g, &r),
(&r, &g),
(&r, &r),
(&r, &s),
(&id, &id),
(&id, &g),
(&g, &id),
(&g, &g),
]
.into_iter()
.for_each(|(x, y)| {
let inputs = vec![*x, *y];
let expected = *x + *y;
run::<F, C, EccChip>(
&inputs,
None,
&expected,
Operation::Add,
true,
cost_model,
name,
"add",
);
cost_model = false;
run::<F, C, EccChip>(&inputs, None, &wrong, Operation::Add, false, false, "", "");
});
}
pub fn test_double<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let wrong = C::CryptographicGroup::random(&mut rng);
let mut cost_model = true;
[
C::CryptographicGroup::identity(),
C::CryptographicGroup::generator(),
C::CryptographicGroup::random(&mut rng),
]
.into_iter()
.for_each(|x| {
let inputs = vec![x];
let expected = x + x;
run::<F, C, EccChip>(
&inputs,
None,
&expected,
Operation::Double,
true,
cost_model,
name,
"double",
);
cost_model = false;
run::<F, C, EccChip>(
&inputs,
None,
&wrong,
Operation::Double,
false,
false,
"",
"",
);
});
}
pub fn test_negate<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let wrong = C::CryptographicGroup::random(&mut rng);
let mut cost_model = true;
[
C::CryptographicGroup::random(&mut rng),
C::CryptographicGroup::identity(),
C::CryptographicGroup::generator(),
]
.into_iter()
.for_each(|x| {
let inputs = vec![x];
let expected = -x;
run::<F, C, EccChip>(
&inputs,
None,
&expected,
Operation::Neg,
true,
cost_model,
name,
"neg",
);
cost_model = false;
run::<F, C, EccChip>(&inputs, None, &wrong, Operation::Neg, false, false, "", "");
});
}
pub fn test_msm<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let n = 3;
let inputs = (0..n).map(|_| C::CryptographicGroup::random(&mut rng)).collect::<Vec<_>>();
let scalars = (0..n)
.map(|_| {
(
C::ScalarField::random(&mut rng),
C::ScalarField::NUM_BITS as usize,
)
})
.collect::<Vec<_>>();
let expected = (inputs.clone().into_iter().zip(scalars.clone().iter()))
.fold(C::CryptographicGroup::identity(), |acc, (base, scalar)| {
acc + (base * scalar.0)
});
let wrong = C::CryptographicGroup::random(&mut rng);
run::<F, C, EccChip>(
&inputs,
Some(&scalars),
&expected,
Operation::Msm,
true,
true,
name,
"msm_3",
);
run::<F, C, EccChip>(
&inputs,
Some(&scalars),
&wrong,
Operation::Msm,
false,
false,
"",
"",
);
}
pub fn test_msm_by_bounded_scalars<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let n = 3;
let r = C::ScalarField::random(&mut rng);
let inputs = (0..n).map(|_| C::CryptographicGroup::random(&mut rng)).collect::<Vec<_>>();
let scalars = [
(C::ScalarField::from(3), 4),
(C::ScalarField::from(1025), 12),
(r, C::ScalarField::NUM_BITS as usize),
]
.to_vec();
let expected = (inputs.clone().into_iter().zip(scalars.clone().iter()))
.fold(C::CryptographicGroup::identity(), |acc, (base, scalar)| {
acc + (base * scalar.0)
});
let wrong = C::CryptographicGroup::random(&mut rng);
run::<F, C, EccChip>(
&inputs,
Some(&scalars),
&expected,
Operation::MsmBounded,
true,
true,
name,
"msm_by_bounded_scalars_3",
);
run::<F, C, EccChip>(
&inputs,
Some(&scalars),
&wrong,
Operation::MsmBounded,
false,
false,
name,
"",
);
}
pub fn test_mul_by_constant<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let base = C::CryptographicGroup::random(&mut rng);
let s = C::ScalarField::random(&mut rng);
let mut cost_model = true;
[
(base, s, base * s, true),
(base, C::ScalarField::ONE, base, true),
(base, s, C::CryptographicGroup::identity(), false),
(
C::CryptographicGroup::identity(),
C::ScalarField::from(123456),
C::CryptographicGroup::identity(),
true,
),
(
C::CryptographicGroup::generator(),
C::ScalarField::ZERO,
C::CryptographicGroup::identity(),
true,
),
]
.into_iter()
.for_each(|(base, s, expected, must_pass)| {
run::<F, C, EccChip>(
&[base],
Some(&[(s, C::ScalarField::NUM_BITS as usize)]),
&expected,
Operation::MulByConstant,
must_pass,
cost_model,
name,
"mul_by_constant",
);
cost_model = false;
})
}
pub fn test_coordinates<F, C, EccChip>(name: &str)
where
F: CircuitField + FromUniformBytes<64> + Ord,
C: CircuitCurve,
EccChip: EccInstructions<F, C>
+ AssignmentInstructions<F, EccChip::Point>
+ AssignmentInstructions<F, EccChip::Scalar>
+ AssertionInstructions<F, EccChip::Point>
+ Chip<F>
+ FromScratch<F>,
EccChip::Point: InnerValue<Element = C::CryptographicGroup> + Clone,
{
let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
let wrong = C::CryptographicGroup::random(&mut rng);
let id_from_coord_ok = {
C::CryptographicGroup::identity()
.into()
.coordinates()
.is_some_and(|(x, y)| C::from_xy(x, y).is_some())
};
let mut cost_model = true;
[
(C::CryptographicGroup::random(&mut rng), true),
(C::CryptographicGroup::identity(), id_from_coord_ok),
(C::CryptographicGroup::generator(), true),
]
.into_iter()
.for_each(|(x, must_pass)| {
let inputs = vec![x];
run::<F, C, EccChip>(
&inputs,
None,
&x,
Operation::Coordinates,
must_pass,
cost_model & must_pass,
name,
"coordinates",
);
if must_pass {
cost_model = false
}
run::<F, C, EccChip>(
&inputs,
None,
&wrong,
Operation::Coordinates,
false,
false,
"",
"",
);
});
}
}