biggroup.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 "../bigfield/bigfield.hpp"
#include "../bigfield/goblin_field.hpp"
#include "../byte_array/byte_array.hpp"
#include "../circuit_builders/circuit_builders_fwd.hpp"
#include "../field/field.hpp"
#include "../field/field_utils.hpp"
#include "../memory/rom_table.hpp"
#include "../memory/twin_rom_table.hpp"
#include "barretenberg/ecc/curves/bn254/g1.hpp"
#include "barretenberg/ecc/curves/secp256k1/secp256k1.hpp"
#include "barretenberg/ecc/curves/secp256r1/secp256r1.hpp"
#include "barretenberg/stdlib/primitives/biggroup/biggroup_goblin.hpp"
#include <cstddef>
 
namespace bb::stdlib::element_default {
 
// ( ͡° ͜ʖ ͡°)
template <class Builder_, class Fq, class Fr, class NativeGroup> class element {
  public:
    using Builder = Builder_;
    using bool_ct = stdlib::bool_t<Builder>;
    using field_ct = stdlib::field_t<Builder>;
    using witness_ct = stdlib::witness_t<Builder>;
    using biggroup_tag = element; // Facilitates a constexpr check IsBigGroup
    using BaseField = Fq;
 
    // Number of bb::fr field elements used to represent a goblin element in the public inputs
    static constexpr size_t PUBLIC_INPUTS_SIZE = BIGGROUP_PUBLIC_INPUTS_SIZE;
 
    element();
    element(const typename NativeGroup::affine_element& input);
 
    // Construct a biggroup element from its coordinates
    // By default, we validate that the point is on the curve
    element(const Fq& x, const Fq& y, const bool assert_on_curve = true);
    element(const Fq& x, const Fq& y, const bool_ct& is_infinity, bool assert_on_curve = true);
 
    element(const element& other);
    element(element&& other) noexcept;
 
    ~element() = default;
 
    uint32_t set_public() const
    {
        const uint32_t start_idx = _x.set_public();
        _y.set_public();
 
        return start_idx;
    }
 
    static element reconstruct_from_public(const std::span<const Fr, PUBLIC_INPUTS_SIZE>& limbs)
    {
        const size_t FRS_PER_FQ = Fq::PUBLIC_INPUTS_SIZE;
        std::span<const Fr, FRS_PER_FQ> x_limbs{ limbs.data(), FRS_PER_FQ };
        std::span<const Fr, FRS_PER_FQ> y_limbs{ limbs.data() + FRS_PER_FQ, FRS_PER_FQ };
 
        const Fq x = Fq::reconstruct_from_public(x_limbs);
        const Fq y = Fq::reconstruct_from_public(y_limbs);
        return element(x, y);
    }
 
    static element from_witness(Builder* ctx, const typename NativeGroup::affine_element& input)
    {
        element out;
        if (input.is_point_at_infinity()) {
            Fq x = Fq::from_witness(ctx, NativeGroup::affine_one.x);
            Fq y = Fq::from_witness(ctx, NativeGroup::affine_one.y);
            out._x = x;
            out._y = y;
        } else {
            Fq x = Fq::from_witness(ctx, input.x);
            Fq y = Fq::from_witness(ctx, input.y);
            out._x = x;
            out._y = y;
        }
        out.set_point_at_infinity(witness_ct(ctx, input.is_point_at_infinity()));
 
        // Mark the element as coming out of nowhere
        out.set_free_witness_tag();
        out.validate_on_curve();
        return out;
    }
 
    void validate_on_curve(std::string const& msg = "biggroup::validate_on_curve") const
    {
        bool has_circuit_failed = get_context()->failed();
 
        Fq b(get_context(), uint256_t(NativeGroup::curve_b));
        Fq adjusted_b = Fq::conditional_assign(is_point_at_infinity(), Fq::zero(), b);
        Fq adjusted_x = Fq::conditional_assign(is_point_at_infinity(), Fq::zero(), _x);
        Fq adjusted_y = Fq::conditional_assign(is_point_at_infinity(), Fq::zero(), _y);
        if constexpr (!NativeGroup::has_a) {
            // we validate y^2 = x^3 + b by setting "fix_remainder_zero = true" when calling mult_madd
            Fq::mult_madd({ adjusted_x.sqr(), adjusted_y }, { adjusted_x, -adjusted_y }, { adjusted_b }, true);
        } else {
            Fq a(get_context(), uint256_t(NativeGroup::curve_a));
            Fq adjusted_a = Fq::conditional_assign(is_point_at_infinity(), Fq::zero(), a);
            // we validate y^2 = x^3 + ax + b by setting "fix_remainder_zero = true" when calling mult_madd
            Fq::mult_madd({ adjusted_x.sqr(), adjusted_x, adjusted_y },
                          { adjusted_x, adjusted_a, -adjusted_y },
                          { adjusted_b },
                          true);
        }
 
        if ((!has_circuit_failed) && (get_context()->failed())) {
            vinfo("Original bigfield error generated by biggroup::validate_on_curve: ", get_context()->err());
            get_context()->failure(msg);
        }
    }
 
    [[nodiscard]] bool is_constant() const
    {
        const bool x_is_const = _x.is_constant();
        const bool y_is_const = _y.is_constant();
        BB_ASSERT_EQ(x_is_const, y_is_const, "biggroup: x and y coordinate constant status mismatch");
        return x_is_const;
    }
 
    void convert_constant_to_fixed_witness(Builder* builder)
    {
        this->_x.convert_constant_to_fixed_witness(builder);
        this->_y.convert_constant_to_fixed_witness(builder);
        // Origin tags should be unset after fixing the witness
        unset_free_witness_tag();
    }
 
    void fix_witness()
    {
        // Origin tags should be updated within
        this->_x.fix_witness();
        this->_y.fix_witness();
 
        // This is now effectively a constant
        unset_free_witness_tag();
    }
 
    static element one(Builder* ctx)
    {
        uint256_t x = uint256_t(NativeGroup::one.x);
        uint256_t y = uint256_t(NativeGroup::one.y);
        Fq x_fq(ctx, x);
        Fq y_fq(ctx, y);
        return element(x_fq, y_fq, /*assert_on_curve=*/false);
    }
 
    static element point_at_infinity(Builder* ctx)
    {
        Fr zero = Fr::from_witness_index(ctx, ctx->zero_idx());
        zero.unset_free_witness_tag();
        Fq x_fq(zero, zero);
        Fq y_fq(zero, zero);
        element result(x_fq, y_fq, /*assert_on_curve=*/false);
        result.set_point_at_infinity(true);
        return result;
    }
 
    element& operator=(const element& other);
    element& operator=(element&& other) noexcept;
 
    element checked_unconditional_add(const element& other) const;
    element checked_unconditional_subtract(const element& other) const;
 
    element operator+(const element& other) const;
    element operator-(const element& other) const;
    element operator-() const
    {
        element result(*this);
        result._y = -result._y;
        return result;
    }
    element operator+=(const element& other)
    {
        *this = *this + other;
        return *this;
    }
    element operator-=(const element& other)
    {
        *this = *this - other;
        return *this;
    }
 
    element operator*(const Fr& scalar) const;
 
    element conditional_negate(const bool_ct& predicate) const
    {
        element result(*this);
        result._y = result._y.conditional_negate(predicate);
        return result;
    }
 
    element conditional_select(const element& other, const bool_ct& predicate) const
    {
        // If predicate is constant, we can select out of circuit
        if (predicate.is_constant()) {
            auto result = predicate.get_value() ? other : *this;
            result.set_origin_tag(
                OriginTag(predicate.get_origin_tag(), other.get_origin_tag(), this->get_origin_tag()));
            return result;
        }
 
        // Get the builder context
        Builder* ctx = validate_context<Builder>(get_context(), other.get_context(), predicate.get_context());
        BB_ASSERT_NEQ(ctx, nullptr, "biggroup::conditional_select must have a context");
 
        element result(*this);
        result._x = result._x.conditional_select(other._x, predicate);
        result._y = result._y.conditional_select(other._y, predicate);
        result._is_infinity =
            bool_ct::conditional_assign(predicate, other.is_point_at_infinity(), result.is_point_at_infinity());
        return result;
    }
 
    void incomplete_assert_equal(const element& other,
                                 const std::string msg = "biggroup::incomplete_assert_equal") const
    {
        is_point_at_infinity().assert_equal(other.is_point_at_infinity(), msg + " (infinity flag)");
        _x.assert_equal(other._x, msg + " (x coordinate)");
        _y.assert_equal(other._y, msg + " (y coordinate)");
    }
 
    element normalize() const
    {
        element result(*this);
        result._x.reduce_mod_target_modulus();
        result._y.reduce_mod_target_modulus();
        return result;
    }
    element scalar_mul(const Fr& scalar, const size_t max_num_bits = 0) const;
 
    element reduce() const
    {
        element result(*this);
        result._x.self_reduce();
        result._y.self_reduce();
        return result;
    }
 
    void assert_coordinates_in_field(const std::string& msg = "biggroup::assert_coordinates_in_field") const
    {
        _x.assert_is_in_field(msg + " (x coordinate)");
        _y.assert_is_in_field(msg + " (y coordinate)");
    }
 
    element dbl() const;
 
    // we use this data structure to add together a sequence of points.
    // By tracking the previous values of x_1, y_1, \lambda, we can avoid
    // computing the output y-coordinate of intermediate additions
    struct chain_add_accumulator {
        Fq x1_prev;
        Fq y1_prev;
        Fq lambda_prev;
        Fq x3_prev;
        Fq y3_prev;
        bool is_full_element = false;
 
        chain_add_accumulator() = default;
        explicit chain_add_accumulator(const element& input)
            : x3_prev(input._x)
            , y3_prev(input._y)
            , is_full_element(true)
        {}
        chain_add_accumulator(const chain_add_accumulator& other) = default;
        chain_add_accumulator(chain_add_accumulator&& other) noexcept = default;
        chain_add_accumulator& operator=(const chain_add_accumulator& other) = default;
        chain_add_accumulator& operator=(chain_add_accumulator&& other) noexcept = default;
        ~chain_add_accumulator() = default;
    };
 
    static chain_add_accumulator chain_add_start(const element& p1, const element& p2);
    static chain_add_accumulator chain_add(const element& p1, const chain_add_accumulator& accumulator);
    static element chain_add_end(const chain_add_accumulator& accumulator);
    element multiple_montgomery_ladder(const std::vector<chain_add_accumulator>& to_add) const;
 
    typename NativeGroup::affine_element get_value() const
    {
        uint512_t x_val = _x.get_value() % Fq::modulus_u512;
        uint512_t y_val = _y.get_value() % Fq::modulus_u512;
        auto result = typename NativeGroup::affine_element(x_val.lo, y_val.lo);
        if (is_point_at_infinity().get_value()) {
            result.self_set_infinity();
        }
        return result;
    }
 
    static element batch_mul(const std::vector<element>& points,
                             const std::vector<Fr>& scalars,
                             const size_t max_num_bits = 0,
                             const bool with_edgecases = false,
                             const Fr& masking_scalar = Fr(1));
 
    template <typename X = NativeGroup, typename = typename std::enable_if_t<std::is_same<X, secp256k1::g1>::value>>
    static element secp256k1_ecdsa_mul(const element& pubkey, const Fr& u1, const Fr& u2);
 
    static std::vector<bool_ct> compute_naf(const Fr& scalar, const size_t max_num_bits = 0);
 
    // Internal struct to represent wNAF for a secp256k1 scalar
    struct secp256k1_wnaf {
        std::vector<field_t<Builder>> wnaf;
        bool_ct positive_skew;
        bool_ct negative_skew;
        field_t<Builder> least_significant_wnaf_fragment;
        bool has_wnaf_fragment = false;
    };
 
    // Internal struct to represent a pair of secp256k1 wNAFs
    struct secp256k1_wnaf_pair {
        secp256k1_wnaf klo;
        secp256k1_wnaf khi;
    };
 
    template <size_t wnaf_size, size_t staggered_lo_offset = 0, size_t staggered_hi_offset = 0>
    static secp256k1_wnaf_pair compute_secp256k1_endo_wnaf(const Fr& scalar, const bool range_constrain_wnaf = true);
 
    Builder* get_context() const { return validate_context<Builder>(_x.get_context(), _y.get_context()); }
 
    Builder* get_context(const element& other) const
    {
        return validate_context<Builder>(get_context(), other.get_context());
    }
 
    // Coordinate accessors (non-owning, const reference)
    const Fq& x() const { return _x; }
    const Fq& y() const { return _y; }
 
    bool_ct is_point_at_infinity() const { return _is_infinity; }
    void set_point_at_infinity(const bool_ct& is_infinity, const bool& add_to_used_witnesses = false)
    {
        _is_infinity = is_infinity.normalize();
        if (add_to_used_witnesses) {
            mark_witness_as_used(field_t<Builder>(_is_infinity));
        };
    }
    element get_standard_form() const;
 
    void set_origin_tag(OriginTag tag) const
    {
        _x.set_origin_tag(tag);
        _y.set_origin_tag(tag);
        _is_infinity.set_origin_tag(tag);
    }
 
    void clear_round_provenance() const
    {
        _x.clear_round_provenance();
        _y.clear_round_provenance();
        _is_infinity.clear_round_provenance();
    }
 
    OriginTag get_origin_tag() const
    {
        return OriginTag(_x.get_origin_tag(), _y.get_origin_tag(), _is_infinity.get_origin_tag());
    }
 
    void unset_free_witness_tag()
    {
        _x.unset_free_witness_tag();
        _y.unset_free_witness_tag();
        _is_infinity.unset_free_witness_tag();
    }
 
    void set_free_witness_tag()
    {
        _x.set_free_witness_tag();
        _y.set_free_witness_tag();
        _is_infinity.set_free_witness_tag();
    }
 
    // For testing purposes only
    friend class element_test_accessor;
 
  private:
    Fq _x;
    Fq _y;
    bool_ct _is_infinity;
 
    std::array<element, 2> checked_unconditional_add_sub(const element& other) const;
 
    static std::pair<std::vector<element>, std::vector<Fr>> mask_points(const std::vector<element>& _points,
                                                                        const std::vector<Fr>& _scalars,
                                                                        const Fr& masking_scalar);
 
    static std::pair<std::vector<element>, std::vector<Fr>> handle_points_at_infinity(
        const std::vector<element>& _points, const std::vector<Fr>& _scalars);
 
    template <size_t num_bits, size_t wnaf_size, size_t lo_stagger, size_t hi_stagger>
    static std::pair<Fr, secp256k1_wnaf> compute_secp256k1_single_wnaf(Builder* builder,
                                                                       const secp256k1::fr& scalar,
                                                                       size_t stagger,
                                                                       bool is_negative,
                                                                       const bool range_constrain_wnaf = true,
                                                                       bool is_lo = false);
 
    template <size_t wnaf_size>
    static std::pair<uint64_t, bool> get_staggered_wnaf_fragment_value(const uint64_t fragment_u64,
                                                                       const uint64_t stagger,
                                                                       bool is_negative,
                                                                       bool wnaf_skew);
 
    template <size_t wnaf_size>
    static std::vector<field_ct> convert_wnaf_values_to_witnesses(Builder* builder,
                                                                  const uint64_t* wnaf_values,
                                                                  bool is_negative,
                                                                  size_t rounds,
                                                                  const bool range_constrain_wnaf = true);
 
    template <size_t wnaf_size>
    static Fr reconstruct_bigfield_from_wnaf(Builder* builder,
                                             const std::vector<field_ct>& wnaf,
                                             const bool_ct& positive_skew,
                                             const bool_ct& negative_skew,
                                             const field_ct& stagger_fragment,
                                             const size_t stagger,
                                             const size_t rounds);
 
    template <size_t num_elements>
    static std::array<twin_rom_table<Builder>, Fq::NUM_LIMBS + 1> create_group_element_rom_tables(
        const std::array<element, num_elements>& rom_data, std::array<uint256_t, Fq::NUM_LIMBS * 2>& limb_max);
 
    template <size_t num_elements>
    static element read_group_element_rom_tables(const std::array<twin_rom_table<Builder>, Fq::NUM_LIMBS + 1>& tables,
                                                 const field_ct& index,
                                                 const std::array<uint256_t, Fq::NUM_LIMBS * 2>& limb_max);
 
    static std::pair<element, element> compute_offset_generators(const size_t num_rounds);
    static typename NativeGroup::affine_element compute_table_offset_generator();
 
    struct four_bit_table_plookup {
        four_bit_table_plookup() = default;
        four_bit_table_plookup(const element& input);
 
        four_bit_table_plookup(const four_bit_table_plookup& other) = default;
        four_bit_table_plookup& operator=(const four_bit_table_plookup& other) = default;
        four_bit_table_plookup(four_bit_table_plookup&& other) noexcept = default;
        four_bit_table_plookup& operator=(four_bit_table_plookup&& other) noexcept = default;
        ~four_bit_table_plookup() = default;
 
        element operator[](const field_ct& index) const;
        element operator[](const size_t idx) const { return element_table[idx]; }
        std::array<element, 16> element_table;
 
        // Each coordinate is an Fq element, which has 4 binary basis limbs and 1 prime basis limb
        std::array<twin_rom_table<Builder>, Fq::NUM_LIMBS + 1> coordinates;
        std::array<uint256_t, Fq::NUM_LIMBS * 2> limb_max; // tracks the maximum size of each binary basis limb
    };
 
    struct eight_bit_fixed_base_table {
        enum CurveType { BN254, SECP256K1, SECP256R1 };
        eight_bit_fixed_base_table(const CurveType input_curve_type, bool use_endo)
            : curve_type(input_curve_type)
            , use_endomorphism(use_endo)
        {}
 
        eight_bit_fixed_base_table(const eight_bit_fixed_base_table& other) = default;
        eight_bit_fixed_base_table& operator=(const eight_bit_fixed_base_table& other) = default;
        eight_bit_fixed_base_table(eight_bit_fixed_base_table&& other) noexcept = default;
        eight_bit_fixed_base_table& operator=(eight_bit_fixed_base_table&& other) noexcept = default;
        ~eight_bit_fixed_base_table() = default;
 
        element operator[](const field_ct& index) const;
 
        element operator[](const size_t index) const;
 
        CurveType curve_type;
        bool use_endomorphism;
    };
 
    static std::pair<four_bit_table_plookup, four_bit_table_plookup> create_endo_pair_four_bit_table_plookup(
        const element& input);
 
    template <size_t length> struct lookup_table_plookup {
        static constexpr size_t table_size = (1ULL << (length));
        lookup_table_plookup() = default;
        lookup_table_plookup(const std::array<element, length>& inputs);
        lookup_table_plookup(const lookup_table_plookup& other) = default;
        lookup_table_plookup& operator=(const lookup_table_plookup& other) = default;
        lookup_table_plookup(lookup_table_plookup&& other) noexcept = default;
        lookup_table_plookup& operator=(lookup_table_plookup&& other) noexcept = default;
        ~lookup_table_plookup() = default;
 
        element get(const std::array<bool_ct, length>& bits) const;
 
        element operator[](const size_t idx) const { return element_table[idx]; }
 
        std::array<element, table_size> element_table;
 
        // Each coordinate is an Fq element, which has 4 binary basis limbs and 1 prime basis limb
        // ROM tables: (idx, x0, x1), (idx, x2, x3), (idx, y0, y1), (idx, y2, y3), (idx, xp, yp)
        std::array<twin_rom_table<Builder>, Fq::NUM_LIMBS + 1> coordinates;
        std::array<uint256_t, Fq::NUM_LIMBS * 2> limb_max;
    };
 
    using twin_lookup_table = lookup_table_plookup<2>;
 
    using triple_lookup_table = lookup_table_plookup<3>;
 
    using quad_lookup_table = lookup_table_plookup<4>;
 
    static std::pair<quad_lookup_table, quad_lookup_table> create_endo_pair_quad_lookup_table(
        const std::array<element, 4>& inputs)
    {
        quad_lookup_table base_table(inputs);
        quad_lookup_table endo_table;
        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 < 8; ++i) {
            endo_table.element_table[i + 8].x = base_table[7 - i].x * beta;
            endo_table.element_table[i + 8].y = base_table[7 - i].y;
 
            endo_table.element_table[7 - i] = (-endo_table.element_table[i + 8]);
        }
 
        endo_table.coordinates = create_group_element_rom_tables<16>(endo_table.element_table, endo_table.limb_max);
        return std::make_pair<quad_lookup_table, quad_lookup_table>(base_table, endo_table);
    }
 
