Generates plookup tables required to perform fixed-base scalar multiplication over a fixed number of points. More...

#include <fixed_base.hpp>

Inheritance diagram for bb::plookup::fixed_base::table:

Public Types
using	affine_element = grumpkin::g1::affine_element

using	element = grumpkin::g1::element

using	single_lookup_table = std::vector< affine_element >

using	fixed_base_scalar_mul_tables = std::vector< single_lookup_table >

using	all_multi_tables = std::array< fixed_base_scalar_mul_tables, NUM_FIXED_BASE_MULTI_TABLES >

Public Member Functions
template<size_t num_table_bits>
grumpkin::g1::affine_element	generate_generator_offset (const grumpkin::g1::affine_element &input)
	For a fixed-base lookup of size `num_table_bits` and an input base point `input`, return the total contrbution in the scalar multiplication output from the offset generators in the lookup tables.

Static Public Member Functions
static constexpr affine_element	lhs_generator_point ()

static constexpr affine_element	rhs_generator_point ()

static single_lookup_table	generate_single_lookup_table (const affine_element &base_point, const affine_element &offset_generator)
	Given a base_point [P] and an offset_generator [G], compute a lookup table of MAX_TABLE_SIZE that contains the following terms:

template<size_t num_bits>
static fixed_base_scalar_mul_tables	generate_tables (const affine_element &input)
	For a given base point [P], compute the lookup tables required to traverse a `num_bits` sized lookup.

template<size_t num_table_bits>
static affine_element	generate_generator_offset (const affine_element &input)

static affine_element	lhs_base_point_lo ()

static affine_element	lhs_base_point_hi ()

static affine_element	rhs_base_point_lo ()

static affine_element	rhs_base_point_hi ()

static const all_multi_tables &	fixed_base_tables ()

static const std::array< affine_element, table::NUM_FIXED_BASE_MULTI_TABLES > &	fixed_base_table_offset_generators ()
	offset generators!

static bool	lookup_table_exists_for_point (const affine_element &input)
	Given a point, do we have a precomputed lookup table for this point?

static std::optional< std::array< MultiTableId, 2 > >	get_lookup_table_ids_for_point (const affine_element &input)
	Given a point, return (if it exists) the 2 MultiTableId's that correspond to the LO_SCALAR, HI_SCALAR MultiTables.

static std::optional< affine_element >	get_generator_offset_for_table_id (MultiTableId table_id)
	Given a table id, return the offset generator term that will be present in the final scalar mul output.

template<size_t multitable_index>
static BasicTable	generate_basic_fixed_base_table (BasicTableId id, size_t basic_table_index, size_t table_index)
	Generate a single fixed-base-scalar-mul plookup table.

template<size_t multitable_index, size_t num_bits>
static MultiTable	get_fixed_base_table (MultiTableId id)
	Generate a multi-table that describes the lookups required to cover a fixed-base-scalar-mul of `num_bits`

template<size_t multitable_index, size_t table_index>
static std::array< bb::fr, 2 >	get_basic_fixed_base_table_values (const std::array< uint64_t, 2 > key)

Static Public Member Functions inherited from bb::plookup::FixedBaseParams
template<size_t num_bits>
static constexpr size_t	get_num_tables_per_multi_table () noexcept
	For a scalar multiplication table that covers input scalars up to `(1 << num_bits) - 1`, how many individual lookup tables of max size BITS_PER_TABLE do we need? (e.g. if BITS_PER_TABLE = 9, for `num_bits = 126` it's 14. For `num_bits = 128` it's 15)

template<size_t multitable_index>
static constexpr size_t	get_num_bits_of_multi_table ()
	For a given multitable index, how many scalar mul bits are we traversing with our multitable?

Static Public Attributes
static constexpr uint256_t	MAX_LO_SCALAR = uint256_t(1) << BITS_PER_LO_SCALAR

Static Public Attributes inherited from bb::plookup::FixedBaseParams
static constexpr size_t	BITS_PER_TABLE = 9

static constexpr size_t	BITS_ON_CURVE = 254

static constexpr size_t	BITS_PER_LO_SCALAR = 128

static constexpr size_t	BITS_PER_HI_SCALAR = BITS_ON_CURVE - BITS_PER_LO_SCALAR

static constexpr size_t	MAX_TABLE_SIZE = (1UL) << BITS_PER_TABLE

static constexpr size_t	MAX_NUM_TABLES_IN_MULTITABLE

static constexpr size_t	NUM_POINTS = 2

static constexpr size_t	NUM_FIXED_BASE_MULTI_TABLES = NUM_POINTS * 2

static constexpr size_t	NUM_TABLES_PER_LO_MULTITABLE

static constexpr size_t	NUM_TABLES_PER_HI_MULTITABLE

static constexpr size_t	NUM_BASIC_TABLES_PER_BASE_POINT

static constexpr size_t	NUM_FIXED_BASE_BASIC_TABLES = NUM_BASIC_TABLES_PER_BASE_POINT * NUM_POINTS

Detailed Description

Generates plookup tables required to perform fixed-base scalar multiplication over a fixed number of points.

