Table of Contents
The key idea of algebra
is to provide usefull interfaces for basic cryptography math. It's based on NilFoundation fork of Boost.Multiprecision so that it can be used with boost cpp_int, gmp or other backends.
We expanded Boost.Multiprecision with modular_adaptor
, which is actually a multi-precision number by some modular. It contains modular number-specific algorithms using Montgomery representation. It also supports compile-time computations, because it gives us opportunity to implement algebra constructions as constexpr.
For our purposes we needed the opportunity to use field and curve arithmetic in compile time, what became possible thanks to compile-time modular_adaptor
.
Algebra library consists of several modules listed below:
- Fields arithmetic
- Elliptic curves arithmetic
- Pairings on elliptic curves
- Multiexponentiation algorithm (will be part of some other module after a while)
- Matricies and vectors
This separation defines the implementation architecture.
Fields Architecture
Fields were meant to be a wrapper over multiprecision
module and concept of modular_adaptor
number. So it basically consist of several parts listed below:
- Field Policies
- Field Extensions (e.g. Fp2, Fp4)
- Field Parameters
- Field Element Algorithms, which are actually wrappers over the
multiprecision
operations.
Field Policies
A field policy describes its essential parameters such as modulus
, arity
or mul_generator
- multiply generator.
Field Extensions
For the purposes of effictive field/elliptic curve operations and pairings evaluation fields are arranged as a field tower.
For example, this is the tower used for bn128
and bls12_381
operations and pairings evaluation:
Fp -> Fp2 -> Fp6 -> Fp12;
There are also the following towers implemented:
Fp -> Fp3 -> Fp6 -> Fp12;
Fp -> Fp2 -> Fp4 -> Fp12;
Field Parameters
Other field parameters are kept in the specific structures. All this structures inherit from basic params
structure, containing all the basic parameters.
For example, extension_params
structure keeps all the parameters needed for field and field extensions arithmetical operation evaluations.
Field Element Algorithms
Field element corresponds an element of the field and has all the needed methods and overloaded arithmetic operators. The corresponding algorithms are also defined here. As the backend they use now Boost::multiprecision, but it can be easily changed.
Elliptic Curves Architecture
Curves were build upon the fields
. So it basically consist of several parts listed below:
- Curve Policies
- Curve g1, g2 group element arithmetic
- Basic curve policies
Curve Policies
A curve policy describes its parameters such as base field modulus p
, scalar field modulus q
, group element types g1_type
and g2_type
. It also contains pairing_policy
type, needed for comfortable usage of curve pairing.
Curve Element Algorithms
Curve element corresponds an point of the curve and has all the needed methods and overloaded arithmetic operators. The corresponding algorithms are based on the underlying field algorithms are also defined here.
Basic Curve Policies
Main reason for existence of basic policyis is that we need some of it params using in group element and pairing arithmetic. So it contains such parameters that are needed by group element arithmetic e.g. coeffs a
and b
or generator coordinates x
, y
. It also contains all needed information about the underlying fields.
Pairing Architecture
Pairing module consist of some internal functions and frontend interface templated by Elliptic Curve.