    struct batch_lookup_table_plookup {
        batch_lookup_table_plookup(const std::vector<element>& points)
            : num_points(points.size())
            , num_fives(num_points / 5)
        {
            // size-6 table is expensive and only benefits us if creating them reduces the number of total tables
            if (num_points == 1) {
                num_fives = 0;
                num_sixes = 0;
            } else if (num_fives * 5 == (num_points - 1)) {
                // last 6 points to be added as one 6-table
                num_fives -= 1;
                num_sixes = 1;
            } else if (num_fives * 5 == (num_points - 2) && num_fives >= 2) {
                // last 12 points to be added as two 6-tables
                num_fives -= 2;
                num_sixes = 2;
            } else if (num_fives * 5 == (num_points - 3) && num_fives >= 3) {
                // last 18 points to be added as three 6-tables
                num_fives -= 3;
                num_sixes = 3;
            }
 
            // Calculate remaining points after allocating fives and sixes tables
            size_t remaining_points = num_points - (num_fives * 5 + num_sixes * 6);
 
            // Allocate one quad table if required (and update remaining points)
            has_quad = (remaining_points >= 4) && (num_points >= 4);
            if (has_quad) {
                remaining_points -= 4;
            }
 
            // Allocate one triple table if required (and update remaining points)
            has_triple = (remaining_points >= 3) && (num_points >= 3);
            if (has_triple) {
                remaining_points -= 3;
            }
 
            // Allocate one twin table if required (and update remaining points)
            has_twin = (remaining_points >= 2) && (num_points >= 2);
            if (has_twin) {
                remaining_points -= 2;
            }
 
            // If there is anything remaining, allocate a singleton
            has_singleton = (remaining_points != 0) && (num_points >= 1);
 
            // Sanity check
            BB_ASSERT_EQ(num_points,
                         num_sixes * 6 + num_fives * 5 + static_cast<size_t>(has_quad) * 4 +
                             static_cast<size_t>(has_triple) * 3 + static_cast<size_t>(has_twin) * 2 +
                             static_cast<size_t>(has_singleton) * 1,
                         "point allocation mismatch");
 
            size_t offset = 0;
            for (size_t i = 0; i < num_sixes; ++i) {
                six_tables.push_back(lookup_table_plookup<6>({
                    points[offset + (6 * i)],
                    points[offset + (6 * i) + 1],
                    points[offset + (6 * i) + 2],
                    points[offset + (6 * i) + 3],
                    points[offset + (6 * i) + 4],
                    points[offset + (6 * i) + 5],
                }));
            }
            offset += 6 * num_sixes;
            for (size_t i = 0; i < num_fives; ++i) {
                five_tables.push_back(lookup_table_plookup<5>({
                    points[offset + (5 * i)],
                    points[offset + (5 * i) + 1],
                    points[offset + (5 * i) + 2],
                    points[offset + (5 * i) + 3],
                    points[offset + (5 * i) + 4],
                }));
            }
            offset += 5 * num_fives;
 
            if (has_quad) {
                quad_tables.push_back(
                    quad_lookup_table({ points[offset], points[offset + 1], points[offset + 2], points[offset + 3] }));
            }
            if (has_triple) {
                triple_tables.push_back(
                    triple_lookup_table({ points[offset], points[offset + 1], points[offset + 2] }));
            }
            if (has_twin) {
                twin_tables.push_back(twin_lookup_table({ points[offset], points[offset + 1] }));
            }
            if (has_singleton) {
                singletons.push_back(points[points.size() - 1]);
            }
        }
 