Definition at line 22 of file fixed_base.hpp.

Member Typedef Documentation

◆ affine_element

using bb::plookup::fixed_base::table::affine_element = grumpkin::g1::affine_element

Definition at line 24 of file fixed_base.hpp.

◆ all_multi_tables

using bb::plookup::fixed_base::table::all_multi_tables = std::array<fixed_base_scalar_mul_tables, NUM_FIXED_BASE_MULTI_TABLES>

Definition at line 28 of file fixed_base.hpp.

◆ element

using bb::plookup::fixed_base::table::element = grumpkin::g1::element

Definition at line 25 of file fixed_base.hpp.

◆ fixed_base_scalar_mul_tables

using bb::plookup::fixed_base::table::fixed_base_scalar_mul_tables = std::vector<single_lookup_table>

Definition at line 27 of file fixed_base.hpp.

◆ single_lookup_table

using bb::plookup::fixed_base::table::single_lookup_table = std::vector<affine_element>

Definition at line 26 of file fixed_base.hpp.

Member Function Documentation

◆ fixed_base_table_offset_generators()

const std::array< table::affine_element, table::NUM_FIXED_BASE_MULTI_TABLES > & bb::plookup::fixed_base::table::fixed_base_table_offset_generators ( )

static

offset generators!

We add a unique "offset generator" into each lookup table to ensure that we never trigger incomplete addition formulae for short Weierstrass curves. The offset generators are linearly independent from the fixed-base points we're multiplying, ensuring that a collision is as likely as solving the discrete logarithm problem. For example, imagine a 2-bit lookup table of a point [P]. The table would normally contain { 0.[P], 1.[P], 2.[P], 3.[P]}. But, we dont want to have to handle points at infinity and we also don't want to deal with windowed-non-adjacent-form complexities. Instead, we derive offset generator [G] and make the table equal to { [G] + 0.[P], [G] + 1.[P], [G] + 2.[P], [G] + 3.[P]}. Each table uses a unique offset generator to prevent collisions. The final scalar multiplication output will have a precisely-known contribution from the offset generators, which can then be subtracted off with a single point subtraction.

NOTE: Without putting these computed lookup tables behind statics there is a timing issue when compiling for the WASM target. hypothesis: because it's 32-bit it has different static init order and this helps?

Definition at line 301 of file fixed_base.cpp.

◆ fixed_base_tables()

const table::all_multi_tables & bb::plookup::fixed_base::table::fixed_base_tables ( )

static

NOTE: Without putting these computed lookup tables behind statics there is a timing issue when compiling for the WASM target. hypothesis: because it's 32-bit it has different static init order and this helps?

Definition at line 285 of file fixed_base.cpp.

◆ generate_basic_fixed_base_table()

template<size_t multitable_index>

template BasicTable bb::plookup::fixed_base::table::generate_basic_fixed_base_table< 3 >	(	BasicTableId	id,
		size_t	basic_table_index,
		size_t	table_index
	)

static

Generate a single fixed-base-scalar-mul plookup table.

Template Parameters

multitable_index,which of our 4 multitables is this basic table a part of?

Parameters

id	the BasicTableId
basic_table_index	plookup table index
table_index	This index describes which bit-slice the basic table corresponds to. i.e. table_index = 0 maps to the least significant bit slice

Returns: BasicTable

Definition at line 192 of file fixed_base.cpp.

◆ generate_generator_offset() [1/2]

template<size_t num_table_bits>

static affine_element bb::plookup::fixed_base::table::generate_generator_offset ( const affine_element & input )

static

◆ generate_generator_offset() [2/2]

template<size_t num_table_bits>

grumpkin::g1::affine_element bb::plookup::fixed_base::table::generate_generator_offset ( const grumpkin::g1::affine_element & input )

For a fixed-base lookup of size num_table_bits and an input base point input, return the total contrbution in the scalar multiplication output from the offset generators in the lookup tables.

Note: We need the base point as an input parameter because we derive the offset generator using our hash-to-curve algorithm, where the base point is used as the domain separator. Ensures generator points cannot collide with base points w/o solving the dlog problem

Template Parameters

num_table_bits

Parameters

input

Returns: grumpkin::g1::affine_element

Definition at line 91 of file fixed_base.cpp.

◆ generate_single_lookup_table()

table::single_lookup_table bb::plookup::fixed_base::table::generate_single_lookup_table	(	const affine_element &	base_point,
		const affine_element &	offset_generator
	)

inlinestatic

Given a base_point [P] and an offset_generator [G], compute a lookup table of MAX_TABLE_SIZE that contains the following terms:

{ [G] + 0.[P] , [G] + 1.[P], ..., [G] + (MAX_TABLE_SIZE - 1).[P] }

Parameters

base_point
offset_generator

Returns: table::single_lookup_table

Definition at line 27 of file fixed_base.cpp.

◆ generate_tables()

template<size_t num_bits>

table::fixed_base_scalar_mul_tables bb::plookup::fixed_base::table::generate_tables ( const affine_element & input )

static

For a given base point [P], compute the lookup tables required to traverse a num_bits sized lookup.

i.e. call generate_single_lookup_table for the following base points:

