batched_affine_addition.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 "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
#include <cstddef>
#include <cstdint>
 
namespace bb {
 
template <typename Curve> class BatchedAffineAddition {
    using G1 = typename Curve::AffineElement;
    using Fr = typename Curve::ScalarField;
    using Fq = typename Curve::BaseField;
 
    // Struct describing a set of points to be reduced to num-sequence-counts-many points via summation of each sequence
    struct AdditionSequences {
        std::vector<size_t> sequence_counts;
        std::span<G1> points;
        std::span<Fq> scratch_space;
    };
 
    // Collection of addition sequences to be handled by each thread
    struct ThreadData {
        std::vector<AdditionSequences> addition_sequences;
        std::vector<std::vector<size_t>> sequence_tags; // allows for the recombining of sequences split across threads
    };
 
  public:
    static std::vector<G1> add_in_place(const std::span<G1>& points, const std::vector<size_t>& sequence_counts);
 
  private:
    static ThreadData construct_thread_data(const std::span<G1>& points,
                                            const std::vector<size_t>& sequence_counts,
                                            const std::span<Fq>& scratch_space);
 
    static std::span<Fq> batch_compute_point_addition_slope_inverses(const AdditionSequences& add_sequences);
 
    static void batched_affine_add_in_place(AdditionSequences add_sequences);
 
    static inline G1 affine_add_with_denominator(const G1& point_1, const G1& point_2, const Fq& denominator)
    {
        const auto& x1 = point_1.x;
        const auto& y1 = point_1.y;
        const auto& x2 = point_2.x;
        const auto& y2 = point_2.y;
 
        const Fq lambda = denominator * (y2 - y1);
        Fq x3 = lambda.sqr() - x2 - x1;
        Fq y3 = lambda * (x1 - x3) - y1;
        return { x3, y3 };
    }
};
 
} // namespace bb