        chain_add_accumulator get_chain_initial_entry() const
        {
            std::vector<element> add_accumulator;
            for (size_t i = 0; i < num_sixes; ++i) {
                add_accumulator.push_back(six_tables[i][0]);
            }
            for (size_t i = 0; i < num_fives; ++i) {
                add_accumulator.push_back(five_tables[i][0]);
            }
            if (has_quad) {
                add_accumulator.push_back(quad_tables[0][0]);
            }
            if (has_twin) {
                add_accumulator.push_back(twin_tables[0][0]);
            }
            if (has_triple) {
                add_accumulator.push_back(triple_tables[0][0]);
            }
            if (has_singleton) {
                add_accumulator.push_back(singletons[0]);
            }
            if (add_accumulator.size() >= 2) {
                chain_add_accumulator output = element::chain_add_start(add_accumulator[0], add_accumulator[1]);
                for (size_t i = 2; i < add_accumulator.size(); ++i) {
                    output = element::chain_add(add_accumulator[i], output);
                }
                return output;
            }
            return chain_add_accumulator(add_accumulator[0]);
        }
 
        element::chain_add_accumulator get_chain_add_accumulator(std::vector<bool_ct>& naf_entries) const
        {
            std::vector<element> round_accumulator;
            for (size_t j = 0; j < num_sixes; ++j) {
                round_accumulator.push_back(six_tables[j].get({ naf_entries[6 * j],
                                                                naf_entries[(6 * j) + 1],
                                                                naf_entries[(6 * j) + 2],
                                                                naf_entries[(6 * j) + 3],
                                                                naf_entries[(6 * j) + 4],
                                                                naf_entries[(6 * j) + 5] }));
            }
            size_t offset = num_sixes * 6;
            for (size_t j = 0; j < num_fives; ++j) {
                round_accumulator.push_back(five_tables[j].get({ naf_entries[offset + (j * 5)],
                                                                 naf_entries[offset + (j * 5) + 1],
                                                                 naf_entries[offset + (j * 5) + 2],
                                                                 naf_entries[offset + (j * 5) + 3],
                                                                 naf_entries[offset + (j * 5) + 4] }));
            }
            offset += num_fives * 5;
            if (has_quad) {
                round_accumulator.push_back(quad_tables[0].get({ naf_entries[offset],
                                                                 naf_entries[offset + 1],
                                                                 naf_entries[offset + 2],
                                                                 naf_entries[offset + 3] }));
            }
 
            if (has_triple) {
                round_accumulator.push_back(
                    triple_tables[0].get({ naf_entries[offset], naf_entries[offset + 1], naf_entries[offset + 2] }));
            }
            if (has_twin) {
                round_accumulator.push_back(twin_tables[0].get({ naf_entries[offset], naf_entries[offset + 1] }));
            }
            if (has_singleton) {
                round_accumulator.push_back(singletons[0].conditional_negate(naf_entries[num_points - 1]));
            }
 
            if (round_accumulator.size() == 1) {
                return element::chain_add_accumulator(round_accumulator[0]);
            }
 
            if (round_accumulator.size() == 2) {
                return element::chain_add_start(round_accumulator[0], round_accumulator[1]);
            }
 
            // Use chain add for at least 3 elements
            element::chain_add_accumulator accumulator =
                element::chain_add_start(round_accumulator[0], round_accumulator[1]);
            for (size_t j = 2; j < round_accumulator.size(); ++j) {
                accumulator = element::chain_add(round_accumulator[j], accumulator);
            }
 
            return (accumulator);
        }
 
