element.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 "affine_element.hpp"
#include "barretenberg/common/compiler_hints.hpp"
#include "barretenberg/common/mem.hpp"
#include "barretenberg/numeric/random/engine.hpp"
#include "barretenberg/numeric/uint256/uint256.hpp"
#include "wnaf.hpp"
#include <array>
#include <random>
#include <vector>
 
namespace bb::group_elements {
 
template <class Fq, class Fr, class Params> class alignas(32) element {
  public:
    static constexpr Fq curve_b = Params::b;
 
    element() noexcept = default;
 
    constexpr element(const Fq& a, const Fq& b, const Fq& c) noexcept;
    constexpr element(const element& other) noexcept;
    constexpr element(element&& other) noexcept;
    constexpr element(const affine_element<Fq, Fr, Params>& other) noexcept;
    ~element() noexcept = default;
 
    static constexpr element one() noexcept { return { Params::one_x, Params::one_y, Fq::one() }; };
    static constexpr element zero() noexcept
    {
        element zero;
        zero.self_set_infinity();
        return zero;
    };
 
    constexpr element& operator=(const element& other) noexcept;
    constexpr element& operator=(element&& other) noexcept;
 
    constexpr operator affine_element<Fq, Fr, Params>() const noexcept;
 
    static element random_element(numeric::RNG* engine = nullptr) noexcept;
 
    constexpr element dbl() const noexcept;
    constexpr void self_dbl() noexcept;
    constexpr void self_mixed_add_or_sub(const affine_element<Fq, Fr, Params>& other, uint64_t predicate) noexcept;
 
    constexpr element operator+(const element& other) const noexcept;
    constexpr element operator+(const affine_element<Fq, Fr, Params>& other) const noexcept;
    constexpr element operator+=(const element& other) noexcept;
    constexpr element operator+=(const affine_element<Fq, Fr, Params>& other) noexcept;
 
    constexpr element operator-(const element& other) const noexcept;
    constexpr element operator-(const affine_element<Fq, Fr, Params>& other) const noexcept;
    constexpr element operator-() const noexcept;
    constexpr element operator-=(const element& other) noexcept;
    constexpr element operator-=(const affine_element<Fq, Fr, Params>& other) noexcept;
 
    friend constexpr element operator+(const affine_element<Fq, Fr, Params>& left, const element& right) noexcept
    {
        return right + left;
    }
    friend constexpr element operator-(const affine_element<Fq, Fr, Params>& left, const element& right) noexcept
    {
        return -right + left;
    }
 
    element operator*(const Fr& exponent) const noexcept;
    element operator*=(const Fr& exponent) noexcept;
 
    // If you end up implementing this, congrats, you've solved the DL problem!
    // P.S. This is a joke, don't even attempt! 😂
    // constexpr Fr operator/(const element& other) noexcept {}
 
    constexpr element normalize() const noexcept;
    static element infinity();
    BB_INLINE constexpr element set_infinity() const noexcept;
    BB_INLINE constexpr void self_set_infinity() noexcept;
    [[nodiscard]] BB_INLINE constexpr bool is_point_at_infinity() const noexcept;
    [[nodiscard]] BB_INLINE constexpr bool on_curve() const noexcept;
    BB_INLINE constexpr bool operator==(const element& other) const noexcept;
 
    static void batch_normalize(element* elements, size_t num_elements) noexcept;
    static void batch_affine_add(const std::span<affine_element<Fq, Fr, Params>>& first_group,
                                 const std::span<affine_element<Fq, Fr, Params>>& second_group,
                                 const std::span<affine_element<Fq, Fr, Params>>& results) noexcept;
    static std::vector<affine_element<Fq, Fr, Params>> batch_mul_with_endomorphism(
        const std::span<const affine_element<Fq, Fr, Params>>& points, const Fr& scalar) noexcept;
 
    static affine_element<Fq, Fr, Params> batch_mul(std::span<const affine_element<Fq, Fr, Params>> points,
                                                    std::span<const Fr> scalars,
                                                    size_t max_num_bits = 0,
                                                    bool with_edgecases = true,
                                                    const Fr& masking_scalar = Fr(1)) noexcept
    {
        return affine_element<Fq, Fr, Params>::batch_mul(points, scalars, max_num_bits, with_edgecases, masking_scalar);
    }
 
    Fq x;
    Fq y;
    Fq z;
 
  private:
    // For test access to mul_without_endomorphism
    friend class TestElementPrivate;
    element mul_without_endomorphism(const Fr& scalar) const noexcept;
    element mul_with_endomorphism(const Fr& scalar) const noexcept;
 
    template <typename = typename std::enable_if<Params::can_hash_to_curve>>
    static element random_coordinates_on_curve(numeric::RNG* engine = nullptr) noexcept;
    // {
    //     bool found_one = false;
    //     Fq yy;
    //     Fq x;
    //     Fq y;
    //     Fq t0;
    //     while (!found_one) {
    //         x = Fq::random_element(engine);
    //         yy = x.sqr() * x + Params::b;
    //         if constexpr (Params::has_a) {
    //             yy += (x * Params::a);
    //         }
    //         y = yy.sqrt();
    //         t0 = y.sqr();
    //         found_one = (yy == t0);
    //     }
    //     return { x, y, Fq::one() };
    // }
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/908) point at inifinty isn't handled
    // To reenable this do NOT do use MSGPACK_FIELDS macro below, instead follow the logic in affine_element
    // MSGPACK_FIELDS(x, y, z);
 
