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

ark_ec/
pairing.rs
