ark_ec_zypher/
pairing.rs

1use ark_ff::{AdditiveGroup, CyclotomicMultSubgroup, Field, One, PrimeField};
2use ark_serialize::{
3    CanonicalDeserialize, CanonicalSerialize, Compress, SerializationError, Valid, Validate,
4};
5use ark_std::{
6    borrow::Borrow,
7    fmt::{Debug, Display, Formatter, Result as FmtResult},
8    io::{Read, Write},
9    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
10    rand::{
11        distributions::{Distribution, Standard},
12        Rng,
13    },
14    vec::*,
15    UniformRand, Zero,
16};
17use derivative::Derivative;
18use zeroize::Zeroize;
19
20use crate::{AffineRepr, CurveGroup, PrimeGroup, VariableBaseMSM};
21
22/// Collection of types (mainly fields and curves) that together describe
23/// how to compute a pairing over a pairing-friendly curve.
24pub trait Pairing: Sized + 'static + Copy + Debug + Sync + Send + Eq {
25    /// This is the base field of the G1 group and base prime field of G2.
26    type BaseField: PrimeField;
27
28    /// This is the scalar field of the G1/G2 groups.
29    type ScalarField: PrimeField;
30
31    /// An element in G1.
32    type G1: CurveGroup<ScalarField = Self::ScalarField, Affine = Self::G1Affine>
33        + From<Self::G1Affine>
34        + Into<Self::G1Affine>
35        // needed due to https://github.com/rust-lang/rust/issues/69640
36        + MulAssign<Self::ScalarField>;
37
38    type G1Affine: AffineRepr<Group = Self::G1, ScalarField = Self::ScalarField>
39        + From<Self::G1>
40        + Into<Self::G1>
41        + Into<Self::G1Prepared>;
42
43    /// A G1 element that has been preprocessed for use in a pairing.
44    type G1Prepared: Default
45        + Clone
46        + Send
47        + Sync
48        + Debug
49        + CanonicalSerialize
50        + CanonicalDeserialize
51        + for<'a> From<&'a Self::G1>
52        + for<'a> From<&'a Self::G1Affine>
53        + From<Self::G1>
54        + From<Self::G1Affine>;
55
56    /// An element of G2.
57    type G2: CurveGroup<ScalarField = Self::ScalarField, Affine = Self::G2Affine>
58        + From<Self::G2Affine>
59        + Into<Self::G2Affine>
60        // needed due to https://github.com/rust-lang/rust/issues/69640
61        + MulAssign<Self::ScalarField>;
62
63    /// The affine representation of an element in G2.
64    type G2Affine: AffineRepr<Group = Self::G2, ScalarField = Self::ScalarField>
65        + From<Self::G2>
66        + Into<Self::G2>
67        + Into<Self::G2Prepared>;
68
69    /// A G2 element that has been preprocessed for use in a pairing.
70    type G2Prepared: Default
71        + Clone
72        + Send
73        + Sync
74        + Debug
75        + CanonicalSerialize
76        + CanonicalDeserialize
77        + for<'a> From<&'a Self::G2>
78        + for<'a> From<&'a Self::G2Affine>
79        + From<Self::G2>
80        + From<Self::G2Affine>;
81
82    /// The extension field that hosts the target group of the pairing.
83    type TargetField: CyclotomicMultSubgroup;
84
85    /// Computes the product of Miller loops for some number of (G1, G2) pairs.
86    fn multi_miller_loop(
87        a: impl IntoIterator<Item = impl Into<Self::G1Prepared>>,
88        b: impl IntoIterator<Item = impl Into<Self::G2Prepared>>,
89    ) -> MillerLoopOutput<Self>;
90
91    /// Computes the Miller loop over `a` and `b`.
92    fn miller_loop(
93        a: impl Into<Self::G1Prepared>,
94        b: impl Into<Self::G2Prepared>,
95    ) -> MillerLoopOutput<Self> {
96        Self::multi_miller_loop([a], [b])
97    }
98
99    /// Performs final exponentiation of the result of a `Self::multi_miller_loop`.
100    #[must_use]
101    fn final_exponentiation(mlo: MillerLoopOutput<Self>) -> Option<PairingOutput<Self>>;
102
103    /// Computes a "product" of pairings.
104    fn multi_pairing(
105        a: impl IntoIterator<Item = impl Into<Self::G1Prepared>>,
106        b: impl IntoIterator<Item = impl Into<Self::G2Prepared>>,
107    ) -> PairingOutput<Self> {
108        Self::final_exponentiation(Self::multi_miller_loop(a, b)).unwrap()
109    }
110
111    /// Performs multiple pairing operations
112    fn pairing(
113        p: impl Into<Self::G1Prepared>,
114        q: impl Into<Self::G2Prepared>,
115    ) -> PairingOutput<Self> {
116        Self::multi_pairing([p], [q])
117    }
118}
119
120/// Represents the target group of a pairing. This struct is a
121/// wrapper around the field that the target group is embedded in.
122#[derive(Derivative)]
123#[derivative(
124    Copy(bound = "P: Pairing"),
125    Clone(bound = "P: Pairing"),
126    Debug(bound = "P: Pairing"),
127    PartialEq(bound = "P: Pairing"),
128    Eq(bound = "P: Pairing"),
129    PartialOrd(bound = "P: Pairing"),
130    Ord(bound = "P: Pairing"),
131    Hash(bound = "P: Pairing")
132)]
133#[must_use]
134pub struct PairingOutput<P: Pairing>(pub P::TargetField);
135
136impl<P: Pairing> Default for PairingOutput<P> {
137    fn default() -> Self {
138        // Default value is AdditiveGroup::ZERO (i.e., P::TargetField::one())
139        Self::ZERO
140    }
141}
142
143impl<P: Pairing> CanonicalSerialize for PairingOutput<P> {
144    #[allow(unused_qualifications)]
145    #[inline]
146    fn serialize_with_mode<W: Write>(
147        &self,
148        writer: W,
149        compress: Compress,
150    ) -> Result<(), SerializationError> {
151        self.0.serialize_with_mode(writer, compress)
152    }
153
154    #[inline]
155    fn serialized_size(&self, compress: Compress) -> usize {
156        self.0.serialized_size(compress)
157    }
158}
159
160impl<P: Pairing> Valid for PairingOutput<P> {
161    fn check(&self) -> Result<(), SerializationError> {
162        if self.0.pow(P::ScalarField::characteristic()).is_one() {
163            Ok(())
164        } else {
165            Err(SerializationError::InvalidData)
166        }
167    }
168}
169
170impl<P: Pairing> CanonicalDeserialize for PairingOutput<P> {
171    fn deserialize_with_mode<R: Read>(
172        reader: R,
173        compress: Compress,
174        validate: Validate,
175    ) -> Result<Self, SerializationError> {
176        let f = P::TargetField::deserialize_with_mode(reader, compress, validate).map(Self)?;
177        if let Validate::Yes = validate {
178            f.check()?;
179        }
180        Ok(f)
181    }
182}
183
184impl<P: Pairing> Display for PairingOutput<P> {
185    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
186        write!(f, "{}", self.0)
187    }
188}
189
190impl<P: Pairing> Zero for PairingOutput<P> {
191    /// The identity element, or "zero", of the group is the identity element of the multiplicative group of the underlying field, i.e., `P::TargetField::one()`.
192    fn zero() -> Self {
193        Self(P::TargetField::one())
194    }
195
196    fn is_zero(&self) -> bool {
197        self.0.is_one()
198    }
199}
200
201impl<'a, P: Pairing> Add<&'a Self> for PairingOutput<P> {
202    type Output = Self;
203
204    #[inline]
205    fn add(mut self, other: &'a Self) -> Self {
206        self += other;
207        self
208    }
209}
210
211impl<'a, P: Pairing> AddAssign<&'a Self> for PairingOutput<P> {
212    fn add_assign(&mut self, other: &'a Self) {
213        self.0 *= other.0;
214    }
215}
216
217impl<'a, P: Pairing> SubAssign<&'a Self> for PairingOutput<P> {
218    fn sub_assign(&mut self, other: &'a Self) {
219        self.0 *= other.0.cyclotomic_inverse().unwrap();
220    }
221}
222
223impl<'a, P: Pairing> Sub<&'a Self> for PairingOutput<P> {
224    type Output = Self;
225
226    #[inline]
227    fn sub(mut self, other: &'a Self) -> Self {
228        self -= other;
229        self
230    }
231}
232
233ark_ff::impl_additive_ops_from_ref!(PairingOutput, Pairing);
234
235impl<P: Pairing, T: Borrow<P::ScalarField>> MulAssign<T> for PairingOutput<P> {
236    fn mul_assign(&mut self, other: T) {
237        *self = self.mul_bigint(other.borrow().into_bigint());
238    }
239}
240
241impl<P: Pairing, T: Borrow<P::ScalarField>> Mul<T> for PairingOutput<P> {
242    type Output = Self;
243
244    fn mul(self, other: T) -> Self {
245        self.mul_bigint(other.borrow().into_bigint())
246    }
247}
248
249impl<P: Pairing> Zeroize for PairingOutput<P> {
250    fn zeroize(&mut self) {
251        self.0.zeroize()
252    }
253}
254
255impl<P: Pairing> Neg for PairingOutput<P> {
256    type Output = Self;
257
258    #[inline]
259    fn neg(self) -> Self {
260        Self(self.0.cyclotomic_inverse().unwrap())
261    }
262}
263
264impl<P: Pairing> Distribution<PairingOutput<P>> for Standard {
265    #[inline]
266    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> PairingOutput<P> {
267        // Sample a random G1 element
268        let g1 = P::G1::rand(rng);
269        // Sample a random G2 element
270        let g2 = P::G2::rand(rng);
271        P::pairing(g1, g2)
272    }
273}
274
275impl<P: Pairing> AdditiveGroup for PairingOutput<P> {
276    type Scalar = P::ScalarField;
277
278    const ZERO: Self = Self(P::TargetField::ONE);
279
280    fn double_in_place(&mut self) -> &mut Self {
281        self.0.cyclotomic_square_in_place();
282        self
283    }
284}
285
286impl<P: Pairing> PrimeGroup for PairingOutput<P> {
287    type ScalarField = P::ScalarField;
288
289    fn generator() -> Self {
290        // TODO: hardcode these values.
291        // Sample a random G1 element
292        let g1 = P::G1::generator();
293        // Sample a random G2 element
294        let g2 = P::G2::generator();
295        P::pairing(g1.into(), g2.into())
296    }
297
298    fn mul_bigint(&self, other: impl AsRef<[u64]>) -> Self {
299        Self(self.0.cyclotomic_exp(other.as_ref()))
300    }
301
302    fn mul_bits_be(&self, other: impl Iterator<Item = bool>) -> Self {
303        // Convert back from bits to [u64] limbs
304        let other = other
305            .collect::<Vec<_>>()
306            .chunks(64)
307            .map(|chunk| {
308                chunk
309                    .iter()
310                    .enumerate()
311                    .fold(0, |r, (i, bit)| r | u64::from(*bit) << i)
312            })
313            .collect::<Vec<_>>();
314        Self(self.0.cyclotomic_exp(&other))
315    }
316}
317
318impl<P: Pairing> crate::ScalarMul for PairingOutput<P> {
319    type MulBase = Self;
320    const NEGATION_IS_CHEAP: bool = P::TargetField::INVERSE_IS_FAST;
321
322    fn batch_convert_to_mul_base(bases: &[Self]) -> Vec<Self::MulBase> {
323        bases.to_vec()
324    }
325}
326
327impl<P: Pairing> VariableBaseMSM for PairingOutput<P> {}
328
329/// Represents the output of the Miller loop of the pairing.
330#[derive(Derivative)]
331#[derivative(
332    Copy(bound = "P: Pairing"),
333    Clone(bound = "P: Pairing"),
334    Debug(bound = "P: Pairing"),
335    PartialEq(bound = "P: Pairing"),
336    Eq(bound = "P: Pairing"),
337    PartialOrd(bound = "P: Pairing"),
338    Ord(bound = "P: Pairing")
339)]
340#[must_use]
341pub struct MillerLoopOutput<P: Pairing>(pub P::TargetField);
342
343impl<P: Pairing> Mul<P::ScalarField> for MillerLoopOutput<P> {
344    type Output = Self;
345
346    fn mul(self, other: P::ScalarField) -> Self {
347        Self(self.0.pow(other.into_bigint()))
348    }
349}
350
351/// Preprocesses a G1 element for use in a pairing.
352pub fn prepare_g1<E: Pairing>(g: impl Into<E::G1Affine>) -> E::G1Prepared {
353    let g: E::G1Affine = g.into();
354    E::G1Prepared::from(g)
355}
356
357/// Preprocesses a G2 element for use in a pairing.
358pub fn prepare_g2<E: Pairing>(g: impl Into<E::G2Affine>) -> E::G2Prepared {
359    let g: E::G2Affine = g.into();
360    E::G2Prepared::from(g)
361}
ark_ec_zypher/pairing.rs

ark_ec_zypher/
pairing.rs
