#include <scalar_multiplication.hpp>

Classes
struct	AffineAdditionData
	Temp data structure, one created per thread! More...

struct	BucketAccumulators
	Temp data structure, one created per thread! More...

struct	JacobianBucketAccumulators

struct	MSMData

struct	MSMWorkUnit
	MSMWorkUnit describes an MSM that may be part of a larger MSM. More...

Public Types
using	Element = typename Curve::Element

using	ScalarField = typename Curve::ScalarField

using	BaseField = typename Curve::BaseField

using	AffineElement = typename Curve::AffineElement

using	G1 = AffineElement

using	ThreadWorkUnits = std::vector< MSMWorkUnit >

Static Public Member Functions
static size_t	get_num_rounds (size_t num_points) noexcept

static void	add_affine_points (AffineElement points, const size_t num_points, typename Curve::BaseField scratch_space) noexcept

static void	transform_scalar_and_get_nonzero_scalar_indices (std::span< typename Curve::ScalarField > scalars, std::vector< uint32_t > &consolidated_indices) noexcept
	Convert scalar out of Montgomery form. Populate `consolidated_indices` with nonzero scalar indices.

static std::vector< ThreadWorkUnits >	get_work_units (std::vector< std::span< ScalarField > > &scalars, std::vector< std::vector< uint32_t > > &msm_scalar_indices) noexcept
	Split a multiple multi-scalar-multiplication into equal units of work that can be processed by threads.

static uint32_t	get_scalar_slice (const ScalarField &scalar, size_t round, size_t normal_slice_size) noexcept
	Given a scalar that is NOT in Montgomery form, extract a `slice_size`-bit chunk.

static size_t	get_optimal_log_num_buckets (const size_t num_points) noexcept
	For a given number of points, compute the optimal Pippenger bucket size.

static bool	use_affine_trick (const size_t num_points, const size_t num_buckets) noexcept
	Given a number of points and an optimal bucket size, should we use the affine trick?

static Element	small_pippenger_low_memory_with_transformed_scalars (MSMData &msm_data) noexcept
	Top-level Pippenger algorithm where number of points is small and we are not using the Affine trick.

static Element	pippenger_low_memory_with_transformed_scalars (MSMData &msm_data) noexcept
	Top-level Pippenger algorithm.

static Element	evaluate_small_pippenger_round (MSMData &msm_data, const size_t round_index, JacobianBucketAccumulators &bucket_data, Element previous_round_output, const size_t bits_per_slice) noexcept
	Evaluate a single Pippenger round when we do not use the Affine trick.

static Element	evaluate_pippenger_round (MSMData &msm_data, const size_t round_index, AffineAdditionData &affine_data, BucketAccumulators &bucket_data, Element previous_round_output, const size_t bits_per_slice) noexcept
	Evaluate a single Pippenger round where we use the affine trick.

static void	consume_point_schedule (std::span< const uint64_t > point_schedule, std::span< const AffineElement > points, AffineAdditionData &affine_data, BucketAccumulators &bucket_data, size_t num_input_points_processed, size_t num_queued_affine_points) noexcept
	Given a list of points and target buckets to add into, perform required group operations.

static std::vector< AffineElement >	batch_multi_scalar_mul (std::vector< std::span< const AffineElement > > &points, std::vector< std::span< ScalarField > > &scalars, bool handle_edge_cases=true) noexcept
	Compute multiple multi-scalar multiplications.

static AffineElement	msm (std::span< const AffineElement > points, PolynomialSpan< const ScalarField > _scalars, bool handle_edge_cases=false) noexcept
	Helper method to evaluate a single MSM. Internally calls `batch_multi_scalar_mul`

template<typename BucketType >
static Element	accumulate_buckets (BucketType &bucket_accumulators) noexcept

Static Public Attributes
static constexpr size_t	NUM_BITS_IN_FIELD = ScalarField::modulus.get_msb() + 1

Detailed Description

template<typename Curve>
class bb::scalar_multiplication::MSM< Curve >

