pairing_plus/
lib.rs

1// `clippy` is a code linting tool for improving code quality by catching
2// common mistakes or strange code patterns. If the `cargo-clippy` feature
3// is provided, all compiler warnings are prohibited.
4#![cfg_attr(feature = "cargo-clippy", deny(warnings))]
5#![cfg_attr(feature = "cargo-clippy", allow(clippy::inline_always))]
6#![cfg_attr(feature = "cargo-clippy", allow(clippy::too_many_arguments))]
7#![cfg_attr(feature = "cargo-clippy", allow(clippy::unreadable_literal))]
8#![cfg_attr(feature = "cargo-clippy", allow(clippy::many_single_char_names))]
9#![cfg_attr(feature = "cargo-clippy", allow(clippy::new_without_default))]
10#![cfg_attr(feature = "cargo-clippy", allow(clippy::write_literal))]
11#![cfg_attr(feature = "cargo-clippy", allow(clippy::missing_safety_doc))]
12#![cfg_attr(feature = "cargo-clippy", allow(clippy::cognitive_complexity))]
13// Force public structures to implement Debug
14#![deny(missing_debug_implementations)]
15
16extern crate digest;
17extern crate ff_zeroize as ff;
18extern crate rand_core;
19extern crate rand_xorshift;
20#[cfg(test)]
21extern crate sha2;
22#[cfg(test)]
23extern crate sha3;
24#[macro_use]
25extern crate zeroize;
26
27#[cfg(test)]
28pub mod tests;
29
30pub mod bls12_381;
31pub mod hash_to_curve;
32pub mod hash_to_field;
33pub mod serdes;
34pub mod signum;
35
36mod wnaf;
37pub use self::wnaf::Wnaf;
38
39use ff::{Field, PrimeField, PrimeFieldDecodingError, PrimeFieldRepr, ScalarEngine, SqrtField};
40use std::error::Error;
41use std::fmt;
42
43/// An "engine" is a collection of types (fields, elliptic curve groups, etc.)
44/// with well-defined relationships. In particular, the G1/G2 curve groups are
45/// of prime order `r`, and are equipped with a bilinear pairing function.
46pub trait Engine: ScalarEngine {
47    /// The projective representation of an element in G1.
48    type G1: CurveProjective<Engine = Self, Base = Self::Fq, Scalar = Self::Fr, Affine = Self::G1Affine>
49        + From<Self::G1Affine>;
50
51    /// The affine representation of an element in G1.
52    type G1Affine: CurveAffine<
53            Engine = Self,
54            Base = Self::Fq,
55            Scalar = Self::Fr,
56            Projective = Self::G1,
57            Pair = Self::G2Affine,
58            PairingResult = Self::Fqk,
59        > + From<Self::G1>;
60
61    /// The projective representation of an element in G2.
62    type G2: CurveProjective<Engine = Self, Base = Self::Fqe, Scalar = Self::Fr, Affine = Self::G2Affine>
63        + From<Self::G2Affine>;
64
65    /// The affine representation of an element in G2.
66    type G2Affine: CurveAffine<
67            Engine = Self,
68            Base = Self::Fqe,
69            Scalar = Self::Fr,
70            Projective = Self::G2,
71            Pair = Self::G1Affine,
72            PairingResult = Self::Fqk,
73        > + From<Self::G2>;
74
75    /// The base field that hosts G1.
76    type Fq: PrimeField + SqrtField;
77
78    /// The extension field that hosts G2.
79    type Fqe: SqrtField;
80
81    /// The extension field that hosts the target group of the pairing.
82    type Fqk: Field;
83
84    /// Perform a miller loop with some number of (G1, G2) pairs.
85    fn miller_loop<'a, I>(i: I) -> Self::Fqk
86    where
87        I: IntoIterator<
88            Item = &'a (
89                &'a <Self::G1Affine as CurveAffine>::Prepared,
90                &'a <Self::G2Affine as CurveAffine>::Prepared,
91            ),
92        >;
93
94    /// Perform final exponentiation of the result of a miller loop.
95    fn final_exponentiation(&Self::Fqk) -> Option<Self::Fqk>;
96
97    /// Performs a complete pairing operation `(p, q)`.
98    fn pairing<G1, G2>(p: G1, q: G2) -> Self::Fqk
99    where
100        G1: Into<Self::G1Affine>,
101        G2: Into<Self::G2Affine>,
102    {
103        Self::final_exponentiation(&Self::miller_loop(
104            [(&(p.into().prepare()), &(q.into().prepare()))].iter(),
105        ))
106        .unwrap()
107    }
108
109    /// performs a pairing product operation with a single "final exponentiation"
110    fn pairing_product<G1, G2>(p1: G1, q1: G2, p2: G1, q2: G2) -> Self::Fqk
111    where
112        G1: Into<Self::G1Affine>,
113        G2: Into<Self::G2Affine>,
114    {
115        Self::final_exponentiation(&Self::miller_loop(
116            [
117                (&(p1.into().prepare()), &(q1.into().prepare())),
118                (&(p2.into().prepare()), &(q2.into().prepare())),
119            ]
120            .iter(),
121        ))
122        .unwrap()
123    }
124
125    /// performs a multi-pairing product operation with a single "final exponentiation"
126    fn pairing_multi_product(p: &[Self::G1Affine], q: &[Self::G2Affine]) -> Self::Fqk {
127        let prep_p: Vec<<Self::G1Affine as CurveAffine>::Prepared> =
128            p.iter().map(|v| v.prepare()).collect();
129        let prep_q: Vec<<Self::G2Affine as CurveAffine>::Prepared> =
130            q.iter().map(|v| v.prepare()).collect();
131        let mut pairs = Vec::with_capacity(p.len());
132        for i in 0..p.len() {
133            pairs.push((&prep_p[i], &prep_q[i]));
134        }
135        let t = Self::miller_loop(&pairs);
136        Self::final_exponentiation(&t).unwrap()
137    }
138}
139
140/// Projective representation of an elliptic curve point guaranteed to be
141/// in the correct prime order subgroup.
142pub trait CurveProjective:
143    PartialEq
144    + Eq
145    + Sized
146    + Copy
147    + Clone
148    + Send
149    + Sync
150    + fmt::Debug
151    + fmt::Display
152//    + rand::Rand
153    + 'static
154{
155    type Engine: Engine<Fr = Self::Scalar>;
156    type Scalar: PrimeField + SqrtField;
157    type Base: SqrtField;
158    type Affine: CurveAffine<Projective = Self, Scalar = Self::Scalar>;
159
160    /// Generate a random curve point.
161    fn random<R: rand_core::RngCore>(rng: &mut R)-> Self;
162
163    /// Returns the additive identity.
164    fn zero() -> Self;
165
166    /// Returns a fixed generator of unknown exponent.
167    fn one() -> Self;
168
169    /// Determines if this point is the point at infinity.
170    fn is_zero(&self) -> bool;
171
172    /// Normalizes a slice of projective elements so that
173    /// conversion to affine is cheap.
174    fn batch_normalization(v: &mut [Self]);
175
176    /// Checks if the point is already "normalized" so that
177    /// cheap affine conversion is possible.
178    fn is_normalized(&self) -> bool;
179
180    /// Doubles this element.
181    fn double(&mut self);
182
183    /// Adds another element to this element.
184    fn add_assign(&mut self, other: &Self);
185
186    /// Subtracts another element from this element.
187    fn sub_assign(&mut self, other: &Self) {
188        let mut tmp = *other;
189        tmp.negate();
190        self.add_assign(&tmp);
191    }
192
193    /// Adds an affine element to this element.
194    fn add_assign_mixed(&mut self, other: &Self::Affine);
195
196    /// Subtracts an affine element from this element
197    fn sub_assign_mixed(&mut self, other: &Self::Affine) {
198        let mut tmp = *other;
199        tmp.negate();
200        self.add_assign_mixed(&tmp);
201    }
202
203    /// Negates this element.
204    fn negate(&mut self);
205
206    /// Performs scalar multiplication of this element.
207    fn mul_assign<S: Into<<Self::Scalar as PrimeField>::Repr>>(&mut self, other: S);
208
209    /// Converts this element into its affine representation.
210    fn into_affine(&self) -> Self::Affine;
211
212    /// Recommends a wNAF window table size given a scalar. Always returns a number
213    /// between 2 and 22, inclusive.
214    fn recommended_wnaf_for_scalar(scalar: <Self::Scalar as PrimeField>::Repr) -> usize;
215
216    /// Recommends a wNAF window size given the number of scalars you intend to multiply
217    /// a base by. Always returns a number between 2 and 22, inclusive.
218    fn recommended_wnaf_for_num_scalars(num_scalars: usize) -> usize;
219
220    /// Borrow references to the X, Y, and Z coordinates of this point.
221    fn as_tuple(&self) -> (&Self::Base, &Self::Base, &Self::Base);
222
223    /// Borrow mutable references to the X, Y, and Z coordinates of this point.
224    /// Unsafe, because incorrectly modifying the coordinates violates the guarantee
225    /// that the point must be on the curve and in the correct subgroup.
226    unsafe fn as_tuple_mut(&mut self) -> (&mut Self::Base, &mut Self::Base, &mut Self::Base);
227
228    // /// multiplication with shamir's Trick
229    // /// compute s1 * p1 + s2 * p2 simultaneously
230    // fn mul_shamir<S: Into<<Self::Scalar as PrimeField>::Repr>>(
231    //     p1: Self,
232    //     p2: Self,
233    //     s1: S,
234    //     s2: S,
235    // ) -> Self;
236}
237
238/// Affine representation of an elliptic curve point guaranteed to be
239/// in the correct prime order subgroup.
240pub trait CurveAffine:
241    Copy + Clone + Sized + Send + Sync + fmt::Debug + fmt::Display + PartialEq + Eq + 'static
242{
243    type Engine: Engine<Fr = Self::Scalar>;
244    type Scalar: PrimeField + SqrtField;
245    type Base: SqrtField;
246    type Projective: CurveProjective<Affine = Self, Scalar = Self::Scalar>;
247    type Prepared: Clone + Send + Sync + 'static;
248    type Uncompressed: EncodedPoint<Affine = Self>;
249    type Compressed: EncodedPoint<Affine = Self>;
250    type Pair: CurveAffine<Pair = Self>;
251    type PairingResult: Field;
252
253    /// Returns the additive identity.
254    fn zero() -> Self;
255
256    /// Returns a fixed generator of unknown exponent.
257    fn one() -> Self;
258
259    /// Determines if this point represents the point at infinity; the
260    /// additive identity.
261    fn is_zero(&self) -> bool;
262
263    /// Negates this element.
264    fn negate(&mut self);
265
266    /// Performs scalar multiplication of this element with mixed addition.
267    fn mul<S: Into<<Self::Scalar as PrimeField>::Repr>>(&self, other: S) -> Self::Projective;
268
269    /// Prepares this element for pairing purposes.
270    fn prepare(&self) -> Self::Prepared;
271
272    /// Perform a pairing
273    fn pairing_with(&self, other: &Self::Pair) -> Self::PairingResult;
274
275    /// Converts this element into its affine representation.
276    fn into_projective(&self) -> Self::Projective;
277
278    /// Converts this element into its compressed encoding, so long as it's not
279    /// the point at infinity.
280    fn into_compressed(&self) -> Self::Compressed {
281        <Self::Compressed as EncodedPoint>::from_affine(*self)
282    }
283
284    /// Converts this element into its uncompressed encoding, so long as it's not
285    /// the point at infinity.
286    fn into_uncompressed(&self) -> Self::Uncompressed {
287        <Self::Uncompressed as EncodedPoint>::from_affine(*self)
288    }
289
290    /// Borrow references to the X and Y coordinates of this point.
291    fn as_tuple(&self) -> (&Self::Base, &Self::Base);
292
293    /// Borrow mutable references to the X and Y coordinates of this point.
294    /// Unsafe, because incorrectly modifying the coordinates violates the guarantee
295    /// that the point must be on the curve and in the correct subgroup.
296    unsafe fn as_tuple_mut(&mut self) -> (&mut Self::Base, &mut Self::Base);
297
298    /// given x, compute x^3+b
299    //    fn rhs_g1(x: &bls12_381::Fq) -> bls12_381::Fq;
300
301    /// multiplication of many points
302    /// compute s1 * p1 + ... + sn * pn simultaneously
303    fn sum_of_products(bases: &[Self], scalars: &[&[u64; 4]]) -> Self::Projective;
304
305    /// Find the optimal window for running Pippinger's algorithm; preprogrammed values
306    fn find_pippinger_window(num_components: usize) -> usize;
307
308    /// Find the optimal window for running Pippinger's algorithm; computed values via an estimate of running time
309    fn find_pippinger_window_via_estimate(num_components: usize) -> usize;
310
311    /// multiplication of many points with Pippinger's algorithm of window size w
312    /// compute s1 * p1 + ... + sn * pn simultaneously
313    fn sum_of_products_pippinger(
314        bases: &[Self],
315        scalars: &[&[u64; 4]],
316        window: usize,
317    ) -> Self::Projective;
318
319    /// multiplication of many points with precompuation
320    /// compute s1 * p1 + ... + sn * pn simultaneously
321    /// assuming  pre[j*256+i] = (\sum_{b such that bth bit of i is 1} 2^{32i}) * bases[j] for each j and i in 0..256
322    fn sum_of_products_precomp_256(
323        bases: &[Self],
324        scalars: &[&[u64; 4]],
325        pre: &[Self],
326    ) -> Self::Projective;
327
328    /// pre[0] becomes (2^64) * self, pre[1]  becomes (2^128) * self, and pre[2] (becomes 2^196) * self
329    fn precomp_3(&self, pre: &mut [Self]);
330
331    /// Performs scalar multiplication of this element,
332    /// assuming pre = [(2^64)*self, (2^128)*self, (2^192)*self]
333    fn mul_precomp_3<S: Into<<Self::Scalar as PrimeField>::Repr>>(
334        &self,
335        other: S,
336        pre: &[Self],
337    ) -> Self::Projective;
338
339    /// pre[i] becomes (\sum_{b such that bth bit of i is 1} 2^{32i}) * self for i in 0..25
340    fn precomp_256(&self, pre: &mut [Self]);
341
342    /// Performs scalar multiplication of this element,
343    /// assuming  pre[i] = (\sum_{b such that bth bit of i is 1} 2^{32i}) * self for i in 0..256
344    fn mul_precomp_256<S: Into<<Self::Scalar as PrimeField>::Repr>>(
345        &self,
346        other: S,
347        pre: &[Self],
348    ) -> Self::Projective;
349}
350
351/// An encoded elliptic curve point, which should essentially wrap a `[u8; N]`.
352pub trait EncodedPoint:
353    Sized + Send + Sync + AsRef<[u8]> + AsMut<[u8]> + Clone + Copy + 'static
354{
355    type Affine: CurveAffine;
356
357    /// Creates an empty representation.
358    fn empty() -> Self;
359
360    /// Returns the number of bytes consumed by this representation.
361    fn size() -> usize;
362
363    /// Converts an `EncodedPoint` into a `CurveAffine` element,
364    /// if the encoding represents a valid element.
365    fn into_affine(&self) -> Result<Self::Affine, GroupDecodingError>;
366
367    /// Converts an `EncodedPoint` into a `CurveAffine` element,
368    /// without guaranteeing that the encoding represents a valid
369    /// element. This is useful when the caller knows the encoding is
370    /// valid already.
371    ///
372    /// If the encoding is invalid, this can break API invariants,
373    /// so caution is strongly encouraged.
374    fn into_affine_unchecked(&self) -> Result<Self::Affine, GroupDecodingError>;
375
376    /// Creates an `EncodedPoint` from an affine point, as long as the
377    /// point is not the point at infinity.
378    fn from_affine(affine: Self::Affine) -> Self;
379}
380
381pub trait SubgroupCheck {
382    /// subgroup membership check using classical method:
383    /// i.e., raise to the power of group order
384    fn in_subgroup(&self) -> bool;
385}
386
387/// An error that may occur when trying to decode an `EncodedPoint`.
388#[derive(Debug)]
389pub enum GroupDecodingError {
390    /// The coordinate(s) do not lie on the curve.
391    NotOnCurve,
392    /// The element is not part of the r-order subgroup.
393    NotInSubgroup,
394    /// One of the coordinates could not be decoded
395    CoordinateDecodingError(&'static str, PrimeFieldDecodingError),
396    /// The compression mode of the encoded element was not as expected
397    UnexpectedCompressionMode,
398    /// The encoding contained bits that should not have been set
399    UnexpectedInformation,
400}
401
402impl Error for GroupDecodingError {
403    fn description(&self) -> &str {
404        match *self {
405            GroupDecodingError::NotOnCurve => "coordinate(s) do not lie on the curve",
406            GroupDecodingError::NotInSubgroup => "the element is not part of an r-order subgroup",
407            GroupDecodingError::CoordinateDecodingError(..) => "coordinate(s) could not be decoded",
408            GroupDecodingError::UnexpectedCompressionMode => {
409                "encoding has unexpected compression mode"
410            }
411            GroupDecodingError::UnexpectedInformation => "encoding has unexpected information",
412        }
413    }
414}
415
416impl fmt::Display for GroupDecodingError {
417    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
418        match *self {
419            GroupDecodingError::CoordinateDecodingError(description, ref err) => {
420                write!(f, "{} decoding error: {}", description, err)
421            }
422            _ => write!(f, "{}", self.to_string()),
423        }
424    }
425}
pairing_plus/lib.rs

pairing_plus/
lib.rs
