1use crate::prelude::*;
  2use algebra::{Field, PairingEngine};
  3use core::fmt::Debug;
  4use r1cs_core::SynthesisError;
  5
  6/// This module implements pairings for BLS12 bilinear groups.
  7pub mod bls12;
  8/// This module implements pairings for MNT4 bilinear groups.
  9pub mod mnt4;
 10/// This module implements pairings for MNT6 bilinear groups.
 11pub mod mnt6;
 12
 13/// Specifies the constraints for computing a pairing in the yybilinear group `E`.
 14pub trait PairingVar<E: PairingEngine, ConstraintF: Field = <E as PairingEngine>::Fq> {
 15    /// An variable representing an element of `G1`.
 16    /// This is the R1CS equivalent of `E::G1Projective`.
 17    type G1Var: CurveVar<E::G1Projective, ConstraintF>
 18        + AllocVar<E::G1Projective, ConstraintF>
 19        + AllocVar<E::G1Affine, ConstraintF>;
 20
 21    /// An variable representing an element of `G2`.
 22    /// This is the R1CS equivalent of `E::G2Projective`.
 23    type G2Var: CurveVar<E::G2Projective, ConstraintF>
 24        + AllocVar<E::G2Projective, ConstraintF>
 25        + AllocVar<E::G2Affine, ConstraintF>;
 26
 27    /// An variable representing an element of `GT`.
 28    /// This is the R1CS equivalent of `E::GT`.
 29    type GTVar: FieldVar<E::Fqk, ConstraintF>;
 30
 31    /// An variable representing cached precomputation  that can speed up pairings computations.
 32    /// This is the R1CS equivalent of `E::G1Prepared`.
 33    type G1PreparedVar: ToBytesGadget<ConstraintF>
 34        + AllocVar<E::G1Prepared, ConstraintF>
 35        + Clone
 36        + Debug;
 37    /// An variable representing cached precomputation  that can speed up pairings computations.
 38    /// This is the R1CS equivalent of `E::G2Prepared`.
 39    type G2PreparedVar: ToBytesGadget<ConstraintF>
 40        + AllocVar<E::G2Prepared, ConstraintF>
 41        + Clone
 42        + Debug;
 43
 44    /// Computes a multi-miller loop between elements
 45    /// of `p` and `q`.
 46    fn miller_loop(
 47        p: &[Self::G1PreparedVar],
 48        q: &[Self::G2PreparedVar],
 49    ) -> Result<Self::GTVar, SynthesisError>;
 50
 51    /// Computes a final exponentiation over `p`.
 52    fn final_exponentiation(p: &Self::GTVar) -> Result<Self::GTVar, SynthesisError>;
 53
 54    /// Computes a pairing over `p` and `q`.
 55    #[tracing::instrument(target = "r1cs")]
 56    fn pairing(
 57        p: Self::G1PreparedVar,
 58        q: Self::G2PreparedVar,
 59    ) -> Result<Self::GTVar, SynthesisError> {
 60        let tmp = Self::miller_loop(&[p], &[q])?;
 61        Self::final_exponentiation(&tmp)
 62    }
 63
 64    /// Computes a product of pairings over the elements in `p` and `q`.
 65    #[must_use]
 66    #[tracing::instrument(target = "r1cs")]
 67    fn product_of_pairings(
 68        p: &[Self::G1PreparedVar],
 69        q: &[Self::G2PreparedVar],
 70    ) -> Result<Self::GTVar, SynthesisError> {
 71        let miller_result = Self::miller_loop(p, q)?;
 72        Self::final_exponentiation(&miller_result)
 73    }
 74
 75    /// Performs the precomputation to generate `Self::G1PreparedVar`.
 76    fn prepare_g1(q: &Self::G1Var) -> Result<Self::G1PreparedVar, SynthesisError>;
 77
 78    /// Performs the precomputation to generate `Self::G2PreparedVar`.
 79    fn prepare_g2(q: &Self::G2Var) -> Result<Self::G2PreparedVar, SynthesisError>;
 80}
 81
 82#[cfg(test)]
 83pub(crate) mod tests {
 84    use crate::{prelude::*, Vec};
 85    use algebra::{
 86        test_rng, BitIteratorLE, Field, PairingEngine, PrimeField, ProjectiveCurve, UniformRand,
 87    };
 88    use r1cs_core::{ConstraintSystem, SynthesisError};
 89
 90    #[allow(dead_code)]
 91    pub(crate) fn bilinearity_test<E: PairingEngine, P: PairingVar<E>>(
 92    ) -> Result<(), SynthesisError>
 93    where
 94        for<'a> &'a P::G1Var: GroupOpsBounds<'a, E::G1Projective, P::G1Var>,
 95        for<'a> &'a P::G2Var: GroupOpsBounds<'a, E::G2Projective, P::G2Var>,
 96        for<'a> &'a P::GTVar: FieldOpsBounds<'a, E::Fqk, P::GTVar>,
 97    {
 98        let cs = ConstraintSystem::<E::Fq>::new_ref();
 99
100        let mut rng = test_rng();
101        let a = E::G1Projective::rand(&mut rng);
102        let b = E::G2Projective::rand(&mut rng);
103        let s = E::Fr::rand(&mut rng);
104
105        let mut sa = a;
106        sa *= s;
107        let mut sb = b;
108        sb *= s;
109
110        let a_g = P::G1Var::new_witness(cs.clone(), || Ok(a.into_affine()))?;
111        let b_g = P::G2Var::new_witness(cs.clone(), || Ok(b.into_affine()))?;
112        let sa_g = P::G1Var::new_witness(cs.clone(), || Ok(sa.into_affine()))?;
113        let sb_g = P::G2Var::new_witness(cs.clone(), || Ok(sb.into_affine()))?;
114
115        let mut preparation_num_constraints = cs.num_constraints();
116        let a_prep_g = P::prepare_g1(&a_g)?;
117        let b_prep_g = P::prepare_g2(&b_g)?;
118        preparation_num_constraints = cs.num_constraints() - preparation_num_constraints;
119        println!(
120            "Preparation num constraints: {}",
121            preparation_num_constraints
122        );
123
124        let sa_prep_g = P::prepare_g1(&sa_g)?;
125        let sb_prep_g = P::prepare_g2(&sb_g)?;
126
127        let (ans1_g, ans1_n) = {
128            let ml_constraints = cs.num_constraints();
129            let ml_g = P::miller_loop(&[sa_prep_g], &[b_prep_g.clone()])?;
130            println!(
131                "ML num constraints: {}",
132                cs.num_constraints() - ml_constraints
133            );
134            let fe_constraints = cs.num_constraints();
135            let ans_g = P::final_exponentiation(&ml_g)?;
136            println!(
137                "FE num constraints: {}",
138                cs.num_constraints() - fe_constraints
139            );
140            let ans_n = E::pairing(sa, b);
141            (ans_g, ans_n)
142        };
143
144        let (ans2_g, ans2_n) = {
145            let ans_g = P::pairing(a_prep_g.clone(), sb_prep_g)?;
146            let ans_n = E::pairing(a, sb);
147            (ans_g, ans_n)
148        };
149
150        let (ans3_g, ans3_n) = {
151            let s_iter = BitIteratorLE::without_trailing_zeros(s.into_repr())
152                .map(Boolean::constant)
153                .collect::<Vec<_>>();
154
155            let mut ans_g = P::pairing(a_prep_g, b_prep_g)?;
156            let mut ans_n = E::pairing(a, b);
157            ans_n = ans_n.pow(s.into_repr());
158            ans_g = ans_g.pow_le(&s_iter)?;
159
160            (ans_g, ans_n)
161        };
162
163        ans1_g.enforce_equal(&ans2_g)?;
164        ans2_g.enforce_equal(&ans3_g)?;
165
166        assert_eq!(ans1_g.value()?, ans1_n, "Failed native test 1");
167        assert_eq!(ans2_g.value()?, ans2_n, "Failed native test 2");
168        assert_eq!(ans3_g.value()?, ans3_n, "Failed native test 3");
169
170        assert_eq!(ans1_n, ans2_n, "Failed ans1_native == ans2_native");
171        assert_eq!(ans2_n, ans3_n, "Failed ans2_native == ans3_native");
172        assert_eq!(ans1_g.value()?, ans3_g.value()?, "Failed ans1 == ans3");
173        assert_eq!(ans1_g.value()?, ans2_g.value()?, "Failed ans1 == ans2");
174        assert_eq!(ans2_g.value()?, ans3_g.value()?, "Failed ans2 == ans3");
175
176        if !cs.is_satisfied().unwrap() {
177            println!("Unsatisfied: {:?}", cs.which_is_unsatisfied());
178        }
179
180        assert!(cs.is_satisfied().unwrap(), "cs is not satisfied");
181        Ok(())
182    }
183}