Class for handling fast batched affine addition of large sets of EC points. More...

#include <batched_affine_addition.hpp>

Classes
struct	AdditionSequences

struct	ThreadData

Static Public Member Functions
static std::vector< G1 >	add_in_place (const std::span< G1 > &points, const std::vector< size_t > &sequence_counts)
	Given a set of points and sequence counts, peform addition to reduce each sequence to a single point.

Private Types
using	G1 = typename Curve::AffineElement

using	Fr = typename Curve::ScalarField

using	Fq = typename Curve::BaseField

Static Private Member Functions
static ThreadData	construct_thread_data (const std::span< G1 > &points, const std::vector< size_t > &sequence_counts, const std::span< Fq > &scratch_space)
	Construct the set of AdditionSequences to be handled by each thread.

static std::span< Fq >	batch_compute_point_addition_slope_inverses (const AdditionSequences &add_sequences)
	Batch compute inverses needed for a set of affine point addition sequences.

static void	batched_affine_add_in_place (AdditionSequences add_sequences)
	Internal method for in-place summation of a single set of addition sequences.

static G1	affine_add_with_denominator (const G1 &point_1, const G1 &point_2, const Fq &denominator)
	Add two affine elements with the inverse in the slope term \lambda provided as input.

Detailed Description

template<typename Curve>
class bb::BatchedAffineAddition< Curve >

Class for handling fast batched affine addition of large sets of EC points.

Useful for pre-reducing the SRS points via summation for commitments to polynomials with large ranges of constant coefficients.

Template Parameters

Curve

Definition at line 23 of file batched_affine_addition.hpp.

Member Typedef Documentation

◆ Fq

template<typename Curve >

using bb::BatchedAffineAddition< Curve >::Fq = typename Curve::BaseField

private

Definition at line 26 of file batched_affine_addition.hpp.

◆ Fr

template<typename Curve >

using bb::BatchedAffineAddition< Curve >::Fr = typename Curve::ScalarField

private

Definition at line 25 of file batched_affine_addition.hpp.

◆ G1

template<typename Curve >

using bb::BatchedAffineAddition< Curve >::G1 = typename Curve::AffineElement

private

Definition at line 24 of file batched_affine_addition.hpp.

Member Function Documentation

◆ add_in_place()

template<typename Curve >

std::vector< typename BatchedAffineAddition< Curve >::G1 > bb::BatchedAffineAddition< Curve >::add_in_place	(	const std::span< G1 > &	points,
		const std::vector< size_t > &	sequence_counts
	)

static

Given a set of points and sequence counts, peform addition to reduce each sequence to a single point.

Reduce each sequence to a single point via repeated rounds of pairwise addition. (If the length of the sequence is odd in a given round, the unpaired point is simply carried over to the next round). The inverses needed in the addition formula are batch computed in a single go for all additions to be performed across all sequences in a given round.

Note

: Multithreading is achieved by evenly distributing the points across the optimal number of available threads. This can result in the bisecting of some sequences which is acounted for in the final result by further summing the reduced points that resulted from a sequence split across two or more threads. An example with two threads and three add sequences:

                |------------------------| Points
                |------------|-----------| Thread boundaries
                |---|-----------|--------| Addition sequence boundaries
                |---|--------|---|-------| New addition sequence boundaries
                | 0 |    1   | 1 |   2   | Tags

Each thread recieves two add sequences and reduces them to two points. The resulting four points are further reduced to three by summing points that share a sequence tag.

Parameters

points	Set of points to be reduced in place to num-sequences many points
sequence_counts	lengths of the individual sequences to be summed (assumed continguous in points)

Returns: std::vector<G1> the set of reduced points in contiguous memory

Definition at line 18 of file batched_affine_addition.cpp.

◆ affine_add_with_denominator()

template<typename Curve >

static G1 bb::BatchedAffineAddition< Curve >::affine_add_with_denominator	(	const G1 &	point_1,
		const G1 &	point_2,
		const Fq &	denominator
	)

inlinestaticprivate

Add two affine elements with the inverse in the slope term \lambda provided as input.

The sum of two points (x1, y1), (x2, y2) is given by x3 = \lambda^2 - x1 - x2, y3 = \lambda*(x1 - x3) - y1, where \lambda = (y2 - y1)/(x2 - x1). When performing many additions at once, it is more efficient to batch compute the inverse component of \lambda for each pair of points. This gives rise to the need for a method like this one.

Template Parameters

Curve

Parameters

point_1	(x1, y1)
point_2	(x2, y2)
denominator	1/(x2 - x1)

Returns: Curve::AffineElement

Definition at line 116 of file batched_affine_addition.hpp.

◆ batch_compute_point_addition_slope_inverses()

template<typename Curve >

std::span< typename BatchedAffineAddition< Curve >::Fq > bb::BatchedAffineAddition< Curve >::batch_compute_point_addition_slope_inverses ( const AdditionSequences & add_sequences )

staticprivate

Batch compute inverses needed for a set of affine point addition sequences.

Addition of points P_1, P_2 requires computation of a term of the form 1/(P_2.x - P_1.x). For efficiency, these terms are computed all at once for a full set of addition sequences using batch inversion.

Template Parameters

Curve

Parameters

add_sequences

Definition at line 138 of file batched_affine_addition.cpp.

◆ batched_affine_add_in_place()

template<typename Curve >

void bb::BatchedAffineAddition< Curve >::batched_affine_add_in_place ( AdditionSequences add_sequences )

staticprivate

Internal method for in-place summation of a single set of addition sequences.

Template Parameters

Curve

Parameters

addition_sequences Set of points and counts indicating number of points in each addition chain

Definition at line 193 of file batched_affine_addition.cpp.

◆ construct_thread_data()

template<typename Curve >

BatchedAffineAddition< Curve >::ThreadData bb::BatchedAffineAddition< Curve >::construct_thread_data	(	const std::span< G1 > &	points,
		const std::vector< size_t > &	sequence_counts,
		const std::span< Fq > &	scratch_space
	)

staticprivate

Construct the set of AdditionSequences to be handled by each thread.

To optimize thread utilization, points are distributed evenly across the number of available threads. This may in general result in the splitting of individual addition sequences across two or more threads. This is accounted for by assigning a tag to each sequence so that the results can be further combined post-facto to ensure that the final number of points corresponds to the number of addition sequences.

Parameters

points
sequence_counts
scratch_space	Space for computing and storing the point addition slope denominators

Returns: ThreadData

Definition at line 52 of file batched_affine_addition.cpp.

The documentation for this class was generated from the following files:

src/barretenberg/ecc/batched_affine_addition/batched_affine_addition.hpp
src/barretenberg/ecc/batched_affine_addition/batched_affine_addition.cpp

Classes

Static Public Member Functions

Private Types

Static Private Member Functions

Detailed Description

Member Typedef Documentation

◆ Fq

◆ Fr

◆ G1

Member Function Documentation

◆ add_in_place()

◆ affine_add_with_denominator()

◆ batch_compute_point_addition_slope_inverses()

◆ batched_affine_add_in_place()

◆ construct_thread_data()