#elliptic-curve #pairing

no-std ark-ec

A library for elliptic curves and pairings

15 releases

0.5.0 Oct 28, 2024
0.5.0-alpha.0 Jun 20, 2024
0.4.2 Mar 18, 2023
0.4.0-alpha.7 Dec 29, 2022
0.2.0 Mar 24, 2021

#10 in Cryptography

Download history 111796/week @ 2024-08-21 122019/week @ 2024-08-28 128875/week @ 2024-09-04 114163/week @ 2024-09-11 261826/week @ 2024-09-18 274189/week @ 2024-09-25 628073/week @ 2024-10-02 663179/week @ 2024-10-09 626080/week @ 2024-10-16 177882/week @ 2024-10-23 142781/week @ 2024-10-30 131334/week @ 2024-11-06 131724/week @ 2024-11-13 134304/week @ 2024-11-20 132307/week @ 2024-11-27 163975/week @ 2024-12-04

586,836 downloads per month
Used in 2,167 crates (171 directly)

MIT/Apache

1MB
18K SLoC

ark-ec

ark-ec defines traits and algorithms for working with different kinds of additive groups, with a focus on groups arising from elliptic curves. It further provides concrete instantiations of these traits for various elliptic curve models, including popular families of pairing-friendly curves such as the BLS12 family of curves. Implementations of particular curves using these curve models can be found in arkworks-rs/curves.

Usage

The Group trait

Many cryptographic protocols use as core building-blocks prime-order groups. The PrimeGroup trait is an abstraction that represents elements of such abelian prime-order groups. It provides methods for performing common operations on group elements:

use ark_ec::{AdditiveGroup, PrimeGroup};
use ark_ff::{PrimeField, Field};
// We'll use the BLS12-381 G1 curve for this example.
// This group has a prime order `r`, and is associated with a prime field `Fr`.
use ark_test_curves::bls12_381::{G1Projective as G, Fr as ScalarField};
use ark_std::{Zero, UniformRand, ops::Mul};

let mut rng = ark_std::test_rng();
// Let's sample uniformly random group elements:
let a = G::rand(&mut rng);
let b = G::rand(&mut rng);

// We can add elements, ...
let c = a + b;
// ... subtract them, ...
let d = a - b;
// ... and double them.
assert_eq!(c + d, a.double());
// We can also negate elements, ...
let e = -a;
// ... and check that negation satisfies the basic group law
assert_eq!(e + a, G::zero());

// We can also multiply group elements by elements of the corresponding scalar field
// (an act known as *scalar multiplication*)
let scalar = ScalarField::rand(&mut rng);
let e = c.mul(scalar);
let f = e.mul(scalar.inverse().unwrap());
assert_eq!(f, c);

Scalar multiplication

While the PrimeGroup trait already produces scalar multiplication routines, in many cases one can take advantage of the group structure to perform scalar multiplication more efficiently. To allow such specialization, ark-ec provides the ScalarMul and VariableBaseMSM traits. The latter trait computes an "inner product" between a vector of scalars s and a vector of group elements g. That is, it computes s.iter().zip(g).map(|(s, g)| g * s).sum().

use ark_ec::{PrimeGroup, VariableBaseMSM};
use ark_ff::{PrimeField, Field};
// We'll use the BLS12-381 G1 curve for this example.
// This group has a prime order `r`, and is associated with a prime field `Fr`.
use ark_test_curves::bls12_381::{G1Projective as G, G1Affine as GAffine, Fr as ScalarField};
use ark_std::{Zero,  UniformRand};

let mut rng = ark_std::test_rng();
// Let's sample uniformly random group elements:
let a = GAffine::rand(&mut rng);
let b = GAffine::rand(&mut rng);

let s1 = ScalarField::rand(&mut rng);
let s2 = ScalarField::rand(&mut rng);