        element get(std::vector<bool_ct>& naf_entries) const
        {
            std::vector<element> round_accumulator;
            for (size_t j = 0; j < num_sixes; ++j) {
                round_accumulator.push_back(six_tables[j].get({ naf_entries[(6 * j)],
                                                                naf_entries[(6 * j) + 1],
                                                                naf_entries[(6 * j) + 2],
                                                                naf_entries[(6 * j) + 3],
                                                                naf_entries[(6 * j) + 4],
                                                                naf_entries[(6 * j) + 5] }));
            }
            size_t offset = num_sixes * 6;
 
            for (size_t j = 0; j < num_fives; ++j) {
                round_accumulator.push_back(five_tables[j].get({ naf_entries[offset + (5 * j)],
                                                                 naf_entries[offset + (5 * j) + 1],
                                                                 naf_entries[offset + (5 * j) + 2],
                                                                 naf_entries[offset + (5 * j) + 3],
                                                                 naf_entries[offset + (5 * j) + 4] }));
            }
 
            offset += num_fives * 5;
 
            if (has_quad) {
                round_accumulator.push_back(quad_tables[0].get(
                    naf_entries[offset], naf_entries[offset + 1], naf_entries[offset + 2], naf_entries[offset + 3]));
            }
            if (has_triple) {
                round_accumulator.push_back(
                    triple_tables[0].get(naf_entries[offset], naf_entries[offset + 1], naf_entries[offset + 2]));
            }
            if (has_twin) {
                round_accumulator.push_back(twin_tables[0].get(naf_entries[offset], naf_entries[offset + 1]));
            }
            if (has_singleton) {
                round_accumulator.push_back(singletons[0].conditional_negate(naf_entries[num_points - 1]));
            }
 
            element result = round_accumulator[0];
            element::chain_add_accumulator accumulator;
            if (round_accumulator.size() == 1) {
                return result;
            }
 
            if (round_accumulator.size() == 2) {
                return result + round_accumulator[1];
            }
 
            // For 3 or more elements, use chain addition
            accumulator = element::chain_add_start(round_accumulator[0], round_accumulator[1]);
            for (size_t j = 2; j < round_accumulator.size(); ++j) {
                accumulator = element::chain_add(round_accumulator[j], accumulator);
            }
 
            return element::chain_add_end(accumulator);
        }
 