Definition at line 15 of file scalar_multiplication.hpp.

Member Typedef Documentation

◆ AffineElement

template<typename Curve >

using bb::scalar_multiplication::MSM< Curve >::AffineElement = typename Curve::AffineElement

Definition at line 20 of file scalar_multiplication.hpp.

◆ BaseField

template<typename Curve >

using bb::scalar_multiplication::MSM< Curve >::BaseField = typename Curve::BaseField

Definition at line 19 of file scalar_multiplication.hpp.

◆ Element

template<typename Curve >

using bb::scalar_multiplication::MSM< Curve >::Element = typename Curve::Element

Definition at line 17 of file scalar_multiplication.hpp.

◆ G1

template<typename Curve >

using bb::scalar_multiplication::MSM< Curve >::G1 = AffineElement

Definition at line 22 of file scalar_multiplication.hpp.

◆ ScalarField

template<typename Curve >

using bb::scalar_multiplication::MSM< Curve >::ScalarField = typename Curve::ScalarField

Definition at line 18 of file scalar_multiplication.hpp.

◆ ThreadWorkUnits

template<typename Curve >

using bb::scalar_multiplication::MSM< Curve >::ThreadWorkUnits = std::vector<MSMWorkUnit>

Definition at line 37 of file scalar_multiplication.hpp.

Member Function Documentation

◆ accumulate_buckets()

template<typename Curve >

template<typename BucketType >

static Element bb::scalar_multiplication::MSM< Curve >::accumulate_buckets ( BucketType & bucket_accumulators )

inlinestaticnoexcept

Definition at line 132 of file scalar_multiplication.hpp.

◆ add_affine_points()

template<typename Curve >

void bb::scalar_multiplication::MSM< Curve >::add_affine_points	(	typename Curve::AffineElement *	points,
		const size_t	num_points,
		typename Curve::BaseField *	scratch_space
	)

staticnoexcept

The trick is to compute the product x_1x_2...x_n , whilst storing all of the temporary products. i.e. we have an array A = [x_1, x_1x_2, ..., x_1x_2...x_n] We then compute a single inverse: I = 1 / x_1x_2...x_n Finally, we can use our accumulated products, to quotient out individual inverses. We can get an individual inverse at index i, by computing I.A_{i-1}.(x_nx_n-1...x_i+1) The last product term we can compute on-the-fly, as it grows by one element for each additional inverse that we require.

TLDR: amortized cost of a modular inverse is 3 field multiplications per inverse. Which means we can compute a point addition with SIX field multiplications in total. The traditional Jacobian-coordinate formula requires 11.

There is a catch though - we need large sequences of independent point additions! i.e. the output from one point addition in the sequence is NOT an input to any other point addition in the sequence.

We can re-arrange the Pippenger algorithm to get this property, but it's...complicated

Template Parameters

Curve

Parameters

points	points to be added pairwise; result is stored in the latter half of the array
num_points
scratch_space	coordinate field scratch space needed for batched inversion

Definition at line 328 of file scalar_multiplication.cpp.

◆ batch_multi_scalar_mul()

template<typename Curve >

std::vector< typename Curve::AffineElement > bb::scalar_multiplication::MSM< Curve >::batch_multi_scalar_mul	(	std::vector< std::span< const AffineElement > > &	points,
		std::vector< std::span< ScalarField > > &	scalars,
		bool	handle_edge_cases = `true`
	)

staticnoexcept

Compute multiple multi-scalar multiplications.

If we need to perform multiple MSMs, this method will be more efficient than calling msm repeatedly This is because this method will be able to dispatch equal work to all threads without splitting the input msms up so much. The Pippenger algorithm runtime is O(N/log(N)) so there will be slight gains as each inner-thread MSM will have a larger N

Template Parameters

Curve

Parameters

points
scalars

Returns: std::vector<typename Curve::AffineElement>

Definition at line 763 of file scalar_multiplication.cpp.

◆ consume_point_schedule()

