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