Pairing on the BLS12-381 Elliptic Curve

This library is a simple and self-contained Haskell implementation of pairing operations over the BLS12-381 elliptic curve. It contains prime-extension finite-field arithmetic arranged in a tower (Fq1, Fq2, Fq6 and Fq12), the group law for both curve groups in affine coordinates with the sextic twist, and culminates in the Ate pairing via a Miller loop. This pairing is used in the IETF CFRG draft specification for BLS signatures at draft-irtf-cfrg-bls-signatures

Please note: This code is for experimental purposes and is not suitable for production. While a limited testing infrastructure is provided, the code may be incomplete, inefficient, incorrect and/or insecure. Specifically, both the point arithmetic algorithms within the code and the use of Haskell's big integers are not constant-time and thus introduce timing side channels.

This code has not undergone a security audit; use at your own risk.

The primary logic resides in Crypto/Pairing_bls12381.hs and strongly prefers simplicity over raw performance.

Quick start

After installing Stack, getting started is extremely simple and fast:

$ git clone https://github.com/nccgroup/pairing-bls12381.git
$ cd ./pairing-bls12381
$ stack test

    pairing-bls12381> test (suite: pairing-bls12381-test)

    Running Tests
      huTstSmokeTest:  OK (1.99s)
      huTstCurve:      OK (0.76s)
      huTstPairingPts: OK (1.53s)
      huTstPairingMul: OK (2.25s)
      huTstPairingGen: OK (9.59s)

    All 5 tests passed (9.59s)

    pairing-bls12381> Test suite pairing-bls12381-test passed

As expected, stack haddock will generate local documentation and stack run will execute app/Main.hs which performs 100 pairings and 30 pointMuls (as a demo).

Example usage

Let's demonstrate the following equality (note the constants shifting positions):

pairing((12+34)*56*g1, 78*g2) == pairing(78*g1, 12*56*g2) * pairing(78*g1, 34*56*g2)

... where g1 and g2 are group generators. Below is an example ghci interpreter session.

$ ghci Crypto/Pairing_bls12381.hs

*Pairing_bls12381> p_12p34m56 = g1Generator >>= pointMul ((12 + 34) * 56)
*Pairing_bls12381> q_78 = g2Generator >>= pointMul 78
*Pairing_bls12381> leftSide = pairing <$> p_12p34m56 <*> q_78 >>= id
*Pairing_bls12381>
*Pairing_bls12381> p_78 = g1Generator >>= pointMul 78
*Pairing_bls12381> q_12m56 = g2Generator >>= pointMul (12 * 56)
*Pairing_bls12381> q_34m56 = g2Generator >>= pointMul (34 * 56)
*Pairing_bls12381> pair2 = pairing <$> p_78 <*> q_12m56 >>= id
*Pairing_bls12381> pair3 = pairing <$> p_78 <*> q_34m56 >>= id
*Pairing_bls12381> rightSide = (*) <$> pair2 <*> pair3
*Pairing_bls12381>
*Pairing_bls12381> (==) <$> leftSide <*> rightSide
Just True

Straightforward API

The general flow is to first generate two pairs of points. Each pair consists of one point from group 1 and another point from group 2. Then, each pair is supplied to the pairing function and the results are compared for equality. It is possible to perform interesting operations 'within the scalars' of each point as well as multiply pairing results as demonstrated by the example above. Aggregate BLS signatures utilize pointAdd and the multiply operator. Additional examples can be found in ./test/Test.hs.

Points are typically generated by either using pointMul on a scalar and the desired group generator, or by constructing the point directly with g1Point or g2Point. The returned points are validated to be on-curve.

g1Point :: Integer -> Integer -> Maybe (Point Fq1)
Given x and y, construct a valid point contained in G1.

g2Point :: Integer -> Integer -> Integer -> Integer -> Maybe (Point Fq2)
Given xu, x, yu and y (where u^2 = -1), construct a valid point contained in G2.

g1Generator :: Maybe (Point Fq1)
The standard generator point for G1.

g2Generator :: Maybe (Point Fq2)
The standard generator point for G2.

pointAdd :: (Field a, Eq a) => Point a -> Point a -> Point a
Add affine curve points; handle all corner cases. This is sufficient for supporting aggregate BLS signatures. A broader API for more elaborate point arithmetic is to do.

pointMul :: (Field a, Eq a) => Integer -> Point a -> Maybe (Point a)
Multiply an integer scalar and a valid point in either G1 or G2.

pairing :: Point Fq1 -> Point Fq2 -> Maybe Fq12
Pairing calculation for a valid point in G1 and another valid point in G2.

fieldPrime :: Integer
The field prime constant used in BLS12-381 is exported for reference.

groupOrder :: Integer
The group order constant of BLS12-381 is exported for reference.

smokeTest :: Bool
A quick test of externally inaccessible functionality; returns success.

References

• Pairings for beginners, Craig Costello, http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf
• On the Implementation of Pairing-Based Cryptography, Ben Lynn PhD Dissertation, https://crypto.stanford.edu/pbc/thesis.html
• BLS12-381: New zk-SNARK Elliptic Curve Construction, Sean Bowe of Zcash, https://electriccoin.co/blog/new-snark-curve/
• BLS12-381 For The Rest Of Us, Ben Edgington, https://hackmd.io/@benjaminion/bls12-381
• Pairing-Friendly Curves, draft-irtf-cfrg-pairing-friendly-curves-04, https://datatracker.ietf.org/doc/draft-irtf-cfrg-pairing-friendly-curves/
• Constructing Tower Extensions of Finite Fields for Implementation of Pairing-Based Cryptography, Naomi Benger and Michael Scott, https://eprint.iacr.org/2009/556.pdf

Copyright (c) 2020 Eric Schorn, NCC Group Plc; Provided under the BSD-3 License.