    static void conditional_negate_affine(const affine_element<Fq, Fr, Params>& in,
                                          affine_element<Fq, Fr, Params>& out,
                                          uint64_t predicate) noexcept;
 
    friend std::ostream& operator<<(std::ostream& os, const element& a)
    {
        os << "{ " << a.x << ", " << a.y << ", " << a.z << " }";
        return os;
    }
};
 
template <class Fq, class Fr, class Params> std::ostream& operator<<(std::ostream& os, element<Fq, Fr, Params> const& e)
{
    return os << "x:" << e.x << " y:" << e.y << " z:" << e.z;
}
 
// constexpr element<Fq, Fr, Params>::one = element<Fq, Fr, Params>{ Params::one_x, Params::one_y, Fq::one() };
// constexpr element<Fq, Fr, Params>::point_at_infinity = one.set_infinity();
// constexpr element<Fq, Fr, Params>::curve_b = Params::b;
 
struct ParallelArrayPolicy {
    static constexpr bool ENABLE_PREFETCH = false;
 
    template <typename AffineElement> static constexpr size_t lhs_index(size_t i) noexcept { return i; }
 
    template <typename AffineElement> static constexpr size_t rhs_index(size_t i) noexcept { return i; }
 
    template <typename AffineElement>
    static constexpr size_t output_index(size_t i, [[maybe_unused]] size_t num_pairs) noexcept
    {
        return i;
    }
};
 
struct InterleavedArrayPolicy {
    static constexpr bool ENABLE_PREFETCH = true;
 
    template <typename AffineElement> static constexpr size_t lhs_index(size_t i) noexcept { return i * 2; }
 
    template <typename AffineElement> static constexpr size_t rhs_index(size_t i) noexcept { return (i * 2) + 1; }
 
    template <typename AffineElement> static constexpr size_t output_index(size_t i, size_t num_pairs) noexcept
    {
        return num_pairs + i;
    }
 
    template <typename AffineElement, typename Fq>
    static void prefetch_iteration(const AffineElement* base_points,
                                   const Fq* scratch,
                                   size_t i,
                                   size_t num_pairs) noexcept
    {
        if (i >= 1) {
            size_t prev = i - 1;
            __builtin_prefetch(&base_points[prev * 2]);
            __builtin_prefetch(&base_points[(prev * 2) + 1]);
            __builtin_prefetch(&base_points[num_pairs + prev]);
            __builtin_prefetch(&scratch[prev]);
        }
    }
};
 
} // namespace bb::group_elements
 
#include "./element_impl.hpp"