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);