Introduction to arkworks algebra APIs

The arkworks ecosystem is a set of state-of-the-art Rust libraries that collectively provide tools to program zkSNARKs. zkHack puzzles will be using arkworks libraries for elliptic curve and finite field arithmetic. This document is a helpful cheat-sheet to get started with using these libraries.

Finite field arithmetic

There are three important traits when working with finite fields: [Field], [SquareRootField], and [PrimeField]. Let's explore these via examples.

[Field]

The [Field] trait provides a generic interface for any finite field. Types implementing [Field] support common field operations such as addition, subtraction, multiplication, and inverses.

use ark_ff::Field;
// We'll use a field associated with the BLS12-381 pairing-friendly
// group for this example.
use ark_bls12_381::Fq2 as F;
// `ark-std` is a utility crate that enables `arkworks` libraries
// to easily support `std` and `no_std` workloads, and also re-exports
// useful crates that should be common across the entire ecosystem, such as `rand`.
use ark_std::{One, UniformRand};

let mut rng = ark_std::rand::thread_rng();
// Let's sample uniformly random field elements:
let a = F::rand(&mut rng);
let b = F::rand(&mut rng);

// We can add...
let c = a + b;
// ... subtract ...
let d = a - b;
// ... double elements ...
assert_eq!(c + d, a.double());

// ... multiply ...
let e = c * d;
// ... square elements ...
assert_eq!(e, a.square() - b.square());

// ... and compute inverses ...
assert_eq!(a.inverse().unwrap() * a, F::one()); // have to to unwrap, as `a` could be zero.

[SquareRootField]

In some cases, it is important to take square roots of field elements (e.g.: for point compression of elliptic curve elements.) To support this, users can implement the [SquareRootField] trait for their field type. This provides access to the following methods:

use ark_ff::{Field, SquareRootField};
// As before, we'll use a field associated with the BLS12-381 pairing-friendly
// group for this example.
use ark_bls12_381::Fq2 as F;
use ark_std::{One, UniformRand};

let mut rng = ark_std::rand::thread_rng();
// Let's try to sample a random square via rejection sampling:
let mut a = F::rand(&mut rng);
while a.legendre().is_qnr() { // A square is also called a *quadratic residue*
    a = F::rand(&mut rng);
}

// Since `a` is a square, we can compute its square root:
let b = a.sqrt().unwrap();
assert_eq!(b.square(), a);

// Let's sample a random *non-square*
let mut a = F::rand(&mut rng);
while a.legendre().is_qr() {
    a = F::rand(&mut rng);
}
// The square root should not exist:
assert_eq!(a.sqrt(), None);

[PrimeField]

If the field is of prime order, then users can choose to implement the [PrimeField] trait for it. This provides access to the following additional APIs:

use ark_ff::{Field, PrimeField, FpParameters, BigInteger};
// Now we'll use the prime field underlying the BLS12-381 G1 curve.
use ark_bls12_381::Fq as F;
use ark_std::{One, Zero, UniformRand};

let mut rng = ark_std::rand::thread_rng();
let a = F::rand(&mut rng);
// We can access the prime modulus associated with `F`:
let modulus = <F as PrimeField>::Params::MODULUS;
assert_eq!(a.pow(&modulus), a);

// We can convert field elements to integers in the range [0, MODULUS - 1]:
let one: num_bigint::BigUint = F::one().into();
assert_eq!(one, num_bigint::BigUint::one());

// We can construct field elements from an arbitrary sequence of bytes:
let n = F::from_le_bytes_mod_order(&modulus.to_bytes_le());
assert_eq!(n, F::zero());

Elliptic curve arithmetic

There are two traits that are important when working with elliptic curves over finite fields: [ProjectiveCurve], and [AffineCurve]. Both traits represent the same curve, but provide different underlying representations. In particular, a [ProjectiveCurve] representation of a curve point is generally more efficient for arithmetic, but does not provide a unique representative for a curve point. An [AffineCurve] 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::{ProjectiveCurve, AffineCurve};
use ark_ff::{PrimeField, Field};
// We'll use the BLS12-381 G1 curve for this example.
use ark_bls12_381::{G1Projective as G, G1Affine as GAffine, Fr as ScalarField};
use ark_std::{Zero, UniformRand};

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