{ [P], [P] * (1 << BITS_PER_TABLE), [P] * (1 << BITS_PER_TABLE * 2), ..., [P] * (1 << BITS_PER_TABLE * (NUM_TABLES - 1)) }

Template Parameters

num_bits

Parameters

input

Returns: table::fixed_base_scalar_mul_tables

Definition at line 57 of file fixed_base.cpp.

◆ get_basic_fixed_base_table_values()

template<size_t multitable_index, size_t table_index>

static std::array< bb::fr, 2 > bb::plookup::fixed_base::table::get_basic_fixed_base_table_values ( const std::array< uint64_t, 2 > key )

inlinestatic

Definition at line 95 of file fixed_base.hpp.

◆ get_fixed_base_table()

template<size_t multitable_index, size_t num_bits>

MultiTable bb::plookup::fixed_base::table::get_fixed_base_table ( MultiTableId id )

static

Generate a multi-table that describes the lookups required to cover a fixed-base-scalar-mul of num_bits

Template Parameters

multitable_index,which	one of our 4 multitables are we generating?
num_bits,this	will be either `BITS_PER_LO_SCALAR` or `BITS_PER_HI_SCALAR`

Parameters

id

Returns: MultiTable

Definition at line 236 of file fixed_base.cpp.

◆ get_generator_offset_for_table_id()

std::optional< grumpkin::g1::affine_element > bb::plookup::fixed_base::table::get_generator_offset_for_table_id ( MultiTableId table_id )

static

Given a table id, return the offset generator term that will be present in the final scalar mul output.

Return value is std::optional in case the table_id is not a fixed-base table.

Parameters

table_id

Returns: std::optional<affine_element>

Definition at line 144 of file fixed_base.cpp.

◆ get_lookup_table_ids_for_point()

std::optional< std::array< MultiTableId, 2 > > bb::plookup::fixed_base::table::get_lookup_table_ids_for_point ( const affine_element & input )

static

Given a point, return (if it exists) the 2 MultiTableId's that correspond to the LO_SCALAR, HI_SCALAR MultiTables.

Parameters

input

Returns: std::optional<std::array<MultiTableId, 2>>

Definition at line 124 of file fixed_base.cpp.

◆ lhs_base_point_hi()

static affine_element bb::plookup::fixed_base::table::lhs_base_point_hi ( )

inlinestatic

Definition at line 52 of file fixed_base.hpp.

◆ lhs_base_point_lo()

static affine_element bb::plookup::fixed_base::table::lhs_base_point_lo ( )

inlinestatic

Definition at line 51 of file fixed_base.hpp.

◆ lhs_generator_point()

static constexpr affine_element bb::plookup::fixed_base::table::lhs_generator_point ( )

inlinestaticconstexpr

Definition at line 30 of file fixed_base.hpp.

◆ lookup_table_exists_for_point()

bool bb::plookup::fixed_base::table::lookup_table_exists_for_point ( const affine_element & input )

static

Given a point, do we have a precomputed lookup table for this point?

Parameters

input

Returns: true; false

Definition at line 112 of file fixed_base.cpp.

◆ rhs_base_point_hi()

static affine_element bb::plookup::fixed_base::table::rhs_base_point_hi ( )

inlinestatic

Definition at line 58 of file fixed_base.hpp.

◆ rhs_base_point_lo()

static affine_element bb::plookup::fixed_base::table::rhs_base_point_lo ( )

inlinestatic

Definition at line 57 of file fixed_base.hpp.

◆ rhs_generator_point()

static constexpr affine_element bb::plookup::fixed_base::table::rhs_generator_point ( )

inlinestaticconstexpr

Definition at line 34 of file fixed_base.hpp.

Member Data Documentation

◆ MAX_LO_SCALAR

constexpr uint256_t bb::plookup::fixed_base::table::MAX_LO_SCALAR = uint256_t(1) << BITS_PER_LO_SCALAR

staticconstexpr

Definition at line 45 of file fixed_base.hpp.

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

src/barretenberg/stdlib_circuit_builders/plookup_tables/fixed_base/fixed_base.hpp
src/barretenberg/stdlib_circuit_builders/plookup_tables/fixed_base/fixed_base.cpp

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ affine_element

◆ all_multi_tables

◆ element

◆ fixed_base_scalar_mul_tables

◆ single_lookup_table

Member Function Documentation

◆ fixed_base_table_offset_generators()

◆ fixed_base_tables()

◆ generate_basic_fixed_base_table()

◆ generate_generator_offset() [1/2]

◆ generate_generator_offset() [2/2]

◆ generate_single_lookup_table()

◆ generate_tables()

◆ get_basic_fixed_base_table_values()

◆ get_fixed_base_table()

◆ get_generator_offset_for_table_id()

◆ get_lookup_table_ids_for_point()

◆ lhs_base_point_hi()

◆ lhs_base_point_lo()

◆ lhs_generator_point()

◆ lookup_table_exists_for_point()

◆ rhs_base_point_hi()

◆ rhs_base_point_lo()

◆ rhs_generator_point()

Member Data Documentation

◆ MAX_LO_SCALAR