biggroup_goblin.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Planned, auditors: [], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#include "../bigfield/goblin_field.hpp"
#include "../circuit_builders/circuit_builders_fwd.hpp"
#include "barretenberg/ecc/curves/bn254/g1.hpp"
#include "barretenberg/transcript/origin_tag.hpp"
 
namespace bb::stdlib::element_goblin {
 
template <class Builder_, class Fq, class Fr, class NativeGroup> class goblin_element {
  public:
    using Builder = Builder_;
    using BaseField = Fq;
    using bool_ct = stdlib::bool_t<Builder>;
    using biggroup_tag = goblin_element; // Facilitates a constexpr check IsBigGroup
 
    // 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;
 
    goblin_element() = default;
    goblin_element(const typename NativeGroup::affine_element& input)
        : _x(input.x)
        , _y(input.y)
    {
        // ECCVM requires points at infinity to be represented by (0, 0) coordinates
        if (input.is_point_at_infinity()) {
            _x = Fq(bb::fq(0));
            _y = Fq(bb::fq(0));
        }
    }
 
    // Construct a goblin biggroup element from its coordinates.
    // The on-curve check is skipped as it is performed in ECCVM (assert_on_curve is unused).
    // Point-at-infinity is represented by (0, 0) coordinates, enforced by ECCVM.
    goblin_element(const Fq& x, const Fq& y, [[maybe_unused]] bool assert_on_curve = true)
        : _x(x)
        , _y(y)
    {}
 
    goblin_element(const goblin_element& other) = default;
    goblin_element(goblin_element&& other) noexcept = default;
    goblin_element& operator=(const goblin_element& other) = default;
    goblin_element& operator=(goblin_element&& other) noexcept = default;
    ~goblin_element() = default;
 
    void incomplete_assert_equal(const goblin_element& other,
                                 const std::string msg = "goblin_element::incomplete_assert_equal") const
    {
        _x.assert_equal(other._x, msg + " (x coordinate)");
        _y.assert_equal(other._y, msg + " (y coordinate)");
    }
 
    static goblin_element from_witness(Builder* ctx, const typename NativeGroup::affine_element& input)
    {
        goblin_element out;
 
        // ECCVM requires points at infinity to be represented by (0, 0) coordinates
        if (input.is_point_at_infinity()) {
            out._x = Fq::from_witness(ctx, bb::fq(0));
            out._y = Fq::from_witness(ctx, bb::fq(0));
        } else {
            out._x = Fq::from_witness(ctx, input.x);
            out._y = Fq::from_witness(ctx, input.y);
        }
        out.set_free_witness_tag();
        return out;
    }
 
    void convert_constant_to_fixed_witness(Builder* builder)
    {
        this->_x.convert_constant_to_fixed_witness(builder);
        this->_y.convert_constant_to_fixed_witness(builder);
        this->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();
    }
 
    void validate_on_curve() const
    {
        // happens in goblin eccvm
    }
 
    static goblin_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 goblin_element(x_fq, y_fq);
    }
 
    static goblin_element constant_infinity([[maybe_unused]] Builder* ctx)
    {
        Fq x_fq(ctx, uint256_t(0));
        Fq y_fq(ctx, uint256_t(0));
        return goblin_element(x_fq, y_fq);
    }
 
    goblin_element checked_unconditional_add(const goblin_element& other) const { return operator+(other); }
    goblin_element checked_unconditional_subtract(const goblin_element& other) const { return operator-(other); }
 
    goblin_element operator+(const goblin_element& other) const
    {
        auto builder = get_context(other);
        return batch_mul({ *this, other }, { Fr(builder, 1), Fr(builder, 1) });
    }
 
