ark_ec/models/bw6/
g2.rs

1use ark_ff::{AdditiveGroup, BitIteratorBE, Field};
2use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
3use ark_std::vec::*;
4use educe::Educe;
5use num_traits::One;
6
7use crate::{
8    bw6::{BW6Config, TwistType},
9    models::short_weierstrass::SWCurveConfig,
10    short_weierstrass::{Affine, Projective},
11    AffineRepr, CurveGroup,
12};
13
14pub type G2Affine<P> = Affine<<P as BW6Config>::G2Config>;
15pub type G2Projective<P> = Projective<<P as BW6Config>::G2Config>;
16
17#[derive(Educe, CanonicalSerialize, CanonicalDeserialize)]
18#[educe(Clone, Debug, PartialEq, Eq)]
19pub struct G2Prepared<P: BW6Config> {
20    /// Stores the coefficients of the line evaluations as calculated in
21    /// <https://eprint.iacr.org/2013/722.pdf>
22    pub ell_coeffs_1: Vec<(P::Fp, P::Fp, P::Fp)>,
23    pub ell_coeffs_2: Vec<(P::Fp, P::Fp, P::Fp)>,
24    pub infinity: bool,
25}
26
27#[derive(Educe, CanonicalSerialize, CanonicalDeserialize)]
28#[educe(Clone, Copy, Debug)]
29pub struct G2HomProjective<P: BW6Config> {
30    x: P::Fp,
31    y: P::Fp,
32    z: P::Fp,
33}
34
35impl<P: BW6Config> Default for G2Prepared<P> {
36    fn default() -> Self {
37        Self::from(G2Affine::<P>::generator())
38    }
39}
40
41// impl into G2Affine from G2HomProjective
42impl<P: BW6Config> From<G2HomProjective<P>> for G2Affine<P> {
43    fn from(q: G2HomProjective<P>) -> Self {
44        let z_inv = q.z.inverse().unwrap();
45        let x = q.x * &z_inv;
46        let y = q.y * &z_inv;
47        G2Affine::<P>::new_unchecked(x, y)
48    }
49}
50
51impl<P: BW6Config> From<G2Affine<P>> for G2Prepared<P> {
52    fn from(q: G2Affine<P>) -> Self {
53        if q.infinity {
54            return Self {
55                ell_coeffs_1: vec![],
56                ell_coeffs_2: vec![],
57                infinity: true,
58            };
59        }
60
61        // f_{u,Q}(P)
62        let mut ell_coeffs_1 = vec![];
63        let mut r = G2HomProjective::<P> {
64            x: q.x,
65            y: q.y,
66            z: P::Fp::one(),
67        };
68
69        for i in BitIteratorBE::new(P::ATE_LOOP_COUNT_1).skip(1) {
70            ell_coeffs_1.push(r.double_in_place());
71
72            if i {
73                ell_coeffs_1.push(r.add_in_place(&q));
74            }
75        }
76        // TODO: this is probably the slowest part
77        // While G2 preparation is overall faster due to shortened 2nd loop,
78        // The inversion could probably be avoided by using Hom(P) + Hom(Q) addition,
79        // instead of mixed addition as is currently done.
80        let r_affine: G2Affine<P> = r.into();
81        // Swap the signs of `qu`, `r` & `neg_qu` if the loop count is negative.
82        let (qu, neg_qu) = if P::ATE_LOOP_COUNT_1_IS_NEGATIVE {
83            (-r_affine, r_affine)
84        } else {
85            (r_affine, -r_affine)
86        };
87
88        r = G2HomProjective::<P> {
89            x: qu.x,
90            y: qu.y,
91            z: P::Fp::one(),
92        };
93        ell_coeffs_1.push(r.clone().add_in_place(&q));
94
95        let mut ell_coeffs_2 = vec![];
96
97        // f_{u^2-u-1,[u]Q}(P)
98        for bit in P::ATE_LOOP_COUNT_2.iter().rev().skip(1) {
99            ell_coeffs_2.push(r.double_in_place());
100
101            match bit {
102                1 => ell_coeffs_2.push(r.add_in_place(&qu)),
103                -1 => ell_coeffs_2.push(r.add_in_place(&neg_qu)),
104                _ => continue,
105            }
106        }
107
108        Self {
109            ell_coeffs_1,
110            ell_coeffs_2,
111            infinity: false,
112        }
113    }
114}
115
116impl<'a, P: BW6Config> From<&'a G2Affine<P>> for G2Prepared<P> {
117    fn from(q: &'a G2Affine<P>) -> Self {
118        (*q).into()
119    }
120}
121
122impl<'a, P: BW6Config> From<&'a G2Projective<P>> for G2Prepared<P> {
123    fn from(q: &'a G2Projective<P>) -> Self {
124        q.into_affine().into()
125    }
126}
127
128impl<P: BW6Config> From<G2Projective<P>> for G2Prepared<P> {
129    fn from(q: G2Projective<P>) -> Self {
130        q.into_affine().into()
131    }
132}
133
134impl<P: BW6Config> G2Prepared<P> {
135    pub fn is_zero(&self) -> bool {
136        self.infinity
137    }
138}
139
140impl<P: BW6Config> G2HomProjective<P> {
141    pub fn double_in_place(&mut self) -> (P::Fp, P::Fp, P::Fp) {
142        // Formula for line function when working with
143        // homogeneous projective coordinates, as described in
144        // <https://eprint.iacr.org/2013/722.pdf>.
145
146        let a = self.x * &self.y;
147        let b = self.y.square();
148        let b4 = b.double().double();
149        let c = self.z.square();
150        let e = P::G2Config::COEFF_B * &(c.double() + &c);
151        let f = e.double() + &e;
152        let g = b + &f;
153        let h = (self.y + &self.z).square() - &(b + &c);
154        let i = e - &b;
155        let j = self.x.square();
156        let e2_square = e.double().square();
157
158        self.x = a.double() * &(b - &f);
159        self.y = g.square() - &(e2_square.double() + &e2_square);
160        self.z = b4 * &h;
161        match P::TWIST_TYPE {
162            TwistType::M => (i, j.double() + &j, -h),
163            TwistType::D => (-h, j.double() + &j, i),
164        }
165    }
166
167    pub fn add_in_place(&mut self, q: &G2Affine<P>) -> (P::Fp, P::Fp, P::Fp) {
168        // Formula for line function when working with
169        // homogeneous projective coordinates, as described in https://eprint.iacr.org/2013/722.pdf.
170        let theta = self.y - &(q.y * &self.z);
171        let lambda = self.x - &(q.x * &self.z);
172        let c = theta.square();
173        let d = lambda.square();
174        let e = lambda * &d;
175        let f = self.z * &c;
176        let g = self.x * &d;
177        let h = e + &f - &g.double();
178        self.x = lambda * &h;
179        self.y = theta * &(g - &h) - &(e * &self.y);
180        self.z *= &e;
181        let j = theta * &q.x - &(lambda * &q.y);
182
183        match P::TWIST_TYPE {
184            TwistType::M => (j, -theta, lambda),
185            TwistType::D => (lambda, -theta, j),
186        }
187    }
188}
ark_ec/models/bw6/g2.rs

ark_ec/models/bw6/
g2.rs
