macro_rules! curve_impl {
(
$name:expr,
$projective:ident,
$affine:ident,
$prepared:ident,
$basefield:ident,
$scalarfield:ident,
$uncompressed:ident,
$compressed:ident,
$pairing:ident
) => {
#[derive(Copy, Clone, PartialEq, Eq, Debug, Zeroize)]
pub struct $affine {
pub(crate) x: $basefield,
pub(crate) y: $basefield,
pub(crate) infinity: bool,
}
pub const unsafe fn transmute_affine(x: $basefield, y: $basefield, i: bool) -> $affine {
$affine {
x: x,
y: y,
infinity: i,
}
}
impl ::std::default::Default for $affine {
fn default() -> Self {
$affine::zero()
}
}
impl ::std::default::Default for $projective {
fn default() -> Self {
$projective::zero()
}
}
impl ::std::fmt::Display for $affine {
fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
if self.infinity {
write!(f, "{}(Infinity)", $name)
} else {
write!(f, "{}(x={}, y={})", $name, self.x, self.y)
}
}
}
#[derive(Copy, Clone, Debug, Eq, Zeroize)]
pub struct $projective {
pub(crate) x: $basefield,
pub(crate) y: $basefield,
pub(crate) z: $basefield,
}
pub const unsafe fn transmute_projective(
x: $basefield,
y: $basefield,
z: $basefield,
) -> $projective {
$projective { x: x, y: y, z: z }
}
impl ::std::fmt::Display for $projective {
fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
write!(f, "{}", self.into_affine())
}
}
impl PartialEq for $projective {
fn eq(&self, other: &$projective) -> bool {
if self.is_zero() {
return other.is_zero();
}
if other.is_zero() {
return false;
}
let mut z1 = self.z;
z1.square();
let mut z2 = other.z;
z2.square();
let mut tmp1 = self.x;
tmp1.mul_assign(&z2);
let mut tmp2 = other.x;
tmp2.mul_assign(&z1);
if tmp1 != tmp2 {
return false;
}
z1.mul_assign(&self.z);
z2.mul_assign(&other.z);
z2.mul_assign(&self.y);
z1.mul_assign(&other.y);
if z1 != z2 {
return false;
}
true
}
}
impl $affine {
fn mul_bits<S: AsRef<[u64]>>(&self, bits: BitIterator<S>) -> $projective {
let mut res = $projective::zero();
for i in bits {
res.double();
if i {
res.add_assign_mixed(self)
}
}
res
}
fn get_point_from_x(x: $basefield, greatest: bool) -> Option<$affine> {
let mut x3b = x;
x3b.square();
x3b.mul_assign(&x);
x3b.add_assign(&$affine::get_coeff_b());
x3b.sqrt().map(|y| {
let mut negy = y;
negy.negate();
$affine {
x: x,
y: if (y < negy) ^ greatest { y } else { negy },
infinity: false,
}
})
}
fn is_on_curve(&self) -> bool {
if self.is_zero() {
true
} else {
let mut y2 = self.y;
y2.square();
let mut x3b = self.x;
x3b.square();
x3b.mul_assign(&self.x);
x3b.add_assign(&Self::get_coeff_b());
y2 == x3b
}
}
fn is_in_correct_subgroup_assuming_on_curve(&self) -> bool {
self.mul($scalarfield::char()).is_zero()
}
}
impl CurveAffine for $affine {
type Engine = Bls12;
type Scalar = $scalarfield;
type Base = $basefield;
type Prepared = $prepared;
type Projective = $projective;
type Uncompressed = $uncompressed;
type Compressed = $compressed;
type Pair = $pairing;
type PairingResult = Fq12;
fn zero() -> Self {
$affine {
x: $basefield::zero(),
y: $basefield::one(),
infinity: true,
}
}
fn one() -> Self {
Self::get_generator()
}
fn is_zero(&self) -> bool {
self.infinity
}
fn mul<S: Into<<Self::Scalar as PrimeField>::Repr>>(&self, by: S) -> $projective {
let bits = BitIterator::new(by.into());
self.mul_bits(bits)
}
fn negate(&mut self) {
if !self.is_zero() {
self.y.negate();
}
}
fn prepare(&self) -> Self::Prepared {
$prepared::from_affine(*self)
}
fn pairing_with(&self, other: &Self::Pair) -> Self::PairingResult {
self.perform_pairing(other)
}
fn into_projective(&self) -> $projective {
(*self).into()
}
fn as_tuple(&self) -> (&$basefield, &$basefield) {
(&self.x, &self.y)
}
unsafe fn as_tuple_mut(&mut self) -> (&mut $basefield, &mut $basefield) {
(&mut self.x, &mut self.y)
}
fn precomp_3(&self, pre: &mut [Self]) {
let mut p = self.into_projective();
for i in 0..3 {
for _ in 0..64 {
p.double();
}
pre[i] = p.into_affine();
}
}
fn mul_precomp_3<S: Into<<Self::Scalar as PrimeField>::Repr>>(
&self,
other: S,
pre: &[Self],
) -> $projective {
let mut precomp = Vec::with_capacity(16);
precomp.push(Self::Projective::zero());
precomp.push(self.into_projective());
precomp.push(pre[0].into_projective());
precomp.push(precomp[2]);
precomp[3].add_assign_mixed(self);
precomp.push(pre[1].into_projective());
precomp.push(precomp[4]);
precomp[5].add_assign_mixed(self);
precomp.push(precomp[2]);
precomp[6].add_assign_mixed(&pre[1]);
precomp.push(precomp[6]);
precomp[7].add_assign_mixed(self);
precomp.push(pre[2].into_projective());
for i in 9..16 {
precomp.push(precomp[i - 8]);
precomp[i].add_assign_mixed(&pre[2]);
}
let repr = other.into();
let bits: &[u64; 4] = &repr.0;
let mut nibble = (bits[3] >> 60) & 8;
nibble |= (bits[2] >> 61) & 4;
nibble |= (bits[1] >> 62) & 2;
nibble |= (bits[0] >> 63) & 1;
let mut res = precomp[nibble as usize];
for i in (0..63).rev() {
res.double();
nibble = ((bits[3] >> i) << 3) & 8;
nibble |= ((bits[2] >> i) << 2) & 4;
nibble |= ((bits[1] >> i) << 1) & 2;
nibble |= (bits[0] >> i) & 1;
res.add_assign(&precomp[nibble as usize]);
}
res
}
fn precomp_256(&self, pre: &mut [Self]) {
pre[0] = Self::zero();
let mut piece_length = 1;
let mut power_of_2_times_self = self.into_projective();
while piece_length <= 128 {
pre[piece_length] = power_of_2_times_self.into_affine();
for i in 1..piece_length {
pre[i + piece_length] = pre[i];
let mut temp = pre[i].into_projective();
temp.add_assign_mixed(&pre[piece_length]);
pre[i + piece_length] = temp.into_affine();
}
if piece_length < 128 {
for _ in 0..32 {
power_of_2_times_self.double();
}
}
piece_length *= 2;
}
}
fn mul_precomp_256<S: Into<<Self::Scalar as PrimeField>::Repr>>(
&self,
other: S,
pre: &[Self],
) -> $projective {
let repr = other.into();
let bits: &[u64; 4] = &repr.0;
let mut byte = (bits[3] >> 56) & 128;
byte |= (bits[3] >> 25) & 64;
byte |= (bits[2] >> 58) & 32;
byte |= (bits[2] >> 27) & 16;
byte |= (bits[1] >> 60) & 8;
byte |= (bits[1] >> 29) & 4;
byte |= (bits[0] >> 62) & 2;
byte |= (bits[0] >> 31) & 1;
let mut res = pre[byte as usize].into_projective();
for i in (0..31).rev() {
res.double();
byte = (bits[3] >> (i + 25)) & 128;
byte |= ((bits[3] >> i) << 6) & 64;
byte |= (bits[2] >> (i + 27)) & 32;
byte |= ((bits[2] >> i) << 4) & 16;
byte |= (bits[1] >> (i + 29)) & 8;
byte |= ((bits[1] >> i) << 2) & 4;
byte |= (bits[0] >> (i + 31)) & 2;
byte |= (bits[0] >> i) & 1;
res.add_assign_mixed(&pre[byte as usize]);
}
res
}
fn sum_of_products(points: &[Self], scalars: &[&[u64; 4]]) -> $projective {
let num_components = if points.len() < scalars.len() {
points.len()
} else {
scalars.len()
};
Self::sum_of_products_pippinger(
points,
scalars,
Self::find_pippinger_window(num_components),
)
}
fn find_pippinger_window(num_components: usize) -> usize {
let boundaries = [
(1, 1),
(2, 2),
(20, 3),
(43, 4),
(105, 5),
(239, 6),
(578, 7),
(1258, 8),
(3464, 9),
(6492, 10),
(17146, 11),
(33676, 12),
(60319, 13),
(218189, 14),
(303280, 15),
(543651, 16),
];
for i in 1..boundaries.len() {
if boundaries[i].0 > num_components {
return boundaries[i - 1].1;
}
}
boundaries[boundaries.len() - 1].1
}
fn find_pippinger_window_via_estimate(num_components: usize) -> usize {
let n_components = num_components as f64;
let affine_time = 768.0;
let projective_time = 1043.0;
let mut w = 1;
let mut two_to_w = 2.0;
let mut affine_adds = 127.0 * n_components;
let mut projective_adds = 256.0;
let mut old_total_cost =
affine_adds * affine_time + projective_adds * projective_time;
while w < 63 {
w += 1;
two_to_w *= 2.0;
let loop_iterations = (255 / w + 1) as f64;
affine_adds =
(loop_iterations - 2.0) * n_components * (two_to_w - 1.0) / two_to_w;
let prob_empty_bucket = (1.0 - 1.0 / two_to_w).powf(n_components);
let expected_nonempty_nonzero_buckets =
(two_to_w - 1.0) * (1.0 - prob_empty_bucket);
affine_adds -= expected_nonempty_nonzero_buckets * (loop_iterations - 2.0);
let mut _a0 = expected_nonempty_nonzero_buckets * (loop_iterations - 2.0);
let first_iteration_max_bucket = two_to_w / 2.0;
affine_adds += n_components * (first_iteration_max_bucket - 1.0)
/ first_iteration_max_bucket;
let prob_empty_bucket_first_iteration =
(1.0 - 1.0 / first_iteration_max_bucket).powf(n_components);
let expected_nonempty_nonzero_buckets_first_iteration =
(first_iteration_max_bucket - 1.0)
* (1.0 - prob_empty_bucket_first_iteration);
affine_adds -= expected_nonempty_nonzero_buckets_first_iteration;
_a0 += expected_nonempty_nonzero_buckets_first_iteration;
let last_iteration_bit_width = 256 - (255 / w) * w;
let last_iteration_max_bucket = (1u64 << last_iteration_bit_width) as f64;
affine_adds += n_components * (last_iteration_max_bucket - 1.0)
/ last_iteration_max_bucket;
let prob_empty_bucket_last_iteration =
(1.0 - 1.0 / last_iteration_max_bucket).powf(n_components);
let expected_nonempty_nonzero_buckets_last_iteration =
(last_iteration_max_bucket - 1.0)
* (1.0 - prob_empty_bucket_last_iteration);
affine_adds -= expected_nonempty_nonzero_buckets_last_iteration;
_a0 += expected_nonempty_nonzero_buckets_last_iteration;
projective_adds = (loop_iterations - 2.0)
* (expected_nonempty_nonzero_buckets + two_to_w - 2.0)
+ first_iteration_max_bucket
- 2.0
+ expected_nonempty_nonzero_buckets_first_iteration
+ last_iteration_max_bucket
- 2.0
+ expected_nonempty_nonzero_buckets_last_iteration;
let _p0 = (loop_iterations - 2.0)
* (two_to_w - 1.0 - expected_nonempty_nonzero_buckets)
+ first_iteration_max_bucket
- expected_nonempty_nonzero_buckets_first_iteration
+ last_iteration_max_bucket
- expected_nonempty_nonzero_buckets_last_iteration
- 2.0;
let new_total_cost =
affine_adds * affine_time + projective_adds * projective_time;
if new_total_cost > old_total_cost {
w -= 1;
break;
}
old_total_cost = new_total_cost;
}
w
}
fn sum_of_products_pippinger(
points: &[Self],
scalars: &[&[u64; 4]],
window: usize,
) -> $projective {
let mut res = Self::Projective::zero();
let num_components = if points.len() < scalars.len() {
points.len()
} else {
scalars.len()
};
let num_buckets = 1 << window;
let edge = window - 1;
let mask = (num_buckets - 1) as u64;
let mut buckets = vec![Self::Projective::zero(); num_buckets];
let mut bit_sequence_index = 255;
let mut num_doubles = 0;
loop {
for _ in 0..num_doubles {
res.double();
}
let mut max_bucket = 0;
let word_index = bit_sequence_index >> 6;
let bit_index = bit_sequence_index & 63;
if bit_index < edge {
if word_index == 0 {
let smaller_mask = ((1 << (bit_index + 1)) - 1) as u64;
for i in 0..num_components {
let bucket_index: usize =
(scalars[i][word_index] & smaller_mask) as usize;
if bucket_index > 0 {
buckets[bucket_index].add_assign_mixed(&points[i]);
if bucket_index > max_bucket {
max_bucket = bucket_index;
}
}
}
} else {
let high_order_mask = ((1 << (bit_index + 1)) - 1) as u64;
let high_order_shift = edge - bit_index;
let low_order_mask = ((1 << high_order_shift) - 1) as u64;
let low_order_shift = 64 - high_order_shift;
let prev_word_index = word_index - 1;
for i in 0..num_components {
let mut bucket_index = ((scalars[i][word_index] & high_order_mask)
<< high_order_shift)
as usize;
bucket_index |= ((scalars[i][prev_word_index] >> low_order_shift)
& low_order_mask)
as usize;
if bucket_index > 0 {
buckets[bucket_index].add_assign_mixed(&points[i]);
if bucket_index > max_bucket {
max_bucket = bucket_index;
}
}
}
}
} else {
let shift = bit_index - edge;
for i in 0..num_components {
let bucket_index: usize =
((scalars[i][word_index] >> shift) & mask) as usize;
assert!(bit_sequence_index != 255 || scalars[i][3] >> 63 == 0);
if bucket_index > 0 {
buckets[bucket_index].add_assign_mixed(&points[i]);
if bucket_index > max_bucket {
max_bucket = bucket_index;
}
}
}
}
res.add_assign(&buckets[max_bucket]);
for i in (1..max_bucket).rev() {
let temp = buckets[i + 1];
buckets[i].add_assign(&temp);
res.add_assign(&buckets[i]);
buckets[i + 1] = Self::Projective::zero();
}
buckets[1] = Self::Projective::zero();
if bit_sequence_index < window {
break;
}
bit_sequence_index -= window;
num_doubles = {
if bit_sequence_index < edge {
bit_sequence_index + 1
} else {
window
}
};
}
res
}
fn sum_of_products_precomp_256(
points: &[Self],
scalars: &[&[u64; 4]],
pre: &[Self],
) -> $projective {
let mut res = Self::Projective::zero();
let num_components = if points.len() < scalars.len() {
points.len()
} else {
scalars.len()
};
for i in (0..32).rev() {
res.double();
for j in 0..num_components {
let mut byte = (scalars[j][3] >> (i + 25)) & 128;
byte |= ((scalars[j][3] >> i) << 6) & 64;
byte |= (scalars[j][2] >> (i + 27)) & 32;
byte |= ((scalars[j][2] >> i) << 4) & 16;
byte |= (scalars[j][1] >> (i + 29)) & 8;
byte |= ((scalars[j][1] >> i) << 2) & 4;
byte |= (scalars[j][0] >> (i + 31)) & 2;
byte |= (scalars[j][0] >> i) & 1;
res.add_assign_mixed(&pre[(j << 8) + byte as usize]);
}
}
res
}
}
impl CurveProjective for $projective {
type Engine = Bls12;
type Scalar = $scalarfield;
type Base = $basefield;
type Affine = $affine;
fn random<R: rand_core::RngCore>(rng: &mut R) -> Self {
loop {
let x = $basefield::random(rng);
let greatest = rng.next_u32() % 2 != 0;
if let Some(p) = $affine::get_point_from_x(x, greatest) {
let p = p.scale_by_cofactor();
if !p.is_zero() {
return p;
}
}
}
}
fn zero() -> Self {
$projective {
x: $basefield::zero(),
y: $basefield::one(),
z: $basefield::zero(),
}
}
fn one() -> Self {
$affine::one().into()
}
fn is_zero(&self) -> bool {
self.z.is_zero()
}
fn is_normalized(&self) -> bool {
self.is_zero() || self.z == $basefield::one()
}
fn batch_normalization(v: &mut [Self]) {
let mut prod = Vec::with_capacity(v.len());
let mut tmp = $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($basefield::one())),
)
{
let mut newtmp = tmp;
newtmp.mul_assign(&g.z);
g.z = tmp;
g.z.mul_assign(&s);
tmp = newtmp;
}
for g in v.iter_mut().filter(|g| !g.is_normalized()) {
let mut z = g.z;
z.square();
g.x.mul_assign(&z);
z.mul_assign(&g.z);
g.y.mul_assign(&z);
g.z = $basefield::one();
}
}
fn double(&mut self) {
if self.is_zero() {
return;
}
let mut a = self.x;
a.square();
let mut b = self.y;
b.square();
let mut c = b;
c.square();
let mut d = self.x;
d.add_assign(&b);
d.square();
d.sub_assign(&a);
d.sub_assign(&c);
d.double();
let mut e = a;
e.double();
e.add_assign(&a);
let mut f = e;
f.square();
self.z.mul_assign(&self.y);
self.z.double();
self.x = f;
self.x.sub_assign(&d);
self.x.sub_assign(&d);
self.y = d;
self.y.sub_assign(&self.x);
self.y.mul_assign(&e);
c.double();
c.double();
c.double();
self.y.sub_assign(&c);
}
fn add_assign(&mut self, other: &Self) {
if self.is_zero() {
*self = *other;
return;
}
if other.is_zero() {
return;
}
let mut z1z1 = self.z;
z1z1.square();
let mut z2z2 = other.z;
z2z2.square();
let mut u1 = self.x;
u1.mul_assign(&z2z2);
let mut u2 = other.x;
u2.mul_assign(&z1z1);
let mut s1 = self.y;
s1.mul_assign(&other.z);
s1.mul_assign(&z2z2);
let mut s2 = other.y;
s2.mul_assign(&self.z);
s2.mul_assign(&z1z1);
if u1 == u2 && s1 == s2 {
self.double();
} else {
let mut h = u2;
h.sub_assign(&u1);
let mut i = h;
i.double();
i.square();
let mut j = h;
j.mul_assign(&i);
let mut r = s2;
r.sub_assign(&s1);
r.double();
let mut v = u1;
v.mul_assign(&i);
self.x = r;
self.x.square();
self.x.sub_assign(&j);
self.x.sub_assign(&v);
self.x.sub_assign(&v);
self.y = v;
self.y.sub_assign(&self.x);
self.y.mul_assign(&r);
s1.mul_assign(&j);
s1.double();
self.y.sub_assign(&s1);
self.z.add_assign(&other.z);
self.z.square();
self.z.sub_assign(&z1z1);
self.z.sub_assign(&z2z2);
self.z.mul_assign(&h);
}
}
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 = $basefield::one();
return;
}
let mut z1z1 = self.z;
z1z1.square();
let mut u2 = other.x;
u2.mul_assign(&z1z1);
let mut s2 = other.y;
s2.mul_assign(&self.z);
s2.mul_assign(&z1z1);
if self.x == u2 && self.y == s2 {
self.double();
} else {
let mut h = u2;
h.sub_assign(&self.x);
let mut hh = h;
hh.square();
let mut i = hh;
i.double();
i.double();
let mut j = h;
j.mul_assign(&i);
let mut r = s2;
r.sub_assign(&self.y);
r.double();
let mut v = self.x;
v.mul_assign(&i);
self.x = r;
self.x.square();
self.x.sub_assign(&j);
self.x.sub_assign(&v);
self.x.sub_assign(&v);
j.mul_assign(&self.y);
j.double();
self.y = v;
self.y.sub_assign(&self.x);
self.y.mul_assign(&r);
self.y.sub_assign(&j);
self.z.add_assign(&h);
self.z.square();
self.z.sub_assign(&z1z1);
self.z.sub_assign(&hh);
}
}
fn negate(&mut self) {
if !self.is_zero() {
self.y.negate()
}
}
fn mul_assign<S: Into<<Self::Scalar as PrimeField>::Repr>>(&mut self, other: S) {
let mut res = Self::zero();
let mut found_one = false;
for i in BitIterator::new(other.into()) {
if found_one {
res.double();
} else {
found_one = i;
}
if i {
res.add_assign(self);
}
}
*self = res;
}
fn into_affine(&self) -> $affine {
(*self).into()
}
fn recommended_wnaf_for_scalar(scalar: <Self::Scalar as PrimeField>::Repr) -> usize {
Self::empirical_recommended_wnaf_for_scalar(scalar)
}
fn recommended_wnaf_for_num_scalars(num_scalars: usize) -> usize {
Self::empirical_recommended_wnaf_for_num_scalars(num_scalars)
}
fn as_tuple(&self) -> (&$basefield, &$basefield, &$basefield) {
(&self.x, &self.y, &self.z)
}
unsafe fn as_tuple_mut(
&mut self,
) -> (&mut $basefield, &mut $basefield, &mut $basefield) {
(&mut self.x, &mut self.y, &mut self.z)
}
}
impl From<$affine> for $projective {
fn from(p: $affine) -> $projective {
if p.is_zero() {
$projective::zero()
} else {
$projective {
x: p.x,
y: p.y,
z: $basefield::one(),
}
}
}
}
impl From<$projective> for $affine {
fn from(p: $projective) -> $affine {
if p.is_zero() {
$affine::zero()
} else if p.z == $basefield::one() {
$affine {
x: p.x,
y: p.y,
infinity: false,
}
} else {
let zinv = p.z.inverse().unwrap();
let mut zinv_powered = zinv;
zinv_powered.square();
let mut x = p.x;
x.mul_assign(&zinv_powered);
let mut y = p.y;
zinv_powered.mul_assign(&zinv);
y.mul_assign(&zinv_powered);
$affine {
x: x,
y: y,
infinity: false,
}
}
}
}
};
}
pub mod g1;
pub mod g2;
pub use self::g1::*;
pub use self::g2::*;
#[test]
fn test_group_defaults() {
use CurveAffine;
use CurveProjective;
assert_eq!(G1::default(), G1::zero());
assert_eq!(G2::default(), G2::zero());
assert_eq!(G1Affine::default(), G1Affine::zero());
assert_eq!(G2Affine::default(), G2Affine::zero());
}