biggroup.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Suyash], commit: 553c5eb82901955c638b943065acd3e47fc918c0}
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#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();
 
    // Construct a biggroup element from its coordinates
    // The infinity flag is automatically set based on whether both coordinates are zero.
    // 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 element& other);
    element(element&& other) noexcept;
 
    ~element() = default;
 
    uint32_t set_public() const
    {
        auto standard = get_standard_form(); // if point is at infinity, ensure coordinates are (0,0).
        const uint32_t start_idx = standard._x.set_public();
        standard._y.set_public();
 
        return start_idx;
    }
 
    static element from_witness(Builder* ctx, const typename NativeGroup::affine_element& input)
    {
        // By convention we set the coordinates of the point at infinity to (0,0).
        Fq x;
        Fq y;
        if (input.is_point_at_infinity()) {
            x = Fq::from_witness(ctx, typename NativeGroup::Fq(0));
            y = Fq::from_witness(ctx, typename NativeGroup::Fq(0));
        } else {
            x = Fq::from_witness(ctx, input.x);
            y = Fq::from_witness(ctx, input.y);
        }
 
        // Create _is_infinity as a witness with the actual infinity status.
        // Security: Since assert_on_curve is true, validate_on_curve() enforces that if infinity=true, then x = y = 0.
        bool_ct is_infinity = bool_ct(witness_ct(ctx, input.is_point_at_infinity()));
 
        // Construct the biggroup element with private constructor to avoid redundant on-curve check
        element out = element(x, y, is_infinity, /*assert_on_curve=*/true);
 
        // Mark the element as coming out of nowhere
        out.set_free_witness_tag();
        return out;
    }
 
    Fq validate_on_curve(std::string const& msg = "biggroup::validate_on_curve", bool assert_is_on_curve = true) const
    {
        // Return early for constant inputs
        if (this->is_constant()) {
            BB_ASSERT(this->get_value().on_curve(), "biggroup::validate_on_curve: constant point not on curve");
            return typename Fq::native(this->get_value().on_curve() ? 0 : 1);
        }
 
        // If this is a point at infinity, it must have (x, y) = (0, 0)
        _x.assert_zero_if(is_point_at_infinity(), "biggroup::validate_on_curve: infinity point must have x = 0");
        _y.assert_zero_if(is_point_at_infinity(), "biggroup::validate_on_curve: infinity point must have y = 0");
 
        bool has_circuit_failed = get_context()->failed();
        Fq result;
 
        Fq b(get_context(), uint256_t(NativeGroup::curve_b));
        Fq adjusted_b = Fq::conditional_assign(is_point_at_infinity(), Fq::zero(), b);
        // If `assert_is_on_curve` is true, we validate y^2 = x^3 + b by setting "fix_remainder_zero = true" when
        // calling mult_madd. Otherwise, we return the difference x^3 + ax + b - y^2
        if constexpr (!NativeGroup::has_a) {
            result = Fq::mult_madd({ _x.sqr(), _y }, { _x, -_y }, { adjusted_b }, assert_is_on_curve);
            ;
        } else {
            Fq a(get_context(), uint256_t(NativeGroup::curve_a));
            Fq adjusted_a = Fq::conditional_assign(is_point_at_infinity(), Fq::zero(), a);
            result = Fq::mult_madd({ _x.sqr(), _x, _y }, { _x, adjusted_a, -_y }, { adjusted_b }, assert_is_on_curve);
        }
 
        if ((!has_circuit_failed) && (get_context()->failed())) {
            vinfo("Original bigfield error generated by biggroup::validate_on_curve: ", get_context()->err());
            get_context()->failure(msg);
        }
 
        return result;
    }
 
    [[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_infinity.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);
        // Use private 4-arg constructor with explicit is_infinity=false (the generator is never infinity).
        // This avoids the expensive bigfield equality checks in the 2-arg constructor's infinity auto-detection.
        return element(x_fq, y_fq, bool_ct(ctx, false), /*assert_on_curve=*/false);
    }
 
    static element constant_infinity(Builder* ctx)
    {
        Fq x_fq(ctx, uint256_t(0));
        Fq y_fq(ctx, uint256_t(0));
        return element(x_fq, y_fq, /*is_infinity=*/bool_ct(ctx, true), /*assert_on_curve=*/false);
    }
 
    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;
    }
 
    static element conditional_assign(const bool_t<Builder>& predicate, const element& lhs, const element& rhs)
    {
        return rhs.conditional_select(lhs, predicate);
    }
 
    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 = true);
 
    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);
 
    struct Secp256r1EcdsaMulResult {
        element result;
        bool_ct u2_is_acceptable;
    };
 
    template <typename X = NativeGroup, typename = typename std::enable_if_t<std::is_same<X, secp256r1::g1>::value>>
    static Secp256r1EcdsaMulResult secp256r1_ecdsa_mul(const element& pubkey, const Fr& u1, const Fr& u2);
 
    template <typename X = NativeGroup, typename = typename std::enable_if_t<std::is_same<X, secp256r1::g1>::value>>
    static element secp256r1_fixed_base_mul(const Fr& u);
 
    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;
    };
 
    // 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; }
    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:
    // Private constructor with explicit infinity flag control.
    // Use public constructors or factory methods instead - they auto-detect infinity from coordinates.
    element(const Fq& x, const Fq& y, const bool_ct& is_infinity, bool assert_on_curve);
 
    Fq _x;
    Fq _y;
    bool_ct _is_infinity;
 
    // Internal implementations - may produce non-canonical infinity representation (efficient for chaining)
    element add_internal(const element& other) const;
    element subtract_internal(const element& other) const;
    element dbl_internal() const;
    static element batch_mul_internal(const std::vector<element>& points,
                                      const std::vector<Fr>& scalars,
                                      const size_t max_num_bits = 0,
                                      const bool with_edgecases = false);
 
    std::array<element, 2> checked_unconditional_add_sub(const element& other) const;
 
    static std::tuple<std::vector<element>, std::vector<Fr>, element> mask_points(const std::vector<element>& _points,
                                                                                  const std::vector<Fr>& _scalars);
 
    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);
    }
 
    template <typename C, typename Fq, typename Fr, typename G>
    static auto mask_points(const std::vector<element<C, Fq, Fr, G>>& points, const std::vector<Fr>& scalars)
    {
        return element<C, Fq, Fr, G>::mask_points(points, scalars);
    }
 
    // 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>
    static element<C, Fq, Fr, G> create_element_with_explicit_infinity(const Fq& x,
                                                                       const Fq& y,
                                                                       const stdlib::bool_t<C>& is_infinity,
                                                                       bool assert_on_curve = false)
    {
        return element<C, Fq, Fr, G>(x, y, is_infinity, assert_on_curve);
    }
};
 
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_secp256r1.hpp"
#include "biggroup_tables.hpp"