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

#include <fixed_base.hpp>

Inheritance diagram for 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 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 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< barretenberg::fr, 2 >	get_basic_fixed_base_table_values (const std::array< uint64_t, 2 > key)

Static Public Member Functions inherited from 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)

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

Static Public Attributes
static constexpr affine_element	LHS_GENERATOR_POINT

static constexpr affine_element	RHS_GENERATOR_POINT

static constexpr uint256_t	MAX_LO_SCALAR = uint256_t(1) << BITS_PER_LO_SCALAR

static const affine_element	lhs_base_point_lo = LHS_GENERATOR_POINT

static const affine_element	lhs_base_point_hi = element(lhs_base_point_lo) * MAX_LO_SCALAR

static const affine_element	rhs_base_point_lo = RHS_GENERATOR_POINT

static const affine_element	rhs_base_point_hi = element(rhs_base_point_lo) * MAX_LO_SCALAR

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 Public Attributes inherited from 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.

Member Function Documentation

◆ generate_basic_fixed_base_table()

template<size_t multitable_index>

template BasicTable 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

◆ generate_generator_offset()

template<size_t num_table_bits>

grumpkin::g1::affine_element 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

◆ generate_single_lookup_table()

table::single_lookup_table 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

◆ generate_tables()

template<size_t num_bits>

template table::fixed_base_scalar_mul_tables plookup::fixed_base::table::generate_tables< table::BITS_PER_HI_SCALAR > ( 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

◆ get_fixed_base_table()

template<size_t multitable_index, size_t num_bits>

template MultiTable plookup::fixed_base::table::get_fixed_base_table< 3, table::BITS_PER_HI_SCALAR > ( 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

◆ get_generator_offset_for_table_id()

std::optional< grumpkin::g1::affine_element > 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>

◆ get_lookup_table_ids_for_point()

std::optional< std::array< MultiTableId, 2 > > 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>>

◆ lookup_table_exists_for_point()

bool 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

Member Data Documentation

◆ fixed_base_table_offset_generators

const std::array< table::affine_element, table::NUM_FIXED_BASE_MULTI_TABLES > plookup::fixed_base::table::fixed_base_table_offset_generators

static

Initial value:

= {
        table::generate_generator_offset<BITS_PER_LO_SCALAR>(lhs_base_point_lo),
        table::generate_generator_offset<BITS_PER_HI_SCALAR>(lhs_base_point_hi),
        table::generate_generator_offset<BITS_PER_LO_SCALAR>(rhs_base_point_lo),
        table::generate_generator_offset<BITS_PER_HI_SCALAR>(rhs_base_point_hi),
    }

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.

◆ fixed_base_tables

const table::all_multi_tables plookup::fixed_base::table::fixed_base_tables

static

Initial value:

= {
    table::generate_tables<BITS_PER_LO_SCALAR>(lhs_base_point_lo),
    table::generate_tables<BITS_PER_HI_SCALAR>(lhs_base_point_hi),
    table::generate_tables<BITS_PER_LO_SCALAR>(rhs_base_point_lo),
    table::generate_tables<BITS_PER_HI_SCALAR>(rhs_base_point_hi),
}

◆ LHS_GENERATOR_POINT

constexpr affine_element plookup::fixed_base::table::LHS_GENERATOR_POINT

staticconstexpr

Initial value:

=

crypto::generator_data<curve::Grumpkin>::precomputed_generators[0]

crypto::generator_data

class that stores precomputed generators used for Pedersen commitments and Pedersen hashes

Definition: generator_data.hpp:40

◆ RHS_GENERATOR_POINT

constexpr affine_element plookup::fixed_base::table::RHS_GENERATOR_POINT

staticconstexpr

Initial value:

=

crypto::generator_data<curve::Grumpkin>::precomputed_generators[1]

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

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

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Function Documentation

◆ generate_basic_fixed_base_table()

◆ generate_generator_offset()

◆ generate_single_lookup_table()

◆ generate_tables()

◆ get_fixed_base_table()

◆ get_generator_offset_for_table_id()

◆ get_lookup_table_ids_for_point()

◆ lookup_table_exists_for_point()

Member Data Documentation

◆ fixed_base_table_offset_generators

◆ fixed_base_tables

◆ LHS_GENERATOR_POINT

◆ RHS_GENERATOR_POINT