Generates plookup tables required to perform fixed-base scalar multiplication over a fixed number of points.
More...
|
| 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 terms: { [G] + 0.[P] , [G] + 1.[P], ..., [G] + (MAX_TABLE_SIZE - 1).[P] }.
|
| |
| 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 set of basic tables required to traverse a num_bits sized lookup.
|
| |
| template<size_t num_table_bits> |
| static affine_element | compute_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) |
| | Returns true iff provided point is one of the two for which we have a precomputed lookup table.
|
| |
| static std::array< MultiTableId, 2 > | get_lookup_table_ids_for_point (const affine_element &input) |
| | Given a point that is one of the two for which we have a precomputed lookup table, return the IDs corresponding to the LO_SCALAR, HI_SCALAR MultiTables used to compute a fixed-base scalar mul with this point.
|
| |
| static 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) |
| |
| template<size_t multitable_index> |
| static constexpr size_t | get_num_bits_of_multi_table () |
| | Returns the number of scalar mul bits we are traversing in multitable with the given index.
|
| |
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.
template<size_t num_table_bits>
For a fixed-base lookup of size num_table_bits and an input base point input, return the total contribution from the offset generators in the scalar multiplication output.
Each lookup table i contains entries of the form: G_i + j*[2^(iw)*P] for j in [0, 2^w) where G_i is a unique offset generator that prevents point-at-infinity edge cases. The scalar multiplication result k*P is computed as: k*P = sum_i(table_lookup(k_i)) - sum_i(G_i) This method returns the correction term sum_i(G_i) that must be subtracted.
- Note
- We need the base point as an input parameter because we derive the offset generators using our hash-to-curve algorithm, where the base point is used as the domain separator. This ensures generator points cannot collide with base points without solving the discrete logarithm problem.
- Template Parameters
-
| num_table_bits | The total number of bits in the scalar multiplication |
- Parameters
-
| input | The base point being multiplied |
- Returns
- grumpkin::g1::affine_element The sum of all offset generators: sum_i(G_i)
Definition at line 92 of file fixed_base.cpp.
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 321 of file fixed_base.cpp.
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.
Creates a BasicTable for a specific bit-slice of the scalar multiplication. Each table covers w = BITS_PER_TABLE bits of the scalar at position table_index*w. The table stores precomputed points: (index, x-coord, y-coord) for index in [0, 2^w). For the last table in a multitable, the size may be smaller if remaining bits < w.
- Template Parameters
-
| multitable_index | Which of our 4 multitables (LEFT_LO/HI, RIGHT_LO/HI) this table belongs to |
- Parameters
-
| id | The unique and fixed BasicTableId for this table |
| basic_table_index | The circuit table index (e.g. idx = i means this is the i'th table used in the circuit) |
| table_index | The bit-slice position (0 = least significant slice) (0 <= table_index < NUM_TABLES_IN_MULTITABLE) |
- Returns
- BasicTable containing the precomputed points and lookup function
Definition at line 202 of file fixed_base.cpp.
template<size_t num_bits>
For a given base point [P], compute the set of basic tables required to traverse a num_bits sized lookup.
Generates NUM_TABLES-many basic tables, one for each of the points: { [P] * 2^(BITS_PER_TABLE * i) : i = 0, 1, ..., NUM_TABLES - 1 }
- Template Parameters
-
- Parameters
-
- Returns
- table::fixed_base_scalar_mul_tables
Definition at line 55 of file fixed_base.cpp.
template<size_t multitable_index, size_t num_bits>
Generate a multi-table that describes the lookups required to cover a fixed-base-scalar-mul of num_bits
Creates a MultiTable that manages multiple BasicTables to perform scalar multiplication. The scalar is split into ceil(num_bits/BITS_PER_TABLE) slices, each handled by a BasicTable. This function sets up the metadata and function pointers for combining the basic table lookups.
- Template Parameters
-
| multitable_index | Which of our 4 multitables (0=LEFT_LO, 1=LEFT_HI, 2=RIGHT_LO, 3=RIGHT_HI) |
| num_bits | Total bits in the scalar (either BITS_PER_LO_SCALAR=128 or BITS_PER_HI_SCALAR=126) |
- Parameters
-
| id | The MultiTableId identifying this multi-table |
- Returns
- MultiTable containing metadata for combining basic table outputs
Definition at line 246 of file fixed_base.cpp.
Static Public Member Functions inherited from bb::plookup::FixedBaseParams