field.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Sergei], commit: 458fb330efa8c470567ab4b84a8a92a58b00586a}
// external_1:  { status: Complete, auditors: [@ed25519, @JakubHeba (Spearbit)], commit:
// 4433c06ae693451c6f69a2f63b7da6628078d872}
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "../circuit_builders/circuit_builders_fwd.hpp"
#include "../witness/witness.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/transcript/origin_tag.hpp"
#include <functional>
 
namespace bb::stdlib {
// Base case: only one pointer
template <typename T> T* validate_context(T* ptr)
{
    return ptr;
}
 
// Variadic version: compare first with the rest
template <typename T, typename... Ts> T* validate_context(T* first, Ts*... rest)
{
    T* tail = validate_context(rest...);
    if (!first) {
        return tail; // first is null, rely on tail
    }
    if (!tail) {
        return first; // tail is null, use first
    }
    BB_ASSERT(first == tail, "Pointers refer to different builder objects!");
    return first;
}
 
template <typename T, typename Container> T* validate_context(const Container& elements)
{
    T* result = nullptr;
    for (const auto& element : elements) {
        result = validate_context<T>(result, element.get_context());
    }
    return result;
}
 
template <typename Builder> class bool_t;
template <typename Builder_> class field_t {
  public:
    using Builder = Builder_;
 
    static constexpr size_t PUBLIC_INPUTS_SIZE = FR_PUBLIC_INPUTS_SIZE;
 
    // Friend declarations for classes that need direct witness_index access
    template <typename B> friend class bool_t;
    template <typename B, typename T> friend class bigfield;
    template <typename B> friend void mark_witness_as_used(const field_t<B>& field);
 
    mutable Builder* context = nullptr;
 
    mutable bb::fr additive_constant;
    mutable bb::fr multiplicative_constant;
 
  private:
    mutable uint32_t witness_index = IS_CONSTANT;
 
  public:
    mutable OriginTag tag;
 
    field_t(Builder* parent_context = nullptr);
    field_t(Builder* parent_context, const bb::fr& value);
 
    field_t(const int value)
        : context(nullptr)
        , additive_constant(bb::fr(value))
        , multiplicative_constant(bb::fr::one())
        , witness_index(IS_CONSTANT)
    {
        tag = OriginTag::constant();
    }
 
    // NOLINTNEXTLINE(google-runtime-int) intended behavior
    field_t(const unsigned long long value)
        : context(nullptr)
        , additive_constant(bb::fr(value))
        , multiplicative_constant(bb::fr::one())
        , witness_index(IS_CONSTANT)
    {
        tag = OriginTag::constant();
    }
 
    field_t(const unsigned int value)
        : context(nullptr)
        , additive_constant(bb::fr(value))
        , multiplicative_constant(bb::fr::one())
        , witness_index(IS_CONSTANT)
    {
        tag = OriginTag::constant();
    }
 
    // NOLINTNEXTLINE(google-runtime-int) intended behavior
    field_t(const unsigned long value)
        : context(nullptr)
        , additive_constant(bb::fr(value))
        , multiplicative_constant(bb::fr::one())
        , witness_index(IS_CONSTANT)
    {
        tag = OriginTag::constant();
    }
 
    // Construct a constant circuit element from a native field element
    field_t(const bb::fr& value)
        : context(nullptr)
        , additive_constant(value)
        , multiplicative_constant(bb::fr::one())
        , witness_index(IS_CONSTANT)
    {
        tag = OriginTag::constant();
    }
 
    // Construct a constant circuit element from a uint256t, that is implicitly converted to a native field element
    field_t(const uint256_t& value)
        : context(nullptr)
        , additive_constant(value)
        , multiplicative_constant(bb::fr::one())
        , witness_index(IS_CONSTANT)
    {
        tag = OriginTag::constant();
    }
 
    field_t(const witness_t<Builder>& value);
 
    // field_t copy constructor
    field_t(const field_t& other)
        : context(other.context)
        , additive_constant(other.additive_constant)
        , multiplicative_constant(other.multiplicative_constant)
        , witness_index(other.witness_index)
        , tag(other.tag)
    {}
 
    // field_t move constructor
    field_t(field_t&& other) noexcept
        : context(other.context)
        , additive_constant(other.additive_constant)
        , multiplicative_constant(other.multiplicative_constant)
        , witness_index(other.witness_index)
        , tag(other.tag)
    {}
 
    // Copy constructor from a bool_t
    field_t(const bool_t<Builder>& other);
 
    ~field_t() = default;
 
    static constexpr bool is_composite = false;
    static constexpr uint256_t modulus = bb::fr::modulus;
 
    static field_t from_witness_index(Builder* ctx, uint32_t witness_index);
 
    explicit operator bool_t<Builder>() const;
 
    field_t& operator=(const field_t& other)
    {
        if (this == &other) {
            return *this;
        }
        additive_constant = other.additive_constant;
        multiplicative_constant = other.multiplicative_constant;
        witness_index = other.witness_index;
        context = other.context;
        tag = other.tag;
        return *this;
    }
 
    field_t& operator=(field_t&& other) noexcept
    {
        additive_constant = other.additive_constant;
        multiplicative_constant = other.multiplicative_constant;
        witness_index = other.witness_index;
        context = other.context;
        tag = other.tag;
        return *this;
    }
 
    static field_t copy_as_new_witness(Builder& context, field_t const& other)
    {
        auto result = field_t<Builder>(witness_t<Builder>(&context, other.get_value()));
        result.assert_equal(other, "field_t::copy_as_new_witness, assert_equal");
        result.tag = other.tag;
        return result;
    }
 
    field_t operator+(const field_t& other) const;
    field_t operator-(const field_t& other) const;
    field_t operator*(const field_t& other) const;
    field_t operator/(const field_t& other) const;
    bool_t<Builder> operator==(const field_t& other) const;
    bool_t<Builder> operator!=(const field_t& other) const;
 
    field_t divide_no_zero_check(const field_t& other) const;
 
    field_t sqr() const { return operator*(*this); }
 
    field_t pow(const uint32_t& exponent) const;
    // N.B. we implicitly range-constrain 'exponent' to be a 32-bit integer!
    field_t pow(const field_t& exponent) const;
 
    field_t operator+=(const field_t& other)
    {
        *this = *this + other;
        return *this;
    }
    field_t operator-=(const field_t& other)
    {
        *this = *this - other;
        return *this;
    }
    field_t operator*=(const field_t& other)
    {
        *this = *this * other;
        return *this;
    }
    field_t operator/=(const field_t& other)
    {
        *this = *this / other;
        return *this;
    }
 
    // Prefix increment (++x)
    field_t& operator++()
    {
        *this = *this + 1;
        return *this;
    };
 
    // Postfix increment (x++)
    // NOLINTNEXTLINE
    field_t operator++(const int)
    {
        field_t this_before_operation = field_t(*this);
        *this = *this + 1;
        return this_before_operation;
    };
 
    field_t invert() const
    {
        // Since the numerator is a constant 1, the constraint
        //      (this.v * this.mul + this.add) * inverse.v == 1;
        // created by applying `assert_is_not_zero` to `*this` coincides with the constraint created by
        // `divide_no_zero_check`, hence we can safely apply the latter instead of `/` operator.
        auto* ctx = get_context();
        if (is_constant()) {
            BB_ASSERT(!get_value().is_zero(), "field_t::invert denominator is constant 0");
        }
 
        if (get_value().is_zero() && !ctx->failed()) {
            ctx->failure("field_t::invert denominator is 0");
        }
 
        return field_t(fr::one()).divide_no_zero_check(*this);
    }
 
    field_t operator-() const
    {
        field_t result(*this);
        result.additive_constant.self_neg();
        if (!is_constant()) {
            result.multiplicative_constant.self_neg();
        }
        return result;
    }
 
    void set_origin_tag(const OriginTag& new_tag) const { tag = new_tag; }
    OriginTag get_origin_tag() const { return tag; };
 
    void set_free_witness_tag() { tag.set_free_witness(); }
 
    void unset_free_witness_tag() const { tag.unset_free_witness(); }
 
    void clear_round_provenance() const { tag.clear_round_provenance(); }
 
    field_t conditional_negate(const bool_t<Builder>& predicate) const;
 
    void assert_equal(const field_t& rhs, std::string const& msg = "field_t::assert_equal") const;
 
    void assert_not_equal(const field_t& rhs, std::string const& msg = "field_t::assert_not_equal") const;
 
    void assert_is_in_set(const std::vector<field_t>& set, std::string const& msg = "field_t::assert_not_in_set") const;
 
    static field_t conditional_assign_internal(const bool_t<Builder>& predicate,
                                               const field_t& lhs,
                                               const field_t& rhs);
 
    static field_t conditional_assign(const bool_t<Builder>& predicate, const field_t& lhs, const field_t& rhs)
    {
        return conditional_assign_internal(predicate, lhs, rhs).normalize();
    }
 
    static std::array<field_t, 4> preprocess_two_bit_table(const field_t& T0,
                                                           const field_t& T1,
                                                           const field_t& T2,
                                                           const field_t& T3);
    static field_t select_from_two_bit_table(const std::array<field_t, 4>& table,
                                             const bool_t<Builder>& t1,
                                             const bool_t<Builder>& t0);
 
    static std::array<field_t, 8> preprocess_three_bit_table(const field_t& T0,
                                                             const field_t& T1,
                                                             const field_t& T2,
                                                             const field_t& T3,
                                                             const field_t& T4,
                                                             const field_t& T5,
                                                             const field_t& T6,
                                                             const field_t& T7);
    static field_t select_from_three_bit_table(const std::array<field_t, 8>& table,
                                               const bool_t<Builder>& t2,
                                               const bool_t<Builder>& t1,
                                               const bool_t<Builder>& t0);
 
    static void evaluate_linear_identity(const field_t& a,
                                         const field_t& b,
                                         const field_t& c,
                                         const field_t& d,
                                         const std::string& msg = "field_t::evaluate_linear_identity");
    static void evaluate_polynomial_identity(const field_t& a,
                                             const field_t& b,
                                             const field_t& c,
                                             const field_t& d,
                                             const std::string& msg = "field_t::evaluate_polynomial_identity");
 
    static field_t accumulate(const std::vector<field_t>& input);
 
    field_t madd(const field_t& to_mul, const field_t& to_add) const;
 
    field_t add_two(const field_t& add_b, const field_t& add_c) const;
 
    [[nodiscard]] field_t normalize() const;
 
    bb::fr get_value() const;
 
    Builder* get_context() const { return context; }
 
    std::pair<field_t<Builder>, field_t<Builder>> no_wrap_split_at(
        const size_t lsb_index, const size_t num_bits = grumpkin::MAX_NO_WRAP_INTEGER_BIT_LENGTH) const;
 
    bool_t<Builder> is_zero() const;
 
    void create_range_constraint(size_t num_bits, std::string const& msg = "field_t::range_constraint") const;
    void assert_is_not_zero(std::string const& msg = "field_t::assert_is_not_zero") const;
    void assert_is_zero(std::string const& msg = "field_t::assert_is_zero") const;
    bool is_constant() const { return witness_index == IS_CONSTANT; }
    bool is_normalized() const
    {
        return (is_constant() || ((multiplicative_constant == bb::fr::one()) && (additive_constant == bb::fr::zero())));
    };
    uint32_t set_public() const
    {
        BB_ASSERT(!is_constant());
        return context->set_public_input(normalize().witness_index);
    }
 
    void convert_constant_to_fixed_witness(Builder* ctx)
    {
        BB_ASSERT(is_constant());
        BB_ASSERT(ctx);
        context = ctx;
        (*this) = field_t<Builder>(witness_t<Builder>(context, get_value()));
        context->fix_witness(witness_index, get_value());
        unset_free_witness_tag();
    }
 
    static field_t from_witness(Builder* ctx, const bb::fr& input)
    {
        auto result = field_t(witness_t<Builder>(ctx, input));
        result.set_free_witness_tag();
        return result;
    }
 
    // Disallow from_witness for non-bb::fr types to prevent implicit conversions (specifically, using indices rather
    // than values)
    template <typename T> static field_t from_witness(Builder* ctx, const T& input) = delete;
 
    static field_t reconstruct_from_public(const std::span<const field_t, PUBLIC_INPUTS_SIZE>& limbs)
    {
        return limbs[0];
    }
 
    void fix_witness()
    {
        BB_ASSERT(!is_constant());
        BB_ASSERT(context);
        // Normalize first to ensure witness_index points to a witness that contains the actual value
        // (i.e., multiplicative_constant = 1, additive_constant = 0)
        *this = normalize();
        // Let     a := *this;
        //       q_l :=  1
        //       q_c := -*this.get_value()
        // Create an aritmetic gate constraining
        //       a.v * q_l - q_c = 0
        context->fix_witness(witness_index, get_value());
        unset_free_witness_tag();
    }
 
    uint32_t get_witness_index() const { return normalize().witness_index; }
 
    static bool witness_indices_match(const field_t& a, const field_t& b) { return a.witness_index == b.witness_index; }
 
    template <size_t num_bits> bool_t<Builder> ranged_less_than(const field_t<Builder>& other) const
    {
 
        const auto& a = (*this);
        const auto& b = other;
        auto* ctx = validate_context(a.context, b.context);
        if (a.is_constant() && b.is_constant()) {
            return uint256_t(a.get_value()) < uint256_t(b.get_value());
        }
 
        // Let q = (a < b)
        // Assume both a and b are < K where K = 2^{num_bits}
        //    q == 1 <=>  0 < b - a - 1     < K
        //    q == 0 <=>  0 < b - a + K - 1 < K
        // i.e. for any bool value of q:
        //    (b - a - 1) * q + (b - a + K - 1) * (1 - q) = r < K
        //     q * (b - a - b + a) + b - a + K - 1 - (K - 1) * q - q = r < K
        //     b - a + (K - 1) - K * q = r < K
 
        static constexpr uint256_t range_constant = (uint256_t(1) << num_bits);
        // Since in the worst case scenario
        //     r = K - 1 + (K - 1) = 2 * K - 2,
        // to ensure that it never wraps around the field modulus, we impose that it's smaller than half the modulus
        static_assert(range_constant < bb::fr::modulus >> 1,
                      "ranged_less_than: 2^num_bits must be less than half the field modulus.");
 
        bool predicate_witness = uint256_t(a.get_value()) < uint256_t(b.get_value());
        bool_t<Builder> predicate(witness_t<Builder>(ctx, predicate_witness));
        field_t predicate_valid = b.add_two(-(a) + range_constant - 1, -field_t(predicate) * range_constant);
        predicate_valid.create_range_constraint(num_bits);
        return predicate;
    }
 
    // Aliases used in Relations' `accumulate` methods
    using View = field_t;
    using CoefficientAccumulator = field_t;
 
    // Alias used in `biggroup` and `CycleGroup`
    using native = bb::fr;
};
 
template <typename Builder> inline std::ostream& operator<<(std::ostream& os, field_t<Builder> const& v)
{
    return os << v.get_value();
}
} // namespace bb::stdlib