use ark_ec::{
short_weierstrass::{Affine as SWAffine, Projective as SWProjective, SWCurveConfig},
AffineRepr, CurveConfig, CurveGroup,
};
use ark_ff::{AdditiveGroup, BitIteratorBE, Field, One, PrimeField, Zero};
use ark_relations::r1cs::{ConstraintSystemRef, Namespace, SynthesisError};
use ark_std::{borrow::Borrow, marker::PhantomData, ops::Mul};
use educe::Educe;
use non_zero_affine::NonZeroAffineVar;
use crate::{
convert::{ToBitsGadget, ToBytesGadget, ToConstraintFieldGadget},
fields::{emulated_fp::EmulatedFpVar, fp::FpVar},
prelude::*,
Vec,
};
pub mod bls12;
pub mod mnt4;
pub mod mnt6;
pub mod non_zero_affine;
type BasePrimeField<P> = <<P as CurveConfig>::BaseField as Field>::BasePrimeField;
#[derive(Educe)]
#[educe(Debug, Clone)]
#[must_use]
pub struct ProjectiveVar<P: SWCurveConfig, F: FieldVar<P::BaseField, BasePrimeField<P>>>
where
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
pub x: F,
pub y: F,
pub z: F,
#[educe(Debug(ignore))]
_params: PhantomData<P>,
}
#[derive(Educe)]
#[educe(Debug, Clone)]
#[must_use]
pub struct AffineVar<P: SWCurveConfig, F: FieldVar<P::BaseField, BasePrimeField<P>>>
where
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
pub x: F,
pub y: F,
pub infinity: Boolean<BasePrimeField<P>>,
#[educe(Debug(ignore))]
_params: PhantomData<P>,
}
impl<P, F> AffineVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
fn new(x: F, y: F, infinity: Boolean<BasePrimeField<P>>) -> Self {
Self {
x,
y,
infinity,
_params: PhantomData,
}
}
pub fn value(&self) -> Result<SWAffine<P>, SynthesisError> {
Ok(match self.infinity.value()? {
true => SWAffine::identity(),
false => SWAffine::new(self.x.value()?, self.y.value()?),
})
}
}
impl<P, F> ToConstraintFieldGadget<BasePrimeField<P>> for AffineVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
F: ToConstraintFieldGadget<BasePrimeField<P>>,
{
fn to_constraint_field(&self) -> Result<Vec<FpVar<BasePrimeField<P>>>, SynthesisError> {
let mut res = Vec::<FpVar<BasePrimeField<P>>>::new();
res.extend_from_slice(&self.x.to_constraint_field()?);
res.extend_from_slice(&self.y.to_constraint_field()?);
res.extend_from_slice(&self.infinity.to_constraint_field()?);
Ok(res)
}
}
impl<P, F> R1CSVar<BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
type Value = SWProjective<P>;
fn cs(&self) -> ConstraintSystemRef<BasePrimeField<P>> {
self.x.cs().or(self.y.cs()).or(self.z.cs())
}
fn value(&self) -> Result<Self::Value, SynthesisError> {
let (x, y, z) = (self.x.value()?, self.y.value()?, self.z.value()?);
let result = if let Some(z_inv) = z.inverse() {
SWAffine::new(x * &z_inv, y * &z_inv)
} else {
SWAffine::identity()
};
Ok(result.into())
}
}
impl<P: SWCurveConfig, F: FieldVar<P::BaseField, BasePrimeField<P>>> ProjectiveVar<P, F>
where
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
pub fn new(x: F, y: F, z: F) -> Self {
Self {
x,
y,
z,
_params: PhantomData,
}
}
#[tracing::instrument(target = "r1cs")]
pub fn to_affine(&self) -> Result<AffineVar<P, F>, SynthesisError> {
if self.is_constant() {
let point = self.value()?.into_affine();
let x = F::new_constant(ConstraintSystemRef::None, point.x)?;
let y = F::new_constant(ConstraintSystemRef::None, point.y)?;
let infinity = Boolean::constant(point.infinity);
Ok(AffineVar::new(x, y, infinity))
} else {
let cs = self.cs();
let infinity = self.is_zero()?;
let zero_affine = SWAffine::<P>::zero();
let zero_x = F::new_constant(cs.clone(), &zero_affine.x)?;
let zero_y = F::new_constant(cs.clone(), &zero_affine.y)?;
let z_inv = F::new_witness(ark_relations::ns!(cs, "z_inverse"), || {
Ok(self.z.value()?.inverse().unwrap_or_else(P::BaseField::zero))
})?;
z_inv.mul_equals(&self.z, &F::from(!&infinity))?;
let non_zero_x = &self.x * &z_inv;
let non_zero_y = &self.y * &z_inv;
let x = infinity.select(&zero_x, &non_zero_x)?;
let y = infinity.select(&zero_y, &non_zero_y)?;
Ok(AffineVar::new(x, y, infinity))
}
}
#[tracing::instrument(target = "r1cs", skip(cs, f))]
pub fn new_variable_omit_on_curve_check(
cs: impl Into<Namespace<BasePrimeField<P>>>,
f: impl FnOnce() -> Result<SWProjective<P>, SynthesisError>,
mode: AllocationMode,
) -> Result<Self, SynthesisError> {
let ns = cs.into();
let cs = ns.cs();
let (x, y, z) = match f() {
Ok(ge) => {
let ge = ge.into_affine();
if ge.is_zero() {
(
Ok(P::BaseField::zero()),
Ok(P::BaseField::one()),
Ok(P::BaseField::zero()),
)
} else {
(Ok(ge.x), Ok(ge.y), Ok(P::BaseField::one()))
}
},
_ => (
Err(SynthesisError::AssignmentMissing),
Err(SynthesisError::AssignmentMissing),
Err(SynthesisError::AssignmentMissing),
),
};
let x = F::new_variable(ark_relations::ns!(cs, "x"), || x, mode)?;
let y = F::new_variable(ark_relations::ns!(cs, "y"), || y, mode)?;
let z = F::new_variable(ark_relations::ns!(cs, "z"), || z, mode)?;
Ok(Self::new(x, y, z))
}
#[tracing::instrument(target = "r1cs", skip(self, other))]
pub(crate) fn add_mixed(&self, other: &NonZeroAffineVar<P, F>) -> Result<Self, SynthesisError> {
let three_b = P::COEFF_B.double() + &P::COEFF_B;
let (x1, y1, z1) = (&self.x, &self.y, &self.z);
let (x2, y2) = (&other.x, &other.y);
let xx = x1 * x2; let yy = y1 * y2; let xy_pairs = ((x1 + y1) * &(x2 + y2)) - (&xx + &yy); let xz_pairs = (x2 * z1) + x1; let yz_pairs = (y2 * z1) + y1; let axz = mul_by_coeff_a::<P, F>(&xz_pairs); let bz3_part = &axz + z1 * three_b; let yy_m_bz3 = &yy - &bz3_part; let yy_p_bz3 = &yy + &bz3_part; let azz = mul_by_coeff_a::<P, F>(z1); let xx3_p_azz = xx.double().unwrap() + &xx + &azz; let bxz3 = &xz_pairs * three_b; let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; let x = (&yy_m_bz3 * &xy_pairs) - &yz_pairs * &b3_xz_pairs; let y = (&yy_p_bz3 * &yy_m_bz3) + &xx3_p_azz * b3_xz_pairs; let z = (&yy_p_bz3 * &yz_pairs) + xy_pairs * xx3_p_azz; Ok(ProjectiveVar::new(x, y, z))
}
#[tracing::instrument(
target = "r1cs",
skip(self, mul_result, multiple_of_power_of_two, bits)
)]
fn fixed_scalar_mul_le(
&self,
mul_result: &mut Self,
multiple_of_power_of_two: &mut NonZeroAffineVar<P, F>,
bits: &[&Boolean<BasePrimeField<P>>],
) -> Result<(), SynthesisError> {
let scalar_modulus_bits = <P::ScalarField as PrimeField>::MODULUS_BIT_SIZE as usize;
assert!(scalar_modulus_bits >= bits.len());
let split_len = ark_std::cmp::min(scalar_modulus_bits - 2, bits.len());
let (affine_bits, proj_bits) = bits.split_at(split_len);
let mut accumulator = multiple_of_power_of_two.clone();
let initial_acc_value = accumulator.into_projective();
multiple_of_power_of_two.double_in_place()?;
for bit in affine_bits.iter().skip(1) {
if bit.is_constant() {
if *bit == &Boolean::TRUE {
accumulator = accumulator.add_unchecked(multiple_of_power_of_two)?;
}
} else {
let temp = accumulator.add_unchecked(multiple_of_power_of_two)?;
accumulator = bit.select(&temp, &accumulator)?;
}
multiple_of_power_of_two.double_in_place()?;
}
let result = accumulator.into_projective();
let subtrahend = bits[0].select(&Self::zero(), &initial_acc_value)?;
*mul_result += result - subtrahend;
for bit in proj_bits {
if bit.is_constant() {
if *bit == &Boolean::TRUE {
*mul_result += &multiple_of_power_of_two.into_projective();
}
} else {
let temp = &*mul_result + &multiple_of_power_of_two.into_projective();
*mul_result = bit.select(&temp, &mul_result)?;
}
multiple_of_power_of_two.double_in_place()?;
}
Ok(())
}
}
impl<P, F> CurveVar<SWProjective<P>, BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
fn constant(g: SWProjective<P>) -> Self {
let cs = ConstraintSystemRef::None;
Self::new_variable_omit_on_curve_check(cs, || Ok(g), AllocationMode::Constant).unwrap()
}
fn zero() -> Self {
Self::new(F::zero(), F::one(), F::zero())
}
fn is_zero(&self) -> Result<Boolean<BasePrimeField<P>>, SynthesisError> {
self.z.is_zero()
}
#[tracing::instrument(target = "r1cs", skip(cs, f))]
fn new_variable_omit_prime_order_check(
cs: impl Into<Namespace<BasePrimeField<P>>>,
f: impl FnOnce() -> Result<SWProjective<P>, SynthesisError>,
mode: AllocationMode,
) -> Result<Self, SynthesisError> {
let ns = cs.into();
let cs = ns.cs();
let g = Self::new_variable_omit_on_curve_check(cs, f, mode)?;
if mode != AllocationMode::Constant {
let b = P::COEFF_B;
let a = P::COEFF_A;
let x2 = g.x.square()?;
let y2 = g.y.square()?;
let z2 = g.z.square()?;
let t = &g.x * (x2 + &z2 * a);
g.z.mul_equals(&(y2 - z2 * b), &t)?;
}
Ok(g)
}
#[tracing::instrument(target = "r1cs")]
fn enforce_prime_order(&self) -> Result<(), SynthesisError> {
unimplemented!("cannot enforce prime order");
}
#[inline]
#[tracing::instrument(target = "r1cs")]
fn double_in_place(&mut self) -> Result<(), SynthesisError> {
let three_b = P::COEFF_B.double() + &P::COEFF_B;
let xx = self.x.square()?; let yy = self.y.square()?; let zz = self.z.square()?; let xy2 = (&self.x * &self.y).double()?; let xz2 = (&self.x * &self.z).double()?; let axz2 = mul_by_coeff_a::<P, F>(&xz2); let bzz3_part = &axz2 + &zz * three_b; let yy_m_bzz3 = &yy - &bzz3_part; let yy_p_bzz3 = &yy + &bzz3_part; let y_frag = yy_p_bzz3 * &yy_m_bzz3; let x_frag = yy_m_bzz3 * &xy2; let bxz3 = xz2 * three_b; let azz = mul_by_coeff_a::<P, F>(&zz); let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; let xx3_p_azz = (xx.double()? + &xx + &azz) * &b3_xz_pairs; let y = y_frag + &xx3_p_azz; let yz2 = (&self.y * &self.z).double()?; let x = x_frag - &(b3_xz_pairs * &yz2); let z = (yz2 * &yy).double()?.double()?; self.x = x;
self.y = y;
self.z = z;
Ok(())
}
#[tracing::instrument(target = "r1cs")]
fn negate(&self) -> Result<Self, SynthesisError> {
Ok(Self::new(self.x.clone(), self.y.negate()?, self.z.clone()))
}
#[tracing::instrument(target = "r1cs", skip(bits))]
fn scalar_mul_le<'a>(
&self,
bits: impl Iterator<Item = &'a Boolean<BasePrimeField<P>>>,
) -> Result<Self, SynthesisError> {
if self.is_constant() {
if self.value().unwrap().is_zero() {
return Ok(self.clone());
}
}
let self_affine = self.to_affine()?;
let (x, y, infinity) = (self_affine.x, self_affine.y, self_affine.infinity);
let x = infinity.select(&F::constant(P::GENERATOR.x), &x)?;
let y = infinity.select(&F::constant(P::GENERATOR.y), &y)?;
let non_zero_self = NonZeroAffineVar::new(x, y);
let mut bits = bits.collect::<Vec<_>>();
if bits.len() == 0 {
return Ok(Self::zero());
}
bits = bits
.into_iter()
.rev()
.skip_while(|b| b.is_constant() && (b.value().unwrap() == false))
.collect();
bits.reverse();
let scalar_modulus_bits = <P::ScalarField as PrimeField>::MODULUS_BIT_SIZE;
let mut mul_result = Self::zero();
let mut power_of_two_times_self = non_zero_self;
for bits in bits.chunks(scalar_modulus_bits as usize) {
self.fixed_scalar_mul_le(&mut mul_result, &mut power_of_two_times_self, bits)?;
}
infinity.select(&Self::zero(), &mul_result)
}
#[tracing::instrument(target = "r1cs", skip(scalar_bits_with_bases))]
fn precomputed_base_scalar_mul_le<'a, I, B>(
&mut self,
scalar_bits_with_bases: I,
) -> Result<(), SynthesisError>
where
I: Iterator<Item = (B, &'a SWProjective<P>)>,
B: Borrow<Boolean<BasePrimeField<P>>>,
{
let (bits, bases): (Vec<_>, Vec<_>) = scalar_bits_with_bases
.map(|(b, c)| (b.borrow().clone(), *c))
.unzip();
let base = bases[0];
*self += Self::constant(base).scalar_mul_le(bits.iter())?;
Ok(())
}
}
impl<P, F> ToConstraintFieldGadget<BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
F: ToConstraintFieldGadget<BasePrimeField<P>>,
{
fn to_constraint_field(&self) -> Result<Vec<FpVar<BasePrimeField<P>>>, SynthesisError> {
self.to_affine()?.to_constraint_field()
}
}
fn mul_by_coeff_a<P: SWCurveConfig, F: FieldVar<P::BaseField, BasePrimeField<P>>>(f: &F) -> F
where
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
if !P::COEFF_A.is_zero() {
f * P::COEFF_A
} else {
F::zero()
}
}
impl_bounded_ops!(
ProjectiveVar<P, F>,
SWProjective<P>,
Add,
add,
AddAssign,
add_assign,
|mut this: &'a ProjectiveVar<P, F>, mut other: &'a ProjectiveVar<P, F>| {
if this.is_constant() {
core::mem::swap(&mut this, &mut other);
}
if other.is_constant() {
let other = other.value().unwrap();
if other.is_zero() {
this.clone()
} else {
let x = F::constant(other.x);
let y = F::constant(other.y);
this.add_mixed(&NonZeroAffineVar::new(x, y)).unwrap()
}
} else {
let three_b = P::COEFF_B.double() + &P::COEFF_B;
let (x1, y1, z1) = (&this.x, &this.y, &this.z);
let (x2, y2, z2) = (&other.x, &other.y, &other.z);
let xx = x1 * x2; let yy = y1 * y2; let zz = z1 * z2; let xy_pairs = ((x1 + y1) * &(x2 + y2)) - (&xx + &yy); let xz_pairs = ((x1 + z1) * &(x2 + z2)) - (&xx + &zz); let yz_pairs = ((y1 + z1) * &(y2 + z2)) - (&yy + &zz); let axz = mul_by_coeff_a::<P, F>(&xz_pairs); let bzz3_part = &axz + &zz * three_b; let yy_m_bzz3 = &yy - &bzz3_part; let yy_p_bzz3 = &yy + &bzz3_part; let azz = mul_by_coeff_a::<P, F>(&zz);
let xx3_p_azz = xx.double().unwrap() + &xx + &azz; let bxz3 = &xz_pairs * three_b; let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; let x = (&yy_m_bzz3 * &xy_pairs) - &yz_pairs * &b3_xz_pairs; let y = (&yy_p_bzz3 * &yy_m_bzz3) + &xx3_p_azz * b3_xz_pairs; let z = (&yy_p_bzz3 * &yz_pairs) + xy_pairs * xx3_p_azz; ProjectiveVar::new(x, y, z)
}
},
|this: &'a ProjectiveVar<P, F>, other: SWProjective<P>| {
this + ProjectiveVar::constant(other)
},
(F: FieldVar<P::BaseField, BasePrimeField<P>>, P: SWCurveConfig),
for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
);
impl_bounded_ops!(
ProjectiveVar<P, F>,
SWProjective<P>,
Sub,
sub,
SubAssign,
sub_assign,
|this: &'a ProjectiveVar<P, F>, other: &'a ProjectiveVar<P, F>| this + other.negate().unwrap(),
|this: &'a ProjectiveVar<P, F>, other: SWProjective<P>| this - ProjectiveVar::constant(other),
(F: FieldVar<P::BaseField, BasePrimeField<P>>, P: SWCurveConfig),
for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>
);
impl_bounded_ops_diff!(
ProjectiveVar<P, F>,
SWProjective<P>,
EmulatedFpVar<P::ScalarField, BasePrimeField<P>>,
P::ScalarField,
Mul,
mul,
MulAssign,
mul_assign,
|this: &'a ProjectiveVar<P, F>, other: &'a EmulatedFpVar<P::ScalarField, BasePrimeField<P>>| {
if this.is_constant() && other.is_constant() {
assert!(this.is_constant() && other.is_constant());
ProjectiveVar::constant(this.value().unwrap() * &other.value().unwrap())
} else {
let bits = other.to_bits_le().unwrap();
this.scalar_mul_le(bits.iter()).unwrap()
}
},
|this: &'a ProjectiveVar<P, F>, other: P::ScalarField| this * EmulatedFpVar::constant(other),
(F: FieldVar<P::BaseField, BasePrimeField<P>>, P: SWCurveConfig),
for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
);
impl<'a, P, F> GroupOpsBounds<'a, SWProjective<P>, ProjectiveVar<P, F>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
{
}
impl<'a, P, F> GroupOpsBounds<'a, SWProjective<P>, ProjectiveVar<P, F>> for &'a ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
{
}
impl<P, F> CondSelectGadget<BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
#[inline]
#[tracing::instrument(target = "r1cs")]
fn conditionally_select(
cond: &Boolean<BasePrimeField<P>>,
true_value: &Self,
false_value: &Self,
) -> Result<Self, SynthesisError> {
let x = cond.select(&true_value.x, &false_value.x)?;
let y = cond.select(&true_value.y, &false_value.y)?;
let z = cond.select(&true_value.z, &false_value.z)?;
Ok(Self::new(x, y, z))
}
}
impl<P, F> EqGadget<BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
#[tracing::instrument(target = "r1cs")]
fn is_eq(&self, other: &Self) -> Result<Boolean<BasePrimeField<P>>, SynthesisError> {
let x_equal = (&self.x * &other.z).is_eq(&(&other.x * &self.z))?;
let y_equal = (&self.y * &other.z).is_eq(&(&other.y * &self.z))?;
let coordinates_equal = x_equal & y_equal;
let both_are_zero = self.is_zero()? & other.is_zero()?;
Ok(both_are_zero | coordinates_equal)
}
#[inline]
#[tracing::instrument(target = "r1cs")]
fn conditional_enforce_equal(
&self,
other: &Self,
condition: &Boolean<BasePrimeField<P>>,
) -> Result<(), SynthesisError> {
let x_equal = (&self.x * &other.z).is_eq(&(&other.x * &self.z))?;
let y_equal = (&self.y * &other.z).is_eq(&(&other.y * &self.z))?;
let coordinates_equal = x_equal & y_equal;
let both_are_zero = self.is_zero()? & other.is_zero()?;
(both_are_zero | coordinates_equal).conditional_enforce_equal(&Boolean::TRUE, condition)
}
#[inline]
#[tracing::instrument(target = "r1cs")]
fn conditional_enforce_not_equal(
&self,
other: &Self,
condition: &Boolean<BasePrimeField<P>>,
) -> Result<(), SynthesisError> {
let is_equal = self.is_eq(other)?;
(is_equal & condition).enforce_equal(&Boolean::FALSE)
}
}
impl<P, F> AllocVar<SWAffine<P>, BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
fn new_variable<T: Borrow<SWAffine<P>>>(
cs: impl Into<Namespace<BasePrimeField<P>>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
mode: AllocationMode,
) -> Result<Self, SynthesisError> {
Self::new_variable(
cs,
|| f().map(|b| SWProjective::from((*b.borrow()).clone())),
mode,
)
}
}
impl<P, F> AllocVar<SWProjective<P>, BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
fn new_variable<T: Borrow<SWProjective<P>>>(
cs: impl Into<Namespace<BasePrimeField<P>>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
mode: AllocationMode,
) -> Result<Self, SynthesisError> {
let ns = cs.into();
let cs = ns.cs();
let f = || Ok(*f()?.borrow());
match mode {
AllocationMode::Constant => Self::new_variable_omit_prime_order_check(cs, f, mode),
AllocationMode::Input => Self::new_variable_omit_prime_order_check(cs, f, mode),
AllocationMode::Witness => {
let mut power_of_2: u32 = 0;
let mut cofactor = P::COFACTOR.to_vec();
while cofactor[0] % 2 == 0 {
div2(&mut cofactor);
power_of_2 += 1;
}
let cofactor_weight = BitIteratorBE::new(cofactor.as_slice())
.filter(|b| *b)
.count();
let modulus_minus_1 = (-P::ScalarField::one()).into_bigint(); let modulus_minus_1_weight =
BitIteratorBE::new(modulus_minus_1).filter(|b| *b).count();
let (mut ge, iter) = if cofactor_weight < modulus_minus_1_weight {
let ge = Self::new_variable_omit_prime_order_check(
ark_relations::ns!(cs, "Witness without subgroup check with cofactor mul"),
|| f().map(|g| g.into_affine().mul_by_cofactor_inv().into()),
mode,
)?;
(
ge,
BitIteratorBE::without_leading_zeros(cofactor.as_slice()),
)
} else {
let ge = Self::new_variable_omit_prime_order_check(
ark_relations::ns!(cs, "Witness without subgroup check with `r` check"),
|| {
f().map(|g| {
let g = g.into_affine();
let power_of_two = P::ScalarField::ONE.into_bigint() << power_of_2;
let power_of_two_inv = P::ScalarField::from_bigint(power_of_two)
.and_then(|n| n.inverse())
.unwrap();
g.mul(power_of_two_inv)
})
},
mode,
)?;
(
ge,
BitIteratorBE::without_leading_zeros(modulus_minus_1.as_ref()),
)
};
for _ in 0..power_of_2 {
ge.double_in_place()?;
}
let mut result = Self::zero();
for b in iter {
result.double_in_place()?;
if b {
result += &ge
}
}
if cofactor_weight < modulus_minus_1_weight {
Ok(result)
} else {
ge.enforce_equal(&ge)?;
Ok(ge)
}
},
}
}
}
#[inline]
fn div2(limbs: &mut [u64]) {
let mut t = 0;
for i in limbs.iter_mut().rev() {
let t2 = *i << 63;
*i >>= 1;
*i |= t;
t = t2;
}
}
impl<P, F> ToBitsGadget<BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
#[tracing::instrument(target = "r1cs")]
fn to_bits_le(&self) -> Result<Vec<Boolean<BasePrimeField<P>>>, SynthesisError> {
let g = self.to_affine()?;
let mut bits = g.x.to_bits_le()?;
let y_bits = g.y.to_bits_le()?;
bits.extend_from_slice(&y_bits);
bits.push(g.infinity);
Ok(bits)
}
#[tracing::instrument(target = "r1cs")]
fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<BasePrimeField<P>>>, SynthesisError> {
let g = self.to_affine()?;
let mut bits = g.x.to_non_unique_bits_le()?;
let y_bits = g.y.to_non_unique_bits_le()?;
bits.extend_from_slice(&y_bits);
bits.push(g.infinity);
Ok(bits)
}
}
impl<P, F> ToBytesGadget<BasePrimeField<P>> for ProjectiveVar<P, F>
where
P: SWCurveConfig,
F: FieldVar<P::BaseField, BasePrimeField<P>>,
for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
{
#[tracing::instrument(target = "r1cs")]
fn to_bytes_le(&self) -> Result<Vec<UInt8<BasePrimeField<P>>>, SynthesisError> {
let g = self.to_affine()?;
let mut bytes = g.x.to_bytes_le()?;
let y_bytes = g.y.to_bytes_le()?;
let inf_bytes = g.infinity.to_bytes_le()?;
bytes.extend_from_slice(&y_bytes);
bytes.extend_from_slice(&inf_bytes);
Ok(bytes)
}
#[tracing::instrument(target = "r1cs")]
fn to_non_unique_bytes_le(&self) -> Result<Vec<UInt8<BasePrimeField<P>>>, SynthesisError> {
let g = self.to_affine()?;
let mut bytes = g.x.to_non_unique_bytes_le()?;
let y_bytes = g.y.to_non_unique_bytes_le()?;
let inf_bytes = g.infinity.to_non_unique_bytes_le()?;
bytes.extend_from_slice(&y_bytes);
bytes.extend_from_slice(&inf_bytes);
Ok(bytes)
}
}
#[cfg(test)]
mod test_sw_curve {
use crate::{
alloc::AllocVar,
convert::ToBitsGadget,
eq::EqGadget,
fields::{emulated_fp::EmulatedFpVar, fp::FpVar},
groups::{curves::short_weierstrass::ProjectiveVar, CurveVar},
};
use ark_ec::{
short_weierstrass::{Projective, SWCurveConfig},
CurveGroup,
};
use ark_ff::PrimeField;
use ark_relations::r1cs::{ConstraintSystem, Result};
use ark_std::UniformRand;
use num_traits::Zero;
fn zero_point_scalar_mul_satisfied<G>() -> Result<bool>
where
G: CurveGroup,
G::BaseField: PrimeField,
G::Config: SWCurveConfig,
{
let mut rng = ark_std::test_rng();
let cs = ConstraintSystem::new_ref();
let point_in = Projective::<G::Config>::zero();
let point_out = Projective::<G::Config>::zero();
let scalar = G::ScalarField::rand(&mut rng);
let point_in =
ProjectiveVar::<G::Config, FpVar<G::BaseField>>::new_witness(cs.clone(), || {
Ok(point_in)
})?;
let point_out =
ProjectiveVar::<G::Config, FpVar<G::BaseField>>::new_input(cs.clone(), || {
Ok(point_out)
})?;
let scalar = EmulatedFpVar::new_input(cs.clone(), || Ok(scalar))?;
let mul = point_in.scalar_mul_le(scalar.to_bits_le().unwrap().iter())?;
point_out.enforce_equal(&mul)?;
cs.is_satisfied()
}
#[test]
fn test_zero_point_scalar_mul() {
assert!(zero_point_scalar_mul_satisfied::<ark_bls12_381::G1Projective>().unwrap());
assert!(zero_point_scalar_mul_satisfied::<ark_pallas::Projective>().unwrap());
assert!(zero_point_scalar_mul_satisfied::<ark_mnt4_298::G1Projective>().unwrap());
assert!(zero_point_scalar_mul_satisfied::<ark_mnt6_298::G1Projective>().unwrap());
assert!(zero_point_scalar_mul_satisfied::<ark_bn254::G1Projective>().unwrap());
}
}