    goblin_element operator-(const goblin_element& other) const
    {
        auto builder = get_context(other);
        // Check that the internal accumulator is zero
        BB_ASSERT(builder->op_queue->get_accumulator().is_point_at_infinity());
 
        // Compute the result natively, and validate that result + other == *this
        typename NativeGroup::affine_element result_value = typename NativeGroup::affine_element(
            typename NativeGroup::element(get_value()) - typename NativeGroup::element(other.get_value()));
 
        ecc_op_tuple op_tuple;
        op_tuple = builder->queue_ecc_add_accum(other.get_value());
        {
            auto x_lo = Fr::from_witness_index(builder, op_tuple.x_lo);
            auto x_hi = Fr::from_witness_index(builder, op_tuple.x_hi);
            auto y_lo = Fr::from_witness_index(builder, op_tuple.y_lo);
            auto y_hi = Fr::from_witness_index(builder, op_tuple.y_hi);
            x_lo.assert_equal(other._x.limbs[0]);
            x_hi.assert_equal(other._x.limbs[1]);
            y_lo.assert_equal(other._y.limbs[0]);
            y_hi.assert_equal(other._y.limbs[1]);
        }
        // if function queue_ecc_add_accum is used, op_tuple creates as a result of construct_and_populate_ultra_ops
        // function. In case of queue_ecc_add_accum, scalar is zero, (z_1, z_2) = (scalar, 0) = (0, 0) and they just put
        // in the wires.
        builder->update_used_witnesses({ op_tuple.z_1, op_tuple.z_2 });
 
        ecc_op_tuple op_tuple2 = builder->queue_ecc_add_accum(result_value);
        auto x_lo = Fr::from_witness_index(builder, op_tuple2.x_lo);
        auto x_hi = Fr::from_witness_index(builder, op_tuple2.x_hi);
        auto y_lo = Fr::from_witness_index(builder, op_tuple2.y_lo);
        auto y_hi = Fr::from_witness_index(builder, op_tuple2.y_hi);
 
        // if function queue_ecc_add_accum is used, op_tuple creates as a result of construct_and_populate_ultra_ops
        // function. In case of queue_ecc_add_accum, scalar is zero, (z_1, z_2) = (scalar, 0) = (0, 0) and they just put
        // in the wires.
        builder->update_used_witnesses({ op_tuple2.z_1, op_tuple2.z_2 });
 
        Fq result_x(x_lo, x_hi);
        Fq result_y(y_lo, y_hi);
 
        goblin_element result(result_x, result_y);
        {
            ecc_op_tuple op_tuple3 = builder->queue_ecc_eq();
            auto x_lo = Fr::from_witness_index(builder, op_tuple3.x_lo);
            auto x_hi = Fr::from_witness_index(builder, op_tuple3.x_hi);
            auto y_lo = Fr::from_witness_index(builder, op_tuple3.y_lo);
            auto y_hi = Fr::from_witness_index(builder, op_tuple3.y_hi);
 
            x_lo.assert_equal(_x.limbs[0]);
            x_hi.assert_equal(_x.limbs[1]);
            y_lo.assert_equal(_y.limbs[0]);
            y_hi.assert_equal(_y.limbs[1]);
        }
 
        // Set the tag of the result to the union of the tags of inputs
        result.set_origin_tag(OriginTag(get_origin_tag(), other.get_origin_tag()));
        return result;
    }
 
    goblin_element operator-() const
    {
        auto builder = get_context();
        return constant_infinity(builder) - *this;
    }
 
    goblin_element operator+=(const goblin_element& other)
    {
        *this = *this + other;
        return *this;
    }
    goblin_element operator-=(const goblin_element& other)
    {
        *this = *this - other;
        return *this;
    }
    std::array<goblin_element, 2> checked_unconditional_add_sub(const goblin_element& other) const
    {
        return std::array<goblin_element, 2>{ *this + other, *this - other };
    }
 
    goblin_element operator*(const Fr& scalar) const { return batch_mul({ *this }, { scalar }); }
 
    goblin_element conditional_negate(const bool_ct& predicate) const
    {
        goblin_element negated = -(*this);
        goblin_element result(*this);
        result._y = Fq::conditional_assign(predicate, negated._y, result._y);
        return result;
    }
 
