use crate::{
impl_sw_curve_serializer,
impl_sw_from_random_bytes,
traits::{AffineCurve, ProjectiveCurve, SWModelParameters as Parameters},
};
use snarkvm_fields::{Field, One, PrimeField, SquareRootField, Zero};
use snarkvm_utilities::{
bititerator::BitIteratorBE,
bytes::{FromBytes, ToBytes},
rand::UniformRand,
serialize::*,
};
use rand::{
distributions::{Distribution, Standard},
Rng,
};
use serde::{Deserialize, Serialize};
use std::{
fmt::{Display, Formatter, Result as FmtResult},
io::{Error, ErrorKind, Read, Result as IoResult, Write},
marker::PhantomData,
ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
};
#[derive(Derivative, Serialize, Deserialize)]
#[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")
)]
pub struct GroupAffine<P: Parameters> {
pub x: P::BaseField,
pub y: P::BaseField,
pub infinity: bool,
#[derivative(Debug = "ignore")]
_params: PhantomData<P>,
}
impl<P: Parameters> Display for GroupAffine<P> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
if self.infinity {
write!(f, "GroupAffine(Infinity)")
} else {
write!(f, "GroupAffine(x={}, y={})", self.x, self.y)
}
}
}
impl<P: Parameters> GroupAffine<P> {
pub fn new(x: P::BaseField, y: P::BaseField, infinity: bool) -> Self {
Self {
x,
y,
infinity,
_params: PhantomData,
}
}
pub fn scale_by_cofactor(&self) -> GroupProjective<P> {
self.mul_bits(BitIteratorBE::new(P::COFACTOR))
}
pub(crate) fn mul_bits<S: AsRef<[u64]>>(&self, bits: BitIteratorBE<S>) -> GroupProjective<P> {
let mut res = GroupProjective::zero();
for i in bits {
res.double_in_place();
if i {
res.add_assign_mixed(self)
}
}
res
}
pub fn is_on_curve(&self) -> bool {
if self.is_zero() {
true
} else {
let y2 = self.y.square();
let x3b = P::add_b(&((self.x.square() * &self.x) + &P::mul_by_a(&self.x)));
y2 == x3b
}
}
}
impl<P: Parameters> Zero for GroupAffine<P> {
#[inline]
fn zero() -> Self {
Self::new(P::BaseField::zero(), P::BaseField::one(), true)
}
#[inline]
fn is_zero(&self) -> bool {
self.infinity
}
}
impl<P: Parameters> AffineCurve for GroupAffine<P> {
type BaseField = P::BaseField;
type Projective = GroupProjective<P>;
type ScalarField = P::ScalarField;
impl_sw_from_random_bytes!();
#[inline]
fn prime_subgroup_generator() -> Self {
Self::new(P::AFFINE_GENERATOR_COEFFS.0, P::AFFINE_GENERATOR_COEFFS.1, false)
}
fn from_x_coordinate(x: Self::BaseField, greatest: bool) -> Option<Self> {
let x3b = P::add_b(&((x.square() * &x) + &P::mul_by_a(&x)));
x3b.sqrt().map(|y| {
let negy = -y;
let y = if (y < negy) ^ greatest { y } else { negy };
Self::new(x, y, false)
})
}
fn from_y_coordinate(_y: Self::BaseField, _greatest: bool) -> Option<Self> {
unimplemented!()
}
fn add(self, _other: &Self) -> Self {
unimplemented!()
}
#[inline]
fn mul<S: Into<<Self::ScalarField as PrimeField>::BigInteger>>(&self, by: S) -> GroupProjective<P> {
let bits = BitIteratorBE::new(by.into());
self.mul_bits(bits)
}
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()
}
#[inline]
fn into_projective(&self) -> GroupProjective<P> {
(*self).into()
}
fn is_in_correct_subgroup_assuming_on_curve(&self) -> bool {
self.mul_bits(BitIteratorBE::new(P::ScalarField::characteristic()))
.is_zero()
}
fn to_x_coordinate(&self) -> Self::BaseField {
self.x
}
fn to_y_coordinate(&self) -> Self::BaseField {
self.y
}
fn is_on_curve(&self) -> bool {
if self.is_zero() {
true
} else {
let y2 = self.y.square();
let x3b = P::add_b(&((self.x.square() * &self.x) + &P::mul_by_a(&self.x)));
y2 == x3b
}
}
}
impl<P: Parameters> Neg for GroupAffine<P> {
type Output = Self;
#[inline]
fn neg(self) -> Self {
if !self.is_zero() {
Self::new(self.x, -self.y, false)
} else {
self
}
}
}
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)?;
self.infinity.write(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)?;
let infinity = bool::read(&mut reader)?;
if infinity != x.is_zero() && y.is_one() {
return Err(Error::new(ErrorKind::InvalidData, "Infinity flag is not valid"));
}
Ok(Self::new(x, y, infinity))
}
}
impl<P: Parameters> Default for GroupAffine<P> {
#[inline]
fn default() -> Self {
Self::zero()
}
}
#[derive(Derivative)]
#[derivative(
Copy(bound = "P: Parameters"),
Clone(bound = "P: Parameters"),
Eq(bound = "P: Parameters"),
Debug(bound = "P: Parameters"),
Hash(bound = "P: Parameters")
)]
pub struct GroupProjective<P: Parameters> {
pub x: P::BaseField,
pub y: P::BaseField,
pub z: P::BaseField,
_params: PhantomData<P>,
}
impl<P: Parameters> Display for GroupProjective<P> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
write!(f, "{}", self.into_affine())
}
}
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;
}
let z1 = self.z.square();
let z2 = other.z.square();
!(self.x * &z2 != other.x * &z1 || self.y * &(z2 * &other.z) != other.y * &(z1 * &self.z))
}
}
impl<P: Parameters> Distribution<GroupProjective<P>> for Standard {
#[inline]
fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> GroupProjective<P> {
let res = GroupProjective::prime_subgroup_generator() * &P::ScalarField::rand(rng);
debug_assert!(res.into_affine().is_in_correct_subgroup_assuming_on_curve());
res
}
}
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.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 z = P::BaseField::read(reader)?;
Ok(Self::new(x, y, 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, z: P::BaseField) -> Self {
Self {
x,
y,
z,
_params: PhantomData,
}
}
}
impl<P: Parameters> Zero for GroupProjective<P> {
#[inline]
fn zero() -> Self {
Self::new(P::BaseField::zero(), P::BaseField::one(), P::BaseField::zero())
}
#[inline]
fn is_zero(&self) -> bool {
self.z.is_zero()
}
}
impl<P: Parameters> ProjectiveCurve for GroupProjective<P> {
type Affine = GroupAffine<P>;
type BaseField = P::BaseField;
type ScalarField = P::ScalarField;
#[inline]
fn prime_subgroup_generator() -> Self {
GroupAffine::prime_subgroup_generator().into()
}
#[inline]
fn is_normalized(&self) -> bool {
self.is_zero() || self.z.is_one()
}
#[inline]
fn batch_normalization(v: &mut [Self]) {
let mut prod = Vec::with_capacity(v.len());
let mut tmp = P::BaseField::one();
for g in v
.iter_mut()
.filter(|g| !g.is_normalized())
{
tmp.mul_assign(&g.z);
prod.push(tmp);
}
tmp = tmp.inverse().unwrap();
for (g, s) in v
.iter_mut()
.rev()
.filter(|g| !g.is_normalized())
.zip(
prod.into_iter()
.rev()
.skip(1)
.chain(Some(P::BaseField::one())),
)
{
let newtmp = tmp * &g.z;
g.z = tmp * &s;
tmp = newtmp;
}
#[cfg(not(feature = "parallel"))]
{
for g in v.iter_mut().filter(|g| !g.is_normalized()) {
let z2 = g.z.square();
g.x *= &z2;
g.y *= &(z2 * &g.z);
g.z = P::BaseField::one();
}
}
#[cfg(feature = "parallel")]
{
use rayon::prelude::*;
v.par_iter_mut().filter(|g| !g.is_normalized()).for_each(|g| {
let z2 = g.z.square();
g.x *= &z2;
g.y *= &(z2 * &g.z);
g.z = P::BaseField::one();
});
}
}
#[allow(clippy::many_single_char_names)]
fn double_in_place(&mut self) -> &mut Self {
if self.is_zero() {
return self;
}
if P::COEFF_A.is_zero() {
let mut a = self.x.square();
let b = self.y.square();
let mut c = b.square();
let d = ((self.x + &b).square() - &a - &c).double();
let e = a + a.double_in_place();
let f = e.square();
self.z.mul_assign(&self.y);
self.z.double_in_place();
self.x = f - &d - &d;
self.y = (d - &self.x) * &e - c.double_in_place().double_in_place().double_in_place();
self
} else {
let xx = self.x.square();
let yy = self.y.square();
let mut yyyy = yy.square();
let zz = self.z.square();
let s = ((self.x + &yy).square() - &xx - &yyyy).double();
let m = xx + &xx + &xx + &P::mul_by_a(&zz.square());
let t = m.square() - &s.double();
self.x = t;
let old_y = self.y;
self.y = m * &(s - &t) - yyyy.double_in_place().double_in_place().double_in_place();
self.z = (old_y + &self.z).square() - &yy - &zz;
self
}
}
#[allow(clippy::many_single_char_names)]
fn add_assign_mixed(&mut self, other: &Self::Affine) {
if other.is_zero() {
return;
}
if self.is_zero() {
self.x = other.x;
self.y = other.y;
self.z = P::BaseField::one();
return;
}
let z1z1 = self.z.square();
let u2 = other.x * &z1z1;
let s2 = (other.y * &self.z) * &z1z1;
if self.x == u2 && self.y == s2 {
self.double_in_place();
} else {
let h = u2 - &self.x;
let hh = h.square();
let mut i = hh;
i.double_in_place().double_in_place();
let mut j = h * &i;
let r = (s2 - &self.y).double();
let v = self.x * &i;
self.x = r.square();
self.x -= &j;
self.x -= &v;
self.x -= &v;
j *= &self.y;
j.double_in_place();
self.y = v - &self.x;
self.y *= &r;
self.y -= &j;
self.z += &h;
self.z.square_in_place();
self.z -= &z1z1;
self.z -= &hh;
}
}
fn mul_assign<S: Into<<Self::ScalarField as PrimeField>::BigInteger>>(&mut self, other: S) {
let mut res = Self::zero();
let mut found_one = false;
for i in BitIteratorBE::new(other.into()) {
if found_one {
res.double_in_place();
} else {
found_one = i;
}
if i {
res.add_assign(self);
}
}
*self = res;
}
#[inline]
fn into_affine(&self) -> GroupAffine<P> {
(*self).into()
}
#[inline]
fn recommended_wnaf_for_scalar(scalar: <Self::ScalarField as PrimeField>::BigInteger) -> usize {
P::empirical_recommended_wnaf_for_scalar(scalar)
}
#[inline]
fn recommended_wnaf_for_num_scalars(num_scalars: usize) -> usize {
P::empirical_recommended_wnaf_for_num_scalars(num_scalars)
}
}
impl<P: Parameters> Neg for GroupProjective<P> {
type Output = Self;
#[inline]
fn neg(self) -> Self {
if !self.is_zero() {
Self::new(self.x, -self.y, self.z)
} else {
self
}
}
}
impl<'a, P: Parameters> Add<&'a Self> for GroupProjective<P> {
type Output = Self;
#[inline]
fn add(self, other: &'a Self) -> Self {
let mut copy = self;
copy += other;
copy
}
}
impl<'a, P: Parameters> AddAssign<&'a Self> for GroupProjective<P> {
#[allow(clippy::many_single_char_names)]
#[allow(clippy::suspicious_op_assign_impl)]
fn add_assign(&mut self, other: &'a Self) {
if self.is_zero() {
*self = *other;
return;
}
if other.is_zero() {
return;
}
let z1z1 = self.z.square();
let z2z2 = other.z.square();
let u1 = self.x * &z2z2;
let u2 = other.x * &z1z1;
let s1 = self.y * &other.z * &z2z2;
let s2 = other.y * &self.z * &z1z1;
if u1 == u2 && s1 == s2 {
self.double_in_place();
} else {
let h = u2 - &u1;
let i = (h.double()).square();
let j = h * &i;
let r = (s2 - &s1).double();
let v = u1 * &i;
self.x = r.square() - &j - &(v.double());
self.y = r * &(v - &self.x) - (s1 * &j).double_in_place();
self.z = ((self.z + &other.z).square() - &z1z1 - &z2z2) * &h;
}
}
}
impl<'a, P: Parameters> Sub<&'a Self> for GroupProjective<P> {
type Output = Self;
#[inline]
fn sub(self, other: &'a Self) -> Self {
let mut copy = self;
copy -= other;
copy
}
}
impl<'a, P: Parameters> SubAssign<&'a Self> for GroupProjective<P> {
fn sub_assign(&mut self, other: &'a Self) {
*self += &(-(*other));
}
}
impl<'a, P: Parameters> Mul<&'a P::ScalarField> for GroupProjective<P> {
type Output = Self;
#[inline]
fn mul(self, other: &'a P::ScalarField) -> Self {
let mut copy = self;
copy *= other;
copy
}
}
impl<'a, P: Parameters> MulAssign<&'a P::ScalarField> for GroupProjective<P> {
#[inline]
fn mul_assign(&mut self, other: &'a P::ScalarField) {
<GroupProjective<P> as ProjectiveCurve>::mul_assign(self, *other);
}
}
impl<P: Parameters> From<GroupAffine<P>> for GroupProjective<P> {
#[inline]
fn from(p: GroupAffine<P>) -> GroupProjective<P> {
if p.is_zero() {
Self::zero()
} else {
Self::new(p.x, p.y, P::BaseField::one())
}
}
}
impl<P: Parameters> From<GroupProjective<P>> for GroupAffine<P> {
#[inline]
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, false)
} else {
let zinv = p.z.inverse().unwrap();
let zinv_squared = zinv.square();
let x = p.x * &zinv_squared;
let y = p.y * &(zinv_squared * &zinv);
GroupAffine::new(x, y, false)
}
}
}
impl_sw_curve_serializer!(Parameters);