template<typename Curve >

void bb::scalar_multiplication::MSM< Curve >::consume_point_schedule	(	std::span< const uint64_t >	point_schedule,
		std::span< const AffineElement >	points,
		AffineAdditionData &	affine_data,
		BucketAccumulators &	bucket_data,
		size_t	num_input_points_processed,
		size_t	num_queued_affine_points
	)

staticnoexcept

Given a list of points and target buckets to add into, perform required group operations.

This algorithm uses exclusively affine group operations, using batch inversions to amortise costs

Template Parameters

Curve

Parameters

point_schedule
points
affine_data
bucket_data
num_input_points_processed
num_queued_affine_points

Definition at line 561 of file scalar_multiplication.cpp.

◆ evaluate_pippenger_round()

template<typename Curve >

Curve::Element bb::scalar_multiplication::MSM< Curve >::evaluate_pippenger_round	(	MSMData &	msm_data,
		const size_t	round_index,
		AffineAdditionData &	affine_data,
		BucketAccumulators &	bucket_data,
		Element	previous_round_output,
		const size_t	bits_per_slice
	)

staticnoexcept

Evaluate a single Pippenger round where we use the affine trick.

Template Parameters

Curve

Parameters

msm_data
round_index
affine_data
bucket_data
previous_round_output
bits_per_slice

Returns: Curve::Element

Definition at line 497 of file scalar_multiplication.cpp.

◆ evaluate_small_pippenger_round()

template<typename Curve >

Curve::Element bb::scalar_multiplication::MSM< Curve >::evaluate_small_pippenger_round	(	MSMData &	msm_data,
		const size_t	round_index,
		JacobianBucketAccumulators &	bucket_data,
		Element	previous_round_output,
		const size_t	bits_per_slice
	)

staticnoexcept

Evaluate a single Pippenger round when we do not use the Affine trick.

Template Parameters

Curve

Parameters

msm_data
round_index
bucket_data
previous_round_output
bits_per_slice

Returns: Curve::Element

Definition at line 441 of file scalar_multiplication.cpp.

◆ get_num_rounds()

template<typename Curve >

static size_t bb::scalar_multiplication::MSM< Curve >::get_num_rounds ( size_t num_points )

inlinestaticnoexcept

Definition at line 85 of file scalar_multiplication.hpp.

◆ get_optimal_log_num_buckets()

template<typename Curve >

size_t bb::scalar_multiplication::MSM< Curve >::get_optimal_log_num_buckets ( const size_t num_points )

staticnoexcept

For a given number of points, compute the optimal Pippenger bucket size.

Template Parameters

Curve

Parameters

num_points

Returns: constexpr size_t

Definition at line 232 of file scalar_multiplication.cpp.

◆ get_scalar_slice()

template<typename Curve >

uint32_t bb::scalar_multiplication::MSM< Curve >::get_scalar_slice	(	const ScalarField &	scalar,
		size_t	round,
		size_t	normal_slice_size
	)

staticnoexcept

Given a scalar that is NOT in Montgomery form, extract a slice_size-bit chunk.

At round i, we extract slice_size * (i-1) to slice_sice * i most significant bits.

Template Parameters

Curve

Parameters

scalar
round
normal_slice_size

Returns: uint32_t

Definition at line 201 of file scalar_multiplication.cpp.

◆ get_work_units()

template<typename Curve >

std::vector< typename MSM< Curve >::ThreadWorkUnits > bb::scalar_multiplication::MSM< Curve >::get_work_units	(	std::vector< std::span< ScalarField > > &	scalars,
		std::vector< std::vector< uint32_t > > &	msm_scalar_indices
	)

staticnoexcept

Split a multiple multi-scalar-multiplication into equal units of work that can be processed by threads.

The goal is to compute the total number of multiplications needed, and assign each thread a set of MSMs such that each thread performs equivalent work. We will split up an MSM into multiple MSMs if this is required.

Template Parameters

Curve

Parameters

scalars
msm_scalar_indices

