1use r1cs_core::SynthesisError;
  2
  3use super::PairingVar as PG;
  4
  5use crate::{
  6    fields::{fp::FpVar, fp2::Fp2Var, fp4::Fp4Var, FieldVar},
  7    groups::mnt4::{
  8        AteAdditionCoefficientsVar, AteDoubleCoefficientsVar, G1PreparedVar, G1Var, G2PreparedVar,
  9        G2ProjectiveExtendedVar, G2Var,
 10    },
 11};
 12use algebra::{
 13    curves::mnt4::{MNT4Parameters, MNT4},
 14    fields::BitIterator,
 15};
 16use core::marker::PhantomData;
 17
 18pub struct PairingVar<P: MNT4Parameters>(PhantomData<P>);
 19
 20type Fp2G<P> = Fp2Var<<P as MNT4Parameters>::Fp2Params>;
 21type Fp4G<P> = Fp4Var<<P as MNT4Parameters>::Fp4Params>;
 22pub type GTVar<P> = Fp4G<P>;
 23
 24impl<P: MNT4Parameters> PairingVar<P> {
 25    pub(crate) fn doubling_step_for_flipped_miller_loop(
 26        r: &G2ProjectiveExtendedVar<P>,
 27    ) -> Result<(G2ProjectiveExtendedVar<P>, AteDoubleCoefficientsVar<P>), SynthesisError> {
 28        let a = r.t.square()?;
 29        let b = r.x.square()?;
 30        let c = r.y.square()?;
 31        let d = c.square()?;
 32        let e = (&r.x + &c).square()? - &b - &d;
 33        let f = (b.double()? + &b) + &a * P::TWIST_COEFF_A;
 34        let g = f.square()?;
 35
 36        let d_eight = d.double()?.double()?.double()?;
 37
 38        let e2 = e.double()?;
 39        let x = &g - &e2.double()?;
 40
 41        let y = &f * (&e2 - &x) - &d_eight;
 42        let z = (&r.y + &r.z).square()? - &c - &r.z.square()?;
 43        let t = z.square()?;
 44
 45        let r2 = G2ProjectiveExtendedVar { x, y, z, t };
 46        let c_h = (&r2.z + &r.t).square()? - &r2.t - &a;
 47        let c_4c = c.double()?.double()?;
 48        let c_j = (&f + &r.t).square()? - &g - &a;
 49        let c_l = (&f + &r.x).square()? - &g - &b;
 50        let coeff = AteDoubleCoefficientsVar {
 51            c_h,
 52            c_4c,
 53            c_j,
 54            c_l,
 55        };
 56
 57        Ok((r2, coeff))
 58    }
 59
 60    pub(crate) fn mixed_addition_step_for_flipped_miller_loop(
 61        x: &Fp2G<P>,
 62        y: &Fp2G<P>,
 63        r: &G2ProjectiveExtendedVar<P>,
 64    ) -> Result<(G2ProjectiveExtendedVar<P>, AteAdditionCoefficientsVar<P>), SynthesisError> {
 65        let a = y.square()?;
 66        let b = &r.t * x;
 67        let d = ((&r.z + y).square()? - &a - &r.t) * &r.t;
 68        let h = &b - &r.x;
 69        let i = h.square()?;
 70        let e = i.double()?.double()?;
 71        let j = &h * &e;
 72        let v = &r.x * &e;
 73        let ry2 = r.y.double()?;
 74        let l1 = &d - &ry2;
 75
 76        let x = l1.square()? - &j - &v.double()?;
 77        let y = &l1 * &(&v - &x) - j * &ry2;
 78        let z = (&r.z + &h).square()? - &r.t - &i;
 79        let t = z.square()?;
 80
 81        let r2 = G2ProjectiveExtendedVar {
 82            x,
 83            y,
 84            z: z.clone(),
 85            t,
 86        };
 87        let coeff = AteAdditionCoefficientsVar { c_l1: l1, c_rz: z };
 88
 89        Ok((r2, coeff))
 90    }
 91
 92    pub fn ate_miller_loop(
 93        p: &G1PreparedVar<P>,
 94        q: &G2PreparedVar<P>,
 95    ) -> Result<Fp4G<P>, SynthesisError> {
 96        let l1_coeff = Fp2G::<P>::new(p.x.clone(), FpVar::<P::Fp>::zero()) - &q.x_over_twist;
 97
 98        let mut f = Fp4G::<P>::one();
 99
100        let mut dbl_idx: usize = 0;
101        let mut add_idx: usize = 0;
102
103        let mut found_one = false;
104
105        for bit in BitIterator::new(P::ATE_LOOP_COUNT) {
106            // code below gets executed for all bits (EXCEPT the MSB itself) of
107            // mnt6_param_p (skipping leading zeros) in MSB to LSB order
108            if !found_one && bit {
109                found_one = true;
110                continue;
111            } else if !found_one {
112                continue;
113            }
114
115            let dc = &q.double_coefficients[dbl_idx];
116            dbl_idx += 1;
117
118            let g_rr_at_p = Fp4G::<P>::new(
119                &dc.c_l - &dc.c_4c - &dc.c_j * &p.x_twist,
120                &dc.c_h * &p.y_twist,
121            );
122
123            f = f.square()? * &g_rr_at_p;
124
125            if bit {
126                let ac = &q.addition_coefficients[add_idx];
127                add_idx += 1;
128
129                let g_rq_at_p = Fp4G::<P>::new(
130                    &ac.c_rz * &p.y_twist,
131                    (&q.y_over_twist * &ac.c_rz + &l1_coeff * &ac.c_l1).negate()?,
132                );
133                f *= &g_rq_at_p;
134            }
135        }
136
137        if P::ATE_IS_LOOP_COUNT_NEG {
138            let ac = &q.addition_coefficients[add_idx];
139
140            let g_rnegr_at_p = Fp4G::<P>::new(
141                &ac.c_rz * &p.y_twist,
142                (&q.y_over_twist * &ac.c_rz + &l1_coeff * &ac.c_l1).negate()?,
143            );
144            f = (&f * &g_rnegr_at_p).inverse()?;
145        }
146
147        Ok(f)
148    }
149
150    pub fn final_exponentiation(value: &Fp4G<P>) -> Result<GTVar<P>, SynthesisError> {
151        let value_inv = value.inverse()?;
152        let value_to_first_chunk = Self::final_exponentiation_first_chunk(value, &value_inv)?;
153        let value_inv_to_first_chunk = Self::final_exponentiation_first_chunk(&value_inv, value)?;
154        Self::final_exponentiation_last_chunk(&value_to_first_chunk, &value_inv_to_first_chunk)
155    }
156
157    fn final_exponentiation_first_chunk(
158        elt: &Fp4G<P>,
159        elt_inv: &Fp4G<P>,
160    ) -> Result<Fp4G<P>, SynthesisError> {
161        // (q^2-1)
162
163        // elt_q2 = elt^(q^2)
164        let elt_q2 = elt.unitary_inverse()?;
165        // elt_q2_over_elt = elt^(q^2-1)
166        Ok(elt_q2 * elt_inv)
167    }
168
169    fn final_exponentiation_last_chunk(
170        elt: &Fp4G<P>,
171        elt_inv: &Fp4G<P>,
172    ) -> Result<Fp4G<P>, SynthesisError> {
173        let elt_clone = elt.clone();
174        let elt_inv_clone = elt_inv.clone();
175
176        let mut elt_q = elt.clone();
177        elt_q.frobenius_map_in_place(1)?;
178
179        let w1_part = elt_q.cyclotomic_exp(&P::FINAL_EXPONENT_LAST_CHUNK_1)?;
180        let w0_part = if P::FINAL_EXPONENT_LAST_CHUNK_W0_IS_NEG {
181            elt_inv_clone.cyclotomic_exp(&P::FINAL_EXPONENT_LAST_CHUNK_ABS_OF_W0)?
182        } else {
183            elt_clone.cyclotomic_exp(&P::FINAL_EXPONENT_LAST_CHUNK_ABS_OF_W0)?
184        };
185
186        Ok(w1_part * &w0_part)
187    }
188}
189
190impl<P: MNT4Parameters> PG<MNT4<P>, P::Fp> for PairingVar<P> {
191    type G1Var = G1Var<P>;
192    type G2Var = G2Var<P>;
193    type G1PreparedVar = G1PreparedVar<P>;
194    type G2PreparedVar = G2PreparedVar<P>;
195    type GTVar = GTVar<P>;
196
197    fn miller_loop(
198        ps: &[Self::G1PreparedVar],
199        qs: &[Self::G2PreparedVar],
200    ) -> Result<Self::GTVar, SynthesisError> {
201        let mut result = Fp4G::<P>::one();
202        for (p, q) in ps.iter().zip(qs) {
203            result *= Self::ate_miller_loop(p, q)?;
204        }
205
206        Ok(result)
207    }
208
209    fn final_exponentiation(r: &Self::GTVar) -> Result<Self::GTVar, SynthesisError> {
210        Self::final_exponentiation(r)
211    }
212
213    fn prepare_g1(p: &Self::G1Var) -> Result<Self::G1PreparedVar, SynthesisError> {
214        Self::G1PreparedVar::from_group_var(p)
215    }
216
217    fn prepare_g2(q: &Self::G2Var) -> Result<Self::G2PreparedVar, SynthesisError> {
218        Self::G2PreparedVar::from_group_var(q)
219    }
220}