        std::vector<lookup_table_plookup<6>> six_tables;
        std::vector<lookup_table_plookup<5>> five_tables;
        std::vector<quad_lookup_table> quad_tables;
        std::vector<triple_lookup_table> triple_tables;
        std::vector<twin_lookup_table> twin_tables;
        std::vector<element> singletons;
        size_t num_points;
 
        size_t num_sixes = 0;
        size_t num_fives;
        bool has_quad;
        bool has_triple;
        bool has_twin;
        bool has_singleton;
    };
 
    using batch_lookup_table = batch_lookup_table_plookup;
 
    static element process_strauss_msm_rounds(const std::vector<element>& points,
                                              const std::vector<Fr>& scalars,
                                              const size_t max_num_bits);
};
 
// For testing purposes only
class element_test_accessor {
  public:
    template <typename C, typename Fq, typename Fr, typename G, size_t wnaf_size>
    static auto get_staggered_wnaf_fragment_value(uint64_t fragment_u64,
                                                  uint64_t stagger,
                                                  bool is_negative,
                                                  bool wnaf_skew)
    {
        return element<C, Fq, Fr, G>::template get_staggered_wnaf_fragment_value<wnaf_size>(
            fragment_u64, stagger, is_negative, wnaf_skew);
    }
 
    template <typename C, typename Fq, typename Fr, typename G>
    static auto checked_unconditional_add_sub(const element<C, Fq, Fr, G>& elem1, const element<C, Fq, Fr, G>& elem2)
    {
        return elem1.checked_unconditional_add_sub(elem2);
    }
 
