Home

Awesome

High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves

This library provides functionality to compute the optimal ate pairing over Barreto-Naehrig (BN) curves. It is released under the BSD 3-Clause License.

Now I'm developing a new pairing library mcl, which is more portable and supports larger primes than this library though it is a little slower.

History

Overview

The following two BN curves are supported:

  1. a BN curve over the 254-bit prime p = 36z^4 + 36z^3 + 24z^2 + 6z + 1 where z = -(2^62 + 2^55 + 1); and
  2. a BN curve over a 254-bit prime p such that n := p + 1 - t has high 2-adicity.

By default, the first curve (we call it as CurveFp254BNb) is used; when setting the flag SUPPORT_SNARK, the second curve (we call it as CurveSNARK) is used instead.

Pairing computations on the first curve are more efficient, and the performance numbers reported below (and in our papers) are achieved using this curve (which is prefered for applications that do not benefit from high 2-adicity). Note that the old parameters in [BDMOHT] are not used now.

Parameters

The curve equation for a BN curve is:

E/Fp: y^2 = x^3 + b .

The two supported BN curves have the following parameters:

  1. b = 2 and p = 16798108731015832284940804142231733909889187121439069848933715426072753864723; and
  2. b = 3 and p = 21888242871839275222246405745257275088696311157297823662689037894645226208583.

As usual,

The field Fp12 is constructed via the following tower:

Requirements

Build instructions

Windows

> git clone git://github.com/herumi/xbyak.git
> git clone git://github.com/herumi/ate-pairing.git
> git clone git://github.com/herumi/cybozulib-ext.git ; compiled binary of mpir

Open ate/ate.sln and compile test_bn with Release mode. The produced binary is ate/x64/Release/test_bn.exe.

Cygwin

Install mingw64-x86_64-gcc-g++ (run Cygwin setup and search mingw64). Then use the following commands:

PATH=/usr/x86_64-w64-mingw32/sys-root/mingw/bin/:$PATH
make -j
test/bn.exe

Note that test/bn.exe uses mulx if possible; if you do not want to use it, run the executable as test/bn.exe -mulx 0. (This allows you to verify the difference with/without mulx on Haswell.)

Linux

Use the following commands:

$ git clone git://github.com/herumi/xbyak.git
$ git clone git://github.com/herumi/ate-pairing.git
$ cd ate-pairing
$ make -j
$ test/bn

The library xbyak is a x86/x86-64 JIT assembler for C++, developed for efficient pairing implementations. (See also this webpage.) Note that binaries other than test/bn are used for testing purposes only.

By the default, the first BN curve is used. If instead you want to use the second BN curve (specialized to SNARKs), modify the fourth line above to:

$ make -j SUPPORT_SNARK=1

Usage

See the function sample2() in sample.cpp. Also, use can use mpz_class for scalar multiplication of points on the elliptic curves, if MIE_ATE_USE_GMP is defined. For instance:

using namespace bn;
Param::init();
const Ec2 g2(...);
const Ec1 g1(...);
mpz_class a("123456789");
mpz_class b("98765432");
Ec1 g1a = g1 * a;
Ec2 g2b = g2 * b;
Fp12 e;
opt_atePairing(e, g2b, g1a);

Usage for Java

See java.md. A sample code is BN254Test.java.

Operation costs

Let mu be the cost of unreduced multiplication producing double-precision result (i.e., 256-bit int x 256-bit int to 512-bit int); and let r be the cost of modular reduction of double-precision integers (i.e., 512-bit int to 256-bit int in Fp). Then, for us,

Next, we compare the costs of our library with the one of [AKLGL10]:

Phase[AKLGL10]This work
Miller loop6792mu + 3022r6785mu + 3022r
Final exponentiation3753mu + 2006r3526mu + 1932r
Optimal ate pairing10545mu + 5028r10311mu + 4954r

Note: [Table 2 in p. 17, AKLGL10] does not contain the cost of (m, r) so we have added the costs of (282m + 6mu + 4r) and (30m + 75mu + 50r) to ML and FE respectively.

Finally, at the moment, our implementation does not support the algorithm in PSNB10.

Benchmark

The cost of a pairing is 1.17M clock cycles on Core i7 4700MQ (Haswell) 2.4GHz processor with TurboBoost disabled. Below, we also include clock cycle counts on Core i7 2600 3.4GHz, Xeon X5650 2.6GHz, and Core i7 4700MQ 2.4GHz. The formal benchmark is written in [ZPMRTH].

% sudo sh -c "echo 0 > /sys/devices/system/cpu/cpufreq/boost"
% cat /sys/devices/system/cpu/cpufreq/boost
0
operationi7 2600Xeon X5650HaswellHaswell with mulx
TurboBoostononoffoff
mu50604238
r80986965
Fp:mul1241469890
Fp2:mul360412
Fp2:square288335
G1::double11501300
G1::add22002600
G2::double25002900
G2::add56506500
Fp12::square45005150
Fp12::mul61507000
Miller loop0.83M0.97M0.82M0.71M
final_exp0.53M0.63M0.51M0.46M
pairing1.36M1.60M1.33M1.17M

References

Authors

Contributors