ark_ec/
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 educe::Educe;
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(Educe)]
123#[educe(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
124#[must_use]
125pub struct PairingOutput<P: Pairing>(pub P::TargetField);
126
127impl<P: Pairing> Default for PairingOutput<P> {
128    fn default() -> Self {
129        // Default value is AdditiveGroup::ZERO (i.e., P::TargetField::one())
130        Self::ZERO
131    }
132}
133
134impl<P: Pairing> CanonicalSerialize for PairingOutput<P> {
135    #[allow(unused_qualifications)]
136    #[inline]
137    fn serialize_with_mode<W: Write>(
138        &self,
139        writer: W,
140        compress: Compress,
141    ) -> Result<(), SerializationError> {
142        self.0.serialize_with_mode(writer, compress)
143    }
144
145    #[inline]
146    fn serialized_size(&self, compress: Compress) -> usize {
147        self.0.serialized_size(compress)
148    }
149}
150
151impl<P: Pairing> Valid for PairingOutput<P> {
152    fn check(&self) -> Result<(), SerializationError> {
153        if self.0.pow(P::ScalarField::characteristic()).is_one() {
154            Ok(())
155        } else {
156            Err(SerializationError::InvalidData)
157        }
158    }
159}
160
161impl<P: Pairing> CanonicalDeserialize for PairingOutput<P> {
162    fn deserialize_with_mode<R: Read>(
163        reader: R,
164        compress: Compress,
165        validate: Validate,
166    ) -> Result<Self, SerializationError> {
167        let f = P::TargetField::deserialize_with_mode(reader, compress, validate).map(Self)?;
168        if let Validate::Yes = validate {
169            f.check()?;
170        }
171        Ok(f)
172    }
173}
174
175impl<P: Pairing> Display for PairingOutput<P> {
176    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
177        write!(f, "{}", self.0)
178    }
179}
180
181impl<P: Pairing> Zero for PairingOutput<P> {
182    /// 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()`.
183    fn zero() -> Self {
184        Self(P::TargetField::one())
185    }
186
187    fn is_zero(&self) -> bool {
188        self.0.is_one()
189    }
190}
191
192impl<'a, P: Pairing> Add<&'a Self> for PairingOutput<P> {
193    type Output = Self;
194
195    #[inline]
196    fn add(mut self, other: &'a Self) -> Self {
197        self += other;
198        self
199    }
200}
201
202impl<'a, P: Pairing> AddAssign<&'a Self> for PairingOutput<P> {
203    fn add_assign(&mut self, other: &'a Self) {
204        self.0 *= other.0;
205    }
206}
207
208impl<'a, P: Pairing> SubAssign<&'a Self> for PairingOutput<P> {
209    fn sub_assign(&mut self, other: &'a Self) {
210        self.0 *= other.0.cyclotomic_inverse().unwrap();
211    }
212}
213
214impl<'a, P: Pairing> Sub<&'a Self> for PairingOutput<P> {
215    type Output = Self;
216
217    #[inline]
218    fn sub(mut self, other: &'a Self) -> Self {
219        self -= other;
220        self
221    }
222}
223
224ark_ff::impl_additive_ops_from_ref!(PairingOutput, Pairing);
225
226impl<P: Pairing, T: Borrow<P::ScalarField>> MulAssign<T> for PairingOutput<P> {
227    fn mul_assign(&mut self, other: T) {
228        *self = self.mul_bigint(other.borrow().into_bigint());
229    }
230}
231
232impl<P: Pairing, T: Borrow<P::ScalarField>> Mul<T> for PairingOutput<P> {
233    type Output = Self;
234
235    fn mul(self, other: T) -> Self {
236        self.mul_bigint(other.borrow().into_bigint())
237    }
238}
239
240impl<P: Pairing> Zeroize for PairingOutput<P> {
241    fn zeroize(&mut self) {
242        self.0.zeroize()
243    }
244}
245
246impl<P: Pairing> Neg for PairingOutput<P> {
247    type Output = Self;
248
249    #[inline]
250    fn neg(self) -> Self {
251        Self(self.0.cyclotomic_inverse().unwrap())
252    }
253}
254
255impl<P: Pairing> Distribution<PairingOutput<P>> for Standard {
256    #[inline]
257    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> PairingOutput<P> {
258        // Sample a random G1 element
259        let g1 = P::G1::rand(rng);
260        // Sample a random G2 element
261        let g2 = P::G2::rand(rng);
262        P::pairing(g1, g2)
263    }
264}
265
266impl<P: Pairing> AdditiveGroup for PairingOutput<P> {
267    type Scalar = P::ScalarField;
268
269    const ZERO: Self = Self(P::TargetField::ONE);
270
271    fn double_in_place(&mut self) -> &mut Self {
272        self.0.cyclotomic_square_in_place();
273        self
274    }
275}
276
277impl<P: Pairing> PrimeGroup for PairingOutput<P> {
278    type ScalarField = P::ScalarField;
279
280    fn generator() -> Self {
281        // TODO: hardcode these values.
282        // Sample a random G1 element
283        let g1 = P::G1::generator();
284        // Sample a random G2 element
285        let g2 = P::G2::generator();
286        P::pairing(g1.into(), g2.into())
287    }
288
289    fn mul_bigint(&self, other: impl AsRef<[u64]>) -> Self {
290        Self(self.0.cyclotomic_exp(other.as_ref()))
291    }
292
293    fn mul_bits_be(&self, other: impl Iterator<Item = bool>) -> Self {
294        // Convert back from bits to [u64] limbs
295        let other = other
296            .collect::<Vec<_>>()
297            .chunks(64)
298            .map(|chunk| {
299                chunk
300                    .iter()
301                    .enumerate()
302                    .fold(0, |r, (i, bit)| r | u64::from(*bit) << i)
303            })
304            .collect::<Vec<_>>();
305        Self(self.0.cyclotomic_exp(&other))
306    }
307}
308
309impl<P: Pairing> crate::ScalarMul for PairingOutput<P> {
310    type MulBase = Self;
311    const NEGATION_IS_CHEAP: bool = P::TargetField::INVERSE_IS_FAST;
312
313    fn batch_convert_to_mul_base(bases: &[Self]) -> Vec<Self::MulBase> {
314        bases.to_vec()
315    }
316}
317
318impl<P: Pairing> VariableBaseMSM for PairingOutput<P> {}
319
320/// Represents the output of the Miller loop of the pairing.
321#[derive(Educe)]
322#[educe(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
323#[must_use]
324pub struct MillerLoopOutput<P: Pairing>(pub P::TargetField);
325
326impl<P: Pairing> Mul<P::ScalarField> for MillerLoopOutput<P> {
327    type Output = Self;
328
329    fn mul(self, other: P::ScalarField) -> Self {
330        Self(self.0.pow(other.into_bigint()))
331    }
332}
333
334/// Preprocesses a G1 element for use in a pairing.
335pub fn prepare_g1<E: Pairing>(g: impl Into<E::G1Affine>) -> E::G1Prepared {
336    let g: E::G1Affine = g.into();
337    E::G1Prepared::from(g)
338}
339
340/// Preprocesses a G2 element for use in a pairing.
341pub fn prepare_g2<E: Pairing>(g: impl Into<E::G2Affine>) -> E::G2Prepared {
342    let g: E::G2Affine = g.into();
343    E::G2Prepared::from(g)
344}
ark_ec/pairing.rs

ark_ec/
pairing.rs