Returns: std::vector<typename MSM<Curve>::ThreadWorkUnits>

Definition at line 117 of file scalar_multiplication.cpp.

◆ msm()

template<typename Curve >

Curve::AffineElement bb::scalar_multiplication::MSM< Curve >::msm	(	std::span< const AffineElement >	points,
		PolynomialSpan< const ScalarField >	_scalars,
		bool	handle_edge_cases = `false`
	)

staticnoexcept

Helper method to evaluate a single MSM. Internally calls batch_multi_scalar_mul

Template Parameters

Curve

Parameters

points
_scalars

Returns: Curve::AffineElement

Definition at line 846 of file scalar_multiplication.cpp.

◆ pippenger_low_memory_with_transformed_scalars()

template<typename Curve >

Curve::Element bb::scalar_multiplication::MSM< Curve >::pippenger_low_memory_with_transformed_scalars ( MSMData & msm_data )

staticnoexcept

Top-level Pippenger algorithm.

Template Parameters

Curve

Parameters

msm_data

Returns: Curve::AffineElement

Definition at line 405 of file scalar_multiplication.cpp.

◆ small_pippenger_low_memory_with_transformed_scalars()

template<typename Curve >

Curve::Element bb::scalar_multiplication::MSM< Curve >::small_pippenger_low_memory_with_transformed_scalars ( MSMData & msm_data )

staticnoexcept

Top-level Pippenger algorithm where number of points is small and we are not using the Affine trick.

Template Parameters

Curve

Parameters

msm_data

Returns: Curve::AffineElement

Definition at line 380 of file scalar_multiplication.cpp.

◆ transform_scalar_and_get_nonzero_scalar_indices()

template<typename Curve >

void bb::scalar_multiplication::MSM< Curve >::transform_scalar_and_get_nonzero_scalar_indices	(	std::span< typename Curve::ScalarField >	scalars,
		std::vector< uint32_t > &	consolidated_indices
	)

staticnoexcept

Convert scalar out of Montgomery form. Populate consolidated_indices with nonzero scalar indices.

Template Parameters

Curve

Parameters

scalars
consolidated_indices

Definition at line 55 of file scalar_multiplication.cpp.

◆ use_affine_trick()

template<typename Curve >

bool bb::scalar_multiplication::MSM< Curve >::use_affine_trick	(	const size_t	num_points,
		const size_t	num_buckets
	)

staticnoexcept

Given a number of points and an optimal bucket size, should we use the affine trick?

Template Parameters

Curve

Parameters

num_points
num_buckets

Returns: true; false

Definition at line 261 of file scalar_multiplication.cpp.

Member Data Documentation

◆ NUM_BITS_IN_FIELD

template<typename Curve >

constexpr size_t bb::scalar_multiplication::MSM< Curve >::NUM_BITS_IN_FIELD = ScalarField::modulus.get_msb() + 1

staticconstexpr

Definition at line 23 of file scalar_multiplication.hpp.

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

src/barretenberg/ecc/scalar_multiplication/scalar_multiplication.hpp
src/barretenberg/ecc/scalar_multiplication/scalar_multiplication.cpp

Classes

Public Types

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ AffineElement

◆ BaseField

◆ Element

◆ G1

◆ ScalarField

◆ ThreadWorkUnits

Member Function Documentation

◆ accumulate_buckets()

◆ add_affine_points()

◆ batch_multi_scalar_mul()

◆ consume_point_schedule()

◆ evaluate_pippenger_round()

◆ evaluate_small_pippenger_round()

◆ get_num_rounds()

◆ get_optimal_log_num_buckets()

◆ get_scalar_slice()

◆ get_work_units()

◆ msm()

◆ pippenger_low_memory_with_transformed_scalars()

◆ small_pippenger_low_memory_with_transformed_scalars()

◆ transform_scalar_and_get_nonzero_scalar_indices()

◆ use_affine_trick()

Member Data Documentation

◆ NUM_BITS_IN_FIELD