ark_r1cs_std/pairing/mnt4/
mod.rs

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

ark_r1cs_std/pairing/mnt4/
mod.rs