// We can add...
let c = a + b;
// ... subtract ...
let d = a - b;
// ... and double elements.
assert_eq!(c + d, a.double());
// We can also negate elements...
let e = -a;
assert_eq!(e + a, G::zero());

// ...and multiply group elements by elements of the corresponding scalar field
let scalar = ScalarField::rand(&mut rng);
let e = c.mul(&scalar.into_repr()); // into_repr() converts the scalar into a `BigInteger`.
let f = e.mul(&scalar.inverse().unwrap().into_repr());
assert_eq!(f, c);

// Finally, we can also convert curve points in projective coordinates to affine coordinates.
let c_aff = c.into_affine();
// Most group operations are slower in affine coordinates, but adding an affine point
// to a projective one is slightly more efficient.
let d = c.add_mixed(&c_aff);
assert_eq!(d, c.double());

// This efficiency also translates into more efficient scalar multiplication routines.
let e_from_aff = c_aff.mul(scalar.into_repr());
assert_eq!(e, e_from_aff);

// Finally, while not recommended, users can directly construct group elements
// from the x and y coordinates. This is useful when implementing algorithms
// like hash-to-curve.
let e_affine = e.into_affine();
let e_x = e_affine.x;
let e_y = e_affine.y;
let is_at_infinity = e_affine.is_zero();
let new_e = GAffine::new(e_x, e_y, is_at_infinity);
assert_eq!(e_affine, new_e);
// Users should check that the new point is on the curve and is in the prime-order group:
assert!(new_e.is_on_curve());
assert!(new_e.is_in_correct_subgroup_assuming_on_curve());

Pairings

[PairingEngine] is the primary trait for working with pairings. It contains associated types and methods that are relevant to pairing operations:

use ark_ec::{ProjectiveCurve, AffineCurve, PairingEngine};
use ark_ff::{PrimeField, Field};
// We'll use the BLS12-381 pairing-friendly group for this example.
use ark_bls12_381::{Bls12_381, G1Projective as G1, G2Projective as G2, G1Affine, G2Affine, Fr as ScalarField};
use ark_std::{Zero, UniformRand};

let mut rng = ark_std::rand::thread_rng();
// Let's sample uniformly random field elements:
let a: G1Affine = G1::rand(&mut rng).into();
let b: G2Affine = G2::rand(&mut rng).into();
// We can compute the pairing of `a` and `b`:
let c = Bls12_381::pairing(a, b);

// We can also compute the pairing partwise:
// First, we compute the Miller loop:
let c_ml = Bls12_381::miller_loop(&[(a.into(), b.into())]);
let c_fe = Bls12_381::final_exponentiation(&c_ml).unwrap();
assert_eq!(c, c_fe);

Serialization

Most types in the arkworks ecosystem implement the [CanonicalSerialize] and [CanonicalDeserialize] traits. These traits enable converting these types to canonical byte representations that are suitable for disk storage and network communication. They also enable support for point compression.

use ark_ec::AffineCurve;
// We'll use the BLS12-381 pairing-friendly group for this example.
use ark_bls12_381::{G1Projective as G1, G2Projective as G2, G1Affine, G2Affine};
use ark_serialize::{CanonicalSerialize, CanonicalDeserialize};
use ark_std::UniformRand;

let mut rng = ark_std::rand::thread_rng();
// Let's sample uniformly random field elements:
let a: G1Affine = G1::rand(&mut rng).into();
let b: G2Affine = G2::rand(&mut rng).into();

// We can serialize with compression...
let mut compressed_bytes = Vec::new();
a.serialize(&mut compressed_bytes).unwrap();
// ...and without:
let mut uncompressed_bytes = Vec::new();
a.serialize_uncompressed(&mut uncompressed_bytes).unwrap();

// We can reconstruct our points from the compressed serialization...
let a_compressed = G1Affine::deserialize(&*compressed_bytes).unwrap();

// ... and from the uncompressed one:
let a_uncompressed = G1Affine::deserialize_uncompressed(&*uncompressed_bytes).unwrap();

assert_eq!(a_compressed, a);
assert_eq!(a_uncompressed, a);

// If we trust the origin of the serialization
// (eg: if the serialization was stored on authenticated storage),
// then we can skip some validation checks:
let a_unchecked = G1Affine::deserialize_unchecked(&*uncompressed_bytes).unwrap();
assert_eq!(a_unchecked, a);