pairing.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Completed, auditors: [Federico], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#include <random>
 
#include "./fq12.hpp"
#include "./fq2.hpp"
#include "./fq6.hpp"
#include "./g1.hpp"
#include "./g2.hpp"
 
namespace bb::pairing {
 
// Number of iterations in the Miller loop, equal to the length minus 1 of the signed bit decomposition of (6 * z + 2),
// where z is the parameter of BN254
constexpr size_t loop_length = 64;
// Bit length minus 1 of the parameter z of BN254
constexpr size_t z_loop_length = 62;
// Number of lines required by the Miller loop: equal to
// loop_length (tangent lines) +
// len([i for i in range(loop_length) if loop_bits[i] != 0]) (addition lines) +
// 2 (final two lines)
constexpr size_t precomputed_coefficients_length = 87;
 
// Signed bit decomposition (from MSB to LSB) of (6 * z + 2) where z is the parameter of BN254, used in the Miller loop.
// \f$6z + 2 = \sum_{i} b_i 2^i + 2^{64}\f$ where b_i = 1 if loop_bits[loop_length - i - 1] = 1, b_i = -1 if
// loop_bits[loop_length - i - 1] = 3 and b_i = 0 if loop_bits[loop_length - i - 1] = 0
constexpr std::array<uint8_t, loop_length> loop_bits{ 1, 0, 1, 0, 0, 0, 3, 0, 3, 0, 0, 0, 3, 0, 1, 0, 3, 0, 0, 3, 0, 0,
                                                      0, 0, 0, 1, 0, 0, 3, 0, 1, 0, 0, 3, 0, 0, 0, 0, 3, 0, 1, 0, 0, 0,
                                                      3, 0, 3, 0, 0, 1, 0, 0, 0, 3, 0, 0, 3, 0, 1, 0, 1, 0, 0, 0 };
 
// Bit decomposition of z (from MSB to LSB): \f$\sum_{i} b_i 2^i + 2^{64}\f$ where b_i = 1 if z_loop_bits[z_loop_length
// - i - 1] = 1 and b_i = 0 if z_loop_bits[z_loop_length - i - 1] = 0
constexpr std::array<bool, z_loop_length> z_loop_bits{
    false, false, false, true,  false, false, true,  true,  true, false, true,  false, false, true,  true,  false,
    false, true,  false, false, true,  false, true,  false, true, true,  false, true,  false, false, false, true,
    false, false, true,  false, true,  false, false, true,  true, false, true,  false, false, true,  false, false,
    false, false, true,  false, false, true,  true,  true,  true, true,  false, false, false, true
};
 
// ======================
// Miller loop
// ======================
struct miller_lines {
    std::array<fq12::ell_coeffs, precomputed_coefficients_length> lines;
};
 
struct g2Projective {
    fq2 x;
    fq2 y;
    fq2 z;
};
 
struct g1Projective {
    fq x;
    fq y;
    fq z;
};
 
constexpr void doubling_step_for_miller_loop(g2Projective& work_point, fq12::ell_coeffs& line);
 
constexpr void mixed_addition_step_for_miller_loop(const g2Projective& Q,
                                                   g2Projective& work_point,
                                                   fq12::ell_coeffs& line);
 
constexpr void precompute_miller_lines(const g2Projective& Q, miller_lines& lines);
 
// Overload when the function is called with a g2::element
constexpr void precompute_miller_lines(const g2::element& Q, miller_lines& lines);
 
constexpr fq12 miller_loop(const g1::affine_element& P, const miller_lines& lines);
 
constexpr fq12 miller_loop_batch(const g1::affine_element* points, const miller_lines* lines, size_t num_pairs);
 
// ======================
// Final exponentiation
// ======================
 
constexpr fq12 final_exponentiation_easy_part(const fq12& elt);
 
constexpr fq12 final_exponentiation_exp_by_z(const fq12& elt);
 
constexpr fq12 final_exponentiation_tricky_part(const fq12& elt);
 
// ======================
// Pairing
//
// NOTE: All points supplied for pairing calculations are checked to be on the curve. This is equivalent to a subgroup
// membership check for points in G1 = BN254. We don't implement subgroup membership checks for G2 because the only
// place in the codebase where we use pairings is in PairingPoints::check(), which takes two points P1, P2 in G1
// and checks e(P1, [1]) * e(P2, [x]) = 1. The points [1] and [x] are taken from the SRS, so we know they belong to G2.
//
// ======================
 
constexpr fq12 reduced_ate_pairing(const g1::affine_element& P_affine, const g2::affine_element& Q_affine);
 
inline fq12 reduced_ate_pairing_batch(const g1::affine_element* P_affines,
                                      const g2::affine_element* Q_affines,
                                      size_t num_points);
 
inline fq12 reduced_ate_pairing_batch_precomputed(const g1::affine_element* P_affines,
                                                  const miller_lines* lines,
                                                  size_t num_points);
 
} // namespace bb::pairing
 
#include "./pairing_impl.hpp"