    goblin_element conditional_select(const goblin_element& other, const bool_ct& predicate) const
    {
        goblin_element result(*this);
        result._x = Fq::conditional_assign(predicate, other._x, result._x);
        result._y = Fq::conditional_assign(predicate, other._y, result._y);
        return result;
    }
 
    goblin_element normalize() const
    {
        // no need to normalize, all goblin eccvm operations are returned normalized
        return *this;
    }
 
    goblin_element reduce() const
    {
        // no need to reduce, all goblin eccvm operations are returned normalized
        return *this;
    }
 
    goblin_element dbl() const
    {
        auto builder = get_context();
        return batch_mul({ *this }, { Fr(builder, 2) });
    }
    //  interface compatible with biggroup.hpp, the final parameter
    //  handle_edge_cases is not needed as this is always done in the eccvm
    static goblin_element batch_mul(const std::vector<goblin_element>& points,
                                    const std::vector<Fr>& scalars,
                                    const size_t max_num_bits = 0,
                                    const bool handle_edge_cases = false);
 
    // 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
 
    typename NativeGroup::affine_element get_value() const
    {
        bb::fq x_val = _x.get_value().lo;
        bb::fq y_val = _y.get_value().lo;
        auto result = typename NativeGroup::affine_element(x_val, y_val);
        // ECCVM represents point-at-infinity as (0, 0)
        if (x_val == 0 && y_val == 0) {
            result.self_set_infinity();
        }
        return result;
    }
 
    Builder* get_context() const
    {
        if (_x.get_context() != nullptr) {
            return _x.get_context();
        }
        if (_y.get_context() != nullptr) {
            return _y.get_context();
        }
        return nullptr;
    }
 
    Builder* get_context(const goblin_element& other) const
    {
        if (_x.get_context() != nullptr) {
            return _x.get_context();
        }
        if (_y.get_context() != nullptr) {
            return _y.get_context();
        }
        if (other._x.get_context() != nullptr) {
            return other._x.get_context();
        }
        if (other._y.get_context() != nullptr) {
            return other._y.get_context();
        }
        return nullptr;
    }
 
    // ECCVM guarantees infinity is canonically (0, 0), so no normalization needed.
    goblin_element get_standard_form() const { return *this; }
 
    OriginTag get_origin_tag() const { return OriginTag(_x.get_origin_tag(), _y.get_origin_tag()); }
 
    void set_origin_tag(const OriginTag& tag) const
    {
        _x.set_origin_tag(tag);
        _y.set_origin_tag(tag);
    }
 
    void set_free_witness_tag()
    {
        _x.set_free_witness_tag();
        _y.set_free_witness_tag();
    }
 
    void unset_free_witness_tag()
    {
        _x.unset_free_witness_tag();
        _y.unset_free_witness_tag();
    }
    uint32_t set_public() const
    {
        const uint32_t start_idx = _x.set_public();
        _y.set_public();
 
        return start_idx;
    }
 
    // Coordinate accessors (non-owning, const reference)
    const Fq& x() const { return _x; }
    const Fq& y() const { return _y; }
    // Non-const accessors for internal use (e.g., fix_witness in tests)
    Fq& x() { return _x; }
    Fq& y() { return _y; }
 
  private:
    Fq _x;
    Fq _y;
};
 
using BiggroupGoblin = goblin_element<bb::MegaCircuitBuilder,
                                      bb::stdlib::goblin_field<MegaCircuitBuilder>,
                                      stdlib::field_t<MegaCircuitBuilder>,
                                      bb::g1>;
 
template <typename C, typename Fq, typename Fr, typename G>
inline std::ostream& operator<<(std::ostream& os, goblin_element<C, Fq, Fr, G> const& v)
{
    return os << "{ " << v.x() << " , " << v.y() << " }";
}
} // namespace bb::stdlib::element_goblin
 
#include "biggroup_goblin_impl.hpp"