    // Overload for goblin_element
    template <typename C, typename Fq, typename Fr, typename G>
    static auto checked_unconditional_add_sub(const element_goblin::goblin_element<C, Fq, Fr, G>& elem1,
                                              const element_goblin::goblin_element<C, Fq, Fr, G>& elem2)
    {
        return elem1.checked_unconditional_add_sub(elem2);
    }
};
 
template <typename C, typename Fq, typename Fr, typename G>
inline std::ostream& operator<<(std::ostream& os, element<C, Fq, Fr, G> const& v)
{
    return os << "{ " << v.x() << " , " << v.y() << " }";
}
} // namespace bb::stdlib::element_default
 
namespace bb::stdlib {
template <typename T>
concept IsBigGroup = std::is_same_v<typename T::biggroup_tag, T>;
 
template <typename Builder, class Fq, class Fr, class NativeGroup>
concept IsGoblinBigGroup =
    IsMegaBuilder<Builder> && std::same_as<Fq, bb::stdlib::bigfield<Builder, bb::Bn254FqParams>> &&
    std::same_as<Fr, bb::stdlib::field_t<Builder>> && std::same_as<NativeGroup, bb::g1>;
 
template <typename C, typename Fq, typename Fr, typename G>
using element = std::conditional_t<IsGoblinBigGroup<C, Fq, Fr, G>,
                                   element_goblin::goblin_element<C, goblin_field<C>, Fr, G>,
                                   element_default::element<C, Fq, Fr, G>>;
} // namespace bb::stdlib
#include "biggroup_edgecase_handling.hpp"
#include "biggroup_goblin.hpp"
#include "biggroup_impl.hpp"
#include "biggroup_nafs.hpp"
#include "biggroup_secp256k1.hpp"
#include "biggroup_tables.hpp"