use crate::{
models::{MontgomeryModelParameters as MontgomeryParameters, TEModelParameters as Parameters},
AffineCurve, ProjectiveCurve,
};
use ark_serialize::{
CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize,
CanonicalSerializeWithFlags, EdwardsFlags, SerializationError,
};
use ark_std::rand::{
distributions::{Distribution, Standard},
Rng,
};
use ark_std::{
fmt::{Display, Formatter, Result as FmtResult},
io::{Read, Result as IoResult, Write},
marker::PhantomData,
ops::{Add, AddAssign, MulAssign, Neg, Sub, SubAssign},
vec::Vec,
};
use num_traits::{One, Zero};
use zeroize::Zeroize;
use ark_ff::{
bytes::{FromBytes, ToBytes},
fields::{BitIteratorBE, Field, PrimeField, SquareRootField},
ToConstraintField, UniformRand,
};
#[cfg(feature = "parallel")]
use rayon::prelude::*;
#[derive(Derivative)]
#[derivative(
Copy(bound = "P: Parameters"),
Clone(bound = "P: Parameters"),
PartialEq(bound = "P: Parameters"),
Eq(bound = "P: Parameters"),
Debug(bound = "P: Parameters"),
Hash(bound = "P: Parameters")
)]
#[must_use]
pub struct GroupAffine<P: Parameters> {
pub x: P::BaseField,
pub y: P::BaseField,
#[derivative(Debug = "ignore")]
_params: PhantomData<P>,
}
impl<P: Parameters> Display for GroupAffine<P> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
write!(f, "GroupAffine(x={}, y={})", self.x, self.y)
}
}
impl<P: Parameters> GroupAffine<P> {
pub fn new(x: P::BaseField, y: P::BaseField) -> Self {
Self {
x,
y,
_params: PhantomData,
}
}
#[must_use]
pub fn scale_by_cofactor(&self) -> <Self as AffineCurve>::Projective {
self.mul_bits(BitIteratorBE::new(P::COFACTOR))
}
pub(crate) fn mul_bits(&self, bits: impl Iterator<Item = bool>) -> GroupProjective<P> {
let mut res = GroupProjective::zero();
for i in bits.skip_while(|b| !b) {
res.double_in_place();
if i {
res.add_assign_mixed(&self)
}
}
res
}
#[allow(dead_code)]
pub fn get_point_from_x(x: P::BaseField, greatest: bool) -> Option<Self> {
let x2 = x.square();
let one = P::BaseField::one();
let numerator = P::mul_by_a(&x2) - &one;
let denominator = P::COEFF_D * &x2 - &one;
let y2 = denominator.inverse().map(|denom| denom * &numerator);
y2.and_then(|y2| y2.sqrt()).map(|y| {
let negy = -y;
let y = if (y < negy) ^ greatest { y } else { negy };
Self::new(x, y)
})
}
pub fn is_on_curve(&self) -> bool {
let x2 = self.x.square();
let y2 = self.y.square();
let lhs = y2 + &P::mul_by_a(&x2);
let rhs = P::BaseField::one() + &(P::COEFF_D * &(x2 * &y2));
lhs == rhs
}
pub fn is_in_correct_subgroup_assuming_on_curve(&self) -> bool {
self.mul_bits(BitIteratorBE::new(P::ScalarField::characteristic()))
.is_zero()
}
}
impl<P: Parameters> Zero for GroupAffine<P> {
fn zero() -> Self {
Self::new(P::BaseField::zero(), P::BaseField::one())
}
fn is_zero(&self) -> bool {
self.x.is_zero() & self.y.is_one()
}
}
impl<P: Parameters> AffineCurve for GroupAffine<P> {
const COFACTOR: &'static [u64] = P::COFACTOR;
type BaseField = P::BaseField;
type ScalarField = P::ScalarField;
type Projective = GroupProjective<P>;
fn prime_subgroup_generator() -> Self {
Self::new(P::AFFINE_GENERATOR_COEFFS.0, P::AFFINE_GENERATOR_COEFFS.1)
}
fn mul<S: Into<<Self::ScalarField as PrimeField>::BigInt>>(&self, by: S) -> GroupProjective<P> {
self.mul_bits(BitIteratorBE::new(by.into()))
}
fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
P::BaseField::from_random_bytes_with_flags::<EdwardsFlags>(bytes).and_then(|(x, flags)| {
if x.is_zero() {
Some(Self::zero())
} else {
Self::get_point_from_x(x, flags.is_positive())
}
})
}
#[inline]
fn mul_by_cofactor_to_projective(&self) -> Self::Projective {
self.scale_by_cofactor()
}
fn mul_by_cofactor_inv(&self) -> Self {
self.mul(P::COFACTOR_INV).into()
}
}
impl<P: Parameters> Zeroize for GroupAffine<P> {
fn zeroize(&mut self) {
self.x.zeroize();
self.y.zeroize();
}
}
impl<P: Parameters> Neg for GroupAffine<P> {
type Output = Self;
fn neg(self) -> Self {
Self::new(-self.x, self.y)
}
}
ark_ff::impl_additive_ops_from_ref!(GroupAffine, Parameters);
impl<'a, P: Parameters> Add<&'a Self> for GroupAffine<P> {
type Output = Self;
fn add(self, other: &'a Self) -> Self {
let mut copy = self;
copy += other;
copy
}
}
impl<'a, P: Parameters> AddAssign<&'a Self> for GroupAffine<P> {
fn add_assign(&mut self, other: &'a Self) {
let y1y2 = self.y * &other.y;
let x1x2 = self.x * &other.x;
let dx1x2y1y2 = P::COEFF_D * &y1y2 * &x1x2;
let d1 = P::BaseField::one() + &dx1x2y1y2;
let d2 = P::BaseField::one() - &dx1x2y1y2;
let x1y2 = self.x * &other.y;
let y1x2 = self.y * &other.x;
self.x = (x1y2 + &y1x2) / &d1;
self.y = (y1y2 - &P::mul_by_a(&x1x2)) / &d2;
}
}
impl<'a, P: Parameters> Sub<&'a Self> for GroupAffine<P> {
type Output = Self;
fn sub(self, other: &'a Self) -> Self {
let mut copy = self;
copy -= other;
copy
}
}
impl<'a, P: Parameters> SubAssign<&'a Self> for GroupAffine<P> {
fn sub_assign(&mut self, other: &'a Self) {
*self += &(-(*other));
}
}
impl<P: Parameters> MulAssign<P::ScalarField> for GroupAffine<P> {
fn mul_assign(&mut self, other: P::ScalarField) {
*self = self.mul(other.into_repr()).into()
}
}
impl<P: Parameters> ToBytes for GroupAffine<P> {
#[inline]
fn write<W: Write>(&self, mut writer: W) -> IoResult<()> {
self.x.write(&mut writer)?;
self.y.write(&mut writer)
}
}
impl<P: Parameters> FromBytes for GroupAffine<P> {
#[inline]
fn read<R: Read>(mut reader: R) -> IoResult<Self> {
let x = P::BaseField::read(&mut reader)?;
let y = P::BaseField::read(&mut reader)?;
Ok(Self::new(x, y))
}
}
impl<P: Parameters> Default for GroupAffine<P> {
#[inline]
fn default() -> Self {
Self::zero()
}
}
impl<P: Parameters> Distribution<GroupAffine<P>> for Standard {
#[inline]
fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> GroupAffine<P> {
loop {
let x = P::BaseField::rand(rng);
let greatest = rng.gen();
if let Some(p) = GroupAffine::get_point_from_x(x, greatest) {
return p.scale_by_cofactor().into();
}
}
}
}
mod group_impl {
use super::*;
use crate::group::Group;
impl<P: Parameters> Group for GroupAffine<P> {
type ScalarField = P::ScalarField;
#[inline]
fn double(&self) -> Self {
let mut tmp = *self;
tmp += self;
tmp
}
#[inline]
fn double_in_place(&mut self) -> &mut Self {
let mut tmp = *self;
tmp += &*self;
*self = tmp;
self
}
}
}
#[derive(Derivative)]
#[derivative(
Copy(bound = "P: Parameters"),
Clone(bound = "P: Parameters"),
Eq(bound = "P: Parameters"),
Debug(bound = "P: Parameters"),
Hash(bound = "P: Parameters")
)]
#[must_use]
pub struct GroupProjective<P: Parameters> {
pub x: P::BaseField,
pub y: P::BaseField,
pub t: P::BaseField,
pub z: P::BaseField,
#[derivative(Debug = "ignore")]
_params: PhantomData<P>,
}
impl<P: Parameters> PartialEq<GroupProjective<P>> for GroupAffine<P> {
fn eq(&self, other: &GroupProjective<P>) -> bool {
self.into_projective() == *other
}
}
impl<P: Parameters> PartialEq<GroupAffine<P>> for GroupProjective<P> {
fn eq(&self, other: &GroupAffine<P>) -> bool {
*self == other.into_projective()
}
}
impl<P: Parameters> Display for GroupProjective<P> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
write!(f, "{}", GroupAffine::from(*self))
}
}
impl<P: Parameters> PartialEq for GroupProjective<P> {
fn eq(&self, other: &Self) -> bool {
if self.is_zero() {
return other.is_zero();
}
if other.is_zero() {
return false;
}
(self.x * &other.z) == (other.x * &self.z) && (self.y * &other.z) == (other.y * &self.z)
}
}
impl<P: Parameters> Distribution<GroupProjective<P>> for Standard {
#[inline]
fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> GroupProjective<P> {
loop {
let x = P::BaseField::rand(rng);
let greatest = rng.gen();
if let Some(p) = GroupAffine::get_point_from_x(x, greatest) {
return p.scale_by_cofactor();
}
}
}
}
impl<P: Parameters> ToBytes for GroupProjective<P> {
#[inline]
fn write<W: Write>(&self, mut writer: W) -> IoResult<()> {
self.x.write(&mut writer)?;
self.y.write(&mut writer)?;
self.t.write(&mut writer)?;
self.z.write(writer)
}
}
impl<P: Parameters> FromBytes for GroupProjective<P> {
#[inline]
fn read<R: Read>(mut reader: R) -> IoResult<Self> {
let x = P::BaseField::read(&mut reader)?;
let y = P::BaseField::read(&mut reader)?;
let t = P::BaseField::read(&mut reader)?;
let z = P::BaseField::read(reader)?;
Ok(Self::new(x, y, t, z))
}
}
impl<P: Parameters> Default for GroupProjective<P> {
#[inline]
fn default() -> Self {
Self::zero()
}
}
impl<P: Parameters> GroupProjective<P> {
pub fn new(x: P::BaseField, y: P::BaseField, t: P::BaseField, z: P::BaseField) -> Self {
Self {
x,
y,
t,
z,
_params: PhantomData,
}
}
}
impl<P: Parameters> Zeroize for GroupProjective<P> {
fn zeroize(&mut self) {
self.x.zeroize();
self.y.zeroize();
self.t.zeroize();
self.z.zeroize();
}
}
impl<P: Parameters> Zero for GroupProjective<P> {
fn zero() -> Self {
Self::new(
P::BaseField::zero(),
P::BaseField::one(),
P::BaseField::zero(),
P::BaseField::one(),
)
}
fn is_zero(&self) -> bool {
self.x.is_zero() && self.y == self.z && !self.y.is_zero() && self.t.is_zero()
}
}
impl<P: Parameters> ProjectiveCurve for GroupProjective<P> {
const COFACTOR: &'static [u64] = P::COFACTOR;
type BaseField = P::BaseField;
type ScalarField = P::ScalarField;
type Affine = GroupAffine<P>;
fn prime_subgroup_generator() -> Self {
GroupAffine::prime_subgroup_generator().into()
}
fn is_normalized(&self) -> bool {
self.z.is_one()
}
fn batch_normalization(v: &mut [Self]) {
let mut z_s = v.iter().map(|g| g.z).collect::<Vec<_>>();
ark_ff::batch_inversion(&mut z_s);
ark_std::cfg_iter_mut!(v)
.zip(z_s)
.filter(|(g, _)| !g.is_normalized())
.for_each(|(g, z)| {
g.x *= &z;
g.y *= &z;
g.t *= &z;
g.z = P::BaseField::one();
});
}
fn double_in_place(&mut self) -> &mut Self {
let a = self.x.square();
let b = self.y.square();
let c = self.z.square().double();
let d = P::mul_by_a(&a);
let e = (self.x + &self.y).square() - &a - &b;
let g = d + &b;
let f = g - &c;
let h = d - &b;
self.x = e * &f;
self.y = g * &h;
self.t = e * &h;
self.z = f * &g;
self
}
fn add_assign_mixed(&mut self, other: &GroupAffine<P>) {
let a = self.x * &other.x;
let b = self.y * &other.y;
let c = P::COEFF_D * &self.t * &other.x * &other.y;
let d = self.z;
let e = (self.x + &self.y) * &(other.x + &other.y) - &a - &b;
let f = d - &c;
let g = d + &c;
let h = b - &P::mul_by_a(&a);
self.x = e * &f;
self.y = g * &h;
self.t = e * &h;
self.z = f * &g;
}
}
impl<P: Parameters> Neg for GroupProjective<P> {
type Output = Self;
fn neg(mut self) -> Self {
self.x = -self.x;
self.t = -self.t;
self
}
}
ark_ff::impl_additive_ops_from_ref!(GroupProjective, Parameters);
impl<'a, P: Parameters> Add<&'a Self> for GroupProjective<P> {
type Output = Self;
fn add(mut self, other: &'a Self) -> Self {
self += other;
self
}
}
impl<'a, P: Parameters> AddAssign<&'a Self> for GroupProjective<P> {
fn add_assign(&mut self, other: &'a Self) {
let a = self.x * &other.x;
let b = self.y * &other.y;
let c = P::COEFF_D * &self.t * &other.t;
let d = self.z * &other.z;
let h = b - &P::mul_by_a(&a);
let e = (self.x + &self.y) * &(other.x + &other.y) - &a - &b;
let f = d - &c;
let g = d + &c;
self.x = e * &f;
self.y = g * &h;
self.t = e * &h;
self.z = f * &g;
}
}
impl<'a, P: Parameters> Sub<&'a Self> for GroupProjective<P> {
type Output = Self;
fn sub(mut self, other: &'a Self) -> Self {
self -= other;
self
}
}
impl<'a, P: Parameters> SubAssign<&'a Self> for GroupProjective<P> {
fn sub_assign(&mut self, other: &'a Self) {
*self += &(-(*other));
}
}
impl<P: Parameters> MulAssign<P::ScalarField> for GroupProjective<P> {
fn mul_assign(&mut self, other: P::ScalarField) {
*self = self.mul(other.into_repr())
}
}
impl<P: Parameters> From<GroupAffine<P>> for GroupProjective<P> {
fn from(p: GroupAffine<P>) -> GroupProjective<P> {
Self::new(p.x, p.y, p.x * &p.y, P::BaseField::one())
}
}
impl<P: Parameters> From<GroupProjective<P>> for GroupAffine<P> {
fn from(p: GroupProjective<P>) -> GroupAffine<P> {
if p.is_zero() {
GroupAffine::zero()
} else if p.z.is_one() {
GroupAffine::new(p.x, p.y)
} else {
let z_inv = p.z.inverse().unwrap();
let x = p.x * &z_inv;
let y = p.y * &z_inv;
GroupAffine::new(x, y)
}
}
}
impl<P: Parameters> core::str::FromStr for GroupAffine<P>
where
P::BaseField: core::str::FromStr<Err = ()>,
{
type Err = ();
fn from_str(mut s: &str) -> Result<Self, Self::Err> {
s = s.trim();
if s.is_empty() {
return Err(());
}
if s.len() < 3 {
return Err(());
}
if !(s.starts_with('(') && s.ends_with(')')) {
return Err(());
}
let mut point = Vec::new();
for substr in s.split(|c| c == '(' || c == ')' || c == ',' || c == ' ') {
if !substr.is_empty() {
point.push(P::BaseField::from_str(substr)?);
}
}
if point.len() != 2 {
return Err(());
}
let point = Self::new(point[0], point[1]);
if !point.is_on_curve() {
Err(())
} else {
Ok(point)
}
}
}
#[derive(Derivative)]
#[derivative(
Copy(bound = "P: MontgomeryParameters"),
Clone(bound = "P: MontgomeryParameters"),
PartialEq(bound = "P: MontgomeryParameters"),
Eq(bound = "P: MontgomeryParameters"),
Debug(bound = "P: MontgomeryParameters"),
Hash(bound = "P: MontgomeryParameters")
)]
pub struct MontgomeryGroupAffine<P: MontgomeryParameters> {
pub x: P::BaseField,
pub y: P::BaseField,
#[derivative(Debug = "ignore")]
_params: PhantomData<P>,
}
impl<P: MontgomeryParameters> Display for MontgomeryGroupAffine<P> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
write!(f, "MontgomeryGroupAffine(x={}, y={})", self.x, self.y)
}
}
impl<P: MontgomeryParameters> MontgomeryGroupAffine<P> {
pub fn new(x: P::BaseField, y: P::BaseField) -> Self {
Self {
x,
y,
_params: PhantomData,
}
}
}
impl<P: Parameters> CanonicalSerialize for GroupAffine<P> {
#[allow(unused_qualifications)]
#[inline]
fn serialize<W: Write>(&self, writer: W) -> Result<(), SerializationError> {
if self.is_zero() {
let flags = EdwardsFlags::default();
P::BaseField::zero().serialize_with_flags(writer, flags)
} else {
let flags = EdwardsFlags::from_y_sign(self.y > -self.y);
self.x.serialize_with_flags(writer, flags)
}
}
#[inline]
fn serialized_size(&self) -> usize {
P::BaseField::zero().serialized_size_with_flags::<EdwardsFlags>()
}
#[allow(unused_qualifications)]
#[inline]
fn serialize_uncompressed<W: Write>(&self, mut writer: W) -> Result<(), SerializationError> {
self.x.serialize_uncompressed(&mut writer)?;
self.y.serialize_uncompressed(&mut writer)?;
Ok(())
}
#[inline]
fn uncompressed_size(&self) -> usize {
self.x.serialized_size() + self.y.serialized_size()
}
}
impl<P: Parameters> CanonicalSerialize for GroupProjective<P> {
#[allow(unused_qualifications)]
#[inline]
fn serialize<W: Write>(&self, writer: W) -> Result<(), SerializationError> {
let aff = GroupAffine::<P>::from(self.clone());
aff.serialize(writer)
}
#[inline]
fn serialized_size(&self) -> usize {
let aff = GroupAffine::<P>::from(self.clone());
aff.serialized_size()
}
#[allow(unused_qualifications)]
#[inline]
fn serialize_uncompressed<W: Write>(&self, writer: W) -> Result<(), SerializationError> {
let aff = GroupAffine::<P>::from(self.clone());
aff.serialize_uncompressed(writer)
}
#[inline]
fn uncompressed_size(&self) -> usize {
let aff = GroupAffine::<P>::from(self.clone());
aff.uncompressed_size()
}
}
impl<P: Parameters> CanonicalDeserialize for GroupAffine<P> {
#[allow(unused_qualifications)]
fn deserialize<R: Read>(mut reader: R) -> Result<Self, SerializationError> {
let (x, flags): (P::BaseField, EdwardsFlags) =
CanonicalDeserializeWithFlags::deserialize_with_flags(&mut reader)?;
if x == P::BaseField::zero() {
Ok(Self::zero())
} else {
let p = GroupAffine::<P>::get_point_from_x(x, flags.is_positive())
.ok_or(SerializationError::InvalidData)?;
if !p.is_in_correct_subgroup_assuming_on_curve() {
return Err(SerializationError::InvalidData);
}
Ok(p)
}
}
#[allow(unused_qualifications)]
fn deserialize_uncompressed<R: Read>(reader: R) -> Result<Self, SerializationError> {
let p = Self::deserialize_unchecked(reader)?;
if !p.is_in_correct_subgroup_assuming_on_curve() {
return Err(SerializationError::InvalidData);
}
Ok(p)
}
#[allow(unused_qualifications)]
fn deserialize_unchecked<R: Read>(mut reader: R) -> Result<Self, SerializationError> {
let x: P::BaseField = CanonicalDeserialize::deserialize(&mut reader)?;
let y: P::BaseField = CanonicalDeserialize::deserialize(&mut reader)?;
let p = GroupAffine::<P>::new(x, y);
Ok(p)
}
}
impl<P: Parameters> CanonicalDeserialize for GroupProjective<P> {
#[allow(unused_qualifications)]
fn deserialize<R: Read>(reader: R) -> Result<Self, SerializationError> {
let aff = GroupAffine::<P>::deserialize(reader)?;
Ok(aff.into())
}
#[allow(unused_qualifications)]
fn deserialize_uncompressed<R: Read>(reader: R) -> Result<Self, SerializationError> {
let aff = GroupAffine::<P>::deserialize_uncompressed(reader)?;
Ok(aff.into())
}
#[allow(unused_qualifications)]
fn deserialize_unchecked<R: Read>(reader: R) -> Result<Self, SerializationError> {
let aff = GroupAffine::<P>::deserialize_unchecked(reader)?;
Ok(aff.into())
}
}
impl<M: Parameters, ConstraintF: Field> ToConstraintField<ConstraintF> for GroupAffine<M>
where
M::BaseField: ToConstraintField<ConstraintF>,
{
#[inline]
fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
let mut x_fe = self.x.to_field_elements()?;
let y_fe = self.y.to_field_elements()?;
x_fe.extend_from_slice(&y_fe);
Some(x_fe)
}
}
impl<M: Parameters, ConstraintF: Field> ToConstraintField<ConstraintF> for GroupProjective<M>
where
M::BaseField: ToConstraintField<ConstraintF>,
{
#[inline]
fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
GroupAffine::from(*self).to_field_elements()
}
}