// Note that we're using the `GAffine` type here, as opposed to `G`.
// This is because MSMs are more efficient when the group elements are in affine form. (See below for why.)
//
// The `VariableBaseMSM` trait allows specializing the input group element representation to allow
// for more efficient implementations.
let r = G::msm(&[a, b], &[s1, s2]).unwrap();
assert_eq!(r, a * s1 + b * s2);

Elliptic curve groups

There are two traits that are important when working with elliptic curves over finite fields: CurveGroup, and AffineRepr. Both traits represent elements of the same curve, but provide different underlying representations. In particular, the CurveGroup representation of a curve point is generally more efficient for arithmetic, but does not provide a unique representative for a curve point. An AffineRepr representation, on the other hand, is unique, but is slower for most arithmetic operations. Let's explore how and when to use these:

use ark_ec::{AdditiveGroup, AffineRepr, PrimeGroup, CurveGroup, VariableBaseMSM};
use ark_ff::{PrimeField, Field};
use ark_test_curves::bls12_381::{G1Projective as G, G1Affine as GAffine, Fr as ScalarField};
use ark_std::{Zero, UniformRand};

let mut rng = ark_std::test_rng();
// Let's generate an elliptic curve group element in the `CurveGroup` representation
let a = G::rand(&mut rng);
// We can convert it the `AffineRepr` representation...
let a_aff = a.into_affine();
// ... and check that the two representations are equal.
assert_eq!(a_aff, a);
// We can also convert back to the `CurveGroup` representation:
assert_eq!(a, a_aff.into_group());

// As a general rule, most group operations are slower when elements
// are represented as `AffineRepr`. However, adding an `AffineRepr`
// point to a `CurveGroup` one is usually slightly more efficient than
// adding two `CurveGroup` points.
let d = a + a_aff;
assert_eq!(d, a.double());

// This efficiency also translates into more efficient scalar multiplication routines.
let scalar = ScalarField::rand(&mut rng);
let mul_result = a_aff * scalar;
assert_eq!(a * scalar, mul_result);

// Finally, while not recommended, users can directly construct group elements
// from the x and y coordinates of the curve points. This is useful when implementing algorithms
// like hash-to-curve.
let a_x = a_aff.x;
let a_y = a_aff.y;
let is_at_infinity = a_aff.is_zero();
// This check ensures that `new_a` is indeed in the curve group, and in particular
// is within the prime-order group.
let new_a = GAffine::new(a_x, a_y);
assert_eq!(a_aff, new_a);
assert!(new_a.is_on_curve());
assert!(new_a.is_in_correct_subgroup_assuming_on_curve());

Besides the foregoing abstract interfaces for elliptic curve groups, ark-ec also provides the following concrete instantiations of common elliptic curve models:

Pairings

Pairing is a trait that defines the interface for a pairing-friendly elliptic curve. Besides the general interface, we provide concrete instantiations of popular pairing-friendly families of curves, such as the Barreto-Lynn-Scott and Barreto-Naehrig families.

use ark_ec::{pairing::Pairing, AffineRepr};
use ark_ff::Field;
use ark_std::UniformRand;

use ark_test_curves::bls12_381::{Bls12_381, G1Projective as G1, G2Projective as G2, Fq12 as Fq12};
use ark_test_curves::bls12_381::Fr as ScalarField;

// The pairing engine is parameterized by the scalar field of the curve.
let mut rng = ark_std::test_rng();
let s = ScalarField::rand(&mut rng);
let a = G1::rand(&mut rng);
let b = G2::rand(&mut rng);

// We can compute the pairing of two points on the curve, either monolithically...
let e1 = Bls12_381::pairing(a, b);
// ... or in two steps. First, we compute the Miller loop...
let ml_result = Bls12_381::miller_loop(a, b);
// ... and then the final exponentiation.
let e2 = Bls12_381::final_exponentiation(ml_result).unwrap();
assert_eq!(e1, e2);

Hash-to-group

ark-ec also provides traits for hashing to elliptic curve groups. The HashToCurve trait allows users to hash arbitrary byte strings to elliptic curve group elements, and allows using different hashing strategies.

Dependencies

~3–4.5MB
~83K SLoC