biggroup_bn254.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#pragma once
#include "barretenberg/common/assert.hpp"
#include "barretenberg/ecc/groups/precomputed_generators_bn254_impl.hpp"
#include "barretenberg/stdlib/primitives/biggroup/biggroup.hpp"
#include "barretenberg/stdlib/primitives/circuit_builders/circuit_builders.hpp"
#include "barretenberg/transcript/origin_tag.hpp"
namespace bb::stdlib::element_default {
 
template <class C, class Fq, class Fr, class G>
template <typename, typename>
    requires(IsNotMegaBuilder<C>)
element<C, Fq, Fr, G> element<C, Fq, Fr, G>::bn254_endo_batch_mul_with_generator(
    const std::vector<element>& big_points,
    const std::vector<Fr>& big_scalars,
    const std::vector<element>& small_points,
    const std::vector<Fr>& small_scalars,
    const Fr& generator_scalar,
    const size_t max_num_small_bits)
{
    C* ctx = nullptr;
    for (auto element : big_points) {
        if (element.get_context()) {
            ctx = element.get_context();
            break;
        }
    }
 
    constexpr size_t NUM_BIG_POINTS = 4;
    // TODO: handle situation where big points size is not 4 :/
 
    auto big_table_pair =
        create_endo_pair_quad_lookup_table({ big_points[0], big_points[1], big_points[2], big_points[3] });
    auto& big_table = big_table_pair.first;
    auto& endo_table = big_table_pair.second;
    batch_lookup_table small_table(small_points);
    std::vector<std::vector<bool_ct>> big_naf_entries;
    std::vector<std::vector<bool_ct>> endo_naf_entries;
    std::vector<std::vector<bool_ct>> small_naf_entries;
 
    const auto split_into_endomorphism_scalars = [ctx](const Fr& scalar) {
        bb::fr k = scalar.get_value();
        bb::fr k1(0);
        bb::fr k2(0);
        bb::fr::split_into_endomorphism_scalars(k.from_montgomery_form(), k1, k2);
        Fr scalar_k1 = Fr::from_witness(ctx, k1.to_montgomery_form());
        Fr scalar_k2 = Fr::from_witness(ctx, k2.to_montgomery_form());
        bb::fr beta = bb::fr::cube_root_of_unity();
        scalar.assert_equal(scalar_k1 - scalar_k2 * beta);
        return std::make_pair<Fr, Fr>((Fr)scalar_k1, (Fr)scalar_k2);
    };
 
    for (size_t i = 0; i < NUM_BIG_POINTS; ++i) {
        const auto [scalar_k1, scalar_k2] = split_into_endomorphism_scalars(big_scalars[i]);
        big_naf_entries.emplace_back(compute_naf(scalar_k1, max_num_small_bits));
        endo_naf_entries.emplace_back(compute_naf(scalar_k2, max_num_small_bits));
    }
 
    const auto [generator_k1, generator_k2] = split_into_endomorphism_scalars(generator_scalar);
    const std::vector<field_t<C>> generator_wnaf = compute_wnaf<128, 8>(generator_k1);
    const std::vector<field_t<C>> generator_endo_wnaf = compute_wnaf<128, 8>(generator_k2);
    const auto generator_table =
        element::eight_bit_fixed_base_table(element::eight_bit_fixed_base_table::CurveType::BN254, false);
    const auto generator_endo_table =
        element::eight_bit_fixed_base_table(element::eight_bit_fixed_base_table::CurveType::BN254, true);
 
    for (size_t i = 0; i < small_points.size(); ++i) {
        small_naf_entries.emplace_back(compute_naf(small_scalars[i], max_num_small_bits));
    }
 
    const size_t num_rounds = max_num_small_bits;
 
    const auto offset_generators = compute_offset_generators(num_rounds);
 
    auto init_point = element::chain_add(offset_generators.first, small_table.get_chain_initial_entry());
    init_point = element::chain_add(endo_table[0], init_point);
    init_point = element::chain_add(big_table[0], init_point);
 
    element accumulator = element::chain_add_end(init_point);
 
    const auto get_point_to_add = [&](size_t naf_index) {
        std::vector<bool_ct> small_nafs;
        std::vector<bool_ct> big_nafs;
        std::vector<bool_ct> endo_nafs;
        for (size_t i = 0; i < small_points.size(); ++i) {
            small_nafs.emplace_back(small_naf_entries[i][naf_index]);
        }
        for (size_t i = 0; i < NUM_BIG_POINTS; ++i) {
            big_nafs.emplace_back(big_naf_entries[i][naf_index]);
            endo_nafs.emplace_back(endo_naf_entries[i][naf_index]);
        }
 
        auto to_add = small_table.get_chain_add_accumulator(small_nafs);
        to_add = element::chain_add(big_table.get({ big_nafs[0], big_nafs[1], big_nafs[2], big_nafs[3] }), to_add);
        to_add = element::chain_add(endo_table.get({ endo_nafs[0], endo_nafs[1], endo_nafs[2], endo_nafs[3] }), to_add);
        return to_add;
    };
 
    // Perform multiple rounds of the montgomery ladder algoritm per "iteration" of our main loop.
    // This is in order to reduce the number of field reductions required when calling `multiple_montgomery_ladder`
    constexpr size_t num_rounds_per_iteration = 4;
 
    // we require that we perform max of one generator per iteration
    static_assert(num_rounds_per_iteration < 8);
 
    size_t num_iterations = num_rounds / num_rounds_per_iteration;
    num_iterations += ((num_iterations * num_rounds_per_iteration) == num_rounds) ? 0 : 1;
    const size_t num_rounds_per_final_iteration = (num_rounds - 1) - ((num_iterations - 1) * num_rounds_per_iteration);
 
    size_t generator_idx = 0;
    for (size_t i = 0; i < num_iterations; ++i) {
 
        const size_t inner_num_rounds =
            (i != num_iterations - 1) ? num_rounds_per_iteration : num_rounds_per_final_iteration;
        std::vector<element::chain_add_accumulator> to_add;
 
        for (size_t j = 0; j < inner_num_rounds; ++j) {
            to_add.emplace_back(get_point_to_add(i * num_rounds_per_iteration + j + 1));
        }
 
        bool add_generator_this_round = false;
        size_t add_idx = 0;
        for (size_t j = 0; j < inner_num_rounds; ++j) {
            add_generator_this_round = ((i * num_rounds_per_iteration + j) % 8) == 6;
            if (add_generator_this_round) {
                add_idx = j;
                break;
            }
        }
        if (add_generator_this_round) {
            to_add[add_idx] = element::chain_add(generator_table[generator_wnaf[generator_idx]], to_add[add_idx]);
            to_add[add_idx] =
                element::chain_add(generator_endo_table[generator_endo_wnaf[generator_idx]], to_add[add_idx]);
            generator_idx++;
        }
        accumulator = accumulator.multiple_montgomery_ladder(to_add);
    }
 
    for (size_t i = 0; i < small_points.size(); ++i) {
        element skew = accumulator - small_points[i];
        Fq out_x = accumulator.x.conditional_select(skew.x, small_naf_entries[i][num_rounds]);
        Fq out_y = accumulator.y.conditional_select(skew.y, small_naf_entries[i][num_rounds]);
        accumulator = element(out_x, out_y);
    }
 
    uint256_t beta_val = bb::field<typename Fq::TParams>::cube_root_of_unity();
    Fq beta(bb::fr(beta_val.slice(0, 136)), bb::fr(beta_val.slice(136, 256)), false);
 
    for (size_t i = 0; i < NUM_BIG_POINTS; ++i) {
        element skew_point = big_points[i];
        skew_point.x *= beta;
        element skew = accumulator + skew_point;
        Fq out_x = accumulator.x.conditional_select(skew.x, endo_naf_entries[i][num_rounds]);
        Fq out_y = accumulator.y.conditional_select(skew.y, endo_naf_entries[i][num_rounds]);
        accumulator = element(out_x, out_y);
    }
    {
        element skew = accumulator - generator_table[128];
        Fq out_x = accumulator.x.conditional_select(skew.x, bool_ct(generator_wnaf[generator_wnaf.size() - 1]));
        Fq out_y = accumulator.y.conditional_select(skew.y, bool_ct(generator_wnaf[generator_wnaf.size() - 1]));
        accumulator = element(out_x, out_y);
    }
    {
        element skew = accumulator - generator_endo_table[128];
        Fq out_x = accumulator.x.conditional_select(skew.x, bool_ct(generator_endo_wnaf[generator_wnaf.size() - 1]));
        Fq out_y = accumulator.y.conditional_select(skew.y, bool_ct(generator_endo_wnaf[generator_wnaf.size() - 1]));
        accumulator = element(out_x, out_y);
    }
 
    for (size_t i = 0; i < NUM_BIG_POINTS; ++i) {
        element skew = accumulator - big_points[i];
        Fq out_x = accumulator.x.conditional_select(skew.x, big_naf_entries[i][num_rounds]);
        Fq out_y = accumulator.y.conditional_select(skew.y, big_naf_entries[i][num_rounds]);
        accumulator = element(out_x, out_y);
    }
    accumulator = accumulator - offset_generators.second;
 
    return accumulator;
}
 
template <typename C, class Fq, class Fr, class G>
template <typename, typename>
    requires(IsNotMegaBuilder<C>)
element<C, Fq, Fr, G> element<C, Fq, Fr, G>::bn254_endo_batch_mul(const std::vector<element>& big_points,
                                                                  const std::vector<Fr>& big_scalars,
                                                                  const std::vector<element>& small_points,
                                                                  const std::vector<Fr>& small_scalars,
                                                                  const size_t max_num_small_bits)
{
 
    BB_ASSERT_EQ(max_num_small_bits % 2, 0U);
 
    const size_t num_big_points = big_points.size();
    const size_t num_small_points = small_points.size();
    C* ctx = nullptr;
    for (auto element : big_points) {
        if (element.get_context()) {
            ctx = element.get_context();
            break;
        }
    }
 
    std::vector<element> points;
    std::vector<Fr> scalars;
    std::vector<element> endo_points;
    std::vector<Fr> endo_scalars;
 
    bb::fr lambda = bb::fr::cube_root_of_unity();
    bb::fq beta = bb::fq::cube_root_of_unity();
    for (size_t i = 0; i < num_big_points; ++i) {
        Fr scalar = big_scalars[i];
        // Q: is it a problem if wraps? get_value is 512 bits
        // A: it can't wrap, this method only compiles if the Fr type is a field_t<bb::fr> type
 
        // Split k into short scalars (scalar_k1, scalar_k2) using bn254 endomorphism.
        bb::fr k = uint256_t(scalar.get_value());
        bb::fr k1(0);
        bb::fr k2(0);
        bb::fr::split_into_endomorphism_scalars(k.from_montgomery_form(), k1, k2);
        Fr scalar_k1 = Fr::from_witness(ctx, k1.to_montgomery_form());
        Fr scalar_k2 = Fr::from_witness(ctx, k2.to_montgomery_form());
 
        // Propagate tags
        scalar_k1.set_origin_tag(scalar.get_origin_tag());
        scalar_k2.set_origin_tag(scalar.get_origin_tag());
 
        // Add copy constraint that validates k1 = scalar_k1 - scalar_k2 * \lambda
        scalar.assert_equal(scalar_k1 - scalar_k2 * lambda);
        scalars.push_back(scalar_k1);
        endo_scalars.push_back(scalar_k2);
        element point = big_points[i];
        points.push_back(point);
 
        // negate the point that maps to the endo scalar `scalar_k2`
        // instead of computing scalar_k1 * [P] - scalar_k2 * [P], we compute scalar_k1 * [P] + scalar_k2 * [-P]
        point.y = -point.y;
        point.x = point.x * Fq(ctx, uint256_t(beta));
        point.y.self_reduce();
        endo_points.push_back(point);
    }
    for (size_t i = 0; i < num_small_points; ++i) {
        points.push_back(small_points[i]);
        scalars.push_back(small_scalars[i]);
    }
    std::copy(endo_points.begin(), endo_points.end(), std::back_inserter(points));
    std::copy(endo_scalars.begin(), endo_scalars.end(), std::back_inserter(scalars));
 
    // Compute the tag of the result
    OriginTag union_tag{};
    for (size_t i = 0; i < points.size(); i++) {
        union_tag = OriginTag(union_tag, OriginTag(points[i].get_origin_tag(), scalars[i].get_origin_tag()));
 
        // Remove tags so they don't interfere during computation
        points[i].set_origin_tag(OriginTag());
        scalars[i].set_origin_tag(OriginTag());
    }
    BB_ASSERT_EQ(big_scalars.size(), num_big_points);
    BB_ASSERT_EQ(small_scalars.size(), num_small_points);
 
    batch_lookup_table point_table(points);
 
    const size_t num_rounds = max_num_small_bits;
    const size_t num_points = points.size();
    std::vector<std::vector<bool_ct>> naf_entries;
    for (size_t i = 0; i < num_points; ++i) {
        naf_entries.emplace_back(compute_naf(scalars[i], max_num_small_bits));
    }
 
    const auto offset_generators = compute_offset_generators(num_rounds);
 
    element accumulator = offset_generators.first + point_table.get_initial_entry();
 
    for (size_t i = 1; i < num_rounds / 2; ++i) {
        // `nafs` tracks the naf value for each point for the current round
        std::vector<bool_ct> nafs;
        for (size_t j = 0; j < points.size(); ++j) {
            nafs.emplace_back(naf_entries[j][i * 2 - 1]);
        }
 
        element::chain_add_accumulator add_1 = point_table.get_chain_add_accumulator(nafs);
        for (size_t j = 0; j < points.size(); ++j) {
            nafs[j] = (naf_entries[j][i * 2]);
        }
        element::chain_add_accumulator add_2 = point_table.get_chain_add_accumulator(nafs);
 
        // Perform the double montgomery ladder.
        accumulator = accumulator.multiple_montgomery_ladder({ add_1, add_2 });
    }
 
    // we need to iterate 1 more time if the number of rounds is even
    if ((num_rounds & 0x01ULL) == 0x00ULL) {
        std::vector<bool_ct> nafs;
        for (size_t j = 0; j < points.size(); ++j) {
            nafs.emplace_back(naf_entries[j][num_rounds - 1]);
        }
        element::chain_add_accumulator add_1 = point_table.get_chain_add_accumulator(nafs);
        accumulator = accumulator.multiple_montgomery_ladder({ add_1 });
    }
 
    for (size_t i = 0; i < num_points; ++i) {
        element skew = accumulator - points[i];
        Fq out_x = accumulator.x.conditional_select(skew.x, naf_entries[i][num_rounds]);
        Fq out_y = accumulator.y.conditional_select(skew.y, naf_entries[i][num_rounds]);
        accumulator = element(out_x, out_y);
    }
 
    // Remove the offset generator point!
    accumulator = accumulator - offset_generators.second;
 
    accumulator.set_origin_tag(union_tag);
    // Return our scalar mul output
    return accumulator;
}
} // namespace bb::stdlib::element_default